Bikonjugerad gradientmetod

Biconjugate gradient method ( BiCG ) är en iterativ numerisk metod för att lösa SLAE av Krylov - typ . Det är en generalisering av den konjugerade gradientmetoden .

Förklaring av problemet

Låt ett system av linjära algebraiska ekvationer av formen ges: . I motsats till MSH är matrisen inte föremål för det självanslutna villkoret, det vill säga det är möjligt att . För en riktig matris betyder det att matrisen kanske inte är symmetrisk. $yxa = b$ $A \ne A^*$

Algoritm för riktiga matriser

Förberedelse inför den iterativa processen

Vi väljer en initial uppskattning $x^0$
$r^0 = b - Ax^0$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

-te iterationen av metoden [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}$

Kriterium för att stoppa den iterativa processen

Stoppet kan ske enligt antalet iterationer, enligt avvikelsen, enligt skillnaden i approximationer och så vidare. Eftersom metoden är instabil bör antalet iterationer dessutom begränsas ovanifrån när den används.

Algoritm för ett förkonditionerat system

Låt ett förkonditionerat system ges $M^{-1}AP^{-1}x = M^{-1}b$

Förberedelse inför den iterativa processen

Vi väljer en initial uppskattning $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

-th metoden iteration

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

Efter den iterativa processen

$x^* = P \widetilde{x}^m$ , där är den ungefärliga lösningen av systemet, är lösningen av det förkonditionerade systemet vid den senaste iterationen. $x^{*}$ $\widetilde{x}^m$

Kriterium för att stoppa den iterativa processen

Funktioner och modifieringar av metoden

BiCG är en instabil [1] metod, så den används sällan för att lösa verkliga problem. Oftare används dess modifiering [3] - den stabiliserade metoden för bikonjugatgradienter .

Anteckningar

↑ 1 2 Henk A. van der Vorst. Iterativa Krylov-metoder för stora linjära system. - Cambridge University Press, 2003. - 221 sid. — ISBN 9780521818285 .
↑ $P^{-T} = (P^{-1})^T$
↑ T. Huttunen, M. Malinen, P. Monk. Lösa Maxwells ekvationer med hjälp av ultrasvag variationsformulering . – 2006.

Metoder för att lösa SLAE
Direkta metoder	Matrismetod Gauss metod Gauss-Jordan-metoden Cramer metod LU-nedbrytning Cholesky nedbrytning Sopa metod
Iterativa metoder	Jacobi metod Gauss-Seidel-metoden Iterationsmetod Avslappningsmetod Konjugerad gradientmetod Bikonjugerad gradientmetod Stabiliserad bikonjugatgradientmetod
Allmän	invers matris Projektionsmetoder för att lösa SLAE Förkonditionering