Interpolare: una guida per principianti!

Un vecchia battuta (oggi si chiamano meme) recitava: ci sono due tipi di persone; chi sa estrapolare informazioni da dati incompleti.

Per quanto vecchia resta sempre attuale e i temi dell’estrapolazione e dell’interpolazione restano quanto mai cruciali nell’ambito delle discipline scientifiche e non solo. In questo post ci andremo a concentrare sull’interpolazione. La scelta non è casuale in quanto l’autore del post tiene in grande considerazione questa forma di analisi mentre ritiene molto meno utile ed affidabile l’estrapolazione.

Prima di passare ai concetti matematici veri e propri bisogna tracciare lo scenario in cui ci muoveremo e prima ancora capire perché l’interpolazione sia cosi importante.

Perché interpolare: un esempio concreto

Immaginiamo di avere un qualche strumento che acquisisce dei dati scientifici ad intervalli regolari e che quindi dalle msiure effettuate otteniamo una lista di valori puntuali.

Indice	Dati
1	13.6
2	13.3
3	11.9
4	11.0
5	13.5
6	11.2
7	11.3

Un elenco di dati di questo tipo ci dice cosa sta accadendo al mommento della misura ma non ci dice nulla su quello che accade tra due misure consecutive. Una tabella di questo tipo può essere rappresentata graficamente al seguente modo.

Il modo corretto di rappresentare questi dati è una serie di punti che corrisponde alle misure disponibili. Nessuna linea dovrebbe essere presente tra i vari dati proprio ad indicare che non abbiamo alcuna informazione tra due misure consecutive. Molti rappresentano questo tipo di dati unendo i punti con delle linee continue ma questo non dovrebbe essere fatto con tanta disinvoltura. L’interpolazione ci viene in contro proprio per colmare questo vuoto, ecco l’interpolazione fa proprio questo, ci fornisce un modo per colmare il vuoto tra due misure consecutive.

In principio era l’interpolazione lineare

Come spesso avviene nel mondo della scienza la forma più semplice di interpolazione è quella lineare. Detto in parole povere una semplice linea retta che unisce due punti consecutivi. Nel nostro caso avendo un totale di 7 punti avremo un totale di 6 linee differenti che uniscono coppie di punti consecutivi. In generale dato $ n $ il numero di punti totali a disposizione il numero di linee che avremo è $ n-1 $.

Dati due punti consecutivi nella nostra tabella indicati come $(x_i , y_i)$ e $(x_{i+1}, y_{i+1})$ l’interpolazione lineare non fa altro che assegnare ad ogni valore di $x$ compreso nell’intervallo $[x_i , x_{i+1}]$ la media ponderata tra $y_i$ e $y_{i+1}$.

L’eqauzione dell’interpolazione lineare si può scrivere come

$f(x) = \frac{x_{i+1} – x}{x_{i+1}-x_i}y_i+\frac{x-x_i}{x_{i+1}-x_i}y_{i+1}$

Facendo riferimento alla tabella riportata sopra otteniamo che l’interpolazione lineare dei dati da il seguente risultato

L’interpolazione lineare è la più semplice da implementare ma presenta alcuni svantaggi anche.

Interpolazione n-sima

La naturale estensione dell’interpolazione lineare è quella di tipo polinomiale. Da un punto di vista più generico una retta non è null’altro che un polinomio di ordine 1. Detto ciò viene quasi naturale chiedersi cosa avviene se invece di utilizzare un polinomio di ordine 1 si utilizzano polinomi di ordine superiore per l’interpolazione dei dati.

Quando si parla di interpolazione polinomiale alcune considerazionidiventano davvero importani e possono influire sul risultato finale.

La prima importante considerazione riguarda la complessità del problema, infatti l’interpolazione polinomiale rispetto a quella lineare presenta uno sforzo per il calcolo dei coefficienti nettamente superiore e, come ci si può immaginare tale sforzo aumenta con il grado del polinomio.

La seconda considerazione importante da fare è che dati $n$ punti questi possono essere interpolati con un polinomio di ordine massimo $n-1$ in quanto siamo limitati dal numero di condizioni al contorno che possiamo imporre (al massimo $n$).

Terza considerazione riguarda l’unicità della soluzione. Infatti dato un insieme di $n$ punti il polinomio di ordine $n-1$ che interpola tali punti è unico e questo costituisce un grande vantaggio per tutta una serie di applicazioni.

