Esercizio - Interpolazione lineare a tratti di sin x, errore e numero di intervalli

Teoria: Interpolazione a tratti, spline cubiche e minimi quadratiInvece di un polinomio di grado alto si usano polinomi di grado basso su ogni intervallo. Lineare a tratti: errore ≤ h²/8·max|f''|. Spline cubica: polinomio di grado 3 su ogni intervallo, di classe C² nei nodi; i momenti M_i = S''(x_i) risolvono un sistema tridiagonale (h_{i−1}/6)M_{i−1} + ((h_{i−1}+h_i)/3)M_i + (h_i/6)M_{i+1} = differenza tra le pendenze dei due intervalli adiacenti, con due condizioni agli estremi (naturale M_0 = M_n = 0, vincolata, not-a-knot); errore O(h⁴), nessun fenomeno di Runge. Minimi quadrati: con più dati che parametri si minimizza ‖Ac − y‖², cioè si risolvono le equazioni normali AᵀA c = Aᵀy (proiezione ortogonale di y sulle colonne di A); la retta di regressione minimizza la somma dei quadrati dei residui e i residui sono ortogonali alle colonne.Interpolazione a tratti, spline cubiche e minimi quadrati →.

Testo

Si approssima $f(x) = \sin x$ con l'interpolante lineare a tratti.

• (a) Con i nodi $0,\ 0{,}5,\ 1,\ 1{,}5$ (valori $0,\ 0{,}479426,\ 0{,}841471,\ 0{,}997495$) stimare $\sin 0{,}8$ e confrontare l'errore con il maggiorante teorico.
• (b) Dimostrare il maggiorante $\frac{h^2}{8}\max|f''|$ per un intervallo di lunghezza $h$.
• (c) Quanti intervalli uguali servono su $[0,\pi]$ per garantire un errore $\le 10^{-3}$?
• (d) Domanda teorica: di quanto cala l'errore se si dimezza il passo? Confrontare con l'interpolazione quadratica a tratti.

Soluzione

(a) Stima di $\sin 0{,}8$

$0{,}8 \in [0{,}5,\ 1]$. L'interpolante lineare è $$s(0{,}8) = y_1 + \frac{y_2 - y_1}{1 - 0{,}5}(0{,}8 - 0{,}5) = 0{,}479426 + \frac{0{,}841471 - 0{,}479426}{0{,}5}\cdot 0{,}3 = 0{,}479426 + 0{,}724090\cdot 0{,}3 = 0{,}696653.$$ Valore esatto $\sin 0{,}8 = 0{,}717356$; errore $0{,}0207$. Maggiorante: $h = 0{,}5$, $\max|f''| = \max|\sin| \le 1$, quindi $\frac{0{,}25}{8}\cdot 1 = 0{,}03125$; $0{,}0207 \le 0{,}03125$ ✓. Si può restringere con il valore locale: nel punto $x = 0{,}8$ l'errore è $\frac{|f''(\xi)|}{2}|(0{,}8 - 0{,}5)(0{,}8 - 1)| = \frac{|\sin\xi|}{2}\cdot 0{,}06$ e con $\sin\xi \approx 0{,}69$ (cioè $\xi \approx 0{,}76$) dà proprio $0{,}0207$.

(b) Dimostrazione

In $[x_i, x_{i+1}]$ l'interpolante è il polinomio di grado $1$ nei due nodi, quindi per la formula dell'errore (Interpolazione polinomiale - forma di Lagrange, differenze divise ed erroreDati n+1 punti con ascisse distinte esiste un unico polinomio p_n di grado ≤ n che passa per tutti. Forma di Lagrange p = Σ y_i L_i(x) (L_i(x_j) = δ_ij); forma di Newton p = Σ f[x_0..x_k] Π_{j<k}(x − x_j) con le differenze divise (si aggiunge un nodo senza rifare tutto). Errore f(x) − p_n(x) = f^(n+1)(ξ)/(n+1)! · ω(x), ω(x) = Π(x − x_i): dipende da f e dalla scelta dei nodi. Nodi equispaziati con n grande danno il fenomeno di Runge; i nodi di Chebyshev minimizzano max|ω| = 2^(−n) su [−1,1].Interpolazione polinomiale - forma di Lagrange, differenze divise ed errore →) $$f(x) - s(x) = \frac{f''(\xi)}{2}(x - x_i)(x - x_{i+1}).$$ La funzione $q(x) = (x - x_i)(x - x_{i+1})$ è una parabola con zeri nei nodi e minimo nel punto medio, dove vale $-\left(\frac h2\right)^2 = -\frac{h^2}{4}$; quindi $|q| \le \frac{h^2}{4}$ e $$|f - s| \le \frac{\max|f''|}{2}\cdot\frac{h^2}{4} = \frac{h^2}{8}\max|f''|.$$

(c) Numero di intervalli

Con $\max|f''| = 1$ e $h = \frac{\pi}{N}$: $\frac{h^2}{8} \le 10^{-3} \iff h \le \sqrt{8\cdot 10^{-3}} = 0{,}08944 \iff N \ge \frac{\pi}{0{,}08944} = 35{,}12$, quindi $\mathbf{N = 36}$ intervalli ($h = 0{,}0873$). Verifica numerica: con $N = 36$ il maggiorante vale $9{,}52\cdot10^{-4}$ e l'errore massimo effettivo $9{,}51\cdot 10^{-4}$ (quasi uguale: il massimo di $|\sin|$ è $1$ nell'intervallo contenente $\frac\pi2$ e il punto medio coincide quasi con il massimo); con $N=35$ il maggiorante sarebbe $1{,}007\cdot 10^{-3} > 10^{-3}$.

(d) Dimezzare il passo

L'errore è $O(h^2)$: dimezzando $h$ si divide per $4$. Con polinomi di grado $d$ a tratti l'errore è $O(h^{d+1})$: quadratica a tratti ($d=2$) darebbe $O(h^3)$, divisione per $8$; cubica $O(h^4)$ (divisione per $16$).

Risultati. $s(0{,}8) = \mathbf{0{,}696653}$ (errore $0{,}0207 \le 0{,}03125$); $N = \mathbf{36}$ intervalli.

Errori tipici

• Usare $\frac{h^2}{4}$ o $\frac{h^2}{2}$ al posto di $\frac{h^2}{8}$: il fattore $\frac18$ viene da $\frac12$ (formula dell'errore) per $\frac14$ (massimo di $|q|$).
• Inserire $h$ come larghezza totale $b-a$ invece che come ampiezza del singolo intervallo.