Metoda konjugovaného gradientu (pro roztok SLAE)

Metoda konjugovaného gradientu je numerická metoda pro řešení soustav lineárních algebraických rovnic , je iterativní metodou Krylovova typu .

Prohlášení o problému

Nechť je dána soustava lineárních rovnic: . Matice systému je navíc reálná matice , která má následující vlastnosti: , to znamená, že je symetrickou kladně-definitivní maticí . Potom lze proces řešení SLAE reprezentovat jako minimalizaci následující funkcionality: $sekera = b$ $A = A^T > 0$

$(Ax,x)-2(b,x)\rightarrow min$

Za ním je skalární součin . Minimalizací tohoto funkcionálu pomocí Krylovových podprostorů získáme algoritmus metody konjugovaného gradientu. $(\cdot, \cdot)$

Algoritmus

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

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

k

-th iterace metody [1]

$\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(Az^{k-1}, z^{k-1})}$
$x^k = x^{k-1} + \alpha_k z^{k-1}$
$r^k = r^{k-1} - \alpha_k A z^{k-1}$
$\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$

Kritéria zastavení

Protože funkcionál, který má být minimalizován, je kvadratický, musí proces dát odpověď na iteraci, avšak při implementaci metody na počítači dochází k chybě v reprezentaci reálných čísel, v důsledku čehož může být provedeno více iterací. Požadované. Můžete také vyhodnotit přesnost pomocí relativní nesrovnalosti a zastavit iterační proces, když nesrovnalost klesne pod dané číslo. $n$ $\frac{||r^k||}{||b||}$

Algoritmus pro předpřipravený systém

Nechť má předupravený systém tvar: , pak algoritmus metody pro takový systém může být zapsán následovně: $SAQx=Sb$

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

Zvolíme počáteční aproximaci $x^0$
$r^0 = Q(b – SAx^0)$
$z^0 = r^0$
$\widetilde{x}^0 = Qx^0$

k

- iterace metody

$\alpha_k = \frac{(r^{k-1}, r^{k-1})}{(SAQz^{k-1}, z^{k-1})}$
$\widetilde{x}^k = \widetilde{x}^{k-1} + \alpha_k z^{k-1}$
$r^k = r^{k-1} - \alpha_k SAQ z^{k-1}$
$\beta_k = \frac{(r^k, r^k)}{(r^{k-1}, r^{k-1})}$
$z^k = r^k + \beta_k z^{k-1}$

Po iteračním procesu

$x^* = Q^{-1} \widetilde{x}^m$ , kde je přibližné řešení systému, je celkový počet iterací metody. $x^{*}$ $m$

Kritéria zastavení

V tomto případě můžete použít stejná kritéria zastavení jako u konvenčního systému, pouze se zohledněním předběžné úpravy. Relativní nesrovnalost se například vypočítá jako: , můžete však použít i nesoulad původního systému, který se vypočítá následovně: $\frac{||\widetilde{r}^k||}{||Sb||}$ $\frac{||r^k||}{||b||} = \frac{||Q^{-1}\widetilde{r}^k||}{||b||}$

Vlastnosti a zobecnění

Stejně jako všechny metody na Krylovových podprostorech vyžaduje metoda konjugovaného gradientu z matice pouze schopnost ji vynásobit vektorem, což vede k možnosti používat speciální formáty ukládání matic (např. řídké) a šetřit paměť pro ukládání matic.
Metoda se často používá k řešení SLAE konečných prvků .
Metoda má zobecnění: metoda bikonjugovaných gradientů pro práci s nesymetrickými maticemi. A metoda komplexně konjugovaného gradientu, kde matice může obsahovat komplexní čísla, ale musí splňovat podmínku: tj. být samoadjungovanou kladně definitní maticí. $A$ $A = A^* > 0$

Poznámky

↑ Henk A. van der Vorst. Iterativní Krylovovy metody pro velký lineární systém. - Cambridge University Press, 2003. - 221 s. — ISBN 9780521818285 .

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