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.

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 ${\displaystyle Ax=b}$.

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

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

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

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

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

${\displaystyle x=Bx+c}$

dove ${\displaystyle B}$ viene definita matrice di iterazione.

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

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

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 ${\displaystyle x^{(0)}}$ è che il raggio spettrale (cioè il più grande autovalore in modulo) di B sia strettamente inferiore a 1, in formule:

${\displaystyle \lim _{k\to \infty }x^{(k)}=x,\forall x^{(0)}\Leftrightarrow \rho (B)<1}$

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

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

Dalla costruzione del metodo iterativo sappiamo che:

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

Sottraiamo la 1 dalla 2 ottenendo:

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

Semplifichiamo e mettiamo in evidenza ${\displaystyle B}$ al secondo termine:

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

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

${\displaystyle e^{(k+1)}=Be^{(k)}}$,

ottenendo quindi una definizione di ${\displaystyle e}$ in termini di ${\displaystyle B}$ come relazione di ricorrenza.

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

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

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

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

${\displaystyle \lim _{k\to \infty }B^{k}e^{(0)}=0,\forall x^{(0)}\Leftrightarrow \lim _{k\to \infty }B^{k}=0}$.

Sapendo che esiste un lemma che afferma che: sia ${\displaystyle A}$ una matrice quadrata, allora

${\displaystyle \lim _{k\to \infty }A^{k}=0\Leftrightarrow \rho (A)<1}$

possiamo quindi concludere che ${\displaystyle \lim _{k\to \infty }B^{k}=0\Leftrightarrow \rho (B)<1}$.

Dimostriamo ora il teorema nel verso opposto.

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

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

${\displaystyle \lim _{k\to \infty }B^{k}e^{(0)}=0\Leftrightarrow \lim _{k\to \infty }\lambda ^{k}e^{(0)}=0}$

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

${\displaystyle \lim _{k\to \infty }\lambda ^{k}e^{(0)}=0\Leftrightarrow \lim _{k\to \infty }\lambda ^{k}=0}$

ma ciò è un assurdo dato che ${\displaystyle \lambda \geq 1}$.

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

• Alfio Quarteroni, Riccardo Sacco; Fausto Saleri, Risoluzione di sistemi lineari con metodi iterativi, in Matematica numerica, 3ª edizione, Milano, Springer Verlag, gennaio 2008, Pagg.111-158, ISBN 978-88-470-0782-6.
• (EN) Gene H. Golub, Charles F. Van Loan, Iterative methods for linear systems, in Matrix computations, 3ª edizione, Johns Hopkins University Press, 1996, Pagg.508-554, ISBN 0-8018-5414-8.

• Wikimedia Commons contiene immagini o altri file su metodo numerico iterativo

Portale Ingegneria

Portale Matematica