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 .
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
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
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
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:
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
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
Note
- ^ Quarteroni, pag.112.
Bibliografia
- 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
Altri progetti
- Wikimedia Commons
Wikimedia Commons contiene immagini o altri file su metodo numerico iterativo
Controllo di autorità | Thesaurus BNCF 58822 · LCCN (EN) sh85069058 · GND (DE) 4123457-1 · J9U (EN, HE) 987007565689305171 |
---|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Crystal_kcontrol_2.svg/23px-Crystal_kcontrol_2.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)