[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren
Gliederung


Das CG-Verfahren

  1. Der formale Algorithmus
  2. Satz über konjugierte Richtungen und Konvergenz
  3. Folgerung aus dem Algorithmus
  4. Der zu implementierende Algorithmus

  5. Eigenschaften einer SPD-Matrix
  6. Folgerungen 1
  7. Folgerungen 2
  8. Wann bricht der Algorithmus ab?
  9. Bezug zum Polynom p
  10. Schließen der Kette

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:






Lehrer 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.
 
 
tigerbine Auf diesen Beitrag antworten »
10a. Der formale Algorithmus
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

  1. minimiert die Funktion f im Teilraum








Beweis:

  1. Seien die Richtungen nun A-konjugiert, das bedeutet es gilt .


    die Minimalität von f im Raum ergibt sich direkt aus den Rechnungen im vorherigen Workshop. Egal wie man die Abstiegsrichtung wählte, so ergab sich die Rekursion:




  2. Man kann auch mehrere Schritte zurück gehen. So erhält man:




    Es ist für beliebige Richtung mit den Definitionen




  3. Weiter folgt mit obiger Darstellung für :




    Multipliziert man diese Gleichung mit , so folgt:




    Für k=n folgt daher:




    Da die Abstiegsrichtung paarweise A-konjugiert sind, sind sie auch linear unabhängig. Damit ist die maximale Anzahl lin. unabhängiger Vektoren im erreicht. Der einzige Vektor der nun noch senkrecht auf allen stehen kann ist der Nullvektor. Somit muss gelten:



    D.h. der Algorithmus konvergiert nach spätestens n Durchläufen.

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
tigerbine Auf diesen Beitrag antworten »
10d. Der zu implementierende Algorithmus
Der eingangs gepostete Algorithmus ergibt sich mit (10c) wie folgt


















Lehrer 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:





tigerbine Auf diesen Beitrag antworten »
10e. Eigenschaften einer SPD-Matrix

---------------------------------------------------------------












tigerbine Auf diesen Beitrag antworten »
10e1. Folgerungen 1

-------------------------------------------------------




Es folgt daraus:

tigerbine Auf diesen Beitrag antworten »
10e2. Folgerungen 2

--------------------------------------------------------------------------------------------------


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





Lehrer 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:

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:

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:





Lehrer Und es wurde somit folgendes gezeigt:

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.
tigerbine Auf diesen Beitrag antworten »
Beweis (3)
Behauptung (3):




Beweis:

Sieha (8a)
tigerbine Auf diesen Beitrag antworten »
Beweis (4)
Behauptung (4):





Beweis:

Siehe (8b)
tigerbine Auf diesen Beitrag antworten »
Beweis (5)
Behauptung (5):





Beweis:

Siehe (8c)
tigerbine Auf diesen Beitrag antworten »
Beweis (6)
Behauptung (6):




Beweis:

Dabei darf angenommen werden, da sonst der Algorithmus schon abgebrochen worden wäre.







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.
tigerbine Auf diesen Beitrag antworten »
Beweis (8)
Behauptung (8):



Beweis:

tigerbine Auf diesen Beitrag antworten »
Beweis (9)
Behauptung (9):



Beweis:








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

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?




  • , d.h. B ist normal.

  • , d.h. A und B sind vertauschbar

A, B sind simultan diagonalisierbar, d.h. es gibt eine orthogonale Matrix mit



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:

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:

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:

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
Neue Frage »
Antworten »



Verwandte Themen

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