# Interpolazione polinomiale

L'interpolazione polinomiale è l'interpolazione di una serie di valori (ad esempio dei dati sperimentali) con una funzione polinomiale che passa per i punti dati. In particolare, un qualsiasi insieme di $n+1$ punti distinti può essere sempre interpolato da un polinomio di grado $n$ che assume esattamente il valore dato in corrispondenza dei punti iniziali.

## Interpolazione e approssimazione

L'interpolazione polinomiale è un caso particolare di approssimazione tramite polinomi, dove il vettore degli scarti $r,$ ossia il vettore dei quadrati della distanza tra il valore dato in un punto e il valore del polinomio approssimante in quel punto è nullo. Mentre per l'approssimazione polinomiale si vuole trovare un polinomio (generalmente di basso grado) che approssima i punti dati con un errore minimo, nell'interpolazione si vuole trovare il polinomio (potenzialmente di alto grado) che passa esattamente per quei punti.
Sebbene il polinomio di interpolazione assuma il valore esatto nei punti dati, dato il grado superiore esso tenderà ad oscillare maggiormente tra un punto e l'altro, dando quindi una previsione del valore in quelle aree che sarà peggiore di quella data da un polinomio di grado inferiore che non passa per tutti i punti dati. Questo fenomeno è noto come fenomeno di Runge.

## Costruzione di un polinomio di interpolazione

Un polinomio di interpolazione può essere costruito con diversi metodi, ad esempio ricorrendo alla matrice di Vandermonde o alla formula di interpolazione di Lagrange.

## Esistenza del polinomio interpolatore

Dati $n+1$ punti $(x_{i},y_{i})$ distinti, dove $y=f(x)$, dobbiamo determinare il polinomio (eventualmente unico) di grado minimo che passa per i punti assegnati.
    $(x_{i},y_{i}),\qquad i=0,1,\ldots ,n,\qquad y_{i}=f(x_{i}).$

### Teorema di unicità del polinomio interpolatore

Esiste uno ed un sol polinomio di grado al più $n$ che assume valori $y_{i}$, $i=0,1,\ldots ,n$, in corrispondenza di $n+1$ punti distinti $x_{i}$, $i=0,1,\ldots ,n$.

#### Dimostrazione

Abbiamo preso $n+1$ punti così da poter usare un polinomio di grado $n$ che ha $n+1$ coefficienti
    $P_{n}(x)=a_{0}+a_{1}x+\dots +a_{n}x^{n}$
e imporre le condizioni
    ${\begin{cases}a_{0}+a_{1}x_{0}+\dots +a_{n}x_{0}^{n}=y_{0}\\a_{0}+a_{1}x_{1}+\dots +a_{n}x_{1}^{n}=y_{1}\\\qquad \vdots \\a_{0}+a_{1}x_{n}+\dots +a_{n}x_{n}^{n}=y_{n}.\end{cases}}$
I parametri incogniti $a_{0},a_{1},\ldots ,a_{n}$ sono soluzione del seguente sistema quadrato di ordine $n+1$. Dovremo quindi risolvere il sistema associato
    $Ax=b$
    $\left({\begin{array}{ccccc}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n}\\\end{array}}\right)\left({\begin{array}{c}a_{0}\\a_{1}\\\vdots \\a_{n}\end{array}}\right)=\left({\begin{array}{c}y_{0}\\y_{1}\\\vdots \\y_{n}\end{array}}\right),$
dove $A$ è la classica matrice di Vandermonde, che risulta non singolare se e solo se $x_{i}\neq x_{j}$ per $i\neq j$ (e quindi $x_{i}-x_{j}\neq 0$), dato che
    $\det(V)=\prod _{n\geq i>j\geq 1}(x_{i}-x_{j})=\prod _{j=0}^{n-1}\left[\prod _{i=j+1}^{n}\underbrace {(x_{i}-x_{j})} _{\neq 0}\right].$
Essendo la matrice non singolare, si ha che il polinomio di grado $n$ esiste ed è unico.
Il sistema ci è servito per stabilire l'esistenza di $P_{n}(x)$ ma non è consigliato risolvere il sistema per due motivi:
* i sistemi con matrici di Vandermonde sono mal condizionati;
* il numero di operazioni aritmetiche necessarie è elevato.

## Esempio di interpolazione

Di una funzione $f$ che in altra sede è nota si supponga di conoscere alcuni valori; in particolare si considerino i seguenti valori tabulati
| x | f(x) |
| 0 | 0 |
| 1 | 0,8415 |
| 2 | 0,9093 |
| 3 | 0,1411 |
| 4 | −0,7568 |
| 5 | −0,9589 |
| 6 | −0,2794 |
Ci si chiede, per esempio: quanto vale la funzione in $x=2,5$? L'interpolazione risolve problemi come questo.
Il seguente polinomio di sesto grado passa attraverso tutti i sette punti dati:
    $f(x)=-0,0001521x^{6}-0,003130x^{5}+0,07321x^{4}-0,3577x^{3}+0,2255x^{2}+0,9038x.$
