Esercizio - condizionamento della matrice di rigidezza di una catena di molle

Teoria: 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 →. La matrice è la stessa di Esercizio - Cholesky della matrice di rigidezza di una catena di tre masse.

Testo. Una catena di $n$ masse collegate da molle uguali di rigidezza $k$ e fissata alle due pareti ha matrice di rigidezza $K=k\,K_n$ con $K_n=\operatorname{tridiag}(-1,2,-1)$. Gli autovalori di $K_n$ sono $\lambda_j=2-2\cos\frac{j\pi}{n+1}$, $j=1,\dots,n$.

1. Per $n=3$ calcolare gli autovalori, $\kappa_2$ e $\kappa_\infty$ (con l'inversa $K_3^{-1}=\frac14\begin{pmatrix}3&2&1\\2&4&2\\1&2&3\end{pmatrix}$). Il valore dipende da $k$?
2. Ricavare la formula approssimata di $\kappa_2(K_n)$ per $n$ grande e calcolarla per $n=10,100,1000$.
3. I carichi sono noti con errore relativo $10^{-6}$. Dare il limite superiore dell'errore relativo sugli spostamenti per $n=100$ e il numero di cifre perse.
4. (Teoria) Perché dimezzare il passo di una discretizzazione (raddoppiare $n$) peggiora il condizionamento? E perché $\kappa(kK_n)=\kappa(K_n)$?

Soluzione

1. Caso $n=3$. $\lambda_j=2-2\cos\frac{j\pi}4$: $\lambda_1=2-\sqrt2=0{,}5858$, $\lambda_2=2-2\cdot0=2$, $\lambda_3=2+\sqrt2=3{,}4142$. La matrice è SPD, quindi $$\kappa_2(K_3)=\frac{\lambda_{\max}}{\lambda_{\min}}=\frac{2+\sqrt2}{2-\sqrt2}=\frac{(2+\sqrt2)^2}{4-2}=\frac{6+4\sqrt2}2=3+2\sqrt2=5{,}828 .$$ Con la norma $\infty$: $\|K_3\|_\infty=4$ (riga centrale $1+2+1$) e $\|K_3^{-1}\|_\infty$ è la massima somma per righe di $K_3^{-1}$: $\frac{3+2+1}4=1{,}5$; $\frac{2+4+2}4=2$; $\frac{1+2+3}4=1{,}5$, quindi $2$. $\kappa_\infty=4\cdot2=8$. I due valori sono compatibili ($\kappa_2\le n\,\kappa_\infty$). Dipendenza da $k$: nessuna. $\kappa(kK_3)=\|kK_3\|\,\|(kK_3)^{-1}\|=k\|K_3\|\cdot\frac1k\|K_3^{-1}\|=\kappa(K_3)$: il condizionamento non dipende dalle unità di misura della rigidezza.

2. Formula per $n$ grande. $\lambda_{\min}=2-2\cos\frac\pi{n+1}\approx\Big(\frac\pi{n+1}\Big)^2$ (sviluppo $1-\cos t\approx\frac{t^2}2$) e $\lambda_{\max}=2+2\cos\frac\pi{n+1}\approx4$. Quindi $$\kappa_2(K_n)\approx\frac{4(n+1)^2}{\pi^2} .$$

3. Stima dell'errore per $n=100$. Il limite superiore è $\kappa_2\cdot10^{-6}=4134\cdot10^{-6}=4{,}1\cdot10^{-3}$, cioè $0{,}4\%$: si perdono $\log_{10}4134=3{,}6$ cifre, quindi dei $6$ digit dei dati ne restano circa $2{,}4$. Con la doppia precisione ($u\approx10^{-16}$) l'errore di arrotondamento amplificato è $\approx4\cdot10^{-13}$, trascurabile: l'errore di rappresentazione dei dati conta più di quello dell'algoritmo. Per $n=1000$ il limite diventa $0{,}4$ (40%): con carichi noti a $10^{-6}$ gli spostamenti non sarebbero attendibili.

4. Teoria. Peggiora perché con più nodi la struttura discreta ha modi sempre più «lunghi» e sempre più «corti»: il rapporto tra l'energia dei modi più rigidi (oscillanti da nodo a nodo, $\lambda_{\max}\approx4$) e quella dei modi più morbidi (spostamento lento di tutta la catena, $\lambda_{\min}\approx\frac{\pi^2}{(n+1)^2}$) cresce come $(n+1)^2$: raddoppiando $n$, $\kappa$ si moltiplica per $\approx4$, cioè si perdono altre $\log_{10}4=0{,}6$ cifre. È una proprietà dei problemi alle differenze finite e agli elementi finiti: più la griglia è fine, più i sistemi sono mal condizionati (da qui i precondizionatori e i metodi multigriglia). Scala: la norma indotta è omogenea, $\|\alpha A\|=|\alpha|\|A\|$, e $(\alpha A)^{-1}=\alpha^{-1}A^{-1}$.

Risultati: $n=3$: $\kappa_2=3+2\sqrt2=5{,}83$, $\kappa_\infty=8$; $\kappa_2(K_n)\approx\frac{4(n+1)^2}{\pi^2}$; per $n=100$ errore relativo $\le0{,}4\%$ con $3{,}6$ cifre perse.

Errori tipici. Calcolare $\kappa_2$ come $\frac{\lambda_{\max}}{\lambda_{\min}}$ per una matrice non SPD (serve $\frac{\sigma_{\max}}{\sigma_{\min}}$); pensare che $\kappa$ dipenda da $k$; confondere $\lambda_{\min}\approx\frac{\pi^2}{(n+1)^2}$ con $\frac1{n+1}$.