Osservazioni introduttive

Introduzione del problema

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

Considero la combinazione lineare

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

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

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

Si può anche avere già $f$$f$ continua tale che $f(x_{i})=y_{i}\forall i$$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$$f$ continua su $[a,b]$$[a,b]$, allora per ogni $\varepsilon >0$$\varepsilon>0$ esiste $n=n(\varepsilon )$$n=n(\varepsilon )$ e un polinomio $p_{n}$$p_n$ tale che

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

$$\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, considero $(x_{i},y_{i})_{i=0}^{n}$$(x_{i},y_{i})_{i=0}^{n}$ e considero $p_{n}$$p_n$ tale che $p_{n}(x_{i})=y_{i}$$p_{n}(x_{i})=y_{i}$ per $i=0,\dots ,n$$i=0,\dots ,n$ (polinomio interpolante).

Teorema 5.2 (teorema di esistenza e unicità)

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

 

Dimostrazione (Dimostrazione teorica)

Scrivo

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

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

e impongo le $n+1$$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$$

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

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

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

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

dove ${\boldsymbol {a}}=(a_{0},\dots ,a_{n})^{t}$${\boldsymbol {a}}=(a_{0},\dots ,a_{n})^{t}$, ${\boldsymbol {y}}=(y_{0},\dots ,y_{n})$${\boldsymbol {y}}=(y_{0},\dots ,y_{n})$, e $B=B(x_{0},\dots ,x_{n})$$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}}$$

$${\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$$

$$\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}$$x_0$ sostituisco la generica variabile $z$$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}}$$

$$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})$$

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

è un polinomio nella variabile $z$$z$ di grado $n$$n$ per la formula di Laplace. Inoltre questo polinomio si annulla in $x_{1},x_{2},\dots ,x_{n}$$x_{1},x_{2},\dots ,x_{n}$ perché se a $z$$z$ sostituisco $x_{i}$$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})$$

$$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}$$p_n$ in 0.

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

$$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)$$

$$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}}}}$$

$$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$$

$$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)$$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}$$

$$(-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$$k$ ricavo l'espressione:

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

$$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})$$\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$$

$$\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}$$

$$=(-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})$$

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

e ho dimostrato la formula $\ast$$\ast$.

 

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

Dimostrazione (dimostrazione costruttiva)

L'obbiettivo è, come prima, quello di cercare un polinomio tale che $p_{n}(x_{i})=y_{i},\,\forall i=0,\dots ,n$$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}$$p_{n},{\bar {p}}_{n}$ di grado $n$$n$ interpolanti, cioè che hanno come radici gli $x_{i}$$x_i$, allora considero $q_{n}=p_{n}-{\bar {p}}_{n}$$q_{n}=p_{n}-{\bar {p}}_{n}$, di grado n, che ha $n+1$$n+1$ zeri. Infatti $q_{n}(x_{i})=p_{n}(x_{i})-{\bar {p}}_{n}(x_{i})=y_{i}-y_{i}=0$$q_{n}(x_{i})=p_{n}(x_{i})-{\bar {p}}_{n}(x_{i})=y_{i}-y_{i}=0$ allora $q_{n}$$q_{n}$ è identicamente nullo e quindi $p_{n}(x)=q_{n}(x)$$p_{n}(x)=q_{n}(x)$.

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

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

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

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

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

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

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

1. se $x_{k}=x_{i}$$x_{k}=x_{i}$, tutti i numeratori sono uguali ai denominatori e si ottiene
   $$l_{i}(x)=1$$

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

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

Calcolo $p_{n}$$p_n$ in $x_{j}$$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}$$

$$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 ho verificato la condizione di interpolazione per ogni $j=0,\dots ,n$$j=0,\dots,n$.