Salta al contenuto
Note per Studenti Esercizio - Jacobi a mano, dominanza diagonale e stima del numero di iterazioni

Esercizio - Jacobi a mano, dominanza diagonale e stima del numero di iterazioni

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 →.

Testo. Si considera il sistema (8−11210−1115)(x1x2x3)=(11−1010)(soluzione x=(1,−1,2)T).\begin{pmatrix}8&-1&1\\2&10&-1\\1&1&5\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}=\begin{pmatrix}11\\-10\\10\end{pmatrix}\qquad(\text{soluzione }\mathbf x=(1,-1,2)^T).

  1. Verificare la dominanza diagonale e scrivere la matrice di iterazione BJB_J del metodo di Jacobi con ∥BJ∥∞\|B_J\|_\infty.
  2. Eseguire due iterazioni di Jacobi da x(0)=0\mathbf x^{(0)}=\mathbf 0.
  3. Stimare l'errore dopo due iterazioni con la formula a posteriori e confrontarlo con quello vero.
  4. Dare, con la stima a priori, il numero di iterazioni che garantisce ∥e(k)∥∞≤10−6\|\mathbf e^{(k)}\|_\infty\le10^{-6}.

Soluzione

1. Dominanza e matrice BJB_J. Per righe: ∣8∣>∣−1∣+∣1∣=2|8|>|-1|+|1|=2; ∣10∣>2+1=3|10|>2+1=3; ∣5∣>1+1=2|5|>1+1=2: dominanza stretta, Jacobi converge. Risolvendo l'equazione ii per xix_i: x1(k+1)=11+x2(k)−x3(k)8,x2(k+1)=−10−2x1(k)+x3(k)10,x3(k+1)=10−x1(k)−x2(k)5,x_1^{(k+1)}=\frac{11+x_2^{(k)}-x_3^{(k)}}8,\quad x_2^{(k+1)}=\frac{-10-2x_1^{(k)}+x_3^{(k)}}{10},\quad x_3^{(k+1)}=\frac{10-x_1^{(k)}-x_2^{(k)}}5 , BJ=−D−1(L+U)=(018−18−150110−15−150).B_J=-D^{-1}(L+U)=\begin{pmatrix}0&\frac18&-\frac18\\-\frac15&0&\frac1{10}\\-\frac15&-\frac15&0\end{pmatrix}. Somme per righe dei moduli: 28=0,25\frac28=0{,}25; 310=0,3\frac3{10}=0{,}3; 25=0,4\frac25=0{,}4. Quindi ∥BJ∥∞=0,4<1\|B_J\|_\infty=0{,}4<1.

2. Iterazioni.

  • x(1)\mathbf x^{(1)} (da 0\mathbf 0): x1=118=1,375x_1=\frac{11}8=1{,}375; x2=−1010=−1x_2=\frac{-10}{10}=-1; x3=105=2x_3=\frac{10}5=2.
  • x(2)\mathbf x^{(2)}: x1=11+(−1)−28=88=1x_1=\frac{11+(-1)-2}8=\frac88=1; x2=−10−2⋅1,375+210=−10,7510=−1,075x_2=\frac{-10-2\cdot1{,}375+2}{10}=\frac{-10{,}75}{10}=-1{,}075; x3=10−1,375−(−1)5=9,6255=1,925x_3=\frac{10-1{,}375-(-1)}5=\frac{9{,}625}5=1{,}925.

Errori vero: x−x(2)=(0; 0,075; 0,075)\mathbf x-\mathbf x^{(2)}=(0;\ 0{,}075;\ 0{,}075), ∥⋅∥∞=0,075\|\cdot\|_\infty=0{,}075 (dopo una sola iterazione era 0,3750{,}375).

3. Stima a posteriori. Incremento: x(2)−x(1)=(−0,375; −0,075; −0,075)\mathbf x^{(2)}-\mathbf x^{(1)}=(-0{,}375;\ -0{,}075;\ -0{,}075), ∥⋅∥∞=0,375\|\cdot\|_\infty=0{,}375. Allora ∥e(2)∥∞≤∥BJ∥1−∥BJ∥⋅0,375=0,40,6⋅0,375=0,25.\|\mathbf e^{(2)}\|_\infty\le\frac{\|B_J\|}{1-\|B_J\|}\cdot0{,}375=\frac{0{,}4}{0{,}6}\cdot0{,}375=0{,}25 . È una maggiorazione corretta (0,075≤0,250{,}075\le0{,}25), prudente di un fattore 3,33{,}3.

