Lineráris egyenletrendszer esetén az iteratív módszerek két fő osztálya a stacionárius iteratív módszerek és az általánosabb Krylov altér módszerek.
Stacionárius iteratív módszerekSzerkesztés
BevezetésSzerkesztés
A stacionárius iteratív módszerek egy lineáris rendszert egy, az eredetit közelítő operátorral oldanak meg; és az eredmény hibájának (a maradéknak) a mérése alapján alkotnak egy “korrekciós egyenletet”, amelyre ezt a folyamatot megismétlik. Bár ezeket a módszereket egyszerű levezetni, megvalósítani és elemezni, a konvergencia csak a mátrixok egy korlátozott osztályára garantált.
DefinícióSzerkesztés
Egy iteratív módszer definíciója:
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
és egy adott A x = b lineáris rendszerre {\displaystyle A\mathbf {x} =\mathbf {b} }
egzakt megoldással x ∗ {\displaystyle \mathbf {x} ^{*}}
a hiba e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}
Egy iteratív módszert lineárisnak nevezünk, ha létezik egy C ∈ R n × n mátrix {\displaystyle C\in \mathbb {R} ^{n\times n}}}
olyan, hogy e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0}
és ezt a mátrixot nevezzük iterációs mátrixnak.Egy adott iterációs mátrixú iterációs módszer C {\displaystyle C}
konvergensnek nevezzük, ha a következő igaz: lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}
Egy fontos tétel kimondja, hogy egy adott iteratív módszerre és annak C iterációs mátrixára {\displaystyle C}
akkor és csak akkor konvergens, ha a spektrális sugara ρ ( C ) {\displaystyle \rho (C)}
kisebb, mint egység, azaz ρ ( C ) < 1 . {\displaystyle \rho (C)<1\,.}
Az alapvető iteratív módszerek az A {\displaystyle A} mátrix felosztásával dolgoznak.
A = M – N {\displaystyle A=M-N} mátrixra osztjuk.
és itt az M mátrix {\displaystyle M}
könnyen invertálhatónak kell lennie.Az iteratív módszereket most úgy definiáljuk, hogy 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\,.}
Ebből következik, hogy az iterációs mátrixot
C = I – M – 1 A = M – 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
PéldákSzerkesztés
A stacionárius iteratív módszerek alapvető példái az A mátrix felosztását használják {\displaystyle A}
például A = D + L + U , D := diag ( ( ( a i i ) i ) i ) {\displaystyle A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})}
ahol D {\displaystyle D}
csak A {\displaystyle A} átlós része.
, és L {\displaystyle L}
az A {\displaystyle A} szigorú alsó háromszög része.
, illetve U {\displaystyle U}
az A {\displaystyle A} szigorú felső háromszög része.
.
- Richardson-módszer: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}
- Jacobi módszer: M := D {\displaystyle M:=D}
- Csökkentett Jacobi módszer: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}
- Gauss-Seidel módszer: M := D + L {\displaystyle M:=D+L}
- Szukcesszív felülrelaxációs módszer (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}
- Szimmetrikus szukcesszív túlrelaxáció (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\})}
A lineáris stacionárius iteratív módszereket relaxációs módszereknek is nevezik.
Krylov altér módszerekSzerkesztés
A Krylov altér módszerek úgy működnek, hogy az egymást követő mátrixpotenciálok sorozatából a kezdeti reziduummal szorzott sorozat (a Krylov-sorozat) alapját képezik. A megoldáshoz való közelítéseket ezután a maradék minimalizálásával képezzük a kialakított altéren. Az ebbe az osztályba tartozó prototipikus módszer a konjugált gradiens módszer (CG), amely feltételezi, hogy a rendszer A {\displaystyle A} mátrixa
szimmetrikus pozitív-definit.Szimmetrikus (és esetleg határozatlan) A {\displaystyle A}
esetén a minimális maradék módszerrel (MINRES) dolgozunk. nem szimmetrikus mátrixok esetén olyan módszereket vezettek le, mint az általánosított minimális maradék módszer (GMRES) és a bikonjugált gradiens módszer (BiCG).
Krylov altér módszerek konvergenciájaSzerkesztés
Mivel ezek a módszerek alapot képeznek, nyilvánvaló, hogy a módszer N iterációban konvergál, ahol N a rendszer mérete. Kerekítési hibák jelenlétében azonban ez az állítás nem érvényes, ráadásul a gyakorlatban N nagyon nagy lehet, és az iteratív eljárás már jóval korábban eléri a kellő pontosságot. Ezeknek a módszereknek az analízise nehézkes, az operátor spektrumának bonyolult függvényétől függ.
PrekondicionálókSzerkesztés
A stacionárius iteratív módszerekben megjelenő közelítő operátor beépíthető a Krylov altér módszerekbe, például a GMRES-be is (alternatívaként az előkondicionált Krylov módszerek a stacionárius iteratív módszerek gyorsításainak tekinthetők), ahol az eredeti operátor transzformációi lesznek egy feltehetően jobban kondicionált operátorhoz. Az előkondicionálók konstruálása nagy kutatási terület.
TörténetSzerkesztés
Valószínűleg az első iteratív módszer egy lineáris rendszer megoldására Gauss egyik diákjának írt levelében jelent meg. Egy 4-szer 4 egyenletrendszer megoldását javasolta annak a komponensnek az ismételt megoldásával, amelyben a maradék a legnagyobb.
A stacionárius iteratív módszerek elmélete D. M. Young munkájával szilárdult meg az 1950-es évektől kezdődően. A konjugált gradiens módszer szintén az 1950-es években született meg, Cornelius Lanczos, Magnus Hestenes és Eduard Stiefel önálló fejlesztéseivel, de annak természetét és alkalmazhatóságát akkoriban félreértették. Csak az 1970-es években jöttek rá, hogy a konjugált gradiens alapú módszerek nagyon jól működnek parciális differenciálegyenletekre, különösen az elliptikus típusúakra.