Interpolazione: polinomio di Lagrange, fenomeno di Runge, nodi di Chebyshev e spline
Esistenza e unicità del polinomio interpolante, errore di interpolazione, fenomeno di Runge, nodi di Chebyshev, spline lineari e cubiche e loro applicazioni.
Spesso una funzione si conosce solo in alcuni punti: i valori di una tabella, le misure di un esperimento, i campioni di un segnale, la curva caratteristica di un sensore fornita dal costruttore. Interpolare vuol dire costruire una funzione semplice che passa esattamente per quei punti, per stimare i valori intermedi. In questa lezione vediamo il polinomio interpolante, il fenomeno di Runge che ne mostra i limiti, i nodi di Chebyshev e le spline.
Il polinomio interpolante
Dati 
punti 
con ascisse distinte, esiste uno e un solo polinomio di grado al massimo 
che passa per tutti.
Dimostrazione dell’unicità. Se due polinomi 
e 
di grado al più passano per gli stessi punti, la differenza 
ha grado al più e si annulla in punti distinti. Un polinomio non nullo di grado ha al massimo radici, quindi 
.
La forma di Lagrange. Si costruiscono i polinomi di base
![\[ \ell_i(x) = \prod_{j \ne i}\frac{x - x_j}{x_i - x_j} \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-8023c75bdf21158b90c262f216457303_l3.png "Rendered by QuickLaTeX.com")
che valgono 1 in 
e 0 in tutti gli altri nodi. Allora
![\[ p_n(x) = \sum_{i=0}^{n}y_i\,\ell_i(x) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-9122bfaf5654256c569edce72232a445_l3.png "Rendered by QuickLaTeX.com")
passa per tutti i punti. Esempio: per 
, 
, 
si ottiene 
. La forma di Lagrange è elegante per le dimostrazioni; per i calcoli si usa la forma di Newton con le differenze divise, che permette di aggiungere un punto senza ricalcolare tutto.
L’errore di interpolazione
Se 
ha derivate continue, per ogni 
esiste 
nell’intervallo tale che
![\[ f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n + 1)!}\,\prod_{i=0}^{n}(x - x_i) \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-03950ea35a952bde177b8ff58b528f68_l3.png "Rendered by QuickLaTeX.com")
L’errore dipende da due fattori: quanto è “liscia” la funzione (la derivata di ordine alto) e come sono distribuiti i nodi (il prodotto).
Il fenomeno di Runge
Viene naturale pensare che aumentando i punti l’interpolazione migliori sempre. Non è così. Runge, nel 1901, studiò la funzione
![\[ f(x) = \frac{1}{1 + 25x^2},\qquad x\in[-1, 1] \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-d95e63e5250f73c41306f721be1ebbd0_l3.png "Rendered by QuickLaTeX.com")
perfettamente regolare, e la interpolò con nodi equidistanti.
Con nodi equidistanti, aumentando il grado l’errore vicino agli estremi cresce senza limite: con 21 nodi il polinomio raggiunge valori sopra 50, mentre la funzione sta tra 0 e 1. La causa è il prodotto 
, che con nodi equidistanti è molto più grande vicino agli estremi che al centro. (Il motivo profondo è complesso, nel senso dei numeri complessi: ha poli in 
, vicini all’intervallo.)
La lezione pratica: non usare polinomi di grado alto su nodi equidistanti. È lo stesso motivo per cui un fit polinomiale di grado 10 su dati sperimentali produce curve con oscillazioni assurde tra i punti.
I nodi di Chebyshev
Se si possono scegliere i nodi, conviene addensarli verso gli estremi. I nodi di Chebyshev in ![[-1, 1]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-2fffd161eb968602f002a855e0974f48_l3.png "Rendered by QuickLaTeX.com")
sono
![\[ x_i = \cos\frac{(2i + 1)\pi}{2(n + 1)},\qquad i = 0, \dots, n \]](https://www.electronics-engineering.com/wp-content/ql-cache/quicklatex.com-d7b81917e5f208e9af9d4402f71be9ee_l3.png "Rendered by QuickLaTeX.com")
le proiezioni sull’asse di punti equidistanti su una semicirconferenza. Rendono il prodotto 
il più piccolo possibile (al massimo 
), e con essi l’interpolazione di funzioni regolari converge sempre. È il principio con cui le librerie numeriche approssimano le funzioni matematiche.
Le spline
L’alternativa più usata in pratica è interpolare a tratti: tra ogni coppia di nodi un polinomio di grado basso, raccordati in modo liscio.
- Lineare a tratti: si uniscono i punti con segmenti. Semplice e senza oscillazioni, ma con spigoli. È ciò che fa un foglio di calcolo con un grafico a linee, e una lookup table in un microcontrollore.
- Spline cubica: tra due nodi un polinomio di terzo grado, con valori, derivate prime e derivate seconde continue nei nodi. È la curva più “liscia” che passa per i punti: minimizza l’integrale del quadrato della derivata seconda, cioè l’energia di flessione di un’asta elastica costretta a passare per i punti. È esattamente l’origine del nome: lo spline era il listello di legno flessibile che i disegnatori navali tenevano con dei pesi per tracciare le curve degli scafi.
I coefficienti si trovano risolvendo un sistema lineare tridiagonale, che si risolve in 
operazioni. Le spline non soffrono del fenomeno di Runge e l’errore con passo 
è proporzionale a 
.
Applicazioni. Le curve dei font (TrueType usa curve di Bézier quadratiche, PostScript e OpenType cubiche), le traiettorie dei robot e delle macchine a controllo numerico, la linearizzazione di sensori come termocoppie e termistori a partire dalle tabelle del costruttore, il ricampionamento dell’audio e delle immagini.
Interpolazione e approssimazione
L’interpolazione ha senso quando i dati sono esatti. Se sono misure affette da rumore, costringere la curva a passare per ogni punto vuol dire seguire anche il rumore. In quel caso si cerca una curva semplice che passi vicino ai punti nel complesso: è l’approssimazione ai minimi quadrati, l’argomento della prossima lezione.