4. Stima a priori. ∥e(0)∥∞=∥x∥∞=2\|\mathbf e^{(0)}\|_\infty=\|\mathbf x\|_\infty=2. Si impone 0,4k⋅2≤10−60{,}4^k\cdot2\le10^{-6}: k≥ln⁡(5⋅10−7)ln⁡0,4=−14,51−0,916=15,8 ⟹ k=16.k\ge\frac{\ln(5\cdot10^{-7})}{\ln0{,}4}=\frac{-14{,}51}{-0{,}916}=15{,}8\ \Longrightarrow\ k=16 . La stima è garantita; in pratica ne servono meno: il raggio spettrale è ρ(BJ)=0,215<0,4\rho(B_J)=0{,}215<0{,}4, e già dopo 4 iterazioni l'errore è 2,8⋅10−32{,}8\cdot10^{-3} (da 0,075, 0,015, 0,00280{,}075,\ 0{,}015,\ 0{,}0028 si vede un fattore ≈0,2\approx0{,}2 per iterazione, cioè ρ\rho).

Risultati: ∥BJ∥∞=0,4\|B_J\|_\infty=0{,}4; x(2)=(1; −1,075; 1,925)\mathbf x^{(2)}=(1;\ -1{,}075;\ 1{,}925), errore vero 0,0750{,}075 (stima 0,250{,}25); a priori k=16k=16.

Errori tipici. Usare i valori nuovi dentro l'iterazione di Jacobi; sbagliare il segno degli elementi di BJB_J (sono −aijaii-\frac{a_{ij}}{a_{ii}}); usare ln⁡∥B∥\ln\|B\| con segno sbagliato (∥B∥<1\|B\|<1 rende il logaritmo negativo).

Versione ripasso

(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 →)

A=(8−11210−1115)A=\begin{pmatrix}8&-1&1\\2&10&-1\\1&1&5\end{pmatrix}, b=(11,−10,10)\mathbf b=(11,-10,10), x=(1,−1,2)\mathbf x=(1,-1,2).

  • Dominanza: 8>28>2, 10>310>3, 5>25>2. BJ=(018−18−150110−15−150)B_J=\begin{pmatrix}0&\frac18&-\frac18\\-\frac15&0&\frac1{10}\\-\frac15&-\frac15&0\end{pmatrix}, ∥BJ∥∞=max⁡(0,25;0,3;0,4)=0,4\|B_J\|_\infty=\max(0{,}25;0{,}3;0{,}4)=0{,}4.
  • x(1)=(1,375;−1;2)\mathbf x^{(1)}=(1{,}375;-1;2), x(2)=(1;−1,075;1,925)\mathbf x^{(2)}=(1;-1{,}075;1{,}925), errore vero 0,0750{,}075.
  • A posteriori: 0,40,6⋅0,375=0,25\frac{0{,}4}{0{,}6}\cdot0{,}375=0{,}25.
  • A priori: 0,4k⋅2≤10−6⇒k≥15,80{,}4^k\cdot2\le10^{-6}\Rightarrow k\ge15{,}8, k=16k=16; in realtà ρ(BJ)=0,215\rho(B_J)=0{,}215: errori 0,075; 0,015; 0,00280{,}075;\,0{,}015;\,0{,}0028.
  • Passi: x2(2)=−10−2⋅1,375+210=−1,075x_2^{(2)}=\frac{-10-2\cdot1{,}375+2}{10}=-1{,}075, x3(2)=10−1,375+15=1,925x_3^{(2)}=\frac{10-1{,}375+1}5=1{,}925.

Errori tipici: valori nuovi in Jacobi; segno di BJB_J; logaritmo di ∥B∥\|B\|.

Esercizi su questo argomento

Teoria collegata