[WS] Lineare Gleichungssysteme 2 - direkte Verfahren |
19.07.2007, 03:38 | tigerbine | Auf diesen Beitrag antworten » |
[WS] Lineare Gleichungssysteme 2 - direkte Verfahren
|
||
19.07.2007, 03:40 | tigerbine | Auf diesen Beitrag antworten » |
1. Lösbarkeit von Linearen Gleichungssystemen Betrachtet werden lineare Gleichungssysteme über reellen endlich-dimensionalen Vektorräumen. ![]() In den weiteren Betrachtungen wird meist A als regulär angesehen. Ziel ist es die eindeutig existierende Lösung von Ax=b zu bestimmen. |
||
19.07.2007, 04:33 | tigerbine | Auf diesen Beitrag antworten » |
1a. Satz von Hurwitz (Sylvester Kriterium) ******************************** Beweis: Vgl. z.B. Fischer - Lineare Algebra |
||
19.07.2007, 04:37 | 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 |
||
19.07.2007, 04:39 | 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
|
||
19.07.2007, 13:59 | tigerbine | Auf diesen Beitrag antworten » |
1d. Dreiecksmatrizen Produkt von Dreiecksmatrizen
Inverse von Dreiecksmatrizen
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. |
||
Anzeige | ||
|
||
19.07.2007, 14:29 | 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: |
||
19.07.2007, 14:53 | 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 . |
||
19.07.2007, 14:55 | 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 . |
||
19.07.2007, 17:12 | 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 . |
||
19.07.2007, 17:45 | 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. |
||
19.07.2007, 17:46 | 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): ![]() Dieses einfache Übertragen der Einträge funktioniert nicht bei , denn: |
||
19.07.2007, 17:58 | 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: |
||
19.07.2007, 18:11 | 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. ![]() Im Falle der strikten Diagonaldominanz folgt hiermit sogar direkt, dass A regulär ist. |
||
19.07.2007, 20:27 | 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. |
||
19.07.2007, 21:14 | 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. |
||
19.07.2007, 21:27 | 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. |
||
19.07.2007, 21:29 | 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. |
||
19.07.2007, 21:31 | 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. |
||
19.07.2007, 21:31 | 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 |
||
19.07.2007, 22:03 | tigerbine | Auf diesen Beitrag antworten » |
4d. Numerische Hinweise
|
||
20.07.2007, 00:28 | 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. |
||
20.07.2007, 01:02 | 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. |
||
20.07.2007, 01:32 | 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. |
||
20.07.2007, 18:12 | tigerbine | Auf diesen Beitrag antworten » |
5c. Inversesbestimmung 1 Gesucht ist Dieses kann man nun mit Gaußalgorithmus für jeden Spaltenvektor von lösen
|
||
20.07.2007, 20:36 | 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) |
||
21.07.2007, 00:00 | 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: |
||
21.07.2007, 00:25 | 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 n² 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!). |
||
21.07.2007, 00:34 | 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. |
||
21.07.2007, 00:42 | 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] |
||
21.07.2007, 01:48 | 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. |
||
21.07.2007, 01:53 | 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 |
||
21.07.2007, 02:34 | 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
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. ![]() 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. |
||
01.01.2009, 17:24 | 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. |
||
01.01.2009, 18:08 | 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. |
||
01.01.2009, 20:40 | 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. |
||
01.01.2009, 20:59 | 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. |
||
01.01.2009, 21:18 | tigerbine | Auf diesen Beitrag antworten » |
9d. Gram-Schmidt-Orthogonalisierung Gesucht ist nun die QR-Zerlegung. Zunächst notiert man: ![]() 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. |
||
02.01.2009, 00:41 | 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. |
||
02.01.2009, 00:43 | 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 |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |
|