Nel caso di un sistema di equazioni lineari, le due classi principali di metodi iterativi sono i metodi iterativi stazionari e i più generali metodi del sottospazio di Krylov.
Metodi iterativi stazionariModifica
IntroduzioneModifica
I metodi iterativi stazionari risolvono un sistema lineare con un operatore che approssima quello originale; e sulla base di una misura dell’errore nel risultato (il residuo), formano una “equazione di correzione” per cui questo processo viene ripetuto. Mentre questi metodi sono semplici da derivare, implementare e analizzare, la convergenza è garantita solo per una classe limitata di matrici.
DefinizioneModifica
Un metodo iterativo è definito da
x k + 1 := Ψ ( x k ) , k ≥ 0 {\displaystyle \mathbf {x} ^{k+1}:=\Psi (\mathbf {x} ^{k})\,,\quad k\geq 0}
e per un dato sistema lineare A x = b {\displaystyle A\mathbf {x} =\mathbf {b} }
con soluzione esatta x ∗ {displaystyle \mathbf {x} ^{*}}
l’errore di e k := x k – x ∗ , k ≥ 0 . {\an8}dimostrazioni di stile \mathbf {e} ^{k}:=\mathbf {x} ^{k}-{mathbf {x} ^{*},\quadro k\geq 0\,.}
Un metodo iterativo è detto lineare se esiste una matrice C ∈ R n × n {\displaystyle C\in \mathbb {R} ^{n\times n}}
tale che e k + 1 = C e k ∀ k ≥ 0 {\displaystyle \mathbf {e} ^{k+1}=C\mathbf {e} ^{k}quadro \per tutti \,k\geq 0}
e questa matrice è chiamata matrice di iterazione.Un metodo iterativo con una data matrice di iterazione C {\displaystyle C}
si dice convergente se vale lim k → ∞ C k = 0 . {\displaystyle \lim _{k\arrow \infty }C^{k}=0\,.}
Un importante teorema afferma che per un dato metodo iterativo e la sua matrice di iterazione C {\displaystyle C}
esso è convergente se e solo se il suo raggio spettrale ρ ( C ) {\displaystyle \rho (C)}
è minore dell’unità, cioè ρ ( C ) < 1 . {displaystyle \rho (C)<1\,.}
I metodi iterativi di base funzionano dividendo la matrice A {displaystyle A}
in A = M – N {\displaystyle A=M-N}
e qui la matrice M {\displaystyle M}
dovrebbe essere facilmente invertibile.I metodi iterativi sono ora definiti come M x k + 1 = N x k + b , k ≥ 0 . {\displaystyle M\mathbf {x} ^{k+1}=N\mathbf {x} ^{k}+b,,\quadro k\geq 0\,.}
Da questo segue che la matrice di iterazione è data da
C = I – M – 1 A = M – 1 N. {\displaystyle C=I-M^{-1}A=M^{-1}N\,.}
EsempiModifica
Esempi basilari di metodi iterativi stazionari usano una divisione della matrice A {\displaystyle A}
come A = D + L + U , D := diag ( ( a i i ) i ) {\displaystyle A=D+L+U\,,\quad D:={\testo{diag}}((a_{ii})_{i})}
dove D {\displaystyle D}
è solo la parte diagonale di A {displaystyle A}
, e L {displaystyle L}
è la parte strettamente triangolare inferiore di A {\displaystyle A}
.Rispettivamente, U {\displaystyle U}
è la parte triangolare superiore rigorosa di A {\displaystyle A}
.
- Metodo Richardson: M := 1 ω I ( ω ≠ 0 ) {displaystyle M:={frac {1}{\omega }}I\quadro (\omega \neq 0)}
- Metodo Jacobi: M := D {\anime M:=D}
- Metodo Jacobi smorzato: M := 1 ω D ( ω ≠ 0 ) {displaystyle M:={frac {1}{\omega }}D\quadro (\omega \neq 0)}
- Metodo Gauss-Seidel: M := D + L {\displaystyle M:=D+L}
- Metodo della sovra-rilassazione successiva (SOR): M := 1 ω D + L ( ω ≠ 0 ) {displaystyle M:={frac {1}{\omega }}D+L\quadro (\omega \neq 0)}
- Rilassamento successivo simmetrico (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\})}
I metodi iterativi stazionari lineari sono anche chiamati metodi di rilassamento.
Metodi del sottospazio di KrylovModifica
I metodi del sottospazio di Krylov lavorano formando una base della sequenza di potenze successive di matrici per il residuo iniziale (la sequenza di Krylov). Le approssimazioni alla soluzione sono poi formate minimizzando il residuo sul sottospazio formato. Il metodo prototipo in questa classe è il metodo del gradiente coniugato (CG) che assume che la matrice del sistema A {displaystyle A}
sia simmetrica positiva-definita.Per simmetrica (e possibilmente indefinita) A {displaystyle A}
si lavora con il metodo del minimo residuo (MINRES).Nel caso di matrici non simmetriche, sono stati derivati metodi come il metodo del minimo residuo generalizzato (GMRES) e il metodo del gradiente biconiugato (BiCG).
Convergenza dei metodi di Krylov subspaceModifica
Siccome questi metodi formano una base, è evidente che il metodo converge in N iterazioni, dove N è la dimensione del sistema. Tuttavia, in presenza di errori di arrotondamento questa affermazione non vale; inoltre, in pratica N può essere molto grande, e il processo iterativo raggiunge una precisione sufficiente già molto prima. L’analisi di questi metodi è difficile, dipendendo da una complicata funzione dello spettro dell’operatore.
PrecondizionatoriModifica
L’operatore approssimato che appare nei metodi iterativi stazionari può anche essere incorporato nei metodi Krylov subspace come il GMRES (in alternativa, i metodi Krylov precondizionati possono essere considerati come accelerazioni dei metodi iterativi stazionari), dove diventano trasformazioni dell’operatore originale in uno presumibilmente meglio condizionato. La costruzione dei precondizionatori è una vasta area di ricerca.
StoriaModifica
Probabilmente il primo metodo iterativo per risolvere un sistema lineare apparve in una lettera di Gauss a un suo studente. Egli propose di risolvere un sistema di equazioni 4 per 4 risolvendo ripetutamente la componente in cui il residuo era il più grande.
La teoria dei metodi iterativi stazionari fu solidamente stabilita con il lavoro di D.M. Young a partire dagli anni 50. Anche il metodo del Gradiente Coniugato è stato inventato negli anni ’50, con sviluppi indipendenti di Cornelius Lanczos, Magnus Hestenes e Eduard Stiefel, ma la sua natura e applicabilità erano incomprese all’epoca. Solo negli anni ’70 si è capito che i metodi basati sulla coniugazione funzionano molto bene per le equazioni differenziali parziali, specialmente quelle di tipo ellittico.