Esercizio - Gauss-Seidel a mano e confronto con Jacobi

Teoria: Metodi iterativi - Jacobi, Gauss-Seidel e convergenzaSi spezza $A=M-N$ con $M$ facile da invertire e si itera $M\mathbf x^{(k+1)}=N\mathbf x^{(k)}+\mathbf b$, cioè $\mathbf x^{(k+1)}=B\mathbf x^{(k)}+\mathbf c$ con $B=M^{-1}N=I-M^{-1}A$. Con $A=D+L+U$ (diagonale, parte strettamente inferiore e superiore): Jacobi $M=D$, $x_i^{(k+1)}=\frac1{a_{ii}}\big(b_i-\sum_{j\ne i}a_{ij}x_j^{(k)}\big)$; Gauss-Seidel $M=D+L$, usa subito i valori nuovi $x_j^{(k+1)}$, $j<i$. Convergenza per ogni $\mathbf x^{(0)}$ se e solo se $\rho(B)<1$ (D); basta $|B|<1$. Matrice a dominanza diagonale stretta per righe: convergono entrambi; $A$ SPD: converge Gauss-Seidel; per matrici tridiagonali $\rho(B_{GS})=\rho(B_J)^2$. Errore: $\mathbf e^{(k)}=B^k\mathbf e^{(0)}$, $|\mathbf e^{(k)}|\le|B|^k|\mathbf e^{(0)}|$ e $|\mathbf x-\mathbf x^{(k)}|\le\frac{|B|}{1-|B|}|\mathbf x^{(k)}-\mathbf x^{(k-1)}|$. Per guadagnare $d$ cifre servono $k\approx\frac d{-\log_{10}\rho(B)}$ iterazioni.Metodi iterativi - Jacobi, Gauss-Seidel e convergenza →. Il sistema è quello di Esercizio - Jacobi a mano, dominanza diagonale e stima del numero di iterazioni.

Testo. Per $$\begin{pmatrix}8&-1&1\\2&10&-1\\1&1&5\end{pmatrix}\mathbf x=\begin{pmatrix}11\\-10\\10\end{pmatrix}\qquad(\mathbf x=(1,-1,2)^T)$$

1. Eseguire due iterazioni di Gauss-Seidel da $\mathbf x^{(0)}=\mathbf 0$.
2. Confrontare gli errori con quelli di Jacobi (iterazioni $1$ e $2$: $0{,}375$ e $0{,}075$ in norma $\infty$).
3. Scrivere $M$ e $N$ del metodo e dire quanti sistemi triangolari si risolvono a ogni passo.
4. Sapendo che $\rho(B_J)=0{,}2151$ e $\rho(B_{GS})=0{,}05$ (calcolati numericamente), stimare quante iterazioni di ciascun metodo servono per guadagnare 6 cifre.

Soluzione

1. Iterazioni di Gauss-Seidel. Ogni componente usa i valori appena calcolati: $$x_1^{(k+1)}=\frac{11+x_2^{(k)}-x_3^{(k)}}8,\quad x_2^{(k+1)}=\frac{-10-2x_1^{(k+1)}+x_3^{(k)}}{10},\quad x_3^{(k+1)}=\frac{10-x_1^{(k+1)}-x_2^{(k+1)}}5 .$$

• $\mathbf x^{(1)}$: $x_1=\frac{11+0-0}8=1{,}375$; $x_2=\frac{-10-2\cdot1{,}375+0}{10}=-1{,}275$; $x_3=\frac{10-1{,}375-(-1{,}275)}5=\frac{9{,}9}5=1{,}98$.
• $\mathbf x^{(2)}$: $x_1=\frac{11+(-1{,}275)-1{,}98}8=\frac{7{,}745}8=0{,}968125$; $x_2=\frac{-10-2\cdot0{,}968125+1{,}98}{10}=\frac{-9{,}95625}{10}=-0{,}995625$; $x_3=\frac{10-0{,}968125+0{,}995625}5=\frac{10{,}0275}5=2{,}0055$.

2. Confronto. Errori in norma $\infty$ (esatto $(1,-1,2)$):

3. Splitting. $M=D+L=\begin{pmatrix}8&0&0\\2&10&0\\1&1&5\end{pmatrix}$, $N=-U=\begin{pmatrix}0&1&-1\\0&0&1\\0&0&0\end{pmatrix}$. A ogni passo si risolve $M\mathbf x^{(k+1)}=N\mathbf x^{(k)}+\mathbf b$, un sistema triangolare inferiore (sostituzione in avanti), esattamente le tre formule sopra: la memoria di un solo vettore basta perché ogni $x_i$ nuovo sostituisce il vecchio.

4. Numero di iterazioni. Per guadagnare 6 cifre: $$k_J\approx\frac6{-\log_{10}0{,}2151}=\frac6{0{,}667}=9{,}0\ \ (\text{9 iterazioni}),\qquad k_{GS}\approx\frac6{-\log_{10}0{,}05}=\frac6{1{,}301}=4{,}6\ \ (\text{5 iterazioni}).$$ Gauss-Seidel richiede circa la metà delle iterazioni. Confronto con la tabella: l'errore di Gauss-Seidel scende di un fattore $\approx0{,}05$–$0{,}14$ per iterazione ($0{,}0319\to0{,}00058\to0{,}000083$ ha rapporti $0{,}018$ e $0{,}14$: gli autovalori complessi $-0{,}0125\pm0{,}0484i$ fanno oscillare i rapporti attorno a $\rho=0{,}05$).

Risultati: $\mathbf x^{(2)}_{GS}=(0{,}968125;\ -0{,}995625;\ 2{,}0055)$, errore $0{,}0319$ contro $0{,}075$ di Jacobi; 5 iterazioni contro 9 per 6 cifre.

Errori tipici. Calcolare $x_2^{(k+1)}$ con il vecchio $x_1^{(k)}$ (è Jacobi); sbagliare il segno di $a_{23}=-1$ (nel calcolo di $x_2$ compare $+x_3$); aspettarsi che Gauss-Seidel sia sempre migliore (non lo è per ogni matrice).