Esempi sui metodi iterativi

Esercizio 8.7

Considero la matrice $A=I-B$$A=I-B$, con

$$B={\begin{array}{ccc}0&0&\alpha \\\beta &0&0\\0&\gamma &0\end{array}}$$

$$B={\begin{array}{ccc}0&0&\alpha \\\beta &0&0\\0&\gamma &0\end{array}}$$

con $\alpha ,\beta ,\gamma \in \mathbb {R}$$\alpha ,\beta ,\gamma \in \mathbb {R}$. Verificare che i metodi di Jacobi e Gauss-Seidel convergono o divergono entrambi, e indicare la relazione tra le velocità di convergenza.

 

$$I-B={\begin{array}{ccc}1&0&-\alpha \\-\beta &1&0\\0&-\gamma &1\end{array}}$$

$$I-B={\begin{array}{ccc}1&0&-\alpha \\-\beta &1&0\\0&-\gamma &1\end{array}}$$

La matrice di iterazione del metodo di Jacobi è

$$P_{j}=-D^{-1}*(L+U)=B={\begin{array}{ccc}0&0&\alpha \\\beta &0&0\\0&\gamma &0\end{array}}$$

$$P_{j}=-D^{-1}*(L+U)=B={\begin{array}{ccc}0&0&\alpha \\\beta &0&0\\0&\gamma &0\end{array}}$$

Calcolo gli autovalori della matrice di iterazione di Jacobi:

$$P_{j}-\lambda I={\begin{array}{ccc}-\lambda &0&\alpha \\\beta &-\lambda &0\\0&\gamma &-\lambda \end{array}}$$

$$P_{j}-\lambda I={\begin{array}{ccc}-\lambda &0&\alpha \\\beta &-\lambda &0\\0&\gamma &-\lambda \end{array}}$$

$$p_{\lambda }=-\lambda ^{3}+\alpha \beta \gamma =0$$

$$p_{\lambda }=-\lambda ^{3}+\alpha \beta \gamma =0$$

$$\lambda ={\sqrt[{3}]{\alpha \beta \gamma }}$$

$$\lambda ={\sqrt[{3}]{\alpha \beta \gamma }}$$

e la convergenza del metodo di Jacobi avviene se e solo se $\rho (P_{j})<1$$\rho (P_{j})<1$, e quindi se $\alpha \beta \gamma <1$$\alpha \beta \gamma <1$.

Costruisco la matrice di iterazione del metodo di Gauss-Heidel:

$$P_{g}=-(D+L)^{-1}U$$

$$P_{g}=-(D+L)^{-1}U$$

Per il calcolo degli autovalori di $p_{g}$$p_{g}$, devo imporre

$$\det(P_{g}-\lambda I)=\det(-(D+L)^{-1}U-\lambda I)=0$$

$$\det(P_{g}-\lambda I)=\det(-(D+L)^{-1}U-\lambda I)=0$$

$$=-\det(D+L)^{-1}*\det(U+\lambda (D+L))=0$$

$$=-\det(D+L)^{-1}*\det(U+\lambda (D+L))=0$$

e siccome $\det(D+L)^{-1}=0$$\det(D+L)^{-1}=0$ si ha che la condizione è verificata se $\det(U+\lambda (D+L))=0$$\det(U+\lambda (D+L))=0$, quindi calcolo $U+\lambda (D+L)$$U+\lambda (D+L)$.

$$U+\lambda (D+L)={\begin{array}{ccc}\lambda &0&-\alpha \\-\lambda \beta &\lambda &0\\0&-\lambda \gamma &\lambda \end{array}}$$

$$U+\lambda (D+L)={\begin{array}{ccc}\lambda &0&-\alpha \\-\lambda \beta &\lambda &0\\0&-\lambda \gamma &\lambda \end{array}}$$

$$P_{\lambda }=\lambda ^{3}-\alpha \beta \gamma \lambda ^{2}=0$$

$$P_{\lambda }=\lambda ^{3}-\alpha \beta \gamma \lambda ^{2}=0$$

$$\lambda _{1,2}=0,\,\lambda _{3}=\alpha \beta \gamma$$

$$\lambda _{1,2}=0,\,\lambda _{3}=\alpha \beta \gamma$$

e anche Gauss-Seidel converge se $\alpha \beta \gamma <1$$\alpha \beta \gamma <1$, però la velocità del metodo di Gauss-Seidel è tripla rispetto a quella del metodo di Jacobi.

