Konjugált gradiens módszer

A Wikipédiából, a szabad enciklopédiából
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[szerkesztés | forrásszöveg szerkesztése]

Adott a következő lineáris egyenletrendszer

Ax = b

ahol A egy valós, szimmetrikus (ha AT = 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[szerkesztés | forrásszöveg szerkesztése]

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 {pk} n db kölcsönösen konjugált vektorokból képzett sorozat. Ekkor pk bázist alkot Rn felett, so így ebben a bázisban az x* megoldást kiterjeszthetjük:

 \mathbf{x}_* = \sum^{n}_{i=1} \alpha_i \mathbf{p}_i

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

 \mathbf{b}=\mathbf{A}\mathbf{x}_* = \sum^{n}_{i=1} \alpha_i  \mathbf{A} \mathbf{p}_i.
 \mathbf{p}_k^{\mathrm{T}} \mathbf{b}=\mathbf{p}_k^{\mathrm{T}} \mathbf{A}\mathbf{x}_* = \sum^{n}_{i=1} \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[szerkesztés | forrásszöveg szerkesztése]

Ha megfelelően választjuk meg pk-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 x0–lal. Tegyük fel, hogy x0 = 0. Az x0-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}) = \frac12 \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 p1 bázisvektor az f függvény gradiense az x = x0 helyen, és p1 egyenlő Ax0b. Ha x0 = 0, akkor p1 = ‒b. A többi bázisvektor a gradiens konjugáltja, ennélfogva ezt a módszert konjugált gradiens módszernek nevezzük.

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

 \mathbf{r}_k = \mathbf{b} - \mathbf{Ax}_k.  \,

Mivel rk az f függvény negatív garadiense az x = xk helyen, ezért a gradiens módszer abból állna, hogy módosítsa rk irányát. Itt feltesszük, hogy pk irányai egymás konjugáltjai, így azt az irányt válassztjuk, amely legközelebb esik rk –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[szerkesztés | forrásszöveg szerkesztése]

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

\mathbf{r}_0 := \mathbf{b} - \mathbf{A x}_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{A p}_k}  \,
\mathbf{x}_{k+1} := \mathbf{x}_k + \alpha_k \mathbf{p}_k \,
\mathbf{r}_{k+1} := \mathbf{r}_k - \alpha_k \mathbf{A p}_k \,
ha rk+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: xk+1

Példa kód a konjugált gradiens módszerre Octave programnyelvben[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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{A x}_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{A p}_k}
\mathbf{x}_{k+1} := \mathbf{x}_k + \alpha_k \mathbf{p}_k
\mathbf{r}_{k+1} := \mathbf{r}_k - \alpha_k \mathbf{A p}_k
ha rk+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 xk+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}

Források[szerkesztés | forrásszöveg szerkesztése]

The conjugate gradient method was originally proposed in

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.