Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Konjugierte Gradienten

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht
Ausgehend von einem beliebigen Startvektor $ x_0$ und $ g_0=-u_1=Ax_0-b$ erhält man mit der Iteration
$\displaystyle x_{\ell}$ $\displaystyle =$ $\displaystyle x_{\ell-1} + \frac{\langle g_{\ell-1},g_{\ell-1}\rangle}{\langle u_{\ell},u_{\ell}\rangle_A}\, u_\ell\,$  
$\displaystyle g_\ell$ $\displaystyle =$ $\displaystyle Ax_\ell-b\,$  
$\displaystyle u_{\ell+1}$ $\displaystyle =$ $\displaystyle -g_\ell+\frac{\langle g_\ell,g_\ell\rangle}{\langle g_{\ell-1},g_{\ell-1}\rangle}\, u_{\ell}\,$  

die Lösung eines linearen Gleichungssystem $ Ax=b$ mit symmetrischer, positiv definiter $ n\times n$-Matrix $ A$ und $ \langle \cdot,\cdot \rangle_A$ dem $ A$-Skalarprodukt in maximal $ n$ Schritten. Bei exakter Rechnung ist $ g_\ell = 0$ spätestens für $ \ell = n$.

Dieses Verfahren wird als Methode der konjugierten Gradienten (cg-Verfahren) bezeichnet.

Für die Gradienten $ g_\ell$ und Suchrichtungen $ u_\ell$ gilt

$\displaystyle g_\ell = g_{\ell -1} + \alpha_\ell Au_\ell, \quad \alpha_\ell = \frac{\left< g_{\ell-1},g_{\ell-1} \right>}{\left< u_\ell,u_\ell\right>_A}. $

Es ist also möglich, bei der Implementierung eines Iterationsschritts

$\displaystyle (x_{\ell-1},g_{\ell-1},u_\ell) \rightarrow (x_\ell,g_\ell,u_{\ell+1}) $

mit nur einer Matrix-Multiplikation, der Berechnung von $ Au_\ell$, auszukommen.

Beispiele:

[Erläuterungen] [Downloads] [Verweise]
  automatisch erstellt am 19.  8. 2013