Konjugált gradiens módszer

A gradiens módszer megfelelő lépésközeinek (zöld) és a konjugált gradiens módszer (piros) minimalizáló formuláinak összehasonlítása. A konjugált gradiens módszer legfeljebb n lépésben konvergál a minimumhoz, ahol n a mátrix dimenziója (itt n=2).

A matematikában a konjugált gradiens módszer bizonyos, szimmetrikus és pozitív definit mátrixszal rendelkező lineáris egyenletrendszerek numerikus megoldására szolgáló algoritmus. A konjugált gradiens módszer egy iterációs módszer, mely alkalmazható olyan rendszerek kezelésére is, melyek túl nagyok ahhoz, hogy direkt módon Cholesky-felbontással megoldhatók legyenek. Ezek főként parciális differenciálegyenletek megoldásakor merülnek fel.

A konjugált gradiens módszer használható olyan optimalizációs problémák megoldására is, mint például az energiaminimalizáció.

A bikonjugált gradiens módszer a fenti módszer általánosítása nemszimmetrikus mátrixokra. A nemlineáris egyenletrendszerek minimumának meghatározására többféle nemlineáris konjugált gradiens módszer létezik.

A módszer leírása

Adott a következő lineáris egyenletrendszer

Ax = b

ahol A egy valós, szimmetrikus (ha A^T = A), pozitív definit, nxn-es mátrix.

Jelöljük az egyenletrendszer egyedüli megoldását x_*-gal.

A konjugált gradiens módszer, mint direkt módszer

Vegyünk két nem-zéró vektort, u-t és v-t, melyek egymás konjugáltjai, ha

$\mathbf {u} ^{\mathrm {T} }\mathbf {A} \mathbf {v} =\mathbf {0} .$

Mivel A szimmetrikus és pozitív, a baloldalt belső szorzatként definiálhatjuk

$\langle \mathbf {u} ,\mathbf {v} \rangle _{\mathbf {A} }:=\langle \mathbf {A} ^{\mathrm {T} }\mathbf {u} ,\mathbf {v} \rangle =\langle \mathbf {A} \mathbf {u} ,\mathbf {v} \rangle =\langle \mathbf {u} ,\mathbf {A} \mathbf {v} \rangle =\mathbf {u} ^{\mathrm {T} }\mathbf {A} \mathbf {v} .$

Két vektor konjugált, ha ortogonálisak, és a belső szorzatukra fennáll a fenti összefüggés. A konjugált tulajdonság szimmetrikus reláció: ha u konjugálja v, akkor v konjugáltja u.

Tegyük fel, hogy {p_k} n db kölcsönösen konjugált vektorokból képzett sorozat. Ekkor p_k bázist alkot Rⁿ felett, so így ebben a bázisban az x_* megoldást kiterjeszthetjük:

$\mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _{i}$

A koefficiens a következőképpen adódik:

$\mathbf {b} =\mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {A} \mathbf {p} _{i}.$

$\mathbf {p} _{k}^{\mathrm {T} }\mathbf {b} =\mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {x} _{*}=\sum _{i=1}^{n}\alpha _{i}\mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {p} _{i}=\alpha _{k}\mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {p} _{k}.$

$\alpha _{k}={\frac {\mathbf {p} _{k}^{\mathrm {T} }\mathbf {b} }{\mathbf {p} _{k}^{\mathrm {T} }\mathbf {A} \mathbf {p} _{k}}}={\frac {\langle \mathbf {p} _{k},\mathbf {b} \rangle }{\,\,\,\langle \mathbf {p} _{k},\mathbf {p} _{k}\rangle _{\mathbf {A} }}}={\frac {\langle \mathbf {p} _{k},\mathbf {b} \rangle }{\,\,\,\|\mathbf {p} _{k}\|_{\mathbf {A} }^{2}}}.$

Ez az eredmény egy valószínűség, mely eleget tesz a fenti belső szorzat kritériumának. Ez a következő módszert szolgáltatja az Ax = b egyenlet megoldására. Először megkeressük az n db konjugált vektor sorozatát, majd kiszámítjuk α_k koefficienseket.

A konjugált gradiens módszer, mint iterációs módszer

Ha megfelelően választjuk meg p_k-t, nincs szükség az összes koefficiens kiszámítására, hogy jó közelítéssel megadjuk x_*-t.Tehát ez esetben a konjugált gradiens módszert, mint iterációs módszert alkalmazzuk. Ez lehetővé teszi olyan egyenletrendszerek megoldását, melyeknél n túl nagy, és ezért direkt megoldásuk túl sok időt venne igénybe.

Az x_* első közelítését jelöljük x₀–lal. Tegyük fel, hogy x₀ = 0. Az x₀-lal kezdve a megoldást keressük, és minden iterációs lépésben szükségünk van egy olyan mutatóra, mely megadja, mennyire jutottunk közel x_*-hoz. A mutató onnan adódik, hogy x_* szintén egy négyzetes függvény minimum helye, vagyis ha f(x) egyre kisebb, akkor egyre közelebb jutunk x_* értékéhez:

$f(\mathbf {x} )={\frac {1}{2}}\mathbf {x} ^{\mathrm {T} }\mathbf {A} \mathbf {x} -\mathbf {b} ^{\mathrm {T} }\mathbf {x} ,\quad \mathbf {x} \in \mathbf {R} ^{n}.$

Ez a képlet sugallja, hogy a p₁ bázisvektor az f függvény gradiense az x = x₀ helyen, és p₁ egyenlő Ax₀‒b. Ha x₀ = 0, akkor p₁ = ‒b. A többi bázisvektor a gradiens konjugáltja, ennélfogva ezt a módszert konjugált gradiens módszernek nevezzük.

