Introduzione

Per quanto i metodi diretti consentano di ottenere con certezza il risultato preciso (a meno di errori inerenti e algoritmici) dell'equazione $Ax=b$, quando si ha a che fare con matrici molto grandi il loro costo computazionale potrebbe diventare insostenibile, per questo si fa ricorso ai metodi iterativi. In particolare si preferiscono i metodi iterativi quando:

• $n$ è molto grande;
• $A$ possiede particolari proprietà o strutture;

Come dicevamo, il costo computazionale è minore rispetto ai metodi diretti, ma l'errore è maggiore! Infatti oltre all'errore inerente e all'errore algoritmico, vi si aggiunge anche l'errore di troncamento.

Difatti questi sono metodi basati sull'iterazione, $x_k=G(x_{k-1})$, il concetto di fondo è costruire una successione che converge alla soluzione $x^*$ per $k\rarr\infty$.

Per questo motivo è importante sapere quando è opportuno fermarsi.

Criteri di arresto

Solitamente si decide quando fermare l'algoritmo con una serie di criteri che hanno tutti la forma di:

1. condizione 1 < $\Tau_1$ (tau);
2. condizione 2 z $\Tau_2$;
3. ecc.

Per eliminare il rischio di finire in cicli infiniti si pone anche un freno di emergenza, $k_{max}$, che interrompe il ciclo quando $k=k_{max}$. In questo caso sicuramente bisogna riguardare le tolleranze scelte e nel caso irrigidirle.

Schema generico di un algoritmo iterativo

1. Dati in input $x$;

2. $k=1$;

3. while (convergenza) {

   1. $x_k=G(x_{k-1})$
   2. $k = k+1$

   } end.

Ciò che cambia in genere sono le condizioni di convergenza.