LR-Zerlegung

1.2. LR-Zerlegung#

Wir betrachten im Folgenden das in Gauss-Eliminationsverfahren hergeleitete Gauss-Eliminationsverfahren in einer alternativen, für uns interessanten Form. Hierfür benötigen wir vorab eine Definition von rechten, oberen und linken, unteren Dreiecksmatrizen, wie sie bereits bei der Gauss-Elimination auftauchten.

Definition 1.2 (Dreiecksmatrizen und Normierung)

Wir nennen eine quadratische Matrix \(L\in \R^{n\times n}\) linke, untere Dreiecksmatrix, wenn \(l_{i,j} = 0\) für alle \(i < j\) gilt. Analog definieren wir eine quadratische Matrix \(R\in \R^{n\times n}\) als rechte, obere Dreiecksmatrix, wenn \(r_{i,j} = 0\) für alle \(i > j\) gilt. Wir nennen eine Dreiecksmatrix normiert, falls auf der Hauptdiagonalen nur Einsen stehen.

Satz 1.2

Die invertierbaren linken, unteren (und auch rechten, oberen) Matrizen bilden eine Gruppe bezüglich der Multiplikation.

Wir definieren im Folgenden eine nützliche Menge von linken, unteren Dreiecksmatrizen, die spezielle Eigenschaften haben.

Definition 1.3 (Frobeniusmatrizen)

Sei \(L_j \in \mathbb{R}^{n\times n}\) eine linke, untere Dreiecksmatrix. Wir nennen \(L_j\) eine Frobeniusmatrix, wenn sie nur in der \(j\)-ten Spalte von der Einheitsmatrix \(I_n \in \mathbb{R}^{n\times n}\) abweicht und folgende Gestalt hat:

(1.10)#\[L_j \ = \ \begin{pmatrix} 1 & & & & & \\ & \ddots & & & &\\ & & 1 & & &\\ & & -l_{j+1,j} & & &\\ & & \vdots & &\ddots &\\ & & -l_{n,j} & & & 1\\ \end{pmatrix}\]

Lemma 1.1 (Eigenschaften von Frobeniusmatrizen)

Für Frobeniusmatrizen \(L_j \in \mathbb{R}^{n\times n}\) der Gestalt (1.10) lassen sich folgende nützliche Eigenschaften zeigen.

  1. Bei Anwendung von \(L_j\) auf einen beliebigen Vektor \(a \in \mathbb{R}^n\) werden nur die Einträge \(a_i\) von \(i=j+1,\ldots,n\) des Vektors \(a\) verändert, d.h.,

    \[L_j \begin{pmatrix} a_1 \\ \vdots \\ a_j \\ a_{j+1} \\ \vdots \\ a_n \end{pmatrix} \ = \ \begin{pmatrix} a_1 \\ \vdots \\ a_j \\ a_{j+1} - l_{j+1,j} a_j \\ \vdots \\ a_n - l_{n,j}a_j \end{pmatrix}\]

  2. Bei Anwendung von \(L_j\) auf eine beliebige Matrix \(A \in \mathbb{R}^{n\times n}\) erhält man das Resultat \(L_j A\), indem man das \(l_{i,j}\)-fache der \(j\)-ten Zeile von \(A\) von der \(i\)-ten Zeile von \(A\) subtrahiert für \(i=j+1,\ldots,n\). Das entspricht genau dem \(j\)-ten Schritt des Gauss-Eliminationsverfahrens in Algorithmus 1.2.

  3. Aus Eigenschaft \((i)\) folgt direkt, dass man die Inverse \(L_j^{-1}\) von \(L_j\) durch Umkehrung des Vorzeichens der Einträge \(l_{i,j}\) für \(i=j+1,\ldots,n\) erhält.

  4. Das Produkt zweier Frobeniusmatrizen \(L_j,L_k\) für \(j<k\) lässt sich durch Überlagern der beiden Matrizen berechnen, d.h.,

    \[L_jL_k \ = \ \begin{pmatrix} 1 & & & & & & &\\ & \ddots & & & & & &\\ & & 1 & & & &\\ & & -l_{j+1,j} & \ddots & & & &\\ & & \vdots & & 1 & & &\\ & & \vdots & & -l_{k+1,k} & \ddots & &\\ & & \vdots & & \vdots & & \ddots &\\ & & -l_{n,j} & & -l_{n,k} & & & 1 \end{pmatrix}.\]

