Metodo iterativo

In analisi numerica un metodo numerico iterativo è un tipo di metodo numerico nel quale le successive approssimazioni della soluzione al problema matematico esaminato sono ottenute a partire dalle precedenti. Ciò comporta che un metodo numerico iterativo necessiti di una stima iniziale (valori di starting) sul quale innestarsi e la possibilità che le approssimazioni convergano solo alla soluzione, ovvero che non sia possibile giungere alla soluzione esatta in un numero finito di passi.

Nella risoluzione di sistemi lineari

I metodi iterativi sono un'alternativa ai metodi diretti per la risoluzione di sistemi lineari; in generale sono preferibili a questi perché più efficienti o più stabili, soprattutto quando si devono trattare matrici di dimensioni considerevoli o matrici sparse.

Si ricorda che, in quanto si parla di un sistema lineare, bisogna cercare di risolvere un problema del tipo $Ax=b$.

I metodi iterativi partono da un dato iniziale arbitrario $x^{(0)}$ e sono fatti in modo che $\underset{k\to \mathrm{\infty }}{\lim }{x}^{(k)}=x$, dove $x$ è la soluzione esatta del sistema (proprietà di convergenza). Trattandosi di vettori si parla di convergenza in norma.

Costruzione di un metodo iterativo per la risoluzione di un sistema lineare

Dato che lo scopo finale del metodo iterativo è la risoluzione del sistema $Ax=b$ si parte proprio da questa uguaglianza, o, più comodamente $b-Ax=0$.

Si supponga poi di prendere una matrice $M$ non singolare (cioè invertibile); sommando $Mx$ ad ambo i membri si ha che:

• $Mx+(b-Ax)=Mx$
• moltiplicando ambo i membri per l'inversa di $M$ si ottiene:
• $M^{-1}(Mx+b-Ax)=M^{-1}Mx$
• sapendo che $M^{-1}M=M{M}^{-1}=I$ e che $Ix=xI=x$, si opera sul secondo membro e si invertono i membri:
• $x=M^{-1}(Mx+b-Ax)$
• si sviluppa la moltiplicazione al secondo membro:
• $x=M^{-1}Mx+M^{-1}b-M^{-1}Ax$
• si mette in evidenza la x nel secondo membro:
• $x=x(I-M^{-1}A)+M^{-1}b$

Se, in questa uguaglianza, sostituiamo $B=I-M^{-1}A$ e $c=M^{-1}b$, si ottiene quindi che:

$x=Bx+c$

dove $B$ viene definita matrice di iterazione.

Questo risultato vale per qualunque matrice M non singolare e quindi si ha che $x^{(k+1)}=B{x}^{(k)}+c$.

Con questa regola ricorsiva si può procedere da un $x^{(0)}$ fissato.

Analisi di convergenza

Dopo aver costruito un metodo iterativo è opportuno domandarsi se la scelta di M è stata opportuna, cioè se dopo infinite iterazioni la soluzione ottenuta è realmente quella del sistema (la proprietà di convergenza di cui sopra).

Condizione necessaria e sufficiente affinché il metodo converga alla soluzione del sistema per ogni scelta di $x^{(0)}$ è che il raggio spettrale (cioè il più grande autovalore in modulo) di B sia strettamente inferiore a 1, in formule:

$\underset{k\to \mathrm{\infty }}{\lim }{x}^{(k)}=x,\mathrm{\forall }{x}^{(0)}\iff \rho (B)<1$

Dimostrazione

Essendo il teorema un se e solo se, la dimostrazione si svolge in due fasi.

Definiamo con $e^{(k)}$ l'errore della soluzione al passo $k$, cioè $x-x^{(k)}$ e notiamo che dire che il metodo converge equivale a dire che l'errore tende a zero: $\underset{k\to \mathrm{\infty }}{\lim }{e}^{(k)}=0$.

Dalla costruzione del metodo iterativo sappiamo che:

