BiCG Verfahren < Lin. Gleich.-systeme < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 22:23 Sa 25.08.2012 | | Autor: | jumape |
| Aufgabe | | Wie funktioniert das bikonjugierte Gradientenverfahren? |
Hallo,
ich muss das BiCG-Verfahren für eine Prüfung verstehen und erklären können und stoße da gerade an meine Grenzen.
Zur Erklärung des Verfahrens verweise ich einmal auf wikipedia:
http://de.wikipedia.org/wiki/BiCG-Verfahren
Es geht bei dem Verfahren um die Lösung eines linearen Gleichungssystems Ax=b, wobei [mm] A\in \R^{nxn}
[/mm]
Es handelt sich um ein Krylov- Unterraum- Verfahren, d.h. ausgehend von einem Anfangswert [mm] x_{0} [/mm] und dem Residuum [mm] r_{0}=Ax_{0}-b [/mm] werden die Krylov-Unterräume [mm] K_{m}(r_{0},A)=span\{r_{0},Ar_{0},...,A^{m-1}r_{0}\} [/mm] betrachtet und die nächste Iterierte so gewählt, dass gilt: [mm] x_{m}\in x_{0}+K_{m}(r_{0},A)
[/mm]
Damit wird bei exakter Rechnung nach maximal n Schritten die exakte Lösung x* gefunden. Aufgrund von Rundungsfehlern sind die Verfahren aber nicht endlich.
Das BiCG-Verfahren funktioniert nun folgendermaßen:
Zum anfangswert [mm] x_{0} [/mm] und dem Residuum [mm] r_{0} [/mm] wird der Krylowraum zu [mm] A,r_{0} [/mm] und der krylowraum zu [mm] \overline{A^{t}},\hat{r_{0}} [/mm] aufgestellt. wobei [mm] \hat{r_{0}} [/mm] frei gewählt wird.
Der Algorithmus sieht dann folgendermaßen aus:
1. [mm] r_{0}=b-Ax_{0}
[/mm]
2. [mm] \hat{r_{0}} [/mm] wählen
Für k=0,...,n-1:
a. [mm] \alpha_{k}=\bruch{}{<\hat{p_{k}},Ap_{k}>}
[/mm]
b. [mm] x_{k+1}=x_{k}+\alpha_k p_k
[/mm]
c. [mm] r_{k+1}=r_k-\alpha_k [/mm] A [mm] p_k
[/mm]
d. [mm] \hat{r_{k+1}}=\hat{r_k}-\overline{\alpha_k} \overline{A^t} \hat{p_k}
[/mm]
[mm] e.\beta_{k}=\bruch{<\hat{r_{k+1}},r_{k+1}>}{<\hat{r_{k}},r_{k}>}
[/mm]
f. [mm] p_{k+1}=r_{k+1}+\beta_k p_k
[/mm]
g. [mm] \hat{p_{k+1}}=\hat{r_{k+1}}+\overline{\beta_k}\hat{p_{k}}
[/mm]
Wenn ich es jetzt richtig verstanden habe soll hier das residuum minimiert werden. Leider verstehe ich überhaupt nicht, warum das hier geschieht.
Was ich verstanden habe ist, dass die Wahl der [mm] \alpha_{k}, \beta_{k} [/mm] dazu führen dass die Residuen orthogonal zueinander sind, ebenso für die suchrichtungen, d.h. das gilt:
1. [mm] =0
[/mm]
2. [mm] =0
[/mm]
Daraus folgt dann, dass [mm] x_{m} [/mm] die Lösung des Problems: b-Ax orthogonal auf dem Krylowunterraum [mm] K_m{\overline{A^{t}},\hat{r_{0}} }.
[/mm]
ist.
Aber ich habe leider nicht verstanden wie das folgt und waas uns das eigentlich bringt, wenn die Residuen alle orthogonal zueinander sind. Liegt das daran dass sobald m=n das Residuum nur dann orthogonal zu allen anderen Residuen sein kann, wenn es null ist?
Und da man ja nicht bis zum ende durchrechnet und auch nicht exakt rechnen kann, was bringt uns diese Tatsache dann?
Es wäre nett wenn mir jemand helfen könnte.
jumape
Inzwischen bin ich etwas weitergekommen. Ich erkläre mal, was ich denke verstanden habe und ielleicht kann mir dann jemand sagen, ob das so stimmt und wo ich noch Fehler mache:
Das BiCG-Verfahren baut auf dem cg-Verfahren aur und das funktioniert so:
Das cg-Verfahren sucht eine Läsung für das lineare GLeichungssystem Ax=b, wobei A eine spd Matrix ist. Es beginnt mit einem beliebigen STartwert und der Suchrichtung [mm] r_0=Ax_0-b.
[/mm]
In diese Suchrichtung berechnet es erst die optimale Schrittweite [mm] \alpha_k, [/mm] und dann den neuen Vektor [mm] x_{k+1}=x_{k}+\alpha_k*p_k, [/mm] wobei [mm] p_k [/mm] die Suchrichtung ist, also im ersten Schritt [mm] r_0.
[/mm]
Dann berechnet es das nächste Residuum [mm] r_{k+1} [/mm] und mithilfe dessen die nächste Scuhrichtung: Die nächste Suchrichtung wird dabei so gewählt, dass sie A-orthogonal auf allen vorherigen Scuhrichtungen steht. Das macht Sinn, da dadurch eine orthogonale Basis aus Suchrichtungen entsteht und der Vektor [mm] x_{k+1} [/mm] immer die optimale Linearkombi des Anfangswert und der bisherigen Suchrichtungen ist findet man damit nach höchstens n Schritten die richtige Lösung, wenn man exakt rechnet.
Jetzt ist das BiCG-Verfahren eine Verallgemeinerung des cg-Verfahrens für nicht selbstadjungierte Matrizen (habe ich das richtig verstanden?). Daher werden zwei Krylow-Unterräume gebildet und das Verfahren sieht anders aus. Speziell ändert sich:
cg
[mm] \alpha_k=\bruch{}{} [/mm]
[mm] \beta_{k}=-\bruch{}{}
[/mm]
bicg
[mm] \alpha_{k}=\bruch{}{<\hat{p_{k}},Ap_{k}>}
[/mm]
[mm] \beta_{k}=\bruch{<\hat{r_{k+1}},r_{k+1}>}{<\hat{r_{k}},r_{k}>}
[/mm]
[mm] \hat{p_{k+1}}=\hat{r_{k+1}}+\overline{\beta_k}\hat{p_{k}}
[/mm]
[mm] \hat{r_{k+1}}=\hat{r_k}-\overline{\alpha_k} \overline{A^t} \hat{p_k}
[/mm]
Und das ist jetzt auch das, was ich nicht verstehe, warum muss ich das machen und warum ist dass die Lösung?
Ich nehme jetzt mal an, irgendwas geht mit dem cg-Verfahren schief sobald A nicht mehr symmetrisch ist, also muss es irgendwie anders gelöst werden und das geht über die zweite Folge die zum adjungierten Problem gehört. Aber wo ist diese STelle wo es kaputt geht und warum ist das die Lösung dazu?
Es wäre nett, wenn mir jemand helfen könnte.
jumape
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:20 Di 25.09.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
