În cazul unui sistem de ecuații liniare, cele două clase principale de metode iterative sunt metodele iterative staționare și metodele mai generale ale subspațiului Krylov.
Metode iterative staționareEdit
IntroducereEdit
Metodele iterative staționare rezolvă un sistem liniar cu un operator care îl aproximează pe cel inițial; și pe baza unei măsurători a erorii din rezultat (rezidualul), formează o „ecuație de corecție” pentru care se repetă acest proces. Deși aceste metode sunt simplu de derivat, implementat și analizat, convergența este garantată doar pentru o clasă limitată de matrici.
DefinițieEdit
O metodă iterativă este definită prin
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
și pentru un sistem liniar dat A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
cu soluția exactă x ∗ {\displaystyle \mathbf {x} ^{*}}
eroarea prin e k := x k – x ∗ , k ≥ 0 . {\displaystyle \mathbf {e} ^{k}:=\mathbf {x} ^{k}-\mathbf {x} ^{*}\,,\quad k\geq 0\,.}
O metodă iterativă se numește liniară dacă există o matrice C ∈ R n × n {\displaystyle C\în \mathbb {R} ^{n\ ori n}}.
astfel încât e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}\quad \pentru toate \,k\geq 0}
și această matrice se numește matrice de iterație. o metodă iterativă cu o matrice de iterație dată C {\displaystyle C}
se numește convergentă dacă sunt valabile următoarele lim k → ∞ C k = 0 . {\displaystyle \lim _{k\rightarrow \infty }C^{k}=0\,.}
O teoremă importantă afirmă că pentru o metodă iterativă dată și matricea sa de iterație C {\displaystyle C}
aceasta este convergentă dacă și numai dacă raza sa spectrală ρ ( C ) {\displaystyle \rho (C)}
este mai mică decât unitatea, adică ρ ( C ) < 1 . {\displaystyle \rho (C)<1\,.}
Metodele iterative de bază funcționează prin divizarea matricei A {\displaystyle A}
în A = M – N {\displaystyle A=M-N}
și aici matricea M {\displaystyle M}
ar trebui să fie ușor de inversat.Metodele iterative sunt acum definite ca 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\,.}
Din aceasta rezultă că matricea de iterație este dată de
C = I – M – 1 A = M – 1 N . {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
ExempleEdit
Exemplele de bază ale metodelor iterative staționare utilizează o divizare a matricei A {\displaystyle A}
cum ar fi A = D + L + U , D := diag ( ( ( a i i ) i ) i ) {\displaystyle A=D+L+U\,,\quad D:={\text{diag}}((a_{ii})_{i})}
unde D {\displaystyle D}
este doar partea diagonală a lui A {\displaystyle A}
, iar L {\displaystyle L}
este partea triunghiulară inferioară strictă a lui A {\displaystyle A}.
.Respectiv, U {\displaystyle U}
este partea triunghiulară superioară strictă a lui A {\displaystyle A}.
.
- Metoda Richardson: M := 1 ω I ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}I\quad (\omega \neq 0)}
- Metoda Jacobi: M := D {\displaystyle M:=D}
- Metoda Jacobi amortizată: M := 1 ω D ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D\quad (\omega \neq 0)}
- Metoda Gauss-Seidel: M := D + L {\displaystyle M:=D+L}
- Metoda suprarelaxării succesive (SOR): M := 1 ω D + L ( ω ≠ 0 ) {\displaystyle M:={\frac {1}{\omega }}D+L\quad (\omega \neq 0)}
- Suprarelaxare succesivă simetrică (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\})}
Metodele iterative staționare liniare se mai numesc și metode de relaxare.
Metode de subspațiu KrylovEdit
Metodele de subspațiu Krylov funcționează prin formarea unei baze a secvenței de puteri succesive ale matricei înmulțite cu reziduul inițial (secvența Krylov). Aproximațiile la soluție se formează apoi prin minimizarea reziduului pe subspațiul format. Metoda prototipică din această clasă este metoda gradientului conjugat (CG), care pornește de la premisa că matricea sistemului A {\displaystyle A}
este simetrică pozitiv-definită. pentru A {\displaystyle A} simetrică (și eventual indefinită)
se lucrează cu metoda reziduului minim (MINRES).În cazul matricelor nesimetrice, au fost derivate metode precum metoda reziduului minim generalizat (GMRES) și metoda gradientului biconjugat (BiCG).
Convergența metodelor subspațiului KrylovEdit
Din moment ce aceste metode formează o bază, este evident că metoda converge în N iterații, unde N este dimensiunea sistemului. Cu toate acestea, în prezența erorilor de rotunjire, această afirmație nu este valabilă; mai mult, în practică, N poate fi foarte mare, iar procesul iterativ atinge o precizie suficientă deja mult mai devreme. Analiza acestor metode este dificilă, depinzând de o funcție complicată a spectrului operatorului.
PrecondiționăriEdit
Operatorul de aproximare care apare în metodele iterative staționare poate fi, de asemenea, încorporat în metodele de subspațiu Krylov, cum ar fi GMRES (alternativ, metodele Krylov precondiționate pot fi considerate drept accelerări ale metodelor iterative staționare), unde acestea devin transformări ale operatorului original într-unul presupus mai bine condiționat. Construcția precondiționerilor este un domeniu de cercetare vast.
IstoricEdit
Probabil că prima metodă iterativă pentru rezolvarea unui sistem liniar a apărut într-o scrisoare a lui Gauss către un student de-al său. El a propus rezolvarea unui sistem de ecuații 4 câte 4 prin rezolvarea repetată a componentei în care reziduul era cel mai mare.
Teoria metodelor iterative staționare a fost solid stabilită cu lucrările lui D.M. Young începând cu anii 1950. Metoda gradientului conjugat a fost, de asemenea, inventată în anii 1950, cu dezvoltări independente ale lui Cornelius Lanczos, Magnus Hestenes și Eduard Stiefel, dar natura și aplicabilitatea sa au fost neînțelese la acea vreme. Abia în anii 1970 s-a realizat că metodele bazate pe conjugare funcționează foarte bine pentru ecuațiile cu derivate parțiale, în special cele de tip eliptic.
.