Formulario · Calcolo Numerico · Note per Studenti

I. Errori e aritmetica di macchina

Aritmetica di macchina - floating point, precisione di macchina e cancellazione

Definizione (errori).

Errore assoluto: $E_a = |x - \tilde x|$ (ha le unità di $x$ ).

Errore relativo: $E_r = \dfrac{|x - \tilde x|}{|x|}$ per $x \ne 0$ (adimensionale).

Esempio. $x = \pi = 3{,}14159265$ e $\tilde x = 3{,}14$ . $E_a = 0{,}00159265$ , $E_r = 0{,}00159265 / 3{,}14159265 \approx 5{,}07 \cdot 10^{-4}$ : circa $3$ cifre corrette.

Definizione (sistema di numeri di macchina $F(\beta, t, L, U)$ ). Un numero normalizzato è $x = \pm\,(d_0{,}d_1 d_2 \dots d_{t-1})_\beta \cdot \beta^{\,e}, \qquad d_0 \ne 0,\quad L \le e \le U$ dove $\beta$ è la base, $t$ il numero di cifre significative (la precisione), $e$ l'esponente. Si aggiunge lo $0$ .

Esempio (sistema "giocattolo"). $F(2, 3, -1, 2)$ : numeri $\pm(1{,}m_1 m_2)_2 \cdot 2^e$ con $e \in \{-1, 0, 1, 2\}$ . I valori positivi sono $(1 + m/4)\cdot 2^e$ con $m = 0, 1, 2, 3$ :

Grafico interattivo: I 16 numeri positivi di F(2,3,−1,2): la distanza raddoppia a ogni potenza di 2, quindi la densità è maggiore vicino a zero

Teorema (errore di arrotondamento). Se $x_{\min} \le |x| \le x_{\max}$ , allora $\mathrm{fl}(x) = x(1 + \delta), \qquad |\delta| \le u = \tfrac12\,\beta^{\,1-t}.$ $u$ si chiama unità di arrotondamento (unit roundoff); $\varepsilon_M = \beta^{1-t} = 2u$ è la precisione di macchina (distanza tra $1$ e il numero di macchina successivo).

Esempio (arrotondamento nel sistema giocattolo). Qui $\varepsilon_M = 2^{1-3} = 0{,}25$ e $u = 0{,}125$ .

$x = 2{,}7$ sta tra $2{,}5$ e $3$ : distanze $0{,}2$ e $0{,}3$ , quindi $\mathrm{fl}(2{,}7) = 2{,}5$ . Errore relativo $0{,}2/2{,}7 \approx 0{,}074 \le 0{,}125$ ✓.
$x = 5{,}4$ sta tra $5$ e $6$ : $\mathrm{fl}(5{,}4) = 5$ , errore relativo $0{,}4/5{,}4 \approx 0{,}074 \le 0{,}125$ ✓.
$x = 7{,}6 > 7 + \tfrac12$ : overflow (risultato $\infty$ o errore). $x = 0{,}1 < x_{\min}$ : underflow (si arrotonda a $0$ o al numero più vicino).
$1 + 0{,}1 = 1{,}1$ sta tra $1$ e $1{,}25$ , più vicino a $1$ : $\mathrm{fl}(1{,}1) = 1$ . Il $0{,}1$ è assorbito: perché il risultato cambi, a $1$ si deve sommare più di $\varepsilon_M/2=u$ (con $u$ esatto si cade a metà tra $1$ e $1{,}25$ e il pareggio va verso $1$ , il numero con ultima cifra pari).

Condizionamento di un problema e stabilità di un algoritmo

Definizione (problema ben posto, Hadamard). Il problema "dato $d$ , trova $x$ tale che $F(x, d) = 0$ " è ben posto se: (1) la soluzione $x$ esiste; (2) è unica; (3) dipende con continuità dai dati $d$ . Altrimenti è mal posto.

