Lineaarisen yhtälösysteemin tapauksessa iteratiivisten menetelmien kaksi pääluokkaa ovat stationaariset iteratiiviset menetelmät ja yleisemmät Krylovin aliavaruusmenetelmät.
Stationaariset iteratiiviset menetelmätEdit
JohdantoEdit
Stationaariset iteratiiviset menetelmät ratkaisevat lineaarisen järjestelmän alkuperäistä approksimoivalla operaattorilla; ja muodostavat tuloksen virheen (residuaalin) mittauksen perusteella ”korjausyhtälön”, jota varten tämä prosessi toistetaan. Vaikka nämä menetelmät on helppo johtaa, toteuttaa ja analysoida, konvergenssi on taattu vain rajoitetulle matriisiluokalle.
MääritelmäMuokkaa
Iteratiivinen menetelmä määritellään seuraavasti
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
ja annetulle lineaariselle systeemille A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
jolla on tarkka ratkaisu x ∗ {\displaystyle \mathbf {x} ^{*}}
virhe e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}
Iteratiivista menetelmää kutsutaan lineaariseksi, jos on olemassa matriisi C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}}}
siten, että e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e}=C\mathbf {e} ^{k}\quad \forall \,k\geq 0}
ja tätä matriisia kutsutaan iterointimatriisiksi.Iteratiivinen menetelmä, jolla on annettu iterointimatriisi C {\displaystyle C}
kutsutaan konvergentiksi, jos pätee lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}
Tärkeä lause sanoo, että tietylle iteratiiviselle menetelmälle ja sen iterointimatriisille C {\displaystyle C}
se on konvergentti, jos ja vain jos sen spektrisäde ρ ( C ) {\displaystyle \rho (C)} on konvergentti.
on pienempi kuin yksikkö, eli ρ ( C ) < 1 . {\displaystyle \rho (C)<1\,.}
Perusiteraatiomenetelmät toimivat jakamalla matriisi A {\displaystyle A}
muotoon A = M – N {\displaystyle A=M-N}
ja tässä matriisi M {\displaystyle M}
pitäisi olla helposti invertoitavissa.Iteratiiviset menetelmät määritellään nyt seuraavasti: M x k + 1 = N x k + b , k ≥ 0 . {\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} = N\mathbf {x} ^{k}+b\,,\quad k\geq 0\,.}
Tästä seuraa, että iteraatiomatriisi saadaan
C = I – M – 1 A = M – 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
EsimerkkejäEdit
Perusesimerkit stationaarisista iteratiivisista menetelmistä käyttävät matriisin A jakamista {\displaystyle A}
kuten A = D + L + U , D := diag ( ( ( a i i ) i ) {\displaystyle A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})}
jossa D {\displaystyle D}
on vain A:n {\displaystyle A} diagonaaliosa.
, ja L {\displaystyle L}
on A {\displaystyle A}:n tiukka alempi kolmiomainen osa.
.Vastaavasti U {\displaystyle U}
on A:n {\displaystyle A} tiukka ylempi kolmiosa.
.
- Richardsonin menetelmä: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}
- Jacobin menetelmä: M := D {\displaystyle M:=D}
- Vaimennettu Jacobin menetelmä: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}
- Gauss-Seidelin menetelmä: M := D + L {\displaystyle M:=D+L}
- Successive over-relaxation method (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}
- Symmetrinen peräkkäinen ylirelaksaatio (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\})}
Lineaarisia stationaarisia iteratiivisia menetelmiä kutsutaan myös relaksaatiomenetelmiksi.
Krylovin aliavaruusmenetelmätEdit
Krylovin aliavaruusmenetelmät toimivat siten, että perusta muodostetaan peräkkäisten matriisipotenssien jakson peräkkäisten matriisipotenssien jaksosta kertaa alkujäännös (Krylovin jakso). Ratkaisun approksimaatiot muodostetaan sitten minimoimalla jäännös muodostetun aliavaruuden yli. Tämän luokan prototyyppinen menetelmä on konjugoidun gradientin menetelmä (CG), jossa oletetaan, että järjestelmän matriisi A {\displaystyle A}
on symmetrinen positiivis-definiittinen.Symmetriselle (ja mahdollisesti epämääräiselle) A {\displaystyle A}:lle {\displaystyle A}
työskennellään minimijäämämenetelmällä (MINRES).Epäsymmetristen matriisien tapauksessa on johdettu menetelmiä, kuten yleistetty minimijäämämenetelmä (GMRES) ja biconjugate gradient method (BiCG).
Krylovin aliavaruusmenetelmien konvergenssiEdit
Koska nämä menetelmät muodostavat perustan, on ilmeistä, että menetelmä konvergoituu N iteraatiossa, jossa N on järjestelmän koko. Pyöristysvirheiden esiintyessä tämä väite ei kuitenkaan päde; lisäksi käytännössä N voi olla hyvin suuri, ja iteratiivinen prosessi saavuttaa riittävän tarkkuuden jo paljon aikaisemmin. Näiden menetelmien analyysi on vaikeaa, sillä se riippuu operaattorin spektrin monimutkaisesta funktiosta.
EsikonditionoijatEdit
Sationaarisissa iteratiivisissa menetelmissä esiintyvä approksimointioperaattori voidaan sisällyttää myös Krylovin aliavaruusmenetelmiin, kuten GMRES:iin (vaihtoehtoisesti esikonditionoituja Krylovin menetelmiä voidaan pitää stationaaristen iteratiivisten menetelmien kiihdyttämöinä), jolloin niistä tulee alkuperäisen operaattorin transformaatioita oletettavasti parempikuntoiseen. Esikonditionoijien rakentaminen on laaja tutkimusalue.
HistoriaEdit
Todennäköisesti ensimmäinen iteratiivinen menetelmä lineaarisen järjestelmän ratkaisemiseen ilmestyi Gaussin kirjeessä eräälle oppilaalleen. Hän ehdotti 4 kertaa 4 yhtälösysteemin ratkaisemista ratkaisemalla toistuvasti se komponentti, jossa jäännös oli suurin.
Sationaaristen iteratiivisten menetelmien teoria vakiintui D.M. Youngin työn myötä 1950-luvulta alkaen. Conjugate Gradient -menetelmä keksittiin myös 1950-luvulla Cornelius Lanczosin, Magnus Hestenesin ja Eduard Stiefelin itsenäisen kehityksen myötä, mutta sen luonne ja sovellettavuus ymmärrettiin tuolloin väärin. Vasta 1970-luvulla huomattiin, että konjugaatioon perustuvat menetelmät toimivat erittäin hyvin osittaisdifferentiaaliyhtälöille, erityisesti elliptisille.