„Konjugált gradiens módszer” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
Új oldal, tartalma: „right|thumb|A [[gradiens módszer megfelelő lépésközeinek (zöld) és a konjugált gradiens módszer (piros) minimalizál…” |
Nincs szerkesztési összefoglaló |
||
1. sor:
[[Image:Conjugate gradient illustration.svg|right|thumb|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
A konjugált gradiens módszer használható olyan opimalizációs problémák megoldására is, mint például az [[energia]] minimalizáció.
7. sor:
A nem-lineáris egyenletrendszerek minimumának meghatározására többféle nem-lineáris konjugált gradiens módszer létezik.
==
Adott a következő lineáris egyenletrendszer
:'''Ax''' = '''b'''
ahol '''A''' egy valós, szimmetrikus (ha '''A'''<sup>T</sup> = '''A'''), pozitív definit, nxn-es mátrix.
Jelöljük az egyenletrendszer egyedüli megoldását '''x'''<sub>*</sub>-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
:<math> \mathbf{u}^{\mathrm{T}} \mathbf{A} \mathbf{v} = \mathbf{0}. </math>
Mivel A szimmetrikus és pozitív, a bal oldalt belső szorzatként definiálhatjuk
:<math> \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}. </math>
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'''<sub>''k''</sub>} n db kölcsönösen konjugált vektorokból képzett sorozat. Ekkor '''p'''<sub>''k''</sub> bázist alkot '''R'''<sup>''n''</sup> felett, so így ebben a bázisban az '''x'''<sub>''*''</sub> megoldást kiterjeszthetjük:
:<math> \mathbf{x}_* = \sum^{n}_{i=1} \alpha_i \mathbf{p}_i</math>
A koefficiens a következőképpen adódik:
:<math> \mathbf{b}=\mathbf{A}\mathbf{x}_* = \sum^{n}_{i=1} \alpha_i \mathbf{A} \mathbf{p}_i.</math>
:<math> \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.</math>
:<math> \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}. </math>
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 α<sub>''k''</sub> koefficienseket.
===A konjugált gradiens módszer, mint iterációs módszer===
Ha megfelelően választjuk meg '''p'''<sub>''k''</sub>-t, nincs szükség az összes koefficiens kiszámítására, hogy jó közelítéssel megadjuk '''x'''<sub>*</sub>-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'''<sub>*</sub> első közelítését jelöljük '''x'''<sub>0</sub>–lal. Tegyük fel, hogy '''x'''<sub>0</sub> = 0. Az '''x'''<sub>0</sub>-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'''<sub>*</sub>-hoz. A mutató onnan adódik, hogy '''x'''<sub>*</sub> szintén egy négyzetes függvény minimum helye, vagyis ha f(x) egyre kisebb, akkor egyre közelebb jutunk '''x'''<sub>*</sub> értékéhez:
:<math> 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. </math>
Ez a képlet sugallja, hogy a '''p'''<sub>1</sub> bázisvektor az f függvény gradiense az '''x''' = '''x'''<sub>0</sub> helyen, és '''p'''<sub>1</sub> egyenlő '''Ax'''<sub>0</sub>−'''b'''. Ha '''x'''<sub>0</sub> = '''0''', akkor '''p'''<sub>1</sub> = '''−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'''<sub>''k''</sub> a k-adik lépés maradéka:
:<math> \mathbf{r}_k = \mathbf{b} - \mathbf{Ax}_k. \, </math>
Mivel '''r'''<sub>''k''</sub> az f függvény negatív garadiense az '''x''' = '''x'''<sub>''k''</sub> helyen, ezért a gradiens módszer abból állna, hogy módosítsa '''r'''<sub>''k''</sub> irányát. Itt feltesszük, hogy '''p'''<sub>''k''</sub> irányai egymás konjugáltjai, így azt az irányt válassztjuk, amely legközelebb esik '''r'''<sub>''k''</sub> –hoz. Ez a következő kifejezéshez vezet:
:<math> \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 </math>
===A megoldó algoritmus===
Néhány egyszerűsítés, a következő algoritmusra vezet '''Ax''' = '''b''' megoldásában. A kezdő '''x'''<sub>0</sub> vektor lehet egy megoldáshoz közeli szám, avagy nulla.
:<math>\mathbf{r}_0 := \mathbf{b} - \mathbf{A x}_0 \,</math>
:<math>\mathbf{p}_0 := \mathbf{r}_0 \,</math>
:<math>k := 0 \, </math>
:'''repeat'''
::<math>\alpha_k := \frac{\mathbf{r}_k^{\mathrm{T}} \mathbf{r}_k}{\mathbf{p}_k^{\mathrm{T}} \mathbf{A p}_k} \, </math>
::<math>\mathbf{x}_{k+1} := \mathbf{x}_k + \alpha_k \mathbf{p}_k \, </math>
::<math>\mathbf{r}_{k+1} := \mathbf{r}_k - \alpha_k \mathbf{A p}_k \, </math>
::'''if''' '''r'''<sub>''k''+1</sub> is sufficiently small '''then''' exit loop '''end if'''
::<math>\beta_k := \frac{\mathbf{r}_{k+1}^{\mathrm{T}} \mathbf{r}_{k+1}}{\mathbf{r}_k^{\mathrm{T}} \mathbf{r}_k} \, </math>
::<math>\mathbf{p}_{k+1} := \mathbf{r}_{k+1} + \beta_k \mathbf{p}_k \, </math>
::<math>k := k + 1 \, </math>
:'''end repeat'''
:The result is '''x'''<sub>''k''+1</sub>
===Példa kód a konjugált gradiens módszerre [[GNU Octave|Octave]] programnyelvben===
<source lang="matlab">
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
</source>
===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:
:<math>\mathbf{r}_0 := \mathbf{b} - \mathbf{A x}_0</math>
:<math>\mathbf{z}_0 := \mathbf{M}^{-1} \mathbf{r}_0</math>
:<math>\mathbf{p}_0 := \mathbf{z}_0</math>
:<math>k := 0 \, </math>
:'''repeat'''
::<math>\alpha_k := \frac{\mathbf{r}_k^{\mathrm{T}} \mathbf{z}_k}{\mathbf{p}_k^{\mathrm{T}} \mathbf{A p}_k}</math>
::<math>\mathbf{x}_{k+1} := \mathbf{x}_k + \alpha_k \mathbf{p}_k</math>
::<math>\mathbf{r}_{k+1} := \mathbf{r}_k - \alpha_k \mathbf{A p}_k</math>
::'''if''' '''r'''<sub>''k''+1</sub> is sufficiently small '''then''' exit loop '''end if'''
::<math>\mathbf{z}_{k+1} := \mathbf{M}^{-1} \mathbf{r}_{k+1}</math>
::<math>\beta_k := \frac{\mathbf{r}_{k+1}^{\mathrm{T}} \mathbf{z}_{k+1}}{\mathbf{r}_k^{\mathrm{T}} \mathbf{z}_k}</math>
::<math>\mathbf{p}_{k+1} := \mathbf{z}_{k+1} + \beta_k \mathbf{p}_k</math>
::<math>k := k + 1 \, </math>
:'''end repeat'''
:The result is '''x'''<sub>''k''+1</sub>
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:
:<math>\mathbf{E}^{-1}\mathbf{A}\mathbf{E}^{-\mathrm{T}}\mathbf{\hat{x}}=\mathbf{E}^{-1}\mathbf{b}</math>,
ahol
:<math>\mathbf{EE}^{\mathrm{T}}=\mathbf{M}</math>
:<math>\mathbf{\hat{x}}=\mathbf{E}^{\mathrm{T}}\mathbf{x}</math>
==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
*{{cite journal|last = Hestenes|first = Magnus R.|coauthors = Stiefel, Eduard|title = Methods of Conjugate Gradients for Solving Linear Systems|journal = Journal of Research of the National Bureau of Standards|volume = 49|issue = 6|month = December | year = 1952|url = http://nvl.nist.gov/pub/nistpubs/jres/049/6/V49.N06.A08.pdf|format=PDF}}
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.
| |||
