V případě soustavy lineárních rovnic existují dvě hlavní třídy iteračních metod: stacionární iterační metody a obecnější metody Krylovových podprostorů.
Stacionární iterační metodyEdit
ÚvodEdit
Stacionární iterační metody řeší lineární soustavu operátorem aproximujícím původní soustavu; a na základě měření chyby ve výsledku (rezidua) tvoří „korekční rovnici“, pro kterou se tento proces opakuje. Ačkoli jsou tyto metody jednoduché na odvození, implementaci a analýzu, konvergence je zaručena pouze pro omezenou třídu matic.
DefiniceEdit
Iterativní metoda je definována vztahem
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
a pro daný lineární systém A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
s přesným řešením x ∗ {\displaystyle \mathbf {x} ^{*}}
chybu pomocí e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}
Iterativní metoda se nazývá lineární, jestliže existuje matice C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}}.
taková, že e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0}
a tato matice se nazývá iterační matice. iterační metoda s danou iterační maticí C {\displaystyle C}
se nazývá konvergentní, jestliže platí následující lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}
Důležitá věta říká, že pro danou iterační metodu a její iterační matici C {\displaystyle C}
je konvergentní tehdy a jen tehdy, když je její spektrální poloměr ρ ( C ) {\displaystyle \rho (C)}
je menší než jednotka, to znamená, že ρ ( C ) < 1 . {\displaystyle \rho (C)<1\,.}
Základní iterační metody pracují tak, že rozdělí matici A {\displaystyle A}
na A = M – N {\displaystyle A=M-N}.
a zde matici M {\displaystyle M}
by měla být snadno invertibilní. iterační metody jsou nyní definovány jako M x k + 1 = N x k + b , k ≥ 0 . {\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.}
Z toho vyplývá, že iterační matice je dána vztahem
C = I – M – 1 A = M – 1 N. {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
PříkladyEdit
Základní příklady stacionárních iteračních metod používají rozdělení matice A {\displaystyle A}.
jako A = D + L + U , D := diag ( ( a i i ) i ) {\displaystyle A=D+L+U\,,\kvadrát D:={\text{diag}}((a_{ii})_{i})}
kde D {\displaystyle D}
je pouze diagonální část A {\displaystyle A}
, a L {\displaystyle L}
je striktní dolní trojúhelníková část A {\displaystyle A}.
. respektive U {\displaystyle U}.
je přísná horní trojúhelníková část A {\displaystyle A}
.
- Richardsonova metoda: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}
- Jacobiho metoda: M := D {\displayystyle M:=D}
- Tlumená Jacobiho metoda: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}
- Gaussova-Seidelova metoda: M := D + L {\displaystyle M:=D+L}
- Postupná nadrelaxační metoda (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}
- Symetrická postupná nadrelaxace (SSOR): M := 1 ω ( 2 – ω ) ( D + ω L ) D – 1 ( D + ω U ) ( ω ≠ { 0 , 2 } ) {\displaystyle M:={\frac {1}{\omega (2-\omega )}}(D+\omega L)D^{-1}(D+\omega U)\quad (\omega \neq \{0,2\})}
Lineární stacionární iterační metody se také nazývají relaxační metody.
Metody Krylovova podprostoruRedakce
Metody Krylovova podprostoru pracují tak, že tvoří bázi posloupnosti po sobě jdoucích mocnin matice krát počáteční reziduum (Krylovova posloupnost). Aproximace řešení se pak tvoří minimalizací rezidua nad vytvořeným podprostorem. Prototypem metody této třídy je metoda konjugovaného gradientu (CG), která předpokládá, že matice systému A {\displaystyle A}
je symetrická kladně definitní. pro symetrickou (a případně neurčitou) matici A {\displaystyle A} je symetrická kladně definitní.
se pracuje s metodou minimálních reziduí (MINRES), v případě nesymetrických matic byly odvozeny metody jako zobecněná metoda minimálních reziduí (GMRES) a metoda bikonjugovaného gradientu (BiCG).
Konvergence metod Krylovových podprostorůUpravit
Protože tyto metody tvoří bázi, je zřejmé, že metoda konverguje v N iteracích, kde N je velikost systému. V přítomnosti zaokrouhlovacích chyb však toto tvrzení neplatí, navíc v praxi může být N velmi velké a iterační proces dosáhne dostatečné přesnosti již mnohem dříve. Analýza těchto metod je obtížná, závisí na komplikované funkci spektra operátoru.
PředpodmínkyEdit
Aproximační operátor, který se objevuje ve stacionárních iteračních metodách, lze také začlenit do Krylovových podprostorových metod, jako je GMRES (případně lze předpodmíněné Krylovovy metody považovat za urychlení stacionárních iteračních metod), kde se stávají transformací původního operátoru na pravděpodobně lépe podmíněný. Konstrukce předpodmínění je rozsáhlou oblastí výzkumu.
HistorieEdit
Pravděpodobně první iterační metoda pro řešení lineárního systému se objevila v Gaussově dopise jednomu z jeho studentů. Navrhl řešit soustavu rovnic 4 x 4 opakovaným řešením té složky, v níž byl zbytek největší.
Teorie stacionárních iteračních metod byla pevně zakotvena prací D. M. Younga počínaje 50. lety 20. století. V 50. letech 20. století byla také vynalezena metoda konjugovaného gradientu, kterou nezávisle na sobě vyvinuli Cornelius Lanczos, Magnus Hestenes a Eduard Stiefel, ale její podstata a použitelnost byly v té době nepochopeny. Teprve v 70. letech 20. století se zjistilo, že metody založené na konjugaci velmi dobře fungují pro parciální diferenciální rovnice, zejména eliptického typu.