[WS] Lineare Gleichungssysteme 2 - direkte Verfahren

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Lineare Gleichungssysteme 2 - direkte Verfahren
Gliederung

  1. Lösbarkeit von Linearen Gleichungssystemen

    1a. Satz von Hurwitz (Sylvester Kriterium)
    1b. Digonaldominante Matrizen
    1c. Strikt Diagonaldominante Matrizen
    1d. Dreiecksmatrizen
    1e. Frobeniusmatrizen

  2. Lösen einfacher Gleichungssysteme

    2a. Diagonalmatrix
    2b. untere Dreiecksmatrix
    2c. obere Dreiecksmatrix

  3. LR-Zerlegung ohne Pivotisierung

    3a. Berechnung
    3b. Existenzsatz 1
    3c. Existenzsatz 2
    3d. Eindeutigkeit
    3e. Algorithmus zur Lösung des LGS Ax = b

  4. LR-Zerlegung mit Pivotisierung

    4a. Berechnung
    4b. Existenz
    4c. Eindeutigkeit - Pivotwahl
    4d. Numerische Hinweise

  5. weitere Möglichkeiten

    5a. Determinantenberechnung
    5b. Rangebstimmung
    5c. Inversenbestimmung 1 - Gauss-Algorithmus
    5d. Inversenbestimmung 2 - Gauss-Jordan Algorithmus
    5e. Inversenbestimmung 3 - Austauschauschalgorithmus

  6. Direkte LR-Zerlegung

    6a. Verfahren von Doolittle und Crout

  7. Bandmatrizen

    7a. Tridiagonalmatrizen
    7b. Allgemein zum Speichern

  8. Symmetrische positiv definite Matrizen (SPD)

    8a. LDL^T-Zerlegungen
    8b.Cholesky-Zerlegung

  9. QR-Zerlegungen

    9a. Eindeutigkeit der QR-Zerlegung
    9b. Lösen regulärer LGS Ax=b
    9c. Existenz von QR-Zerlegungen
    9d. Gram-Schmidt-Orthogonalisierung
    9e. Householder-Spiegelungen
    9f. Givens-Rotationen
tigerbine Auf diesen Beitrag antworten »
1. Lösbarkeit von Linearen Gleichungssystemen
Betrachtet werden lineare Gleichungssysteme über reellen endlich-dimensionalen Vektorräumen.








Lehrer
In den weiteren Betrachtungen wird meist A als regulär angesehen. Ziel ist es die eindeutig existierende Lösung von Ax=b zu bestimmen.
tigerbine Auf diesen Beitrag antworten »
1a. Satz von Hurwitz (Sylvester Kriterium)

********************************




Beweis:

Vgl. z.B. Fischer - Lineare Algebra
tigerbine Auf diesen Beitrag antworten »
1b. Diagonaldominate Matrizen
Eine (n x n)-Matrix heißt schwach diagonaldominant, falls die Beträge ihrer Diagonalelemente jeweils größer oder gleich der Summe der Beträge der restlichen jeweiligen Zeileneinträge sind, d.h. wenn für alle gilt

tigerbine Auf diesen Beitrag antworten »
1c. Strikt Diagonaldominate Matrizen und SPD-Matrizen
Eine (n x n)-Matrix heißt strikt diagonaldominant, falls die Beträge ihrer Diagonalelemente jeweils größer sind als die Summe der Beträge der restlichen jeweiligen Zeileneinträge , d.h. wenn für alle gilt






*******************************************

Beweis:
Es wird hier gezeigt, dass A dann eine LR-Zerlegung (ohne Pivotisierung) besitzt. Daraus folgt direkt die Regularität.






********************************************************




Beweis:
Eine symmetrische Matrix ist z.B. dann pos. definit, wenn alle EW nicht negativ sind. Sie ist nach dem Spektralsatz diagonalisierbar, d.h. es gibt eine ONB aus Eigenvektoren. Es gilt dann:




Wie sehen nun die EW der vorliegenden Matrix A aus? Sei ein EW von A mit EV x, mit . So gibt es ein maximales Element in x. Dann gilt:







Also gilt wegen der strikten Diagonaldominanz und der pos. Diagonalelemente:









************************************************






