Metoda gradientului biconjugat

Metoda gradientului biconjugat ( BiCG ) este o metodă numerică iterativă pentru rezolvarea SLAE-urilor de tip Krylov . Este o generalizare a metodei gradientului conjugat .

Enunțul problemei

Să fie dat un sistem de ecuații algebrice liniare de forma: . Spre deosebire de MSH, matricea nu este supusă condiției auto-adjuncte, adică este posibil ca . Pentru o matrice reală, aceasta înseamnă că matricea poate să nu fie simetrică. $ax = b$ $A \ne A^*$

Algoritm pentru matrici reale

Pregătirea înaintea procesului iterativ

Alegem o aproximare inițială $x^0$
$r^0 = b - Ax^0$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

-a iterație a metodei [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}$

Criteriu pentru oprirea procesului iterativ

Oprirea poate apărea în funcție de numărul de iterații, în funcție de discrepanță, în funcție de diferența de aproximări și așa mai departe. Deoarece metoda este instabilă, atunci când o utilizați, numărul de iterații ar trebui limitat suplimentar de sus.

Algoritm pentru un sistem precondiționat

Să fie dat un sistem precondiționat $M^{-1}AP^{-1}x = M^{-1}b$

Pregătirea înaintea procesului iterativ

Alegem o aproximare inițială $x^0$
$\widetilde{x}^0 = P^{-1}x^0$
$r^0 = M^{-1}\left( b - A \widetilde{x}^0 \right)$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

-a iterație a metodei

$\alpha_k = \frac{(p^{k-1}, r^{k-1})}{(s^{k-1}, M^{-1}AP^{-1}z^{k -unu})}$
$\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}$

După procesul iterativ

$x^* = P \widetilde{x}^m$ , unde este soluția aproximativă a sistemului, este soluția sistemului precondiționat la ultima iterație. $x^{*}$ $\widetilde{x}^m$

Criteriu pentru oprirea procesului iterativ

Caracteristici și modificări ale metodei

BiCG este o metodă instabilă [1] , deci este rar folosită pentru a rezolva probleme reale. Mai des, se folosește modificarea sa [3] - metoda stabilizată a gradienților biconjugați .

Note

↑ 1 2 Henk A. van der Vorst. Metode Krylov iterative pentru sisteme liniare mari. - Cambridge University Press, 2003. - 221 p. — ISBN 9780521818285 .
↑ $P^{-T} = (P^{-1})^T$
↑ T. Huttunen, M. Malinen, P. Monk. Rezolvarea ecuațiilor lui Maxwell folosind formularea variațională ultra slabă . — 2006.

Metode de rezolvare a SLAE
Metode directe	Metoda matricei metoda Gauss Metoda Gauss-Iordan Metoda Cramer descompunerea LU Descompunerea Cholesky Metoda de măturare
Metode iterative	metoda Jacobi Metoda Gauss-Seidel Metoda iterației Metoda de relaxare Metoda gradientului conjugat Metoda gradientului biconjugat Metoda gradientului biconjugat stabilizat
General	matrice inversă Metode de proiecție pentru rezolvarea SLAE Precondiționare