Häufig ist in der numerischen Mathematik das Gleichungssystem für eingegebene (feste) reguläre Matrix und unterschiedliche rechte Seiten zu lösen.
Effizienzbetrachtung für den Algorithmus
[Bearbeiten]
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 wiederholt die gleichen Teiloperationen durchführen würde. Deshalb möchte man die beim Gauß-Algorithmus durchgeführten Teiloperationen von in irgendeiner Form speichern, die den Rechenaufwand reduziert.
Dieses kann in Form einer Zerlegung von der Form geschehen, wie sie im folgenden Unterabschnitt eingeführt wird, wobei eine untere Dreiecksmatrix, eine obere Dreiecksmatrix und eine Permutationsmatrix ist.
Eine solche Zerlegung bzw. Faktorisierung von kann man, wie wir zeigen wollen, mittels des Gauß-Algorithmus mit Spaltenpivotsuche gewinnen.
Ein Permutationsmatrix ist invertierbar und existiert. Damit lässt sich dann über die Gleichung Matrix über folgendes Matrixprodukt darstellen:
Liegt eine solche Faktorisierung vor, so kann man das Gleichungssystem bzw. für ein gegebenes lösen, indem man hintereinander die beiden Dreieckssysteme
löst, wobei die Lösung des ersten Systems die rechte Seite des zweiten Systems liefert.
Anwendung für unterschiedliche Vektoren b
[Bearbeiten]
Hat man das System für mehrere unterschiedliche rechte Seiten zu lösen, so muss man dann nur einmal die numerisch teuere Zerlegung bestimmen, während die Berechnung der Lösung gemäß numerisch relativ durch die Verwendung von Dreiecksmatrizen nicht mehr so rechenintensiv ist.
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 realisiert werden. Durch Matrixmultiplikation kann diese Elementarmatrizen auch zu einer Pemutationsmatrix "zusammenfassen".
- .
Geben Sie die als und die folgende Matrix in Maxima CAS ein
- .
und berechnen Sie das Matrizenprodukt über Z.A mit "." als Operatorsymbol für die Matrixmultiplikation.
Jede Matrix mit genau einer Eins und sonst nur Nullen in jeder Zeile und Spalte heißt Permutationsmatrix.
Die folgende Matrix stellt eine Permutationsmatrix dar:
Jede bijektive Abbildung heißt eine Permutation.
Zusammenhang Permutation - Permutationsmatrix
[Bearbeiten]
Offensichtlich ist genau dann eine Permutionsmatrix, wenn es eine Permutation gibt, so dass
gilt, wobei die -te Spalte der Einheitsmatrix bezeichnet.
Beispiel - Permutation - Permutationmatrix
[Bearbeiten]
Die im obigen Beispiel genannte Permutationmatrix ist die durch folgende Permutation definiert
wobei die folgende Permutationmatrix liefert
Mittels Zusammenhang von Permutation und Permutationsmatrix kann man nun die Aussagen des folgenden Satzes erschließen.
Geben Sie in Maxima die Permutationsmatrix an, die die obige Permutation durchführt.
Sei eine Permutationsmatrix und bezeichne die zu der Matrix gehörende Permutation. Dann gilt:
- (i) ist eine orthogonale Matrix, d. h. es ist .
- (ii) Es gilt
- .
- (iii) Für gilt
- (iv) Für jede Matrix mit Zeilen und Spalten gilt
- (3.6)
(i) folgt mit (3.5) aus
Die Behauptung in (ii) ergibt sich aus
Die erste Behauptung in (iii) folgt aus
die zweite folgt mit (ii) und letzterer Identität aus
Die entsprechenden Matrixversionen in (iv) folgen analog aus
sowie unter Verwendung dieser Beziehung und (ii) aus
q.e.d.
Man beachte, dass die Indizes gemäß Aussage (ii) von Satz 3.10 gerade die Indizes der Einheitsvektoren, welche die Spalten von bzw. die Zeilen von bilden, sind. Somit bewirkt also die Multiplikation einer Matrix mit einer Permutationsmatrix von links bzw. rechts eine Permutation der Zeilen bzw. Spalten von , die der Permutation der Zeilen bzw. Spalten von im Vergleich mit der Einheitsmatrix entspricht.
Seien
Dann folgt
In numerischen Implementierungen erfolgt die Abspeicherung einer Permutationsmatrix mit der zugehörigen Permutation in Form eines Vektors
- oder .
Eine besondere Rolle spielen Elementarpermutationen , die zwei Zahlen vertauschen und die restlichen Zahlen unverändert lassen. Im Fall einer Elementarpermutation gibt es also zwei Zahlen mit
- (3.7)
Hier gilt wegen
die Identität , so dass sich für die zu gehörende Permutationsmatrix (vgl. (3.5)) ergibt:
- (3.8)
Wir betrachten eine weitere wichtige Klasse von Matrizen.
Sei . Jede Matrix der Form
- (3.9)
heißt Frobenius-Matrix vom Index .
Eine Frobenius-Matrix vom Index unterscheidet sich von der Einheitsmatrix gleicher Größe also nur in der -ten Spalte und dort auch nur unterhalb der Diagonalen. Insbesondere lässt sich die prinzipielle Vorgehensweise bei den Zeilenoperationen der -ten Stufe des Gauß-Algorithmus durch Multiplikation mit einer Frobenius-Matrix vom Index beschreiben. So gilt für Vektoren
- (3.10)
Offenbar lässt sich die Frobenius-Matrix in (3.9) mit
- (3.11)
wegen
in der Form
- (3.12)
darstellen, wobei die Einheitsmatrix und wieder die -te Spalte von bezeichnet.
- Für sind die Frobenius-Matrizen vom Index regulär und es gilt für
- (3.13)
- sowie
- (3.14)
Für hat man mit (3.11) die Darstellung (3.12). Wegen
folgt
also die Regularität von sowie die behauptete Darstellung von . Im Folgenden soll nun mittels vollständiger Induktion die Identität
- (3.15)
nachgewiesen werden, welche im Fall der Formel (3.14) entspricht.
Die Darstellung in (3.15) ist sicher richtig für . Wir nehmen nun weiter an, dass sie für ein beliebiges richtig ist. Dann gilt die Darstellung in (3.15) auch für , denn
q.e.d.
Sei eine wie in (3.12) mit (3.11) dargestellte Frobenius-Matrix vom Index und eine Permutationsmatrix mit zugehöriger Elementarpermutation von der Form (3.7) mit . Dann entsteht die Matrix aus durch Vertauschen der Einträge und in der -ten Spalte, d. h.
Die Aussage ergibt sich unmittelbar aus
wobei (3.8) und Satz 3.10 (iii) sowie die Forderungen für und eingehen.
q.e.d.
3.3.3 Die LR-Zerlegung mittels Gauß-Algorithmus
[Bearbeiten]
Im Folgenden wird die allgemeine Vorgehensweise beim Gauß-Algorithmus zur sukzessiven Erzeugung von Matrizen der Form
- (3.16)
mit Spaltenpivotsuche als Folge spezieller Matrix-Operationen beschrieben. Und zwar wird im -ten Schritt entsprechend Algorithmus 1 eine Zeilenvertauschung vorgenommen. Hierbei ist eine elementare Permutationsmatrix, die nur eine Vertauschung der Zeilen und von bewirkt. ( und somit ist möglich.) Damit ergibt sich gemäß (3.6) und (3.10)
- (3.17)
mit
- (3.18)
für
- (3.19)
sowie
- (3.20)
Der Index bezeichnet dabei die Position der Zeile aus , welche das Pivotelement enthält.
- Mit den Definitionen (3.16) - (3.20) gilt die Identität für
- und
- (3.21)
- mit
- (3.22)
Für gilt mit (3.17) sowie (3.8)
und so weiter, was schließlich
- (3.23)
ergibt mit
und den Frobenius-Matrizen und
für , wobei in die letzte Identität Lemma 3.14 eingeht. Eine Umformung von (3.23) liefert dann
wobei die letzte Gleichheit mit Lemma 3.13 folgt. Damit ist alles bewiesen.
q.e.d.
Man beachte, dass die Matrix (3.21) also gerade aus den aktuellen Umrechnungsfaktoren 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 sukzessive mit den Einträgen der unteren Dreiecksmatrix überschrieben, während sich in dem rechten Dreieck der Matrix die Einträge der Dreiecksmatrix ergeben. Die Permutationsmatrix , deren Zeilen genannt seien, lässt sich einfach in Form eines Buchhaltungsvektors angeben, und es gilt, wie man mit Satz 3.10 erschließt,
Wir wollen die Vorgehensweise an einem Beispiel vorführen.
Gegeben sei die Matrix
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 aus (3.21), (3.22)):
Dabei ist das jeweils gewählte Pivotelement unterstrichen. Der letzte Permutationsvektor besagt, dass
für die zu gehörende Permutation gilt und dass also aus hervorgeht, indem man die erste Zeile von in die dritte Position bringt, die zweite in die erste, usw. Es ergibt sich somit die Faktorisierung
Man beachte, dass die Zerlegung einer Matrix nicht eindeutig ist. Man könnte ja beispielsweise die Matrix mit einem Skalar und die Matrix mit dem Skalar multiplizieren.
Mit dem Gauß-Algorithmus kann man bekanntlich auch die Determinante von berechnen. So gilt im Fall, dass eine Zerlegung vorliegt,
und
wobei die Anzahl von paarweisen Zeilenvertauschungen ist, die die Überführung von in erfordert bzw. welche beim Gauß-Algorithmus vorgenommen wird und die die Diagonalelemente von sind. Demnach hat man
Aufgrund von Rundungsfehlern errechnet man in der Praxis nicht eine Zerlegung , sondern eine Zerlegung von , so dass
gilt. Statt der (hier als eindeutig vorausgesetzten Lösung) von bzw. berechnet man demnach unter Verwendung von und eine Näherungslösung und den durch sie erzeugten Defekt
Daher ist die folgende Nachiteration sinnvoll: wiederum unter Verwendung der vorliegenden Zerlegung von bestimmt man die Lösung der Defektgleichung
- (3.24)
und setzt man anschließend
Bei exakter Lösung des Systems (3.24) (mit und nicht ) hätte man dann
Da man i. a. jedoch nicht exakt rechnet, könnte man diesen Prozess wiederholen. Normalerweise genügt es jedoch, und mit doppelter Genauigkeit zu berechnen und die beschriebene Nachiteration nur einmal durchzuführen (vgl. Deuflhard/Hohmann).
Wir betrachten das Gleichungssystem mit
Die Lösung des Systems lautet
Gauß-Elimination ohne Zeilenvertauschung liefert bei 3-stelliger Rechnung
sowie
Man errechnet
mit dem Defekt
Nachiteration mit 6-stelliger Rechnung ergibt
In gewissen Situationen ist es möglich und zwecks Ausnutzung vorhandener Strukturen der Matrix auch sinnvoll, auf eine Pivotstrategie zu verzichten und mittels einer unteren Dreiecksmatrix und einer oberen Dreiecksmatrix eine LR-Zerlegung der Form
- (3.25)
auf direkte Weise zu bestimmen. Eine solche Zerlegung einer regulären Matrix existiert genau dann, wenn für die Hauptuntermatrizen
- (3.26)
von gilt (z. B. Sätze 2.14 und 2.17 bei Kanzow). Wegen ist dann auch , also und damit das folgende Vorgehen möglich.
Existiert eine LR-Zerlegung von wie in (3.25), so verwendet den Ansatz in (3.25), um für die gesuchten Größen und die Bestimmungsgleichungen
zu erhalten, welche wegen für und für mit
- (3.27)
identisch sind. Dabei gibt es verschiedene Möglichkeiten, wie man aus den Gleichungen (3.27) die Einträge von und bestimmen kann. Zum Beispiel führt eine Berechnung der Zeilen von und der Spalten von entsprechend der Parkettierung auf den folgenden Algorithmus:
(0) Gib mit und setze .
(1) Berechne
(2) Falls , stop!
(3) Setze und gehe nach (1).
Für eine solche direkte LR-Zerlegung sind insgesamt , d. h. die gleiche Größenordnung von Multiplikationen und Divisionen wie für den Gauß-Algorithmus erforderlich.
Cholesky-Zerlegung positiv definiter Matrizen
[Bearbeiten]
In diesem Abschnitt zeigen wir, dass die eben vorgestellte LR-Zerlegungen für positiv definite Matrizen besonders attraktiv ist.
Eine Matrix heißt positiv definit, falls symmetrisch, d. h. ist und falls gilt:
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
[Bearbeiten]
Sei eine zweimal stetig differenzierbare Funktion. Dann ist die Hesse-Matrix von am Punkt definiert durch
Ist die Hesse-Matrix an einer Stelle positiv definit, wobei gleichzeitig der Gradient der Nullvektor ist, dann besitzt ein lokales Minimum.
Lemma - Kriterien für positive Definitheit
[Bearbeiten]
Folgende Aussagen sind für eine Matrix mit äquivalent:
- (i) ist positiv definit.
- (ii) Alle Eigenwerte von sind reell und positiv.
- (iii) Die Determinanten der Hauptuntermatrizen von in (3.26) sind alle positiv.
Bemerkung - Kriterien für positive Definitheit
[Bearbeiten]
Den Beweis des Lemmas findet man in Büchern der Linearen Algebra. Im Folgenden beweisen wir Eigenschaften positiv definite Matrizen die positiv Definitheit von allen Untermatrizen und der Invertierbarkeit der Matrix.
Lemma - positiv Definitheit von Untermatrizen
[Bearbeiten]
Die Matrix sei positiv definit. Dann gilt:
- (i) ist regulär,
- (ii) alle Untermatrizen von der Form
- (3.29)
- sind positiv definit,
- (iii) .
Der Beweis erfolgt in der Reihenfolge der drei Eigenschaften von positiv definiten Matrizen aus dem Lemma.
(i) Wäre singulär, so gäbe es einen Vektor mit . Damit wäre auch , was einen Widerspruch zur positiven Definitheit der Matrix darstellte.
(ii) Sei nun eine Untermatrix der Form (3.29) und . Wegen der vorausgesetzten Symmetrie von ist auch symmetrisch. Für mit
gilt dann sowie
(iii) Die Eigenwerte von sind (reell und) positiv, denn für mit gilt ja
(siehe auch Lemma 3.19). Weiter ist die Matrix nach einem Ergebnis aus der Linearen Algebra diagonalisierbar, d. h., es gibt eine reguläre Matrix mit
wobei die Matrix
ist. Somit folgt
q.e.d.
Satz - Produktzerlegung mit unterer Dreiecksmatrix
[Bearbeiten]
Die Matrix sei positiv definit. Dann gibt es genau eine untere Dreiecksmatrix mit und
- (3.30)
Der Beweis wird mit vollständiger Induktion geführt. Für ist eine positiv definite Matrix eine positive Zahl . Eine solche kann eindeutig in der Form
geschrieben werden. Wir nehmen nun an, dass die Behauptung für positiv definite Matrizen bis zur Dimension richtig ist und betrachten jetzt eine positiv definite Matrix . Diese lässt sich mit der nach Lemma 3.20 positiv definiten Matrix und einem Vektor in der Form
partitionieren, wobei nach der Induktionsvoraussetzung mittels einer eindeutig bestimmten unteren Dreiecksmatrix mit zerlegt werden kann in
- (3.31)
Für die gesuchte Matrix machen wir nun einen Ansatz der Form
und versuchen wir und so zu bestimmen, dass
- (3.32)
gilt. Gleichheit in (3.32) hat man nun wegen (3.31) genau dann, wenn
- (3.33)
- (3.34)
gilt. Die Gleichung (3.33) besitzt sicher eine eindeutige Lösung , da als untere Dreiecksmatrix mit positiven Diagonalelementen regulär ist. Auch die zweite Gleichung (3.34) besitzt offenbar eine Lösung . Aufgrund von (3.32) gilt außerdem
so dass wegen (vgl. Lemma 3.20) und auch ist und somit die Gleichung (3.34) eine eindeutige Lösung hat. Damit ist alles gezeigt.
q.e.d.
Die Zerlegung einer positiv definiten Matrix bezeichnet man als Cholesky-Zerlegung von . Ein direkter Ansatz zu ihrer Bestimmung ist es, die Gleichungen bzw. die Gleichungen
als Bestimmungsgleichungen für die gesuchten Größen aufzufassen:
Spaltenweise Berechnung der Einträge der unteren Dreiecksmatrix aus diesen Gleichungen führt auf den folgenden Algorithmus:
(0) Gib eine positiv definite Matrix und setze .
(1) Berechne
(2) Falls , stop!
(3) Setze und gehe nach (1).
Gegeben sei die positiv definite Matrix
Dann errechnet man für den Spaltenindex die Einträge
für den Spaltenindex die Einträge
und schließlich für den Spaltenindex den Eintrag
Somit erhält man für die Cholesky-Zerlegung
Eine Cholesky-Zerlegung erfordert insgesamt die folgende Anzahl von Multiplikationen, Divisionen und Berechnungen von Quadratwurzeln:
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.
Bei der Diskretisierung von gewöhnlichen und partiellen Differentialgleichungen oder auch der Berechnung der Momente kubischer Splines (vgl. Abschnitt 7) ergeben sich lineare Gleichungssysteme , bei denen mit eine Bandmatrix der Bandbreite ist, d. h. bei denen die Gestalt
- (3.35)
hat und somit
mit gewissen gilt. Insbesondere spricht man im Fall , d. h. im Fall
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 in (3.35) möglich ist (und ist), so ist diese im Fall, dass man die Diagonaleinträge von als 1 wählt, eindeutig und von der Gestalt
(siehe z. B. Satz 2.29 bei Kanzow). Komponentenschreibweise geschrieben heißt dies
was bei einer Parkettierung wie in (3.28) auf den folgenden Algorithmus zur Bestimmung der LR-Zerlegung der Bandmatrix führt:
Algorithmus 4 (LR-Zerlegung für Bandmatrizen)
[Bearbeiten]
(0) Gib eine Matrix mit
für gegebene und setze .
(1) Für berechne und
(2) Für berechne und
(3) Falls , stop!
(4) Setze und gehe nach (1).
Ist eine Tridiagonalmatrix und schreibt man
- (3.36)
so vereinfacht sich Algorithmus 4 zu
Algorithmus 4* (LR-Zerlegung Tridiagonalmatrizen)
[Bearbeiten]
(0) Gib eine Tridiagonalmatrix und schreibe und wie in (3.36). Setze
und .
(1) Berechne
(2) Falls , berechne
und stoppe!
(3) Setze 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):
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 macht Sinn, da im anderen Fall eine LR-Zerlegung mit und existiert und folglich nicht berechnet werden muss. Für die LR-Zerlegung einer Tridiagonalmatrix sind offenbar nur
wesentliche Rechenoperationen erforderlich.
Diese Lernresource können Sie als Wiki2Reveal-Foliensatz darstellen.
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.