[WS] Lineare Gleichungssysteme 4 - Das Gradientenverfahren

Neue Frage »

tigerbine Auf diesen Beitrag antworten »
[WS] Lineare Gleichungssysteme 4 - Das Gradientenverfahren
Gliederung

Ausgangssituation: SPD-Matrix

Lösen äquivalenter Probleme
  1. Beweis (1)
  2. Beweis (2)
  3. Beweis (3)

  4. x* ist einzige Extremstelle von f
  5. Bestimmung des Minimums von f - Abstiegsrichtung
  6. Güte der Annäherung - Fehler und Residuum

Das Gradienten-Verfahren
  1. Algorithmus
  2. Die Residuen sind orthogonal
  3. Konvergenz-Probleme
tigerbine Auf diesen Beitrag antworten »
Ausgangssituation
Nun soll der spezielle Fall, dass A nicht nur regulär ist, sondern dass es sich um eine symmetrische positiv definite Matrix handelt, untersucht werden. Diese Eigenschaft wird im folgenden mit SPD-Matrix abgekürzt, ohne damit politisch zu sein. Augenzwinkern




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















tigerbine Auf diesen Beitrag antworten »
8. Lösen äquivalenter Probleme

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




Dabei nennt man die Norm auch Energienorm.
tigerbine Auf diesen Beitrag antworten »
8a. Beweis (1)
Behauptung (1):





Beweis:

Zunächst konstruiert man eine Hilfsfunktion g wie folgt:



Da A regulär ist, existiert die eindeutige Lösung x* des LGS Ax = b. Es gilt dann (Ax*- b) = 0 und somit auch g(x*)=0 . Da eine SPD-Matrix ist, gilt ansonsten g(x) > 0. Da sich g und f nur durch die Konstante unterscheiden, gilt:


tigerbine Auf diesen Beitrag antworten »
8b. Beweis (2)
Behauptung (2):





Beweis:

Aus der Definition von e folgt und es gilt . Somit gilt:

tigerbine Auf diesen Beitrag antworten »
8c. Beweis (3)
Behauptung (3):





Beweis:

Da sich und nur um die Konstante unterscheiden folgt die Äquivalenz sofort.
 
 
tigerbine Auf diesen Beitrag antworten »
8d. x* ist einzige Extremstelle von f
Mit Beweis (1) folgt die Existenz des Minimums x* und auch dessen Eindeutigkeit. Zur Bestimmung von Extremstellen ist jedoch der erste Schritt, die Bestimmung aller Punkte, die die notwendige Bedingung " f'(x)=0 ", erfüllen.


Lehrer
Damit ein darauf basierender Algorithmus auch wirklich x* liefert, muss sichergestellt werden, dass f keine weiteren Extremstellen besitzt.

Notwendige Voraussetzung ist dann also , dass für die partiellen Ableitungen gilt:



Behauptung (1a):

Da A eine SPD-Matrix ist, gilt für den Gradienten an der Stelle x:




Beweis:

Es gilt
.


Bestimmt man die partiellen Ableitungen, so erhält man:


Also die i-te Zeile von Ax - b.



Damit gilt für den Gradienten an einer Extremstelle die Forderung:



Somit x* ist der einzige Kandidat für eine Extremstelle von f und wegen Beweis (1) auch das Minimum.
tigerbine Auf diesen Beitrag antworten »
8e. Bestimmung des Minimums von f - Abstiegsrichtung y_k
Idee ist es nun ein gegen x* konvergente Folge zu konstruieren. Ohne deren Gestalt explizit zu kennen, kann man schon einmal den Richtungsvektor wie folgt definieren:



d.h. der Vektor gibt die Abstiegsrichtung des Schrittes an.



Seien nun fest gewählt. Wie weit sollte man sich dann vom "Punkt " in der "Richtung " bewegen, um die best mögliche Annäherung an x* in dieser Richtung zu erhalten? Dazu betrachtet man die Funktion definiert durch:




Es gilt dann:




Da nun A eine SPD Matrix ist, gilt:



Somit ist der Graph von h eine nach oben geöffnete Parabel und h besitzt genau ein Minimum (Scheitelpunkt). Bestimmt wird dieses wie üblich durch Nullsetzen der Ableitung (Notwendige Bedingung ist hier hinreichend). Da es sich bei <,> um reelle Skalarprodukte handelt, gilt <v,w> = <w,v>.




Daher gilt für das Minimum:




Somit ist die Schrittweite, die man in Richtung geht. Damit ergibt sich für den neuen Punkt :



Es folgt damit auch die Darstellung



d.h. es gilt

tigerbine Auf diesen Beitrag antworten »
8f. Güte der Annäherung
Nun haben wir eine Rekursion aufgestellt, brauchen aber noch ein Mittel um zu Prüfen, wie nahe wir schon an der Lösung x* sind. Dazu definiert man sich den

Fehler



Dieser ist auch schon in aufgetreten, doch da man x* nicht kennt, bislang noch ohne praktischen nutzen.


Somit muss die Güte der Näherung anhand des Funktionswerts des LGS Ax=b an der Stelle beurteilt werden. Dazu definiert man das

Residuum

siehe hier


