1.3. Pivotisierung mittels Permutationen

Bisher haben wir immer angenommen, dass \(a_{j,j}^{(j)} \neq 0\) auf der Hauptdiagonalen gilt im \(j\)-ten Schritt des Gauss-Eliminationsverfahrens für \(j=1,\ldots,n-1\). Falls nun durch eine der vorherigen Operationen des Verfahrens eine Null auf der Hauptdiagonalen entsteht, so wird der Algorithmus abgebrochen, da man bei der Berechnung der Elemente \(l_{i,j} = a_{i,j}^{(j)} / a_{j,j}^{(j)}\) nicht durch Null teilen kann. Das folgende Beispiel illustriert, was passiert wenn diese Bedingung verletzt ist.

Beispiel 1.3 (Problem bei der Gauss-Elimination)

Wir suchen eine Lösung \(x \in \mathbb{R}^2\) des LGS \(Ax = b\) für eine \(2\times 2\) Matrix

\[A \ = \ \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix},\]

und eine beliebige rechte Seite \(b\in \mathbb{R}^2\). Man sieht ein, dass A invertierbar ist mit

\[A^{-1} \ = \ \begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}.\]

Dennoch scheitert das Gauss-Elimininationsverfahren in Algorithmus 1.2 bereits im ersten Schritt (da wir nicht durch Null teilen können) und es existiert keine LR-Zerlegung \(A = LR\) mit \(L\) linker, unterer und \(R\) rechter, oberer Dreieckmatrix. Der Grund hierfür ist das Matrixelement \(a_{11} = 0\) auf der Hauptdiagonalen.

Um das Problem in Beispiel 1.3 zu lösen führen wir im Folgenden das Konzept der Pivotisierung der Matrix \(A\) ein.

Definition 1.5 (Pivotelement)

Sei \(j \in \lbrace 1,\ldots,n-1\rbrace\), dann bezeichnen wir das Hauptdiagonalelement \(a_{j,j}^{(j)}\) der Matrix \(A^{(j)}\) im \(j\)-ten Schritt des Gauss-Eliminationsverfahrens als Pivotelement.

Bemerkung 1.5 (Betragsmäßig kleine Pivotelemente)

Für das Gauss-Eliminationsverfahren ist nicht nur der Fall eines Pivotelements \(a_{j,j}^{(j)} = 0\) problematisch, sondern auch der Fall eines sehr kleinen Pivotelements \(0 < a_{j,j}^{(j)} <\!\!< 1\), da man bei der Berechnung der Elemente \(l_{i,j}\) in (1.9) große Zwischenergebnisse erhält. Wir werden in Grundlagen des numerischen Rechnens näher analysieren, warum solche Fälle zu großen Ungenauigkeiten beim numerischen Rechnen führen. Aus diesem Grund lohnt es sich häufig den im folgenden beschriebenen Algorithmus der Spaltenpivotsuche in jedem Schritt durchzuführen.

Die Idee der Pivotisierung ist recht einfach und soll im folgenden Algorithmus beschrieben werden.

Algorithmus 1.4 (Spaltenpivotsuche)

Wir nehmen zunächst an, dass wir uns im \(j\)-ten Schritt des Gauss-Eliminationsverfahrens in Algorithmus Algorithmus 1.2 befinden und für das aktuelle Pivotelement gelte \(a_{j,j}^{(j)} = 0\). Das LGS hat in diesem Schritt dann die folgende Form:

