Beweis mit konjugiertem Grandientenverfahren

19.05.2010, 21:21

Lea

Beweis mit konjugiertem Grandientenverfahren

Hallo
Ich habe eine Aufgabe zu lösen bei der ich nicht recht weiß wie ich da weiterkomme.

Sei $\begin{eqnarray*} A\in \mathbb R^{nxn} \end{eqnarray*}$ symmetrisch und positiv definit. Die Vektoren $\begin{eqnarray*} g_i \end{eqnarray*}$ und $\begin{eqnarray*} v_i \end{eqnarray*}$ seien durch das konjugierte Gradientenverfahren erzeugt. Zeigen Sie, dass dann gilt:
$\begin{eqnarray*} span(v_0,...,v_i)=span(g_0,...,g_i)=span(g_0,Ag_0,...,A^ig_0)=K_{i-1}(A,g_0) \end{eqnarray*}$ , wobei $\begin{eqnarray*} span(x_1,---,x_n) \end{eqnarray*}$ die lineare Hülle der Vektoren $\begin{eqnarray*} x_1,...,x_n \end{eqnarray*}$ bezeichnet und K den Krylovraum.

Also ich habe die Definition des Krylovraums angewandt und habe dann für
$\begin{eqnarray*} K_{i-1}(A,g_0)=span(g_0,Ag_0,A^2g_0,...,A^{i-2}g_0 \end{eqnarray*}$
Aber das hilft mir ja noch nicht richtig viel.
Außerdem weiß ich, dass $\begin{eqnarray*} g_i=Ax_i-b \end{eqnarray*}$ beim konjugierten Gradientenverfahren ist und [l]v_i[l] die Abstiegsrichtung beschreibt.
Aber ich weiß nicht wi ich da irgendwie mit weiterkommen soll.
Kann mir da vielleicht jemand etwas helfen?
Das wäre super.

19.05.2010, 23:37

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Da in jeder Vorlesung die Variablen anders belegt werden, wirst du nicht umhin kommen, das CG-Verfahren in eurer Notation hier zu posten. Ich werde in den nächsten Tagen keine Zeit haben, mich um diesen Thread zu kümmern. Vielleicht findest du hier eine Gedankenanregung:

[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren

Wink

23.05.2010, 12:12

Lea

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Danke für die Antwort. Habe mich bei dem Link mal eingelesen. Hier zuerst mal meine Notation:
$\begin{eqnarray*} x_i \end{eqnarray*}$ =Interative $\begin{eqnarray*} v_i \end{eqnarray*}$ = Abstiegsrichtung und $\begin{eqnarray*} g_i \end{eqnarray*}$ =Residuen
$\begin{eqnarray*} x_0 \in \mathbb R^n \end{eqnarray*}$
$\begin{eqnarray*} g_0=Ax_0-b \end{eqnarray*}$ und $\begin{eqnarray*} v_0=-g_0 \end{eqnarray*}$
$\begin{eqnarray*} \alpha_i=\frac{\|g_i\|^2}{v_i^TAv_i} \end{eqnarray*}$
$\begin{eqnarray*} x_{i+1}=x_i+\alpha_i v_i \end{eqnarray*}$
$\begin{eqnarray*} g_{i+1}=g_i+\alpha_i Av_i \end{eqnarray*}$
$\begin{eqnarray*} \beta_i=\frac{\|g_{i+1}\|^2}{\|g_i\|^2} \end{eqnarray*}$
$\begin{eqnarray*} v_{i+1}=-g_{i+1}+\beta_i v_i \end{eqnarray*}$
Beim Beweis 7a wird ja das erste Gleichzeichen bewiesen. Allerdings passt die IA bei mir schon nicht so ganz weil bei mir $\begin{eqnarray*} v_0=-g_0 \end{eqnarray*}$ ist. Aber wenn ich meine Gleichung für das $\begin{eqnarray*} g_0 \end{eqnarray*}$ mit minus eins multipliziere hätte ich das gleiche wie in deiner Notation. Darf ich das dann so verwenden?
Aber die anderen "2 Gleichzeichen fehlen mir irgendwie noch. Vielleicht findest du ja nochmal kurz Zeit zum drüberschauen. Wäre dir sehr dankbar.

23.05.2010, 14:25

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren

Zitat:

Original von Lea
Beim Beweis 7a wird ja das erste Gleichzeichen bewiesen. Allerdings passt die IA bei mir schon nicht so ganz weil bei mir $\begin{eqnarray*} v_0=-g_0 \end{eqnarray*}$ ist. Aber wenn ich meine Gleichung für das $\begin{eqnarray*} g_0 \end{eqnarray*}$ mit minus eins multipliziere hätte ich das gleiche wie in deiner Notation. Darf ich das dann so verwenden?.

Wie gesagt, wenig Zeit. Nur ist bei mir das Residuum doch $\begin{eqnarray*} b-Ax \end{eqnarray*}$ , also sollten die Vorzeichen am Ende doch gleich sein. verwirrt

23.05.2010, 16:26

Lea

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Ja das meinte ich. dass das ja eigentlich gehn müsste. Trotzdem danke für die antwort.

23.05.2010, 22:49

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren

Zitat:

Lea
$\begin{eqnarray*} x_i \end{eqnarray*}$ =Interative $\begin{eqnarray*} v_i \end{eqnarray*}$ = Abstiegsrichtung und $\begin{eqnarray*} g_i \end{eqnarray*}$ =Residuen
$\begin{eqnarray*} x_0 \in \mathbb R^n \end{eqnarray*}$
$\begin{eqnarray*} g_0=Ax_0-b \end{eqnarray*}$ und $\begin{eqnarray*} v_0=-g_0 \end{eqnarray*}$
$\begin{eqnarray*} \alpha_i=\frac{\|g_i\|^2}{v_i^TAv_i} \end{eqnarray*}$
$\begin{eqnarray*} x_{i+1}=x_i+\alpha_i v_i \end{eqnarray*}$
$\begin{eqnarray*} g_{i+1}=g_i+\alpha_i Av_i \end{eqnarray*}$
$\begin{eqnarray*} \beta_i=\frac{\|g_{i+1}\|^2}{\|g_i\|^2} \end{eqnarray*}$
$\begin{eqnarray*} v_{i+1}=-g_{i+1}+\beta_i v_i \end{eqnarray*}$

Zitat:

tigerbine

Der Algorithmus lautet

Algorithmus:

$\begin{eqnarray*} x_0&&=0 \qquad \qquad \quad \text{ (zweckmäßig)} \\r_0&&=b-Ax_0 \qquad \text{Residuum = neg. Gradient} \\p_0&& = r_0 \\\\ s_k&&=\frac{r_k^Tr_k}{p_k^TAp_k} \qquad \text{Lauflänge in Richtung }p_k \\ x_{k+1}&&=x_k+s_k\cdot p_k \quad \text{ Minimum in Richtung }p_k \\r_{k+1}&&=r_k-s_k\cdot Ap_k \quad \text{ neues Residuum } \\\\ &&\fbox{$\displaystyle \text{Prüfe, ob } r_{k+1} = 0 \text{, dann ist } x_{k+1} = x^* \Rightarrow \text{ENDE} $} \\\\\\t_k&&=\frac{r_{k+1}^Tr_{k+1}}{r_k^T\cdot r_k} \\ p_{k+1} &&= r_{k+1} + t_k\cdot p_k \text{ neue Abstiegsrichtung, A-konjugiert zu }p_k \end{eqnarray*}$

Lehrer

Es wird sich am Ende Folgendes zeigen:

$\begin{eqnarray*} \fbox{$\displaystyle \text{Das cg-Verfahren bricht nach spätestens } m \leq n \text{ Schritten ab, wobei m die Anzahl der versch. Eigenwerte von A ist} $} \end{eqnarray*}$

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 $\begin{eqnarray*} \mathcal K_k(p_0, A)=\text{span}\{p^0, Ap_0,...,A^{k-1}p_0\} \end{eqnarray*}$ minimiert. Aus den Eigenschaften der Krylow-Räume folgt dann die Eigenschaft, dass der Algorithmus theoretisch in $\begin{eqnarray*} m \leq n \end{eqnarray*}$ Schritten terminiert.

Wenn du dir das man anschaust, dann ist das doch das gleiche. Du hast das Residuum anders herum berechnet, daher musst du das VZ der Abstiegsrichtung auch rumdrehen. Augenzwinkern

30.05.2010, 20:26

Lea

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Vielen Dank für die ausführliche Antwort.Für die erste Gleichung
$\begin{eqnarray*} span(v_0,...,v_i)=span(g_0,...,g_i) \end{eqnarray*}$ habe ich in dem Skript einen Beweis gefunden, den ich auch soweit verstanden habe.
Dann habe ich versucht diese Gleichung zu beweisen.
$\begin{eqnarray*} span(g_0,Ag_0,...,A^ig_0)=K_{i-1}(A,g_0) \end{eqnarray*}$
Ich bin habe die Definition für Krylovräume angewandt und bin dann auf folgendes gekommen:
$\begin{eqnarray*} K_{i-1}(A,g_0)=span(g_0,Ag_0,A^2g_0...,A^{i-2}g_0) \end{eqnarray*}$ Das passt ja irgendwie nicht. Bei der dann noch fehlenden Gleichung hänge ich noch ziemlich. Kannst du mir da einen Tipp geben?

31.05.2010, 17:16

Lea

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Es war ein Fehler in der Aufgabenstellung. Der Krylovraum hat die Ordnung i+1. Damit hat sich auch ein Problem gelöst. Dann ist nämlich
$\begin{eqnarray*} K_{i+1}(A,g_0)=span(g_0,Ag_0,A^2g_0...,A^{(i+1)-1}g_0) \end{eqnarray*}$ und das stimmt ja dann. Aber mit dieser Gleichung habe ich immer noch ein Problem:
$\begin{eqnarray*} span(g_0,...,g_i)=span(g_0,Ag_0,...,A^ig_0) \end{eqnarray*}$

31.05.2010, 22:30

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Hilft das denn nicht weiter? verwirrt

[WS] Lineare Gleichungssysteme 5 - Das CG-Verfahren

Es tut mir Leid, dass ich nicht für mehr Hilfe Zeit habe.

31.05.2010, 23:04

Lea

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Also den Beweis 7a) konnte ich gut verwenden. Aber meine zweite Gleichung konnte ich damit leider nicht beweisen. Danke für die Hilfe trotzdem.

31.05.2010, 23:11

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Das müßte aber doch in 7b stehen... verwirrt

01.06.2010, 10:40

Lea

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Das Problem ist, dass jetzt in meiner Schreibweise geschrieben, bei der 7b bewiesen wird,
$\begin{eqnarray*} span(g_0,...,g_i)=span(v_0,Av_0,...,A^iv_0) \end{eqnarray*}$
Ich muss aber doch zeigen, dass
$\begin{eqnarray*} span(g_0,...,g_i)=span(g_0,Ag_0,...,A^ig_0) \end{eqnarray*}$
Deswegen hatte ich Probleme das zu übertragen. Oder habe ich da etwas falsch verstanden oder übersehen?

01.06.2010, 13:13

tigerbine

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Du hattest

Zitat:

Vielen Dank für die ausführliche Antwort.Für die erste Gleichung
$\begin{eqnarray*} span(v_0,...,v_i)=span(g_0,...,g_i) \end{eqnarray*}$ habe ich in dem Skript einen Beweis gefunden, den ich auch soweit verstanden habe.

Wie hängen denn dann v0 und g0 zusammen?

02.06.2010, 11:07

Lea

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Sie sind gleich?

02.06.2010, 15:09

tiger_off

Auf diesen Beitrag antworten »

RE: Beweis mit konjugiertem Grandientenverfahren
Setz doch mal i=0. Sie sind zumindest linear abhängig. Wenn nicht sogar identisch.

Neue Frage »

Antworten »

Beweis mit konjugiertem Grandientenverfahren

Verwandte Themen