Salta al contenuto
Note per Studenti Esercizio - matrici di iterazione e raggio spettrale di sistemi 2x2 e 3x3

Esercizio - matrici di iterazione e raggio spettrale di sistemi 2x2 e 3x3

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 →, Norme di matrici e condizionamento dei sistemi lineariNorme di vettore $|x|1=\sum|x_i|$, $|x|2=\sqrt{\sum x_i^2}$, $|x|\infty=\max|x_i|$. Norma di matrice indotta $|A|=\max{x\ne0}\frac{|Ax|}{|x|}$: $|A|1$ = massima somma per colonne, $|A|\infty$ = massima somma per righe, $|A|2=\sqrt{\lambda{\max}(A^TA)}$ (= $\rho(A)$ se $A$ simmetrica); valgono $|Ax|\le|A||x|$, $|AB|\le|A||B|$, $\rho(A)\le|A|$. Numero di condizionamento $\kappa(A)=|A||A^{-1}|\ge1$ ($\kappa_2=\frac{\sigma_{\max}}{\sigma_{\min}}$, per SPD $\frac{\lambda_{\max}}{\lambda_{\min}}$, per ortogonali 1). Se $A\mathbf x=\mathbf b$ e $A(\mathbf x+\delta\mathbf x)=\mathbf b+\delta\mathbf b$: $\frac{|\delta\mathbf x|}{|\mathbf x|}\le\kappa(A)\frac{|\delta\mathbf b|}{|\mathbf b|}$ (D); con residuo $\mathbf r=\mathbf b-A\hat{\mathbf x}$: $\frac1\kappa\frac{|\mathbf r|}{|\mathbf b|}\le\frac{|\mathbf x-\hat{\mathbf x}|}{|\mathbf x|}\le\kappa\frac{|\mathbf r|}{|\mathbf b|}$. Si perdono circa $\log_{10}\kappa$ cifre; un residuo piccolo non garantisce un errore piccolo se $\kappa$ è grande.Norme di matrici e condizionamento dei sistemi lineari →.

Testo.

  1. Per A=(1231)A=\begin{pmatrix}1&2\\3&1\end{pmatrix} scrivere BJB_J e BGSB_{GS}, calcolarne il raggio spettrale e dire se i metodi convergono. Cosa succede scambiando le due equazioni?
  2. Per A1=(12−2111221)A_1=\begin{pmatrix}1&2&-2\\1&1&1\\2&2&1\end{pmatrix} mostrare che BJB_J ha tutti gli autovalori nulli e calcolare gli autovalori di BGSB_{GS}. Quale metodo converge?
  3. Per A2=(2−11222−1−12)A_2=\begin{pmatrix}2&-1&1\\2&2&2\\-1&-1&2\end{pmatrix} calcolare ρ(BJ)\rho(B_J) e ρ(BGS)\rho(B_{GS}).
  4. (Teoria) Una matrice a dominanza diagonale stretta per colonne ma non per righe garantisce la convergenza di Jacobi? Perché?

Soluzione

1. D=diag⁡(1,1)D=\operatorname{diag}(1,1), L=(0030)L=\begin{pmatrix}0&0\\3&0\end{pmatrix}, U=(0200)U=\begin{pmatrix}0&2\\0&0\end{pmatrix}. BJ=−(L+U)=(0−2−30),det⁡(BJ−λI)=λ2−6=0⇒λ=±6, ρ(BJ)=2,449.B_J=-(L+U)=\begin{pmatrix}0&-2\\-3&0\end{pmatrix},\qquad\det(B_J-\lambda I)=\lambda^2-6=0\Rightarrow\lambda=\pm\sqrt6,\ \rho(B_J)=2{,}449 . Per Gauss-Seidel BGS=−(D+L)−1UB_{GS}=-(D+L)^{-1}U, con (D+L)−1=(10−31)(D+L)^{-1}=\begin{pmatrix}1&0\\-3&1\end{pmatrix}: BGS=−(10−31)(0200)=−(020−6)=(0−206),λ=0, 6, ρ(BGS)=6=ρ(BJ)2.B_{GS}=-\begin{pmatrix}1&0\\-3&1\end{pmatrix}\begin{pmatrix}0&2\\0&0\end{pmatrix}=-\begin{pmatrix}0&2\\0&-6\end{pmatrix}=\begin{pmatrix}0&-2\\0&6\end{pmatrix},\qquad\lambda=0,\ 6,\ \rho(B_{GS})=6=\rho(B_J)^2 . Entrambi divergono (ρ>1\rho>1), e Gauss-Seidel più in fretta (come Jacobi al quadrato: coerente col teorema per matrici tridiagonali, qui 2×22\times2). Scambiando le equazioni: A′=(3112)A'=\begin{pmatrix}3&1\\1&2\end{pmatrix}, BJ=(0−13−120)B_J=\begin{pmatrix}0&-\frac13\\-\frac12&0\end{pmatrix}, λ2=16\lambda^2=\frac16, ρ(BJ)=0,408\rho(B_J)=0{,}408; ρ(BGS)=16=0,167\rho(B_{GS})=\frac16=0{,}167. Ora convergono, perché A′A' è a dominanza diagonale stretta (3>13>1, 2>12>1).

