Kurs:Numerik I/Zerlegung PA = LR

Einführung - Die Zerlegung PA = LR

Häufig ist in der numerischen Mathematik das Gleichungssystem $Ax=b$ für eingegebene (feste) reguläre Matrix $A\in {ℝ}^{n\times n}$ und unterschiedliche rechte Seiten zu lösen.

Effizienzbetrachtung für den Algorithmus

In einem solchen Fall ist es ineffizient, für jede neue rechte Seiten wieder den gesamten Gauß-Algorithmus durchzuführen, da er bei jedem Durchlauf in Bezug auf $A$ wiederholt die gleichen Teiloperationen durchführen würde. Deshalb möchte man die beim Gauß-Algorithmus durchgeführten Teiloperationen von $A$ in irgendeiner Form speichern, die den Rechenaufwand reduziert.

Zerlegung in Teiloperationen

Dieses kann in Form einer Zerlegung von $A$ der Form $PA=LR$ geschehen, wie sie im folgenden Unterabschnitt eingeführt wird, wobei $L\in {ℝ}^{n\times n}$ eine untere Dreiecksmatrix, $R\in {ℝ}^{n\times n}$ eine obere Dreiecksmatrix und $P\in {ℝ}^{n\times n}$ eine Permutationsmatrix ist.

Umformungen als Matrixmultiplikationen

Eine solche Zerlegung bzw. Faktorisierung von $A$ kann man, wie wir zeigen wollen, mittels des Gauß-Algorithmus mit Spaltenpivotsuche gewinnen.

Bemerkung zur PA-LR-Darstellung

Ein Permutationsmatrix ist invertierbar und $P^{-1}$ existiert. Damit lässt sich dann über die Gleichung $P\cdot A=L\cdot R$ Matrix $A$ über folgendes Matrixprodukt darstellen:

$A=P^{-1}\cdot L\cdot R$

Faktorisierung - Lösungsschritte

Liegt eine solche Faktorisierung vor, so kann man das Gleichungssystem $Ax=b$ bzw. $LRx=Pb$ für ein gegebenes $b\in {ℝ}^n$ lösen, indem man hintereinander die beiden Dreieckssysteme

$Ly=Pb,Rx=y$

löst, wobei die Lösung $y$ des ersten Systems die rechte Seite des zweiten Systems liefert.

Anwendung für unterschiedliche Vektoren b

Hat man das System $Ax=b$ für mehrere unterschiedliche rechte Seiten $b$ zu lösen, so muss man dann nur einmal die numerisch teuere Zerlegung $PA=LR$ bestimmen, während die Berechnung der Lösung $x$ gemäß $Ly=Pb,Rx=y$ numerisch relativ durch die Verwendung von Dreiecksmatrizen nicht mehr so rechenintensiv ist.

Permutationsmatrizen

In der obigen Beschreibung haben wir die Notwendigkeit identifiziert, dass man für das Lösungsverfahren Zeilen vertauschen müssen. Eine einzelne Zeilvertauschung kann durch ein Matrix $Z_{(i,j)}$ realisiert werden. Durch Matrixmultiplikation kann diese Elementarmatrizen auch zu einer Pemutationsmatrix "zusammenfassen".

Beispiel - Vertauschung 1 und 4 Zeile

$Z_{(1,4)}=\left(\begin{array}{ccccc}0& 0& 0& 1& 0\\ 0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0\\ 0& 0& 0& 0& 1\end{array}\right)\in {ℝ}^{5\times 5}$.

Maxima - Vertauschung 1 und 4 Zeile

Geben Sie die $Z_{(1,4)}$ als $Z$ und die folgende Matrix in Maxima CAS ein

$A=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ 0& 6& 0& 0& 0\\ 0& 0& 7& 0& 0\\ 0& 0& 0& 8& 0\\ 0& 0& 0& 0& 9\end{array}\right)\in {ℝ}^{5\times 5}$.

und berechnen Sie das Matrizenprodukt über Z.A mit "." als Operatorsymbol für die Matrixmultiplikation.

Definition - Permutationsmatrix

Jede Matrix $P\in {ℝ}^{n\times n}$ mit genau einer Eins und sonst nur Nullen in jeder Zeile und Spalte heißt Permutationsmatrix.

Beispiel - Permutationsmatrix

Die folgende Matrix stellt eine Permutationsmatrix dar:

$P:=\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\end{array}\right)\in {ℝ}^{4\times 4}.$

Definition - Permution

Jede bijektive Abbildung $\pi :\{1,...,n\}\to \{1,...,n\}$ heißt eine Permutation.

Zusammenhang Permutation - Permutationsmatrix

Offensichtlich ist $P\in {ℝ}^{n\times n}$ genau dann eine Permutionsmatrix, wenn es eine Permutation $\pi :\{1,...,n\}\to \{1,...,n\}$ gibt, so dass

$P=\left(\begin{array}{ccc}{e}^{\pi (1)}& ...& e^{\pi (n)}\end{array}\right)$

gilt, wobei $e^j\in {ℝ}^n$ die $j$-te Spalte der Einheitsmatrix bezeichnet.

Beispiel - Permutation - Permutationmatrix

Die im obigen Beispiel genannte Permutationmatrix ist die durch folgende Permutation definiert

$\pi (1):=3,\pi (2):=1,\pi (3):=2,\pi (4):=4,$

wobei $\pi :\{1,...,n\}\to \{1,...,n\}$ die folgende Permutationmatrix liefert

$P=\left(\begin{array}{cccc}{e}^3& e^1& e^2& e^4\end{array}\right)=\left(\begin{array}{cccc}{e}^{\pi (1)}& e^{\pi (2)}& e^{\pi (3)}& e^{\pi (4)}\end{array}\right).$

Mittels Zusammenhang von Permutation und Permutationsmatrix kann man nun die Aussagen des folgenden Satzes erschließen.

Aufgabe - Studierende

Geben Sie in Maxima die Permutationsmatrix an, die die obige Permutation durchführt.

Satz - Permutationsmatrizen

Sei $P\in {ℝ}^{n\times n}$ eine Permutationsmatrix und $\pi :\{1,...,n\}\to \{1,...,n\}$ bezeichne die zu der Matrix $P$ gehörende Permutation. Dann gilt:

• (i) $P$ ist eine orthogonale Matrix, d. h. es ist $P^{-1}=P^T$.
• (ii) Es gilt

$P^{-1}=P^T=\left(\begin{array}{ccc}{e}^{{\pi }^{-1}(1)}& ...& e^{{\pi }^{-1}(n)}\end{array}\right)$.

• (iii) Für $\alpha :=({\alpha }_i)\in {ℝ}^n$ gilt

$P\alpha =\left(\begin{array}{c}{\alpha }_{{\pi }^{-1}(1)}\\ ⋮\\ {\alpha }_{{\pi }^{-1}(n)}\end{array}\right),{\alpha }^{T}P=\left(\begin{array}{ccc}{\alpha }_{\pi (1)}& ...& {\alpha }_{\pi (n)}\end{array}\right).$

• (iv) Für jede Matrix $A\in {ℝ}^{n\times n}$ mit Zeilen $(z^i{)}^T$ und Spalten $a^i$ $(i=1,...,n)$ gilt

(3.6) $PA=\left(\begin{array}{c}{\left(z^{{\pi }^{-1}(1)}\right)}^T\\ ⋮\\ {\left(z^{{\pi }^{-1}(n)}\right)}^T\end{array}\right),AP=\left(\begin{array}{ccc}{a}^{\pi (1)}& ...& a^{\pi (n)}\end{array}\right).$

Beweis.

(i) folgt mit (3.5) aus