Beweis

  1. Da A positiv definit ist, gilt speziell für die Einheitsvektoren . Damit folgt die Behauptung.

  2. Angenommen, sei das betragsmaximale Element von A. Es ergibt sich folgende Fallunterscheidung:




    Sei so gewählt, dass gilt . Dann folgt mit






    Sei so gewählt, dass gilt . Dann folgt mit




    Dann ist aber A nicht positiv definit. somit ist die Behauptung falsch und das betragsmaximale Element ist ein Diagonalelement.
tigerbine Auf diesen Beitrag antworten »
1d. Dreiecksmatrizen
Produkt von Dreiecksmatrizen

  1. Sind zwei untere (normierte) Dreiecksmatrizen, so ist auch eine untere (normierte) Dreiecksmatrix.

  2. Sind zwei obere (normierte) Dreiecksmatrizen, so ist auch eine obere (normierte) Dreiecksmatrix.



Inverse von Dreiecksmatrizen
  1. Ist eine reguläre (normierte) untere Dreiecksmatrix, so ist auch eine untere (normierte) Dreiecksmatrix.

  2. Ist eine reguläre (normierte) obere Dreiecksmatrix, so ist auch eine obere (normierte) Dreiecksmatrix.




Beweis 1:

Den Beweis führt man durch Aufschreiben der Matrizenmultiplikation. Es ist für :




Handelt es sich um normierte untere Dreiecksmatrizen, so folgt analog:




Der Beweis für B folgt bereits aus A, da er sich durch Transponieren auf diesen Fall zurückführen lässt.


Beweis 2:

Setze , dann gilt und Spaltenweise genommen .


Nun schreibt man die Matrizen als Blockmatrizen, derart:



mit














so kann man schreiben:




Hieraus folgt:



Somit ist die Inverse Matrix eine untere Dreiecksmatrix. Ist L normiert, so folgt




Da eine normierte untere Dreiecksmatrix ist, folgt, dass das i-te Element des Spaltenvektors eine Eins sein muss. Da dies für alle i=1,...,n gilt, ist Die Inverse ebenfalls normiert.
 
 
tigerbine Auf diesen Beitrag antworten »
1e. Frobeniusmatrizen
Betrachtet wird hier nu das Rechnung mit Frobeniusmatrizen.

Inversion

Da eine normierte untere Dreiecksmatrix ist, existiert die Inverse und ist ebenfalls normiert. Für ihre Gestalt sei die Behauptung:






mit und als i-tem Einheitsvektor.


Es gilt dann offensichtlich und somit ergibt sich:





Produkt spezieller Frobenius-Matrizen

Auch hier soll zunächst die Behauptung allgemein formuliert werden:




Der Beweis wird dann über Induktion geführt. Der Induktionsanfang folgt aus dem vorherigen Beweis. sei die Aussage nun richtig für ein beligeiges . Dann folgt wegen

sowie mit den Darstellungen der Inversen Matrizen aus dem vorherigen Beweis und mit der IV:

tigerbine Auf diesen Beitrag antworten »
2a. Diagonalmatrix
Im Falle einer Diagonalmatrix gestaltet sich das Lösen des LGS ziemlich einfach.




Somit gilt für die Lösung:




Der daraus resultierende Algorithmus ist wohl definiert, da D regulär ist. Die Laufzeit beträgt .
tigerbine Auf diesen Beitrag antworten »
2b. untere Dreiecksmatrix
Im Fall einer unteren Dreiecksmatrix hat das LGS die Gestalt Lx=b:





Der daraus resultierende Lösungsalgorithmus heißt Vorwärtssubstitution:



FOR i = 2:1:n

END


Auch hier ist die Durchfürhrbarkeit an die Regularität der Matrix L geknüpft. Die Anzahl der Rechenoperarationen ist n². Die Laufzeit beträgt .
tigerbine Auf diesen Beitrag antworten »
2c. obere Dreiecksmatrix
Im Fall einer oberen Dreiecksmatrix hat das LGS die Gestalt Rx=b:





Der daraus resultierende Lösungsalgorithmus heißt Rückwärtssubstitution:



FOR i = (n-1):-1:1

END

Auch hier ist die Durchfürhrbarkeit an die Regularität der Matrix R geknüpft. Die Anzahl der Rechenoperarationen ist n². Die Laufzeit beträgt .
tigerbine Auf diesen Beitrag antworten »
3. LR-Zerlegung ohne Pivotisierung
Unter einer LR-Zerlegung (ohne Pivotisierung) einer Matrix versteht man eine Zerlegung in der Form , wobei eine normierte untere Dreiecksmatrix und eine obere Dreiecksmatrix ist.
tigerbine Auf diesen Beitrag antworten »
3a. Berechnung
Wie berechnet man eine LR-Zerlegung?