1.    $x=Bx+c$
2.    $x^{(k+1)}=B{x}^{(k)}+c$

Sottraiamo la 1 dalla 2 ottenendo:

$x^{(k+1)}-x=B{x}^{(k)}+c-Bx-c$.

Semplifichiamo e mettiamo in evidenza $B$ al secondo termine:

$x^{(k+1)}-x=B(x^{(k)}-x)$.

In base alla definizione dell'errore $e^{(k)}$ di cui sopra, possiamo riscrivere l'equazione come

$e^{(k+1)}=B{e}^{(k)}$,

ottenendo quindi una definizione di $e$ in termini di $B$ come relazione di ricorrenza.

Proviamo a sviluppare tale relazione di ricorrenza per ottenere una nuova definizione di $e$ in termini di $B$ che non sia ricorsiva ma diretta; procediamo quindi:

• $e^{(0)}$ è la base della relazione di ricorrenza e dipenderà dalla scelta di $x^{(0)}$;
• $e^{(1)}=B{e}^{(0)}$;
• $e^{(2)}=B{e}^{(1)}\Rightarrow e^{(2)}=BB{e}^{(0)}\Rightarrow e^{(2)}=B^2{e}^{(0)}$;
• $e^{(3)}=B{e}^{(2)}\Rightarrow e^{(3)}=B{B}^2{e}^{(0)}\Rightarrow e^{(3)}=B^3{e}^{(0)}$;
• $e^{(4)}=B{e}^{(3)}\Rightarrow e^{(4)}=B{B}^3{e}^{(0)}\Rightarrow e^{(4)}=B^4{e}^{(0)}$;
• ...

Possiamo quindi riscrivere la relazione come $e^{(k)}=B^k{e}^{(0)}$.

Dall'osservazione di cui sopra quindi il metodo convergerà se:

$\underset{k\to \mathrm{\infty }}{\lim }{B}^k{e}^{(0)}=0,\mathrm{\forall }{x}^{(0)}\iff \underset{k\to \mathrm{\infty }}{\lim }{B}^k=0$.

Sapendo che esiste un lemma che afferma che: sia $A$ una matrice quadrata, allora

$\underset{k\to \mathrm{\infty }}{\lim }{A}^k=0\iff \rho (A)<1$

possiamo quindi concludere che $\underset{k\to \mathrm{\infty }}{\lim }{B}^k=0\iff \rho (B)<1$.

Dimostriamo ora il teorema nel verso opposto.

Supponiamo per assurdo che il metodo converga per ogni scelta di $x^{(0)}$ ma $\rho (B)\ge 1$, cioè che almeno un autovalore di $B$ in modulo sia maggiore o uguale di 1. Denotiamo tale autovalore con $\lambda$.

Potendo scegliere arbitrariamente $x^{(0)}$, scegliamo quel $x^{(0)}$ tale che $e^{(0)}$ sia l'autovettore di $\lambda$. Ciò significa che:

$\underset{k\to \mathrm{\infty }}{\lim }{B}^k{e}^{(0)}=0\iff \underset{k\to \mathrm{\infty }}{\lim }{\lambda }^k{e}^{(0)}=0$

dato che per definizione un autovettore, quale è $e^{(0)}$, non può essere nullo

$\underset{k\to \mathrm{\infty }}{\lim }{\lambda }^k{e}^{(0)}=0\iff \underset{k\to \mathrm{\infty }}{\lim }{\lambda }^k=0$

ma ciò è un assurdo dato che $\lambda \ge 1$.

Metodi iterativi noti

Alcuni metodi iterativi particolarmente noti sono:

• il metodo di Newton: per la soluzione di equazioni
• il metodo di Jacobi, il metodo di Gauss-Seidel e il metodo del rilassamento: per la soluzione di sistemi lineari
• l'algoritmo del simplesso: per la soluzione di problemi di programmazione lineare

Bibliografia

• Template:Cita libro
• Template:Cita libro