${\left(P^{T}P\right)}_{ij}={\left[\left(\begin{array}{c}{\left(e^{\pi (1)}\right)}^T\\ ⋮\\ {\left(e^{\pi (n)}\right)}^T\end{array}\right)\left(\begin{array}{ccc}{e}^{\pi (1)}& ...& e^{\pi (n)}\end{array}\right)\right]}_{ij}={\left[{\left(e^{\pi (i)}\right)}^T{e}^{\pi (j)}\right]}_{ij}=({\delta }_{\pi (i),\pi (j)}{)}_{ij}=({\delta }_{ij}{)}_{ij}=I.$

Die Behauptung in (ii) ergibt sich aus

${\left[\left(\begin{array}{ccc}{e}^{{\pi }^{-1}(1)}& ...& e^{{\pi }^{-1}(n)}\end{array}\right)\left(\begin{array}{ccc}{e}^{\pi (1)}& ...& e^{\pi (n)}\end{array}\right)\right]}_{ij}=\sum _{\ell =1}^n{\left(e^{{\pi }^{-1}(\ell )}\right)}_i{\left(e^{\pi (j)}\right)}_{\ell }=\sum _{\ell =1}^n{\delta }_{i,{\pi }^{-1}(\ell )}{\delta }_{\pi (j),\ell }$

$=\sum _{k=1}^n{\delta }_{i,k}{\delta }_{\pi (j),\pi (k)}={\delta }_{\pi (j),\pi (i)}={\delta }_{ji}={\delta }_{ij}.$

Die erste Behauptung in (iii) folgt aus

$P\alpha =\sum _{j=1}^n{\alpha }_j{e}^{\pi (j)}=\sum _{\ell =1}^n{\alpha }_{{\pi }^{-1}(\ell )}{e}^{\ell }=({\alpha }_{{\pi }^{-1}(1)},...,{\alpha }_{{\pi }^{-1}(n)}{)}^T,$

die zweite folgt mit (ii) und letzterer Identität aus

${\alpha }^{T}P={\left(P^T\alpha \right)}^T={\left(\sum _{j=1}^n{\alpha }_j{e}^{{\pi }^{-1}(j)}\right)}^T=({\alpha }_{\pi (1)},...,{\alpha }_{\pi (n)}).$

Die entsprechenden Matrixversionen in (iv) folgen analog aus