Aus der Schulzeit erinnert man sich vielleicht noch an das Lösen von Linearen Gleichungssystemen. Dazu wurde die Matrix A mittels Elementarer Zeileinumformungen auf Dreiecksgestalt R gebracht (Änderungen wirken sich auch auf b aus) und das neue LGS wurde durch Rückwärtssubstitution gelöst. Würde man die an A,b durchgeführten Änderungen in einer Matrix L speichern, so ergäbe sich:



Damit sei die Motivation erklärt, wie man mittels Frobeniusmatrizen letztendlich die LR-Zerlegung der Matrix konstruiert.


Die Konstruktion des Algorithmus soll hier dabei an einem Beispiel erläutert werden:



Nun sollen die Eintrage in der ersten Spalte unterhalb der Diagonale annulliert werden. Dies geschieht (Nachrechnen) durch folgende Matrizenmultiplikation:



Nun ist die zweite Spalte an der Reihe:




Bleibt noch die dritte Spalte:




Nun kommen 2 Interessante Details. Man überprüfe durch nachrechnen, dass gilt (2),(3):







Lehrer
Dieses einfache Übertragen der Einträge funktioniert nicht bei , denn:

tigerbine Auf diesen Beitrag antworten »
3b. Existenzsatz 1
Die reguläre Matrix A besitzt eine LR-Zerlegung ohne Pivotisierung



Alle Hauptabschnittsmatrizen regulär sind. Eine Hauptabschnittsmatrix ist genau dann regulär, wenn gilt .


Beweis:



Besitze A eine LR-Zerlegung. Dann existiert eine normierte untere Dreiecksmatrix und eine obere Dreiecksmatrix mit . Aus und der Regularität von A folgt . Da es sich um Dreiecksmatirzen handelt folgt sofort, dass auch alle ihre Hauptabschnittsmatrizen regulär sind.

Durch "Nachrechnen" zeigt man die Gültigkeit von



für jede (nicht notwendigerweise normierte) Dreiecksmatrix. Damit folgt:






Seien alle Hauptabschnittsmatrizen positiv. Die Existenz der LR-Zerlegung weißt man durch die in diesem Falle Wohldefiniertheit des Algorithmus ihrer Berechnung nach. Es muss also gezeigt werden, dass alle Pivotelemente von Null verschieden sind. Der Beweis wird durch Induktion geführt:


tigerbine Auf diesen Beitrag antworten »
3c. Existenzsatz 2
Die reguläre Matrix A ist diagonaldominant



Es existiert eine LR Zerlegung A=LR ohne Pivotisierung.



Beweis



Die Matrix hat dann die Gestalt:













Man kann also alle Schritte ohne Pivotisierung durchführen.

Lehrer
Im Falle der strikten Diagonaldominanz folgt hiermit sogar direkt, dass A regulär ist.
tigerbine Auf diesen Beitrag antworten »
3d. Eindeutigkeit
Seien und zwei LR-Zerlegungen von A. Dann gilt:



Aufgrund der Regularität von A folgt dann:




Damit folgt wegen der Gestalt (L ist normiert), dass gelten muss:



Somit folgt:



Und die Zerlegung ist Eindeutig.
tigerbine Auf diesen Beitrag antworten »
3e. Algorithmus zur Lösung des LGS Ax = b


Gemäßt 2.6 bedeutet gerade die Gestalt einer Frobeniusmatrix.


Bei der Durchführung der LR-Zerlegung wird man die Elemente der Matrix A sukzessive überschreiben. Dabei geht die Diagonale von L verloren, aber die ist ja definiert durch lauter Einsen. Der Algorithmus sieht dann wie folgt aus:





Nun soll ja das LGS Ax = b, bzw LRx = b gelöst werden.



Dazu löst man zunächst Ly = b durch Vorwärtssubstitution und speichert y durch überschreiben von b. Danach löst man Rx=y durch Rückwärtssubstitution und speichert wieder die Lösung in b.