Definizione (numero di condizionamento). Per $y = f(x)$ derivabile con $x f(x) \ne 0$ $K(x) = \left|\frac{x\,f'(x)}{f(x)}\right|$ è il fattore con cui un errore relativo sul dato $x$ viene moltiplicato nel risultato. Il problema è ben condizionato se $K$ è piccolo (qualche unità), mal condizionato se $K$ è grande.

Esempio 1: il coseno vicino a $\frac\pi2$ . Per $x = 1{,}57$ : $K = 1{,}57 \cdot \tan 1{,}57 = 1{,}57 \cdot 1255{,}77 \approx 1971{,}6$ . Si perturba $x$ con errore relativo $10^{-4}$ , cioè $\tilde x = 1{,}57 \cdot 1{,}0001 = 1{,}570157$ . Previsione: errore relativo su $\cos x$ circa $1971{,}6 \cdot 10^{-4} \approx 0{,}197$ ( $19{,}7\%$ ). Calcolo diretto: $\cos 1{,}57 = 7{,}9633\cdot 10^{-4}$ e $\cos 1{,}570157 = 6{,}3933\cdot 10^{-4}$ , variazione relativa $\frac{1{,}570\cdot 10^{-4}}{7{,}9633\cdot 10^{-4}} = 0{,}1972$ ✓. Una perturbazione dello $0{,}01\%$ sull'angolo cambia il risultato del $20\%$ : vicino a $\frac\pi2$ la pendenza del coseno vale circa $-1$ , quindi la variazione assoluta del risultato è pari a quella del dato ( $1{,}57\cdot 10^{-4}$ ); ma il valore del coseno è prossimo a zero, e diviso per un numero così piccolo l'errore relativo esplode.

Definizione (errore in avanti e all'indietro).

Errore in avanti (forward): $\dfrac{|\hat y - f(x)|}{|f(x)|}$ .

Errore all'indietro (backward): la perturbazione $\Delta x$ dei dati per cui $\hat y$ è il risultato esatto, $\hat y = f(x + \Delta x)$ , cioè $\dfrac{|\Delta x|}{|x|}$ . Un algoritmo è stabile all'indietro se l'errore all'indietro è dell'ordine di $u$ (di poco più di un arrotondamento sui dati).

Esempio svolto: ricorrenza instabile. Sia $I_n = \displaystyle\int_0^1 x^n e^{x-1}\,dx$ per $n \ge 0$ . Per parti (Integrazione per parti): $I_n = \bigl[x^n e^{x-1}\bigr]_0^1 - n\int_0^1 x^{n-1}e^{x-1}dx = 1 - n\,I_{n-1}, \qquad I_0 = 1 - e^{-1} = 0{,}63212\ldots$ Il problema è ben condizionato (un integrale di una funzione positiva e limitata: $\frac{1}{e(n+1)} \le I_n \le \frac1{n+1}$ , cioè $I_n$ è piccolo e decrescente). Si prova la ricorrenza in avanti con $4$ cifre significative, partendo da $I_0 \to 0{,}6321$ (errore $e_0 = 2{,}06\cdot 10^{-5}$ ):

Definizione.

Consistenza: se si inserisce nello schema la soluzione esatta $x$ , il residuo tende a zero per $h \to 0$ ( $n \to \infty$ ): lo schema "assomiglia" al problema.

Stabilità: la soluzione numerica dipende con continuità, in modo uniforme rispetto a $h$ , dai dati: piccole perturbazioni dei dati non vengono amplificate al diminuire di $h$ .

Convergenza: $x_n \to x$ per $h \to 0$ .

Teorema (di equivalenza di Lax-Richtmyer). Per un problema ben posto e lineare, uno schema consistente è convergente se e solo se è stabile. Per i problemi non lineari vale in generale almeno la direzione consistenza + stabilità $\Rightarrow$ convergenza.

Esempio svolto: derivata numerica. Per approssimare $f'(x)$ si usa il rapporto incrementale $D_h = \dfrac{f(x + h) - f(x)}{h}$ .

Errore di troncamento: dallo sviluppo di Taylor, $D_h - f'(x) = \frac h2 f''(\xi)$ . Tende a zero con $h$ (schema consistente, di ordine $1$ ).
Errore di arrotondamento: i due valori $f(x+h)$ e $f(x)$ hanno ciascuno errore relativo $u$ ; la loro differenza (numeri quasi uguali!) ha errore assoluto $\approx 2u|f|$ , e dividendo per $h$ l'errore diventa $\approx \frac{2u|f|}{h}$ : cresce al diminuire di $h$ .
Errore totale $E(h) \approx \dfrac h2|f''| + \dfrac{2u|f|}{h}$ . Il minimo è per $h_{\text{ott}} = 2\sqrt{\dfrac{u|f|}{|f''|}}$ , circa $\sqrt u \approx 10^{-8}$ in doppia precisione.

II. Equazioni non lineari

Metodo di bisezione e iterazioni di punto fisso

Teorema (degli zeri). Se $f$ è continua in $[a,b]$ e $f(a)f(b) < 0$ , esiste $\alpha \in\, ]a,b[$ con $f(\alpha) = 0$ .

Teorema (stima dell'errore). Il punto medio $c_n$ soddisfa $|c_n - \alpha| \le \frac{b - a}{2^{\,n+1}}.$

Esempio svolto. $f(x) = x^3 - x - 2$ su $[1,2]$ : $f(1) = -2 < 0$ e $f(2) = 4 > 0$ , quindi c'è una radice ( $\alpha = 1{,}52138\ldots$ ).

Grafico interattivo: f(x) = x³ − x − 2: cambia segno in [1, 2], lo zero è α ≈ 1,5214

Teorema (delle contrazioni, o del punto fisso). Sia $g: [a,b] \to [a,b]$ derivabile con $|g'(x)| \le L < 1 \quad \forall x \in [a,b].$ Allora: (1) $g$ ha un solo punto fisso $\alpha \in [a,b]$ ; (2) per ogni $x_0 \in [a,b]$ la successione $x_{k+1} = g(x_k)$ converge ad $\alpha$ ; (3) valgono le stime $|x_k - \alpha| \le L^k\,|x_0 - \alpha| \quad\text{(velocità)},\qquad |x_k - \alpha| \le \frac{L^k}{1-L}\,|x_1 - x_0| \quad\text{(a priori)},\qquad |x_k - \alpha| \le \frac{L}{1-L}\,|x_k - x_{k-1}| \quad\text{(a posteriori)}.$

Metodo di Newton, metodo delle secanti e ordine di convergenza

Definizione (ordine di convergenza). La successione converge con ordine $p \ge 1$ e costante asintotica $C$ se $\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^p} = C, \qquad 0 < C < \infty \quad(\text{con } C<1 \text{ se } p=1).$

$p = 1$ : convergenza lineare (tasso $C$ ): l'errore si moltiplica per $C$ a ogni passo (bisezione: $C=\frac12$ ; punto fisso: $C = |g'(\alpha)|$ ).

$p = 2$ : convergenza quadratica. Se $|e_k| \approx 10^{-s}$ allora $|e_{k+1}| \approx C\,10^{-2s}$ : il numero di cifre corrette raddoppia a ogni iterazione.

$1<p<2$ : convergenza superlineare.

Teorema (convergenza locale quadratica). Sia $f \in C^2$ in un intorno di $\alpha$ , con $f(\alpha) = 0$ e $f'(\alpha) \ne 0$ (radice semplice). Allora esiste $\delta > 0$ tale che per ogni $x_0$ con $|x_0 - \alpha| < \delta$ il metodo di Newton converge ad $\alpha$ e $\lim_{k\to\infty}\frac{e_{k+1}}{e_k^2} = \frac{f''(\alpha)}{2f'(\alpha)}.$ L'ordine è $2$ se $f''(\alpha) \ne 0$ (se $f''(\alpha) = 0$ l'ordine è maggiore).

