, 23 min read

Lösung linearer Gleichungssysteme

Original post is here eklausmeier.goip.de/blog/2024/06-10-loesung-linearer-gleichungssysteme.


Bei jedem Iterationsschritt eines Newton-Raphson-Verfahrens, bzw. bei jeder Aktualisierung der Iterationsmatrix beim Newton-Kantorovich Iterationsverfahren, fällt die Lösung eines linearen Gleichungssystems an. Es ist daher von Wichtigkeit, für diesen Prozeß ein zuverlässiges und zugleich effizientes Lösungsverfahren parat zu haben.

1. Konditionszahlen von Matrizen

Wie könnte man erkennen, ob ein berechnetes Ergebnis x für ein lineares Gleichungssystem Ax=b, eine gute Näherung darstellt? Naheliegend wäre die Betrachtung des Residuums Axb. Wie das folgende Beispiel deutlich macht, ist dieses Maß mit Vorsicht zu geniessen.

1. Beispiel: Sei betrachtet das lineare Gleichungssystem

(107877565861975910)(x1x2x3x4)=(32233331).

Einige Vektoren x und ihre Bilder Ax lauten

(67.22.90.1)(32.122.932.931.1),(1.500.181.190.89)(32.0122.9932.9931.01),richtig:(1111)(32233331).

Die ersten beiden Vektoren könnten den Eindruck erwecken, daß man sich schon sehr nahe der richtigen Lösung befindet, jedoch ist beim ersten Mal keine der angegebenen Nachkommaziffern richtig, und beim zweiten Mal ist nur bei 2 Komponenten eine einzige Stelle hinter dem Komma richtig. Dies alles ist möglich, obwohl die Matrix symmetrisch ist und alle Komponenten der Matrix dem gleichen Größenbereich entstammen.

Ähnliche Verhältnisse liegen vor bei dem nachstehenden Beispiel.

2. Beispiel: Betrachtet sei nun das lediglich zweidimensionale Problem mit den Daten

A:=(1.29690.86480.21610.1441),b:=(0.86420.1440),x:=(0.99110.4870).

Der Residuenvektor ist hier exakt (108,108), dennoch lautet die exakte Lösung (2,2).

Die Empfindlichkeit, mit der ein lineares Gleichungsystem auf Änderung der Eingabedaten reagiert, wird quantitativ erfaßt durch die Konditionszahl.

3. Satz: Voraussetzungen: Die Matrix A sei invertierbar und x sei die exakte Lösung des linearen Gleichungssystems Ax=b. Bekannt sei eine Näherungslösung x^. r sei das Residuum, also r:=bAx^.

Behauptung: Es gilt die beidseitige, scharfe Abschätzung

1|A||A1||r||b|1)|xx^||x|2)|A||A1||r||b|.

Beweis: Zu 1). Wegen |r|=|bAx^|=|AxAx^||A||xx^|, ist |r|/|A||xx^|. Andererseits ist |x|=|A1b||A1||b|, also 1/(|A1||b|)1/|x|, nach Multiplikation entsprechender Seiten der beiden hergeleiteten Ungleichung die unter 1) gemachte Behauptung

1|A||A1||r||b||xx^||x|.

Diese Abschätzung ist scharf. Sei zur Abkürzung e:=xx^. Die Ungleichung wird zu einer Gleichung, wenn |Ae|=|A||e| und |A1b|=|A1||b|. Nach Definition von Matrixnormen gibt es solche Vektoren e und b, sodaß |Ae|=|A||e| und |A1b|=|A1||b|. Für b und x~:=A1be wird die Ungleichung zu einer Gleichung.

Zu 2). Erstens wegen |b|=|Ax||A||x| ist 1/|x||A|/|b|. Zweitens ist |xx^|=|A1bA1Ax^|=|A1r||A1||r|. Insgesamt ergibt sich wieder durch Multiplikation entsprechender Seiten

|xx^||x||A||A1||r||b|.

