Szimmetrikus, pozitív definit mátrixú lineáris egyenletrendszerek megoldására alkalmas

$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\)

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

\(\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

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}}\)

2. ITERÁLT KÖZELÍTŐ MEGOLDÁS
   \(x_{k+1} = x_k + \alpha_k s_k\)

4.SEGÉDVÁLTOZÓ
\(\beta_{k+1}=\left(r_{k+1}^{T} r_{k+1}\right) /\left(r_{k}^{T} r_{k}\right)\)

5. ÚJ KERESÉSI IRÁNY
   \(s_{k+1} = r_{k+1} + \beta_{k+1}s_k\)