Quarta, ed ultima, considerazione è che un polinomio è infinitamente derivabile in tutti i suoi punti per cui possiamo derivare quante volte vogliamo il nostro polinomio di grado $n-1$ senza temere per la continuità dello stesso. Gran bel vantaggio rispetto all’interpolazione lineare!

Passiamo ora alla parte matematica che l’interpolazione polinomiale si porta dietro. Per fare ciò partiamo con l’esprimere l’equazione generale di un polinomio

$p_n(x)=a_0 x^n + a_1 x^{n-1} + a_2 x^{n-2} + … + a_n$

Abbiamo quindi un vettore di $n$ coefficienti che indicheremo con $a$ e un vettore di $n$ condizioni da soddisfare (i punti in cui conosciamo il valore esatto) che indicheremo con $s$. Possiamo dunque scrivere la seguente relazione

$V_x a=s$

Dove $V_x$ rappresenta la matrice di Vandermonde delle $x$ dei nostri dati. Tale matrice ha dimensione $nxn$ e va invertita al fine di trovare il vettore dei coefficienti incogniti $a$.

Per il caso in esame applicando l’equazione otteniamo un interpolazione con polinomio di ordine 6 come quella mostrata in figura.

Tale metodo è molto complesso e computazionalmente molto costoso. Fortunatamente se invece che a disegnare l’intero polinomio siamo interessati al valore che il polinomio assume in un punto specifico possiamo ricorrere ai coefficienti di Lagrange e ridurre drasticamente il costo computazionale del problema.

Gli alti e bassi dei polinomi

Un ultima nota sull’interpolazione polinomiale riguarda il loro andamento oscillante (come si può vedere anche dalla figura sopra). Questo comportamento oscillante viene chiamato fenomeno di Runge e prende nome dal matematico e fisico tedesco Carl David Tolmé Runge che si occupò di tale problema. Il fenomeno di Runge, per dirla in modo semplice, ci dice che l’errore del polinomio interpolante aumenta agli estremi dell’intervallo di interpolazione e aumenta con il grado del polinomio.

Per fortuna ci sono alcuni metodi per evitare l’insorgere di questo problema, tra i più comuni:

• Evitare che i punti di interpolazione siano equispaziati tra di loro;
• Suddividere il dominio in domini più piccoli su cui interpolare usando polinomi di ordine inferiore (ordine 1 oppure ordine 2)

Volendo quindi riepilogare quanto detto fino ad ora abbiamo che:

Oltre i polinomi

Ovviamente, il modo migliore per eliminare gli svantaggi dell’interpolazione polinomiale è non utilizzare l’interpolazione polinomiale per nulla. In questo caso ci viene in aiuto l’interpolazione mediante spline.

Le spline sono un pò come tornare al passato dell’interpolazione, invece di considerare l’intero intervallo si considerano coppie di punti adiacenti. La differenza rispetto all’interpolazione lineare?

In questo caso le funzioni interpolanti non sono delle rette ma dei polinomi di ordine fisso e basso. I vantaggi di semplicità e basso costo computazionale si uniscono alla possibilità di avere derivate continue come per i polinomi.

La spline più semplice a cui possiamo pensare è la spline di Hermite. La spline di Hermite è un polinomio di grado 3 derivabile una volta sola per tanto il suo andamento sarà continuo ma non lo sarà la sua curvatura. La spline di Hermite assume la forma

$p(x)=ax^3+bx^2+cx+d$

Il polinomio presenta 4 coefficienti incogniti e avremo per tanto bisogno di 4 equazioni per chiudere il sistema e poterlo risolvere. Considerando che la unisce i punti $(x_i,Y_i)$ e $(x_{i+1},y_{i+1})$ le prime due condizioni si ottengono imponendo il passaggio della spline per i due punti considerati. Ma questo ci porta alla considerazione che mancano ancora 2 equazioni per chiudere il sistema. La derivata prima della spline di Hermite si può scrivere come

$p'(x)=3ax^2+2bx+c$

Le condizioni da imporre sono ai punti estremi dell’intervallo e riguardano il valore della derivata prima in quei due punti. In questo caso possiamo scegliere due approcci

• La spline di Hermite naturale si ottiene imponendo che le due derivate agli estrimi dell’intervallo siano nulle e che quindi sia $p'(x_i)=0$ e $p'(x_{i+1}) = 0$.
• La seconda scelta ci porta alla spline di Catmull-Rom e consiste nell’imporre la seguente condizione

$p'(x_i)=\frac{y_{i+1}-y_{i-1}}{x_{i+1}-x_{i-1}}$ e $p'(x_{i+1})=\frac{y_{i+2}-y_{i}}{x_{i+2}-x_{i}}$

