[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren |
09.07.2007, 19:38 | tigerbine | Auf diesen Beitrag antworten » |
[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren Das CG-Verfahren
|
||
09.07.2007, 19:39 | tigerbine | Auf diesen Beitrag antworten » |
10. Das CG-Verfahren Nun sollen die Nachteile des Gradienten-Verfahrens beseitigt werden, indem man die Abstiegsrichtungen A-konjugiert wählt. Der Algorithmus lautet Algorithmus: Es wird sich am Ende Folgendes zeigen: Der entscheidende Gewinn ist hier also, dass man durch diese Wahl der Abstiegsrichtung nicht nur entlang einer Richtung, sondern gleich über den Krylow-Räum minimiert. Aus den Eigenschaften der Krylow-Räume folgt dann die Eigenschaft, dass der Algorithmus theoretisch in Schritten terminiert. |
||
09.07.2007, 21:25 | tigerbine | Auf diesen Beitrag antworten » |
10a. Der formale Algorithmus |
||
09.07.2007, 22:52 | tigerbine | Auf diesen Beitrag antworten » |
10b. Satz über konjugierte Richtungen und Konvergenz Seien n paarweise A-konjugierte Richtungen gegeben (A sei SPD-Matrix). Wählt man diese Richtungen nacheinander im Abstiegsverfahren (also als ) mit beliebigem , so
Beweis:
|
||
09.07.2007, 23:03 | tigerbine | Auf diesen Beitrag antworten » |
10c. Folgerungen aus dem Algorithmus D.h. die Abstiegsrichtungen sind A-konjugiert, bis der Algorithmus (10a) abbricht. Beweis: _______________________________________________________________________ _______________________________________________________________________ _______________________________________________________________________ Beweis _______________________________________________________________________ folgt aus (10b), d.h. das Verfahren konvergiert spätestens für |
||
09.07.2007, 23:07 | tigerbine | Auf diesen Beitrag antworten » |
10d. Der zu implementierende Algorithmus Der eingangs gepostete Algorithmus ergibt sich mit (10c) wie folgt Bei n Durchläufen benötigt man so Operationen. Dass man es ggf. mit Weniger als n Durchläufen schafft, soll nun gezeigt werden. Identität des Residuums Beweis: |
||
Anzeige | ||
|
||
10.07.2007, 03:16 | tigerbine | Auf diesen Beitrag antworten » |
10e. Eigenschaften einer SPD-Matrix --------------------------------------------------------------- |
||
10.07.2007, 03:38 | tigerbine | Auf diesen Beitrag antworten » |
10e1. Folgerungen 1 ------------------------------------------------------- Es folgt daraus: |
||
10.07.2007, 03:39 | tigerbine | Auf diesen Beitrag antworten » |
10e2. Folgerungen 2 -------------------------------------------------------------------------------------------------- |
||
10.07.2007, 03:40 | tigerbine | Auf diesen Beitrag antworten » |
10f. Wann bricht der Algorithmus ab? Der Algorithmus bricht ab, wenn für ein minimales m für das Residuum gilt: Die entscheidende Äquivalenzkette Residuen-Raum Raum der Abstiegsrichtungen Krylov-Raum Der Raum heißt Krylov-Raum. Kennen wir seine maximale Dimension, so wissen wir nach wie vielen Schritten das Verfahren spätestens abbricht. Es gilt des weitern: Es gilt offensichtlicht: |
||
10.07.2007, 03:40 | tigerbine | Auf diesen Beitrag antworten » |
10g. Bezug zum Polynom p Für die Iterierten gilt: Somit lassen sie sich als Linearkombination wie folgt darstellen: Für die Iterierten ergibt sich daher: Allgemein bedeutet das: Für das Residuum folgt dann: |
||
10.07.2007, 03:40 | tigerbine | Auf diesen Beitrag antworten » |
10h. Schließen der Kette Als Folgerung des vorherigen Post ergibt sich Nun muss nur noch gezeigt werden, dass gilt: Und es wurde somit folgendes gezeigt: |
||
12.07.2007, 05:16 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (1) Behauptung (1): Beweis: offensichtlich Angenommen es gäbe einen Eigenwert mit . Dann wäre , was im Widerspruch zu steht. |
||
12.07.2007, 05:29 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (3) Behauptung (3): Beweis: Sieha (8a) |
||
12.07.2007, 05:31 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (4) Behauptung (4): Beweis: Siehe (8b) |
||
12.07.2007, 05:43 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (5) Behauptung (5): Beweis: Siehe (8c) |
||
12.07.2007, 05:43 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (6) Behauptung (6): Beweis: Dabei darf angenommen werden, da sonst der Algorithmus schon abgebrochen worden wäre. |
||
12.07.2007, 05:44 | tigerbine | Auf diesen Beitrag antworten » |
Beweise (7a), (7b), (7) Behauptung (7a): Beweis: Die Residuen sind paarweise orthogonal und die Abstiegsrichtungen paarweise A-konjugiert. Daher sind auch jeweils paarweise linear unabängig. Vergleiche (10c) Behauptung (7b): Beweis: Die letzte Argumentation teilt sich in 2 Fälle. Entweder die Räume haben sich nicht vergrößert, dann sind sie nach IV identisch. Wenn sie sich vergrößern, dann folgt aus Dimensionsgründen, dass sie übereinstimmen. Das wirft die Frage auf, wann sich die Dimension der Räume nicht mehr erhöht. Behauptung (7): Beweis: Da m bzgl. der Eigenschaft minimal ist (siehe 10f) und die Residuuen bis dahin paarweise orthogonal sind, folgt die Behauptung. Die Residuen sind paarweise orthogonal. Der einzige Vektor, bei dem sich dann die Dimension nicht mehr erhöht ist der Nullvektor. Somit muss gelten , Damit folgt aus (6) die Behauptung. |
||
12.07.2007, 05:45 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (8) Behauptung (8): Beweis: |
||
12.07.2007, 05:45 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (9) Behauptung (9): Beweis: |
||
12.07.2007, 05:46 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (10) Behauptung (10): Beweis: Laut Algorithmus gilt: Dies kann man auch zu zurückführen (Induktionsbeweis): Stellt man dies nun um, so erhalt man: Mit der Definition von folgt: Mit (7b), (9) folgt dann: |
||
12.07.2007, 05:47 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (11) Behauptung (11): Beweis: Wegen (10) gilt: Somit ist der Term als Linearkombination wie folgt darstellbar: Umstellen liefert: Somit gibt es ein Polynom mit: Damit folgt die Behauptung |
||
12.07.2007, 05:48 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (12) Behauptung (12): Beweis: es ist wieder eine Matrix. Laut dem [Workshop-Lineare Gleichungssysteme 1] gilt: Es gilt hier i.A. , sonst hätte man mit x_0 schon die gesuchte Lösung gefunden. Gilt nun also: So folgt wegen der Normeigenschaft: die Behauptung. |
||
13.07.2007, 01:21 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (2) Erfolgt über mehrere Post. ******************************************** Sei eine SPD-Matrix. Dann besitzt diese nur reelle positive Eigenwerte, d.h. das charakteristische Polynom zerfällt über in Linearfaktoren. Dabei bezeichnen nun die Anzahl der verschiedenen Eigenwerte von A. Aus der Regularität von A folgt, dass 0 kein Eigenwert ist. Es gilt: Spektrum von A A-Vektor-Norm induzierte Matrixnorm Wir konstruieren nun ein Polynom aus folgenden (m+1)-Interpolalationsbedingungen. Aus dem [Workshop - Polynominterpolation] wissen wir, dass p eindeutig exisitiert. |
||
13.07.2007, 01:23 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (2) - Was ist p(A)? Was passiert, wenn man A in p einsetzt? Das ist wiederum eine Matrix aus dem , die mit B bezeichnet werden soll. Welche Eigenschaften hat B?
A, B sind simultan diagonalisierbar, d.h. es gibt eine orthogonale Matrix mit |
||
13.07.2007, 01:24 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (2) - Was ist ||B||_A ? Die induzierte Matrixnorm wurde bereits definiert. Dabei beachte man, dass aus Kompaktheitsgründen durch ersetzt werden kann. Da die Spalten von Q eine ONB bilden, kann man jeden Vektor x als Linearkombination dieser ausdrücken: Mit dem Wissen folgt: Daraus ergibt sich die folgende Darstellung: Da A eine SPD-Matrix ist, gilt . Damit ergibt sich: Also letztendlich gilt: |
||
13.07.2007, 01:25 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (2) - Was ist das Spektrum von B? Behauptung: Beweis -Teil 1: Sei x ein Eigenvektor von A zum Eigenwert . Dann gilt wegen : Beweis -Teil 2: Da das char. Polynom von A über IR in Linearfaktoren zerfällt, ist A trigonalisierbar (Schur-Zerlegung R): Setzt man nun R in das Polynom p ein, so folgt wegen Somit sind und ähnliche Matrizen und besitzen das gleiche Spektrum. Nun sind die Diagonaleinträge von R das Spektrum von A. Damit ergibt sich für die Diagonale von (nachrechnen): Es ist dann also eine obere Dreiecksmatrix mit: |
||
13.07.2007, 01:26 | tigerbine | Auf diesen Beitrag antworten » |
Beweis (2) - Was ist ||p(A)||_A? Mit den letzten beiden Antworten folgt nun also: Wenn wir uns nun an die Konstruktion von p erinnern, dann folgt: |
||
16.08.2007, 14:00 | tigerbine | Auf diesen Beitrag antworten » |
Ausblick Bislang haben wir immer den Fall Ax=b für reguläres A betrachtet. Was passiert nun, wenn A singulär ist? Was wenn A nicht quadratisch ist? Mehr dazu im Wokshop lineare Ausgleichprobleme |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |
|