Metodi di rilassamento

Definizione del metodo[modifica | modifica wikitesto]

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

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.

 


Vale la seguente condizione sufficiente per la convergenza:

Teorema 2.17 (Teorema di Ostrosky-Right)

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

 
Dimostrazione

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

 

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