Metodo iterativo

In analisi numerica un metodo iterativo è un algoritmo di calcolo usato per ottenere l'approssimazione di una soluzione di un problema matematico attraverso un numero teoricamente infinito di passi. I metodi iterativi sono spesso usati in analisi numerica.

A partire da una stima iniziale, il metodo iterativo passa attraverso approssimazioni successive che convergono alla soluzione esatta solo in senso limite.

Nella risoluzione di sistemi lineari

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

Si ricorda che, in quanto si parla di un sistema lineare, bisogna cercare di risolvere un problema del tipo $Ax^{*}=b$ ($x^{*}$ è la soluzione esatta del sistema).

I metodi iterativi partono da un punto assegnato $x^{(0)}$ e sono fatti in modo che $\lim _{k\to \infty }x^{(k)}=x^{*}$. Poiché si parla 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), si ha quindi che:

$Mx+(b-Ax)=Mx$

$M^{-1}(Mx+b-Ax)=M^{-1}Mx$

$x=M^{-1}Mx+M^{-1}b-M^{-1}Ax$.

Il risultato finale è quindi $x=x(I-M^{-1}A)+M^{-1}b$. Se, in questa uguaglianza, sostituiamo $G=I-M^{-1}A$ e $c=M^{-1}b$, si ottiene quindi che:

$x=Gx+c$.

Questo risultato vale per qualunque matrice M non singolare e quindi si ha che $x^{(k+1)}=Gx^{(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.

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

• Alfio Quarteroni, Riccardo Sacco; Fausto Saleri, Risoluzione di sistemi lineari con metodi iterativi, in Matematica numerica, 3^a edizione, Milano, Springer Verlag, gennaio 2008, Pagg.111-158, ISBN 978-88-470-0782-6.