\[A^{(j)}x \ = \ \begin{pmatrix} a_{1,1}^{(1)} & * & * & \dots & * \\ 0 & \ddots & * & \dots & * \\ 0 & 0 & a_{j,j}^{(j)}=0 & \dots & a_{j,n}^{(j)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & a_{n,j}^{(j)} & \dots & a_{n,n}^{(j)} \\ \end{pmatrix} \cdot x \ = \ \begin{pmatrix} b_1^{(1)} \\ \vdots \\ b_j^{(j)} \\ \vdots \\ b_n^{(j)} \end{pmatrix}.\]

Bei der sogenannten Spaltenpivotsuche versucht man nun durch Zeilenvertauschungen zwischen den Zeilen \(j\) bis \(n\) ein günstiges Pivotelement zu finden. Hierbei wird in der Regel das betragsmäßig größte Element \(a_{i,j}^{(j)}\), mit \(i > j\) ausgewählt, so dass man im \(j\)-ten Schritt des Gauss-Eliminationsverfahrens nun das folgende äquivalente Problem löst:

\[\tilde{A}^{(j)}x \ = \ \begin{pmatrix} a_{1,1}^{(1)} & * & * & \dots & * \\ 0 & \ddots & * & \dots & * \\ 0 & 0 & a_{i,j}^{(j)}\neq 0 & \dots & a_{i,n}^{(j)} \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & a_{j,j}^{(j)} = 0 & \dots & a_{j,n}^{(j)} \\ \vdots & \vdots & \vdots & & \vdots \\ 0 & 0 & a_{n,j}^{(j)} & \dots & a_{n,n}^{(j)} \\ \end{pmatrix} \cdot x \ = \ \begin{pmatrix} b_1^{(1)} \\ \vdots \\ b_i^{(j)} \\ \vdots \\ b_j^{(j)} \\ \vdots \\ b_n^{(j)} \end{pmatrix}.\]

Hierbei erhält man die Matrix \(\tilde{A}^{(j)}\) aus \(A^{(j)}\) durch Vertauschung der \(j\)-ten und \(i\)-ten Zeile für \(i > j\). Dieses Vorgehen wird im Allgemeinen auch Pivotisierung genannt.

Bemerkung 1.6 (Rechenaufwand der Spaltenpivotsuche)

Die Spaltenpivotsuche im \(j\)-ten Schritt des Gauss-Eliminationsvefahrens benötigt \(n-j\) Vergleiche, so dass der Gesamtrechenaufwand angegeben werden kann als

\[\sum_{j=1}^{n-1} i \ = \ \frac{(n-1)n}{2} \ = \ \frac{n^2}{2} - \frac{n}{2}.\]

Somit liegt der Rechenaufwand der Spaltenpivotsuche in \(\mathcal{O}(n^2)\) und ist somit vernachlässigbar gegenüber dem Rechenaufwand des gesamten Verfahrens.

Satz 1.3 (Durchführbarkeit der Spaltenpivotsuche)

Ist die Matrix \(A\) invertierbar, so lässt sich in jedem Schritt des Gauss-Eliminationsverfahrens eine Spaltenpivotsuche durchführen, so dass man ein Pivotelement \(a_{i,j}^{(j)}, i \geq j\) erhält, das nicht Null ist.

Proof. Nehmen wir an, dass im \(j\)-ten Schritt des Gauss-Eliminationsverfahrens kein Pivotelement \(a_{i,j}^{(j)} \neq 0, i > j\) existiert. Das bedeutet, dass die erste Spalte der Matrix \((a_{k,k}^{(j)})_{k=j,\ldots,n}\) nur aus Nullen besteht und somit nicht vollen Rang hat. Daraus folgt mit Argumenten der linearen Algebra, dass \(\operatorname{det}((a_{k,k}^{(j)})_{k=j,\ldots,n}) = 0\) gilt. Andererseits gilt jedoch auch auf Grund des Determinantenmultiplikationssatzes:

\[0 \ \neq \ \operatorname{det}(A) \ = \ \prod_{i=1}^{j-1} a_{i,i}^{(j)} \cdot \operatorname{det}((a_{k,k}^{(j)})_{k=j,\ldots,n}).\]

Dies ist ein klarer Widerspruch zur Annahme, woraus die Behauptung folgt. ◻

Die gewünschte Zeilenvertauschung bei der Pivotisierung im \(j\)-ten Schritt des Gauss-Eliminationsverfahrens lässt sich formal auch durch die Multiplikation mit einer Permutationsmatrix \(P_\sigma \in \R^{n \times n}\) beschreiben, wobei \(\sigma \in S_n\) mit \(\sigma \colon \lbrace 1,\ldots,n \rbrace \rightarrow \lbrace 1,\ldots,n \rbrace\) die entsprechende Permutation aus der symmetrischen Gruppe ist.

Definition 1.6 (Permutationsmatrix)

Sei \(\sigma \in S_n\) eine Permutation der Zahlen \(1\) bis \(n\) mit \(\sigma(1) = i_1, \ldots, \sigma(n) = i_n\) für die vertauschten Zahlen \(i_k \in \lbrace 1,\ldots,n \rbrace\) für \(k=1,\ldots,n\) mit \(i_j \neq i_k\) falls \(i \neq k\). Außerdem sei \(e_j\) der \(j\)-te Einheitsvektor. Dann lässt sich mit Hilfe von \(\sigma\) eine Permutationsmatrix \(P_\sigma\) definieren mit

\[P \ = \ \begin{pmatrix} e_{\sigma(1)}^T \\ \vdots \\ e_{\sigma(n)}^T \end{pmatrix} \ = \ \begin{pmatrix} e_{i_1}^T \\ \vdots \\ e_{i_n}^T \end{pmatrix}.\]

Das heißt es handelt sich um eine Permutation der Einheitsmatrix, bei der die Zeilen gemäß \(\sigma\) vertauscht wurden.

Für die oben eingeführte Permutationsmatrix lassen sich folgende mathematische Eigenschaften beobachten.

Lemma 1.2 (Eigenschaften von Permutationsmatrizen)

Sei \(\sigma \in S_n\) eine Permutation und sei \(P_\sigma \in \R^{n \times n}\) die zugehörige Permutationsmatrix. Dann gelten die folgenden Rechenregeln:

1. Die Anwendung auf einen Vektor \(b \in \mathbb{R}^n\) permutiert die Elemente gemäß \(\sigma \in S_n\), d.h.,

   \[P_\sigma \begin{pmatrix} b_1 \\ \vdots \\ b_n \end{pmatrix} \ = \ \begin{pmatrix} b_{i_1} \\ \vdots \\ b_{i_n} \end{pmatrix}.\]

2. Die Multiplikation \(P_\sigma A\) von links an eine \(n \times n\) Matrix \(A\) permutiert deren Zeilen gemäß \(\sigma \in S_n\).

3. Die Multiplikation \(A P_\sigma^T\) von rechts an eine \(n \times n\) Matrix \(A\) permutiert deren Spalten gemäß \(\sigma \in S_n\).

4. Jede Permutationsmatrix \(P_\sigma\) ist invertierbar und es gilt \(P_\sigma^{-1} = P_\sigma^T\). Da insbesondere gilt \(P_\sigma P_\sigma^T = P_\sigma^T P_\sigma = I_n\) folgt, dass \(P_\sigma\) unitär ist.

Das folgende Beispiel soll die Gestalt und Wirkung von Permutationsmatrizen für einen dreidimensionalen Vektor verdeutlichen.

Beispiel 1.4 (Permutationsmatrix)

Sei \(\sigma\) eine Permutation, die eindeutig festgelegt ist durch \(\overline{\sigma}(1,2,3) = (2,3,1)\), dann lässt sich die zugehörige Permutationsmatrix \(P_\sigma\) schreiben als

\[P_\sigma \ = \ \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix},\]