Die Anzahl der Rechenoperationen der Gaußeleiminationen ist , so dass man ein LGS in der Laufzeit lösen kann.
tigerbine Auf diesen Beitrag antworten »
4. LR-Zerlegung mit Pivotisierung
In der Praxis wird jedoch häufiger der Fall einer LR-Zerlegung mit Pivotisierung auftreten, d.h. die Matrix A muss erst noch "aufbereitet" werden. Man schreibt die Zerlegung dann in der Form , wobei P eine Permutationsmatrix ist.


Selbst wenn eine Pivotisierung nicht nötig ist, ist es am Ende günstiger die Matrix gleich durch diesen Algorithmus zu schicken. Denn bei der LR-Zerlegung ohne Pivotisierung muss man ja noch den Aufwand hinzunehmen, nachzuprüfen, ob diese Überhaupt möglich ist.

Ein weiterer Vorteil ist, dass man hier noch nicht einmal die Regularität von A prüfen muss. Bricht der Algorithmus ab, so ist A numerisch singulär.
tigerbine Auf diesen Beitrag antworten »
4a. Berechnung
An einem Beispiel soll wieder die Idee verdeutlicht werden.







Darauf läßt sich nun ein Schritt der LR-Zerlegung (3a) durchführen.


mit



Im nächsten Schritt ist keine Vertauschung nötig. Dennoch schreibt man P=I hin. Warum werden wir später sehen.


mit



Im letzten Schritt ist nun wieder ein Vertauschen nötig.



Damit ist schon die gewünschte Dreiecksgestalt erreicht. Dennoch notiert man auch hier:


mit




Wie hängen nun die theoretisch existierende Darstellung PA=LR und die eben berechnete zusammen?
Dazu bedient man sich folgendes "Tricks", der am Beispiel illustriert werden soll:



Diese Matrizen haben sind wieder untere Dreiecksmatrizen mit der gleichen Struktur (Beweis unten). Die Permutationsmatrizen geben in ihrem Index hier nur an, welche Zeile getauscht werden soll. Den Tauschpartner läßt man hier nun einmal außen vor(siehe auch hier).


Somit ergibt sich:




Und damit die Zerlegung:




Dabei ist P wieder eine Permutationsmatrix und L wieder eine untere normierte Dreiecksmatrix. Im Beispiel also:










***********************************************************


Beweis:

Hier soll einmal die Struktur der konstruierten Matrizen betrachtet werden. Eine Permutationsmatrix ist zu sich selbst invers. Allgemein definiert ist nun:




Betrachten wir erstmal nur die Struktur von:




mit der Rechtsmultiplikation mit werden die Spalte (i+1) und eine Spalte vertauscht. Für diese gilt als Spaltenvektoren:






Nach dem ersten Tausch gilt also:




Nun werden die Zeilen (i+1) und j getauscht, somit ergibt sich:




Und somit ist die Struktur der Matrix erhalten geblieben, die Einträge sind jedoch vertauscht worden.
tigerbine Auf diesen Beitrag antworten »
4b. Existenz
Jede reguläre Matrix besitzt eine Zerlegung in der Gestalt PA = LR mit mit einer(n x n) Permutationsmatrix P, einer (n x n) normierten unteren Dreiecksmatrix L sowie einer (n x n) oberen Dreiecksmatrix R.


Beweis:

Der Beweis wird durch Induktion geführt.








tigerbine Auf diesen Beitrag antworten »
4c. Eindeutigkeit - Pivotwahl
In den Überlegungen von (4b) wurde bislang nur festgestellt, dass man bei einer regulären Matrix A immer einen "Tauschpartner" für den Fall einer Null auf der Diagonale findet.

Steht einem nicht nur ein "Tauschpartner" zur Verfügung, so stellt sich die Frage nach der "besten" Wahl. Den geringsten Aufwand wird wohl eine Suche nach dem ersten von 0 verschiedenen Eintrag in der betreffenden Spalte unterhalb der Diagonale machen. Ist diese "blinde" Wahl jedoch numerisch sinnvoll?


Durch die Implementierung erhält man eine Zerlegung und löst das LGS der Form:



mit einer unbekannten Matrix E, für die folgende Abschätzung gilt (Golub & VanLoan[1996, S. 106]):



m: Maschinengenauigkeit

n: Ordnung von A, also ist A eine (n x n) Matrix

|.|: Matrix der betragsmäßigen Einträgen


Somit ist es erstrebenswert die Einträge von möglichst klein zu halten.


2 LR-Zerlegungen:









Im ersten Fall treten also, im Gegensatz zum Zweiten, sehr große Werte auf. Man kann nun zeigen, dass allgemein für sehr kleine Diagonalelemente in der Matrix die Einträge in den Matrizen L und R sehr groß werden. Somit sollte man Kehrschluss die Diagonalelemente durch vertauschen möglichst groß wählen. Somit ergeben sich:



weitere Pivotsuchstrategien:

Spaltenpivotsuche
Unter den Elementen der j-ten Spalte wähle man ein dem Betrage nach größtes als neues Diagonalelement.
Suchaufwand:

Totale Pivotsuche
Unter den Elementen wähle man ein dem Betrag nach größtes als neues Diagonalelement aus. Hier müssen dann ggf. Zeilen und Spalten getauscht werden.
Suchaufwand:


Bei größeren Matrizen kann es sinnvoll sein, nur so lange zu suchen, bis ein Schwellenwert s überschritten wird.



Mit diesem Wissen kann man nun festhalten, dass auch im Falle der Existenz einer LR-Zerlegung ohne Pivotisierung es sinnvoll seien kann, selbige durchzuführen.


Hierzu ein Beispiel:




Exakte Lösung




Ohne Pivotisierung










Mit Spalten-Pivotisierung






tigerbine Auf diesen Beitrag antworten »
4d. Numerische Hinweise
  1. Ein singuläres LGS wird vom Gaußverfahren dadurch erkannt, dass an einer bestimmten Stelle alle Pivotsuchen erfolglos verlaufen. Durch Rundungsfehler kann es aber passieren, dass das System trotzdem als unlösbar erscheint. Eine hieraus berechnete Lösung ist jedoch wenig sinnvoll und man wird in der Praxis Systeme mit Pivotelementen kleiner als nicht behandelbar erklären.

  2. Aufgrund von Rechenungenaugkeiten wird in der Regel die berechnete Lösung nicht mit der exakten übereinstimmen. Vergleiche hierzu die Überlegungen aus dem [Workshop - lineare Gleichungssysteme 1]

  3. Ferner kann es trotzdem noch zu Problemen kommen, wenn die verschiedenen Gleichungen stark unterschiedlich gewichtet sind. Es empfiehlt sich eine Equilibrierung. (siehe Anhang)
tigerbine Auf diesen Beitrag antworten »
5. Weitere Möglichkeiten
Vielleicht erinnert man sich noch an die Lineare Algebra I, und wie man dort die Inverse einer Matrix berechnet hat. Dies und anderes was man neben der Lösung des LGS Ax=b noch aus der LR Zerlegung erhält, soll hier betrachtet werden.
tigerbine Auf diesen Beitrag antworten »
5a. Determinantenberechnung
Für quadratische Matrizen A und B gilt:




Für die Determinante einer Dreiecksmatrix gilt:




Determinante einer Permutationsmatrix:




Determinante einer Frobeniusmatrix:



Gestalt der LR-Zerlegung mit Pivotisierung:




Somit folgt:



Die Dreieckszerlegung bietet so eine einfache Möglichkeit die Determinante zu berechnen und ist im Vergleich zur Leibnizformel auch kostengünstig.
tigerbine Auf diesen Beitrag antworten »
5b. Rangebstimmung
Falls es immer ein von Null verschiedenes Pivotelement gibt, so ist und damit hat A den vollen Rang.

Ist im i-ten Eliminationsschritt für alle Elemente der i-ten Spalte , dann ist A singulär.




Um nun den Vollen Rang bestimmen zu können, nimmt man eine Totalpivotisierung vor. Gilt dann nach dem i-ten Eliminationsschritt



So ist Rang(A) = i. Gilt auch für nicht quadratische Matizen.
tigerbine Auf diesen Beitrag antworten »
5c. Inversesbestimmung 1


Gesucht ist





Dieses kann man nun mit Gaußalgorithmus für jeden Spaltenvektor von lösen

  1. Berechne die LR Zerlegung PA=LR
  2. Löse
    Löse
    i=1,...,n

tigerbine Auf diesen Beitrag antworten »
5d. Inversesbestimmung 2 - Gauß Jordan Algorithmus
Man kann ein LGS auch mit dem Gauß-Jordan Algorithmus lösen. Der erste Teil ist Gauß-Algorithmus gleich, danach wird aus der oberen Dreiecksmatrix R jedoch noch eine Diagonalmatrix gemacht. Dazu multipliziert man z.B. von Links mit Matrizen (ähnlich Frobenius). Dabei ändern sich nur die Einträge in der entsprechenden Spalte oberhalb der Diagonalen. Man kann also die Matrizen direkt aus der Dreiecksmatrix angeben. Ebenso bleiben die Rechenregeln (Inversion, Multiplikation der Inversen) wie bei den Frobenismatrizen erhalten.









