Esempi sui metodi iterativi

{{InizioEsercizio|title=|number=8.7|anchor=Esercizio8_7}}
Considero la matrice <math>A=I-B</math>, con<math display="block">B = \begin{array}{ccc} 0 & 0 & \alpha \\ \beta & 0 & 0 \\ 0 & \gamma & 0 \end{array}</math>con <math>\alpha,\beta,\gamma \in \mathbb R</math>. Verificare che i metodi di Jacobi e Gauss-Seidel convergono o divergono entrambi, e indicare la relazione tra le velocità di convergenza.
{{FineEsercizio}}
<math display="block">I-B = \begin{array}{ccc} 1 & 0 & -\alpha \\ -\beta & 1 & 0 \\ 0 & -\gamma & 1 \end{array}</math>La matrice di iterazione del metodo di Jacobi è<math display="block">P_j = -D^{-1}*(L+U) =B= \begin{array}{ccc} 0 & 0 & \alpha \\ \beta & 0 & 0 \\ 0 & \gamma & 0 \end{array}</math>Calcolo gli autovalori della matrice di iterazione di Jacobi:<math display="block">P_j-\lambda I = \begin{array}{ccc}-\lambda & 0 & \alpha \\ \beta & -\lambda & 0 \\ 0 & \gamma & -\lambda \end{array}</math><math display="block">p_\lambda = -\lambda^3+\alpha \beta \gamma =0</math><math display="block">\lambda = \sqrt[3]{\alpha \beta \gamma}</math>e la convergenza del metodo di Jacobi avviene se e solo se <math>\rho(P_j) < 1</math>, e quindi se <math>\alpha \beta \gamma < 1</math>.

Costruisco la matrice di iterazione del metodo di Gauss-Heidel:
<math display="block">P_g = -(D+L)^{-1} U</math>Per il calcolo degli autovalori di <math>p_g</math>, devo imporre<math display="block">\det (P_g-\lambda I) = \det (-(D+L)^{-1} U-\lambda I)=0</math><math display="block">= -\det (D+L)^{-1}*\det(U+\lambda(D+L))=0</math>e siccome <math>\det (D+L)^{-1}=0</math> si ha che la condizione è verificata se <math>\det(U+\lambda(D+L))=0</math>, quindi calcolo <math>U+\lambda(D+L)</math>.<math display="block">U+\lambda(D+L) = \begin{array}{ccc} \lambda & 0 & -\alpha \\ -\lambda \beta & \lambda & 0 \\ 0 & -\lambda \gamma & \lambda \end{array}</math><math display="block">P_\lambda = \lambda^3-\alpha \beta \gamma \lambda^2=0</math><math display="block">\lambda_{1,2}=0, \, \lambda_3 = \alpha \beta \gamma</math>e anche Gauss-Seidel converge se <math>\alpha \beta \gamma < 1</math>, però la velocità del metodo di Gauss-Seidel è tripla rispetto a quella del metodo di Jacobi.

{{InizioEsempio|title=fallimento del test dell'incremento|number=8.1|anchor=Esempio8_1}}
Considero il sistema lineare <math>A \boldsymbol{x} = \boldsymbol{b}</math> con<math display="block">A = \begin{array}{ccc} 1 & e-1 & 0 \\ (e-1)/2 & 1 & (e-1)/2 \\ 0 & e-1 & 1 \end{array}</math><math display="block">\boldsymbol{b} = (e,e,e)^t</math>con soluzione esatta<math display="block">\boldsymbol{x}_\ast = (1,1,1)</math>
{{FineEsempio}}

Calcolando le iterate a partire dal vettore d'innesco<math display="block">\boldsymbol{x}_0 = (0,0,0)</math>Considero il caso in cui <math>e=10^{-4}</math> e uso il test d'arresto dell'incremento in norma infinito.
La condizione che dev'essere verificata è<math display="block">\vert \boldsymbol{x}_k-\boldsymbol{x}_{k-1} \vert \le \varepsilon</math>Applicando il metodo di Jacobi<math display="block">P_j = -\begin{array}{ccc} 0 & e-1 & 0 \\ (e-1)/2 & 0 & (e-1)/2 \\ 0 & e-1 & 0 \end{array}</math>La norma infinito di questa matrice è <math>1-e</math>, e si ha la condizione che rende il test dell'arresto inaffidabile, infatti <math>\vert P_j \vert \simeq 1</math>.<br>
Per il test dell'arresto si ha:<math display="block">\boldsymbol{x}_1 = P \boldsymbol{x}_0+\boldsymbol{c} = \boldsymbol{c}</math>ma <math>\boldsymbol{c} = D^{-1} \boldsymbol{b} = \boldsymbol{b} = (e,e,e)</math>.

Allora:<math display="block">\vert \boldsymbol{x}_0-\boldsymbol{x}_1 \vert = 10^{-4}</math>e la condizione è verificata e il test si arresta, ma la soluzione ottenuta è diversa da quella esatta.

{{InizioEsempio|title=fallimento test del residuo|number=8.2|anchor=Esempio8_2}}
Considerare il sistema<math display="block">A \boldsymbol{x} = \boldsymbol{b}</math>con<math display="block">A = \begin{array}{ccc} 1+e & 1 & 1 \\ 1 & 1+e & 1 \\ 1 & 1 & 1+e \end{array}</math>con soluzione esatta<math display="block">\boldsymbol{x}_\ast = (1,1,1)</math>e termine noto<math display="block">\boldsymbol{b} = (3+e, 3+e, 3+e)</math>
{{FineEsempio}}
<math display="block">\boldsymbol{x}_0 = (0,0,0)</math>Imponiamo che<math display="block">\vert r_k \vert = \vert \boldsymbol{b}-A \boldsymbol{x}_k \vert^{\infty} \le \varepsilon</math>con <math>\varepsilon=10^{-4}</math>.
Sappiamo che l'errore è controllato dal residuo secondo la relazione:<math display="block">E_k \le \frac{K(A)}{\vert A \vert}*R(x)</math>Il condizionamento è<math display="block">K(A) = 4*10^4</math>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.