W przypadku układu równań liniowych, dwie główne klasy metod iteracyjnych to stacjonarne metody iteracyjne oraz bardziej ogólne metody podprzestrzeni Kryłowa.
Stacjonarne metody iteracyjneEdit
WprowadzenieEdit
Stacjonarne metody iteracyjne rozwiązują układ liniowy z operatorem aproksymującym oryginalny; i na podstawie pomiaru błędu w wyniku (residuum), tworzą „równanie korekcyjne”, dla którego proces ten jest powtarzany. Chociaż metody te są proste do wyprowadzenia, implementacji i analizy, zbieżność jest gwarantowana tylko dla ograniczonej klasy macierzy.
DefinicjaEdit
Metodę iteracyjną definiuje się przez
x k + 1 := Ψ ( x k ) , k ≥ 0 {\i0}mathbf {x} ^{k+1}:= \Psi (\mathbf {x} ^{k})\,,\quad k \geq 0}
i dla danego układu liniowego A x = b {\displaystyle A\mathbf {x} = \mathbf {b} }
z rozwiązaniem dokładnym x ∗ {displaystyle \mathbf {x} ^{*}}
błąd przez e k := x k – x ∗ , k ≥ 0 . {^{k}} ^{k}:= ^mathbf {x} ^{k}- \mathbf {x} ^{*}},,\quad k \geq 0\,,}
Metodę iteracyjną nazywamy liniową, jeśli istnieje macierz C ∈ R n × n {{displaystyle C} w ∈mathbf {R} ^{n razy n}}.
taka, że e k + 1 = C e k ∀ k ≥ 0 {displaystyle \mathbf {e} ^{k+1}=C^mathbf {e} ^{k}}quad \forall \,k\geq 0}
i macierz ta nazywana jest macierzą iteracji.Metoda iteracyjna z daną macierzą iteracji C {displaystyle C}
nazywa się zbieżną, jeśli zachodzi następująca zależność lim k → ∞ C k = 0 . C^{k} = 0 {displaystyle ^lim _{krightarrow ^infty } C^{k} = 0}.
Ważne twierdzenie mówi, że dla danej metody iteracyjnej i jej macierzy iteracyjnej C {displaystyle C}
jest ona zbieżna wtedy i tylko wtedy, gdy jej promień spektralny ρ ( C ) {{displaystyle \rho (C)}
jest mniejszy od jedności, to znaczy, że ρ ( C ) < 1 . {displaystyle ρrho (C)<1 }
Podstawowe metody iteracyjne działają poprzez podział macierzy A {displaystyle A}
na A = M – N {{displaystyle A=M-N}}
i tu macierz M {displaystyle M}
powinna być łatwo odwracalna.Metody iteracyjne są teraz zdefiniowane jako M x k + 1 = N x k + b , k ≥ 0 . {^{k+1} = N x k + b , k ≥ 0 . ^{k+1}=Nathmathbf {x} ^{k}+b,,^quad k 0,,^geq 0,,}
Wynika z tego, że macierz iteracji jest dana przez
C = I – M – 1 A = M – 1 N . {{displaystyle C=I-M^{-1}A=M^{-1}N\,.}
PrzykładyEdit
Podstawowe przykłady stacjonarnych metod iteracyjnych wykorzystują podział macierzy A {{displaystyle A}
takie jak A = D + L + U , D := diag ( ( a i i ) i ) {{displaystyle A=D+L+U}}, quad D:={diag}((a_{ii})_{i})}
gdzie D {displaystyle D}
jest tylko przekątną części A {displaystyle A}
, a L {displaystyle L}
jest ścisłą dolną trójkątną częścią A {displaystyle A}
.Odpowiednio, U {displaystyle U}
jest ścisłą górną trójkątną częścią A {displaystyle A}
.
.
- Metoda Richardsona: M := 1 ω I ( ω ≠ 0 ) {displaystyle M:={frac {1}{omega }}Iquad (≠ 0)}
- Metoda Jacobiego: M := D { {przykład M:=D}
- Stłumiona metoda Jacobiego: M := 1 ω D ( ω ≠ 0 ) {displaystyle M:={frac {1}{omega }}Dquad (≠ 0)}
- Metoda Gaussa-Seidela: M := D + L {przykład M:=D+L}
- Metoda sukcesywnej nadrelaksacji (SOR): M := 1 ω D + L ( ω ≠ 0 ) {displaystyle M:={frac {1}{omega }}D+Lquad (≠ 0)}
- Symmetric successive over-relaxation (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\})}
Liniowe stacjonarne metody iteracyjne są również nazywane metodami relaksacyjnymi.
Metody podprzestrzeni KryłowaEdit
Metody podprzestrzeni Kryłowa działają poprzez utworzenie podstawy ciągu kolejnych potęg macierzy razy resztę początkową (sekwencja Kryłowa). Przybliżenia do rozwiązania są następnie tworzone poprzez minimalizację reszt nad utworzoną podprzestrzenią. Prototypową metodą w tej klasie jest metoda gradientu sprzężonego (CG), w której zakłada się, że macierz układu A {{displaystyle A}
jest symetryczna dodatnio-definitywna.Dla symetrycznych (i ewentualnie niedefinitywnych) macierzy A {displaystyle A}
pracuje się z metodą minimalnej pozostałości (MINRES).W przypadku macierzy niesymetrycznych wyprowadzono takie metody jak uogólniona metoda minimalnej pozostałości (GMRES) i metoda gradientu dwuwypukłego (BiCG).
Zbieżność metod podprzestrzeni KryłowaEdit
Ponieważ metody te tworzą podstawę, jest oczywiste, że metoda zbiega w N iteracjach, gdzie N jest rozmiarem systemu. Jednak w obecności błędów zaokrągleń stwierdzenie to nie jest prawdziwe; co więcej, w praktyce N może być bardzo duże, a proces iteracyjny osiąga wystarczającą dokładność już dużo wcześniej. Analiza tych metod jest trudna, zależy od skomplikowanej funkcji widma operatora.
Kondycjonery wstępneEdit
Operator aproksymujący pojawiający się w stacjonarnych metodach iteracyjnych może być również włączony do metod podprzestrzeni Kryłowa, takich jak GMRES (alternatywnie, wstępnie uwarunkowane metody Kryłowa mogą być traktowane jako akceleracje stacjonarnych metod iteracyjnych), gdzie stają się one transformacjami oryginalnego operatora na przypuszczalnie lepiej uwarunkowany. Konstrukcja kondycjonerów jest dużym obszarem badawczym.
HistoriaEdit
Prawdopodobnie pierwsza iteracyjna metoda rozwiązywania układów liniowych pojawiła się w liście Gaussa do jednego z jego studentów. Zaproponował on rozwiązanie układu równań 4 na 4 poprzez wielokrotne rozwiązywanie składnika, w którym reszta była największa.
Teoria stacjonarnych metod iteracyjnych została solidnie ugruntowana dzięki pracy D.M. Younga, która rozpoczęła się w latach pięćdziesiątych. Metoda gradientu sprzężonego została również wynaleziona w latach 50-tych, z niezależnymi opracowaniami Corneliusa Lanczosa, Magnusa Hestenesa i Eduarda Stiefela, ale jej natura i możliwości zastosowania były wówczas niezrozumiałe. Dopiero w latach 70-tych zdano sobie sprawę, że metody oparte na koniugacji bardzo dobrze sprawdzają się w przypadku równań różniczkowych cząstkowych, zwłaszcza typu eliptycznego.