In het geval van een stelsel lineaire vergelijkingen zijn de twee belangrijkste klassen van iteratieve methoden de stationaire iteratieve methoden, en de meer algemene Krylov-deelruimtemethoden.
Stationaire iteratieve methodenEdit
InleidingEdit
Stationaire iteratieve methoden lossen een lineair stelsel op met een operator die het oorspronkelijke benadert; en vormen op basis van een meting van de fout in het resultaat (de rest) een “correctievergelijking” waarvoor dit proces wordt herhaald. Hoewel deze methoden eenvoudig af te leiden, uit te voeren en te analyseren zijn, is de convergentie slechts voor een beperkte klasse van matrices gegarandeerd.
DefinitieEdit
Een iteratieve methode wordt gedefinieerd door
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=[Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
en voor een gegeven lineair stelsel A x = b {\displaystyle A\mathbf {x} =\mathbf {b}} }
met exacte oplossing x ∗ {\displaystyle \mathbf {x}} ^{*}}
de fout door e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:= {mathbf {x} ^{k}-[mathbf {x} ^{*},,\quad k\geq 0,}
Een iteratieve methode wordt lineair genoemd als er een matrix C ∈ R n × n {\displaystyle C\in \mathbf {R} ^{n} keer n}} bestaat.
zodat e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}quad \vooralle \,k0}
en deze matrix wordt de iteratiematrix genoemd.Een iteratieve methode met een gegeven iteratiematrix C {Displaystyle C}
wordt convergent genoemd als het volgende geldt lim k → ∞ C k = 0 . {Displaystyle \lim _{k}rightarrow \infty }C^{k}=0.
Een belangrijke stelling stelt dat voor een gegeven iteratieve methode en haar iteratiematrix C {\displaystyle C}
convergent is als en slechts als de spectrale straal ρ ( C ) {{\displaystyle \rho (C)}
kleiner is dan eenheid, dat wil zeggen, ρ ( C ) < 1 . {Displaystyle \rho (C)} <1
De basis iteratieve methoden werken door het splitsen van de matrix A {\displaystyle A}
in A = M – N {\displaystyle A=M-N}
en hier de matrix M {\displaystyle M}
moet gemakkelijk inverteerbaar zijn.De iteratieve methoden zijn nu gedefinieerd als M x k + 1 = N x k + b , k ≥ 0 . {\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b,,\quad k\geq 0,.}
Hieruit volgt dat de iteratiematrix gegeven wordt door
C = I – M – 1 A = M – 1 N. {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
VoorbeeldenEdit
Basisvoorbeelden van stationaire iteratieve methoden gebruiken een splitsing van de matrix A {\displaystyle A}
zoals A = D + L + U , D := diag ( ( a i i ) i ) {\displaystyle A=D+L+U,,\quad D:={\text{diag}((a_{ii})_{i})}
waar D {{Displaystyle D}}
alleen het diagonale deel van A {\displaystyle A}
, en L {\displaystyle L}
is het strikte lagere driehoeksdeel van A {\displaystyle A}
. Respectievelijk, U {\displaystyle U}
het strikte bovenste driehoekige deel van A {\displaystyle A}
.
- Methode van Richardson: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}Iquad (\omega \neq 0)}
- Jacobimethode: M := D {M:=D}
- Gedempte Jacobi-methode: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}Dquad (\omega \neq 0)}
- Gauss-Seidel methode: M := D + L {Displaystyle M:=D+L}
- Successieve over-relaxatiemethode (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+Lquad (\omega \neq 0)}
- Symmetrische opeenvolgende over-relaxatie (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\})}
Lineaire stationaire iteratieve methoden worden ook wel relaxatiemethoden genoemd.
Krylov-deelruimtemethodenEdit
Krylov-deelruimtemethoden werken door een basis te vormen van de opeenvolging van opeenvolgende matrixmachten maal het initiële residu (de Krylov-reeks). De benaderingen van de oplossing worden dan gevormd door het residu over de gevormde deelruimte te minimaliseren. De prototypische methode in deze klasse is de geconjugeerde-gradiëntmethode (CG), die ervan uitgaat dat de systeemmatrix A {{Displaystyle A}
symmetrisch positief-definiet is.Voor symmetrische (en mogelijk indefiniete) A {\displaystyle A}
werkt men met de minimale residumethode (MINRES).In het geval van niet-symmetrische matrices zijn methoden afgeleid zoals de gegeneraliseerde minimale residumethode (GMRES) en de biconjugate gradient methode (BiCG).
Convergentie van Krylov-deelruimtemethodenEdit
Omdat deze methoden een basis vormen, is het evident dat de methode convergeert in N iteraties, waarbij N de systeemgrootte is. In aanwezigheid van afrondingsfouten gaat deze bewering echter niet op; bovendien kan N in de praktijk zeer groot zijn, en bereikt het iteratieve proces al veel eerder voldoende nauwkeurigheid. De analyse van deze methoden is moeilijk, afhankelijk van een gecompliceerde functie van het spectrum van de operator.
PreconditionersEdit
De benaderingsoperator die in stationaire iteratieve methoden voorkomt kan ook worden opgenomen in Krylov deelruimtemethoden zoals GMRES (als alternatief kunnen gepreconditioneerde Krylov methoden worden beschouwd als versnellingen van stationaire iteratieve methoden), waar zij transformaties worden van de oorspronkelijke operator naar een vermoedelijk beter geconditioneerde operator. De constructie van preconditioners is een groot onderzoeksterrein.
GeschiedenisEdit
Waarschijnlijk verscheen de eerste iteratieve methode voor het oplossen van een lineair stelsel in een brief van Gauss aan een leerling van hem. Hij stelde voor een stelsel van 4 bij 4 vergelijkingen op te lossen door herhaaldelijk de component op te lossen waarin de rest het grootst was.
De theorie van stationaire iteratieve methoden kreeg vaste vorm met het werk van D.M. Young vanaf de jaren 1950. De Conjugate Gradient methode werd ook uitgevonden in de jaren 1950, met onafhankelijke ontwikkelingen door Cornelius Lanczos, Magnus Hestenes en Eduard Stiefel, maar de aard en toepasbaarheid ervan werden toen verkeerd begrepen. Pas in de jaren 1970 realiseerde men zich dat op conjugatie gebaseerde methoden zeer goed werken voor partiële differentiaalvergelijkingen, vooral van het elliptische type.