Metoda bikonjugovaného gradientu

Metoda bikonjugovaného gradientu ( BiCG ) je iterativní numerická metoda pro řešení SLAE Krylovova typu . Jde o zobecnění metody konjugovaného gradientu .

Prohlášení o problému

Nechť je dána soustava lineárních algebraických rovnic tvaru: . Na rozdíl od MSH matice nepodléhá samoadjungované podmínce, to znamená, že je možné, že . Pro skutečnou matici to znamená, že matice nemusí být symetrická. $sekera = b$ $A \ne A^*$

Algoritmus pro reálné matice

Příprava před iteračním procesem

Zvolíme počáteční aproximaci $x^0$
$r^0 = b - Ax^0$
$p^0 = r^0$
$z^0 = r^0$
$s^0 = r^0$

k

-th iterace metody [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}$

Kritérium pro zastavení iteračního procesu

Zastavení může nastat podle počtu iterací, podle nesouladu, podle rozdílu v aproximacích a tak dále. Vzhledem k tomu, že metoda je nestabilní, při jejím použití by měl být počet iterací navíc shora omezen.

Algoritmus pro předpřipravený systém

Nechť je dán předem připravený systém $M^{-1}AP^{-1}x = M^{-1}b$

Příprava před iteračním procesem

Zvolíme počáteční aproximaci $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

- iterace metody

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

Po iteračním procesu

$x^* = P \widetilde{x}^m$ , kde je přibližné řešení systému, je řešení předupraveného systému při poslední iteraci. $x^{*}$ $\widetilde{x}^m$

Kritérium pro zastavení iteračního procesu

Vlastnosti a modifikace metody

BiCG je nestabilní [1] metoda, proto se k řešení skutečných problémů používá jen zřídka. Častěji se používá její modifikace [3] - stabilizovaná metoda bikonjugovaných gradientů .

Poznámky

↑ 1 2 Henk A. van der Vorst. Iterativní Krylovovy metody pro velký lineární systém. - Cambridge University Press, 2003. - 221 s. — ISBN 9780521818285 .
↑ $P^{-T} = (P^{-1})^T$
↑ T. Huttunen, M. Malinen, P. Monk. Řešení Maxwellových rovnic pomocí ultra slabé variační formulace . — 2006.

Metody řešení SLAE
Přímé metody	Maticová metoda Gaussova metoda Gauss-Jordanova metoda Cramerova metoda LU rozklad Choleský rozklad Metoda zametání
Iterační metody	Jacobiho metoda Gauss-Seidelova metoda Iterační metoda Relaxační metoda Metoda konjugovaného gradientu Metoda bikonjugovaného gradientu Metoda stabilizovaného bikonjugátového gradientu
Všeobecné	inverzní matice Projekční metody pro řešení SLAE Předběžná úprava