title: Metodo iterativo
text: # 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 $\lim _{k\to \infty }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=MM^{-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)}=Bx^{(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:
  
      $\lim _{k\to \infty }x^{(k)}=x,\forall x^{(0)}\Leftrightarrow \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: $\lim _{k\to \infty }e^{(k)}=0$.
  
  Dalla costruzione del metodo iterativo sappiamo che:
  
  * $x=Bx+c$
  * $x^{(k+1)}=Bx^{(k)}+c$
  
  Sottraiamo la 1 dalla 2 ottenendo:
  
      $x^{(k+1)}-x=Bx^{(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)}=Be^{(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)}=Be^{(0)}$;
  * $e^{(2)}=Be^{(1)}\Rightarrow e^{(2)}=BBe^{(0)}\Rightarrow e^{(2)}=B^{2}e^{(0)}$;
  * $e^{(3)}=Be^{(2)}\Rightarrow e^{(3)}=BB^{2}e^{(0)}\Rightarrow e^{(3)}=B^{3}e^{(0)}$;
  * $e^{(4)}=Be^{(3)}\Rightarrow e^{(4)}=BB^{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:
  
      $\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 $A$ una matrice quadrata, allora
  
      $\lim _{k\to \infty }A^{k}=0\Leftrightarrow \rho (A)<1$
  
  possiamo quindi concludere che $\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 $x^{(0)}$ ma $\rho (B)\geq 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:
  
      $\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 è $e^{(0)}$, non può essere nullo
  
      $\lim _{k\to \infty }\lambda ^{k}e^{(0)}=0\Leftrightarrow \lim _{k\to \infty }\lambda ^{k}=0$
  
  ma ciò è un assurdo dato che $\lambda \geq 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
  