Metodo iterativo

metodo numerico nel quale l'n-esima approssimazione della soluzione del problema si ricava a partire dalle precedenti (n-1) approssimazioni precedenti

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

modifica

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  .

I metodi iterativi partono da un dato iniziale arbitrario   e sono fatti in modo che  , dove   è 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

modifica

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

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

  •  
  • moltiplicando ambo i membri per l'inversa di   si ottiene:
  •  
  • sapendo che   e che  , si opera sul secondo membro e si invertono i membri:
  •  
  • si sviluppa la moltiplicazione al secondo membro:
  •  
  • si mette in evidenza la x nel secondo membro:
  •  

Se, in questa uguaglianza, sostituiamo   e  , si ottiene quindi che:

 

dove   viene definita matrice di iterazione.

Questo risultato vale per qualunque matrice M non singolare e quindi si ha che  .

Con questa regola ricorsiva si può procedere da un   fissato.

Analisi di convergenza

modifica

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

 

Dimostrazione

modifica

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

Definiamo con   l'errore della soluzione al passo  , cioè   e notiamo che dire che il metodo converge equivale a dire che l'errore tende a zero:  .

Dalla costruzione del metodo iterativo sappiamo che:

  1.     
  2.     

Sottraiamo la 1 dalla 2 ottenendo:

 .

Semplifichiamo e mettiamo in evidenza   al secondo termine:

 .

In base alla definizione dell'errore   di cui sopra, possiamo riscrivere l'equazione come

 ,

ottenendo quindi una definizione di   in termini di   come relazione di ricorrenza.

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

  •   è la base della relazione di ricorrenza e dipenderà dalla scelta di  ;
  •  ;
  •  ;
  •  ;
  •  ;
  • ...

Possiamo quindi riscrivere la relazione come  .

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

 .

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

 

possiamo quindi concludere che  .

Dimostriamo ora il teorema nel verso opposto.

Supponiamo per assurdo che il metodo converga per ogni scelta di   ma  , cioè che almeno un autovalore di   in modulo sia maggiore o uguale di 1. Denotiamo tale autovalore con  .

Potendo scegliere arbitrariamente  , scegliamo quel   tale che   sia l'autovettore di  . Ciò significa che:

 

dato che per definizione un autovettore, quale è  , non può essere nullo

 

ma ciò è un assurdo dato che  .

Metodi iterativi noti

modifica

Alcuni metodi iterativi particolarmente noti sono:

  1. ^ Quarteroni, pag.112.

Bibliografia

modifica
  • 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.

Altri progetti

modifica
Controllo di autoritàThesaurus BNCF 58822 · LCCN (ENsh85069058 · GND (DE4123457-1 · J9U (ENHE987007565689305171