Beispiel:



Schreibe



Vorwärtselimination 1 (Obere Dreiecksmatrix links erzeugen)



Pivotisierung 1 (größtes Spaltenelement)



Vorwärtselimination 2 (Obere Dreiecksmatrix links erzeugen)



Rückwärtselimination 1 (Diagonalmatrix erzeugen)



Rückwärtselimination 2 (Diagonalmatrix erzeugen)



Skalierung (auf Einheitsmatrix)




tigerbine Auf diesen Beitrag antworten »
5e. Austauschalgorithmus
Auch hier ist die Grundlage ein Algorithmus zur Lösung des LGS Ax=y. Wieder gibt es Varianten mit und ohne Pivotisierung. Die zweite Variante soll anhand eines Beispiels erläutert werden. Mehr kann man dem angehängten PDF-File entnehmen. Die Laufzeit liegt hier bei


Wir betrachten also das LGS:








Die erste Spalte enthält nur die 1 als Koeffizient, also ist keine Zeilenvertauschung nötig. Man stellt nun die erste Zeile nach um:




Die erste Zeile wird nun damit getauscht, in den anderen wird ersetzt.








Nun schaut man in die zweite Spalte, dort ist ein Tausch nötig.








Nun stellt man die Zweite Zeile nach




Nun wieder das LGS aufschreiben








Nun noch die Letze Zeile umstellen:




Und im LGS Austauschen und einsetzen:








Wollte man nun nur die Lösung des LGS, wäre man an dieser Stellt bereits fertig. Um die Inverse von A zu bestimmen, müssen noch die Spalten 2 und 3 vertauscht werden. Dazu multipliziert man von rechts mit einer Permutationsmatrix. Alles in Matrixschreibweise ergibt dann:

tigerbine Auf diesen Beitrag antworten »
6. Direkte LR-Zerlegung
In Abschnitt 3,4 haben wir festgestellt, dass man eine reguläre Matrix A so permutieren kann, dass alle Hauptabschnittsmatrizen A[k] regulär sind. Im folgenden sei A schon in dieser Weise sortiert, so dass es eine eindeutige Zerlegung A = LR gibt.


Wie kann man eine Dreieckszerlegung allgemein erzeugt werden?






Damit folgt für die Matrix A:




Das ist ein Gleichungssystem mit Gleichungen (Einträge von a) und n²+n Unbekannten, nämlich den von Null verschiedenen Einträgen von L und R (hier wird L noch nicht als normiert vorausgesetzt!).
tigerbine Auf diesen Beitrag antworten »
6a. Verfahren von Doolittle und Crout
Um nun eine eindeutige Lösung zu erhalten, könnte man n Einträge, z.B. die Diagonaleinträge von L oder R, vorgeben. Insbesondere sind diese aufgrund der Regularität von A von Null verschieden. Sind nun die Diagonalelemente von L vorgegeben, d.h. es gilt:



ergibt sich das


Verfahren von Doolitle







Bildlich werden die Einträge dann wie folgt berechnet:






Gibt man hingegen die Diagonalelemente von R vor, so berechnet man andersherum mit dem

Verfahren von Crout








Bildlich werden die Einträge dann wie folgt berechnet:






Anmerkung:
Im Falle K=1 ist die Summe durch 0 zu ersetzen.


Wie sollte man nun die Diagonalelemente vorgeben? Am einfachsten ist die Wahl des Wertes 1, da so die Division entfallen kann. Aus vorherigen Überlegungen ist aber auch hier i.A. eine Pivotisierung vorzunehmen.
tigerbine Auf diesen Beitrag antworten »
7a. Tridiagonalmatrizen
Besonders einfach gestalten sich die ebenen genannten Algorithmen im Fall einer Tridiagonalmatrix. Im Falle von Crout ergibt sich dann mit :






Aufwand:




Wann ist der Algorithmus wohl definiert?

Falls die Matrix A strikt diagonaldominant ist, sind alle Hauptabschnittsmatrizen regulär, insbesondere gilt .