Auch diese Ungleichung ist scharf. Wähle x und r mit |Ax|=|A||x| und |A1r|=|A1||r|. Für b:=A1x und x^:=xA1r gilt Gleichheit.     ☐

4. Definition: Die Zahl κ(A):=|A||A1| heißt Konditionszahl der quadratischen Matrix A zur Norm ||.

Für rein theoretische Überlegungen stellt die Konditionszahl eine gute Beschreibung von Störungs- und Empfindlichkeitsphänomenen dar. Jedoch ist man ja gerade an der Inverse, bzw. an der Lösung des linearen Gleichungssystems interessiert. Die hier bei der Analyse auftauchende Konditionszahl ist also bei der praktischen Auflösung nicht bekannt. Es gibt Verfahren, mit denen die Konditionszahl geschätzt werden kann. Diese Verfahren sind stellenweise mit der Gaußschen Eliminationsmethode auf das engste gekoppelt und ergeben sich daher zusammen mit der Rechnung. Direkt aus der Defintion der Konditionszahl ersieht man

5. Eigenschaften: Es gelten κ(A)1 und κ(AB)κ(A)κ(B).

Mit Hilfe der Konditionszahl lässt sich eine Abschätzung einfach schreiben, welche charakterisiert, inwieweit Störungen in der Matrix A zu Veränderungen in der eigentlich gewünschten Lösung x führen.

6. Satz: Löst man statt des exakten Systems Ax=b das gestörte System A^x^=b, so gilt die scharfe Abschätzung nach oben

|xx^||x^|κ(A)|AA^||A|.

Beweis: Zunächst ist x=A1b=A1A^x^=A1(A+A^A)x^=x^+A1(A^A)x^, also xx^=A1(A^A)x^, somit |xx^||A1||AA^||x^|. Durch Erweitern mit |A|0 schließlich

|xx^||x^||A1||AA^|=|A1||A||AA^||A|.

Die Abschätzung ist offensichtlich scharf.     ☐

Die Konditionszahl charakterisiert gleichzeitig auch den Abstand zu allen nicht-invertierbaren Matrizen “in der Nähe” von A.

7. Satz: Für alle invertierbaren Matrizen A gilt

min{|AB||A|:B nicht invertierbar}1κ(A).

Für die Maximumnorm, die 1-Norm und die euklidische Norm gilt Gleichheit.

Beweis: Ist B eine beliebige nicht-invertierbare Matrix, so gibt es also einen Vektor x0, mit Bx=0. Für diesen Vektor x gilt:

|x|=|A1Ax||A1||Ax|=|A1||(AB)x||A1||AB||x|.

Daher 1|A1||AB|, somit

1κ(A)=1|A||A1||AB||A|.

Für die behauptete Gleichheit bei der Maximumnorm, schätzt man in umgekehrter Richtung ab und zeigt damit indirekt durch Eingabelung, die Gleichheit.

Zur genaueren Unterscheidung von Normen und Betragsstrichen, werde mit || die Maximumnorm bezeichnet und mit || die gewöhnliche Betragsfunktion für skalare Größen. Sei v ein Einheitsvektor mit den beiden Eigenschaften |v|=1 und |A1v|=|A1||v|. Nach Definition der zu einer Vektornorm gehörenden Matrixnorm gibt es solch einen Vektor v.

Weiter sei y:=A1v, |y|=:|ym|. Sei em der m-te Einheitsvektor; z:=ym1em und B:=Avz. Wegen By=AA1vym1ymv=0 und y0, ist B nicht invertierbar. Für beliebige Vektoren x gilt

(AB)x=ym1xmv=|ym|1|xm|v=|ym|1|xm|=y|xm|=(A1v)1|xm|=A11v|xm|=A11x.

Da x beliebig war gilt somit

AB1A1,

also

ABA1A1A=1κ(A).

Für die 1-Norm führt man den Beweis ganz ähnlich und für die euklidische Norm benutzt man den Satz über die Existenz einer Singulärwertzerlegung. Der genaue Beweis werde hier nicht ausgeführt.     ☐