Wir wollen nun eine Zerlegung einer gegebenen Matrix \(A \in \mathbb{R}^{n \times n}\) definieren.

Definition 1.4 (LR-Zerlegung)

Wir definieren die LR-Zerlegung einer Matrix \(A \in \mathbb{R}^{n \times n}\) als ein Produkt einer linken, unteren Dreiecksmatrix \(L \in \mathbb{R}^{n \times n}\) und einer rechten, oberen Dreiecksmatrix \(R \in \mathbb{R}^{n \times n}\), die, wenn sie existiert, folgende Gestalt hat

\[A \ = \ LR.\]

Nehmen wir nun an, dass die Matrix \(A\) weiterhin nicht singulär ist und eine LR-Zerlegung von \(A\) existiert. Mit Hilfe der Eigenschaften von Frobeniusmatrizen aus Lemma 1.1 und dem Zusammenhang zum Gauss-Eliminationsverfahren in Algorithmus 1.2 können wir nun schreiben:

\[L^{-1}Ax \ = \ L_{n-1}\dots L_1Ax \ = \ Rx \, = \, y \ = \ L_{n-1}\dots L_1 b \ = \ L^{-1}b,\]

wobei jede der Frobeniusmatrizen \(L_j\) für \(j=1,\ldots,n-1\) den \(j\)-ten Schritt des Gauss-Eliminationsverfahrens durchführt. Das bedeutet, dass wir die Matrix \(A\) in eine rechte, obere Dreiecksmatrix \(R\) überführen können, indem wir sukzessive Frobeniusmatrizen \(L_j\) mit Einträgen \(l_{i,j}\) wie in (1.9) definiert von links multiplizieren für \(j=1,\ldots,n-1\). Aus der ursprünglichen rechten Seite \(b\in \mathbb{R}^n\) des LGS in (1.1) wird durch diese Operationen die neue rechte Seite \(y\in \mathbb{R}^n\).

Sei nun für eine Matrix \(A \in \mathbb{R}^{n\times n}\) eine LR-Zerlegung \(A = LR\) gegeben. Dann lässt sich das LGS \(Ax = b\) äquivalent schreiben als das Lösen der beiden folgenden Probleme:

\[Ly \, = \, b \quad \text{ und } \quad \ Rx \, = \, y, \qquad \text{ für } x,y,b \in \mathbb{R}^n.\]

Das heißt, man bestimmt zuerst die rechte Seite \(y\) durch Vorwärtseinsetzen von \(Ly=b\) und löst dann \(Rx=y\) durch Rückwärtseinsetzen nach Algorithmus 1.1. Der Rechenaufwand beträgt nach Bemerkung 1.1 in diesem Fall \(n^2 + \mathcal{O}(n)\) FLOPS.

Wir wollen die Berechnung der LR-Zerlegung einer regulären Matrix \(A \in \R^{n \times n}\) im Folgenden algorithmisch beschreiben.

Algorithmus 1.3 (LR-Zerlegung (ohne Pivotisierung))

Wir wollen zur Beschreibung dieses Algorithmus zunächst auf das Vertauschen von Zeilen verzichten, da wir später detailliert darauf eingehen werden. Darum müssen wir für den Moment annehmen, dass im \(j\)-ten Schritt der LR-Zerlegung das entsprechende Element auf der Hauptdiagonale von \(A^{(j)}\) ungleich Null ist, d.h., es gelte \(a_{j,j}^{(j)} \neq 0\).

Für die Initialisierung des Algorithmus wählen wir zunächst \(L \coloneqq I_n\) als Einheitsmatrix und \(A^{(1)} \coloneqq A\).

Im ersten Schritt der LR-Zerlegung berechnen wir die Elemente der linken unteren Dreiecksmatrix \(L_1 =: L^{(1)}\) durch:

\[L^{(1)}_{i,1} \ \coloneqq \ \frac{a^{(1)}_{i,1}}{a^{(1)}_{1,1}}, \qquad i=2,\ldots,n.\]

Anschließend setzen wir \(A^{(2)} = A^{(1)}\) und erzeugen eine Nullspalte unterhalb des Hauptdiagonalelements \(a^{(1)}_{1,1}\) durch zeilenweise Differenzen mit den Vorfaktoren in \(L^{(1)}\) wie folgt:

\[a^{(2)}_{i,k} \ \coloneqq \ a^{(1)}_{i,k} - L^{(1)}_{i,1} \cdot a^{(1)}_{1,k}, \qquad i=2,\ldots,n, \quad k=1,\ldots,n.\]

Für den j-ten Schritt der LR-Zerlegung für \(j=2,\ldots,n-1\) lässt sich das Vorgehen wie folgt verallgemeinern. Wir berechnen zunächst die Einträge der linken unteren Dreiecksmatrix \(L_j =: L^{(j)}\) durch:

\[L^{(j)}_{i,j} \ \coloneqq \ \frac{a^{(j)}_{i,j}}{a^{(j)}_{j,j}}, \qquad i=j+1,\ldots,n.\]

Anschließend erzeugen wir eine Nullspalte unterhalb des Hauptdiagonalelements \(a^{(j)}_{j,j}\) durch zeilenweise Differenzen mit den Vorfaktoren in \(L^{(j)}\) wie folgt:

\[a^{(j+1)}_{i,k} \ \coloneqq \ a^{(j)}_{i,k} - L^{(j)}_{i,j} \cdot a^{(j)}_{j,k}, \qquad i=j+1,\ldots,n, \quad k=j,\ldots,n.\]

Nach dem letzten Schritt, d.h., für \(j=n-1\) erhält man die obere rechte Dreiecksmatrix \(R := A^{(n-1)}\) und die linke untere Dreiecksmatrix \(L = L_1 \cdot \ldots \cdot L_{n-1}\) durch Überlagern der einzelnen Frobeniusmatrizen, so dass gilt \(A = LR\).

Das gesamte Verfahren zur Berechnung der LR-Zerlegung lässt sich anschaulich durch folgenden Pseudo-Code beschreiben.

function (L,R) =  lr(A):
    R = A
    L = I_n

    for j=1,...,n-1:
        for i=j+1,...,n:
            L[i,j] = R[i,j] / R[j,j]
            for k=j,...,n:
                R[i,k] = R[i,k] - L[i,j] * R[j,k]

Bemerkung 1.3 (Berechnung der Inversen via LR-Zerlegung)

Für eine invertierbare \(n \times n\) Matrix \(A\) lässt sich die LR-Zerlegung auch zur Berechnung der Inversen \(A^{-1}\) von \(A\) nutzen, denn es gilt:

\[A \, = \, LR \quad \Rightarrow \quad A^{-1} \, = \, R^{-1} L^{-1},\]

wobei die Inversen \(L^{-1}\) und \(R^{-1}\) sehr einfach berechnet werden können.

Bemerkung 1.4 (Gleichungssysteme mit fester Matrix A)

Wir haben oben angenommen, dass bereits eine LR-Zerlegung von der Matrix \(A\) bekannt ist. Der Rechenaufwand zur Bestimmung einer LR-Zerlegung hat sich jedoch nicht verringert und liegt weiterhin in \(\mathcal{O}(n^3)\). Dennoch ist obige Betrachtung in Fällen interessant in denen man \(m \in \mathbb{N}, m>\!\!>1\) lineare Gleichungssysteme der Form

\[A x_k \ = \ b_k, \quad k=1,\ldots,m\]

lösen muss, d.h., wenn die Matrix \(A\) in allen \(m\) Problemen gleich ist. In diesen Fällen muss nur eine LR-Zerlegung der Matrix \(A\) bestimmt werden, welche dann zur Lösung aller \(m\) Probleme effizient genutzt werden kann.