Metodi di rilassamento

Definizione del metodo

Definiamo il metodo di Gauss-Seidel come:

Possiamo scrivere con . La nuova iterata è il punto in che otteniamo a partire da facendo un passo di lunghezza nella direzione di .


Viene definita una nuova classe di metodi, detti di rilassamento, dove

dove si fa un passo di lunghezza .


Se ho un sottorilassamento, mentre se ho un soprarilassamento.


Un metodo di questo tipo viene chiamato SOR.


Sostituisco nella relazione che definisce il metodo SOR l'espressione di che deriva da Gauss-Seidel.

e mettendo in evidenza si ha:
Raccogliendo tutti i termini che moltiplicano :
Moltiplicando per :
Allora
è la matrice di iterazione, invece
Allora
Considerando la i-esima componente:
e per si ha il metodo di Gauss-Seidel.

Il costo computazionale di questo metodo è vicino a quello di Gauss-Seidel.

Ottimizzazione del metodo

Si vuole determinare l' ottimale, tale per cui il metodo converge più velocemente.


Teorema 2.16

[teorema di Kan] Condizione necessaria per la convergenza del SOR è che , ovvero se è reale.

 


Dim. La matrice di iterazione è

è una matrice triangolare inferiore con elementi sulla diagonale principale, e il determinante è uguale al prodotto degli elementi sulla diagonale, cioè è uguale a .


La matrice è una triangolare superiore con elementi diagonali mentre la parte triangolare ha entrate . Il determinante è ancora dato dal prodotto degli elementi sulla diagonale principale, e quindi è .


Per il teorema di Binet:

Inoltre
Siccome ciascun autovalore di è minore del raggio spettrale, si ha
e se deve esserci convergenza dev'essere
allora la relazione implica .


cvd


Vale la seguente condizione sufficiente per la convergenza:

Teorema 2.17

Se è definita positiva e allora il metodo SOR è convergente.

 


Nel caso delle matrici tridiagonali vale il seguente teorema:

Teorema 2.18

Sia tridiagonale. Se (matrice d'iterazione di Jacobi) è tale che , e ha autovalori reali, allora esiste ed è unico tale che

 

Sappiamo che .


E' possibile rappresentare la variazione del raggio spettrale in funzione di : traccio un grafico con in ascissa e in ordinata, allora il grafico scende, ha una cuspide in e poi risale in maniera lineare. Per , . Conviene stare a destra di , perché in questo modo il raggio spettrale sarà più grande di poco, invece a sinisra si è in prossimità della cuspide e il valore varia di molto. Conviene approssimare per eccesso.

 Precedente