In anderer Formulierung des oben schon bewiesenen Satzes, lässt sich schreiben:

8. Satz: Es sei A invertierbar und es sei A(x+Δx)=b+Δb. Dann gilt

|Δx||x|κ(A)|Δb||b|.

Der nächste Satz zeigt, daß das symmetrisierte Gleichungssystem AAx=Ab eine größere, und damit schlechtere Konditionszahl besitzt, als das ursprüngliche System. Insbesondere gelten diese Überlegungen für das Normalgleichungssystem (Ausgleichung im Sinne kleinster Quadrate), obwohl dort die entsprechenden Matrizen nicht quadratisch, also erst recht nicht invertierbar sind.

9. Satz: Für eine beliebige invertierbare Matrix A gilt κs(A)κs(AA).

Beweis: Seien μmax und μmin entsprechend die größten und kleinsten Eigenwerte von AA. Dann ist |A|s=μmax und |A1|=μmin1. Weiter ist |AA|s=μmax und |(AA)1|=μmin1. Daher ist

κs=μmaxμminμmaxμmin=κs(AA).

    ☐

Welche ist nun die beste Vorkonditionierung mit einer Diagonalmatrix? Es zeigt sich nun, daß dies gerade die normmässige Äquilibrierung aller Zeilenvektoren der Matrix A ist.

10. Satz: Ist die invertierbare (n×n)-Matrix A=(aik) normiert (äquilibriert) gemäß

k=1n|aik|=1,füri=1,,n,

so gilt für jede Diagonmalmatrix D mit detD0, die Ungleichung

κ(DA)κ(A).

κ bezeichnet hier die Konditionszahl bezüglich der Zeilensummennorm (verträgliche Norm für die Maximumnorm ||).

Beweis: siehe Werner (1975)*1972+1, Werner, Helmut. Es sei || die Maximum-Vektornorm bzw. die Zeilensummennorm bei Matrizen. Für jede Diagonalmatrix D=(dii), mit detD0 gilt

|DA|=maxi=1n(|dii|k=1n|aik|)=maxi=1n|dii|

und

|(DA)1|=|A1D1|=maxi=1n(k=1n|a~ik|1dkk)|A1|mini=1n1|dii|.

Hierbei bezeichnete a~ik die Komponenten der inversen Matrix A1. Aus den beiden obigen Gleichungen folgt

κ(DA)=|DA||(DA)1||A1|maxi=1n|dii|mini=1n1|dii|=1=|A|=κ(A).

    ☐

Versucht man nun hingegen auf beiden Seiten der Matrix eine Äquilibrierung zu erreichen, so kann man sich nach den Worten von Dahlquist und Björck u.U. ebenfalls “in die Nesseln setzen”.

11. Beispiel: Man betrachte für 0<|ε|<1 die Matrix

A:=(ε11111111),A1=14(02221ε1+ε21+ε1ε).

Sein nun D1:=diag(1,ε,ε) und D2:=diag(ε1,1,1). Die skalierte Matrix

B:=D2AD1=(1111εε1εε)

ist zwar jetzt zeilenäquilibriert, jedoch beträgt die Konditionszahl jetzt κ(B)3/ε, während hingegen κ(A)=3.

2. Elementare Zeilen- und Spaltenoperationen

Wenn auch die Cramersche Regel eine elegante Darstellung der Lösung eines linearen Gleichungssystems liefert, so ist doch selbst bei bestmöglicher Ausrechnung aller Determinanten der Aufwand höher, als derjenige von Verfahren, die im folgenden vorgestellt werden. Würde man die (n+1) Determinanten (n Zählerdeterminanten und eine Nennerdeterminante) als Summe von jeweils n Faktoren berechnen, so gelänge man zu Rechengrößenordnungen der Form (n!). Schon n=50 würde mehr als 1064 Gleitkommamultiplikationen erfordern, was selbst für Größtrechenanlagen unvertretbar lange Rechenzeiten heraufbeschwören würde. Aber, wie eben erwähnt, selbst bei bestmöglicher und effizientester Auswertung von Determinanten, wären immer noch größenordnungsmässig n4 Operationen nötig, während hingegen die im weiteren Verlaufe dargestellten Verfahren in der Größenordnung n3 liegen.