2. Matrice A1A_1. D=ID=I, L+U=(02−2101220)L+U=\begin{pmatrix}0&2&-2\\1&0&1\\2&2&0\end{pmatrix}, BJ=−(L+U)B_J=-(L+U). Autovalori: det⁡(λI−BJ)=det⁡(λ2−21λ122λ)\det(\lambda I-B_J)=\det\begin{pmatrix}\lambda&2&-2\\1&\lambda&1\\2&2&\lambda\end{pmatrix}. Sviluppando secondo la prima riga: λ(λ2−2)−2(λ−2)+(−2)(2−2λ)=λ3−2λ−2λ+4−4+4λ=λ3.\lambda(\lambda^2-2)-2(\lambda-2)+(-2)(2-2\lambda)=\lambda^3-2\lambda-2\lambda+4-4+4\lambda=\lambda^3 . Quindi tutti gli autovalori sono 00: ρ(BJ)=0\rho(B_J)=0 e Jacobi converge in al più 3 iterazioni (BJB_J nilpotente, BJ3=0B_J^3=0). Per Gauss-Seidel: D+L=(100110221)D+L=\begin{pmatrix}1&0&0\\1&1&0\\2&2&1\end{pmatrix}, con inversa (100−1100−21)\begin{pmatrix}1&0&0\\-1&1&0\\0&-2&1\end{pmatrix} e U=(02−2001000)U=\begin{pmatrix}0&2&-2\\0&0&1\\0&0&0\end{pmatrix}: BGS=−(D+L)−1U=−(02−20−2300−2)=(0−2202−3002).B_{GS}=-(D+L)^{-1}U=-\begin{pmatrix}0&2&-2\\0&-2&3\\0&0&-2\end{pmatrix}=\begin{pmatrix}0&-2&2\\0&2&-3\\0&0&2\end{pmatrix}. È triangolare superiore, gli autovalori sono sulla diagonale: 0,2,20,2,2, quindi ρ(BGS)=2>1\rho(B_{GS})=2>1: Gauss-Seidel diverge, Jacobi converge. La matrice non è né dominante né SPD.

3. Matrice A2A_2. BJ=−D−1(L+U)=(012−12−10−112120)B_J=-D^{-1}(L+U)=\begin{pmatrix}0&\frac12&-\frac12\\-1&0&-1\\\frac12&\frac12&0\end{pmatrix}. Il polinomio caratteristico: det⁡(λI−BJ)=det⁡(λ−12121λ1−12−12λ)=λ(λ2+12)+12(λ+12)+12(−12+λ2)=λ3+54λ.\det(\lambda I-B_J)=\det\begin{pmatrix}\lambda&-\frac12&\frac12\\1&\lambda&1\\-\frac12&-\frac12&\lambda\end{pmatrix}=\lambda\Big(\lambda^2+\frac12\Big)+\frac12\Big(\lambda+\frac12\Big)+\frac12\Big(-\frac12+\frac\lambda2\Big)=\lambda^3+\frac54\lambda . (Primo termine: λ(λ⋅λ−1⋅(−12))=λ(λ2+12)\lambda(\lambda\cdot\lambda-1\cdot(-\frac12))=\lambda(\lambda^2+\frac12); secondo: −(−12)⋅(1⋅λ−1⋅(−12))=12(λ+12)-(-\frac12)\cdot(1\cdot\lambda-1\cdot(-\frac12))=\frac12(\lambda+\frac12); terzo: 12⋅(1⋅(−12)−λ⋅(−12))=12(−12+λ2)\frac12\cdot(1\cdot(-\frac12)-\lambda\cdot(-\frac12))=\frac12(-\frac12+\frac\lambda2).) Gli autovalori sono λ=0, ±i52\lambda=0,\ \pm i\frac{\sqrt5}2: ρ(BJ)=52=1,118>1\rho(B_J)=\frac{\sqrt5}2=1{,}118>1, Jacobi diverge. Gauss-Seidel: D+L=(200220−1−12)D+L=\begin{pmatrix}2&0&0\\2&2&0\\-1&-1&2\end{pmatrix}, U=(0−11002000)U=\begin{pmatrix}0&-1&1\\0&0&2\\0&0&0\end{pmatrix}, e (per sostituzione) BGS=(012−120−12−1200−12)B_{GS}=\begin{pmatrix}0&\frac12&-\frac12\\0&-\frac12&-\frac12\\0&0&-\frac12\end{pmatrix}: triangolare, autovalori 0,−12,−120,-\frac12,-\frac12, ρ(BGS)=12<1\rho(B_{GS})=\frac12<1: converge.