Legyen r_k a k-adik lépés maradéka:

$\mathbf {r} _{k}=\mathbf {b} -\mathbf {Ax} _{k}.\,$

Mivel r_k az f függvény negatív garadiense az x = x_k helyen, ezért a gradiens módszer abból állna, hogy módosítsa r_k irányát. Itt feltesszük, hogy p_k irányai egymás konjugáltjai, így azt az irányt válassztjuk, amely legközelebb esik r_k –hoz. Ez a következő kifejezéshez vezet:

$\mathbf {p} _{k+1}=\mathbf {r} _{k}-\sum _{i\leq k}{\frac {\mathbf {p} _{i}^{\mathrm {T} }\mathbf {A} \mathbf {r} _{k}}{\mathbf {p} _{i}^{\mathrm {T} }\mathbf {A} \mathbf {p} _{i}}}\mathbf {p} _{i}$

A megoldó algoritmus

Néhány egyszerűsítés, a következő algoritmusra vezet Ax = b megoldásában. A kezdő x₀ vektor lehet egy megoldáshoz közeli szám, avagy nulla.

$\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}\,$

$\mathbf {p} _{0}:=\mathbf {r} _{0}\,$

$k:=0\,$

ismétlés

$\alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {r} _{k}}{\mathbf {p} _{k}^{\mathrm {T} }\mathbf {Ap} _{k}}}\,$

$\mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}\,$

$\mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}\,$

ha r_k+1 elegendően kicsiny akkor fejezze be a ciklust vége ha

$\beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {r} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {r} _{k}}}\,$

$\mathbf {p} _{k+1}:=\mathbf {r} _{k+1}+\beta _{k}\mathbf {p} _{k}\,$

$k:=k+1\,$

vége ismétlés

Az eredmény: x_k+1

Példa kód a konjugált gradiens módszerre Octave programnyelvben

function [x] = conjgrad(A,b,x0)

   r = b - A*x0;
   w = -r;
   z = A*w;
   a = (r'*w)/(w'*z);
   x = x0 + a*w;
   B = 0;

   for i = 1:size(A)(1);
      r = r - a*z;
      if( norm(r) < 1e-10 )
           break;
      end if
      B = (r'*z)/(w'*z);
      w = -r + B*w;
      z = A*w;
      a = (r'*w)/(w'*z);
      x = x + a*w;
   end

end

A konjugált gradiens módszer előfeltétel megadásával

Néhány esetben a gyors konvergencia eléréséhez szükség van előfeltétel megadására. A konjugált gradiens módszer ez esetben a következő formában adható meg:

$\mathbf {r} _{0}:=\mathbf {b} -\mathbf {Ax} _{0}$

$\mathbf {z} _{0}:=\mathbf {M} ^{-1}\mathbf {r} _{0}$

$\mathbf {p} _{0}:=\mathbf {z} _{0}$

$k:=0\,$

ismétlés

$\alpha _{k}:={\frac {\mathbf {r} _{k}^{\mathrm {T} }\mathbf {z} _{k}}{\mathbf {p} _{k}^{\mathrm {T} }\mathbf {Ap} _{k}}}$

$\mathbf {x} _{k+1}:=\mathbf {x} _{k}+\alpha _{k}\mathbf {p} _{k}$

$\mathbf {r} _{k+1}:=\mathbf {r} _{k}-\alpha _{k}\mathbf {Ap} _{k}$

ha r_k+1 elegendően kicsiny akkor fejezze be a ciklust vége ha

$\mathbf {z} _{k+1}:=\mathbf {M} ^{-1}\mathbf {r} _{k+1}$

$\beta _{k}:={\frac {\mathbf {r} _{k+1}^{\mathrm {T} }\mathbf {z} _{k+1}}{\mathbf {r} _{k}^{\mathrm {T} }\mathbf {z} _{k}}}$

$\mathbf {p} _{k+1}:=\mathbf {z} _{k+1}+\beta _{k}\mathbf {p} _{k}$

$k:=k+1\,$

vége ismétlés

Az eredmény x_k+1

A fenti formulákban M az előfeltétel, és ez is szimmetrikus és pozitív definit. Ez ekvivalens az előfeltétel nélküli konjugált gradiens módszerrel, abban az esetben, ha érvényesül:

$\mathbf {E} ^{-1}\mathbf {A} \mathbf {E} ^{-\mathrm {T} }\mathbf {\hat {x}} =\mathbf {E} ^{-1}\mathbf {b}$,

ahol

$\mathbf {EE} ^{\mathrm {T} }=\mathbf {M}$

$\mathbf {\hat {x}} =\mathbf {E} ^{\mathrm {T} }\mathbf {x}$

Külső hivatkozások (angol)

• Conjugate gradient method
• Biconjugate gradient method (BICG)
• Preconditioned conjugate gradient method (PCG)
• Nonlinear conjugate gradient method

Referenciák (angol)

The conjugate gradient method was originally proposed in

• Hestenes, Magnus R., Stiefel, Eduard (1952. December). „Methods of Conjugate Gradients for Solving Linear Systems” (PDF). Journal of Research of the National Bureau of Standards 49 (6).  

Descriptions of the method can be found in the following text books:

• Kendell A. Atkinson (1988), An introduction to numerical analysis (2nd ed.), Section 8.9, John Wiley and Sons. ISBN 0-471-50023-2.
• Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Gene H. Golub and Charles F. Van Loan, Matrix computations (3rd ed.), Chapter 10, Johns Hopkins University Press. ISBN 0-8018-5414-8.