1. Ein lineares Gleichungssystem mit p Gleichungen und n Unbekannten x1, x2 bis xn hat die Form

a11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2ap1x1+ap2x2++apnxn=bp

Hierbei sind aij und bk feste gegebene Zahlen. Die aij heißen die Koeffizienten. Der erste Index (hier i) heißt Zeilenindex, der zweite Index (hier j) heißt Spaltenindex. Der Vektor (b1,,bp) heißt Vektor der rechten Seite [^{right hand side (RHS)}]. Das lineare Gleichungssystem heißt homogen, falls der Vektor der rechten Seite gleich dem Nullvektor ist, also bk=0, für alle k=1,,p.

2. Daß man beim Operieren mit Gleichungssystemen vorsichtig sein muß, zeigt das folgende Beispielgleichungssystem

x+y+z=1xy+z=0x+yz=0

Zieht man nun die drei Folgerungen, erstens die 1.te Gleichung beizubehalten, zweitens alle drei Gleichungen zusammenzuaddieren und drittens die 2.te zur 3.ten Gleichung zu addieren, so erhält man

x+y+z=1x+y+z=10=0

Aufgrund der Konstruktion ist jedes Tripel (x,y,z), welches das ursprüngliche Gleichungssystem löst auch gleichzeitig Lösung des neuen umgeformten Systems. Die Umkehrung gilt jedoch nicht! Das Tripel mit x=y=z=1/3 löst zwar das neue, umgeformte System, nicht aber das ursprüngliche. Durch Ziehen von Folgerungen können also Lösungen hinzukommen!

3. Gibt es Umformungen, die die Lösungsmenge nicht verändern? Ja, es gibt bei linearen Gleichungssystemen unendlich viele Umformungsmöglichkeiten, die die Lösungsgesamtheit nicht verändern. Drei besonders wichtige sind die nachstehenden Umformungen:

  1. Vertauschen zweier Gleichungen, und
  2. Multiplikation einer der Gleichungen mit einer Zahl0,
  3. Addition einer mit einer beliebigen Zahl multiplizierten Gleichung zu einer weiteren Gleichung.

Die nicht betroffenen Gleichungen des Systems werden beibehalten, so wie sie sind. Es gilt nun, daß die obigen drei Vertreter von Umformungen, die Lösungsgesamtheit nicht verändern. Diese drei ausgezeichneten Umformungen, heißen {\it ^{elementare Umformungen}}. Mit den obigen drei Umformungen, wäre das obige malheur nicht passiert.

4. Satz: Bei elementaren Umformungen ändert sich die Lösungsmenge nicht.

Beweis: Das oben angeschriebene Gleichungssystem lautet nach Anwendung der dritten Umformungsregel

a11x1+a12x2++a1nxn=b1(a21+λa11)x1+(a22+λa12)x2++(a2n+λa1n)xn=b2+λb1ap1x1+ap2x2++apnxn=bp

Die erste Zeile des Gleichungssytems wurde mit λ multipliziert und zur zweiten Gleichung hinzuaddiert. Die restlichen Zeilen wurden völlig unverändert übernommen. Die Lösung des alten Gleichungssystems ist zugleich auch Lösung des neuen umgeformten Lösungssystems, da aber diese Umformung rückgängig gemacht werden kann, hat das neue System genau die gleichen Lösungen. Die Rückgängigmachung geschähe dadurch, daß man die erste Gleichung mit (λ) multipliziert und zur zweiten Gleichung hinzuaddiert. Der Rest der Gleichungen wird wieder belassen.     ☐

5. Zu diesen drei elementaren Umformungen korrespondieren die folgenden sogenannten Elementarmatrizen. Die Vertauschung zweier Zeilen

(10i01j1001)

