Cg - Verfahren < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:23 Do 11.12.2008 | | Autor: | Irmchen |
Guten Tag alle zusammen!
Ich beschäftige mich mit dem konjugierten Gradienten - Verfahren ( cg - Verfahren ). Ich habe eine Frage zum Inhalt eines Satzes, der sich auf den cg-Algorithmus bezieht.
Da der Satz sich auf den Algorithmus bezieht, hier erstmal der Algorithmus:
cg - Algorithmus :
Voraussetzung: Sei [mm] f(x) = \bruch{1}{2} x^T A x + b^Tx + x, A \in \mathbb R^{n x n } [/mm] eine symmetrische positiv definite MAtrix und
[mm] g(x) := Ax + b = \nabla f(x) [/mm] der Gradient von f.
Start: Wähle [mm] x^0 \in \mathbb R^n [/mm] und setze [mm] g_0 := g( x^0 ), s_0 := - g_0 [/mm].
Für [mm] i = 0, 1, ... [/mm]
1. Falls [mm] g_i = g ( x^i ) = 0 [/mm] STOP: [mm] x^i [/mm] ist MInimum von f .
2. Sonst setze [mm] x^{i + 1 } := x^i + \lambda_i s_i [/mm] wobei
[mm] \lambda_i := arg min_{ \lambda \ge 0 } f( x^i + \lambda s_i ) [/mm].
3. Berechne [mm] \gamma_{i+1} := \bruch{g_{i+1}^T g_{i+1}}{g_i^T g_i^T } [/mm] und setze [mm] s_{i+1} := -g_{i+1} + \gamma_{i+1}s_i [/mm]
Was macht denn diese [mm] \gamma [/mm] ? Inwiefern spielt das bei der Änderung der Suchrichtung mit, kann man das graphisch erklären?
Satz :
Sei [mm] f(x) = \bruch{1}{2} x^T A x + b^Tx + x, A \in \mathbb R^{n x n } [/mm] eine symmetrische positiv definite MAtrix und [mm] x^0 \in \mathbb R^n [/mm] ein beliebiger Startvektor für den obigen Algorithmus.
Dann gibt es ein kleinstes [mm] m \le n [/mm], so dass [mm] g_m = 0 [/mm]
Weiter gelten in jedem Schritt [mm] l \le m [/mm] die Aussagen:
1a) [mm] s_i^T g_k = 0 [/mm] für [mm] 0 \le i < k \le l [/mm]
b) [mm]s_k^T g_k = - g_k^T g_k [/mm] für [mm] 0 \le k \le l [/mm]
2. [mm] g_i^T g_k = 0 [/mm] für [mm] 0 \le i < k \le l [/mm]
3. [mm] s_i^T A s_k = 0 [/mm] für [mm] 0 \le i < k´\le l [/mm]
Wenn ich das richtig sehe, dann bricht der A nach endlich vielen Rechenschritten höchstens n mit der exakten Berechnung eines MInimums ab, sobald dieses kleinste m gefunden ist, richtig?
Aber ich verstehe nicht die Aussagen 1 - 3 ? Was sagen die mir?
Kann mir das jemand vielleicht erklären ,was man dort sicherstellen möchte.
Vielen lieben Dank für die Hilfe!
VIele Grüße
Irmchen
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Fr 19.12.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