$PA=\sum _{j=1}^n{e}^{\pi (j)}(z^j{)}^T=\sum _{\ell =1}^n{e}^{\ell }(z^{{\pi }^{-1}(\ell )}=\left(\begin{array}{c}{\left(z^{{\pi }^{-1}(1)}\right)}^T\\ ⋮\\ {\left(z^{{\pi }^{-1}(n)}\right)}^T\end{array}\right)$

sowie unter Verwendung dieser Beziehung und (ii) aus

$AP={\left(P^T{A}^T\right)}^T={\left[P^T\left(\begin{array}{c}(a^1{)}^T\\ ⋮\\ (a^n{)}^T\end{array}\right)\right]}^T={\left(\begin{array}{c}(a^{\pi (1)}{)}^T\\ ⋮\\ (a^{\pi (n)}{)}^T\end{array}\right)}^T.$

q.e.d.

Man beachte, dass die Indizes ${\pi }^{-1}(1),...,{\pi }^{-1}(n)$ gemäß Aussage (ii) von Satz 3.10 gerade die Indizes der Einheitsvektoren, welche die Spalten von $P^T$ bzw. die Zeilen von $P$ bilden, sind. Somit bewirkt also die Multiplikation einer Matrix $A$ mit einer Permutationsmatrix von links bzw. rechts eine Permutation der Zeilen bzw. Spalten von $A$, die der Permutation der Zeilen bzw. Spalten von $P$ im Vergleich mit der Einheitsmatrix entspricht.

Beispiel 3.11

Seien

$P:=\left(\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right),A:=\left(\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right).$

Dann folgt

$PA=\left(\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right)\left(\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right)=\left(\begin{array}{ccc}7& 8& 9\\ 1& 2& 3\\ 4& 5& 6\end{array}\right),$

$AP=\left(\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\\ 7& 8& 9\end{array}\right)\left(\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right)=\left(\begin{array}{ccc}2& 3& 1\\ 5& 6& 4\\ 8& 9& 7\end{array}\right).$

---

In numerischen Implementierungen erfolgt die Abspeicherung einer Permutationsmatrix mit der zugehörigen Permutation $\pi$ in Form eines Vektors

$({\pi }^{-1}(1),...,{\pi }^{-1}(n){)}^T\in {ℝ}^n$ oder $(\pi (1),...,\pi (n){)}^T\in {ℝ}^n$.

Eine besondere Rolle spielen Elementarpermutationen $\pi :\{1,...,n\}\to \{1,...,n\}$, die zwei Zahlen vertauschen und die restlichen Zahlen unverändert lassen. Im Fall einer Elementarpermutation gibt es also zwei Zahlen $i,r\in \{1,...,n\}$ mit

(3.7) $\pi (i)=r,\pi (r)=i,\pi (j)=j(j\notin \{i,r\}).$

Hier gilt wegen

${\pi }^{-1}(r)=i=\pi (r),{\pi }^{-1}(i)=r=\pi (i),{\pi }^{-1}(j)=j=\pi (j)(j\notin \{i,r\})$

die Identität ${\pi }^{-1}=\pi$, so dass sich für die zu $\pi$ gehörende Permutationsmatrix $P\in {ℝ}^{n\times n}$ (vgl. (3.5)) ergibt:

(3.8) $P^{-1}=P^T=P.$

3.3.2 Frobenius-Matrizen

Wir betrachten eine weitere wichtige Klasse von Matrizen.

Definition - Frobeniusmatrix

Sei $k\in \{1,...,n\}$. Jede Matrix der Form

(3.9) $\left(\begin{array}{cccccc}1& & & & & \\ & \ddots & & & & \\ & & 1& & & \\ & & -l_{k+1,k}& 1& & \\ & & ⋮& & \ddots & \\ & & -l_{n,k}& & & 1\end{array}\right)\in {ℝ}^{n\times n}$

heißt Frobenius-Matrix vom Index $k$.

Bemerkung - Frobeniusmatrix

Eine Frobenius-Matrix vom Index $k$ unterscheidet sich von der Einheitsmatrix gleicher Größe also nur in der $k$-ten Spalte und dort auch nur unterhalb der Diagonalen. Insbesondere lässt sich die prinzipielle Vorgehensweise bei den Zeilenoperationen der $k$-ten Stufe des Gauß-Algorithmus durch Multiplikation mit einer Frobenius-Matrix vom Index $k$ beschreiben. So gilt für Vektoren $z^j\in {ℝ}^n$ $(j=1,...,n)$

(3.10) $\left(\begin{array}{cccccc}1& & & & & \\ & \ddots & & & & \\ & & 1& & & \\ & & -l_{k+1,k}& 1& & \\ & & ⋮& & \ddots & \\ & & -l_{n,k}& & & 1\end{array}\right)\left(\begin{array}{c}{\left(z^1\right)}^T\\ ⋮\\ {\left(z^n\right)}^T\end{array}\right)=\left(\begin{array}{c}{\left(z^1\right)}^T\\ ⋮\\ {\left(z^k\right)}^T\\ {\left(z^{k+1}\right)}^T-l_{k+1,k}{\left(z^k\right)}^T\\ ⋮\\ {\left(z^n\right)}^T-l_{n,k}{\left(z^k\right)}^T\end{array}\right)$

Offenbar lässt sich die Frobenius-Matrix in (3.9) mit

(3.11) $f^k:=(0,...,0,l_{k+1,k},...,l_{n,k}{)}^T\in {ℝ}^n$

wegen

$f^k(e^k{)}^T=\left(\begin{array}{c}0\\ ⋮\\ 0\\ 0\\ l_{k+1,k}\\ ⋮\\ l_{n,k}\end{array}\right)(0,...,0,\stackrel{k\text{-te Stelle}}{\overbrace{1}},0,...,0)=\left(\begin{array}{ccccccc}0& ...& 0& 0& 0& ...& 0\\ ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& ...& 0& 0& 0& ...& 0\\ 0& ...& 0& 0& 0& ...& 0\\ 0& ...& 0& l_{k+1,k}& 0& ...& 0\\ ⋮& \ddots & ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& ...& 0& l_{n,k}& 0& ...& 0\end{array}\right)$

in der Form

(3.12) $F_k=I-f^k(e^k{)}^T$

darstellen, wobei $I\in {ℝ}^{n\times n}$ die Einheitsmatrix und $e^k\in {ℝ}^n$ wieder die $k$-te Spalte von $I$ bezeichnet.

Lemma 3.13

Für $k=1,...,n-1$ sind die Frobenius-Matrizen $F_k\in {ℝ}^{n\times n}$ vom Index $k$ regulär und es gilt für $k=1,...,n-1$

(3.13) $F_k^{-1}=\left(\begin{array}{cccccc}1& & & & & \\ & \ddots & & & & \\ & & 1& & & \\ & & l_{k+1,k}& 1& & \\ & & ⋮& & \ddots & \\ & & l_{n,k}& & & 1\end{array}\right)=I+f^k(e^k{)}^T$

sowie

(3.14) $F_1^{-1}\cdots F_{n-1}^{-1}=\left(\begin{array}{ccccc}1& & & & \\ l_{21}& 1& & & \\ ⋮& l_{32}& 1& & \\ ⋮& ⋮& \ddots & \ddots & \\ l_{n1}& l_{n2}& ...& l_{n,n-1}& 1\end{array}\right)=I+\sum _{j=1}^{n-1}{f}^j(e^j{)}^T.$

Beweis.

Für $F_k$ hat man mit (3.11) die Darstellung (3.12). Wegen

$[I+f^k(e^k{)}^T]\underset{=F_k}{\underbrace{[I-f^k(e^k{)}^T]}}=I+f^k(e^k{)}^T-f^k(e^k{)}^T-f^k\underset{=0}{\underbrace{[(e^k{)}^T{f}^k]}}(e^k{)}^T=I$

folgt

$\det (I+f^k(e^k{)}^T)\det (I+f^k(e^k{)}^T)=1,$

also die Regularität von $F_k$ sowie die behauptete Darstellung von $F_k^{-1}$. Im Folgenden soll nun mittels vollständiger Induktion die Identität

(3.15) $F_1^{-1}\cdots F_k^{-1}=I+\sum _{j=1}^k{f}^j(e^j{)}^T,k=1,...,n-1$

nachgewiesen werden, welche im Fall $k:=n-1$ der Formel (3.14) entspricht.

Die Darstellung in (3.15) ist sicher richtig für $k:=1$. Wir nehmen nun weiter an, dass sie für ein beliebiges $k\in \{1,...,n-2\}$ richtig ist. Dann gilt die Darstellung in (3.15) auch für $k+1$, denn

$F_1^{-1}\cdots F_k^{-1}{F}_{k+1}^{-1}=[I+\sum _{j=1}^k{f}^j(e^j{)}^T][I+f^{k+1}(e^{k+1}{)}^T]$

$=I+f^{k+1}(e^{k+1}{)}^T+\sum _{j=1}^k{f}^j(e^j{)}^T+\sum _{j=1}^k{f}^j\underset{=0}{\underbrace{[(e^j{)}^T{f}^{k+1}]}}(e^{k+1}{)}^T=I+\sum _{j=1}^{k+1}{f}^j(e^j{)}^T.$

q.e.d.

Lemma 3.14

Sei $F_k$ eine wie in (3.12) mit (3.11) dargestellte Frobenius-Matrix vom Index $k$ und $P$ eine Permutationsmatrix mit zugehöriger Elementarpermutation $\pi$ von der Form (3.7) mit $i,r\in \{k+1,...,n\}$. Dann entsteht die Matrix $P{F}_{k}P$ aus $F_k$ durch Vertauschen der Einträge $i$ und $r$ in der $k$-ten Spalte, d. h.

$P{F}_{k}P=I-\left(P{f}^k\right)(e^k{)}^T.$

Beweis.

Die Aussage ergibt sich unmittelbar aus

$P{F}_{k}P=P[I-f^k(e^k{)}^T]P=\underset{=I}{\underbrace{P^2}}-[P{f}^k][\underset{=(e^k{)}^T}{\underbrace{(e^k{)}^{T}P}}],$

wobei (3.8) und Satz 3.10 (iii) sowie die Forderungen für $i$ und $r$ eingehen.

q.e.d.

3.3.3 Die LR-Zerlegung mittels Gauß-Algorithmus

Im Folgenden wird die allgemeine Vorgehensweise beim Gauß-Algorithmus zur sukzessiven Erzeugung von Matrizen $A^{(k)}\in {ℝ}^{n\times n}$ der Form

(3.16) $A^{(k)}=\left(\begin{array}{cccccc}{a}_{11}^{(k)}& a_{12}^{(k)}& ...& ...& ...& a_{1n}^{(k)}\\ & a_{22}^{(k)}& ...& ...& ...& a_{1n}^{(k)}\\ & & \ddots & & & ⋮\\ & & & a_{kk}^{(k)}& ...& a_{kn}^{(k)}\\ & & & ⋮& \ddots & ⋮\\ & & & a_{nk}^{(k)}& ...& a_{nn}^{(k)}\end{array}\right)\in {ℝ}^{n\times n}$

mit Spaltenpivotsuche als Folge spezieller Matrix-Operationen beschrieben. Und zwar wird im $k$-ten Schritt entsprechend Algorithmus 1 eine Zeilenvertauschung $A^{(k)}\to P_k{A}^{(k)}$ vorgenommen. Hierbei ist $P_k\in {ℝ}^{n\times n}$ eine elementare Permutationsmatrix, die nur eine Vertauschung der Zeilen $k$ und $p_k\ge k$ von $A^{(k)}$ bewirkt. ($p_k=k$ und somit $P_k=I$ ist möglich.) Damit ergibt sich gemäß (3.6) und (3.10)

(3.17) $A^{(k+1)}=F_k{P}_k{A}^{(k)}$

mit

(3.18) $F_k:=\left(\begin{array}{cccccc}1& & & & & \\ & \ddots & & & & \\ & & 1& & & \\ & & -l_{k+1,k}& 1& & \\ & & ⋮& & \ddots & \\ & & -l_{n,k}& & & 1\end{array}\right)$

für

(3.19) $l_{p_k,k}:=\frac{a_{kk}^{(k)}}{a_{p_k,k}^{(k)}},l_{ik}=\frac{a_{ik}^{(k)}}{a_{p_k,k}^{(k)}}(i=k+1,...,n,i\ne p_k)$

sowie

(3.20) $P_k:=\left(\begin{array}{ccccccccccc}1& & & & & & & & & & \\ & \ddots & & & & & & & & & \\ & & 1& & & & & & & & \\ & & & 0& & & & 1& & & \\ & & & & 1& & & & & & \\ & & & & & \ddots & & & & & \\ & & & & & & 1& & & & \\ & & & 1& & & & 0& & & \\ & & & & & & & & 1& & \\ & & & & & & & & & \ddots & \\ & & & & & & & & & & 1\end{array}\right)$ $\begin{array}{cc}\leftarrow & \text{Zeile }k\\ & \\ & \\ & \\ \leftarrow & \text{Zeile }{p}_k\end{array}$

Der Index $p_k$ bezeichnet dabei die Position der Zeile aus $A^{(k)}$, welche das Pivotelement enthält.

Satz 3.15

Mit den Definitionen (3.16) - (3.20) gilt die Identität $PA=LR$ für

$P:=P_{n-1}\cdots P_1,R:=A^{(n)}$

und

(3.21) $L:=\left(\begin{array}{ccccc}1& & & & \\ {\hat{l}}_{21}& 1& & & \\ ⋮& {\hat{l}}_{32}& 1& & \\ ⋮& ⋮& \ddots & \ddots & \\ {\hat{l}}_{n1}& {\hat{l}}_{n2}& ...& {\hat{l}}_{n,n-1}& 1\end{array}\right)$

mit

(3.22) $\left(\begin{array}{c}0\\ ⋮\\ 0\\ 1\\ {\hat{l}}_{k+1,k}\\ ⋮\\ {\hat{l}}_{n,k}\end{array}\right):=P_{n-1}\cdots P_{k+1}\left(\begin{array}{c}0\\ ⋮\\ 0\\ 1\\ l_{k+1,k}\\ ⋮\\ l_{n,k}\end{array}\right)$

Beweis.

Für $k=1,2,...$ gilt mit (3.17) sowie (3.8)

$A^{(2)}=F_1{P}_{1}A=F_1(P_{1}A),$

$A^{(3)}=F_2{P}_2{A}^{(2)}=F_2(P_2{F}_1\underset{=I}{\underbrace{P_2)(P_2}}{P}_{1}A),$

$A^{(4)}=F_3{P}_3{A}^{(3)}=F_3(P_3{F}_2\underset{=I}{\underbrace{P_3)(P_3}}{P}_2{F}_1{P}_2\underset{=I}{\underbrace{P_3)(P_3}}{P}_2{P}_{1}A)$

und so weiter, was schließlich

(3.23) $R=A^{(n)}={\hat{F}}_{n-1}\cdots {\hat{F}}_{1}PA$

ergibt mit

$P:=P_{n-1}\cdots P_1$

und den Frobenius-Matrizen ${\hat{F}}_{n-1}=F_{n-1}$ und

${\hat{F}}_k:=P_{n-1}\cdots P_{k+1}{F}_k{P}_{k+1}\cdots P_{n-1}=\left(\begin{array}{cccccc}1& & & & & \\ & \ddots & & & & \\ & & 1& & & \\ & & -{\hat{l}}_{k+1,k}& \ddots & & \\ & & ⋮& & \ddots & \\ & & -{\hat{l}}_{nk}& & & 1\end{array}\right)$

für $k=1,...,n-2$, wobei in die letzte Identität Lemma 3.14 eingeht. Eine Umformung von (3.23) liefert dann

$PA=\left(\begin{array}{ccc}{\hat{F}}_1^{-1}& ...& {\hat{F}}_{n-1}^{-1}\end{array}\right)R=LR,$

wobei die letzte Gleichheit mit Lemma 3.13 folgt. Damit ist alles bewiesen.

q.e.d.

Man beachte, dass die Matrix $L$ (3.21) also gerade aus den aktuellen Umrechnungsfaktoren ${\hat{l}}_{ik}$ $(i>k)$ gebildet wird, nachdem (sofern erforderlich) die Zeilenvertauschung, welche die Zeile mit dem jeweils gewählten Pivotelement an die richtige Position bringt, erfolgt ist. In Implementierungen werden die frei werdenden Anteile des linken Dreiecks der Matrix $A$ sukzessive mit den Einträgen der unteren Dreiecksmatrix $L$ überschrieben, während sich in dem rechten Dreieck der Matrix $A$ die Einträge der Dreiecksmatrix $R$ ergeben. Die Permutationsmatrix $P$, deren Zeilen $(e^{r_i}{)}^T,i=1,...,n$ genannt seien, lässt sich einfach in Form eines Buchhaltungsvektors $r\in {\mathbb{N}}^n$ angeben, und es gilt, wie man mit Satz 3.10 erschließt,

$\left(\begin{array}{c}{r}_1\\ ⋮\\ r_n\end{array}\right)=P\left(\begin{array}{c}1\\ ⋮\\ n\end{array}\right)$

Wir wollen die Vorgehensweise an einem Beispiel vorführen.

Beispiel 3.16

Gegeben sei die Matrix

$A:=\left(\begin{array}{cccc}0& 0& 1& 1\\ 2& 2& 2& 2\\ 1& 2& 2& 2\\ 1& 2& 3& 6\end{array}\right).$

Nach Anhängen des für die Speicherung der Zeilenpermutationen zuständigen Buchhaltervektors liefert der Algorithmus folgendes (unterhalb der Treppe ergeben sich sukzessive die Einträge von $L$ aus (3.21), (3.22)):

$\left(\begin{array}{cccc}0& 0& 1& 1\\ 2& 2& 2& 2\\ 1& 2& 2& 2\\ 1& 2& 3& 6\end{array}\right),\left(\begin{array}{c}1\\ 2\\ 3\\ 4\end{array}\right)\underset{⟶}{\text{ Zeilentausch }}\left(\begin{array}{cccc}2& 2& 2& 2\\ 0& 0& 1& 1\\ 1& 2& 2& 2\\ 1& 2& 3& 6\end{array}\right),\left(\begin{array}{c}2\\ 1\\ 3\\ 4\end{array}\right)$

$\underset{⟶}{\text{Elimination }}\left(\begin{array}{cccc}2& 2& 2& 2\\ 0& 0& 1& 1\\ \frac{1}{2}& \underset{\_}{1}& 1& 1\\ \frac{1}{2}& 1& 2& 5\end{array}\right),\left(\begin{array}{c}2\\ 1\\ 3\\ 4\end{array}\right)\underset{⟶}{\text{ Zeilentausch }}\left(\begin{array}{cccc}2& 2& 2& 2\\ \frac{1}{2}& 1& 1& 1\\ 0& 0& 1& 1\\ \frac{1}{2}& 1& 2& 5\end{array}\right),\left(\begin{array}{c}2\\ 3\\ 1\\ 4\end{array}\right)$

$\underset{⟶}{\text{Elimination }}\left(\begin{array}{cccc}2& 2& 2& 2\\ \frac{1}{2}& 1& 1& 1\\ 0& 0& \underset{\_}{1}& 1\\ \frac{1}{2}& 1& 1& 4\end{array}\right),\left(\begin{array}{c}2\\ 3\\ 1\\ 4\end{array}\right)\underset{⟶}{\text{ Elimination }}\left(\begin{array}{cccc}2& 2& 2& 2\\ \frac{1}{2}& 1& 1& 1\\ 0& 0& 1& 1\\ \frac{1}{2}& 1& 1& 3\end{array}\right),\left(\begin{array}{c}2\\ 3\\ 1\\ 4\end{array}\right)$

Dabei ist das jeweils gewählte Pivotelement unterstrichen. Der letzte Permutationsvektor $(2,3,1,4{)}^T$ besagt, dass

$\pi (1)=3,\pi (2)=1,\pi (3)=2,\pi (4)=4$

für die zu $P$ gehörende Permutation $\pi$ gilt und dass also $PA$ aus $A$ hervorgeht, indem man die erste Zeile von $A$ in die dritte Position bringt, die zweite in die erste, usw. Es ergibt sich somit die Faktorisierung

$PA=\left(\begin{array}{cccc}2& 2& 2& 2\\ 1& 2& 2& 2\\ 0& 0& 1& 1\\ 1& 2& 3& 6\end{array}\right)=\left(\begin{array}{cccc}1& & & \\ \frac{1}{2}& 1& & \\ 0& 0& 1& \\ \frac{1}{2}& 1& 1& 1\end{array}\right)\left(\begin{array}{cccc}2& 2& 2& 2\\ & 1& 1& 1\\ & & 1& 1\\ & & & 3\end{array}\right)=LR.$

---

Man beachte, dass die Zerlegung $PA=LR$ einer Matrix nicht eindeutig ist. Man könnte ja beispielsweise die Matrix $L$ mit einem Skalar $\alpha \ne 0$ und die Matrix $R$ mit dem Skalar $1/\alpha$ multiplizieren.

Mit dem Gauß-Algorithmus kann man bekanntlich auch die Determinante von $A$ berechnen. So gilt im Fall, dass eine Zerlegung $PA=LR$ vorliegt,

$\det (P)=(-1{)}^{\sigma }$

und

$\det (PA)=\det (P)\det (A)=\det (L)\det (R)=\prod _{i=1}^n{r}_{ii},$

wobei $\sigma$ die Anzahl von paarweisen Zeilenvertauschungen ist, die die Überführung von $I$ in $P$ erfordert bzw. welche beim Gauß-Algorithmus vorgenommen wird und die $r_{ii}$ die Diagonalelemente von $R$ sind. Demnach hat man

$\det (A)=(-1{)}^{\sigma }\prod _{i=1}^n{r}_{ii}.$

3.3.4 Nachiteration

Aufgrund von Rundungsfehlern errechnet man in der Praxis nicht eine Zerlegung $LR$, sondern eine Zerlegung $\tilde{L}\tilde{R}$ von $PA$, so dass

$PA\approx \tilde{L}\tilde{R}$

gilt. Statt der (hier als eindeutig vorausgesetzten Lösung) $x$ von $Ax=b$ bzw. $PAx=Pb$ berechnet man demnach unter Verwendung von $\tilde{L}$ und $\tilde{R}$ eine Näherungslösung $x^0$ und den durch sie erzeugten Defekt

$d^0:=Pb-PA{x}^0\ne 0.$

Daher ist die folgende Nachiteration sinnvoll: wiederum unter Verwendung der vorliegenden Zerlegung $\tilde{L}\tilde{R}$ von $PA$ bestimmt man die Lösung $\delta x^0$ der Defektgleichung

(3.24) $PA\delta x=d^0$

und setzt man anschließend

$x^1:=x^0+\delta x^0.$

Bei exakter Lösung des Systems (3.24) (mit $PA$ und nicht $\tilde{L}\tilde{R}$) hätte man dann

$PA{x}^1=PA{x}^0+PA\delta x^0=Pb-d^0+d^0=Pb.$

Da man i. a. jedoch nicht exakt rechnet, könnte man diesen Prozess wiederholen. Normalerweise genügt es jedoch, $d^0$ und $\delta x^0$ mit doppelter Genauigkeit zu berechnen und die beschriebene Nachiteration nur einmal durchzuführen (vgl. Deuflhard/Hohmann).

Beispiel 3.17

Wir betrachten das Gleichungssystem $Ax=b$ mit

$A:=\left(\begin{array}{cc}1.05& 1.02\\ 1.04& 1.02\end{array}\right),b:=\left(\begin{array}{c}1\\ 2\end{array}\right).$

Die Lösung $x$ des Systems lautet

$x\approx (-100,103.921569{)}^T.$

Gauß-Elimination ohne Zeilenvertauschung liefert bei 3-stelliger Rechnung

$\tilde{L}:=\left(\begin{array}{cc}1& 0\\ .990& 1\end{array}\right),\tilde{R}:=\left(\begin{array}{cc}1.05& 1.02\\ 0& 0.01\end{array}\right)$

sowie

$\tilde{L}\tilde{R}-A=\left(\begin{array}{cc}0& 0\\ 5_{10}-4& 2_{10}-4\end{array}\right).$

Man errechnet

$x^0:=(-97.1,101{)}^T$

mit dem Defekt

$d^0:=b-A{x}^0=\{\begin{array}{cc}(0,0{)}^T& (3\text{-stellig}),\\ (0.065,0.035{)}^T& (6\text{-stellig}).\end{array}$

Nachiteration mit 6-stelliger Rechnung ergibt

$x^1:=x^0+\delta x^0=(-99.9,104{)}^T.$

3.3.5 Direkte LR-Zerlegung

In gewissen Situationen ist es möglich und zwecks Ausnutzung vorhandener Strukturen der Matrix $A:=(a_{ij})\in {ℝ}^{n\times n}$ auch sinnvoll, auf eine Pivotstrategie zu verzichten und mittels einer unteren Dreiecksmatrix $L:=(l_{ij})\in {ℝ}^{n\times n}$ und einer oberen Dreiecksmatrix $R:=(r_{ij})\in {ℝ}^{n\times n}$ eine LR-Zerlegung der Form

(3.25) $\left(\begin{array}{cccc}{a}_{11}& a_{12}& ...& a_{1n}\\ a_{21}& a_{22}& ...& a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& ...& a_{nn}\end{array}\right)=\left(\begin{array}{cccc}1& & & \\ l_{21}& 1& & \\ ⋮& \ddots & \ddots & \\ l_{n1}& ...& l_{n,n-1}& 1\end{array}\right)\left(\begin{array}{cccc}{r}_{11}& r_{12}& ...& r_{1n}\\ & r_{22}& ...& r_{2n}\\ & & \ddots & ⋮\\ & & & r_{nn}\end{array}\right)$

auf direkte Weise zu bestimmen. Eine solche Zerlegung einer regulären Matrix $A$ existiert genau dann, wenn $\det (H_k)\ne 0$ $(k=1,...,n)$ für die Hauptuntermatrizen

(3.26) $H_k:=\left(\begin{array}{ccc}{a}_{11}& ...& a_{1k}\\ ⋮& \ddots & ⋮\\ a_{k1}& ...& a_{kk}\end{array}\right)\in {ℝ}^{k\times k},k=1,...,n$

von $A$ gilt (z. B. Sätze 2.14 und 2.17 bei Kanzow). Wegen $\det (A)\ne 0$ ist dann auch $\det (R)\ne 0$, also $r_{ii}\ne 0$ $(i=1,...,n)$ und damit das folgende Vorgehen möglich.

Existiert eine LR-Zerlegung von $A$ wie in (3.25), so verwendet den Ansatz in (3.25), um für die $n^2$ gesuchten Größen $r_{ik}$ $(i\le k)$ und $l_{ik}$ $(i>k)$ die $n^2$ Bestimmungsgleichungen

$a_{ik}=\sum _{j=1}^n{l}_{ij}{r}_{jk},i,k=1,...,n$

zu erhalten, welche wegen $l_{ij}=0$ für $i<j$ und $r_{jk}=0$ für $j>k$ mit

(3.27) $a_{ik}=\sum _{j=1}^{\min (i,k)}{l}_{ij}{r}_{jk},i,k=1,...,n$

identisch sind. Dabei gibt es verschiedene Möglichkeiten, wie man aus den Gleichungen (3.27) die Einträge von $L$ und $R$ bestimmen kann. Zum Beispiel führt eine Berechnung der Zeilen von $R$ und der Spalten von $L$ entsprechend der Parkettierung auf den folgenden Algorithmus:

Algorithmus 2 (Direkte LR-Zerlegung)

(0) Gib $A:=(a_{ij})\in {ℝ}^{n\times n}$ mit $\det (A)\ne 0$ und setze $i:=1$.

(1) Berechne

$r_{ik}:=a_{ik}-\sum _{j=1}^{i-1}{l}_{ij}{r}_{jk}(k=i,...,n),$

$l_{ki}:=(a_{ki}-\sum _{j=1}^{i-1}{l}_{kj}{r}_{ji})/r_{ii}(k=i+1,...,n).$

(2) Falls $i=n$, stop!

(3) Setze $i:=i+1$ und gehe nach (1).

Für eine solche direkte LR-Zerlegung sind insgesamt $(n^3/3)(1+0(1/n))$, d. h. die gleiche Größenordnung von Multiplikationen und Divisionen wie für den Gauß-Algorithmus erforderlich.

Cholesky-Zerlegung positiv definiter Matrizen

In diesem Abschnitt zeigen wir, dass die eben vorgestellte LR-Zerlegungen für positiv definite Matrizen besonders attraktiv ist.

Definition - positiv definite Matrix

Eine Matrix $A\in {ℝ}^{n\times n}$ heißt positiv definit, falls $A$ symmetrisch, d. h. $A=A^T$ ist und falls gilt:

$⟨x,Ax⟩=x^{T}Ax>0,x\in {ℝ}^n\setminus \{0\}.$

Bemerkung - positiv definite Matrix

Mit dieser Definition selbst lässt sich, wie es ähnlich häufig in der Mathematik der Fall ist, nur schwer arbeiten. Deshalb sind äquivalente Bedingungen von Interesse.

Hesse-Matrix und ein lokales Minimum einer Fehlerfunktion

Sei $f:U\subset {ℝ}^n\to ℝ$ eine zweimal stetig differenzierbare Funktion. Dann ist die Hesse-Matrix von $f$ am Punkt $x=(x_1,\dots ,x_n)\in U$ definiert durch

${\mathrm{H}}_f(x):={(\frac{{\partial }^{2}f}{\partial x_i\partial x_j}(x))}_{i,j=1,\dots ,n}=\left(\begin{array}{cccc}\frac{{\partial }^{2}f}{\partial x_1\partial x_1}(x)& \frac{{\partial }^{2}f}{\partial x_1\partial x_2}(x)& \cdots & \frac{{\partial }^{2}f}{\partial x_1\partial x_n}(x)\\ \frac{{\partial }^{2}f}{\partial x_2\partial x_1}(x)& \frac{{\partial }^{2}f}{\partial x_2\partial x_2}(x)& \cdots & \frac{{\partial }^{2}f}{\partial x_2\partial x_n}(x)\\ ⋮& ⋮& \ddots & ⋮\\ \frac{{\partial }^{2}f}{\partial x_n\partial x_1}(x)& \frac{{\partial }^{2}f}{\partial x_n\partial x_2}(x)& \cdots & \frac{{\partial }^{2}f}{\partial x_n\partial x_n}(x)\end{array}\right).$

Ist die Hesse-Matrix an einer Stelle $x=(x_1,\dots ,x_n)\in U$ positiv definit, wobei gleichzeitig der Gradient der Nullvektor ist, dann besitzt $f$ ein lokales Minimum.

Lemma - Kriterien für positive Definitheit

Folgende Aussagen sind für eine Matrix $A:=(a_{ij})\in {ℝ}^{n\times n}$ mit $A=A^T$ äquivalent:

• (i) $A$ ist positiv definit.
• (ii) Alle Eigenwerte ${\lambda }_i$ $(i=1,...,n)$ von $A$ sind reell und positiv.
• (iii) Die Determinanten der $n$ Hauptuntermatrizen $H_k$ $(k=1,...,n)$ von $A$ in (3.26) sind alle positiv.

Bemerkung - Kriterien für positive Definitheit

Den Beweis des Lemmas findet man in Büchern der Linearen Algebra. Im Folgenden beweisen wir Eigenschaften positiv definite Matrizen $A$ die positiv Definitheit von allen Untermatrizen und der Invertierbarkeit der Matrix.

Lemma - positiv Definitheit von Untermatrizen

Die Matrix $A:=(a_{ij})\in {ℝ}^{n\times n}$ sei positiv definit. Dann gilt:

• (i) $A$ ist regulär,
• (ii) alle Untermatrizen von $A$ der Form

(3.29) $\left(\begin{array}{ccc}{a}_{kk}& ...& a_{k,k+\ell }\\ ⋮& \ddots & ⋮\\ a_{k+\ell ,k}& ...& a_{k+\ell ,k+\ell }\end{array}\right)\in {ℝ}^{(\ell +1)\times (\ell +1)}$

sind positiv definit,

• (iii) $\det (A)>0$.

Beweis

Der Beweis erfolgt in der Reihenfolge der drei Eigenschaften von positiv definiten Matrizen aus dem Lemma.

Beweis (i)

(i) Wäre $A$ singulär, so gäbe es einen Vektor $x\in {ℝ}^n\setminus \{0\}$ mit $Ax=0$. Damit wäre auch $x^{T}Ax=0$, was einen Widerspruch zur positiven Definitheit der Matrix $A$ darstellte.

Beweis (ii)

(ii) Sei nun $B\in {ℝ}^{(\ell +1)\times (\ell +1)}$ eine Untermatrix der Form (3.29) und $x:=(x_i)\in {ℝ}^{\ell +1}\setminus \{0\}$. Wegen der vorausgesetzten Symmetrie von $A$ ist auch $B$ symmetrisch. Für $z:=(z_i)\in {ℝ}^n$ mit

$z_i:=\{\begin{array}{cc}{x}_{i+1-k},& k\le i\le k+\ell \\ 0,& \text{sonst}\end{array}$

gilt dann $z\ne 0$ sowie

$x^{T}Bx=\sum _{i,j=k}^{k+\ell }{a}_{ij}{x}_{i+1-k}{x}_{j+1-k}=\sum _{i,j=k}^{k+\ell }{a}_{ij}{z}_i{z}_j=\sum _{i,j=1}^n{a}_{ij}{z}_i{z}_j=z^{T}Az>0.$

Beweis (iii)

(iii) Die Eigenwerte ${\lambda }_1,...,{\lambda }_n$ von $A$ sind (reell und) positiv, denn für $x^{(k)}\in {ℝ}^n\setminus \{0\}$ mit $A{x}^{(k)}={\lambda }_k{x}^{(k)}$ gilt ja

$0<(x^{(k)}{)}^{T}A{x}^{(k)}={\lambda }_k[(x^{(k)}{)}^{T}x(k)],k=1,...,n$

(siehe auch Lemma 3.19). Weiter ist die Matrix $A$ nach einem Ergebnis aus der Linearen Algebra diagonalisierbar, d. h., es gibt eine reguläre Matrix $S\in {ℝ}^{n\times n}$ mit

$SA{S}^{-1}=D,$

wobei $D$ die Matrix

$D:=\mathrm{diag}({\lambda }_1,...,{\lambda }_n)\in {ℝ}^{n\times n}$

ist. Somit folgt

$\det (A)=\det (S^{-1})\det (D)\det (S)=\det (D)=\prod _{k=1}^n{\lambda }_k>0.$

q.e.d.

Satz - Produktzerlegung mit unterer Dreiecksmatrix

Die Matrix $A\in {ℝ}^{n\times n}$ sei positiv definit. Dann gibt es genau eine untere Dreiecksmatrix $L:=(l_{kj})\in {ℝ}^{n\times n}$ mit $l_{kk}>0$ $(k=1,...,n)$ und

(3.30) $A=L{L}^T.$

Beweis.

Der Beweis wird mit vollständiger Induktion geführt. Für $n:=1$ ist eine positiv definite Matrix $A=(\alpha )\in {ℝ}^{1\times 1}$ eine positive Zahl $\alpha >0$. Eine solche kann eindeutig in der Form

$\alpha =l\cdot l,l=\sqrt{\alpha }$

geschrieben werden. Wir nehmen nun an, dass die Behauptung für positiv definite Matrizen bis zur Dimension $n-1$ richtig ist und betrachten jetzt eine positiv definite Matrix $A\in {ℝ}^{n\times n}$. Diese lässt sich mit der nach Lemma 3.20 positiv definiten Matrix $A_{n-1}\in {ℝ}^{(n-1)\times (n-1)}$ und einem Vektor $s\in {ℝ}^n$ in der Form

$A=\left(\begin{array}{cc}{A}_{n-1}& s\\ s^T& a_{nn}\end{array}\right)$

partitionieren, wobei $A_{n-1}$ nach der Induktionsvoraussetzung mittels einer eindeutig bestimmten unteren Dreiecksmatrix $L_{n-1}:=(l_{kj})\in {ℝ}^{(n-1)\times (n-1)}$ mit $l_{kk}>0$ $(k=1,...,n-1)$ zerlegt werden kann in

(3.31) $A_{n-1}=L_{n-1}{L}_{n-1}^T.$

Für die gesuchte Matrix $L\in {ℝ}^{n\times n}$ machen wir nun einen Ansatz der Form

$L:=\left(\begin{array}{cc}{L}_{n-1}& 0\\ c^T& \alpha \end{array}\right)$

und versuchen wir $c\in {ℝ}^{n-1}$ und $\alpha \in ℝ$ so zu bestimmen, dass

(3.32) $A=\left(\begin{array}{cc}{A}_{n-1}& s\\ s^T{a}_{nn}\end{array}\right)=\left(\begin{array}{cc}{L}_{n-1}& 0\\ c^T& \alpha \end{array}\right)\left(\begin{array}{cc}{L}_{n-1}^T& c\\ 0& \alpha \end{array}\right)$

gilt. Gleichheit in (3.32) hat man nun wegen (3.31) genau dann, wenn

(3.33) $L_{n-1}c=s,$

(3.34) $c^{T}c+{\alpha }^2=a_{nn}$

gilt. Die Gleichung (3.33) besitzt sicher eine eindeutige Lösung $c=L_{n-1}^{-1}s$, da $L_{n-1}\in {ℝ}^{(n-1)\times (n-1)}$ als untere Dreiecksmatrix mit positiven Diagonalelementen regulär ist. Auch die zweite Gleichung (3.34) besitzt offenbar eine Lösung $\alpha \in ℂ$. Aufgrund von (3.32) gilt außerdem

$\det (A)=\det \left(\begin{array}{cc}{L}_{n-1}& 0\\ c^T& \alpha \end{array}\right)\det \left(\begin{array}{cc}{L}_{n-1}^T& c\\ 0& \alpha \end{array}\right)={\alpha }^2[\det (L_{n-1}){]}^2,$

so dass wegen $\det (A)>0$ (vgl. Lemma 3.20) und $\det (L_{n-1})=\prod _{k=1}^n{l}_{kk}>0$ auch ${\alpha }^2>0$ ist und somit die Gleichung (3.34) eine eindeutige Lösung $\alpha >0$ hat. Damit ist alles gezeigt.

q.e.d.

Die Zerlegung $A=L{L}^T$ einer positiv definiten Matrix $A:=(a_{ij})\in {ℝ}^{n\times n}$ bezeichnet man als Cholesky-Zerlegung von $A$. Ein direkter Ansatz zu ihrer Bestimmung ist es, die Gleichungen $A=L{L}^T$ bzw. die Gleichungen

$\left(\begin{array}{cccc}{a}_{11}& a_{12}& ...& a_{1n}\\ a_{21}& a_{22}& ...& a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& ...& a_{nn}\end{array}\right)=\left(\begin{array}{cccc}{l}_{11}& & & \\ l_{21}& l_{22}& & \\ ⋮& \ddots & \ddots & \\ l_{n1}& ...& l_{n,n-1}& l_{nn}\end{array}\right)\left(\begin{array}{cccc}{l}_{11}& l_{21}& ...& l_{n1}\\ & l_{22}& ...& l_{n2}\\ & & \ddots & ⋮\\ & & & l_{nn}\end{array}\right)$

als $n(n+1)/2$ Bestimmungsgleichungen für die $n(n+1)/2$ gesuchten Größen $l_{ik}$ $(i\ge k)$ aufzufassen:

$a_{ik}=\sum _{j=1}^k{l}_{ij}{l}_{kj},1\le k\le i\le n(i=1,...,n).$

Spaltenweise Berechnung der Einträge der unteren Dreiecksmatrix $L\in {ℝ}^{n\times n}$ aus diesen Gleichungen führt auf den folgenden Algorithmus:

Algorithmus 3 (Cholesky-Zerlegung)

(0) Gib eine positiv definite Matrix $A:=(a_{ij})\in {ℝ}^{n\times n}$ und setze $k:=1$.

(1) Berechne

$l_{kk}:={(a_{kk}-\sum _{j=1}^{k-1}{l}_{kj}^2)}^{1/2},$

$l_{ik}:=(a_{ik}-\sum _{j=1}^{k-1}{l}_{ij}{l}_{kj})/l_{kk}(i=k+1,...,n).$

(2) Falls $k=n$, stop!

(3) Setze $k:=k+1$ und gehe nach (1).

Beispiel 3.22

Gegeben sei die positiv definite Matrix

$A:=(a_{ij})=\left(\begin{array}{ccc}1& 2& 1\\ 2& 5& 2\\ 1& 2& 10\end{array}\right).$

Dann errechnet man für den Spaltenindex $k:=1$ die Einträge

$l_{11}:=\sqrt{a_{11}}=\sqrt{1}=1,$

$l_{21}:=a_{21}/l_{11}=2/1=2,$

$l_{31}:=a_{31}/l_{11}=1/1=1,$

für den Spaltenindex $k:=2$ die Einträge

$l_{22}:=\sqrt{a_{22}-l_{21}^2}=\sqrt{5-4}=1,$

$l_{32}:=(a_{32}-l_{31}{l}_{21})/l_{22}=(2-1\cdot 2)/1=0$

und schließlich für den Spaltenindex $k:=3$ den Eintrag

$l_{33}:=\sqrt{a_{33}-l_{31}^2-l_{32}^2}=\sqrt{10-1^2-0^2}=3.$

Somit erhält man für $A$ die Cholesky-Zerlegung

$A=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 1& 0& 3\end{array}\right)\left(\begin{array}{ccc}1& 2& 1\\ 0& 1& 0\\ 0& 0& 3\end{array}\right).$

---

Eine Cholesky-Zerlegung erfordert insgesamt die folgende Anzahl von Multiplikationen, Divisionen und Berechnungen von Quadratwurzeln:

$\sum _{k=1}^n[k+\sum _{i=k+1}^{n}k]=\sum _{k=1}^n[k+(n-k)k]=\sum _{k=1}^{n}k+n\sum _{k=1}^{n}k-\sum _{k=1}^n{k}^2$

$=\frac{n(n+1)}{2}+n\frac{n(n+1)}{2}-\frac{n(n+1)(2n+1)}{6}=\frac{n^3}{6}(1+0\left(\frac{1}{n}\right)).$

Dies sind etwa halb so viele wesentliche Rechenoperationen, wie sie der Gauß-Algorithmus bzw. eine direkte LR-Zerlegung für eine beliebige reguläre Matrix erfordern.

3.3.7 Bandmatrizen

Bei der Diskretisierung von gewöhnlichen und partiellen Differentialgleichungen oder auch der Berechnung der Momente kubischer Splines (vgl. Abschnitt 7) ergeben sich lineare Gleichungssysteme $Ax=b$, bei denen $A=(a_{ij})\in {ℝ}^{n\times n}$ mit $\det (A)\ne 0$ eine Bandmatrix der Bandbreite $p+q+1$ ist, d. h. bei denen $A$ die Gestalt

(3.35) $A:=\left(\begin{array}{cccccc}{a}_{11}& ...& a_{1,q+1}& & & \\ ⋮& \ddots & & \ddots & & \\ a_{p+1,1}& & \ddots & & \ddots & \\ & \ddots & & \ddots & & a_{n-q,n}\\ & & \ddots & & \ddots & ⋮\\ & & & a_{n,n-p}& ...& a_{nn}\end{array}\right)$

hat und somit

$a_{ik}:=0,i=1,...,n,1\le k<i-p\le n,1\le i+q<k\le n$

mit gewissen $p,q\in \{1,...,n-1\}$ gilt. Insbesondere spricht man im Fall $p=q=1$, d. h. im Fall

$A:=\left(\begin{array}{cccccc}{a}_{11}& a_{12}& & & & \\ a_{21}& a_{22}& a_{23}& & & \\ & a_{32}& a_{33}& \ddots & & \\ & & \ddots & \ddots & a_{n-2,n-1}& \\ & & & a_{n-1,n-2}& a_{n-1,n-1}& a_{n-1,n}\\ & & & & a_{n,n-1}& a_{nn}\end{array}\right)$

von einer Tridiagonalmatrix.

Bei Gleichungssystemen mit Bandmatrizen lässt sich der zu betreibende Aufwand bei allen in diesem Kapitel angesprochenen Methoden verringern, außer bei denen mit Pivotstrategien, da diese die Bandstruktur im Allgemeinen zerstören. Exemplarisch soll das Vorgehen für Bandmatrizen am Beispiel der direkten LR-Zerlegung demonstriert werden. Wenn eine LR-Zerlegung für $A$ in (3.35) möglich ist (und $\det (A)\ne 0$ ist), so ist diese im Fall, dass man die Diagonaleinträge von $L$ als 1 wählt, eindeutig und von der Gestalt

$A=\left(\begin{array}{cccccc}1& & & & & \\ l_{21}& \ddots & & & & \\ ⋮& \ddots & \ddots & & & \\ l_{p+1,1}& & \ddots & \ddots & & \\ & \ddots & & \ddots & \ddots & \\ & & l_{n,n-p}& ...& l_{n,n-1}& 1\end{array}\right)\left(\begin{array}{ccccc}{r}_{11}& ...& r_{1,q+1}& & \\ & \ddots & & \ddots & \\ & & \ddots & & r_{n-q,n}\\ & & & \ddots & ⋮\\ & & & & r_{nn}\end{array}\right)$

(siehe z. B. Satz 2.29 bei Kanzow). Komponentenschreibweise geschrieben heißt dies

$a_{ik}=\sum _{j=j_0}^{\min \{i,k\}}{l}_{ij}{r}_{jk},i=1,...,n,k=\max \{1,i-p\},...,\min \{n,i+q\},j_0:=\max \{1,i-p,k-q\},$

was bei einer Parkettierung wie in (3.28) auf den folgenden Algorithmus zur Bestimmung der LR-Zerlegung der Bandmatrix $A$ führt:

Algorithmus 4 (LR-Zerlegung für Bandmatrizen)

(0) Gib eine Matrix $A:=(a_{ij})\in {ℝ}^{n\times n}$ mit

$a_{ik}:=0,i=1,...,n,1\le k<i-p\le n,1\le i+q<k\le n$

für gegebene $p,q\in \{1,...,n-1\}$ und setze $i:=1$.

(1) Für $k=i,...,\min \{i+q,n\}$ berechne $j_0=\max \{1,i-p,k-q\}$ und

$r_{ik}:=a_{ik}-\sum _{j=j_0}^{i-1}{l}_{ij}{r}_{jk}.$

(2) Für $k=i+1,...,\min \{i+p,n\}$ berechne $j_0=\max \{1,i-p,k-q\}$ und

$l_{ki}:=(a_{ki}-\sum _{j=j_0}^{i-1}{l}_{kj}{r}_{ji})/r_{ii}.$

(3) Falls $i=n$, stop!

(4) Setze $i:=i+1$ und gehe nach (1).

Ist $A$ eine Tridiagonalmatrix und schreibt man

(3.36) $\left(\begin{array}{cccc}{\alpha }_1& {\beta }_2& & \\ {\gamma }_2& {\alpha }_2& \ddots & \\ & \ddots & \ddots & {\beta }_n\\ & & {\gamma }_n& {\alpha }_n\end{array}\right)=\left(\begin{array}{cccc}1& & & \\ l_2& 1& & \\ & \ddots & \ddots & \\ & & l_n& 1\end{array}\right)\left(\begin{array}{cccc}{d}_1& r_2& & \\ & \ddots & \ddots & \\ & & \ddots & r_n\\ & & & d_n\end{array}\right),$

so vereinfacht sich Algorithmus 4 zu

Algorithmus 4* (LR-Zerlegung Tridiagonalmatrizen)

(0) Gib eine Tridiagonalmatrix $A\in {ℝ}^{n\times n}$ und schreibe $A,L$ und $R$ wie in (3.36). Setze

$d_1:={\alpha }_1,r_2:={\beta }_2$

und $i:=2$.

(1) Berechne

$l_i:={\gamma }_i/d_{i-1},d_i:={\alpha }_i-l_i{r}_i,r_{i+1}:={\beta }_{i+1}.$

(2) Falls $i=n-1$, berechne

$l_n:={\gamma }_n/d_{n-1},d_n:={\alpha }_n-l_n{r}_n$

und stoppe!

(3) Setze $i:=i+1$ und gehe nach (1).

Man kann zeigen, dass im Fall einer Tridiagonalmatrix eine LR-Zerlegung wie in (3.36) möglich ist, wenn gilt (Lemma 2.28 bei Kanzow):

$|{\alpha }_1|>|{\beta }_2|,|{\alpha }_i|\ge |{\gamma }_i|+|{\beta }_{i+1}|,i=2,...,n-1,$

$|{\alpha }_n|\ge |{\gamma }_n|,{\gamma }_i\ne 0,i=2,...,n.$

Diese Bedingungen besagen offenbar, dass man für die erste Zeile strikte und für die anderen Zeilen nur normale Diagonaldominanz fordern muss. Die Forderung ${\gamma }_i\ne 0$ $(i=2,...,n)$ macht Sinn, da im anderen Fall eine LR-Zerlegung mit $L:=I$ und $R:=A$ existiert und folglich nicht berechnet werden muss. Für die LR-Zerlegung einer Tridiagonalmatrix sind offenbar nur

$(n-2)\cdot 2+2=2n-2$

wesentliche Rechenoperationen erforderlich.

Siehe auch

• Lösung linearer Gleichungssysteme - (Foliensatz)
• Orthonormalisierungsverfahren - (Foliensatz)

Seiteninformation

Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.

Wiki2Reveal

Dieser Wiki2Reveal Foliensatz wurde für den Lerneinheit Kurs:Numerik I' erstellt der Link für die Wiki2Reveal-Folien wurde mit dem Wiki2Reveal-Linkgenerator erstellt.

• Die Seite wurde als Dokumententyp PanDocElectron-SLIDE erstellt.
• Link zur Quelle in Wikiversity: https://de.wikiversity.org/wiki/Kurs:Numerik%20I/Zerlegung%20PA%20=%20LR
• siehe auch weitere Informationen zu Wiki2Reveal und unter Wiki2Reveal-Linkgenerator.