Calcolo numerico/Metodi di rilassamento

Definizione del metodo

Definiamo il metodo di Gauss-Seidel come:

${\boldsymbol {x}}_{k}=D^{-1}({\boldsymbol {b}}-L{\boldsymbol {x}}_{k}-U{\boldsymbol {x}}_{k-1})$

Possiamo scrivere ${\boldsymbol {x}}_{k}={\boldsymbol {x}}_{k-1}+{\boldsymbol {v}}_{k}$ con ${\boldsymbol {v}}_{k}={\boldsymbol {x}}_{k}-{\boldsymbol {x}}_{k-1}$. La nuova iterata è il punto in $\mathbb {C} _{n}$ che otteniamo a partire da ${\boldsymbol {x}}_{k-1}$ facendo un passo di lunghezza $\vert {\boldsymbol {v}}_{k}\vert$ nella direzione di ${\boldsymbol {v}}_{k}$.

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

${\boldsymbol {x}}_{k}={\boldsymbol {x}}_{k-1}+\omega *{\boldsymbol {v}}_{k}$

dove si fa un passo di lunghezza $\omega *\vert {\boldsymbol {v}}_{k}\vert$.

Se $\omega <1$ abbiamo un sottorilassamento, mentre se $\omega >1$ abbiamo un soprarilassamento.

Un metodo di questo tipo viene chiamato SOR.

Sostituiamo nella relazione che definisce il metodo SOR l'espressione di ${\boldsymbol {v}}_{k}$ che deriva da Gauss-Seidel.

${\boldsymbol {x}}_{k}={\boldsymbol {x}}_{k-1}+\omega *({\boldsymbol {x}}_{k}-{\boldsymbol {x}}_{k-1})=(1-\omega ){\boldsymbol {x}}_{k-1}+\omega {\boldsymbol {x}}_{k}$

$=(1-\omega ){\boldsymbol {x}}_{k-1}+\omega (D^{-1}({\boldsymbol {b}}-L{\boldsymbol {x}}_{k}-U{\boldsymbol {x}}_{k-1}))$

e mettendo in evidenza $D^{-1}$ si ha:

${\boldsymbol {x}}_{k}=D^{-1}[(1-\omega )D*{\boldsymbol {x}}_{k-1}+\omega {\boldsymbol {b}}-\omega L{\boldsymbol {x}}_{k}-\omega U{\boldsymbol {x}}_{k-1}]$

Raccogliendo tutti i termini che moltiplicano ${\boldsymbol {x}}_{k}$:

$(I+\omega D^{-1}L){\boldsymbol {x}}_{k}=D^{-1}((1-\omega )D-\omega U){\boldsymbol {x}}_{k-1}+\omega D^{-1}{\boldsymbol {b}}$

Moltiplicando per $D$:

$(D+\omega L){\boldsymbol {x}}_{k}=((1-\omega )D-\omega U){\boldsymbol {x}}_{k-1}+\omega {\boldsymbol {b}}$

Allora

$P=(D+\omega L)^{-1}*((1-\omega )D-\omega U)$

è la matrice di iterazione, invece

${\boldsymbol {c}}=\omega (D+\omega L)^{-1}{\boldsymbol {b}}$

Allora

$D{\boldsymbol {x}}_{k}=((1-\omega )D-\omega U){\boldsymbol {x}}_{k-1}-\omega L{\boldsymbol {x}}_{k}+\omega {\boldsymbol {b}}$

Considerando la $i$-esima componente:

$x_{i}^{(k)}=(1-\omega )x_{i}^{(k-1)}+{\frac {\omega }{A_{ii}*[b_{i}-\sum _{j}<i}}a_{ij}x_{j}^{(k)}-\sum {j>i}a_{ij}x_{j}^{(k+1)}]$

e per $\omega =1$ 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'$\omega$ ottimale, tale per cui il metodo converge più velocemente.

Teorema 2.16 (teorema di Kan)

Condizione necessaria per la convergenza del SOR è che $|\omega -1|<1$, ovvero $\omega \in (0,2)$ se $\omega$ è reale.

Vale la seguente condizione sufficiente per la convergenza:

Teorema 2.17 (Teorema di Ostrosky-Right)

Se $A$ è definita positiva e $\omega \in (0,2)$ allora il metodo SOR è convergente.

Dimostrazione

La matrice di iterazione è

$P_{\omega }=(D+\omega L)^{-1}*((1-\omega )D-\omega U)$

$D+\omega L$ è una matrice triangolare inferiore con elementi $a_{11},\dots a_{nn}$ sulla diagonale principale, e il determinante è uguale al prodotto degli elementi sulla diagonale, cioè è uguale a $\det D$.

La matrice $(1-\omega )D-\omega U$ è una triangolare superiore con elementi diagonali $(1-\omega )a_{11},\dots ,(1-\omega )a_{nn}$ mentre la parte triangolare ha entrate $\omega a_{ij}$. Il determinante è ancora dato dal prodotto degli elementi sulla diagonale principale, e quindi è $(1-\omega )^{n}\det D$.

Per il teorema di Binet:

$\det P_{\omega }=\det[(1-\omega )D-\omega U]*{\frac {1}{\det(D+\omega L)}}={\frac {(1-\omega )^{n}*\det D}{\det D}}=(1-\omega )^{n}$

Inoltre

$\det P_{\omega }=\prod _{i=1}^{n}\lambda _{i}(P_{\omega })=$

Siccome ciascun autovalore di $P_{\omega }$ è minore del raggio spettrale, si ha

$|1-\omega |^{n}\leq \rho ^{n}(P_{\omega })$

e se deve esserci convergenza dev'essere

$\rho (P_{\omega })\leq 1$

allora la relazione implica $|1-\omega |\leq 1$.

cvd

Nel caso delle matrici tridiagonali vale il seguente teorema:

Teorema 2.18

Sia $A\in \mathbb {C} _{n,n}$ tridiagonale. Se $P_{j}$ (matrice d'iterazione di Jacobi) è tale che $\rho (P_{j})<1$, e ha autovalori reali, allora esiste ed è unico $\omega ^{\ast }$ tale che

$\rho (P_{\omega }^{\ast })=\min _{\omega \in (0,2)}\{\rho (P_{\omega })\}$

Sappiamo che $\omega ^{\ast }={\frac {2}{1+{\sqrt {1-\rho ^{2}(P_{j})}}}}$.

È possibile rappresentare la variazione del raggio spettrale in funzione di $\omega$: traccio un grafico con $\omega$ in ascissa e $p_{\omega }$ in ordinata, allora il grafico scende, ha una cuspide in $\omega ^{\ast }$ e poi risale in maniera lineare.

Per $\omega >\omega ^{\ast }$, $\rho (P(\omega ^{\ast }))=\omega -1$.

Conviene stare a destra di $\omega ^{\ast }$, perché in questo modo il raggio spettrale sarà più grande di poco, invece a sinistra si è in prossimità della cuspide e il valore varia di molto. Conviene approssimare per eccesso.