Gleichungssysteme und Matrizen

 

1.1. Einleitung

Der Einfachste Fall eines linearen Gleichungssystems ist ein System mit n Gleichungen und n Unbekannten. Dieses kann mit Verfahren wie der Cramerschen Regel (praktikabel nur bis n=3) oder der Gaußschen Elimination gelöst werden.
Die Idee der Gaußschen Elimination ist, alle Gleichungen in eine Matrix zu schreiben und miteinander zu kombinieren, bis eine Gleichung mit einer Unbekannten herauskommt, die man dann in die anderen Gleichungen einsetzen kann, um die anderen Unbekannten zu bestimmen.

Ein einfaches Beispiel für ein Gleichungssystem mit 3 Gleichungen und 3 Unbekannten:

\begin{array}{*{20}{c}} 2u & +v & +w &  = 1  \\ 4u & +v &  &  = -2  \\ - 2u & +2v & +w &  = 7  \\ \end{array}

Die 2u links oben bezeichnet man als “Pivot-Element”. Dieses wird später noch eine Rolle
spielen.

Dieses System wird mit folgenden Einzelschritten gelöst:
a) Subtrahiere das 2-fache der I. Gleichung von der II.
b) Subtrahiere das (-1)-fache der I. Gleichung von der III.

\begin{array}{*{20}{c}} 2u & +v & +w &  = 1  \\ & -v & -2w &  = -4  \\ & +3v & +2w &  = 8  \\ \end{array}

Das Pivotelement ist nun das -v vorne in der II. Gleichung.
c) Subtrahiere das (-3)-fache der II. Gleichung von der III.

\begin{array}{*{20}{c}} 2u & +v & +w &  = 1  \\ & -v & -2w &  = -4  \\ &+& -4w &  =-4  \\  \end{array}

Die letzte Gleichung liefert: w = 1
Eingesetzt in die II. Gleichung liefert das: v = 2
Eingesetzt in die I. Gleichung liefert das: u = -1

Wann bricht der Gaußsche Algorithmus vorzeitig ab?
Obiges Beispiel hatte die Pivots 2 und -1, also beide ungleich 0. Dabei konnte man die -1 nicht sofort sehen, da sie erst im Laufe des Verfahrens zustande kam. Falls einer der auftretenden Einträge auf der Diagonalen = 0 ist, stoppt der Eliminationsprozess.
Eine eventuelle Abhilfe bringt das Vertauschen von Zeilen.

1.2. Matrixschreibweise mit Matrixmultiplikation

Die Unbekannten können in einen Vektor zusammengefasst werden:

\vec x = \left( {\begin{array}{*{20}{c}} u  \\ v  \\ w  \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} {-1}  \\ 2  \\ 1  \\ \end{array} } \right)

die hinter dem = stehenden Ergebnisse in einen anderen:

\vec b = \left( {\begin{array}{*{20}{c}} 1  \\ {-2}  \\ 7  \\  \end{array} } \right)

Die Gleichungen selbst können als eine Matrix dargestellt werden, wobei die Einträge die Faktoren vor den Unbekannten sind:

A = \left( {\begin{array}{*{20}{c}} 2 & 1 & 1  \\ 4 & 1 & 0  \\ {-2} & 2 & 1  \\  \end{array} } \right)

Diese Matrix nennt man Koeffizientenmatrix.
Um die beiden Vektoren und die Matrix nun kombinieren zu können, benötigt man ein paar Grundrechenoperationen mit Vektoren und Matrizen.

Elementweise Addition von Matrizen

\left( {\begin{array}{*{20}{c}} 1 & 2 & 3  \\ 4 & 5 & 6  \\  \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 0 & {-5} & {-10}  \\ {-3} & {-6} & {-9}  \\  \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 1 & {-3} & {-7}  \\ 1 & {-1} & {-3}  \\  \end{array} } \right)

Die Dimensionen der Matrizen müssen für diese Operation gleich sein.

\left( {\begin{array}{*{20}{c}} 1  \\ 2  \\  \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 3  \\ 4  \\ 5  \\  \end{array} } \right)

oder

\left( {\begin{array}{*{20}{c}} 1 & 3  \\ 2 & 4  \\  \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 5 & 6 & 7  \\ 8 & 9 & 0  \\  \end{array} } \right)

kann nicht berechnet werden.

Skalare Multiplikation von Matrizen

a \cdot \left( {\begin{array}{*{20}{c}} 5 & 6 & 7  \\ 8 & 9 & 0  \\  \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 5a & 6a & 7a  \\ 8a & 9a & 0  \\ \end{array} } \right)

Multiplikation von Matrix und Vektor

Das Ziel ist es, das Gleichungssystem mit Vektoren und Matrizen darzustellen in der Form

A \cdot \vec x+\vec b

Dies bedeutet ausgeschrieben:

