Larpanet

Metodi Iterativi

I metodi iterativi per la soluzione di sistemi lineari ${\displaystyle Ax=b}$  sono dei procedimenti attraverso cui si costruisce una successione ${\displaystyle x^{(k)}}$  di approssimanti della soluzione vera ${\displaystyle x_{v}:=A^{-1}b}$  a partire da una soluzione tentativo ${\displaystyle x^{(0)}}$ .

La successione ${\displaystyle x^{(k)}}$  converge alla soluzione vera soltanto al limite:

${\displaystyle \lim _{k\rightarrow \infty }x^{(k)}=x_{v}}$ 

questa condizione equivale alla seguente:

${\displaystyle \lim _{k\rightarrow \infty }||x^{(k)}-x_{v}||=0}$ 

Possiamo riscrivere ancora in un altro modo la condizione di convergenza. Se definiamo l'errore commesso al passo ${\displaystyle k}$ -mo nel seguente modo:

${\displaystyle e^{(k)}:=x^{(k)}-x_{v}}$ 

allora la convergenza di ${\displaystyle x^{(k)}}$  si scrivera' cosi':

${\displaystyle x^{(k)}\rightarrow x_{v}\Leftrightarrow \lim _{k\rightarrow \infty }||e^{(k)}||=0}$ 

Generalmente, ad una formula atta a costruire una successione di approssimanti, si richiede la convergenza al limite (incondizionata, cioe' a prescindere dalla soluzione tentativo iniziale scelta) e la cosiddetta consistenza esclusiva.

Si dice che una successione di approssimanti ${\displaystyle x^{(k)}}$  e' consistente se:

${\displaystyle x^{(k)}=x_{v}\Rightarrow x^{(k)}=x^{(k+1)}}$ 

si dice poi che la consistenza e' esclusiva quando vale pure il viceversa:

${\displaystyle x^{(k)}=x_{v}\Leftarrow x^{(k)}=x^{(k+1)}}$ 

Percio' diciamo che una certa successione ${\displaystyle x^{(k)}}$  e' convergente (incondizionatamente) e consistente in maniera esclusiva quando si verificano entrambe queste condizioni:

convergenza incondizionata

${\displaystyle \lim _{k\rightarrow \infty }||x^{(k)}-x_{v}||=0}$ 

consistenza esclusiva

${\displaystyle x^{(k)}=x_{v}\Leftrightarrow x^{(k)}=x^{(k+1)}}$ 

Metodi iterativi convergenti e consistenti

Si pone il problema di costruire dei metodi iterativi per risolvere ${\displaystyle Ax=b}$  che siano consistenti e convergenti.

Ebbene, esiste una formula che, sotto opportune condizioni, permette di costruire una famiglia di metodi iterativi. Questa formula (dovuta a Wittmeyer) e' il paradigma dei metodi iterativi per risolvere sistemi lineari.

La formula-modello in questione e' la seguente:

${\displaystyle x^{(k+1)}=x^{(k)}+M(Ax^{(k)}-b)}$ 

Per ogni scelta della matrice ${\displaystyle M}$  o della matrice ${\displaystyle B:=I+MA}$  che e' detta matrice di iterazione, si ottiene un particolare metodo iterativo.

Condizioni di consistenza e convergenza

Si puo' dimostrare che la formula:

${\displaystyle x^{(k+1)}=x^{(k)}+M(Ax^{(k)}-b)}$ 

con l'ipotesi che ${\displaystyle M}$  sia non singolare (${\displaystyle \det(M)\neq 0}$ ) e che il raggio spettrale di ${\displaystyle B}$  sia strettamente minore di 1 (${\displaystyle \rho (B)<1}$ ), fornisce metodi iterativi convergenti e consistenti.

Piu' precisamente si dimostrano queste due proprieta' per una qualsiasi successione ${\displaystyle x^{(k)}}$  generata dalla formula-modello:

${\displaystyle \det(M)\neq 0\Leftrightarrow x^{(k)}}$  consistente esclusivamente

${\displaystyle \rho (B)<1\Leftrightarrow \lim _{k\leftarrow \infty }x^{(k)}=x_{v}}$