Metodo iterativo

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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 | modifica wikitesto]

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 | modifica wikitesto]

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 | modifica wikitesto]

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 | modifica wikitesto]

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 | modifica wikitesto]

Alcuni metodi iterativi particolarmente noti sono:

  1. ^ Quarteroni, pag.112.
  • 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 | modifica wikitesto]
Controllo di autoritàThesaurus BNCF 58822 · LCCN (ENsh85069058 · GND (DE4123457-1 · J9U (ENHE987007565689305171