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 ${\varphi }_j(x)$ per $j=1,\dots ,n$, che siano linearmente indipendenti.

Consideriamo la combinazione lineare

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

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

Problema: dobbiamo determinare la funzione $\varphi =\sum _{j=0}^n{\alpha }_j{\varphi }_j(x)$, tale che $\varphi (x_i)=y_i\mathrm{\forall }i=0,\dots ,n$.

Si può anche avere già $f$ continua tale che $f(x_i)=y_i\mathrm{\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 $\epsilon >0$ esiste $n=n(\epsilon )$ e un polinomio $p_n$ tale che

$|f-p_n|=\underset{x\in [a,b]}{max}|f(x)-p_n(x)|\le \epsilon$

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\mathrm{\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\mathrm{\forall }i=1,\dots n$

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

$B𝒂=𝒚$

dove $𝒂=(a_0,\dots ,a_n{)}^t$, $𝒚=(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

$detB(x_0,x_1,\dots ,x_n)=\prod _{i>j,i,j=0}^n(x_i-x_j)\text{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

$detB(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)=detB(z,x_1,\dots ,x_n)=(z-x_1)(z-x_2)\ast \dots \ast (z-x_n)\ast k(x_1,\dots ,x_n)$

Valuto $p_n$ in 0.

$p_n(0)=(-1{)}^n\ast k\ast \prod _{i=0}^n{x}_i,\text{relazione }\circ$

Inoltre per definizione:

$p_n(0)=detB(0,x_1,\dots ,x_n)=detB(2:n,2:n)$

e sappiamo che

$B(2:n,2:n)=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\mathrm{(}{\mathrm{x}}_{\mathrm{1}},\mathrm{\dots },{\mathrm{x}}_{\mathrm{n}}\mathrm{)}\mathrm{\ast }\begin{array}{cccc}\mathrm{1}& {\mathrm{x}}_{\mathrm{1}}& \mathrm{\dots }& {\mathrm{x}}_{\mathrm{1}}^{\mathrm{n}\mathrm{-}\mathrm{1}}\\ \mathrm{1}& {\mathrm{x}}_{\mathrm{2}}& \mathrm{\dots }& {\mathrm{x}}_{\mathrm{2}}^{\mathrm{n}\mathrm{-}\mathrm{1}}\\ \mathrm{\dots }& \mathrm{\dots }& \mathrm{\dots }& \mathrm{\dots }\\ \mathrm{1}& {\mathrm{x}}_{\mathrm{n}}& \mathrm{\dots }& {\mathrm{x}}_{\mathrm{n}}^{\mathrm{n}\mathrm{-}\mathrm{1}}\end{array}$

quindi

$p_n(0)=detB(x_1,\dots ,x_n)\ast \prod _{i=0}^n{x}_i\text{formula }\circ \circ$

ed eguagliando le due espressioni di $p_n(0)$:

$(-1{)}^n\ast k(x_1,\dots ,x_n)\ast \prod _{i=0}^n{x}_i=detB(x_1,x_n)\ast \prod _{i=0}^n{x}_i$

quindi per $k$ ricavo l'espressione:

$k=(-1{)}^{n}detB(x_1,\dots ,x_n)$

Ipotesi induttiva: $detB(x_1,\dots ,x_n)=\prod _{i>j,i,j=1}^n(x_i-x_j)$ Allora

$detB(x_0,x_1,\dots ,x_n)=\prod _{j=1}^n(x_0-x_j)\ast k$

$=(-1{)}^n(x_1-x_0)\ast (x_2-x_0)\ast \dots \ast (x_n-x_0)\ast detB(x_1,\dots ,x_n))\ast (-1{)}^n$

$=(x_1-x_0)\ast (x_2-x_0)\ast \dots \ast (x_n-x_0)\ast \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,\mathrm{\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,{\overline{p}}_n$ di grado $n$ interpolanti, cioè che hanno come radici gli $x_i$, allora consideriamo $q_n=p_n-{\overline{p}}_n$, di grado $n$, che ha $n+1$ zeri. Infatti $q_n(x_i)=p_n(x_i)-{\overline{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{\varphi }_i(x)$

dove ${\alpha }_i=y_i$ (sono le ordinate degli $x_i$) e ${\varphi }_i=l_i(x)$ con ${\lambda }_i(x)$ polinomio di Lagrange.

$l_i(x)=\prod _{j\ne 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\ne x_i$, segue che $x_k={\overline{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$.