und bei Anwendung auf einen Vektor \(b \in \mathbb{R}^3\) gilt

\[P_\sigma b \ = \ \begin{pmatrix} 0 & 1 & 0\\ 0 & 0 & 1\\ 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} b_1 \\ b_2 \\ b_3 \end{pmatrix} \ = \ \begin{pmatrix} b_2 \\ b_3 \\ b_1 \end{pmatrix}.\]

Mit Hilfe der oben eingeführten Frobenius- und Permutationsmatrizen lässt sich nun das Gauss-Eliminationsverfahren mit Pivotisierung für eine \(n\times n\) Matrix \(A\) schreiben als

(1.11)\[L_{n-1}P_{n-1}\dots L_2P_2L_1P_1 Ax \ = \ Rx \ = \ y \ = \ L_{n-1}P_{n_1}\dots L_2P_2L_1P_1 b.\]

Um diese Form der rekursiven Linksmultiplikation mit Frobenius- und Permutationsmatrizen in eine geschlossene Form einer LR-Zerlegung zu überführen benötigen wir noch das folgende Lemma.

Lemma 1.3 (Wirkung von Permutationen auf Frobeniusmatrizen)

Sei \(j \in \lbrace 1,\ldots,n-1\rbrace\), \(L_j \in \mathbb{R}^{n\times n}\) eine Frobeniusmatrix und sei \(P_\sigma \in \R^{n \times n}\) eine Permutationsmatrix, die nur Zeilen mit Index \(i > j\) vertauscht, d.h., \(\sigma(\lbrace 1,\ldots,j\rbrace) = \lbrace 1,\ldots,j\rbrace\). Dann gilt

\[P_\sigma L_j P^T_\sigma \ = \ L_j',\]

wobei \(L'_j\) die gleiche Form wie \(L_j\) hat, jedoch mit gemäß der Permutation \(\sigma\) vertauschten Elementen \(l'_{k,j} = l_{i_k,j}\). Aus der Eigenschaft, dass \(P_\sigma\) unitär ist, folgt folgende Vertauschungsrelation:

(1.12)\[P_\sigma L_j \ = \ L_j' P_\sigma.\]

Folgendes Beispiel soll die Wirkung der Permutationsmatrizen \(P\) und \(P^T\) auf eine Frobeniusmatrix \(L\), wie in Lemma 1.3 beschrieben, näher verdeutlichen.

Beispiel 1.5 (Wirkung von Permutationen auf Frobeniusmatrizen)

Sei

\[P \ = \ \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix} \ = \ P^T \quad \text{ und } \quad L \ = \ \begin{pmatrix} 1 & 0 & 0\\ -l_{2,1} & 1 & 0\\ -l_{3,1} & 0 & 1 \end{pmatrix},\]

dann gilt:

\[\begin{aligned} PLP^T &= \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0\\ -l_{2,1} & 1 & 0\\ -l_{3,1} & 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix}\\ &= \begin{pmatrix} 1 & 0 & 0\\ -l_{3,1} & 0 & 1\\ -l_{2,1} & 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix}\\ &= \begin{pmatrix} 1 & 0 & 0\\ -l_{3,1} & 1 & 0\\ -l_{2,1} & 0 & 1 \end{pmatrix}. \end{aligned}\]

