Please enable JavaScript.
Coggle requires JavaScript to display documents.
KONJUGÁLT GRADIENS MÓDSZER - Coggle Diagram
KONJUGÁLT GRADIENS MÓDSZER
Szimmetrikus, pozitív definit mátrixú lineáris egyenletrendszerek megoldására alkalmas
Pontos aritmetikával véges sok lépésben megtalálná a megoldást, kerekítsi hibák miatt ITERÁCIÓS ELJÁRÁSNAK kell tenkinteni
\( q(x) = \frac{1}{2} x^T Ax − x^T b \)
FELTÉTEL:
A: szimmetrikus pozitív definit mátrix
KÖVETKEZTETÉS:
\(x^*\): egyetlen minimum pontja van
EMIATT TELJESÜL:
\(Ax^* = b\)
Más szóval a \(q(x)\) minimumpontjának meghatározása ekvivalens az \(Ax^* = b\) lineáris egyenletrendszer megoldásával.
Többdimenziós optimalizálási eljárás
Új közelítő megoldást, mint általában itt is az
\(x_{k+1} = x_k + \alpha s_k\)
alakban keressük, ahol
\(s_k\): keresési irány
\(\alpha \): lépésköz
Kvadratikus függvények optimalizálása:
reziduális vektor:
\(-\nabla q(x) = b - Ax = r\)
Negatív gradiens iránya kedvező az optimalizálási feladatokhoz
Gradiens:Függvény első deriváltja amivel ellentétes irányba haladva a célfüggvény értéke csökken
\(\alpha\) lépésközt közvetlenül meg tudjuk adni. A keresési irány mentén ott lesz a célfüggvény értéke minimális, ahol az új reziduális vektor merőleges \(s_k\) ra
\(0=\frac{\mathrm{d}}{\mathrm{d} \alpha} q\left(x_{k+1}\right)=\nabla q\left(x_{k+1}\right)^{T} \frac{\mathrm{d}}{\mathrm{d} \alpha} x_{k+1}=\left(A x_{k+1}-b\right)^{T}\left(\frac{\mathrm{d}}{\mathrm{d} \alpha}\left(x_{k}+\alpha s_{k}\right)\right)=-r_{k+1}^{T} s_{k}\)
Az új reziduális vektort ki lehet fejezni a régivel és a keresési iránnyal
\(r_{k+1}=b-A x_{k+1}=b-A\left(x_{k}+\alpha s_{k}\right)=\left(b-A x_{k}\right)-\alpha A s_{k}=r_{k}-\alpha A s_{k}\)
Ezt behelyettesítve az \(r_{k+1}\) helyére, alfára rendezve megkaphatjuk a lépésközt
1 more item...
KONJUGÁLT GRADIENS MÓDSZER LÉPÉSEI
1.LÉPÉSHOSSZ MEGHATÁROZÁSA
\(\alpha=\frac{r_{k}^{T} r_{k}}{s_{k}^{T} A s_{k}}\)
ITERÁLT KÖZELÍTŐ MEGOLDÁS
\(x_{k+1} = x_k + \alpha_k s_k\)
3.ÚJ REZIDUÁLIS VEKTOR
\(r_{k+1} = r_k - \alpha As_k\)
4.SEGÉDVÁLTOZÓ
\(\beta_{k+1}=\left(r_{k+1}^{T} r_{k+1}\right) /\left(r_{k}^{T} r_{k}\right)\)
ÚJ KERESÉSI IRÁNY
\(s_{k+1} = r_{k+1} + \beta_{k+1}s_k\)
MEGÁLLÁSI FELTÉTEL:
Utolsó néhány iterált közelítés eltérése, és a lineáris egyenletrendszer két oldalának különbsége normája egy adott kis pozitív értékek alatt marad
\(x_0\) indulópontra:
\(s_0 = r_0 = b - Ax_0\)