III. Interpolazione e approssimazione

Interpolazione polinomiale - forma di Lagrange, differenze divise ed errore

Teorema (esistenza e unicità). Per $n+1$ coppie $(x_i, y_i)$ con $x_i$ a due a due distinti esiste un unico polinomio $p_n$ di grado $\le n$ con $p_n(x_i) = y_i$ per ogni $i$ .

Definizione (differenze divise). $f[x_i] = f(x_i)$ e ricorsivamente $f[x_i, \dots, x_{i+k}] = \frac{f[x_{i+1}, \dots, x_{i+k}] - f[x_i, \dots, x_{i+k-1}]}{x_{i+k} - x_i}.$

Teorema (forma di Newton). Il polinomio di interpolazione è $p_n(x) = f[x_0] + f[x_0,x_1](x - x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \dots + f[x_0,\dots,x_n]\prod_{j=0}^{n-1}(x - x_j).$

Esempio svolto: tabella delle differenze divise di $e^x$ . Per i nodi $0$ , $0{,}5$ , $1$ : $f[0,0{,}5] = \frac{1{,}648721 - 1}{0{,}5} = 1{,}297443,\qquad f[0{,}5,1] = \frac{2{,}718282 - 1{,}648721}{0{,}5} = 2{,}139121,$ $f[0,0{,}5,1] = \frac{2{,}139121 - 1{,}297443}{1 - 0} = 0{,}841679.$ Allora $p_2(x) = 1 + 1{,}297443\,x + 0{,}841679\,x(x - 0{,}5)$ e $p_2(0{,}25) = 1 + 0{,}324361 + 0{,}841679\cdot 0{,}25\cdot(-0{,}25) = 1{,}324361 - 0{,}052605 = 1{,}271756,$ lo stesso valore di Lagrange (stesso polinomio, scritto in un'altra base).

Teorema (errore). Sia $f \in C^{n+1}([a,b])$ , con nodi $x_0,\dots,x_n \in [a,b]$ . Per ogni $x \in [a,b]$ esiste $\xi = \xi(x) \in\,]a,b[$ tale che $f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\,\omega_{n+1}(x), \qquad \omega_{n+1}(x) = \prod_{i=0}^{n}(x - x_i).$

Esempio (continuazione). Per $e^x$ , $n=2$ , $M_3 = e^1 = 2{,}718$ su $[0,1]$ . Per $x = 0{,}25$ : $|\omega_3(0{,}25)| = |0{,}25\cdot(-0{,}25)\cdot(-0{,}75)| = 0{,}046875$ . Maggiorazione: $\frac{2{,}718}{6}\cdot 0{,}046875 = 0{,}02124$ . L'errore effettivo $0{,}01227$ è inferiore ✓.

Interpolazione a tratti, spline cubiche e minimi quadrati

Teorema (errore). Se $f \in C^2$ e $h = \max_i (x_{i+1} - x_i)$ , $\max_{[a,b]}|f(x) - s(x)| \le \frac{h^2}{8}\,\max_{[a,b]}|f''|.$

Esempio. $f = e^x$ su $[0,1]$ , $f'' \le e$ . Con $h = 0{,}1$ ( $10$ intervalli): maggiorante $\frac{0{,}01}{8}e = 3{,}40\cdot 10^{-3}$ ; errore effettivo (massimo calcolato su una griglia fine) $3{,}23\cdot 10^{-3}$ . Per garantire $10^{-4}$ : $h^2 \le \frac{8\cdot 10^{-4}}{e} = 2{,}94\cdot 10^{-4}$ , $h \le 0{,}01716$ , quindi $N \ge 58{,}3$ , cioè $N = 59$ intervalli (errore effettivo $9{,}7\cdot 10^{-5}$ ✓).

Definizione (spline cubica interpolante). È una funzione $S: [x_0, x_n] \to \mathbb{R}$ tale che

su ogni $[x_i, x_{i+1}]$ , $S = S_i$ è un polinomio di grado $\le 3$ ;

$S(x_i) = y_i$ per $i = 0,\dots,n$ ;

$S \in C^2([x_0,x_n])$ : $S_{i-1}'(x_i) = S_i'(x_i)$ e $S_{i-1}''(x_i) = S_i''(x_i)$ per $i = 1,\dots,n-1$ .

Esempio svolto. Nodi $0,1,2,3$ ( $h=1$ ), valori $y = 0,\ 1,\ 0,\ 1$ ; spline naturale: $M_0 = M_3 = 0$ . Equazioni per $i=1,2$ : $4M_1 + M_2 = 6(0 - 2 + 0) = -12, \qquad M_1 + 4M_2 = 6(1 - 0 + 1) = 12.$ Dalla prima $M_2 = -12 - 4M_1$ ; nella seconda $M_1 - 48 - 16M_1 = 12 \Rightarrow -15M_1 = 60 \Rightarrow M_1 = -4$ , $M_2 = 4$ . Gli intervalli:

$S_0(x) = \frac{M_1x^3}{6} + \left(y_1 - \frac{M_1}6\right)x + y_0(1-x) = -\frac23x^3 + \frac53x$ (con $M_0=0$ , $y_0 = 0$ , $y_1 - M_1/6 = 1 + \frac23$ );
$S_1(x) = -\frac23(2-x)^3 + \frac23(x-1)^3 + \frac53(2-x) - \frac23(x-1)$ ;
$S_2(x) = \frac23(3-x)^3 - \frac23(3-x) + (x-2)$ .

Grafico interattivo: Spline cubica naturale per i punti (0,0), (1,1), (2,0), (3,1) e polinomio di grado 3 sugli stessi punti (tratteggiato): la spline resta nell'intervallo dei dati, il polinomio no

IV. Integrazione numerica

Formule di quadratura - trapezi, Cavalieri-Simpson ed estrapolazione di Richardson

Definizione (grado di esattezza). Una formula di quadratura ha grado di esattezza $r$ se $E(p)=0$ per ogni polinomio di grado $\le r$ ed $E(x^{r+1})\ne0$ .

Formula del punto medio. $Q_{PM}=H\,f(m)$ (un nodo, $p_0$ costante). Formula del trapezio. $Q_T=\dfrac H2\big[f(a)+f(b)\big]$ (due nodi, $p_1$ retta per $(a,f(a))$ e $(b,f(b))$ : l'integrale è l'area del trapezio). Formula di Cavalieri-Simpson. $Q_S=\dfrac H6\big[f(a)+4f(m)+f(b)\big]$ (tre nodi $a,m,b$ , $p_2$ parabola).

Esempio. Su $[0,1]$ Simpson dà $Q_S(x^3)=\frac16\big[0+4\cdot\frac18+1\big]=\frac16\cdot\frac32=\frac14=\int_0^1x^3dx$ (esatto) e $Q_S(x^4)=\frac16\big[0+4\cdot\frac1{16}+1\big]=\frac{5}{24}=0{,}20833\ne\frac15$ .

Grafico interattivo: Integrale di e^x su [0,1]: la corda del trapezio (tratteggiata) sta sopra la curva, perché e^x è convessa, e il trapezio sovrastima l'area (E < 0)

Teorema (errore del trapezio). Se $f\in C^2([a,b])$ esiste $\xi\in(a,b)$ con $E_T=I-Q_T=-\frac{(b-a)^3}{12}\,f''(\xi).$

Esempio. $I=\int_0^1e^xdx=e-1=1{,}718282$ . Con $f=e^x$ , $f''=f^{(4)}=e^x\le e$ su $[0,1]$ .

Trapezio: $Q_T=\frac{1+e}2=1{,}859141$ , $E_T=-0{,}140859$ ; la stima dà $|E_T|\le\frac e{12}=0{,}2265$ ✓.
Simpson: $Q_S=\frac16\big[1+4e^{0{,}5}+e\big]=\frac16[1+6{,}594885+2{,}718282]=1{,}718861$ , $E_S=-0{,}000579$ ; la stima dà $|E_S|\le\frac e{2880}=0{,}000944$ ✓.

Teorema (errore delle formule composite). Se $f\in C^2$ (rispettivamente $C^4$ ) esistono $\xi,\eta\in(a,b)$ con $I-T_h=-\frac{(b-a)\,h^2}{12}f''(\xi),\qquad I-S_h=-\frac{(b-a)\,h^4}{180}f^{(4)}(\eta).$

Esempio. $\int_0^1e^xdx$ con $\varepsilon=10^{-6}$ : $M_2=M_4=e$ . Trapezi: $\frac{h^2}{12}e\le10^{-6}\Rightarrow h\le\sqrt{12\cdot10^{-6}/e}=0{,}00210\Rightarrow n\ge476$ . Simpson: $\frac{h^4}{180}e\le10^{-6}\Rightarrow h\le\big(180\cdot10^{-6}/e\big)^{1/4}=0{,}0902\Rightarrow n\ge11{,}08$ , cioè $n=12$ (pari). Simpson richiede 13 valutazioni contro 477.

Quadratura gaussiana e formule composite adattive

Teorema (D). Siano $t_1,\dots,t_m$ le radici di $P_m$ e $w_i=\int_{-1}^1\ell_i(t)\,dt$ i pesi interpolatori. La formula ha grado di esattezza $2m-1$ .

Esempio. $\int_0^1e^x\,dx=1{,}718282$ con $m=2$ . Nodi: $x=\frac12\pm\frac12\cdot0{,}57735=0{,}211325;\ 0{,}788675$ . Valori: $e^{0{,}211325}=1{,}235314$ , $e^{0{,}788675}=2{,}200479$ . $Q=\frac{1-0}2\,(1\cdot1{,}235314+1\cdot2{,}200479)=\frac{3{,}435793}2=1{,}717896,\qquad I-Q=3{,}85\cdot10^{-4}.$ Per confronto Simpson con tre valori ha errore $5{,}79\cdot10^{-4}$ : la formula gaussiana con meno valori è più precisa. Con $m=3$ ( $x=0{,}112702;\,0{,}5;\,0{,}887298$ , valori $1{,}119298;\,1{,}648721;\,2{,}428560$ ): $Q=\frac12\big(\frac59\cdot1{,}119298+\frac89\cdot1{,}648721+\frac59\cdot2{,}428560\big)=1{,}718281$ , errore $8{,}2\cdot10^{-7}$ .

V. Sistemi lineari

Fattorizzazione LU, pivoting e Cholesky

Teorema. Se $\det A_k\ne0$ per $k=1,\dots,n-1$ , esiste un'unica fattorizzazione $A=LU$ con $L$ a diagonale unitaria. I pivot sono $u_{kk}=\dfrac{\det A_k}{\det A_{k-1}}$ .

Teorema (Cholesky). Se $A$ è SPD esiste un'unica matrice triangolare inferiore $L$ con elementi diagonali positivi tale che $A=LL^T$ .

Esempio. $A=\begin{pmatrix}4&2&2\\2&5&3\\2&3&6\end{pmatrix}$ . Minori di testa: $4$ , $4\cdot5-4=16$ , $\det A=64$ : tutti positivi, A è SPD.

Colonna 1: $l_{11}=\sqrt4=2$ , $l_{21}=\frac22=1$ , $l_{31}=\frac22=1$ .
Colonna 2: $l_{22}=\sqrt{5-1^2}=2$ , $l_{32}=\frac{3-l_{31}l_{21}}{l_{22}}=\frac{3-1\cdot1}2=1$ .
Colonna 3: $l_{33}=\sqrt{6-1^2-1^2}=\sqrt4=2$ .

Norme di matrici e condizionamento dei sistemi lineari

Definizione. Una norma su $\mathbb R^n$ è una funzione $\|\cdot\|$ con: $\|\mathbf x\|\ge0$ e $=0$ solo per $\mathbf x=\mathbf 0$ ; $\|\alpha\mathbf x\|=|\alpha|\|\mathbf x\|$ ; $\|\mathbf x+\mathbf y\|\le\|\mathbf x\|+\|\mathbf y\|$ (disuguaglianza triangolare).

Definizione (norma indotta). $\|A\|=\displaystyle\max_{\mathbf x\ne\mathbf 0}\frac{\|A\mathbf x\|}{\|\mathbf x\|}=\max_{\|\mathbf x\|=1}\|A\mathbf x\|$ .

Teorema (formule esplicite). $\|A\|_1=\max_j\sum_{i=1}^n|a_{ij}|\ \ (\text{massima somma per colonne}),\qquad\|A\|_\infty=\max_i\sum_{j=1}^n|a_{ij}|\ \ (\text{massima somma per righe}),$ $\|A\|_2=\sqrt{\lambda_{\max}(A^TA)}=\sigma_{\max}(A).$

Esempio ( $3\times3$ ). $A=\begin{pmatrix}1&-2&3\\0&4&-1\\-2&1&5\end{pmatrix}$ . Somme per colonne: $|1|+|0|+|-2|=3$ ; $|-2|+4+1=7$ ; $3+1+5=9$ : $\|A\|_1=9$ . Somme per righe: $1+2+3=6$ ; $0+4+1=5$ ; $2+1+5=8$ : $\|A\|_\infty=8$ . Frobenius: $\sqrt{1+4+9+0+16+1+4+1+25}=\sqrt{61}=7{,}81$ . Stime per la norma 2: $\|A\|_2\le\sqrt{9\cdot8}=8{,}49$ e $\|A\|_2\ge\rho(A)=4{,}38$ ; il valore esatto (Python) è $6{,}13$ .

Definizione. Per $A$ invertibile $\kappa(A)=\|A\|\,\|A^{-1}\|$ (con la stessa norma indotta).

Esempio. $A=\begin{pmatrix}1&2\\0&1\end{pmatrix}$ ha $A^{-1}=\begin{pmatrix}1&-2\\0&1\end{pmatrix}$ , quindi $\kappa_1=\kappa_\infty=3\cdot3=9$ e $\kappa_2=(1+\sqrt2)^2=5{,}83$ .

Teorema (perturbazione del termine noto, D). Se $A\mathbf x=\mathbf b$ e $A(\mathbf x+\delta\mathbf x)=\mathbf b+\delta\mathbf b$ , con $\mathbf b\ne\mathbf 0$ , $\frac{\|\delta\mathbf x\|}{\|\mathbf x\|}\le\kappa(A)\,\frac{\|\delta\mathbf b\|}{\|\mathbf b\|}.$

Esempio. Con $A=\begin{pmatrix}1&1\\1&1{,}0001\end{pmatrix}$ e $\mathbf b=(2;\,2{,}0001)^T$ la soluzione è $\mathbf x=(1,1)^T$ . Se $b_2$ passa a $2{,}0002$ ( $\|\delta\mathbf b\|_\infty=10^{-4}$ , errore relativo $\frac{10^{-4}}{2{,}0001}=5\cdot10^{-5}$ ) la soluzione diventa $(0,\,2)^T$ : $\delta\mathbf x=(-1,1)$ , errore relativo $\frac{1}{1}=1$ , cioè 100%. L'amplificazione effettiva è $\frac1{5\cdot10^{-5}}=2\cdot10^4\le\kappa_\infty=4\cdot10^4$ ✓.

Metodi iterativi - Jacobi, Gauss-Seidel e convergenza

Teorema (convergenza, D). L'iterazione converge per ogni $\mathbf x^{(0)}$ se e solo se $\rho(B)<1$ . Basta che $\|B\|<1$ per una norma indotta.

Teorema (dominanza diagonale). Se $A$ è a dominanza diagonale stretta per righe, $|a_{ii}|>\sum_{j\ne i}|a_{ij}|$ per ogni $i$ , Jacobi e Gauss-Seidel convergono.

Teorema (SPD). Se $A$ è simmetrica definita positiva, Gauss-Seidel converge (Jacobi in generale no: richiede anche $2D-A$ definita positiva). Tridiagonali. Se $A$ è tridiagonale con diagonale non nulla, $\rho(B_{GS})=\rho(B_J)^2$ e Jacobi e Gauss-Seidel convergono o divergono insieme.

VI. Equazioni differenziali ordinarie

Metodi di Eulero esplicito, implicito e Crank-Nicolson

Definizione. L'errore di troncamento locale $\tau_n(h)$ è il residuo che si ottiene inserendo la soluzione esatta nello schema, diviso per $h$ . Il metodo è consistente se $\tau_n(h)\to0$ per $h\to0$ ; ha ordine $p$ se $\tau(h)=O(h^p)$ .

Definizione (stabilità, o zero-stabilità). Un metodo è stabile se, perturbando lo schema con errori $\delta_n$ a ogni passo (e $\delta_0$ sul dato iniziale), la soluzione numerica perturbata $z_n$ dista da quella non perturbata $u_n$ al più $|z_n-u_n|\le C\big(|\delta_0|+\sum_k h|\delta_k|\big)$ , con $C$ indipendente da $h$ su un intervallo fissato $[t_0,T]$ .

Teorema (convergenza). Se $f$ è lipschitziana in $y$ (costante $L$ ) e il metodo è consistente di ordine $p$ e stabile, allora $\max_n|e_n|\le C\,h^p$ per $h\to0$ , con $C$ dipendente da $L$ , dall'intervallo e dalle derivate di $y$ .

Esempio. Per $y'=t-y$ : $L=1$ , $y''=2e^{-t}$ , $M=2$ . A $t=1$ con $h=0{,}2$ : $|e|\le\frac{2\cdot0{,}2}{2}(e-1)=0{,}344$ . L'errore vero è $0{,}0804$ : la stima è corretta, ma pessimistica di un fattore $4$ .

Stabilità assoluta, problemi stiff e sistemi di equazioni differenziali

Definizione. La regione di stabilità assoluta è $\mathcal A=\{z\in\mathbb C:|R(z)|<1\}$ . Il metodo è A-stabile se $\mathcal A$ contiene tutto il semipiano $\mathrm{Re}\,z<0$ .

Esempio ( $\lambda=-50$ , $y(0)=1$ ). Il fattore di EE è $1-50h$ : $h=0{,}01$ : $0{,}5$ (decade monotonamente); $h=0{,}02$ : $0$ (azzera la soluzione al primo passo); $h=0{,}03$ : $-0{,}5$ (oscilla smorzata); $h=0{,}04$ : $-1$ (oscillazione permanente di ampiezza $1$ ); $h=0{,}05$ : $-1{,}5$ (diverge). La soglia è $h=\frac{2}{50}=0{,}04$ . Con EI il fattore è $\frac1{1+50h}$ ( $h=0{,}05$ : $0{,}286$ ) e con CN $\frac{1-25h}{1+25h}$ ( $h=0{,}05$ : $-0{,}111$ ): stabili.

Grafico interattivo: Piano z = h·lambda: regione di stabilità di Eulero esplicito (interno del cerchio centrato in -1, raggio 1) e cerchio di centro +1 e raggio 1, il cui esterno è la regione di Eulero implicito; Crank-Nicolson è stabile in tutto il semipiano Re z < 0