Zum Inhalt springen

Kurs:Numerik I/Zerlegung PA = LR

Aus Wikiversity

Einführung - Die Zerlegung PA = LR

[Bearbeiten]

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.

Zerlegung in Teiloperationen

[Bearbeiten]

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.

Umformungen als Matrixmultiplikationen

[Bearbeiten]

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

Bemerkung zur PA-LR-Darstellung

[Bearbeiten]

Ein Permutationsmatrix ist invertierbar und existiert. Damit lässt sich dann über die Gleichung Matrix über folgendes Matrixprodukt darstellen:

Faktorisierung - Lösungsschritte

[Bearbeiten]

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.

Permutationsmatrizen

[Bearbeiten]

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".

Beispiel - Vertauschung 1 und 4 Zeile

[Bearbeiten]
.

Maxima - Vertauschung 1 und 4 Zeile

[Bearbeiten]

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.

Definition - Permutationsmatrix

[Bearbeiten]

Jede Matrix mit genau einer Eins und sonst nur Nullen in jeder Zeile und Spalte heißt Permutationsmatrix.

Beispiel - Permutationsmatrix

[Bearbeiten]

Die folgende Matrix stellt eine Permutationsmatrix dar:

Definition - Permution

[Bearbeiten]

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.

Aufgabe - Studierende

[Bearbeiten]

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

Satz - Permutationsmatrizen

[Bearbeiten]

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)

Beweis.

[Bearbeiten]

(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.

Beispiel 3.11

[Bearbeiten]

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)

3.3.2 Frobenius-Matrizen

[Bearbeiten]

Wir betrachten eine weitere wichtige Klasse von Matrizen.

Definition - Frobeniusmatrix

[Bearbeiten]

Sei . Jede Matrix der Form

(3.9)

heißt Frobenius-Matrix vom Index .

Bemerkung - Frobeniusmatrix

[Bearbeiten]

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.

Lemma 3.13

[Bearbeiten]
Für sind die Frobenius-Matrizen vom Index regulär und es gilt für
(3.13)
sowie
(3.14)

Beweis.

[Bearbeiten]

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.

Lemma 3.14

[Bearbeiten]

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.

Beweis.

[Bearbeiten]

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.

Satz 3.15

[Bearbeiten]
Mit den Definitionen (3.16) - (3.20) gilt die Identität für
und
(3.21)
mit
(3.22)

Beweis.

[Bearbeiten]

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.

Beispiel 3.16

[Bearbeiten]

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

3.3.4 Nachiteration

[Bearbeiten]

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).

Beispiel 3.17

[Bearbeiten]

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

3.3.5 Direkte LR-Zerlegung

[Bearbeiten]

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:

Algorithmus 2 (Direkte LR-Zerlegung)

[Bearbeiten]

(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.

Definition - positiv definite Matrix

[Bearbeiten]

Eine Matrix heißt positiv definit, falls symmetrisch, d. h. ist und falls gilt:

Bemerkung - positiv definite Matrix

[Bearbeiten]

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) .

Beweis

[Bearbeiten]

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

Beweis (i)

[Bearbeiten]

(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.

Beweis (ii)

[Bearbeiten]

(ii) Sei nun eine Untermatrix der Form (3.29) und . Wegen der vorausgesetzten Symmetrie von ist auch symmetrisch. Für mit

gilt dann sowie

Beweis (iii)

[Bearbeiten]

(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)

Beweis.

[Bearbeiten]

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:

Algorithmus 3 (Cholesky-Zerlegung)

[Bearbeiten]

(0) Gib eine positiv definite Matrix und setze .

(1) Berechne

(2) Falls , stop!

(3) Setze und gehe nach (1).

Beispiel 3.22

[Bearbeiten]

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.

3.3.7 Bandmatrizen

[Bearbeiten]

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.


Siehe auch

[Bearbeiten]

Seiteninformation

[Bearbeiten]

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

Wiki2Reveal

[Bearbeiten]

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.