Sostituendo $x=2,5,$ si ha che $f(2,5)=0,5965.$
L'errore di interpolazione è proporzionale alla distanza fra i punti dati alla potenza $n.$ Inoltre questo interpolante, essendo un polinomio, è illimitatamente differenziabile. Quindi l'interpolazione polinomiale, in linea di principio, risolve tutti i problemi di interpolazione lineare.
Tuttavia questo metodo presenta alcuni svantaggi. Il calcolo che porta ai coefficienti del polinomio d'interpolazione è molto "costoso" (in termini di tempo di esecuzione richiesto al calcolatore e in termini di complessità delle elaborazioni). Inoltre, l'interpolazione polinomiale per il complesso dei valori dalla variabile indipendente non si rivela molto esatta; questo accade in particolare nei punti estremi. Questi svantaggi possono essere evitati usando i metodi dell'interpolazione spline o razionale col metodo Floater Hormann.

## Interpolazione di funzioni su calcolatore

Su calcolatore l'interpolazione polinomiale è soggetta a diversi problemi. Il peggiore è sicuramente il mal condizionamento della matrice dei coefficienti (che assume la forma di matrice di Vandermonde). Ciò si traduce nella impossibilità di poter risolvere il sistema di equazioni con metodi standard come decomposizione LU o sostituzione all'indietro, infatti al crescere del numero dei nodi cresce il sistema e l'indice di condizionamento si fa sempre più grande.
Per calcolare i coefficienti del polinomio interpolante, senza dover risolvere il sistema di equazioni mal condizionato, viene utilizzata l'interpolazione di Lagrange oppure l'interpolazione spline.
I software per il calcolo numerico sono, il più delle volte, provvisti di funzioni built-in per risolvere questi problemi.
Su MATLAB vengono utilizzati due comandi per interpolare una funzione tramite polinomi:
* polyfit per calcolare il polinomio interpolante su un insieme di nodi noti;
* polyval per valutare il polinomio su punti in cui non si conosce la $f(x).$
La scelta dei nodi da utilizzare per l'interpolazione viene fatta in modo da soddisfare la proprietà di convergenza uniforme tra funzione interpolante e funzione da interpolare, scegliendo i nodi in modo che non siano equidistanti.
Sulla scelta influiscono diverse cause:
* Teorema di Faber: data una qualunque successione di nodi in un intervallo chiuso $[a,b]$ esiste sempre una funzione $f(x)$ che genera una sequenza di polinomi di interpolazione che non convergono uniformemente a $f$ in $[a,b]$.
* Fenomeno di Runge: nell'intervallo $[-5,5]$ la funzione $f(x)=1/(1+x^{2})$ se interpolata con una funzione $p(x)$ mostra che all'aumentare del numero di nodi (equidistanti) $p(x)$ non converge a $f(x)$ ma l'errore aumenta.
Ciò che viene fatto generalmente è scegliere i nodi utilizzando la definizione di nodi di Čebyšëv che assicurano la convergenza uniforme all'aumentare del numero di nodi.
Su MATLAB i nodi di Čebyšëv su un intervallo $[a,b]$ vengono calcolati eseguendo la funzione:
nchev conterrà alla fine un vettore riga che rappresenta i nodi (x) da utilizzare per interpolare la funzione.

## Stima dell'errore

Siano dati $n+1$ punti distinti, $x_{0},x_{1},\ldots ,x_{n}$ dell'intervallo chiuso e limitato $[a,b]\subset \mathbb {R}$. Sia $f(x)$ una funzione assegnata nello spazio $C^{n+1}[a,b]$ e $p(x)$ il polinomio di grado n tale che:
$p(x_{i})=f(x_{i}),\qquad i=0,1,\ldots ,n.$
Allora per ogni $x\in [a,b]$ esiste un valore
    $\zeta _{x}$, con $E(x)=f(x)-p(x)={\frac {1}{(n+1)!}}(x-x_{0})(x-x_{1})\ldots (x-x_{n})f^{(n+1)}(\zeta _{x})$
con $E(x)$ definito errore di interpolazione, ossia l'errore che si commette approssimando il valore della funzione col valore del polinomio.
Posto $M_{n+1}=\max _{x\in [a,b]}|f^{(n+1)}(x)|$, un limite superiore del valore assoluto dell'errore di interpolazione $E(x)=f(x)-p(x)$ risulta essere $|E(x)|\leq {\frac {M_{n+1}}{(n+1)!}}|(x-x_{0})(x-x_{1})\ldots (x-x_{n})|$.
Questa formula è molto utile per stimare, ad esempio, il numero di nodi necessari ad ottenere un errore di interpolazione minore di una data tolleranza massima.

## Nodi di Čebyšëv

I nodi di Čebyšëv sono dei valori sull'asse delle ascisse, da utilizzare per l'interpolazione polinomiale di una funzione, che permettono di minimizzare l'errore di interpolazione.