CG Verfahren (Algorithmus)

28.12.2017, 20:28

alina94

CG Verfahren (Algorithmus)

Hey

ich habe in einem Skript hier folgenden Algorithmus für das CG-Verfahren (für $\begin{eqnarray*} Ax = b \end{eqnarray*}$ , $\begin{eqnarray*} A \end{eqnarray*}$ spd):

Wähle $\begin{eqnarray*} x_0 \in \mathbb{R}^n \end{eqnarray*}$ und setze $\begin{eqnarray*} d_0 := r_0 := b - Ax_0 \end{eqnarray*}$ .
Für $\begin{eqnarray*} k=0,1,2,... \end{eqnarray*}$ :
(i) Falls $\begin{eqnarray*} d_k = 0 \end{eqnarray*}$ : Abbruch, $\begin{eqnarray*} x_k \end{eqnarray*}$ ist gesuchte Lösung.
(ii) Andernfalls: Setze

$\begin{eqnarray*} \ \ t_k = \frac{(r_k,r_k)}{(Ad_k,d_k)} \\ \ \ x_{k+1} = x_k + t_k d_k \\ \ \ r_{k+1} = r_k - t_k A d_k \\ \ \ \beta _k = \frac{(r_{k+1}, r_{k+1})}{(r_k, r_k)} \\ \ \ d_{k+1} = r_{k+1} + \beta _k d_k \end{eqnarray*}$

Anschließend ist noch bemerkt, dass gilt

$\begin{eqnarray*} b - Ax_{k+1} = b - Ax_k - t_k A d_k = r_k - Ad_k \end{eqnarray*}$

Ich habe zwecks Verständnis jetzt 2 Fragen:
1.) Wieso ist $\begin{eqnarray*} x_k \end{eqnarray*}$ die Lösung, wenn $\begin{eqnarray*} d_k = 0 \end{eqnarray*}$ ?
2.) Woher kommt die 2. Gleichung in der anschließenden Bemerkung?

Meine Vermutung ist, dass beides zusammenhängt. In einem anschließenden Satz wurde bewiesen, dass für $\begin{eqnarray*} d_k = 0 \end{eqnarray*}$ auch $\begin{eqnarray*} r_k = 0 \end{eqnarray*}$ . Auf der linken Seite der Bemerkung steht schließlich das Residuum, das null werden muss. Und auf der rechten Seite vermute ich gerade, ob das ein Druckfehler ist und eigentlich $\begin{eqnarray*} r_k - t_k Ad_k \end{eqnarray*}$ heißen muss, was genau $\begin{eqnarray*} r_{k+1} \end{eqnarray*}$ entspräche nach der Definition? Allerdings sehe ich auch hier noch nicht, wie dann die Gleichheit folgen würde.
Wäre super, wenn mir hier jemand weiterhelfen oder mir sagen könnte ob ich gerade auf dem Holzweg bin. Danke schon mal! smile

01.01.2018, 20:37

sibelius84

Auf diesen Beitrag antworten »

Hallo alina,

was bedeutet denn "CG"? Mir sagt Jacobi oder Gauß-Seidel in diesem Zusammenhang etwas. Jedenfalls scheint es hier um die Implementierung eines iterativen Verfahrens zu gehen. Und wenn eben die Iterierte x_k sich ab dann nicht mehr verändert (also x_k = x_(k+1) = x_(k+2) = ...), dann handelt es sich um die Lösung, zumindest wenn die Iteration auf dem Banach'schen Fixpunktsatz basiert.

In der zweiten Gleichung gilt die erste Gleichheit nach der Definition von x_(k+1), und für die zweite bin ich gerade unsicher, denn b taucht ja in den ganzen Definitionen praktisch gar nicht auf, nur oben drüber bei r_0 und d_0. Man könnte versuchen es so anzugehen, um anhand dessen vielleicht etwas zu sehen:

$\begin{eqnarray*} r_0 = b-Ax_0 \end{eqnarray*}$
$\begin{eqnarray*} r_1 = r_0 - t_0Ad_0 = b-Ax_0 -t_0Ad_0 \end{eqnarray*}$

$\begin{eqnarray*} \ldots \end{eqnarray*}$

LG
sibelius84

03.01.2018, 15:28

alina94

Auf diesen Beitrag antworten »

Hallo sibelius,

danke für deine Antwort! CG steht für Conjugate Gradients (also ein Krylow Raum Verfahren, das beruht soweit ich sehe nicht auf dem Banachschen Fixpunktsatz), hat mit Jacobi und Gauß Seidel aber nicht direkt zu tun. Ich habe mir das Ganze jetzt so erklärt:

Nach Definition ist $\begin{eqnarray*} r_0 = b - ax_0 \end{eqnarray*}$ . Und induktiv erhalten wir

$\begin{eqnarray*} b - Ax_{k+1} = b - Ax_k - t_kAd_k = r_k - t_kAd_k = r_{k+1} \end{eqnarray*}$ ,

wobei die letzte Gleichung einfach Definition aus dem Algorithmus ist, die vorletzte benutzt die I.V. Dementsprechend wäre die Stelle im Skript tatsächlich ein Druckfehler, was dann wieder zu meiner anfänglichen Annahme passt.

05.01.2018, 22:45

sibelius84

Auf diesen Beitrag antworten »

Zitat:

Fortunately, the conjugate gradient method can be used as an iterative method as it provides monotonically improving approximations $\begin{eqnarray*} \mathbf {x} _{k} \end{eqnarray*}$ to the exact solution [...]. The improvement is typically linear and its speed is determined by the condition number $\begin{eqnarray*} \kappa (A) \end{eqnarray*}$ of the system matrix A: the larger $\begin{eqnarray*} \kappa (A) \end{eqnarray*}$ is, the slower the improvement.[2]
(Quelle: en.wikipedia.org)

Also handelt es sich um ein Iterationsverfahren, bei dem die Lösung x_k in jedem Schritt besser, und der Fehler r_k demnach in jedem Schritt kleiner wird. Wenn also x_k = x_(k+1) für irgendein k eintritt, so muss x_k schon die Lösung gewesen sein (sonst hätte sich ja noch etwas geändert / verbessert).

09.01.2018, 22:40

alina94

Auf diesen Beitrag antworten »

Zitat:

Original von sibelius84

Zitat:

So hatte ich es bisher noch nicht betrachtet, aber ja, das leuchtet natürlich ein. Danke nochmal smile

Neue Frage »

Antworten »

CG Verfahren (Algorithmus)

Verwandte Themen