Addiert man zur i-ten Zeile von L(λ) die j-te Zeile multipliziert mit f(λ), so ist die äquivaltent mit der Linksmultiplikation mit

(j1i1f(λ)11)

Die gleiche Operation für die Spalten ist äquivalent mit der Multiplikation von rechts mit der transponierten Matrix

(1i1jf(λ)11)

Schließlich die Multiplikation der i-ten Zeile (Spalte) von L(λ) mit einer Zahl a0 ist äquivalent mit der Multiplikation von links (rechts) mit der Matrix

(j11ia11)

3. Die LU-Zerlegung

1. Die Produktzerlegung der Matrix ACn×n in A=LU, mit Subdiagonalmatrix L und Superdiagonalmatrix U heißt eine LU-Zerlegung. Wie das Beispiel der Matrix A=(0110) zeigt, braucht es nicht unbedingt immer eine LU-Zerlegung zu geben.

Gibt es jedoch eine LU-Zerlegung, so ist diese Zerlegung unter gewissen Normierungsbedingungen auch eindeutig.

2. Satz: Die Zerlegung einer invertierbaren Matrix A in das Produkt A=LU, einer Superdiagonalmatrix U und einer normierten Subdiagonalmatrix L (Subdiagonalmatrix mit lauter Einsen in der Diagonalen), ist eindeutig, wenn sie existiert.

Beweis: A sei zerlegbar in die beiden Produkte A=LU=L^U^, mit Superdiagonalmatrizen U, U^ und normierten Subdiagonalmatrizen L, L^. Das Produkt von Superdiagonalmatrizen ist wieder eine Superdiagonalmatrix. Durch Transponierung erhält man entsprechend, daß das Produkt von Subdiagonalmatrizen wieder eine Subdiagonalmatrix ist und, daß weiter das Produkt von zwei normierten Subdiagonalmatrizen wieder eine normierte Subdiagonalmatrix ist. Nun folgt aus der Gleichung UU^1=L1L^=I, dann L^1=L1 und U^1=U1 (Eindeutigkeit der Inversen).     ☐

Die folgende Tabelle gibt an: die wesentliche Anzahl der durchzuführenden Operationen und der benötigte Speicherplatzbedarf bei vollbesetzten Matrizen, bei symmetrischen (m,m)-Bandmatrizen und dies in Abhängigkeit davon, ob eine Pivotsuche durchgeführt wird oder nicht.

  vollbesetzte Matrix Bandmatrix ohne Pivot Bandmatrix mit Pivot
Speicherplatzbedarf n2 (2m+1)n (3m+1)n
LU-Faktorisierung n3/3 (m+1)mn (2m+1)mn
Rücksubstitution n2 (2m+1)n (3m+1)n

3. Definition: ACn×n heißt ^{(m,k)-Bandmatrix} (m,k{0,,n1}) mit linksseitiger Bandbreite m und rechtsseitiger Bandbreite k, wenn A insgesamt m ^{Unterdiagonalen} und k ^{Oberdiagonalen} enthält, welche Nichtnullelemente besitzen und sonst A nur aus Nullen besteht. Eine ^{Tridiagonalmatrix} ist somit eine (1,1)-Bandmatrix, eine ^{obere Hessenbergmatrix} ist eine (1,n1)-Bandmatrix und eine ^{untere Hessenbergmatrix} ist eine (n1,1)-Bandmatrix. Hermitesche (m,k)-Bandmatrizen sind stets (m,m)-Bandmatrizen. Gelegentlich ist es nützlich zu sagen, daß A eine (m,k)-Bandmatrix ist, wenn die entsprechenden Unter- oder Überdiagonalen Nichtnullelemente enthalten können. So wäre dann die Nullmatrix eine (m,k)-Bandmatrix für jedes m,k{0,,n1}.

4. Lemma: ACn×n sei eine (m,k)-Bandmatrix und besitze eine LU-Zerlegung. Dann ist L eine (m,0)-Bandmatrix und U ist eine (0,k)-Bandmatrix.

Beweis: Es ist aij=ν=1min(i,j)iνuνj, also

