I fallet med ett system av linjära ekvationer är de två huvudklasserna av iterativa metoder de stationära iterativa metoderna och de mer allmänna Krylov subspace-metoderna.
Stationära iterativa metoderEdit
IntroduktionEdit
Stationära iterativa metoder löser ett linjärt system med en operatör som närmar sig det ursprungliga systemet, och utifrån en mätning av felet i resultatet (restvärdet) bildar de en ”korrigeringsekvation” för vilken denna process upprepas. Även om dessa metoder är enkla att härleda, implementera och analysera är konvergensen endast garanterad för en begränsad klass av matriser.
DefinitionEdit
En iterativ metod definieras genom
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
och för ett givet linjärt system A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
med exakt lösning x ∗ {\displaystyle \mathbf {x} ^{*}}
felet med e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}
En iterativ metod kallas linjär om det finns en matris C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}}}
så att e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0}
och denna matris kallas iterationsmatris.En iterativ metod med en given iterationsmatris C {\displaystyle C}
kallas konvergent om följande gäller lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}
En viktig sats säger att för en given iterativ metod och dess iterationsmatris C {\displaystyle C}
är konvergent om och endast om dess spektralradie ρ ( C ) {\displaystyle \rho (C)}
är mindre än ett, det vill säga ρ ( C ) < 1 . {\displaystyle \rho (C)<1\,.}
De grundläggande iterativa metoderna fungerar genom att dela upp matrisen A {\displaystyle A}
i A = M – N {\displaystyle A=M-N}
och här matrisen M {\displaystyle M}
bör vara lätt inverterbar.De iterativa metoderna definieras nu 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\,.}
Därav följer att iterationsmatrisen ges av
C = I – M – 1 A = M – 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
ExempelRedigera
Basiska exempel på stationära iterativa metoder använder en uppdelning av matrisen 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})}
där D {\displaystyle D}
är endast den diagonala delen av A {\displaystyle A}
, och L {\displaystyle L}
är den strikta nedre triangulära delen av A {\displaystyle A}
, och U {\displaystyle U}
är den strikta övre triangulära delen av A {\displaystyle A}.
.
- Richardson-metoden: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}
- Jacobimetoden: M := D {\displaystyle M:=D}
- Dämpad Jacobimetod: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}
- Gauss-Seidel-metoden: M := D + L {\displaystyle M:=D+L}
- Successiv överrelaxeringsmetod (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}
- Symmetrisk successiv överrelaxation (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\})}
Linjära stationära iterativa metoder kallas också relaxationsmetoder.
Krylov subspace metoderRedigera
Krylov subspace metoder fungerar genom att bilda en bas av sekvensen av på varandra följande matrispotenser gånger den initiala residualen (Krylovsekvensen). Approximationerna till lösningen bildas sedan genom att minimera restvärdet över det bildade underutrymmet. Den prototypiska metoden i denna klass är den konjugerade gradientmetoden (CG) som utgår från att systemmatrisen A {\displaystyle A}
är symmetrisk positiv-definit.För symmetriska (och eventuellt obestämda) A {\displaystyle A}
arbetar man med den minimala residualmetoden (MINRES).När det gäller icke-symmetriska matriser har metoder som den generaliserade minimala residualmetoden (GMRES) och den bikonjugerade gradientmetoden (BiCG) tagits fram.
Konvergens av Krylov subspace metoderRedigera
Då dessa metoder bildar en bas är det uppenbart att metoden konvergerar i N iterationer, där N är systemets storlek. I närvaro av avrundningsfel gäller dock inte detta påstående; dessutom kan N i praktiken vara mycket stort och den iterativa processen når tillräcklig noggrannhet redan långt tidigare. Analysen av dessa metoder är svår och beror på en komplicerad funktion av operatörens spektrum.
PrekonditioneringarRedigera
Den approximerande operatör som förekommer i stationära iterativa metoder kan också införlivas i Krylov-underrymdsmetoder som GMRES (alternativt kan prekonditionerade Krylov-metoder betraktas som accelerationer av stationära iterativa metoder), där de blir omvandlingar av den ursprungliga operatören till en förmodligen bättre konditionerad sådan. Konstruktionen av prekonditionerare är ett stort forskningsområde.
HistorikRedigera
Den första iterativa metoden för att lösa ett linjärt system dök troligen upp i ett brev från Gauss till en av hans elever. Han föreslog att man skulle lösa ett 4 x 4 ekvationssystem genom att upprepade gånger lösa den komponent där restvärdet var störst.
Teorin om stationära iterativa metoder var fast etablerad i och med D.M. Youngs arbete med början på 1950-talet. Den konjugerade gradientmetoden uppfanns också på 1950-talet, med oberoende utveckling av Cornelius Lanczos, Magnus Hestenes och Eduard Stiefel, men dess natur och användbarhet missförstods då. Först på 1970-talet insåg man att konjugatbaserade metoder fungerar mycket bra för partiella differentialekvationer, särskilt av elliptisk typ.