Durch die in Lemma 1.3 beschriebene Vertauschungsrelation in (1.12) lässt sich nun die Linksmultiplikation des LGS \(Ax=b\) in (1.11) umschreiben. Ohne Beschränkung der Allgemeinheit betrachten wir hierfür den Fall \(n=4\):

\[\begin{split} L_3P_3L_2P_2L_1P_1 \ &= \ L_3P_3L_2L_1'P_2P_1 \\ \ &= \ L_3L_2'P_3L_1'P_2P_1 \\ \ &= \ L_3L_2'L_1''P_3P_2P_1 \ = \ L^{-1}P. \end{split}\]

Man erhält nun die Matrix \(L\) der LR-Zerlegung von \(A\) durch Invertierung als

\[L \ = \ (L_3L_2'L_1'')^{-1} \ = \ (L_1'')^{-1}(L_2')^{-1}(L_3)^{-1}.\]

Wir können nun eine LR-Zerlegung mit Pivotisierung für beliebige \(A \in \mathbb{R}^{n\times n}\) angeben:

\[PA \ = \ LR.\]

Satz 1.4 (Existenz und Eindeutigkeit der LR-Zerlegung)

Sei \(A\) eine reguläre \(n \times n\) Matrix. Dann existiert für eine geeignet gewählte Permutationsmatrix \(P \in \R^{n \times n}\) eine eindeutige LR-Zerlegung der Form \(PA = LR\), wobei \(L\) normierte, linke, untere Dreiecksmatrix und \(R\) eine rechte, obere Dreiecksmatrix ist.

Proof. Wie wir in Satz 1.3 gesehen haben, existiert für eine reguläre Matrix \(A \in \R^{n \times n}\) im \(j\)-ten Schritt des Gaußschen Eliminationsverfahrens immer ein Spaltenpivotelement \(a_{i,j} \neq 0\) für \(i \geq j\). Somit existiert auch eine Permutationsmatrix \(P \in \R^{n \times n}\), so dass die Anwendung von \(P\) auf \(A\) die Spaltenpivotsuche aus Algorithmus 1.4 durchführt. Somit haben wir bereits die Existenz der Zerlegung \(PA = LR\) gezeigt.

Für die Eindeutigkeit dieser Zerlegung nehmen wir an, dass es zwei LR-Zerlegungen gäbe mit

\[PA \ = \ L_1 R_1 \ = \ L_2 R_2.\]

Auf Grund der Gruppeneigenschaften von normierten, linken, unteren bzw. rechten, oberen Dreiecksmatrizen können wir die rechte Gleichung mit den jeweiligen inversen Matrizen multiplizieren und erhalten:

(1.13)\[R_1 R_2^{-1} \ = \ L_1^{-1} L_2.\]

Ebenfalls aus den Gruppeneigenschaften dieser speziellen Matrizen folgt nun, dass auf der linken Seiten von (1.13) eine rechte, obere Dreiecksmatrix stehen muss und auf der linken Seite eine normierte, linke, untere Dreiecksmatrix. Die einzige Matrix, die diese Bedingungen alle erfüllt ist dementsprechend die Einheitsmatrix \(I_n \in \R^{n \times n}\) und somit folgt schon:

\[R_1 R_2^{-1} \ = \ I_n \ = \ L_1^{-1} L_2.\]

Damit folgt aber auch schon direkt, dass \(L_1 = L_2\) und \(R_1 = R_2\) sein muss, was die Eindeutigkeit der LR Zerlegung beweist. ◻

Bemerkung 1.7

Ist die \(n \times n\) Matrix \(A\) singulär, so existiert dennoch eine Zerlegung \(PA = LR\), die jedoch im Allgemeinen nicht eindeutig ist, da die linke, untere Dreiecksmatrix \(L\) nicht notwendigerweise normiert ist. In diesem Fall existiert ein \(j \in \lbrace 1,\ldots,n-1\rbrace\), so dass im \(j\)-ten Schritt des Gauss-Eliminationsverfahrens kein Pivotelement \(a_{i,j}^{(j)} \neq 0\) für \(i \geq j\) gefunden werden kann. Dann überspringt man den Eliminationsschritt, d.h., man setzt \(L_j = P_j = I_n\). Ein Beispiel für die Zerlegung einer singulären Matrix \(A \in \mathbb{R}^{2\times 2}\) ist:

\[PA \ = \ \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1\\ 1 & 1 \end{pmatrix} \ = \ \begin{pmatrix} 1 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1\\ 0 & 0 \end{pmatrix} \ = \ L R.\]