Nun sollen auf diesen Ideen basierende Verfahren betrachten werden.
tigerbine Auf diesen Beitrag antworten »
9. Das Gradienten-Verfahren
Da wir das Minimum x* der Funktion f suchen, könnte es "sinnvoll" sein in Richtung des steilsten Abstiegs zu gehen. Diese wird durch den negativen Gradienten angegeben. Man wählt also:




Bestimmt man nun die partiellen Ableitungen, so erhält man wie schon erwähnt




Für die Rekursionsformel folgt dann:

tigerbine Auf diesen Beitrag antworten »
9a. Algorithmus


tigerbine Auf diesen Beitrag antworten »
9b. Die Residuen sind orthogonal
Behauptung

Die Abstiegsrichtungen sind orthogonal.


Beweis:

[/quote]
tigerbine Auf diesen Beitrag antworten »
9c. Konvergenz-Probleme
Die Kondition einer Matrix ist definiert als





bzgl. einer beliebigen induzierten Matrixnorm. Wählt man z.B. die Spektralnorm:





Da A eine SPD-Matrix ist, folgt:





Da die Eigenwerte von die Kehrwerte der Eigenwerte von sind, gilt:





Damit folgt für die Kondition von A:





Mittels der Ungleichung von Kantorowitsch kann man dann den Abstand zwischen und wie folgt abschätzen:





Lehrer D.h. für große Konditionszahlen liegt die Konvergenzrate sehr nahe bei 1.
Anschaulich liegt dass daran, dass die Abstiegsrichtungen bzgl. fast parallel sein können. In wurde festgestellt, dass aber gerade diesbezüglich der Abstand zur Lösung x* minimiert wird.
tigerbine Auf diesen Beitrag antworten »
Ausblick
Mit einem Blick aus der Optimierung auf das Verfahren, sprich mit dem Ziel eine Funktion zu Minimieren ist die Rosenbrock-Funktion ein klassisches Beispiel, für das das Verfahren nur sehr langsam konvergiert.

Wer bzgl. dem Lösen eines LGS mit spd-Matrix selbst mal was rechnen möchte, der nehme zum Beispiel Ax=0 mit und



Die Höhenlinien der entstehenden Funktion f sind Elipsen und man kann schön den Zick-Zack Kurs verfolgen. Hier mal die Iterationsschritte für eine Abbruchgenauigkeit von .

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
k | xk                                 | rk
-------------------------------------------------------------------------
0: 	[4.500000e+000, 3.000000e+000], 	[-4.500000e+000, -6.000000e+000]  
1: 	[1.756098e+000, -6.585366e-001], 	[-1.756098e+000, 1.317073e+000]  
2: 	[4.648494e-001, 3.098996e-001], 	[-4.648494e-001, -6.197991e-001]  
3: 	[1.814046e-001, -6.802673e-002], 	[-1.814046e-001, 1.360535e-001]  
4: 	[4.801887e-002, 3.201258e-002], 	[-4.801887e-002, -6.402516e-002]  
5: 	[1.873907e-002, -7.027152e-003], 	[-1.873907e-002, 1.405430e-002]  
6: 	[4.960343e-003, 3.306895e-003], 	[-4.960343e-003, -6.613790e-003]  
7: 	[1.935743e-003, -7.259038e-004], 	[-1.935743e-003, 1.451808e-003]  
8: 	[5.124027e-004, 3.416018e-004], 	[-5.124027e-004, -6.832036e-004]  
9: 	[1.999620e-004, -7.498576e-005], 	[-1.999620e-004, 1.499715e-004]  
10: 	[5.293112e-005, 3.528742e-005], 	[-5.293112e-005, -7.057483e-005]  
11: 	[2.065605e-005, -7.746018e-006], 	[-2.065605e-005, 1.549204e-005]  
12: 	[5.467777e-006, 3.645185e-006], 	[-5.467777e-006, -7.290370e-006]  
13: 	[2.133767e-006, -8.001625e-007], 	[-2.133767e-006, 1.600325e-006]  
14: 	[5.648206e-007, 3.765471e-007], 	[-5.648206e-007, -7.530942e-007]  
15: 	[2.204178e-007, -8.265668e-008], 	[-2.204178e-007, 1.653134e-007]  
16: 	[5.834589e-008, 3.889726e-008], 	[-5.834589e-008, -7.779452e-008]  
17: 	[2.276913e-008, -8.538423e-009], 	[-2.276913e-008, 1.707685e-008]  
18: 	[6.027122e-009, 4.018081e-009], 	[-6.027122e-009, -8.036163e-009]
19: 	[2.352048e-009, -8.820178e-010], 	[-2.352048e-009, 1.764036e-009]


Die Konvergenzprobleme kann man mit dem CG-Verfahren beheben. Mehr dazu im nächsten Workshop. Für dieses Beispiel bekommt man zum Beipsiel

code:
1:
2:
3:
4:
5:
6:
k | xk                                 | rk
-------------------------------------------------------------------------
0: 	[4.500000e+000, 3.000000e+000], 	[-4.500000e+000, -6.000000e+000]  
1: 	[1.756098e+000, -6.585366e-001], 	[-1.756098e+000, 1.317073e+000]  
2: 	[0.000000e+000, 0.000000e+000], 	[0.000000e+000, 0.000000e+000]
Neue Frage »
Antworten »



Verwandte Themen

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