Beweis

siehe hier, [Workshop - Spline-Interpolation]
tigerbine Auf diesen Beitrag antworten »
7b. Allgemein zum Speichern
Mit steigendem n kann es zu Speicherproblemen von Matrizen kommen, haben diese doch n² Einträge. So ist es zu überlegen, ob es bei speziellen Matrizen, möglich ist mit weniger Speicherplatz aus zukommen. Dazu betrachtet man Bandmatrizen


Die Speicherplatz Ersparnis beruht darauf, dass man nur das Band speichert. Das hat aber auch zur Folge, dass man keine Zeilenvertauschungen mehr durchführen kann.


Ist nun bei Bandmatrix A das Gauß'sche Eliminationsverfahren ohne Pivotiserung durchführbar ist, dann sind auch alle reduzierten Matrizen Bandmatrizen desselben Typs und die Faktoren der LR-Zerlegung sind Bandmatrizen vom Typ (p,0), (0,q).

Eine dünne Besetzung der Bandmatrix bringt keine Speicherplatzersparnis.
tigerbine Auf diesen Beitrag antworten »
8a. LDL^T Zerlegungen
Sei nun die reguläre Matrix A symmetrisch, d.h. es gilt . Zunächst macht man den verallgemeinerten Ansatz.



Wobei D eine Diagonalmatrix und L eine normierte untere Dreiecksmatrix ist. Die rechte Seite ergibt offensichtlich eine symmetrische Matrix. Bleibt noch offen, ob es eine solche Zerlegung für jede reguläre symmetrische Matrix A gibt. Zunächst einmal erhält man:







Daraus ergibt sich dann für K=1,2,...,n:







Existiert diese Zerlegung für jede reguläre symmetrische Matrix?




Hier ist keine Zerlegung möglich, denn



und damit
tigerbine Auf diesen Beitrag antworten »
8b. Cholesky-Zerlegung
Ist nun die Matrix A auch noch positiv definit, so sind alle Diagonalelemente von D positiv (betrachte die pos. Definitheit für die Einheitsvektoren). In diesem Fall existiert:




Und es ist:



eine Dreieckszerlegung von A, die Cholesky-Zerlegung. Der Algorithmus folgt aus voherigem:






Weiter ist aufgrund der SPD-Gestalt eine Zerlegung immer ohne Pivotisierung möglich (alle Hauptabschnittsmatrizen sind regulär, ferner sind die Diagonalelemente von A positiv)

Beweis

  • Sei der i-te Einheitsvektor des . Aus der positiven Definitheit von A folgt:




  • Die Symmetrie der der A[k] folgt direkt aus der von A.


  • Für sei beliebig gegeben. Mit . Es folgt dann



    somit dass A[k] positiv definit ist.




Aufwand




Leider weichen hier die Angaben über die Laufzeiten von Buch zu Buch ab. Festzuhalten bleibt, das für SPD Matrizen die Cholesky Zerlegung halb so aufwendig ist wie die Gaußelimination und man ohne Pivotisierung auskommt.


Lehrer

Der Cholesky-Algorithmus ist die effizienteste allgemeine Testmethode auf positive Definitheit. Man kann auf das Rechnen mit den Quadratwurzeln verzichten, indem man unter Berücksichtigung der Symmetrie den Gaußalgorithmus wie gewohnt durchführt und nur die Pivots in einer Diagonalmatrix (als Vektor) speichert. Dies gibt dann die Eingang erwähnte Zerlegung.
tigerbine Auf diesen Beitrag antworten »
9. QR-Zerlegung
In diesem Workshop soll sich mir der QR-Zerlegung auseinander gesetzt werden. D.h. die Matrix A soll Produkt einer orthogonalen Matrix Q und einer oberen Dreiecksmatrix R dargestellt werden. Als Anwendung soll dann nur das Lösen Linearer Gleichungssysteme im Vergleich zur LR-Zerlegung betrachtet werden. Daher sei A im folgenden auch als regulär angenommen.

Die Bedeutung bei der Lösung linearer Ausgleichsprobleme und Eigenwertprobleme wird in eigenen Workshops behandelt.
tigerbine Auf diesen Beitrag antworten »
9a. Eindeutigkeit der QR-Zerlegung (bis auf Diagonalmatrix)
Gegeben sind n² Einträge der Matrix A und zu bestimmen sind [n² + n(n+1)/2] Einträge der Matrizen Q und R. So ohne weiteres ist also (im Falle der Existenz) nicht mit einer Eindeutigen Zerlegung A=QR zu rechnen. Die Spalten der Matrix Q müssen orthonomiert sein.


