Calcolo numerico/Interpolazione polinomiale

Introduzione del problema

Consideriamo $n+1$ coppie di dati, $(x_{i},y_{i})_{i=0}^{n}$, e fissiamo un modello di approssimazione. Abbiamo un set di funzioni $\phi _{j}(x)$ per $j=1,\dots ,n$, che siano linearmente indipendenti.

Consideriamo la combinazione lineare

$\sum _{j=0}^{n}\alpha _{j}\phi _{j}(x)$

che restituisce 0 se e solo se $\alpha _{j}=0\forall j$.

Problema: dobbiamo determinare la funzione $\phi =\sum _{j=0}^{n}\alpha _{j}\phi _{j}(x)$, tale che $\phi (x_{i})=y_{i}\forall i=0,\dots ,n$.

Si può anche avere già $f$ continua tale che $f(x_{i})=y_{i}\forall i$, ma può essere conveniente approssimarla con polinomi.

Teorema 5.1 (teorema di Iston-Weierstrass)

Data una funzione $f$ continua su $[a,b]$, allora per ogni $\varepsilon >0$ esiste $n=n(\varepsilon )$ e un polinomio $p_{n}$ tale che

$\vert f-p_{n}\vert =\max _{x\in [a,b]}|f(x)-p_{n}(x)|\leq \varepsilon$

Quindi, data una funzione continua, è una buona idea quella di usare polinomi per approssimarla.

Esistenza e unicità dell'interpolazione

Nella pratica, consideriamo $(x_{i},y_{i})_{i=0}^{n}$ e consideriamo $p_{n}$ tale che $p_{n}(x_{i})=y_{i}$ per $i=0,\dots ,n$ (polinomio interpolante).

Teorema 5.2 (teorema di esistenza e unicità)

Dati $(x_{i},y_{i})_{i=1}^{n}$ nodi a due a due disgiunti, allora esiste ed è unico il polinomio $p_{n}(x)$ al più di grado $n$ tale che $p_{n}(x_{i})=y_{i}\forall i$.

Dimostrazione (dimostrazione teorica)

Scriviamo

$p_{n}(x)=a_{0}+a_{1}x+a_{2}x^{2}+\dots +a_{n}x^{n}$

e imponiamo le $n+1$ condizioni di interpolazione:

$p_{n}(x_{i})=\sum _{j=1}^{n}a_{j}(x_{i})^{j}=y_{i}\forall i=1,\dots n$

e abbiamo $n+1$ equazioni in $n+1$ incognite, equivalenti al sistema:

$B{\boldsymbol {a}}={\boldsymbol {y}}$

dove ${\boldsymbol {a}}=(a_{0},\dots ,a_{n})^{t}$, ${\boldsymbol {y}}=(y_{0},\dots ,y_{n})$, e $B=B(x_{0},\dots ,x_{n})$ è una matrice con la seguente struttura:

${\begin{array}{ccccc}1&x_{0}&x_{0}^{2}&\dots &x_{0}^{n}\\1&x_{2}&x_{2}^{2}&\dots &x_{2}^{n}\\\dots &\dots &\dots &\dots &\dots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n}\end{array}}$

e una matrice di questo tipo è detta di Vandermonde.

Si dimostra che

$\det B(x_{0},x_{1},\dots ,x_{n})=\prod _{i>j,i,j=0}^{n}(x_{i}-x_{j})\quad {\hbox{formula }}\ast$

e siccome i nodi sono a due a due distinti per ipotesi, il determinante è diverso da 0, ovvero esiste ed è unico il polinomio interpolante perché il sistema si può risolvere e tutti i coefficienti sono determinati.

Dimostrazione (dimostrazione della formula $\ast$)

Consideriamo la matrice di Vandermonde in cui al nodo $x_{0}$ sostituisco la generica variabile $z$, quindi

$B(z,x_{1},x_{2},\dots ,x_{n})={\begin{array}{ccccc}1&z&z^{2}&\dots &z^{n}\\1&x_{1}&x_{1}^{2}&\dots &x_{1}^{n}\\\dots &\dots &\dots &\dots &\dots \\1&x_{n}&x_{n}^{2}&\dots &x_{n}^{n}\end{array}}$

Allora

$\det B(z,x_{1},\dots ,x_{n})$

è un polinomio nella variabile $z$ di grado $n$ per la formula di Laplace. Inoltre questo polinomio si annulla in $x_{1},x_{2},\dots ,x_{n}$ perché se a $z$ sostituisco $x_{i}$, trovo una matrice con due righe uguali che ha determinante nullo. Allora si avrà:

$p_{n}(z)=\det B(z,x_{1},\dots ,x_{n})=(z-x_{1})(z-x_{2})*\dots *(z-x_{n})*k(x_{1},\dots ,x_{n})$

Valuto $p_{n}$ in 0.

$p_{n}(0)=(-1)^{n}*k*\prod _{i=0}^{n}x_{i},\quad {\hbox{relazione }}\circ$

Inoltre per definizione:

$p_{n}(0)=\det B(0,x_{1},\dots ,x_{n})=\det B(2:n,2:n)$

e sappiamo che

$B(2:n,2:n)={\rm {{diag}(x_{1},\dots ,x_{n})*{\begin{array}{cccc}1&x_{1}&\dots &x_{1}^{n-1}\\1&x_{2}&\dots &x_{2}^{n-1}\\\dots &\dots &\dots &\dots \\1&x_{n}&\dots &x_{n}^{n-1}\end{array}}}}$

quindi

$p_{n}(0)=\det B(x_{1},\dots ,x_{n})*\prod _{i=0}^{n}x_{i}{\hbox{formula }}\circ \circ$

ed eguagliando le due espressioni di $p_{n}(0)$:

$(-1)^{n}*k(x_{1},\dots ,x_{n})*\prod _{i=0}^{n}x_{i}=\det B(x_{1},x_{n})*\prod _{i=0}^{n}x_{i}$

quindi per $k$ ricavo l'espressione:

$k=(-1)^{n}\det B(x_{1},\dots ,x_{n})$

Ipotesi induttiva: $\det B(x_{1},\dots ,x_{n})=\prod _{i>j,i,j=1}^{n}(x_{i}-x_{j})$ Allora

$\det B(x_{0},x_{1},\dots ,x_{n})=\prod _{j=1}^{n}(x_{0}-x_{j})*k$

$=(-1)^{n}(x_{1}-x_{0})*(x_{2}-x_{0})*\dots *(x_{n}-x_{0})*\det B(x_{1},\dots ,x_{n}))*(-1)^{n}$

$=(x_{1}-x_{0})*(x_{2}-x_{0})*\dots *(x_{n}-x_{0})*\prod _{j<i,j=1}^{n}(x_{j}-x_{i})$

e abbiamo dimostrato la formula $\ast$.

Nota: spesso la matrice di Vandermonde è mal condizionata, quindi nella pratica non si usa questo procedimento per ottenere i polinomi interpolanti.

Dimostrazione (dimostrazione costruttiva)

L'obiettivo è, come prima, quello di cercare un polinomio tale che $p_{n}(x_{i})=y_{i},\,\forall i=0,\dots ,n$ (condizione di interpolazione).

Premettiamo che i polinomi interpolanti sono unici, infatti, supponiamo per assurdo che esistano due polinomi $p_{n},{\bar {p}}_{n}$ di grado $n$ interpolanti, cioè che hanno come radici gli $x_{i}$, allora consideriamo $q_{n}=p_{n}-{\bar {p}}_{n}$, di grado $n$, che ha $n+1$ zeri. Infatti $q_{n}(x_{i})=p_{n}(x_{i})-{\bar {p}}_{n}(x_{i})=y_{i}-y_{i}=0$ allora $q_{n}$ è identicamente nullo e quindi $p_{n}(x)=q_{n}(x)$.

Consideriamo una combinazione lineare di un opportuno set di funzioni (polinomi di Lagrange):

$p_{n}(x)=\sum _{i=0}^{n}\alpha _{i}\phi _{i}(x)$

dove $\alpha _{i}=y_{i}$ (sono le ordinate degli $x_{i}$) e $\phi _{i}=l_{i}(x)$ con $\lambda _{i}(x)$ polinomio di Lagrange.

$l_{i}(x)=\prod _{j\neq i,j=0}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}$

Valutando $l_{i}(x)$ in un qualsiasi nodo $x_{k}$, segue che

1. se $x_{k}=x_{i}$, tutti i numeratori sono uguali ai denominatori e si ottiene $l_{i}(x)=1$
2. se invece $x_{k}\neq x_{i}$, segue che $x_{k}={\bar {x}}_{j}$, quindi un numeratore si annulla, e $l_{i}(x_{k})=0$.

In forma sintetica $l_{i}(x_{k})=\delta _{ik}$.

Calcoliamo $p_{n}$ in $x_{j}$:

$p_{n}(x_{j})=\sum _{i=0}^{n}y_{i}l_{i}(x_{j})=\sum _{i=0}^{n}y_{i}\delta _{ij}=y_{j}$

e abbiamo verificato la condizione di interpolazione per ogni $j=0,\dots ,n$.