Metodo iterativo

Da Wikipedia, l'enciclopedia libera.

In analisi numerica un metodo iterativo è un algoritmo di calcolo usato per ottenere l'approssimazione di una soluzione di un problema matematico attraverso un numero teoricamente infinito di passi.

A partire da una stima iniziale, il metodo iterativo passa attraverso approssimazioni successive che convergono alla soluzione esatta solo in senso limite.

Nella risoluzione di sistemi lineari[modifica | modifica sorgente]

I metodi iterativi sono un'alternativa ai metodi diretti per la risoluzione di sistemi lineari, in generale 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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

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:

  1.    x = Bx + c
  2.    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)} = B e^{(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)} = B e^{(0)} ;
  • e^{(2)} = B e^{(1)} \Rightarrow e^{(2)} = B B e^{(0)} \Rightarrow e^{(2)} = B^{2} e^{(0)} ;
  • e^{(3)} = B e^{(2)} \Rightarrow e^{(3)} = B B^{2} e^{(0)} \Rightarrow e^{(3)} = B^{3} e^{(0)};
  • e^{(4)} = B e^{(3)} \Rightarrow e^{(4)} = B B^{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) \ge 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 \ge 1.

Metodi iterativi noti[modifica | modifica sorgente]

Alcuni metodi iterativi particolarmente noti sono:

Note[modifica | modifica sorgente]

  1. ^ Quarteroni, op. cit., pag.112

Bibliografia[modifica | modifica sorgente]

  • Alfio Quarteroni, Riccardo Sacco; Fausto Saleri, Risoluzione di sistemi lineari con metodi iterativi in Matematica numerica, 3a edizione, Milano, Springer Verlag, gennaio 2008, Pagg.111-158, ISBN 978-88-470-0782-6.
  • (EN) Gene H. Golub, Charles F. Van Loan, Itherative methods for linear systems in Matrix computations, 3a edizione, Johns Hopkins University Press, 1996, Pagg.508-554, ISBN 0-8018-5414-8.