[WS] Lineare Gleichungssysteme 4 - Das Gradientenverfahren |
05.07.2007, 16:35 | tigerbine | Auf diesen Beitrag antworten » | ||||||||||
[WS] Lineare Gleichungssysteme 4 - Das Gradientenverfahren Ausgangssituation: SPD-Matrix Lösen äquivalenter Probleme
Das Gradienten-Verfahren |
||||||||||||
05.07.2007, 16:47 | 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. --------------------------------------------------------------- |
||||||||||||
05.07.2007, 17:24 | tigerbine | Auf diesen Beitrag antworten » | ||||||||||
8. Lösen äquivalenter Probleme -------------------------------------------------------------------------------------------------- Dabei nennt man die Norm auch Energienorm. |
||||||||||||
05.07.2007, 17:55 | 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: |
||||||||||||
06.07.2007, 01:35 | tigerbine | Auf diesen Beitrag antworten » | ||||||||||
8b. Beweis (2) Behauptung (2): Beweis: Aus der Definition von e folgt und es gilt . Somit gilt: |
||||||||||||
06.07.2007, 02:31 | tigerbine | Auf diesen Beitrag antworten » | ||||||||||
8c. Beweis (3) Behauptung (3): Beweis: Da sich und nur um die Konstante unterscheiden folgt die Äquivalenz sofort. |
||||||||||||
Anzeige | ||||||||||||
|
||||||||||||
06.07.2007, 03:49 | 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. 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. |
||||||||||||
10.07.2007, 19:46 | 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 |
||||||||||||
10.07.2007, 19:48 | 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. |
||||||||||||
10.07.2007, 20:44 | 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: |
||||||||||||
10.07.2007, 20:46 | tigerbine | Auf diesen Beitrag antworten » | ||||||||||
9a. Algorithmus |
||||||||||||
10.07.2007, 21:17 | tigerbine | Auf diesen Beitrag antworten » | ||||||||||
9b. Die Residuen sind orthogonal Behauptung Die Abstiegsrichtungen sind orthogonal. Beweis: [/quote] |
||||||||||||
10.07.2007, 21:17 | 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: 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. |
||||||||||||
16.08.2007, 13:58 | 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 .
Die Konvergenzprobleme kann man mit dem CG-Verfahren beheben. Mehr dazu im nächsten Workshop. Für dieses Beispiel bekommt man zum Beipsiel
|
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
|
Die Neuesten » |