Kapitel 4 Lineare Gleichungssysteme

In den Wirtschaftswissenschaften und speziell in der Ökonometrie spielen große lineare Gleichungssysteme eine extrem wichtige Rolle. Auch wenn die tatsächlichen wirtschaftlichen Zusammenhänge nichtlinear sind, können sie trotzdem oft in eine lineare Form transformiert werden. Außerdem sind lineare Zusammenhänge in vielen Fällen gute lokale Approximationen.

4.1 Notation

Lineare Gleichungssysteme lassen sich in allgemeiner Form so schreiben: \[ \begin{align*} a_{11}x_1 + a_{12}x_2 + a_{13}x_3+\ldots +a_{1n}x_n &= b_1\\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3+\ldots +a_{2n}x_n &= b_2\\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3+\ldots +a_{3n}x_n &= b_3\\ &\vdots\\ a_{m1}x_1 + a_{m2}x_2 + a_{m3}x_3+\ldots +a_{mn}x_n &= b_m \end{align*} \] Das Gleichungssystem hat \(m\) Gleichungen, es gibt \(n\) Unbekannte, nämlich \(x_1,x_2,\ldots,x_n\). Alle anderen Größen (also die \(b_{i}\) und die \(a_{ij}\) für \(i=1,\ldots,m\) und \(j=1,\ldots,n\)) sind gegebene reelle Zahlen, sie werden oft Koeffizienten oder Parameter genannt. Natürlich ist es auch möglich, dass einige Koeffizienten wegfallen, indem sie auf Null gesetzt werden.

Beispiel:

Das folgende lineare Gleichungssystem hat zwei Gleichungen und zwei Unbekannte: \[ \begin{align*} -2x_1+5x_2 &= 1\\ x_1-3x_2&=4 \end{align*} \] Nicht immer ist die Form bereits so klar vorgegeben. Das gleiche System könnte auch so aussehen, \[ \begin{align*} 5x_2 &= 1+2x_1\\ x_1-x_2\times 3-4&=0. \end{align*} \]

Wie kehren zurück zum allgemeinen Gleichungssystem mit \(m\) Gleichungen und \(n\) Unbekannten. Die linke Seite des Systems hat exakt die Struktur einer Matrixmultiplikation. Das allgemeine Gleichungssystem kann in Matrixnotation so geschrieben werden: \[ \left[ \begin{array}{ccccc} a_{11} & a_{12} & a_{13} & \ldots & a_{1n}\\ a_{21} & a_{22} & a_{23} & \ldots & a_{2n}\\ a_{31} & a_{32} & a_{33} & \ldots & a_{3n}\\ \vdots &\vdots &\vdots &\ddots&\vdots\\ a_{m1} & a_{m2} & a_{m3} & \ldots & a_{mn} \end{array} \right] \left[ \begin{array}{c} x_1\\ x_2\\ x_3\\ \vdots\\ x_n \end{array} \right] = \left[ \begin{array}{c} b_1\\ b_2\\ b_3\\ \vdots\\ b_m \end{array} \right] \] oder kompakter \[ \underset{m\times n\rule{0mm}{7pt}}{\mathbf{A}}~\underset{n\times 1}{\mathbf{x}}=\underset{m\times 1}{\mathbf{b}}. \] Man erkennt sofort, dass die Matrixnotation die Sache nicht komplizierter, sondern im Gegenteil erheblich einfacher und übersichtlicher macht.

In dieser Gleichung sind die Matrix \(\mathbf{A}\) und der Vektor \(\mathbf{b}\) gegeben, und der Vektor \(\mathbf{x}\) ist gesucht.

4.2 Reguläre Matrix