4. Dominanza per colonne. Sì. Se ∑i≠j∣aij∣<∣ajj∣\sum_{i\ne j}|a_{ij}|<|a_{jj}| per ogni colonna jj, la matrice C=−(L+U)D−1C=-(L+U)D^{-1} ha elementi −aijajj-\frac{a_{ij}}{a_{jj}} (i≠ji\ne j) e norma ∥C∥1=max⁡j∑i≠j∣aij∣∣ajj∣<1\|C\|_1=\max_j\sum_{i\ne j}\frac{|a_{ij}|}{|a_{jj}|}<1. Inoltre C=D BJ D−1C=D\,B_J\,D^{-1} è simile a BJB_J, quindi ha gli stessi autovalori e ρ(BJ)=ρ(C)≤∥C∥1<1\rho(B_J)=\rho(C)\le\|C\|_1<1: Jacobi converge. (Per Gauss-Seidel vale lo stesso risultato, con dimostrazione più laboriosa.)

Risultati: AA: ρJ=6\rho_J=\sqrt6, ρGS=6\rho_{GS}=6 (divergono); scambiate le righe 0,4080{,}408 e 0,1670{,}167. A1A_1: ρJ=0\rho_J=0, ρGS=2\rho_{GS}=2. A2A_2: ρJ=1,118\rho_J=1{,}118, ρGS=12\rho_{GS}=\frac12.

Errori tipici. Calcolare ρ\rho dalla diagonale di BB senza risolvere il polinomio caratteristico; dimenticare il segno meno in B=−D−1(L+U)B=-D^{-1}(L+U); dedurre dalla convergenza di un metodo quella dell'altro.

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=(1231)A=\begin{pmatrix}1&2\\3&1\end{pmatrix}: BJ=(0−2−30)B_J=\begin{pmatrix}0&-2\\-3&0\end{pmatrix}, λ=±6\lambda=\pm\sqrt6; BGS=(0−206)B_{GS}=\begin{pmatrix}0&-2\\0&6\end{pmatrix}, ρ=6=ρJ2\rho=6=\rho_J^2: divergono. Righe scambiate (3112)\begin{pmatrix}3&1\\1&2\end{pmatrix}: ρJ=0,408\rho_J=0{,}408, ρGS=16\rho_{GS}=\frac16.

  • A1=(12−2111221)A_1=\begin{pmatrix}1&2&-2\\1&1&1\\2&2&1\end{pmatrix}: det⁡(λI−BJ)=λ3\det(\lambda I-B_J)=\lambda^3 (nilpotente, ρJ=0\rho_J=0); BGS=(0−2202−3002)B_{GS}=\begin{pmatrix}0&-2&2\\0&2&-3\\0&0&2\end{pmatrix}, autovalori 0,2,20,2,2: Jacobi converge, GS diverge.

  • A2=(2−11222−1−12)A_2=\begin{pmatrix}2&-1&1\\2&2&2\\-1&-1&2\end{pmatrix}: det⁡(λI−BJ)=λ3+54λ\det(\lambda I-B_J)=\lambda^3+\frac54\lambda, ρJ=52=1,118\rho_J=\frac{\sqrt5}2=1{,}118; BGSB_{GS} triangolare con 0,−12,−120,-\frac12,-\frac12, ρGS=12\rho_{GS}=\frac12: GS converge, Jacobi diverge.

  • Dominanza per colonne: BJB_J simile a −(L+U)D−1-(L+U)D^{-1}, ∥⋅∥1<1\|\cdot\|_1<1: Jacobi converge.

  • Calcoli: BGS=−(D+L)−1UB_{GS}=-(D+L)^{-1}U con (D+L)−1=(10−31)(D+L)^{-1}=\begin{pmatrix}1&0\\-3&1\end{pmatrix} per AA; per A1A_1 (D+L)−1=(100−1100−21)(D+L)^{-1}=\begin{pmatrix}1&0&0\\-1&1&0\\0&-2&1\end{pmatrix}; sviluppo di det⁡(λI−BJ)\det(\lambda I-B_J) secondo la prima riga.

  • AA non dominante; A′A' (righe scambiate) dominante: 3>13>1, 2>12>1.

Errori tipici: ρ\rho senza polinomio caratteristico; segno meno di BB; convergenza di un metodo dedotta dall'altro.

Teoria collegata