\left( {\begin{array}{*{20}{c}} 2 & 1 & 1  \\ 4 & 1 & 0  \\ {-2} & 2 & 1  \\  \end{array} } \right) \cdot \left( {\begin{array}{*{20}{c}} u  \\ v  \\ w  \\  \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 1  \\ {-2}  \\ 7  \\  \end{array} } \right)

An dieser Stelle zwei Definitionen:

Ein n-dimensionaler Spaltenvektor ist eine (n x 1)-Matrix.
Beispiel:

\left( {\begin{array}{*{20}{c}} u  \\ v  \\ w  \\  \end{array} } \right)

Ein n-dimensionaler Zeilenvektor ist eine (1 x n)-Matrix.
Beispiel:

\left( {\begin{array}{*{20}{c}} u & v & w  \\  \end{array} } \right)

Wir wenden uns nun wieder dem Gleichungssystem zu. Die 1. Komponente des Produktes Ax muss entstehen durch eine “Multiplikation” der ersten Zeile in A mit dem Spaltenvektor x:

\left( {\begin{array}{*{20}{c}} 2 & 1 & 1  \\  \end{array} } \right) \cdot \left( {\begin{array}{*{20}{c}} u  \\ v  \\ w  \\  \end{array} } \right) = 2u+1v+1w

Dementsprechend verhält es sich mit den anderen Komponenten. Man erhält also das skalare Produkt (“innere Produkt”) immer durch die Multiplikation eines Zeilenvektors mit einem Spaltenvektor. Das Produkt aus der mehrzeiligen Matrix A und dem Vektor x kombiniert drei solche inneren Produkte und ist daher ein dreidimensionaler Spaltenvektor:

A \cdot \vec x = \left( {\begin{array}{*{20}{c}} {2u+1v+1w}  \\ {4u+1u+0w}  \\ {-2u+2v+1w}  \\  \end{array} } \right)

Wir betrachten die Multiplikation von einer Matrix und einem Vektor noch ein mal etwas genauer an Hand eines Zahlenbeispiels:

\left( {\begin{array}{*{20}{c}} 2 & 1 & 1  \\ 4 & 1 & 0  \\ - 2 & 2 & 1  \\  \end{array} } \right) \cdot \left( {\begin{array}{*{20}{c}} - 1  \\ 2  \\ 1  \\  \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 2 \cdot \left( {-1} \right)+1 \cdot 2+1 \cdot 1  \\ 4 \cdot \left( {-1} \right)+1 \cdot 2+0 \cdot 1  \\ \left( {-2} \right) \cdot \left( {-1} \right)+2 \cdot 2+1 \cdot 1  \\  \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 1  \\ - 2  \\ 7  \\  \end{array} } \right)

Das Produkt Ax ist also eine Linearkombination der Spalten von A, wobei jede Spalte von A durch die jeweilige Komponente von x gewichtet wird. Im Beispiel:

\left( {\begin{array}{*{20}{c}} 2 & 1 & 1  \\ 4 & 1 & 0  \\ {-2} & 2 & 1  \\ \end{array} } \right) \cdot \left( {\begin{array}{*{20}{c}} {-1}  \\ 2  \\ 1  \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 2  \\ 4  \\ {-2}  \\ \end{array} } \right) \cdot \left( {-1} \right)+\left( {\begin{array}{*{20}{c}} 1  \\ 1  \\ 2  \\ \end{array} } \right) \cdot \left( 2 \right)+\left( {\begin{array}{*{20}{c}} 1  \\ 0  \\ 1  \\ \end{array} } \right) \cdot \left( 1 \right) = \left( {\begin{array}{*{20}{c}} {-2}  \\ {-4}  \\ 2  \\ \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 2  \\ 2  \\ 4  \\ \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 1  \\ 0  \\ 1  \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 1  \\ {-2}  \\ 7  \\ \end{array} } \right)

Wir verallgemeinern nun weiter und suchen eine allgemein gültige Formel für das Produkt von A und x. Dazu verwenden wir die folgenden Bezeichnungen:

Die Matrix A enthält die Einträge aij. Diese stehen in der i-ten Zeile in der j-ten Spalte. Dies ist wichtig zu beachten, da es gegen die Gewohnheit verstößt, dass die erste Koordinate die Horizontale und die Zweite die Vertikale bedeutet.
Wir schreiben kurz für eine m x n Matrix:

A = \left( {a_{ij} } \right)

Dabei läuft i von 1 bis m und j von 1 bis n. Die Formel in Indexschreibweise:

A\vec x = \sum\limits_{j = 1}^n {a_{ij}  \cdot x_j }

Folgerung:
Die durch eine Matrix A definierte Abbildung

A : \vec x \mapsto A \vec x

ist linear, das heißt es gilt:

A\left( {\vec x+\vec y} \right) = A\vec x+A\vec y