Wenn das lineare Gleichungssystem eine reguläre (also invertierbare) Koeffizientenmatrix \(\mathbf{A}\) hat, gibt es eine eindeutige Lösung und sie ist relativ leicht zu finden. Die Matrix ist regulär, wenn \(m=n\) und \(rg(\mathbf{A})=n\) bzw. \(\det(\mathbf{A})\neq 0\) ist. Die eindeutige Lösung erhält man durch Auflösen des Gleichungssystems \[ \mathbf{Ax}=\mathbf{b} \] nach \(\mathbf{x}\). Die Lösung ist der Vektor \[ \mathbf{x}=\mathbf{A}^{-1}\mathbf{b}. \]

Beispiel:

In Matrixschreibweise sieht das System \[ \begin{align*} -2x_1+5x_2 &= 1\\ x_1-3x_2&=4 \end{align*} \] mit zwei Gleichungen und zwei Unbekannten so aus: \[ \left[ \begin{array}{cc} -2 & 5 \\ 1 & -3 \end{array} \right] \left[ \begin{array}{c} x_1\\ x_2 \end{array} \right]= \left[ \begin{array}{c} 1\\ 4 \end{array} \right]. \] Sie kennen vermutlich bereits mehrere Ansätze, wie ein solches einfaches Gleichungssystem gelöst werden kann. An dieser Stelle nehmen wir aber zuerst einmal einen anderen Standpunkt ein und interpretieren das Gleichungssystem geometrisch. Wir wissen aus Kapitel 2, dass eine Matrix als Kurzschreibweise für eine lineare Transformation aufgefasst werden kann. In diesem Beispiel bedeutet das, dass \[ \left[ \begin{array}{cc} -2 & 5 \\ 1 & -3 \end{array} \right] \left[ \begin{array}{c} x_1\\ x_2 \end{array} \right] \] den Punkt \((x_1,x_2)\) einer linearen Transformation unterzieht. Der Punkt landet also irgendwo anders im Raum.

Die Gleichung besagt nun, dass der gesuchte Punkt \((x_1,x_2)\) auf dem Punkt \((1,4)\) landen soll. Die Frage ist also: Welcher Punkt \((x_1,x_2)\) landet auf \((1,4)\), wenn man die lineare Transformation \[ \left[ \begin{array}{cc} -2 & 5 \\ 1 & -3 \end{array} \right] \] auf ihn anwendet? Um die Antwort zu finden, können wir die lineare Transformation “rückwärts” laufen lassen. Wir transformieren den Zielvektor \((1,4)\) mit der inversen Matrix und finden so den gesuchten Ursprungsvektor. Die Inverse ist \[ \left[ \begin{array}{cc} -3 & -5 \\ -1 & -2 \end{array} \right]. \] Deshalb ist \[ \left[ \begin{array}{cc} -3 & -5 \\ -1 & -2 \end{array} \right] \left[ \begin{array}{c} 1\\ 4 \end{array} \right]= \left[ \begin{array}{c} -23\\ -9 \end{array} \right] \] die gesuchte Lösung. Zur Kontrolle berechnen wir die lineare Transformation des Punkts \((-23,-9)\). Wir erhalten \[ \left[ \begin{array}{cc} -2 & 5 \\ 1 & -3 \end{array} \right] \left[ \begin{array}{c} -23\\ -9 \end{array} \right]= \left[ \begin{array}{c} 1\\ 4 \end{array} \right]. \] Die Lösung ist also korrekt. Das lineare Gleichungssystem \[ \begin{align*} -2x_1+5x_2 &= 1\\ x_1-3x_2&=4 \end{align*} \] hat die Lösung \[ \begin{align*} x_1 &= -23\\ x_2 &= -9. \end{align*} \] In diesem einfachen Fall mit nur zwei Gleichungen und nur zwei Unbekannten wären andere Lösungsverfahren vielleicht schneller gewesen. Die Berechnung der Inversen zur Lösung der Gleichung hat aber den Vorteil, dass sie auch für höhere Dimensionen gut funktioniert, sofern das Gleichungssystem genauso viele Gleichungen wie Unbekannte hat (\(m=n\)). Außerdem muss die Matrix \(\mathbf{A}\) natürlich invertierbar sein, um eine Lösung zu finden. Zur Erinnerung: Eine \((n\times n)\)-Matrix \(\mathbf{A}\) ist invertierbar, wenn \(\det(\mathbf{A})\neq 0\) bzw. wenn sie den Rang \(n\) hat.

Die Inversionsmethode lässt sich - auch in höheren Dimensionen - leicht in R implementieren, wenn alle Koeffizienten numerisch bekannt sind.

Beispiel:

Wir betrachten die \((6\times 6)\)-Matrix

A <- matrix(c( 0, 3, 0, 0, 7, 5,
               9,10, 5, 9, 7, 4,
               1,-1, 5, 8, 4, 7,
               9, 0, 3,-1, 0, 5,
              -2, 2,-3,-1,10, 9,
               7, 6, 3, 1, 3, 9), 6, 6)
A
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    0    9    1    9   -2    7
#> [2,]    3   10   -1    0    2    6
#> [3,]    0    5    5    3   -3    3
#> [4,]    0    9    8   -1   -1    1
#> [5,]    7    7    4    0   10    3
#> [6,]    5    4    7    5    9    9

Die Determinante dieser Matrix beträgt

det(A)
#> [1] 110413

Der Koeffizientenvektor \(\mathbf{b}\) auf der rechten Seite des Gleichungssystems sei

b <- c(60, 40, 25, 21, 11, 47)
b
#> [1] 60 40 25 21 11 47

Die Lösung des Gleichungssystems erhalten wir, indem wir die Inverse \(\mathbf{A}^{-1}\) von links an den Vektor \(\mathbf{b}\) heranmultiplizieren. Dabei ergibt sich

solve(A) %*% b
#>              [,1]
#> [1,] -4.00000e+00
#> [2,]  2.00000e+00
#> [3,]  4.44089e-16
#> [4,]  1.00000e+00
#> [5,]  1.00000e+00
#> [6,]  5.00000e+00

bzw. auf viele Stellen nach dem Komma gerundet

round(solve(A) %*% b, 12)
#>      [,1]
#> [1,]   -4
#> [2,]    2
#> [3,]    0
#> [4,]    1
#> [5,]    1
#> [6,]    5

Der Vektor \[ \mathbf{x}=\left[ \begin{array}{r} -4\\2\\0\\1\\1\\5 \end{array} \right] \] ist also die (einzige) Lösung des Gleichungssystems.

4.3 Allgemeiner Fall

Wenn die Matrix \(\mathbf{A}\) singulär ist, gibt die Funktion solve eine Fehlermeldung aus und das Programm bricht ab, wie das folgende Beispiel zeigt:

A <- matrix(1:9, 3, 3)
b <- c(-4,2,9)
solve(A) %*% b

#> Fehler in solve.default(A) :
#> Lapackroutine dgesv: System ist genau singulär: U[3,3] = 0

Da nicht alle Gleichungssysteme die Bedingungen \(m=n\) und \(rg(\mathbf{A})=n\) erfüllen, betrachten wir nun den allgemeinen Fall. Wenn es nicht unbedingt eine eindeutige Lösung gibt, stellen sich diese Fragen: Gibt es überhaupt eine Lösung des Gleichungssystems? Und wenn ja, gibt es möglicherweise mehr als eine Lösung? Die nachfolgende Darstellung orientiert sich eng an dem Lehrbuch von Mosler, Dyckerhoff und Scheicher (s. Literaturübersicht in Kap. A).

Leider lässt sich an dem Gleichungssystem \(\mathbf{Ax}=\mathbf{b}\) normalerweise nicht unmittelbar erkennen, ob es überhaupt eine Lösung hat oder ob es sogar mehr als eine Lösung gibt. Um das Problem anzugehen, schreiben wir das Gleichungssystem kompakter auf, indem wir den Vektor \(\mathbf{b}\) als Extraspalte rechts neben die Koeffizientenmatrix \(\mathbf{A}\) setzen, \[ \mathbf{A}|\mathbf{b}. \] Dann formen wir das Gleichungssystem Schritt für Schritt mit “elementaren Zeilenumformungen” um. Ziel ist es, das System in eine Form zu bringen, an der leicht und schnell erkennbar ist, wie die Lösungsmenge aussieht. Als Lösungsmenge bezeichnen wir die Menge aller Vektoren \(\mathbf{x}\), die für gegebene Koeffizienten \(\mathbf{A}\) und \(\mathbf{b}\) die Gleichung \(\mathbf{Ax}=\mathbf{b}\) erfüllen. Die Lösungsmenge des linearen Gleichungssystems schreiben wir allgemein als \(L(\mathbf{A},\mathbf{b})\).

Die erlaubten elementaren Zeilenumformungen sind:

• Zwei Zeilen werden miteinander vertauscht. Offensichtlich ändert sich die Lösungsmenge nicht dadurch, dass die Gleichungen in einer anderen Reihenfolge geschrieben werden.

• Alle Elemente einer Zeile \(i\) werden mit einer Konstanten ungleich 0 multipliziert. Die Lösungsmenge wird durch diese Umformung nicht verändert, denn wenn ein Vektor \(\mathbf{x}\) eine Lösung ist, dann erfüllt er die Gleichung \(i\), d.h. \[ a_{i1}x_1+\ldots+a_{in}x_n=b_i. \] Multipliziert man beide Seiten mit einer Konstanten \(\lambda\neq 0\), bleibt die Gleichung erfüllt.

• Eine Zeile wird durch die Summe (oder Differenz) dieser Zeile und dem Vielfachen einer anderen Zeile ersetzt. Ohne Einschränkung der Allgemeinheit betrachten wir die ersten beiden Zeilen und ersetzen die erste Zeile durch die Summe aus der ersten Zeile und dem \(\lambda\)-Fachen der zweiten Zeile. Die beiden Zeilen lauten nach der Umformung also \[ \begin{align*} (a_{11}+\lambda a_{21})x_1& +\ldots &+(a_{1n}+\lambda a_{2n})x_n &= b_1+\lambda b_2\\ a_{21}x_1 & +\ldots &+a_{2n}x_n &=b_2. \end{align*} \] An dieser Darstellung wird deutlich, dass ein Vektor \(\mathbf{x}\), der die ersten beiden ursprünglichen Gleichungen erfüllt, auch diese beiden Gleichungen erfüllt. Die Lösungsmenge ändert sich also nicht.

Neben diesen drei Zeilenumformungen brauchen wir in manchen Situationen zusätzlich eine Vertauschung der Spalten. Das entspricht einer Umbenennung der Variablen, also der Elemente des Vektors \(\mathbf{x}\).

Die Zeilenumformungen (und ggf. die Spaltenvertauschung mit einer Umbenennung der Elemente von \(\mathbf{x}\)) werden nun gezielt so eingesetzt, dass man am Ende das Schema \[ \mathbf{A|b} \] in ein neues Schema \[ \mathbf{\tilde A}|\mathbf{\tilde b} \] überführt, das folgende generische Form hat (bei einer Spaltenvertauschung stehen in der Kopfzeile die Elemente von \(\mathbf{x}\) in einer anderen Reihenfolge): \[ \begin{array}{cccccc|c} x_1 & \ldots & x_k & x_{k+1} & \ldots & x_n & \mathbf{\tilde b}\\\hline 1 & \ldots & 0 & \tilde a_{1k+1} & \ldots & \tilde a_{1n} & \tilde b_1\\ \vdots & \ddots & \vdots &\vdots & \ddots & \vdots & \vdots\\ 0 & \ldots & 1 & \tilde a_{kk+1} & \ldots & \tilde a_{kn} & \tilde b_k\\ \hline 0 & \ldots& \ldots& \ldots& \ldots & 0 & \tilde b_{k+1}\\ \vdots & & & & & \vdots & \vdots\\ 0 & \ldots& \ldots& \ldots& \ldots & 0 & \tilde b_m\\ \end{array} \] Das neue Schema hat genauso viele Zeilen (nämlich \(m\)) wie das ursprüngliche Schema. Oben links steht eine \((k\times k)\)-Einheitsmatrix, die unteren Zeilen bestehen links vom senkrechten Strich nur aus Nullen. Rechts neben der Einheitsmatrix stehen beliebige Einträge. Und rechts vom Strich stehen ebenfalls beliebige Einträge.

Nicht immer tauchen alle diese Bestandteile auf, es kann durchaus passieren, dass im unteren Bereich keine Zeilen mit Nullen stehen oder dass die Einheitsmatrix bis an den senkrechten Strich heranreicht. Daher untersuchen wir vier verschiedene Fälle:

• Erstens, die Einheitsmatrix erstreckt sich bis zum senkrechten Strich, d.h. \(k=m=n\). Dies ist der Fall einer regulären Matrix \(\mathbf{A}\), den wir bereits im vorhergehenden Abschnitt behandelt haben. Es gibt also genau eine Lösung. Man findet sie z.B. mit Hilfe der inversen Matrix, \(\mathbf{x}=\mathbf{A}^{-1}\mathbf{b}\).

• Zweitens, der untere Bereich mit den Nullzeilen fehlt, aber rechts von der Einheitsmatrix gibt es noch Spalten, d.h. \(k=m<n\). Da eine allgemeine Notation unübersichtlich wird, betrachten wir beispielhaft den Fall mit \(k=m=3\) Gleichungen und \(n=4\) Unbekannten. \[ \begin{array}{cccc|c} x_1 & x_2 & x_3 & x_4 & \mathbf{\tilde b}\\\hline 1 & 0 & 0 & \tilde a_{14} & \tilde b_1\\ 0 & 1 & 0 & \tilde a_{24} & \tilde b_2\\ 0 & 0 & 1 & \tilde a_{34} & \tilde b_3 \end{array} \] In diesem Fall kann man \(x_4\) beliebig wählen, die restlichen drei Unbekannten ergeben sich dann als \[ \begin{align*} x_1 &= \tilde b_1-\tilde a_{14}x_4\\ x_2 &= \tilde b_2-\tilde a_{24}x_4\\ x_3 &= \tilde b_3-\tilde a_{34}x_4. \end{align*} \] Mit anderen Worten: Es gibt unendliche viele Lösungen.

• Drittens, es gibt im unteren Bereich Zeilen mit Nullen, d.h. \(k<m\), und \(\tilde b_{k+1}=\ldots=\tilde b_{m}=0\), d.h. in den Nullzeilen sind auch rechts vom senkrechten Strich nur Nullen. In diesem Fall können die unteren \(m-k\) Zeilen (die ja nur Nullen enthalten) ersatzlos gestrichen werden. Man gelangt auf diese Weise wieder zum vorhergehenden Fall. Es gibt also wieder unendliche viele Lösungen und sie werden wie oben beschrieben gefunden.

• Viertens, es gibt im unteren Bereich Zeilen mit Nullen, d.h. \(k<m\), aber mindestens einer der Werte \(\tilde b_{k+1},\ldots,\tilde b_{m}\) ist ungleich 0. Angenommen \(\tilde b_m\neq 0\), dann müsste die Gleichung \[ 0\cdot x_1 + \ldots + 0\cdot x_n = \tilde b_m \neq 0 \] erfüllt sein, was natürlich nicht möglich ist. In dieser Situation hat das Gleichungssystem keine Lösung.

4.4 Cramers Regel

