Bikonjugált gradiens módszer

A bikonjugált gradiens módszer ( BiCG ) egy iteratív numerikus módszer Krylov - típusú SLAE -ek megoldására . Ez a konjugált gradiens módszer általánosítása .

A probléma leírása

Legyen adott alakú lineáris algebrai egyenletrendszer: . Az MSH-val ellentétben a mátrixra nem vonatkozik az önadjungált feltétel, vagyis lehetséges, hogy . Valós mátrix esetén ez azt jelenti, hogy a mátrix nem feltétlenül szimmetrikus. $ax = b$ $A \ne A^*$

Algoritmus valós mátrixokhoz

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

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

k

-a módszer iterációja [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}$

Az iteratív folyamat leállításának kritériuma

A megállás történhet az iterációk száma szerint, az eltérés szerint, a közelítések különbsége szerint stb. Mivel a módszer instabil, használatakor az iterációk számát felülről is korlátozni kell.

Algoritmus egy előfeltételes rendszerhez

Adjunk meg egy előfeltételezett rendszert $M^{-1}AP^{-1}x = M^{-1}b$

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

Kezdő közelítést választunk $x^0$
$\widetilde{x}^0 = P^{-1}x^0$
$r^0 = M^{-1}\left(b - A \widetilde{x}^0 \jobb)$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

-adik módszer iterációja

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

Az iteratív folyamat után

$x^* = P \widetilde{x}^m$ , ahol a rendszer közelítő megoldása, az előfeltételezett rendszer megoldása az utolsó iterációban. $x^{*}$ $\widetilde{x}^m$

Az iteratív folyamat leállításának kritériuma

A módszer jellemzői és módosításai

A BiCG instabil [1] módszer, ezért ritkán használják valós problémák megoldására. Gyakrabban a módosítását használják [3] - a bikonjugált gradiensek stabilizált módszere .

Jegyzetek

↑ 1 2 Henk A. van der Vorst. Iteratív Krylov-módszerek nagy lineáris rendszerekhez. - Cambridge University Press, 2003. - 221 p. — ISBN 9780521818285 .
↑ $P^{-T} = (P^{-1})^T$
↑ T. Huttunen, M. Malinen, P. Monk. Maxwell - egyenletek megoldása ultragyenge variációs formulával . – 2006.

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