Bikonjugaattigradienttimenetelmä

Bikonjugaattigradienttimenetelmä ( BiCG ) on iteratiivinen numeerinen menetelmä Krylov - tyyppisten SLAE :iden ratkaisemiseksi . Se on konjugaattigradienttimenetelmän yleistys .

Ongelman selvitys

Olkoon muotoinen lineaaristen algebrallisten yhtälöiden järjestelmä: . Toisin kuin MSH, matriisiin ei sovelleta itseliitosehtoa, eli on mahdollista, että . Todelliselle matriisille tämä tarkoittaa, että matriisi ei ehkä ole symmetrinen. $kirves = b$ $A \ne A^*$

Algoritmi reaalimatriiseille

Valmistelu ennen iteratiivista prosessia

Valitsemme alustavan likiarvon $x^0$
$r^0 = b - Ax^0$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

- menetelmän iteraatio [1]

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

Iteratiivisen prosessin pysäyttämisen kriteeri

Pysäytys voi tapahtua iteraatioiden lukumäärän, poikkeaman, approksimaatioiden eron ja niin edelleen mukaan. Koska menetelmä on epävakaa, sitä käytettäessä iteraatioiden määrää tulee lisäksi rajoittaa ylhäältä.

Esiehdotetun järjestelmän algoritmi

Annetaan esiehdollinen järjestelmä $M^{-1}AP^{-1}x = M^{-1}b$

Valmistelu ennen iteratiivista prosessia

Valitsemme alustavan likiarvon $x^0$
$\widetilde{x}^0 = P^{-1}x^0$
$r^0 = M^{-1}\vasen(b - A \widetilde{x}^0 \oikea)$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

-th menetelmä iteraatio

$\alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, M^{-1}AP^{-1}z^{k -yksi})}$
$\widetilde{x}^k = \widetilde{x}^{k-1} +\alpha_k z^{k-1}$
$r^{k} = r^{k-1} - \alpha_k M^{-1}AP^{-1}z^{k-1}$
$p^k = p^{k-1} - \alpha_k P^{-T} A^TM^{-T} s^{k-1}$ [2]
$\beta_k = \frac{(p^k, r^k)}{(p^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$
$s^k = p^k + \beta_k s^{k-1}$

Iteratiivisen prosessin jälkeen

$x^* = P \widetilde{x}^m$ , jossa on järjestelmän likimääräinen ratkaisu, on esiehdotetun järjestelmän ratkaisu viimeisessä iteraatiossa. $x^{*}$ $\widetilde{x}^m$

Iteratiivisen prosessin pysäyttämisen kriteeri

Menetelmän ominaisuudet ja muutokset

BiCG on epävakaa [1] menetelmä, joten sitä käytetään harvoin todellisten ongelmien ratkaisemiseen. Useammin käytetään sen modifikaatiota [3] - bikonjugaattigradienttien stabiloitua menetelmää .

Muistiinpanot

↑ 1 2 Henk A. van der Vorst. Iteratiiviset Krylov-menetelmät suurelle lineaariselle järjestelmälle. - Cambridge University Press, 2003. - 221 s. — ISBN 9780521818285 .
↑ $P^{-T} = (P^{-1})^T$
↑ T. Huttunen, M. Malinen, P. Monk. Maxwellin yhtälöiden ratkaiseminen ultraheikosta variaatioformulaatiolla . – 2006.

Menetelmät SLAE :n ratkaisemiseksi
Suorat menetelmät	Matriisimenetelmä Gaussin menetelmä Gauss-Jordan menetelmä Cramer menetelmä LU:n hajoaminen Cholesky-hajoaminen Lakaisumenetelmä
Iteratiiviset menetelmät	Jacobin menetelmä Gauss-Seidelin menetelmä Iterointimenetelmä Rentoutumismenetelmä Konjugaattigradienttimenetelmä Bikonjugaattigradienttimenetelmä Stabiloitu bikonjugaattigradienttimenetelmä
Kenraali	käänteinen matriisi Projektiomenetelmät SLAE:n ratkaisemiseen Esikäsittely