Sollte nun eine QR-Zerlegung existieren, so ist sie im Wesentlichen eindeutig. Betrachtet man also 2 QR-Zerlegungen, so existiert eine Diagonalmatrix D (mit Werten +/- 1), so dass gilt:





Beweis:

Es nun nach Voraussetzung . Da es sich bei den Qs um orthogonale Matrizen handelt, folgt sofort:




Damit erhält man dann aus der ersten Gleichheit:



und andersherum folgt:



Es sind nun die Rs regulär, sonst wäre Rang(A) <n, und somit existieren die Inversen:






Nun definiert man und weist nach, dass es sich um eine orthogonale Diagonalmatrix handelt. Mit dem Wissen über Dreiecksmatrizen folgt, dass auch die Inversen obere Dreiecksmatrizen sind. Es ist also auch D eine obere Dreiecksmatrix und ihre Transponierte somit eine untere Dreiecksmatrix. Es gilt weiter:



Somit muss D eine Diagonalmatrix sein. Nun folgt weiter



Womit nun auch die Orthogonalität von D gezeigt wurde, d.h. die Diagonalwerte sind +/- 1. Mit



folgt dann die Behauptung.
tigerbine Auf diesen Beitrag antworten »
9b. Lösen eines reg. LGS Ax=b
Sollte einer Zerlegung existieren, so ist Q einfach durch Transponieren invertierbar und man kann das LGS am Ende durch Rückwärtssubstitution lösen.

tigerbine Auf diesen Beitrag antworten »
9c. Existenz von QR-Zerlegungen
Mit der Angabe eines durchführbaren Algorithmus, der zu einer Matrix A eine Zerlegung QR=A liefert dürfte die Frage nach der Existenz einer solchen Zerlegung beantwortet sein.
tigerbine Auf diesen Beitrag antworten »
9d. Gram-Schmidt-Orthogonalisierung
Gesucht ist nun die QR-Zerlegung. Zunächst notiert man:



Lehrer Die Potenzen Kennzeichen hier die Spaltenvektoren


ausgeschrieben bedeutet das:












allgemein:




Damit erhält man nun eine Berechnungsvorschrift für die orthonormalen Vektoren "q" und die zugehörigen Koeffizienten "r". Für j=1 ergibt sich:



Da Q orthogonal ist, gilt





Um nun eine eindeutige Lösung zu erhalten, sollen die Diagonalelemente von R positiv sein. Weiter erhält man durch Umstellen zunächst:






Nun die Orthogonalitätsbedingung:













Allgemein ergibt sich dann:








Mit dieser Vorschrift (Gram-Schmidt-Verfahren) ist die Existenz einer red. QR-Zerlegung konstruktiv (fast) bewiesen worden. Es ist noch zu zeigen, dass das Verfahren wohldefiniert ist. Dies ist dann der Fall, wenn für die Nenner gilt .

Wäre nun für ein kleinstes , so folgt aus (*) Dies steht aber im Widerspruch zu Rang(A) = n.

Numerisch ist das Verfahren nicht stabil. Ein modifizierter Algorithmus befindet sich im Anhang.
tigerbine Auf diesen Beitrag antworten »
9e. Householder-Spiegelungen
Bei diesem Ansatz geht man ähnlich der Berechnung der LR-Zerlegung vor. Durch Linksmultiplikation mit Orthogonalen Matrizen soll A auf die Form einer Dreiecksmatrix gebracht werden.




Dabei annulliert die Eintrage der j-ten Spalte unterhalb der Diagonalen.







Householder-Spiegelung (Definition)




Konstruktion von u

x sei nun der Teil des Spaltenvektors von "A", den es zu annullieren gilt, zzgl. des Diagonalelements.





tigerbine Auf diesen Beitrag antworten »
9f. Givens-Rotatioinen
Bei diesem Ansatz geht man ähnlich der Berechnung der LR-Zerlegung vor. Durch Linksmultiplikation mit Orthogonalen Matrizen soll A auf die Form einer Dreiecksmatrix gebracht werden.




Dabei annulliert den Eintrag an der Stelle (i,j).





Givens-Rotation (Definition)




Konstruktion von c und s



Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »