Metoda konjugovaného gradientu je numerická metoda pro řešení soustav lineárních algebraických rovnic , je iterativní metodou Krylovova typu .
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:
Za ním je skalární součin . Minimalizací tohoto funkcionálu pomocí Krylovových podprostorů získáme algoritmus metody konjugovaného gradientu.
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.
Nechť má předupravený systém tvar: , pak algoritmus metody pro takový systém může být zapsán následovně:
Příprava před iteračním procesemV 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ě:
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í.
SLAE | Metody řešení|
---|---|
Přímé metody | |
Iterační metody | |
Všeobecné |