u1j=a1j(j=1,,n),i1=ai1u11,i=2,,n:uij=aijν=1i1iνuνj(j=i,i+1,,n),ji=1uii(ajiν=1i1iνuνj)(j=i+1,,n).

    ☐

Umgekehrt ist das Produkt einer (m,0)-Bandmatrix mit einer (0,k)-Bandmatrix immer mindestens eine (m,k)-Bandmatrix.

5. Beispiel: Die Inversen von Bandmatrizen können einen hohen Auffüllungsgrad aufweisen. Dies zeigt

A=(1112112112112),L=U=(111111111).

Die Matrix A ist diagonal-dominant mit positiven Diagonaleinträgen, also positiv definit. L und U sind Dreiecksbandmatrizen, dennoch ist die Inverse von A vollbesetzt, nämlich

A1=(5432144321333212222111111).

4. Die Gauß-Elimination

1. Definition: Es bezeichnet B[k]:=(bij)i,j=1,,k die Matrix gebildet aus den führenden k Zeilen und Spalten. Entsprechend entgegengesetzt bezeichnet B][:=(bij)i,j=n,,n die Matrix zusammengesetzt aus den letzten Zeilen und Spalten.

2. Das Gaußsche Eliminationsverfahren mit totaler Pivotsuche (GECP: Gaussian Elimination with complete pivoting) geht wie folgt vor sich. Es sei A eine komplexe n×n Matrix.

  1. Durchsuche die Matrix A nach dem betragsmässig größten Element, das sogenannte Pivotelement. Dieses sei aij. Vertausche die i-te Zeile mit der ersten Zeile und vertausche die j-te Spalte mit der ersten Spalte. Die so neu gebildete Matrix heiße A(0).
  2. Pivotiere bzgl. a11(0), d.h. addiere ein Vielfaches der ersten Zeile zu allen darunterliegenden Zeilen, sodaß in der ersten Spalte, nur noch Nullen stehen (außer in dem ersten Element, dem Pivot, stehen dann nur noch Nullen im ersten Spaltenvektor). Die jetzt neu erhaltene Matrix heiße A(1).
  3. In gleicher Weise führe den zweiten Schritt durch für k=2,,n1, d.h. finde in A(k1)]nk+1[ das betragsmässig größte Element, nenne es Pivotelement, und vertausche dann die entsprechende Zeile und Spalte, sodaß dieses Element in die Position (k,k) kommt. Wenn das Pivotelement nicht Null ist, so pivotiere, andernfalls breche das Verfahren ganz ab: die Matrix A ist nicht invertierbar. Die neu erhaltene Matrix nenne A(k).

Die Gauß-Elimination liefert entweder eine obere Dreiecksmatrix A(n1, oder die Information, daß A nicht invertierbar ist. Wie erwähnt, heißen die Diagonalelemente akk(k1) Pivotelemente. Eine Matrix A ist genau dann invertierbar, wenn alle Pivotelemente nicht verschwinden (Produkt der Diagonalelemente ist bis auf das Vorzeichen der Wert einer Determinante). Wenn man das betragsmässig größte Element der Restmatrix A]nk[ nur in der ersten Spalte von A]nk[ sucht, also das betragsmässig größte Element der jeweils ersten Spalte sucht, anstatt in der ganzen Matrix A]nk[ danach zu suchen (w.o.), so spricht man von Gauß-Elimination mit partieller Pivotsuche. Beschränkt man sich sogar bei der Suche auf ein beliebiges nicht verschwindendes Element, so spricht man von gewöhnlicher Gauß-Elimination. Bei Handrechnung verwendet man häufig die gewöhnliche Gauß-Elimination und wählt als Pivot möglichst kleine ganze Zahlen, falls vorhanden, z.B. 1. Programmiert wird i.d.R. die Gauß-Elimination mit partieller Pivotwahl, während GECP eher selten angewendet wird.

Nach dem k-ten Eliminationsschritt sieht die umgeformte Matrix A dann wie folgt aus

A(k1)=(a11(0)a12(0)a1,k(0)a1,k+1(0)a1,n(0)a22(1)a2,k(1)a2,k+1(1)a2,n(1)0ak,k(k1)ak,k+1(k1)ak,n(k1)0)

Wüßte man im voraus, welche Zeilen und Spalten jeweils zu vertauschen wären, so könnte man diese gleich im voraus durchführen. Mit dieser so vorpräparierten Matrix bräuchte man dann keinerlei Zeilen- und Spaltenvertauschungen durchzuführen. Alle diejenigen Matrizen, bei denen diese Vorvertauschungen schon durchgeführt sind, sollen CP heißen (^{completely pivoted}).

Es sei

g(A)=maxi,j,k|aij(k)|maxi,j|aij|.

Diese Größe heißt Wachstum der Pivotstrategie.

Bei partieller Pivotwahl kann gelten g(A)=2n. Bei totaler Pivotsuche sagt die 1992 falsifizierte Wilkinsonsche Vermutung (local copy), nach James Hardy Wilkinson (1919--1986), g(A)n. Diese Abschätzung ist scharf, wie man anhand von sogenanten Hadamard-Matrizen, Jacques S. Hadamard, (1865--1963), zeigen kann. Für komplexe Matrizen sind diese Schranken zu erhöhen. Hierzu Jane Day und Brian Peterson in Day/Peterson (1988):

Wilkinson's conjecture is very intriguing---easy to state, soon believed, and apparently very difficult to resolve.

3. Proposition: ACn×n sei invertierbar und CP. Es werde der k-te Eliminationsschritt der GECP durchgeführt, k<i,jn. Dann gilt

aij(k)=A1,,k,i1,,k,jA1k1k.

Beweis: Da A CP und da Pivotierung (nämlich Linearkombination von Zeilen) die Determinante und die Hauptminoren von A nicht ändern, ergibt der Laplacesche Entwicklungssatz nach der k-ten Spalte (oder Zeile) sofort A1,,k,j1,,k,i=aij(k)A1k1k. Aufgrund der Invertierbarkeit von A folgt die gemachte Aussage.     ☐

4. Corollar: Das Pivotelement akk(k1) bei GECP ist akk(k1)=1x; x ist das (k,k)-Element der Inverse der Matrix A[1k], also von (A[1k])1. Insbesondere ist ann(n1) das Reziproke eines Elementes von A1.

Beweis: Sei B:=A[1k]. Nach der Proposition ist dann

(B1)k,k=B1,,k11,,k1B1k1k=A1,,k11,,k1A1k1k=1akk(k1).

    ☐

5. Bemerkungen: (1) GECP kann wie folgt interpretiert werden: Hat man die ersten k1 Zeilen und Spalten gewählt, so wählt man die k-te Zeile und Spalte deswegen aus, weil dann die führende k×k Determinante maximalen Betrag aufweist.

(2) Alternativ kann man argumentieren: Hat man die ersten k1 Zeilen und Spalten gewählt, so wählt man die k-te Zeile und Spalte deswegen aus, weil dann detA]nk[ minimalen Betrag aufweist.

(3) Geometrisch gesprochen: man wählt die k-te Zeile und Spalte deswegen aus, weil dann das k-Volumen des Spates gebildet aus den ersten k Zeilenvektoren und Spaltenvektoren aus A[k] maximal wird.

(4) Umgekehrt: man wählt die k-te Zeile und Spalte deswegen aus, weil damit das (nk)-Volumen des projizierten Spates minimal wird, denn Pivotieren bzgl. akk(k1) heißt Projizieren des Spates aufgespannt durch die Zeilen von A(k1)]nk+1[ in den Spat aufgespannt durch die Zeilen von A(k)]nk[.

6. Satz: Darstellungssatz für die Gauß-Elimination nach Day/Peterson (1988). Es sei ACn×n invertierbar und k<n. Die Restmatrix nach dem k-ten Eliminationsschritt ist gegeben durch

A(k)]nk[=(A1]nk[)1.

D.h. die nach dem k-ten Eliminationsschritt noch nicht in Dreiecksform vorliegende Restmatrix A(k)]nk[ ist nichts anderes als von der eigentlichen Inversen A1 die invertierte Restmatrix (A1]nk[)1. Damit stellt die Restmatrix nicht nur irgendeine Hilfsmatrix dar, sondern steht im Gegenteil mit der Inversen schon in engster Verbindung.

Beweis: Für i,j>k sei aij(k) ein beliebiges Element von A(k)]nk[. Nach der vorhergehenden Proposition und dem Satz über Minoren Inverser gilt

aij(k)=A1,,k,i1,,k,jA1k1k=(1)i+j|A|(A1)k+1,,ı^,,nk+1,,ȷ^,,nA1k1k

Erneut wegen dem Satz über die Minoren Inverser gilt

|A1]nk[|=(A1)k+1,,nk+1,,n=αk+1,,nk+1,,n|A|=A1k1k|A|

Durch Einsetzen

aij(k)=(1)i+j(A1)k+1,,ı^,,nk+1,,ȷ^,,n|A1]nk[|.

Damit ist aij(k) genau der (i,j)-Eintrag von (A1]nk[)1.     ☐

7. Corollar: Führt man vor der eigentlichen Elimination sämtliche Zeilen- und Spaltenvertauschungen im voraus durch (also Matrix ist CP), so hat dies die Bedeutung, daß für k=1,,n1 der Betrag der Determinante von A1]nk[ nicht vergrößert werden kann durch irgendwelche Zeilen- und Spaltenvertauschungen der letzten nk+1 Zeilen und Spalten von A.

Beweis: Nach den obigen Bemerkungen (3) und (4) ist GECP gleichbedeutend mit der Minimierung von |detA(k)]nk[| in jedem Schritt k, also der Maximierung von |detA1]nk[|.     ☐

Für positiv definite Matrizen A ist GE immer anwendbar und zugleich liefert GE ein einfaches Kriterium zur Überprüfung auf positve Definitheit. Es gilt nämlich

8. Satz: Voraussetzung: ACn×n sei hermitesch. (Hermite, Charles (1822--1901))

Behauptung: GE durchführbar aii(k)>0 A0.

Beweis: A positiv definit A1r1r>0 aii(k)>0, da Determinanten oder Hauptminoren sich nicht ändern bei Addition von Vielfachen von Zeilen zueinander.     ☐

9. Corollar: Jede positiv definite (hermitesche) Matrix A besitzt genau eine LU-Zerlegung der Form A=LU=LDL, mit einer normierten Subdiagonalmatrix L und einer Diagonalmatrix D mit lauter positiven Diagonalelementen.

Die Gauß-Elimination mit Diagonalstrategie mit positiven (Diagonal-) Pivots ist genau dann ausführbar, wenn die Matrix positiv definit ist. Also bei positiv definiten Matrizen sind Zeilen- und/oder Spaltenvertauschungen prinzipiell nicht erforderlich. Dies ist insofern von besonderem Interesse, als daß bei sehr großdimensionalen Matrizen (n>1000 beispielsweise) man besonders Wert legt auf einen geringen Auffüllungsgrad, welcher mit einer Pivotstrategie i.d.R. in einem Zielkonflikt steht. Konzentriert man sich daher bei positiv definiten Matrizen allein darauf, den Auffüllungsgrad gering zu halten, so bleibt dennoch die Gauß-Elimination immer durchführbar.

Genauso zeigt man: GE durchführbar A1r1r0, da auch hier wieder sich die Hauptminoren nicht ändern bei Linearkombination von Zeilen. Damit hat man: Eine Matrix A besitzt genau dann eine LU-Zerlegung, wenn alle führenden Hauptminoren nicht verschwinden. Dies deswegen, weil die Existenz einer LU-Zerlegung äquivalent ist mit der Durchführbarkeit der Gauß-Elimination ohne irgendwelche Zeilen- oder Spaltenvertauschungen.