I tilfælde af et system af lineære ligninger er de to hovedklasser af iterative metoder de stationære iterative metoder og de mere generelle Krylov-underrumsmetoder.
Stationære iterative metoderRediger
IndledningRediger
Stationære iterative metoder løser et lineært system med en operatør, der tilnærmer sig det oprindelige system; og på grundlag af en måling af fejlen i resultatet (residualet) danner de en “korrektionsligning”, for hvilken denne proces gentages. Selv om disse metoder er enkle at udlede, implementere og analysere, er konvergens kun garanteret for en begrænset klasse af matricer.
DefinitionEdit
En iterativ metode er defineret ved
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
og for et givet lineært system A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
med nøjagtig løsning x ∗ {\displaystyle \mathbf {x} ^{*}}
fejlen ved e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}
En iterativ metode kaldes lineær, hvis der findes en matrix C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}}}
således at e k + 1 = C e k ∀ k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0}
og denne matrix kaldes iterationsmatrixen.En iterativ metode med en given iterationsmatrix C {\displaystyle C}
kaldes konvergent, hvis følgende gælder lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}
En vigtig sætning siger, at for en given iterativ metode og dens iterationsmatrix C {\displaystyle C}
er den konvergent, hvis og kun hvis dens spektralradius ρ ( C ) {\displaystyle \rho (C)}
er mindre end enheden, dvs. at ρ ( C ) < 1 . {\displaystyle \rho (C)<1\,.}
De grundlæggende iterative metoder fungerer ved at opdele matrixen A {\displaystyle A}
i A = M – N {\displaystyle A=M-N}
og her er matrixen M {\displaystyle M}
bør være let invertibel.De iterative metoder er nu defineret som 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\,.}
Deraf følger, at iterationsmatrixen er givet ved
C = I – M – 1 A = M – 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
EksemplerRediger
Basiseksempler på stationære iterative metoder anvender en opsplitning af matrixen A {\displaystyle A}
såsom A = D + L + U , D := diag ( ( ( a i i i ) i ) {\displaystyle A=D+L+U\,,\quad D:={{\text{diag}}((a_{ii})_{i})}
hvor D {\displaystyle D}
kun er den diagonale del af A {\displaystyle A}
, og L {\displaystyle L}
er den strenge nedre trekantede del af A {\displaystyle A}
, henholdsvis er U {\displaystyle U}
er den strenge øvre trekantede del af A {\displaystyle A}
.
- Richardson-metoden: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}
- Jacobi-metoden: M := D {\displaystyle M:=D}
- Dæmpet Jacobi-metode: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={{\frac {1}{\omega }}D\quad (\omega \neq 0)}
- Gauss-Seidel-metode: M := D + L {\displaystyle M:=D+L}
- Successiv overrelaksationsmetode (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}
- Symmetrisk successiv overrelaksation (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ære stationære iterative metoder kaldes også afslapningsmetoder.
Krylov subspace metoderRediger
Krylov subspace metoder fungerer ved at danne en basis af sekvensen af på hinanden følgende matrixpowers gange den oprindelige residual (Krylov sekvensen). Tilnærmelserne til løsningen dannes derefter ved at minimere restværdien over det dannede underrum. Den prototypiske metode i denne klasse er den konjugerede gradientmetode (CG), som antager, at systemets matrix A {\displaystyle A}
er symmetrisk positiv-definit.For symmetrisk (og muligvis udefinit) A {\displaystyle A}
arbejder man med den minimale residualmetode (MINRES).I tilfælde af ikke-symmetriske matricer er metoder som den generaliserede minimale residualmetode (GMRES) og den bikonjugerede gradientmetode (BiCG) blevet afledt.
Konvergens af Krylov-underrumsmetoderRediger
Da disse metoder danner et grundlag, er det indlysende, at metoden konvergerer i N iterationer, hvor N er systemets størrelse. I tilfælde af afrundingsfejl holder dette udsagn imidlertid ikke; desuden kan N i praksis være meget stor, og den iterative proces når tilstrækkelig nøjagtighed allerede langt tidligere. Analysen af disse metoder er vanskelig, idet den afhænger af en kompliceret funktion af operatørens spektrum.
ForkonditioneringsmetoderRediger
Den approksimerende operatør, der optræder i stationære iterative metoder, kan også indarbejdes i Krylov-underrumsmetoder såsom GMRES (alternativt kan forkonditionerede Krylov-metoder betragtes som accelerationer af stationære iterative metoder), hvor de bliver transformationer af den oprindelige operatør til en formodentlig bedre konditioneret operatør. Konstruktionen af preconditioners er et stort forskningsområde.
HistorieRediger
Den første iterative metode til løsning af et lineært system optrådte formentlig i et brev fra Gauss til en af hans elever. Han foreslog at løse et 4 x 4-system af ligninger ved gentagne gange at løse den komponent, hvor residualet var størst.
Teorien om stationære iterative metoder blev solidt etableret med D.M. Young’s arbejde fra 1950’erne. Den konjugerede gradientmetode blev også opfundet i 1950’erne med uafhængige udviklinger af Cornelius Lanczos, Magnus Hestenes og Eduard Stiefel, men dens karakter og anvendelighed blev misforstået på daværende tidspunkt. Først i 1970’erne blev det indset, at konjugationsbaserede metoder fungerer meget godt for partielle differentialligninger, især af elliptisk type.