Cosi abbiamo ottenuto le 4 condizioni che ci servono per definire il sistema.

Di seguito riportiamo anche la spline di Hermite che interpola i dati proposti.

Come è possibile vedere la spline di Hermite presenta oscillazioni molto meno marcate rispetto al polinomio di ordine.

Ma se volessimo di più? Se volessimo trovare un espressione che ci dia anche una derivata seconda continua dobbiamo trovare una nuova formulazione. La spline di tipo cubico è quella che fa al caso nostro.. L’espressione di una spline cubica è la stessa di una spline di Hermite ma cambiano le condizioni al contorno da imporre.

Dati $n$ punti possiamo definire $n-1$ polinomi, ricordate quanto fatto con le linee dell’interpolazione lineare. Questi $n-1$ polinomi hanno ognuno 4 coefficienti per un totale di $4n-4$ incognite da risolvere. Ma quali condizioni imporre?

• La prima condizione rigurda il passaggio per i punti $y_i$, ovvero che $p_i(x_i)=Y_i$ e questo ci da un totale di $2n-2$ incognite.
• Dobbiamo imporre la continuità della derivata prima ovvero che $p’_{i-1}(x_i)=p’_i(x_i)$ che ci da altre $n-2$ condizioni al contorno
• Imponendo la continuità anche per le derivate seconde $p”_{i-1}(x_i)=p”_i(x_i)$ aggiungiamo altre $n-2$ condizioni al contorno

Il totale delle condizioni al contorno è di $4n-6$ a dispetto dei $4n-4$ coefficienti del nostro sistema. Altre due condizioni al contorno sono dunque richieste. Anche in questo caso dobbiamo fare una scelta:

• Una spline cubica di tipo naturale si ottiene imponendo che $p”_0(x_0)=0$ e che $p”_{n-1}(x_n)=0$
• Una spline cubica vincolata si ottiene invece imponendo che $p’0(x_0)=f'(x_0)$ e che $p'{n-1}(x_n)=f'(x_0)$

Questo aggiunge le due condizioni che mancano per completare il sistema e trovare la soluzione al problema dell’interpolazione.

Quando anche le spline non bastano

Quando le spline non sembrano essere adeguate per l’interpolazione che abbiamo in mente possiamo ricorrere all’ultima arma a disposizione degli interpolatori seriali. Stiamo parlando delle spline di Bézier (anche chiamate b-spline). Ma perché queste sarebbero diverse dalle spline normali?

Le spline di Bézier sono diverse perché invece di utilizzare dei polinomi di ordine $n$ per interpolare basano il loro funzionamento sulle curve di Bézier.

Una spline di Bézier è definita nella seguente formula

$C(u)=\sum_{i=0}^{n-1} N_{i,p}P_i$

Nell’equazione scritta sopra $P_i$ rappresentano gli $n$ punti di controllo presenti nei nostri dati mentre $N_{i,p}$ sono coefficienti che dipendono dal punto i-esimo e dal grado $p$ del polinomio e possono essere calcolati mediante le formule ricorsive di Cox – De Boor. Per cui otteniamo che

$N_{i,0}(u)=1$ se $u_i < u < u_{i+1}$ altrimenti vale $0$

$N_{i,p}(u)=\frac{u-u_i}{u_{i+p}-u_i}N_{i,p-1}(u)+\frac{u_{i+p+1}-u}{u_{i+p+1}-u_{i+1}}N_{i+1,p-1}(u)$

Per risolvere il problema della curva di Bézier dobbiamo trovare un set di coefficienti, detti punti di controllo, che servono per definire la curva. Per calcolare tali punti di controllo incogniti dobbiamo risolvere il seguente sistema lineare

$D=N*P$

Dove $P$ rappresenta l’insieme dei punti di controllo incognito, $D$ invece è l’insieme dei dati a disposizione per cui la curva deve necessariamente passare e $N$ è la matrice dei coefficienti $N_{i,p}$ come definiti prima.

Tiriamo le somme

Abbiamo detto che l’interpolazione è uno strumento molto utile ma anche complesso ed un uso improprio può essere fuorviante nell’analisi ed interpretazione dei dati.

Diversi metodo possono essere utilizzati, da quelli più semplici come l’interpolazione lineare a quelli più elaborati come le spline e le b-spline. Ogni metodo presenta comunque dei vantaggi e degli svantaggi che possono renderli più o meno appropriati nelle diverse applicazioni.

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.