Metodi iterativi

Descrizione e osservazioni introduttive[modifica | modifica wikitesto]

Nei metodi iterativi si crea una successione di vettori , avendo assegnato un vettore iniziale, e una matrice . Il metodo viene iterato finché è un'approssimazione sufficientemente buona della soluzione.

I metodi iterativi sono convenienti quando è una marice sparsa, cioè quando il numero degli elementi diversi da 0 è trascurabile.

Applicando un metodo diretto a matrici di questo tipo, ho il fenomeno del fill in.

I metodi iterativi non alterano la struttura della matrice, e la loro operazione di base è quella di un prodotto matrice per vettore, che costa operazioni se la matrice è piena, e se la matrice è sparsa (vantaggio computazionale).

Per sua natura un metodo iterativo è meno sensibile all'errore algoritmico di un metodo diretto. Supponiamo che le operazioni iterative convergano. A causa dell'errore algoritmico la può variare, ma questo non importa perché con questi metodi non si cerca di calcolare una soluzione esatta, ma solo un'approssimazione.

Il fatto di troncare la successione causa la presenza di un errore analitico, che era assente nei metodi diretti.

Si dice che converge a se questo vale puntualmente, cioè se

Esempio 2.9 (metodo di Jacobi)

Considero la i-esima equazione di un sisema , cioè

ed esplicitando rispetto a ottengo
e al passo successivo ottengo:
In forma compatta, questo metodo si scrive come:
dove
Si ha quindi una scrittura della forma

 

Generalità sulle tecniche di splitting[modifica | modifica wikitesto]

Dato il sistema lineare , , chiamo la soluzione esatta. Considero uno splitting della matrice che viene scritta come , dove sono matrici quadrate e è invertibile.

Applico lo splitting alla matrice nel sistema lineare, cioè

e posso riscrivere
allora pongo e quindi ho il sistema
Il metodo iterativo è
e viene chiamata matrice di iterazione.
Supponiamo che la successione dei vetori converga, allora
Passando al limite nella relazione :
Sottraendo membro a membro le relazioni e ottengo:
dove è l'errore assoluto al passo -esimo, e si ha
Per ogni ,

Convergenza del metodo iterativo[modifica | modifica wikitesto]

Definizione 2.15

Dico che un metodo iterativo è convergente se

per ogni vettore d'innesco .

 

Il metodo iterativo è convergente se e solo se

per ogni , e quindi se

Teorema 2.12 (condizione necessaria e sufficiente per la convergenza)

Il metodo è convergente, cioè

se e solo se .

 
Dimostrazione

: Supponiamo che il metodo sia convergente, allora

Scelgo in modo tale che sia un autovettore rispetto a che realizza il raggio spettrale, quindi
(infatti è autovettore)
allora
e .
:
Caso di diagonalizzabile: può essere scritta come dove è la matrice diagonale con entrate uguali agli autovalori. (la maggior parte delle matrici sono diagonalizzabili)

Allora

e tende a 0 se tende a 0, cioè se e solo se , quindi se e solo se .

Caso generale: per dimostrare questo caso serve la nozione di forma normale di Shur.


Teorema 2.13 (forma normale di Shur)

Data una matrice con autovalori , allora esiste unitaria e una matrice triangolare superiore con elementi diagonali tali che .

 

Se è hermitiana, diventa la matrice degli autovalori.

Considero la forma di Shur di , cioè

Allora considero
e siccome è unitria, , quindi rimane
allora
se e solo se
Inoltre, perché le due matrici sono simili, e si ha
Definisco la matrice in modo che:

  1. sia una matrice diagonale, non negativa
  2. ,
  3. gli elementi diagonali di sono a due a due distinti, cioè richiedo che la matrice sia diagonalizzabile.

Allora, per diagonalizzabile, ho già dimostrato che

se e solo se
Allora per confronto
e segue la tesi.

cvd

 

Suppongo di considerare e di ordinarne gli autovalori per modulo decrescente, in modo che . Allora la matrice è la matrice diagonale con entrate dove

Con questa tecnica riesco a garantire che gli autovalori di sono a due a due distinti.

Altre osservazioni sulla convergenza[modifica | modifica wikitesto]

Vale la seguente proposizione:

Proposizione 2.4

[condizione sufficiente di convergenza] Se esiste una norma matriciale indotta tale che allora il metodo è convergente.

 
Dimostrazione

Dim. Per ogni norma matriciale indotta vale che , allora .

cvd

 


Osservazione 2.6

Supponiamo che esista una norma tale che

(cioè il metodo converge)

Allora, usando la stessa norma, l'errore decresce in modo monotono.

 
Dimostrazione

Consideriamo

Inoltre sappiamo che
e si ha una decrescita monotona anche dell'incremento.

cvd

 

Tuttavia non implica che per qualsiasi norma, e l'errore prima di convergere può avere una crescita iniziale.

Esempio 2.10

Considero una matrice d'iterazione

invece , infatti
e il polinomio caratteristico è
quindi .
Quindi, prima che il metodo converga, l'errore ha una crescita iniziale.

 

Stiamo considerando metodi che generano la successione

tali che . In uno spazio finitodimensionale, non ho la dipendenza dalla norma.

Infatti

e se e solo se .

è l'inf delle norme matriciali indotte della norma di . Questo implica che, se , allora esiste una norma matriciale indotta tale che

quindi
allora per il teorema di Banach ho convergenza.

Siccome tutte le norme in uno spazio finitodimensionale sono topologicamente equivalenti, si ha convergenza rispetto a una qualsiasi norma.

Se , siccome , anche la norma a primo membro tende a 0.

 PrecedenteSuccessivo