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 für ein
lineares Gleichungssystem , eine gute Näherung darstellt?
Naheliegend wäre die Betrachtung des Residuums .
Wie das folgende Beispiel deutlich macht, ist dieses Maß mit Vorsicht
zu geniessen.
1. Beispiel: Sei betrachtet das lineare Gleichungssystem
Einige Vektoren und ihre Bilder lauten
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
Der Residuenvektor ist hier exakt , dennoch lautet
die exakte Lösung .
Die Empfindlichkeit, mit der ein lineares Gleichungsystem auf
Änderung der Eingabedaten reagiert, wird quantitativ erfaßt durch die
Konditionszahl.
3. Satz: Voraussetzungen: Die Matrix sei invertierbar und
sei die exakte Lösung des linearen Gleichungssystems .
Bekannt sei eine Näherungslösung .
sei das Residuum, also .
Behauptung: Es gilt die beidseitige, scharfe Abschätzung
Beweis: Zu 1). Wegen ,
ist .
Andererseits ist , also
, nach Multiplikation entsprechender
Seiten der beiden hergeleiteten Ungleichung die unter 1) gemachte Behauptung
Diese Abschätzung ist scharf.
Sei zur Abkürzung .
Die Ungleichung wird zu einer Gleichung, wenn und
.
Nach Definition von Matrixnormen gibt es solche Vektoren und ,
sodaß und .
Für und wird die Ungleichung zu einer
Gleichung.
Zu 2). Erstens wegen
ist .
Zweitens ist .
Insgesamt ergibt sich wieder durch Multiplikation entsprechender Seiten
Auch diese Ungleichung ist scharf.
Wähle und mit und
.
Für und gilt Gleichheit.
☐
4. Definition: Die Zahl
heißt
Konditionszahl der quadratischen Matrix 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 und
.
Mit Hilfe der Konditionszahl lässt sich eine Abschätzung einfach schreiben,
welche charakterisiert, inwieweit Störungen in der Matrix zu
Veränderungen in der eigentlich gewünschten Lösung führen.
6. Satz: Löst man statt des exakten Systems das gestörte
System , so gilt die scharfe Abschätzung nach oben
Beweis: Zunächst ist
,
also , somit
.
Durch Erweitern mit schließlich
Die Abschätzung ist offensichtlich scharf.
☐
Die Konditionszahl charakterisiert gleichzeitig auch den Abstand zu allen
nicht-invertierbaren Matrizen “in der Nähe” von .
7. Satz: Für alle invertierbaren Matrizen gilt
Für die Maximumnorm, die 1-Norm und die euklidische Norm gilt Gleichheit.
Beweis: Ist eine beliebige nicht-invertierbare Matrix, so gibt es
also einen Vektor , mit .
Für diesen Vektor gilt:
Daher , somit
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 ein Einheitsvektor mit den beiden Eigenschaften
und .
Nach Definition der zu einer Vektornorm gehörenden Matrixnorm gibt es
solch einen Vektor .
Weiter sei , .
Sei der -te Einheitsvektor; und .
Wegen und , ist nicht invertierbar.
Für beliebige Vektoren gilt
Da beliebig war gilt somit
also
Für die -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 invertierbar und es sei
.
Dann gilt
Der nächste Satz zeigt, daß das symmetrisierte Gleichungssystem
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 gilt
.
Beweis: Seien und entsprechend die
größten und kleinsten Eigenwerte von .
Dann ist
und .
Weiter ist
und .
Daher ist
☐
Welche ist nun die beste Vorkonditionierung mit einer Diagonalmatrix?
Es zeigt sich nun, daß dies gerade die normmässige Äquilibrierung aller
Zeilenvektoren der Matrix ist.
10. Satz: Ist die invertierbare -Matrix
normiert (äquilibriert) gemäß
ü
so gilt für jede Diagonmalmatrix mit , die Ungleichung
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 , mit gilt
und
Hierbei bezeichnete die Komponenten der inversen
Matrix .
Aus den beiden obigen Gleichungen folgt
☐
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
die Matrix
Sein nun und
.
Die skalierte Matrix
ist zwar jetzt zeilenäquilibriert, jedoch beträgt die Konditionszahl jetzt
, während hingegen .
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 Determinanten ( Zählerdeterminanten und
eine Nennerdeterminante) als Summe von jeweils Faktoren berechnen,
so gelänge man zu Rechengrößenordnungen der Form .
Schon würde mehr als 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
Operationen nötig, während hingegen die im weiteren Verlaufe
dargestellten Verfahren in der Größenordnung liegen.
1. Ein lineares Gleichungssystem mit Gleichungen und Unbekannten
, bis hat die Form
Hierbei sind und feste gegebene Zahlen.
Die heißen die Koeffizienten.
Der erste Index (hier ) heißt Zeilenindex, der zweite Index (hier )
heißt Spaltenindex.
Der Vektor 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 , für
alle .
2. Daß man beim Operieren mit Gleichungssystemen vorsichtig sein muß,
zeigt das folgende Beispielgleichungssystem
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
Aufgrund der Konstruktion ist jedes Tripel , welches das
ursprüngliche Gleichungssystem löst auch gleichzeitig Lösung des
neuen umgeformten Systems.
Die Umkehrung gilt jedoch nicht!
Das Tripel mit 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:
Vertauschen zweier Gleichungen, und
Multiplikation einer der Gleichungen mit einer Zahl,
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
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
⋰⋰
Addiert man zur -ten Zeile von die -te Zeile
multipliziert mit , so ist die äquivaltent mit der
Linksmultiplikation mit
Die gleiche Operation für die Spalten ist äquivalent mit der Multiplikation
von rechts mit der transponierten Matrix
Schließlich die Multiplikation der -ten Zeile (Spalte) von
mit einer Zahl ist äquivalent mit der Multiplikation von links
(rechts) mit der Matrix
3. Die -Zerlegung
1. Die Produktzerlegung der Matrix in
, mit Subdiagonalmatrix und Superdiagonalmatrix
heißt eine -Zerlegung.
Wie das Beispiel der Matrix zeigt, braucht
es nicht unbedingt immer eine -Zerlegung zu geben.
Gibt es jedoch eine -Zerlegung, so ist diese Zerlegung unter
gewissen Normierungsbedingungen auch eindeutig.
2. Satz: Die Zerlegung einer invertierbaren Matrix in das
Produkt , einer Superdiagonalmatrix und einer
normierten Subdiagonalmatrix (Subdiagonalmatrix mit lauter Einsen in
der Diagonalen), ist eindeutig, wenn sie existiert.
Beweis: sei zerlegbar in die beiden Produkte ,
mit Superdiagonalmatrizen , und normierten Subdiagonalmatrizen
, .
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
, dann und
(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 -Bandmatrizen und dies in Abhängigkeit
davon, ob eine Pivotsuche durchgeführt wird oder nicht.
vollbesetzte Matrix
Bandmatrix ohne Pivot
Bandmatrix mit Pivot
Speicherplatzbedarf
LU-Faktorisierung
Rücksubstitution
3. Definition: heißt
^{-Bandmatrix} () mit linksseitiger
Bandbreite und
rechtsseitiger Bandbreite ,
wenn insgesamt ^{Unterdiagonalen} und ^{Oberdiagonalen} enthält,
welche Nichtnullelemente besitzen und sonst nur aus Nullen besteht.
Eine ^{Tridiagonalmatrix} ist somit eine -Bandmatrix, eine ^{obere
Hessenbergmatrix} ist eine -Bandmatrix
und eine ^{untere Hessenbergmatrix} ist eine
-Bandmatrix.
Hermitesche -Bandmatrizen sind stets -Bandmatrizen.
Gelegentlich ist es nützlich zu sagen, daß eine -Bandmatrix ist,
wenn die entsprechenden Unter- oder Überdiagonalen Nichtnullelemente enthalten
können.
So wäre dann die Nullmatrix eine
-Bandmatrix für jedes .
4. Lemma: sei eine -Bandmatrix und
besitze eine -Zerlegung.
Dann ist eine -Bandmatrix und ist eine -Bandmatrix.
Beweis: Es ist ,
also
☐
Umgekehrt ist das Produkt einer -Bandmatrix mit einer -Bandmatrix
immer mindestens eine -Bandmatrix.
5. Beispiel: Die Inversen von Bandmatrizen können einen hohen
Auffüllungsgrad aufweisen.
Dies zeigt
Die Matrix ist diagonal-dominant mit positiven Diagonaleinträgen,
also positiv definit.
und sind Dreiecksbandmatrizen, dennoch ist die Inverse von
vollbesetzt, nämlich
4. Die Gauß-Elimination
1. Definition: Es bezeichnet
die Matrix gebildet aus den führenden Zeilen und Spalten.
Entsprechend entgegengesetzt bezeichnet
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 eine komplexe Matrix.
Durchsuche die Matrix nach dem betragsmässig größten Element,
das sogenannte Pivotelement.
Dieses sei .
Vertausche die -te Zeile mit der ersten Zeile und vertausche die
-te Spalte mit der ersten Spalte.
Die so neu gebildete Matrix heiße .
Pivotiere bzgl. , 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 .
In gleicher Weise führe den zweiten Schritt durch für
, d.h. finde in das
betragsmässig größte Element, nenne es Pivotelement, und vertausche dann
die entsprechende Zeile und Spalte, sodaß dieses Element in die
Position kommt.
Wenn das Pivotelement nicht Null ist, so pivotiere, andernfalls breche
das Verfahren ganz ab: die Matrix ist nicht invertierbar.
Die neu erhaltene Matrix nenne .
Die Gauß-Elimination liefert entweder eine obere Dreiecksmatrix
, oder die Information, daß nicht invertierbar ist.
Wie erwähnt, heißen die Diagonalelemente Pivotelemente.
Eine Matrix 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
nur in der ersten Spalte von
sucht, also das betragsmässig größte Element der jeweils ersten Spalte sucht,
anstatt in der ganzen Matrix 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 -ten Eliminationsschritt sieht die umgeformte Matrix dann
wie folgt aus
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}).
Wilkinson's conjecture is very intriguing---easy to state, soon believed,
and apparently very difficult to resolve.
3. Proposition: sei invertierbar und CP.
Es werde der -te Eliminationsschritt der GECP durchgeführt, .
Dann gilt
Beweis: Da CP und da Pivotierung (nämlich Linearkombination von
Zeilen) die Determinante und die Hauptminoren von nicht ändern, ergibt
der Laplacesche Entwicklungssatz nach der -ten Spalte (oder Zeile) sofort
Aufgrund der Invertierbarkeit von folgt die gemachte Aussage.
☐
4. Corollar: Das Pivotelement bei GECP ist
;
ist das -Element der Inverse der Matrix , also
von .
Insbesondere ist das Reziproke eines Elementes von .
Beweis: Sei .
Nach der Proposition ist dann
☐
5. Bemerkungen: (1) GECP kann wie folgt interpretiert werden:
Hat man die ersten Zeilen und Spalten gewählt, so wählt man die
-te Zeile und Spalte deswegen aus, weil dann die führende
Determinante maximalen Betrag aufweist.
(2) Alternativ kann man argumentieren: Hat man die ersten Zeilen und
Spalten gewählt, so wählt man die -te Zeile und Spalte deswegen aus, weil
dann minimalen Betrag aufweist.
(3) Geometrisch gesprochen: man wählt die -te Zeile und Spalte deswegen
aus, weil dann das -Volumen des Spates gebildet aus den ersten
Zeilenvektoren und Spaltenvektoren aus maximal wird.
(4) Umgekehrt: man wählt die -te Zeile und Spalte deswegen aus, weil
damit das -Volumen des projizierten Spates minimal wird, denn
Pivotieren bzgl. heißt Projizieren des Spates aufgespannt
durch die Zeilen von in den Spat aufgespannt
durch die Zeilen von .
6. Satz: Darstellungssatz für die Gauß-Elimination nach
Day/Peterson (1988).
Es sei invertierbar und .
Die Restmatrix nach dem -ten Eliminationsschritt ist gegeben durch
D.h. die nach dem -ten Eliminationsschritt noch nicht in Dreiecksform
vorliegende Restmatrix ist nichts anderes als
von der eigentlichen Inversen die invertierte Restmatrix
.
Damit stellt die Restmatrix nicht nur irgendeine Hilfsmatrix dar, sondern
steht im Gegenteil mit der Inversen schon in engster Verbindung.
Beweis: Für sei ein beliebiges Element von
.
Nach der vorhergehenden Proposition und dem Satz über Minoren Inverser gilt
Erneut wegen dem Satz über die Minoren Inverser gilt
Durch Einsetzen
Damit ist genau der -Eintrag von
.
☐
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 der Betrag der Determinante
von nicht vergrößert werden kann durch irgendwelche
Zeilen- und Spaltenvertauschungen der letzten Zeilen und Spalten
von .
Beweis: Nach den obigen Bemerkungen (3) und (4) ist GECP gleichbedeutend
mit der Minimierung von in jedem
Schritt , also der Maximierung von .
☐
Für positiv definite Matrizen ist GE immer anwendbar und zugleich liefert
GE ein einfaches Kriterium zur Überprüfung auf positve Definitheit.
Es gilt nämlich
Beweis: positiv definit , da Determinanten oder Hauptminoren sich nicht ändern bei
Addition von Vielfachen von Zeilen zueinander.
☐
9. Corollar: Jede positiv definite (hermitesche) Matrix
besitzt genau eine -Zerlegung der Form , mit
einer normierten Subdiagonalmatrix und einer Diagonalmatrix
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 ( 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 ,
da auch hier wieder sich die Hauptminoren nicht ändern bei Linearkombination
von Zeilen.
Damit hat man: Eine Matrix besitzt genau dann eine -Zerlegung, wenn
alle führenden Hauptminoren nicht verschwinden.
Dies deswegen, weil die Existenz einer -Zerlegung äquivalent ist mit der
Durchführbarkeit der Gauß-Elimination ohne irgendwelche Zeilen- oder
Spaltenvertauschungen.