und

A\left( {\alpha  \cdot \vec x} \right) = \alpha  \cdot A\vec x

Dies gilt für alle Vektoren x, y mit Skalaren &alpha.

Die Matrixform eines Eliminationsschrittes

Wir gehen nun der Rechenoperation auf den Grund, auf der der Eliminationsschritt aufbaut.
Im Beispiel der Einzelschritt a), “Subtrahiere das 2-fache der I. Gleichung von der II. Gleichung”.
Dies bedeutet, dass auf der rechten Seite das 2-fache der 1. Komponente von b subtrahiert wird von der 2. Komponente. Dies lässt sich auch erreichen, indem wir den Vektor b mit folgender elementaren Matrix E multiplizieren:

E = \left( {\begin{array}{*{20}{c}} 1 & 0 & 0  \\ {-2} & 1 & 0  \\ 0 & 0 & 1  \\  \end{array} } \right)

Dies funktioniert, denn:

E \vec b = \left( {\begin{array}{*{20}{c}} 1 & 0 & 0  \\ {-2} & 1 & 0  \\ 0 & 0 & 1  \\  \end{array} } \right) \cdot \left( {\begin{array}{*{20}{c}} 1  \\ {-2}  \\ 7  \\  \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 1  \\ {-2}  \\ 0  \\  \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 0  \\ {-2}  \\ 0  \\  \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 0  \\ 0  \\ 7  \\  \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 1  \\ {-4}  \\ 7  \\  \end{array} } \right)

Um Gleichheit zu erhalten, muss die selbe Operation auf beiden Seiten durchgeführt werden. Der Vektor Ax muss daher mit E erweitert (multipliziert) werden. Es entsteht:

E\left( {A\vec x} \right) = E\vec b

Wir wollen uns an dieser Stelle von den Klammern lösen und schreiben:

EA \vec x

Für diese Operation brauchen wir die Matrixmultiplikation.

Matrixmultiplikation

Es gibt drei Zugänge zur Matrixmultiplikation.

1. aus der Gaußschen Elimination ist bekannt:
- die ursprüngliche Koeffizientenmatrix, die Matrix nach dem Eliminationsschritt a) und die Matrix E, die den Schritt durchführt.

In unserem Beispiel gilt offenbar für

E = \left( {\begin{array}{*{20}{c}} 1 & 0 & 0  \\ {-2} & 1 & 0  \\ 0 & 0 & 1  \\  \end{array} } \right)

und

A = \left( {\begin{array}{*{20}{c}} 2 & 1 & 1  \\ 4 & 1 & 0  \\ {-2} & 2 & 1  \\  \end{array} } \right)

EA = \left( {\begin{array}{*{20}{c}} 2 & 1 & 1  \\ 0 & {-1} & {-2}  \\ {-2} & 2 & 1  \\  \end{array} } \right)

Damit ist die Matrixmultiplikation konsistent mit den Zeilenoperationen des Eliminationsschrittes a)

2. Zugang: Hierfür benötigen wir eine weitere Anforderung an die Matrixmultiplikation, nämlich konsistenz mit der alten Definitino, das heißt ist B eine Matrix mit einer einzigen Spalte x, dann soll AB = Ax gelten.

Besteht B aus mehreren Spalten, z.B. x1, x2, x3, dann sollen die Spalten von AB gerade Ax1, Ax2, Ax3 sein.

Damit ist klar, wie die Matrixmultiplikation abzulaufen hat:
Arbeite das Matrixprodukt AB spaltenweise mit den Spalten von B ab. (Jede Zeile von A muss mit jeder Zeile von B zu einem inneren Produkt kombiniert werden. Die sich ergebenden Skalare sind die Einträge in die neue Matrix)

Zahlenbeispiel:
erste Spalte von EA = E “mal” die erste Spalte von A

= \left( {\begin{array}{*{20}{c}} 1 & 0 & 0  \\ {-2} & 1 & 0  \\ 0 & 0 & 1  \\ \end{array} } \right) \cdot \left( {\begin{array}{*{20}{c}} 2  \\ 4  \\ {-2}  \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 2  \\ {-4}  \\ 0  \\ \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 0  \\ 4  \\ 0  \\ \end{array} } \right)+\left( {\begin{array}{*{20}{c}} 0  \\ 0  \\ {-2}  \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} 2  \\ 0  \\ {-2}  \\ \end{array} } \right)

Entsprechend werden die anderen Spalten berechnet.

3. Zugang mit den einzelnen Einträgen der Matrix

Hier geht es um eine allgemeine Formel für die Berechnung des neuen Eintrags:
(AB)ij = inneres Produkt der i-ten Zeile von A und der j-ten Spalte von B

Damit das gut geht, muss die Anzahl der Spalten von A gleich der Anzahl der Zeilen von B sein.