In wirtschaftswissenschaftlichen Texten werden lineare Gleichungssysteme, die genauso viele Unbekannte wie Gleichungen haben (\(m=n\)), oft mit Cramers Regel gelöst. Sie ist besonders praktisch, wenn das Gleichungssystem eher klein ist (und sogar oft nur zwei oder drei Gleichungen umfasst) und die Matrixelemente nur symbolisch, nicht numerisch bekannt sind.

Cramers Regel besagt, dass die Unbekannte \(x_i\) in dem Gleichungssystem \(\mathbf{Ax}=\mathbf{b}\) wie folgt gefunden werden kann:

• Zuerst ersetzt man die \(i\)-te Spalte in \(\mathbf{A}\) durch den Vektor \(\mathbf{b}\). Wir nennen die Matrix, die sich ergibt, \(\mathbf{\tilde A}_i\),

\[ \mathbf{\tilde A}_i=\left[ \begin{array}{ccccccc} a_{11} & \ldots & a_{1i-1} & b_1 & a_{1i+1} & \ldots &a_{1n}\\ a_{21} & \ldots & a_{2i-1} & b_2 & a_{2i+1} & \ldots & a_{2n}\\ \vdots && \vdots & \vdots &\vdots &&\vdots \\ a_{n1} & \ldots & a_{ni-1} & b_n & a_{ni+1} & \ldots & a_{nn} \end{array} \right]. \] (Natürlich kann auch die erste oder letzte Spalte ersetzt werden.)

• Nun bestimmt man die Determinante von \(\mathbf{\tilde A}_i\) und die Determinante von \(\mathbf{A}\).

• Die Lösung für das \(i\)-te Element von \(\mathbf{x}\) lautet \[ x_i = \frac{\det(\mathbf{\tilde A}_i)}{\det(\mathbf{A})}. \] Cramers Regel ist vor allem dann hilfreich, wenn man sich vor allem für einzelne Elemente des Lösungsvektors interessiert. Wenn die Koeffizientenmatrix \(\mathbf{A}\) singulär ist, dann ist die Determinante im Nenner 0. In diesem Fall kann Cramers Regel keine Lösung finden, da es keine oder zumindest keine eindeutige Lösung gibt.

Beispiel:

Als Beispiel betrachten wir ein kleines Gleichungssystem mit zwei Unbekannten und zwei Gleichungen, \[ \begin{align*} -2x_1+5x_2 &= 1\\ x_1-3x_2&=4. \end{align*} \] Die Bestandteile sind in Matrixnotation \[ \mathbf{A} = \left[ \begin{array}{cc} -2 & 5\\ 1 & -3 \end{array} \right],\quad \mathbf{x} = \left[ \begin{array}{c} x_1\\ x_2 \end{array} \right],\quad \mathbf{b}=\left[ \begin{array}{c} 1\\ 4 \end{array} \right]. \] Die Determinante von \(\mathbf{A}\) beträgt \(-2\cdot(-3)-5\cdot 1=1\), das System hat also eine eindeutige Lösung. Um das erste Element des Lösungsvektors zu finden, setzen wir den Vektoren der Konstanten, \(\mathbf{b}\), in die erste Spalte ein und bestimmen wir die Determinante von \[ \mathbf{\tilde A}_1=\left[ \begin{array}{cc} 1 & 5\\ 4 & -3 \end{array} \right]. \] Die Determinante ist \(1\cdot (-3)-5\cdot 4=-23\), so dass \[ x_1=\frac{-23}{1}=-23 \] die Lösung ist. Für das zweite Elemente berechnen wir die Determinante von \[ \mathbf{\tilde A}_2=\left[ \begin{array}{cc} -2 & 1\\ 1 & 4 \end{array} \right]. \] Sie ist \(-2\cdot 4-1\cdot 1=-9\), so dass die Lösung für \(x_2\) \[ x_2=\frac{-9}{1}=-9 \] ist.