Konjugált gradiens módszer (SLAE oldathoz)

A konjugált gradiens módszer egy numerikus módszer lineáris algebrai egyenletrendszerek megoldására , egy Krylov típusú iteratív módszer .

A probléma leírása

Legyen adott a lineáris egyenletrendszer: . Ráadásul a rendszer mátrixa egy valós mátrix , amelynek a következő tulajdonságai vannak: , azaz szimmetrikus pozitív-definit mátrix . Ekkor az SLAE megoldásának folyamata a következő funkciók minimalizálásaként ábrázolható: $ax = b$ $A = A^T > 0$

${\megjelenítési stílus (Ax,x)-2(b,x)\jobbra nyíl min}$

Mögötte a skalárszorzat található . Ezt a függvényt a Krylov-alterek használatával minimalizálva megkapjuk a konjugált gradiens módszer algoritmusát. $(\cdot, \cdot)$

Algoritmus

Felkészülés az iteratív folyamat előtt

Kezdő közelítést választunk $x^0$
$r^0 = b - Ax^0$
$z^0 = r^0$

k

-a módszer iterációja [1]

$\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(Az^{k-1}, z^{k-1})}$
$x^k = x^{k-1} + \alpha_k z^{k-1}$
$r^k = r^{k-1} - \alpha_k A z^{k-1}$
$\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$

Stop Criteria

Mivel a minimalizálandó függvény másodfokú, ezért a folyamatnak az iterációra kell választ adnia, azonban a metódus számítógépen való implementálásakor hiba lép fel a valós számok ábrázolásában, aminek következtében több iteráció is előfordulhat. kívánt. Kiértékelheti a pontosságot a relatív eltéréssel is , és leállíthatja az iteratív folyamatot, ha az eltérés kisebb lesz egy adott számnál. $n$ $\frac{||r^k||}{||b||}$

Algoritmus egy előfeltételes rendszerhez

Legyen az előfeltételezett rendszer alakja: , akkor egy ilyen rendszerre vonatkozó metódus algoritmusa a következőképpen írható fel: $SAQx=Sb$

Felkészülés az iteratív folyamat előtt

Kezdő közelítést választunk $x^0$
$r^0 = Q(b - SAx^0)$
$z^0 = r^0$
$\widetilde{x}^0 = Qx^0$

k

-adik módszer iterációja

$\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(SAQz^{k-1}, z^{k-1})}$
$\widetilde{x}^k = \widetilde{x}^{k-1} + \alpha_k z^{k-1}$
$r^k = r^{k-1} - \alpha_k SAQ z^{k-1}$
$\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$

Az iteratív folyamat után

$x^* = Q^{-1} \widetilde{x}^m$ , ahol a rendszer közelítő megoldása, a módszer iterációinak teljes száma. $x^{*}$ $m$

Stop Criteria

Ebben az esetben ugyanazokat a leállási feltételeket használhatja, mint a hagyományos rendszereknél, csak az előkondicionálás figyelembevételével. Például a relatív eltérés kiszámítása a következőképpen történik: , azonban használhatja az eredeti rendszer eltérését is, amely a következőképpen kerül kiszámításra: $\frac{||\widetilde{r}^k||}{||Sb||}$ $\frac{||r^k||}{||b||} = \frac{||Q^{-1}\widetilde{r}^k||}{||b||}$

Jellemzők és általánosítások

A Krylov-altereken alkalmazott összes módszerhez hasonlóan a mátrixból származó konjugált gradiens módszernek csak a vektorral való szorzásának képességére van szükség, ami speciális mátrixtárolási formátumok (például ritka) használatához és memóriamegtakarításhoz vezet a mátrixtároláshoz.
A módszert gyakran használják végeselemes SLAE-ek megoldására.
A módszernek vannak általánosításai: a bikonjugált gradiensek módszere , nem szimmetrikus mátrixokkal való munkavégzéshez. És a komplex konjugált gradiens módszer, ahol a mátrix tartalmazhat komplex számokat, de teljesítenie kell a feltételt: , azaz önadjungált pozitív határozott mátrixnak kell lennie. $A$ $A = A^* > 0$

Jegyzetek

↑ Henk A. van der Vorst. Iteratív Krylov-módszerek nagy lineáris rendszerekhez. - Cambridge University Press, 2003. - 221 p. — ISBN 9780521818285 .

Az SLAE megoldásának módszerei
Közvetlen módszerek	Mátrix módszer Gauss módszer Gauss-Jordan módszer Cramer módszer LU bomlás Cholesky-bomlás Sweep módszer
Iteratív módszerek	Jacobi módszer Gauss-Seidel módszer Iterációs módszer Relaxációs módszer Konjugált gradiens módszer Bikonjugált gradiens módszer Stabilizált bikonjugátum gradiens módszer
Tábornok	inverz mátrix Vetítési módszerek SLAE megoldására Előkondicionálás