Calcolo numerico/Metodi di rilassamento

Definizione del metodo

Definiamo il metodo di Gauss-Seidel come:

${𝒙}_k=D^{-1}(𝒃-L{𝒙}_k-U{𝒙}_{k-1})$

Possiamo scrivere ${𝒙}_k={𝒙}_{k-1}+{𝒗}_k$ con ${𝒗}_k={𝒙}_k-{𝒙}_{k-1}$. La nuova iterata è il punto in ${ℂ}_n$ che otteniamo a partire da ${𝒙}_{k-1}$ facendo un passo di lunghezza $|{𝒗}_k|$ nella direzione di ${𝒗}_k$.

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

${𝒙}_k={𝒙}_{k-1}+\omega \ast {𝒗}_k$

dove si fa un passo di lunghezza $\omega \ast |{𝒗}_k|$.

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 ${𝒗}_k$ che deriva da Gauss-Seidel.

${𝒙}_k={𝒙}_{k-1}+\omega \ast ({𝒙}_k-{𝒙}_{k-1})=(1-\omega ){𝒙}_{k-1}+\omega {𝒙}_k$

$=(1-\omega ){𝒙}_{k-1}+\omega (D^{-1}(𝒃-L{𝒙}_k-U{𝒙}_{k-1}))$

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

${𝒙}_k=D^{-1}[(1-\omega )D\ast {𝒙}_{k-1}+\omega 𝒃-\omega L{𝒙}_k-\omega U{𝒙}_{k-1}]$

Raccogliendo tutti i termini che moltiplicano ${𝒙}_k$:

$(I+\omega D^{-1}L){𝒙}_k=D^{-1}((1-\omega )D-\omega U){𝒙}_{k-1}+\omega D^{-1}𝒃$

Moltiplicando per $D$:

$(D+\omega L){𝒙}_k=((1-\omega )D-\omega U){𝒙}_{k-1}+\omega 𝒃$

Allora

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

è la matrice di iterazione, invece

$𝒄=\omega (D+\omega L{)}^{-1}𝒃$

Allora

$D{𝒙}_k=((1-\omega )D-\omega U){𝒙}_{k-1}-\omega L{𝒙}_k+\omega 𝒃$

Considerando la $i$-esima componente:

$x_i^{(k)}=(1-\omega )x_i^{(k-1)}+\frac{\omega }{A_{ii}\ast [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}\ast ((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 $detD$.

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}detD$.

Per il teorema di Binet:

$det{P}_{\omega }=det[(1-\omega )D-\omega U]\ast \frac{1}{det(D+\omega L)}=\frac{(1-\omega {)}^n\ast detD}{detD}=(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\le {\rho }^n(P_{\omega })$

e se deve esserci convergenza dev'essere

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

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

cvd

Nel caso delle matrici tridiagonali vale il seguente teorema:

Teorema 2.18

Sia $A\in {ℂ}_{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 })=\underset{\omega \in (0,2)}{min}\{\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.