Bikonjugeret gradientmetode

Biconjugate gradient method ( BiCG ) er en iterativ numerisk metode til at løse Krylov - type SLAE'er . Det er en generalisering af den konjugerede gradientmetode .

Udtalelse af problemet

Lad et system af lineære algebraiske ligninger af formen være givet :. I modsætning til MSH er matrixen ikke underlagt den selvadjoinerende betingelse, det vil sige, at det er muligt at . For en rigtig matrix betyder det, at matrixen muligvis ikke er symmetrisk. $økse = b$ $A \ne A^*$

Algoritme for rigtige matricer

Forberedelse før den iterative proces

Vi vælger en indledende tilnærmelse $x^0$
$r^0 = b - Ax^0$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

-te iteration af 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 for at stoppe den iterative proces

Stoppet kan forekomme i henhold til antallet af iterationer, ifølge uoverensstemmelsen, ifølge forskellen i tilnærmelser og så videre. Da metoden er ustabil, bør antallet af iterationer yderligere begrænses ovenfra, når den bruges.

Algoritme for et forudkonditioneret system

Lad et forudkonditioneret system blive givet $M^{-1}AP^{-1}x = M^{-1}b$

Forberedelse før den iterative proces

Vi vælger en indledende tilnærmelse $x^0$
$\widetilde{x}^0 = P^{-1}x^0$
$r^0 = M^{-1}\venstre( b - A \widetilde{x}^0 \right)$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

-th metode iteration

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

$x^* = P \widetilde{x}^m$ , hvor er den omtrentlige løsning af systemet, er løsningen af det prækonditionerede system ved den sidste iteration. $x^{*}$ $\widetilde{x}^m$

Kriterium for at stoppe den iterative proces

Funktioner og ændringer af metoden

BiCG er en ustabil [1] metode, så den bruges sjældent til at løse reelle problemer. Oftere bruges dens modifikation [3] - den stabiliserede metode til bikonjugatgradienter .

Noter

↑ 1 2 Henk A. van der Vorst. Iterative Krylov-metoder for stort lineært system. - Cambridge University Press, 2003. - 221 s. — ISBN 9780521818285 .
↑ $P^{-T} = (P^{-1})^T$
↑ T. Huttunen, M. Malinen, P. Munk. Løsning af Maxwells ligninger ved hjælp af ultrasvag variationsformulering . – 2006.

Metoder til løsning af SLAE
Direkte metoder	Matrix metode Gauss metode Gauss-Jordan metode Cramer metode LU nedbrydning Kolesky nedbrydning Feje metode
Iterative metoder	Jacobi metode Gauss-Seidel metode Iterationsmetode Afslapningsmetode Konjugeret gradientmetode Bikonjugeret gradientmetode Stabiliseret bikonjugat gradientmetode
Generel	omvendt matrix Projektionsmetoder til løsning af SLAE Forkonditionering