Esempio 8.1 (fallimento del test dell'incremento)

Considero il sistema lineare $A{\boldsymbol {x}}={\boldsymbol {b}}$$A \boldsymbol{x} = \boldsymbol{b}$ con

$$A={\begin{array}{ccc}1&e-1&0\\(e-1)/2&1&(e-1)/2\\0&e-1&1\end{array}}$$

$$A={\begin{array}{ccc}1&e-1&0\\(e-1)/2&1&(e-1)/2\\0&e-1&1\end{array}}$$

$${\boldsymbol {b}}=(e,e,e)^{t}$$

$${\boldsymbol {b}}=(e,e,e)^{t}$$

con soluzione esatta

$${\boldsymbol {x}}_{\ast }=(1,1,1)$$

$${\boldsymbol {x}}_{\ast }=(1,1,1)$$

 

Calcolando le iterate a partire dal vettore d'innesco

$${\boldsymbol {x}}_{0}=(0,0,0)$$

$${\boldsymbol {x}}_{0}=(0,0,0)$$

Considero il caso in cui $e=10^{-4}$$e=10^{-4}$ e uso il test d'arresto dell'incremento in norma infinito. La condizione che dev'essere verificata è

$$\vert {\boldsymbol {x}}_{k}-{\boldsymbol {x}}_{k-1}\vert \leq \varepsilon$$

$$\vert {\boldsymbol {x}}_{k}-{\boldsymbol {x}}_{k-1}\vert \leq \varepsilon$$

Applicando il metodo di Jacobi

$$P_{j}=-{\begin{array}{ccc}0&e-1&0\\(e-1)/2&0&(e-1)/2\\0&e-1&0\end{array}}$$

$$P_{j}=-{\begin{array}{ccc}0&e-1&0\\(e-1)/2&0&(e-1)/2\\0&e-1&0\end{array}}$$

La norma infinito di questa matrice è $1-e$$1-e$, e si ha la condizione che rende il test dell'arresto inaffidabile, infatti $\vert P_{j}\vert \simeq 1$$\vert P_{j}\vert \simeq 1$.
Per il test dell'arresto si ha:

$${\boldsymbol {x}}_{1}=P{\boldsymbol {x}}_{0}+{\boldsymbol {c}}={\boldsymbol {c}}$$

$${\boldsymbol {x}}_{1}=P{\boldsymbol {x}}_{0}+{\boldsymbol {c}}={\boldsymbol {c}}$$

ma ${\boldsymbol {c}}=D^{-1}{\boldsymbol {b}}={\boldsymbol {b}}=(e,e,e)$${\boldsymbol {c}}=D^{-1}{\boldsymbol {b}}={\boldsymbol {b}}=(e,e,e)$.

Allora:

$$\vert {\boldsymbol {x}}_{0}-{\boldsymbol {x}}_{1}\vert =10^{-4}$$

$$\vert {\boldsymbol {x}}_{0}-{\boldsymbol {x}}_{1}\vert =10^{-4}$$

e la condizione è verificata e il test si arresta, ma la soluzione ottenuta è diversa da quella esatta.

Esempio 8.2 (fallimento test del residuo)

Considerare il sistema

$$A{\boldsymbol {x}}={\boldsymbol {b}}$$

$$A{\boldsymbol {x}}={\boldsymbol {b}}$$

con

$$A={\begin{array}{ccc}1+e&1&1\\1&1+e&1\\1&1&1+e\end{array}}$$

$$A={\begin{array}{ccc}1+e&1&1\\1&1+e&1\\1&1&1+e\end{array}}$$

con soluzione esatta

$${\boldsymbol {x}}_{\ast }=(1,1,1)$$

$${\boldsymbol {x}}_{\ast }=(1,1,1)$$

e termine noto

$${\boldsymbol {b}}=(3+e,3+e,3+e)$$

$${\boldsymbol {b}}=(3+e,3+e,3+e)$$

 

$${\boldsymbol {x}}_{0}=(0,0,0)$$

$${\boldsymbol {x}}_{0}=(0,0,0)$$

Imponiamo che

$$\vert r_{k}\vert =\vert {\boldsymbol {b}}-A{\boldsymbol {x}}_{k}\vert ^{\infty }\leq \varepsilon$$

$$\vert r_{k}\vert =\vert {\boldsymbol {b}}-A{\boldsymbol {x}}_{k}\vert ^{\infty }\leq \varepsilon$$

con $\varepsilon =10^{-4}$$\varepsilon =10^{-4}$. Sappiamo che l'errore è controllato dal residuo secondo la relazione:

$$E_{k}\leq {\frac {K(A)}{\vert A\vert }}*R(x)$$

$$E_{k}\leq {\frac {K(A)}{\vert A\vert }}*R(x)$$

Il condizionamento è

$$K(A)=4*10^{4}$$

$$K(A)=4*10^{4}$$

e per questo motivo il test si arresta lontano dalla soluzione esatta.

Non è detto che il metodo di Jacobi converga più lentamente di quello di Gauss-Seidel.