%% Copyright (C) 2007 Alvise Sommariva. This is a free document; you can redistribute it and/or modify
%% it under the terms of the GNU General Public License as published by
%% the Free Software Foundation; either version 2 of the License, or
%% at your option) any later version. This document is distributed in the hope that it will be useful,
%% but WITHOUT ANY WARRANTY; without even the implied warranty of
%% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%% GNU General Public License for more details. You should have received a copy of the GNU General Public License
%% along with this program; if not, write to the Free Software
%% Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA}
\documentclass[10pt]{beamer}
\input{hal_prefs}

\setlength{\tabcolsep}{2.5pt}
\setbeamertemplate{navigation symbols}{} %no nav symbols
\title[Interpolazione polinomiale \hspace{2em}\insertframenumber/
\inserttotalframenumber]{Interpolazione polinomiale}
\author{Alvise Sommariva}
\institute{Universit\`a degli Studi di Padova}
\date{\today}
\begin{document}
\frame{\titlepage}



\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale}

\smnsp

{\small{

\begin{problema}[Interpolazione polinomiale]
Siano dati {\purples{$n+1$}} punti $x_0,\ldots,x_n$ a due a due distinti e i valori $y_0,\ldots,y_n$ 
(assunti ad esempio da una funzione $y=f(x)$).

\smsp

Il problema dell'{\blues{\href{https://it.wikipedia.org/wiki/Interpolazione\_polinomiale}{interpolazione polinomiale}}} (cf. \cite[p.131]{ATK}) consiste nel calcolare
il polinomio $p_n(x)=a_0+\ldots+a_n x^n$ di grado {\purples{$n$}} tale che

\smnsp
\bc
\btc[width=7cm]
\begin{equation}
{p_n(x_i)=y_i, \, \, i=0,\ldots,n.}
\end{equation}
\etc
\ec
\end{problema}

\smnsp

\begin{esempio}
Dati $2$ punti distinti $x_0,x_1$ e i valori $y_0,y_1$, determinare il polinomio $p_1$ di grado $1$ tale che

\smnsp

\begin{equation}
p_1(x_0)=y_0,  \,\,\,\, p_1(x_1)=y_1
\end{equation}
ovvero la retta che {\it{passa}} per le coppie $(x_0,y_0)$, $(x_1,y_1)$.
\end{esempio}

In questa sezione mostreremo che questo polinomio {\underline{interpolatore}} {\purples{$p_n$ esiste ed \mye unico e come calcolarlo}}.

\smsp

Di seguito denoteremo con ${\mathbb{P}}_n$ l'insieme dei polinomi il cui grado \mye al pi\myu $n$.
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}

 \begin{figure}\label{fig1aa8a}
 \centering
 {\includegraphics[scale=0.4,clip]{esintp.eps}}
 \caption{Esempio di interpolazione della funzione $f(x)=\exp(x) \sin(x)+\cos(x)$ (in nero) mediante un polinomio di grado 3 (in rosso) in 4 punti equispaziati di $[0,\pi]$ (cerchietti in verde). Sono stati esposti i grafici delle funzioni e le coppie $\{(x_k,y_k)\}_{k=0,\ldots,3}$, ove $x_k=k\pi/3$ e $y_k=f(x_k)$, $k=0,\dots,3$.}
 \end{figure}
\end{frame}


\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}

\smnsp

{\footnotesize{

\begin{teorema}[Unicit\mya del polinomio interpolatore]
Dati $n+1$ punti distinti $x_0,x_1,\ldots,x_n$ e i valori $y_0,y_1,\ldots,y_n$ il polinomio $p_n$ di grado al pi\myu $n$ tale che

\smnsp

$$
p_n(x_i)=y_i, \,\,\,\, i=0,\ldots,n.
$$

\smnsp

\mye al pi\myu unico.
\end{teorema}

\begin{dimostrazione}
La dimostrazione procede per assurdo.
Supponiamo che esistano due polinomi distinti $p_n$ e $q_n$ di grado al pi\myu $n$ tali che

\smnsp

$$
p_n(x_i)=y_i, \,\,\,\, q_n(x_i)=y_i, \,\,\,\, i=0,\ldots,n.
$$
Allora il polinomio $p_n-q_n$ ha grado $n$ in quanto differenza di due polinomi di grado $n$ ed \'e pure
$$
(p_n-q_n)(x_i)=p_n(x_i)-q_n(x_i)=0 , \,\,\,\, i=0,\ldots,n.
$$
e quindi per un certo polinomio non nullo $\gamma(x)$, dal teorema di Ruffini per la fattorizzazione dei polinomi si ha che $$(p_n-q_n)(x)=\gamma(x) 	\cdot \prod_{k=0}^n (x-x_k)=\gamma(x) \cdot (x-x_0) \cdot (x-x_1) \cdot \ldots \cdot (x-x_n)$$ e quindi $p_n-q_n$ mye un polinomio di grado almeno $n+1$, il che \mye assurdo.
\end{dimostrazione}

}}

\end{frame}




\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}

Per studiare l'esistenza del polinomio interpolatore, {\blues{\href{https://it.wikipedia.org/wiki/Interpolazione\_di\_Lagrange}{Lagrange}}} (cf. \cite{GAUPAP}, {\cite{WIKLI}}) osserv\myo nel 1792 che il polinomio di grado $n$ (detto appunto di Lagrange, ma gi\'a noto a Waring nel 1779)
{\small{
\bc
\btc
\smnsp
\smnsp
$$
L_k(x):= \prod_{j=0, j\neq k}^n {\frac{x-x_j}{x_k-x_j}} =
{\frac{ (x-x_0)\ldots(x-x_{k-1})(x-x_{k+1}) \ldots (x-x_n) }{ (x_k-x_0)\ldots(x_k-x_{k-1})(x_k-x_{k+1}) \ldots (x_k-x_n)  }}
$$
\etc
\ec
}}
\mye tale che 

\bc
\btc[width=5cm]
$$ L_k(x_j)=\delta_{k,j}$$
\etc
\ec

dove $\delta_{k,j} $ \mye l'operatore di Kronecker, il cui valore \mye $1$ se $k=j$ e $0$ se $k \neq j$.

{\footnotesize{
\begin{nota}
Osserviamo che ogni $L_k$ \'e un polinomio di grado $n$ e quindi una funzione continua. Di conseguenza non \'e vero che vale $0$ ovunque eccetto in $x_k$ dove vale $1$ (sarebbe una funzione discontinua!).

Abbiamo esclusivamente descritto il valore del polinomio di Lagrange $L_k$ nelle ascisse di interpolazione $x_j$ con $j=0,\ldots,n$.
\end{nota}
}}

\end{frame}




\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}
{\small{
\begin{teorema}[Esistenza del polinomio interpolatore]
Dati $n+1$ punti distinti $x_0,x_1,\ldots,x_n$ e i valori $y_0,y_1,\ldots,y_n$, il polinomio di grado al pi\myu $n$
\bc
\btc[width=9.5cm]
\smnsp
\smnsp
\begin{equation}\label{2}
p_n(x)= \sum_{k=0}^n y_k L_k(x)=y_0 L_0(x)+ y_1 L_1(x) +\ldots + y_n L_n(x)
\end{equation} 
\smnsp
\smnsp
\etc
\ec
\mye tale che {\purples{$
p_n(x_i)=y_i, \,\,\,\, i=0,\ldots,n.$}}
\end{teorema}

\smnsp

\begin{dimostrazione}
Poich\mye {\purples{$L_k$ \mye un polinomio di grado al pi\myu $n$}}, lo \mye certamente lo stesso moltiplicato per lo scalare $y_k$ e la somma di polinomi di grado al pi\myu $n$. Quindi sicuramente $p_n \in {\mathbb{P}}_n$.

\smsp

Inoltre {\purples{$p_n$ interpola i dati}} visto che per $j=0,1,\ldots,n$
\begin{eqnarray}\label{2x}
p_n(x_j)&=& y_0 \underbrace{L_0(x_j)}_{0}+\ldots+ y_{j-1}\underbrace{L_{j-1}(x_j)}_{0}+y_{j}\underbrace{L_j(x_j)}_{1}+y_{j+1}\underbrace{L_{j+1}(x_j)}_{0}+\ldots+y_{n}\underbrace{L_n(x_j)}_{0} \nonumber \\
&=& y_0 \cdot 0+\ldots+y_{j-1} \cdot 0+y_j \cdot 1+y_{j+1} \cdot 0 + \ldots + y_{n} \cdot 0 = y_j \nonumber
\end{eqnarray}

Quindi $p_n$ \mye un polinomio interpolatore.
\end{dimostrazione}

}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}


\begin{nota}
\begin{enumerate}
\item [1.] Il teorema precedente \mye {\purples{costruttivo}}, in quanto non solo permette di stabilire l'esistenza del polinomio interpolatore, ma ne evidenzia un metodo di calcolo.
\item [2.] Si osservi inoltre come ogni termine della sommatoria $$p_n(x)= \sum_{k=0}^n y_k L_k(x)$$ {\purples{separa (in qualche senso) il contributo}} delle ordinate $y_k$ da quello dei polinomi di Lagrange $L_k$ essenzialmente dipendenti dai punti $\left\{x_j\right\}_{j=0,\ldots,n}$ (si rifletta bene su questa affermazione).
\end{enumerate}
\end{nota}
\end{frame}

\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}

\smnsp

{\fns{
\begin{nota}[Esistenza e unicit\'a via matrice di Vandermonde]

Se $$p_n(x)=\sum_{k=0}^{n} a_k x^k=a_0+a_1 x+\ldots+ a_n x^n$$ \'e il polinomio interpolatore allora  $p_n(x_j)=y_j$ per $j=0,\ldots,n$ e quindi

\begin{equation}\label{Vc}
\left\{
\begin{array}{l}
a_0+a_1 x_0+\ldots+ a_n x_0^n=y_0 \\
\ldots+\ldots+\ldots+ \ldots=\ldots \\
a_0+a_1 x_j+\ldots+ a_n x_j^n=y_j \\
\ldots+\ldots+\ldots+ \ldots=\ldots \\
a_0+a_1 x_n+\ldots+ a_n x_n^n=y_n
\end{array}
\right.
\end{equation}

Definiamo
\begin{itemize}
\item la {\blues{\href{https://it.wikipedia.org/wiki/Matrice\_di\_Vandermonde}{matrice di Vandermonde}}} $V=(v_{i,j})=(x_i^j), \smhsp 0\leq i,j \leq n$
ovvero
$$
V=
\begin{bmatrix} 
1 & x_0 & x^2_0 & \ldots & x^n_0 \\
1 & x_1 & x^2_1 & \ldots & x^n_1 \\
\ldots & \ldots & \ldots & \ldots & \ldots \\
1 & x_{n-1} & x^2_{n-1} & \ldots & x^n_{n-1} \\
1 & x_n & x^2_n & \ldots & x^n_n 
\end{bmatrix} 
$$
\item $y=(y_0,\ldots,y_n)^T$;
\item $a=(a_k)_{k=0,\ldots,n}$  i coefficienti del polinomio interpolatore $p_n(x)=\sum_{k=0}^{n} a_{k}x^k$.
\end{itemize}

\end{nota}
}}
\end{frame}

\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore (facoltativo)}

\smnsp

{\small{
\begin{vuoto}
Utilizzando questa notazione, il problema dell'interpolazione polinomiale (\ref{Vc}) \'e equivalente alla risoluzione del sistema lineare

\bc
\btc[width=2.5cm]
\begin{center}
Va=y
\end{center}
\etc
\ec

\smsp

Poich\'e si mostra che $\det(V)=\prod_{0 \leq i < j \leq n} (x_j-x_i) \neq 0$, ovvero la matrice $V$ \mye non singolare (in alcuni testi dicono {\it{invertibile}}), e quindi dal teorema di Rouch\'e-Capelli
\begin{enumerate}
\item il problema $Va=y$ ha una e una sola soluzione $a^*=(a^*_0,\ldots,a^*_n)$;
\item dal punto precedente esistono e sono unici gli $a^*_k$, $k=0,\ldots,n$ che siano coefficienti del polinomio interpolatore; in altri termini, il polinomio interpolatore $$p_n(x)=\sum_{k=0}^{n} a^*_{k}x^k$$ si pu\'o determinare  {\it{risolvendo}} il sistema lineare {\purples{$Va=y$}} avente dimensione $(n+1) \times (n+1)$, cos\'i da determinare univocamente i coefficienti $a^*_k$, $k=0,\ldots,n$ del polinomio interpolatore, che altro non sono che le componenti del vettore soluzione $a^*$.
\end{enumerate}

\end{vuoto}
}}
\end{frame}














\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}

\smnsp

\begin{esempio}
Calcolare il polinomio di grado 2 che assume nei nodi $x_0=-2$, $x_1=1$, $x_2=3$ rispettivamente i valori $y_0=-2$, $y_1=11$, $y_2=17$. 
\end{esempio}

{\footnotesize{
Dalla definizione, $L_k(x):= \prod_{j=0, j\neq k}^n {\frac{x-x_j}{x_k-x_j}} $ e quindi
\begin{eqnarray}
 L_0(x) &=&  { \frac {(x-x_1)(x-x_2)} {(x_0-x_1)(x_0-x_2)} } = { \frac {(x-1)(x-3)} {(-2-1)(-2-3)} } = { \frac {(x-1)(x-3)} {15} } \nonumber \\
 L_1(x) &=&  { \frac {(x-x_0)(x-x_2)} {(x_1-x_0)(x_1-x_2)} } = { \frac {(x-(-2))(x-3)} {(1-(-2))(1-3)} } = { \frac {(x+2)(x-3)} {-6} } \nonumber\\
 L_2(x) &=&  { \frac {(x-x_0)(x-x_1)} {(x_2-x_0)(x_2-x_1)} } = { \frac {(x-(-2))(x-1)} {(3-(-2))(3-1)} } = { \frac {(x+2)(x-1)} {10} } \nonumber
\end{eqnarray}
I polinomi $L_0$, $L_1$, $L_2 \in {\mathbb{P}}_2$ (e quindi tali le loro combinazioni lineari), e
\begin{itemize}
\item $L_0(x_0)=L_0(-2)=1$,  $L_0(x_1)=L_0(1)=0$,  $L_0(x_2)=L_0(3)=0$;
\item $L_1(x_0)=L_1(-2)=0$,  $L_1(x_1)=L_1(1)=1$,  $L_1(x_2)=L_1(3)=0$;
\item $L_2(x_0)=L_2(-2)=0$,  $L_2(x_1)=L_2(1)=0$,  $L_2(x_2)=L_2(3)=1$.
\end{itemize}
}}

\end{frame}


\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}

\smnsp

 \begin{figure}\label{fig1aaa}
 \centering
 {\includegraphics[scale=0.265,clip]{L0_2023.eps}}
 {\includegraphics[scale=0.265,clip]{L1_2023.eps}}
 {\includegraphics[scale=0.265,clip]{L2_2023.eps}}
 
 \smnsp
 \caption{I polinomi di Lagrange $L_0$, $L_1$, $L_2$ relativi ai punti $x_0=-2$, $x_1=1$, $x_2=3$.}
 \end{figure}
\end{frame}


\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}
Essendo 
\begin{itemize}
\item $p_2(x)= \sum_{k=0}^2 y_k L_k(x)=y_0 \, L_0(x) + y_1 \, L_1(x) + y_2 \, L_2(x)$,
\item $y_0=-2$,  $y_1=11$,  $y_2=17$
\end{itemize}
il polinomio interpolatore risulta
$$p_2(x)=-2 \, L_0(x) + 11 \, L_1(x) + 17 \, L_2(x).$$
In effetti \mye tale che
\begin{itemize}
\item ${\purples{p(x_0)}}=-2 \, L_0(x_0) + 11 \, L_1(x_0) + 17 \, L_2(x_0)= -2 \cdot 1 + 11 \cdot  0 + 17 \cdot  0 ={\purples{-2}},$
\item ${\purples{p(x_1)}}=-2 \, L_0(x_1) + 11 \, L_1(x_1) + 17 \, L_2(x_1)= -2 \cdot 0 + 11 \cdot  1 + 17 \cdot  0 ={\purples{11}},$
\item ${\purples{p(x_2)}}=-2 \, L_0(x_2) + 11 \, L_1(x_2) + 17 \, L_2(x_2)= -2 \cdot 0 + 11 \cdot  0 + 17 \cdot  1 ={\purples{17}},$
\end{itemize}
quindi \mye proprio il polinomio interpolante cercato, visto che assume in
\begin{itemize} 
\item $x_0=-2$ il valore $y_0=-2$,
\item $x_1=1$ il valore $y_1=11$,
\item $x_2=3$ il valore $y_2=17$,
\end{itemize}
come richiesto.
\end{frame}




\begin{frame}[fragile]
\frametitle{Esistenza e unicit\mya del polinomio interpolatore}

\begin{nota}
Dal punto di vista pratico, ({\ref{2}}) ha alcuni problemi. 

\smsp

Se dopo aver
calcolato il polinomio $p_N$ interpolante in $N+1$ punti $$(x_0,y_0),
\ldots, (x_N,y_N)$$ desideriamo ottenere il polinomio $p_{N+1}$
interpolante in $N+2$ punti $$(x_0,y_0),
\ldots, (x_N,y_N),(x_{N+1},y_{N+1})$$ la formula
({\ref{2}}) \mye inefficiente poich\mye bisogna ricalcolare da capo tutti i polinomi di Lagrange. 

\smsp

Fortunatamente, esistono altre maniere di esprimere il
polinomio interpolatore, come quella di {\blues{\href{https://en.wikipedia.org/wiki/Newton_polynomial}{Newton}}} (cf. \cite[p.138]{ATK}, \cite{WIKIN}, \cite{WIKNP}), che non risentono di questo problema.
\end{nota}
\end{frame}




\begin{frame}[fragile]
\frametitle{Errore di interpolazione}

Per quanto concerne l'errore compiuto nell'approssimare una funzione $f$ con il polinomio $p_n$ tale che $y_k=f(x_k)$, $k=0,\ldots,n$ vale il seguente teorema,

\begin{teorema}[Errore di interpolazione, Cauchy (1840)]\label{errint}
Sia $f \in C^{n+1}([a,b])$ e si supponga che $x_0,\ldots,x_n \in [a,b]$ siano a 2 a 2 distinti e che il polinomio $p_n \in {\mathbb{P}}_n$ sia tale che
$$
p_n(x_k)=f(x_k), \,\,\,\, k=0,\ldots,n.
$$
Allora
\bc
\btc
\begin{equation}\label{2a}
{\purples{E_n[f](x)}}:=f(x)-p_n(x)= {\purples{f^{(n+1)}(\xi) {\frac { \prod_{i=0}^{n} (x-x_i)  }{(n+1)!}}}}
\end{equation}
\etc
\ec
dove $\xi \in I$ con $I$ il pi\myu piccolo intervallo aperto contenente $x_0,\ldots,x_n$ e il valore $x$.
\end{teorema}
\end{frame}




\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale (dimostrazione facoltativa)}

\smnsp

{\tiny{
\begin{dimostrazione}[Errore di interpolazione, Cauchy (1840), facoltativa]

Il teorema di Rolle asserisce che se $f$ \'e una funzione continua definita in un intervallo chiuso $[a,b]$, derivabile in ogni punto dell'intervallo aperto 
$(a,b)$, tale che $f(a)=f(b)$, allora esiste almeno un punto $c \in (a,b)$ in cui $f'(c)=0$.

Se $x=x_i$, per qualche $i$, l'asserto \mye ovvio.

Altrimenti, sia $x \neq x_i$, $i=0,\ldots,n$ e poniamo per $z \in [a,b]$

\begin{equation}\label{teq}
{\purples{\boxed{G(z)=E_n[f](z)-w(z) Q(x),}}}
\end{equation}

\smnsp


dove 
\begin{itemize}
\item $w(z)=\prod_{i=0}^n (z-x_i)$ \mye un polinomio di grado $n+1$,
\item $Q(x)=E_n[f](x)/w(x)$.
\end{itemize}
Si noti che in (\ref{teq}) la funzione $Q$ viene valutata in $x$ e non in $z$.

Osserviamo che essendo ${\purples{G(z)=E_n[f](z)-w(z) Q(x)}}$, ove
\begin{itemize}
\item $E_n[f](z):=f(z)-p_n(z)$,
\item $w(z)=\prod_{i=0}^n (z-x_i)$ \mye un polinomio di grado $n+1$,
\item $Q(x)=E_n[f](x)/w(x)$.
\end{itemize}

\noindent abbiamo

$$
{{\purples{G(x)=}}E_n[f](x)-w(x) Q(x)} =E_n[f](x)-w(x) (E_n[f](x)/w(x)) ={\purples{0}},
$$
$$
{\purples{G(x_k)}}=E_n[f](x_k)-w(x_k) Q(x) =0-0\cdot Q(x)={\purples{0}}, {\mbox{  }}k=0,\ldots,n
$$
Dato che 
\begin{itemize}
\item $f \in C^{n+1}([a,b])$,  $p_n \in C^{\infty}([a,b])$, sicuramente $E_n[f] \in C^{n+1}([a,b])$,
\item $w \in C^{\infty}([a,b])$,
\item $Q(x)$ \mye un numero (si osservi che $Q$ non dipende da $z$),
\end{itemize}
deduciamo che ${\purples{G}} \in  C^{n+1}([a,b])$ e {\purples{si annulla in $n+2$ punti}}. 

\end{dimostrazione}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale (dimostrazione facoltativa)}

\smnsp
\smnsp

{\tiny{
\begin{vuoto}

Sia ${\cal{I}}(x,x_0,\ldots,x_n)$ il pi\myu piccolo intervallo aperto contenente $x,x_0,\ldots,x_n$. Per il teorema di Rolle {\cite{WIKRT}}, visto che $G$ si annulla in $n+2$ punti, allora 
\begin{itemize}
\item $G^{(1)}$ si annulla in $n+1$ punti di  ${\cal{I}}(x,x_0,\ldots,x_n)$,
\item $G^{(2)}$ si annulla in $n$ punti di  ${\cal{I}}(x,x_0,\ldots,x_n)$,
\item $G^{(k)}$ si annulla in $n+2-k$ punti di  ${\cal{I}}(x,x_0,\ldots,x_n)$,
\item {\purples{$G^{(n+1)}$ si annulla in $1$ punto $\xi$ di  ${\cal{I}}(x,x_0,\ldots,x_n)$}}.
\end{itemize}
Indicata con $D^n f$ la derivata $n$-sima di $f$, abbiamo
\begin{itemize}
\item $D^{n+1}p_n \equiv 0$ ($p_n$ ha grado $n$),
\item $D^{n+1}w \equiv 0$ ($w$ ha grado $n$),
\end{itemize}
visto che $Q(x)$ \mye costante (non dipende da $z$), ${{G(z)=E_n[f](z)-w(z) Q(x)}}$,

\bignsp

\begin{eqnarray}
G^{(n+1)}(z)&=&D^{n+1} E_n[f](z) - Q(x) D^{n+1} w(z) \nonumber \\ &=&D^{n+1} (f(z)-p_n(z)) - Q(x) D^{n+1} w(z)  \nonumber \\ &=& f^{(n+1)}(z)-Q(x) \cdot (n+1)!
\end{eqnarray}
Da $Q(x)=E_n[f](x)/w(x)$


\bignsp

$$
0=G^{(n+1)}(\xi) = f^{(n+1)}(\xi)-Q(x) \cdot (n+1)! =f^{(n+1)}(\xi)-\frac{E_n[f](x)}{w(x)} \cdot (n+1)!
$$

\smnsp

per cui riarrangiando i termini

\smnsp

$$
E_n[f](x)= f^{(n+1)}(\xi) {\frac { w(x)  }{(n+1)!}} = f^{(n+1)}(\xi) {\frac { \prod_{i=0}^{n} (x-x_i)  }{(n+1)!}}.
$$
\end{vuoto}
}}
\end{frame}












\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale}

\smnsp

Si osservi che \mye noto che esiste $\xi$ tale che
$$
{{E_n[f](x)}}:=f(x)-p_n(x)= {\purples{f^{(n+1)}(\xi) {\frac { \prod_{i=0}^{n} (x-x_i)  }{(n+1)!}}}}$$
ma non si sa in generale chi sia. Quindi non si pu\myo dire esattamente quanto sia l'errore compiuto. 

\smsp

Noto $$M=\max_{s \in [a,b]} | f^{(n+1)}(s) |$$ si pu\'o {\purples{stimare l'errore compiuto}}, in quanto per ogni $x \in [a,b]$
\begin{eqnarray}
 |f(x)-p_n(x)| &=& \left|f^{(n+1)}(\xi) {\frac { \prod_{i=0}^{n} (x-x_i)  }{(n+1)!}}\right|
 =  |f^{(n+1)}(\xi)| {\frac { |\prod_{i=0}^{n} (x-x_i) | }{(n+1)!}} \nonumber \\
 &\leq& M  {\frac {| \prod_{i=0}^{n} (x-x_i)  |}{(n+1)!}}.
\end{eqnarray}

\end{frame}

\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale}

Visto che 
$$
|g(x)| \leq M |h(x)|, \smhsp \forall x \in [a,b] \Rightarrow {\purples{\max_{x\in[a,b]}|g(x)|}} \leq \max_{x\in[a,b]} M |h(x)| ={\purples{M \max_{x\in[a,b]} |h(x)|}},
$$
ponendo 
\begin{itemize}
\item $g(x)=f(x)-p_n(x)$, 
\item $h(x)= { {| \prod_{i=0}^{n} (x-x_i)  |}/{(n+1)!}}$
\end{itemize}
e visto che
\begin{equation}
 |f(x)-p_n(x)| \leq M  {\frac {| \prod_{i=0}^{n} (x-x_i)  |}{(n+1)!}}.
\end{equation}

\bignsp
\begin{eqnarray}
{\color{red}{\max_{x \in [a,b]} |f(x)-p_n(x)|}} &\leq& M \max_{x \in [a,b]} {\frac {| \prod_{i=0}^{n} (x-x_i)  |}{(n+1)!}} \nonumber \\
&=&{\color{red}{\frac{M}{(n+1)!} \max_{x \in [a,b]}  {\left| \prod_{i=0}^{n} (x-x_i)  \right| }}} \nonumber
\end{eqnarray}
\smnsp
\smnsp

e quindi risulta possibile valutare il massimo errore compiuto.

\end{frame}




\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale}
\begin{esempio}
Sia $f(x)=\exp(x)$ e sia $p_4$ il polinomio che interpola $f$ nei punti equispaziati $x_i=-1+2i/4 $, $i=0,\ldots,4$.
Stimare l'errore di interpolazione.
\end{esempio}

{\footnotesize{
\begin{itemize}
\item Essendo $f^{(k)}(x)=\exp(x)$, per $k=0,1,\ldots$ ed $\exp(x)$ una funzione crescente, abbiamo
$$
{\purples{M}}=\|f^{(5)}\|_{\infty}=\max_{x \in [-1,1]} |\exp(x)|={\purples{\exp(1) \approx 2.7183}}.
$$
\item Inoltre, come si pu\myo vedere dal grafico in figura, {\purples{$\prod_{i=0}^4 |x-x_i| \leq 0.12$}}. 
\item Visto che {\purples{$5!=120$}}, abbiamo che se $E_n[f]$ \mye il massimo errore compiuto in $[-1,1]$ nell'approssimare la funzione $f$ con l'interpolante $p_4$ nei nodi equispaziati $\{x_i\}_{i=0,\ldots,4}$, dal teorema \ref{errint}, fissato $x \in [-1,1]$
$$
|E_4[f](x)| =|f^{(5)}(\xi)| {\frac { \prod_{i=0}^{n}| (x-x_i) | }{5!}} \leq \frac{\exp(1) \cdot 0.12}{120}\approx 0.0027.
$$
\item L'esperimento numerico in figura mostra che in effetti l'errore \mye minore di $1.2 \cdot 10^{-3} < 2.7 \cdot 10^{-3}$.
Si osservi come il grafico sia tale che $E_4[f]$ si annulla ovviamente nei $5$ punti di interpolazione $x_i$, $i=0,\ldots,4$. 
\end{itemize}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale}
 \begin{figure}[h!]\label{bisae}
 \centering
   {\includegraphics[scale=0.25,clip]{err_polypart.eps}}
   {\includegraphics[scale=0.25,clip]{err_polypart2.eps}}
 \caption{ \newline A {\purples{sinistra}}, il grafico di $\prod_{i=0}^4 |x-x_i|$ dove $x_i=-1+2i/4$, $i=0,\ldots,4$. 
 \smsp
 \newline A {\purples{destra}}, il grafico dell'errore $|E_n[f]|$ in $[-1,1]$ che evidentemente \mye sempre minore di $1.2 \cdot 10^{-3}$ e quindi della stima $2.7 \cdot 10^{-3}$. Tale errore \'e nullo nei punti $x_0,\ldots,x_4$ (punti di interpolazione).}
 \end{figure} 


\end{frame}




\begin{frame}[fragile]
\frametitle{Convergenza dell'interpolazione polinomiale}


{\footnotesize{
Relativamente al problema della {\bf{scelta dei punti in cui interpolare}}
la funzione continua $f:[a,b] \rightarrow \R$, spesso si considerano le seguenti distribuzioni:

\begin{enumerate}
\item nodi {\purples{equispaziati}}: fissato $n$, i punti sono
\bc
\btc[width=7.5cm]
\smnsp
\begin{equation}
x_k=a+ k \, {\frac {(b-a) } {n}   }, \, \, k=0,\ldots,n ;
\end{equation}
\etc
\ec
\item nodi di {\blues{{\href{https://en.wikipedia.org/wiki/Chebyshev\_nodes}{Chebyshev}}}} (scalati): fissato $n$, i punti sono
\begin{equation}
x_k={\frac {(a+b) } {2}   } + {\frac {(b-a) } {2}   } \, t_k,  \, \,
k=0,\ldots,n
\end{equation}
con

\bc
\btc[width=7.5cm]
\smnsp
\begin{equation}
t_k=\cos \left(     {\frac {2k+1} {2n+2} }   \, \pi  \right), \, k=0,\ldots,n;
\end{equation}
\etc
\ec

\item nodi di {\purples{Chebyshev-Lobatto}} (scalati): fissato $n$, i punti sono
\begin{equation}
x_k={\frac {(a+b) } {2}   } + {\frac {(b-a) } {2}   } \, t_k,  \, \,
k=0,\ldots,n
\end{equation}
con
\bc
\btc[width=7.5cm]
\smnsp
\begin{equation}\label{CGL}
t_k=- \cos \left(     {\frac {k \pi} {n} }    \right), \, k=0,\ldots,n;
\end{equation}
\etc
\ec
\end{enumerate}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Convergenza dell'interpolazione polinomiale}

\smnsp

\begin{nota}[Interpretazione geometrica dei punti di Chebyshev-Lobatto]
\fns{
Il set di $n+1$ punti di Chebyshev-Lobatto in $[-1,1]$, utili per l'interpolazione polinomiale a grado $n$, si ottengono proiettando i punti equispaziati nell'angolo della semicirconferenza {\purples{$
\gamma=\{\left( \cos(\theta),\sin(\theta) \right): \theta \in [0,\pi]\}
$}}
sull'asse delle ascisse.

\smsp

Nell'esempio, 
\begin{itemize}
\item i punti in rosso sulla circonferenza sono ($\cos(k\pi/6),\sin(k\pi/6)$) con $k=0,\ldots,6$, 
\item i punti in blu sono ($\cos(k\pi/6),0$) con $k=0,\ldots,6$ cio\'e quelli di (\ref{CGL}), a parte l'ordinamento.
\end{itemize}
}

\smnsp

 \begin{figure}\label{figch}
 \centering
   {\includegraphics[scale=0.25,clip]{chebproj.eps}}
 \caption{Interpretazione geometrica dell'insieme dei punti di Chebyshev-Lobatto utili per determinare un'interpolante polinomiale di grado $n=6$.}
 \end{figure}
 
 \smnsp
  \smnsp
\end{nota}

\end{frame}




\begin{frame}[fragile]
\frametitle{Convergenza dell'interpolazione polinomiale}

Una delle questioni rilevanti \mye se aumentando il numero di nodi, la successione di polinomi interpolatori $p_n$  {\blues{\href{https://it.wikipedia.org/wiki/Successione\_di\_funzioni#Convergenza_uniforme}{converge uniformemente}}} alla funzione $f$ da approssimare, ovvero
\bc
\btc[width=7cm]
$$
\lim_n \max_{x \in [a,b]} |f(x)-p_n(x)|=0
$$
\etc
\ec
\noindent dove $-\infty < a < b < +\infty$.

\smsp

Se ci\'o accade, al crescere di $n$, il polinomio interpolatore approssima {\purples{ovunque e arbitrariamente bene}} la funzione $f$.
\end{frame}



\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale}


{\vspace{-0.05cm}}

{\footnotesize{
Operativamente, utilizzando la notazione $\|f\|_{\infty}:=\max_{x \in [a,b]}|f(x)|$,

{\vspace{-0.05cm}}

\begin{itemize}
\item per {\purples{$n=1$}}, 
\begin{enumerate}
\item si definisce il set di nodi $X_1=\{x^{(1)}_0,x^{(1)}_1\}$, 
\item si calcola il polinomio $p_1$ interpolante le coppie $$(x^{(1)}_0,f(x^{(1)}_0)), \smhsp (x^{(1)}_1,f(x^{(1)}_1)),$$
\item si valuta $\|E_1[f]\|_{\infty}:=\max_{x \in [a,b]} |f(x)-p_1(x)|$.
\end{enumerate}

{\vspace{0.1cm}}

\item per {\purples{$n=2$}}, 
\begin{enumerate}
\item si definisce il set di nodi $X_n=\{x^{(2)}_0,x^{(2)}_1,x^{(2)}_2\}$, 
\item si calcola il polinomio $p_2$ interpolante le coppie 
$$(x^{(1)}_0,f(x^{(1)}_0)), \smhsp (x^{(1)}_1,f(x^{(1)}_1)), \smhsp (x^{(2)}_2,f(x^{(2)}_2)),$$
\item si valuta $\|E_2[f]\|_{\infty}:=\max_{x \in [a,b]} |f(x)-p_2(x)|$.
\end{enumerate}

{\vspace{0.1cm}}

\item fissato {\purples{$n$ generico}}, 
\begin{enumerate}
\item si definisce il set di nodi $X_n=\{x^{(n)}_0,x^{(n)}_1,\ldots,x^{(n)}_n\}$, 
\item si calcola il polinomio $p_n$ interpolante le coppie 
$$(x^{(n)}_0,f(x^{(n)}_0)), \smhsp (x^{(n)}_1,f(x^{(n)}_1)), \smhsp \ldots \smhsp (x^{(n)}_n,f(x^{(n)}_n)),$$
\item si valuta $\|E_n[f]\|_{\infty}:=\max_{x \in [a,b]} |f(x)-p_n(x)|$.
\end{enumerate}
\end{itemize}

Quindi si guarda se per $n \rightarrow +\infty$ la sequenza dei massimi errori $\|E_n[f]\|_{\infty} \rightarrow 0$.
}}
\end{frame}





\begin{frame}[fragile]
\frametitle{Interpolazione polinomiale}

\bignsp

 \begin{figure}\label{fig1}
 \centering
   {\includegraphics[scale=0.4,clip]{esempio_striscie.eps}}
   
\smnsp   
   
 \caption{Grafico che illustra il polinomio $p_6$ interpolante di grado $6$ su $7$ nodi equispaziati di $[0,2 \pi]$ della funzione $f(x)=\sin(2x)$,  (la
funzione ha la linea continua in nero, il polinomio interpolatore \mye
in rosso, in tratteggiato la striscia $f(x)\pm M$ dove $M=\max_{x \in [a,b]} |f(x)-p_6(x)|$).}
 \end{figure}
 

\end{frame}






\begin{frame}[fragile]
\frametitle{Convergenza dell'interpolazione polinomiale}

{\small{
\begin{nota}
Supponiamo che 
\begin{itemize}
\item $f \in C^{\infty}([a,b])$;
\item $\{x_k\}_{k=0,\ldots,n} \subset [a,b]$ a 2 a 2 distinti, ad esempio equispaziati o di tipo Chebyshev.
\end{itemize}
Da
$$
\max_{x \in [a,b]} |f(x)-p_n(x)| \leq \max_{s \in [a,b]} | f^{(n+1)}(s) |  \max_{x \in [a,b]} {\frac {| \prod_{i=0}^{n} (x-x_i) | }{(n+1)!}}
$$
se $\max_{s \in [a,b]} | f^{(n+1)}(s) | $ \mye sufficientemente grande per ogni $n$, allora potrebbe accadere che
$$
\max_{s \in [a,b]} | f^{(n+1)}(s) |  \max_{x \in [a,b]} {\frac {| \prod_{i=0}^{n} (x-x_i) | }{(n+1)!}}
$$
non sia infinitesima per $n \rightarrow +\infty$ e quindi che {\it{possa}} succedere che
$$
\|E_n[f]\|_{\infty}:=\max_{x \in [a,b]} |f(x)-p_n(x)|
$$
non converga a $0$ per $n \rightarrow +\infty$.
\end{nota}
}}
\end{frame}








\begin{frame}[fragile]
\frametitle{Convergenza dell'interpolazione polinomiale}

In generale,
\begin{teorema}[Faber (1914)]
Per ogni distribuzione di nodi esiste almeno una funzione $f \in C([a,b])$, $-\infty < a < b <+\infty$, tale che l'errore di interpolazione $\|E_n[f]\|_{\infty}$ non converge a $0$ per $n \rightarrow +\infty$.
\end{teorema}

Per contro
\begin{teorema}
Per ogni funzione $f \in C([a,b])$, $-\infty < a < b <+\infty$, esiste almeno una distribuzione di nodi tale che $\|E_n[f]\|_{\infty} \rightarrow 0$ per $n \rightarrow +\infty$.
\end{teorema}
e
\begin{teorema}[Bernstein (1916)]
Per ogni funzione $f \in C^1([a,b])$, $-\infty < a < b <+\infty$, allora se $p_n$ \mye l'interpolante di $f$ in $n+1$ nodi di Chebyshev, $\|E_n[f]\|_{\infty} \rightarrow 0$ per $n \rightarrow +\infty$.
\end{teorema}

\end{frame}


\begin{frame}[fragile]
\frametitle{Controesempio di Runge}

\begin{esempio}
Sia $f$ la funzione di {\blues{\href{https://it.wikipedia.org/wiki/Fenomeno\_di\_Runge}{Runge}}} (scoperta nel 1901)
\bc
\btc[width=7cm]
\smnsp
{{
\begin{equation}\label{runge}
{
f(x)= {\frac{1}{1+x^2}}, \,\,x \in [-5,5].
}
\end{equation}
}}
\etc
\ec
Si dimostra che il polinomio $p_n$ che interpola $f$ in {\purples{$n+1$ nodi equispaziati}},  {\purples{non converge uniformemente  a $f$}} (vedasi relativa figura, e le forti differenze tra $p_n$ e $f$ vicino agli estremi $-5$, $5$).
\end{esempio}

\smsp

Nelle tabelle e figure che seguono, illustriamo il fenomeno di Runge, e di come l'interpolante in nodi equispaziati non converga uniformemente alla funzione di Runge nell'intervallo $[-5,5]$, nonostante la stessa appartenga a $C^{\infty}([-5,5])$.
\end{frame}


\begin{frame}[fragile]
\frametitle{Controesempio di Runge}

\bignsp

 \begin{figure}\label{fig1}
 \centering
   {\includegraphics[scale=0.4,clip]{runge_22.eps}}
   
\smnsp   
   
 \caption{Grafico che illustra il polinomio interpolante di grado $12$ su $13$ nodi equispaziati della funzione di Runge,  (la
funzione ha la linea continua, il polinomio interpolatore \mye
tratteggiato, si osservino le oscillazioni agli estremi).}
 \end{figure}
 

\end{frame}



\begin{frame}[fragile]
\frametitle{Controesempio di Runge}

\bignsp

 \begin{figure}\label{fig1}
 \centering
   {\includegraphics[scale=0.4,clip]{runge_errs.eps}}
   
\smnsp   
   
 \caption{Grafico che illustra l'errore tra il polinomio $p_{12}$ di grado $12$ interpolante su $13$ nodi equispaziati la funzione di Runge e la funzione di Runge.}
 \end{figure}
 

\end{frame}


\begin{frame}[fragile]
\frametitle{Controesempio di Runge}
\begin{itemize}
\item Fortunatamente ci\myo non succede in questo caso per i {\purples{nodi di Chebyshev}}, per cui comunque esistono funzioni continue $f$ ma non di classe $C^1$ tali che
l'interpolante $p_n$ non converge puntualmente a $f$.

\smsp
\smsp

\item Nel controesempio di Runge in cui $f(x)=\frac{1}{1+x^2}$, in virt\myu del teorema di Bernstein, essendo $f \in C^{\infty}([-5,5])$ e quindi in particolare $f \in C^{1}([-5,5])$, possiamo affermare che se i nodi di interpolazione sono quelli di Chebyshev allora $\|E_n[f]\|_{\infty} \rightarrow 0$. 

\smsp
\smsp

\item In effetti in tabella successiva, si vede che l'errore in tali set di nodi ha numericamente tale propriet\myash, differentemente dall'interpolante in nodi equispaziati.
\end{itemize}
\end{frame}









\begin{frame}[fragile]
\frametitle{Controesempio di Runge}

\smnsp

\footnotesize{
 
\begin{table}[h!]
\begin{center}
\begin{tabular}{c c c}
\hline
$n$&   $E^{\mbox{e}}_n$ & $E^{\mbox{c}}_n$  \\
\hline
$  1$ & $9.615e-01$ & $9.615e-01$ \\
$  2$ & $6.462e-01$ & $6.462e-01$\\
 	 $  3$ & $7.070e-01$ & $8.289e-01$\\
 	 $  4$ & $4.384e-01$ & $4.600e-01$\\
 	 $  5$ & $4.327e-01$ & $6.386e-01$\\
 	 $  6$ & $6.169e-01$ & $3.112e-01$\\
 	 $  7$ & $2.474e-01$ & $4.596e-01$\\
 	 $  8$ & $1.045e+00$ & $2.047e-01$\\
 	 $  9$ & $3.003e-01$ & $3.191e-01$\\
 	 $ 10$ & $1.916e+00$ & $1.322e-01$\\
%  	 $ 11$ & $5.568e-01$ & $2.177e-01$
%  	 $ 12$ & $3.663e+00$ & $8.440e-02$
%  	 $ 13$ & $1.070e+00$ & $1.473e-01$
%  	 $ 14$ & $7.195e+00$ & $5.351e-02$
%  	 $ 15$ & $2.108e+00$ & $9.932e-02$
%  	 $ 16$ & $1.439e+01$ & $3.671e-02$
%  	 $ 17$ & $4.224e+00$ & $6.685e-02$
%  	 $ 18$ & $2.919e+01$ & $2.572e-02$
%  	 $ 19$ & $8.579e+00$ & $4.495e-02$
  	 $ 20$ & $5.982e+01$ & $1.774e-02$ \\
%  	 $ 21$ & $1.760e+01$ & $3.022e-02$
%  	 $ 22$ & $1.236e+02$ & $1.209e-02$
%  	 $ 23$ & $3.641e+01$ & $2.031e-02$
%  	 $ 24$ & $2.572e+02$ & $8.166e-03$
%  	 $ 25$ & $7.582e+01$ & $1.365e-02$
%  	 $ 26$ & $5.382e+02$ & $5.476e-03$
%  	 $ 27$ & $1.587e+02$ & $9.176e-03$
%  	 $ 28$ & $1.131e+03$ & $3.653e-03$
%  	 $ 29$ & $3.339e+02$ & $6.167e-03$
  	 $ 30$ & $2.388e+03$ & $2.426e-03$ \\
%  	 $ 31$ & $7.053e+02$ & $4.145e-03$
%  	 $ 32$ & $5.059e+03$ & $1.618e-03$
%  	 $ 33$ & $1.495e+03$ & $2.786e-03$
%  	 $ 34$ & $1.075e+04$ & $1.102e-03$
%  	 $ 35$ & $3.177e+03$ & $1.872e-03$
%  	 $ 36$ & $2.290e+04$ & $7.470e-04$
%  	 $ 37$ & $6.772e+03$ & $1.258e-03$
%  	 $ 38$ & $4.891e+04$ & $5.047e-04$
%  	 $ 39$ & $1.447e+04$ & $8.457e-04$
  	 $ 40$ & $1.047e+05$ & $3.399e-04$ \\
%  	 $ 41$ & $3.097e+04$ & $5.684e-04$
%  	 $ 42$ & $2.244e+05$ & $2.283e-04$
%  	 $ 43$ & $6.643e+04$ & $3.820e-04$
%  	 $ 44$ & $4.821e+05$ & $1.530e-04$
%  	 $ 45$ & $1.427e+05$ & $2.567e-04$
%  	 $ 46$ & $1.037e+06$ & $1.024e-04$
%  	 $ 47$ & $3.073e+05$ & $1.725e-04$
%  	 $ 48$ & $2.234e+06$ & $6.835e-05$
%  	 $ 49$ & $6.630e+05$ & $1.160e-04$
  	 $ 50$ & $4.822e+06$ & $4.622e-05$ \\
%  	 $ 51$ & $1.431e+06$ & $7.793e-05$
%  	 $ 52$ & $1.033e+07$ & $3.120e-05$
%  	 $ 53$ & $3.270e+06$ & $5.238e-05$
%  	 $ 54$ & $2.292e+07$ & $2.102e-05$
%  	 $ 55$ & $7.172e+06$ & $3.520e-05$
%  	 $ 56$ & $6.184e+07$ & $1.415e-05$
%  	 $ 57$ & $1.554e+07$ & $2.366e-05$
%  	 $ 58$ & $7.487e+07$ & $9.507e-06$
%  	 $ 59$ & $8.985e+07$ & $1.590e-05$
  	 $ 60$ & $1.796e+11$ & $6.381e-06$ \\
%  	 $ 61$ & $1.862e+07$ & $1.069e-05$
%  	 $ 62$ & $4.193e+07$ & $4.278e-06$
%  	 $ 63$ & $9.875e+06$ & $7.182e-06$
%  	 $ 64$ & $1.602e+08$ & $2.865e-06$
%  	 $ 65$ & $7.565e+08$ & $4.827e-06$
%  	 $ 66$ & $3.186e+07$ & $1.930e-06$
%  	 $ 67$ & $7.448e+06$ & $3.244e-06$
%  	 $ 68$ & $9.908e+06$ & $1.300e-06$
%  	 $ 69$ & $2.996e+06$ & $2.180e-06$
  	 $ 70$ & $4.171e+07$ & $8.755e-07$ \\
%  	 $ 71$ & $1.019e+07$ & $1.465e-06$
%  	 $ 72$ & $2.468e+07$ & $5.889e-07$
%  	 $ 73$ & $8.674e+05$ & $9.848e-07$
%  	 $ 74$ & $1.244e+07$ & $3.958e-07$
%  	 $ 75$ & $1.006e+08$ & $6.619e-07$
%  	 $ 76$ & $1.645e+06$ & $2.658e-07$
%  	 $ 77$ & $3.604e+05$ & $4.448e-07$
%  	 $ 78$ & $5.598e+05$ & $1.784e-07$
%  	 $ 79$ & $7.697e+04$ & $2.990e-07$
  	 $ 80$ & $6.774e+05$ & $1.196e-07$ \\
%  	 $ 81$ & $3.249e+05$ & $2.009e-07$
%  	 $ 82$ & $2.937e+05$ & $8.046e-08$
%  	 $ 83$ & $5.458e+04$ & $1.350e-07$
%  	 $ 84$ & $5.107e+04$ & $5.417e-08$
%  	 $ 85$ & $9.221e+03$ & $9.075e-08$
%  	 $ 86$ & $9.964e+04$ & $3.645e-08$
%  	 $ 87$ & $1.810e+04$ & $6.099e-08$
%  	 $ 88$ & $9.763e+04$ & $2.451e-08$
%  	 $ 89$ & $4.425e+04$ & $4.099e-08$
  	 $ 90$ & $1.498e+05$ & $1.648e-08$ \\
%  	 $ 91$ & $3.062e+03$ & $2.755e-08$
%  	 $ 92$ & $8.719e+03$ & $1.107e-08$
%  	 $ 93$ & $2.284e+04$ & $1.852e-08$
%  	 $ 94$ & $2.369e+04$ & $7.432e-09$
%  	 $ 95$ & $1.765e+03$ & $1.244e-08$
%  	 $ 96$ & $3.193e+04$ & $4.988e-09$
%  	 $ 97$ & $5.023e+02$ & $8.363e-09$
%  	 $ 98$ & $2.618e+07$ & $3.352e-09$
%  	 $ 99$ & $1.177e+03$ & $5.621e-09$
  	 $100$ & $5.177e+03$ & $2.256e-09$ \\
 \hline
\end{tabular}

\smnsp

\caption{\footnotesize{Grado $n$ ed errore $\|E_n[f]\|_{\infty}$ con $p_n$ interpolante $f$ risp. in $n+1$ nodi equispaziati e di Chebyshev (denotato rispettivamente con $E^{\mbox{e}}_n$, $E^{\mbox{c}}_n$).} }
\end{center}
\end{table}
}
\end{frame}




\begin{frame}[fragile]
\frametitle{Controesempio di Runge}

 
 \begin{figure}[h!]\label{bisae}
 \centering
   {\includegraphics[scale=0.25,clip]{rungeE.eps}}
    {\includegraphics[scale=0.25,clip]{rungeC.eps}}
 \caption{Grado $n$ ed errore $E_n[f]=\max_{x \in [-5,5]} |f(x)-p_n(x)|$ con $p_n$ interpolante $f$ rispettivamente in $n+1$ nodi equispaziati (figura a sinistra) e di Chebyshev (figura a destra), in scala semilogaritmica.}
 \end{figure} 
 

\end{frame}








\begin{frame}[fragile]
\frametitle{Stabilit\mya dell'interpolazione polinomiale}

Siano  $f \in C([a,b])$, con [$a,b$] intervallo chiuso e limitato.

\smsp

Si ponga per semplicit\mya di notazione $f_k:=f(x_k)$ e si supponga di avere al suo posto dei valori approssimati ${\tilde{f}}_k$ (ad esempio perch\'e ottenuti approssimando tali quantit\'a con numeri macchina o per noti errori di misura).

\smsp

Definiamo 
\begin{itemize}
\item il polinomio ${ p_n} \in {\mathbb{P}}_n$ che interpola $(x_j,{ f}_j)_{j=0,\ldots,n}$;
\item il polinomio ${\tilde p_n} \in {\mathbb{P}}_n$ che interpola $(x_j,{\tilde f}_j)_{j=0,\ldots,n}$.
\end{itemize}

\smsp

Si desidera che se \'e piccola la massima perturbazione sui dati
$$
\delta_{\mbox{max}}=\max_k |f_k-{\tilde f}_k|
$$
allora lo sia pure il massimo errore tra i polinomi $p_n$, ${\tilde{p}}_n$, 
$$
\|p_n-{\tilde{p}}_n\|_{\infty}=\max_{x \in [a,b]} |p_n(x)-{\tilde{p}}_n(x)|.
$$
ovvero che i polinomi interpolatori i dati esatti e quelli approssimati non siano troppo distanti tra loro (relativamente alla massima perturbazione sui dati $\delta_{\mbox{max}}$).
\end{frame}






\begin{frame}[fragile]
\frametitle{Stabilit\mya dell'interpolazione polinomiale}
{\small{
Si mostra che
{\purples{
$$\|p_n-{\tilde p}_n\|_{\infty}:=\max_{x \in [a,b]}|p_n(x)-{\tilde p}_n(x)|\leq \left( \max_k |f_k-{\tilde f}_k| \right) \max_{x \in [a,b]} \sum_{k=0}^{n} |L_k(x)|.$$
}}
Il valore 
\bc
\btc[width=6cm]
\smnsp
$${{\Lambda_n=\max_{x \in [a,b]} \sum_{k=0}^{n} |L_k(x)|}}$$ 
\smnsp
\smnsp
\etc
\ec

\'e noto come {\purples{costante di Lebesgue}} dell'insieme di punti $x_0,\ldots,x_n$ e  quindi

\bc
\btc[width=6cm]
\smnsp
\smnsp
$$\|p_n-{\tilde p}_n\|_{\infty} \leq \left( \max_k |f_k-{\tilde f}_k| \right) \cdot \Lambda_n.
$$
\smnsp
\smnsp
\etc
\ec

Osserviamo che 
\begin{itemize}
\item $\Lambda_n$ dipende esclusivamente dai polinomi di Lagrange e quindi {\purples{dipende esclusivamente dai punti di interpolazione}},
\item $\Lambda_n$ \'e un {\purples{indice di stabilit\'a}}, ovvero pi\'u grande  e \'e pi\'u a piccole perturbazioni ${\tilde{f}}_k$ sugli $f_k$, $k=0,\ldots,n$ possono corrispondere polinomi interpolatori $p_n$, ${\tilde p}_n$ molto diversi tra loro  (alta sensibilit\'a a perturbazioni sui dati).
\end{itemize}
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Stabilit\mya dell'interpolazione polinomiale (facoltativo)}
{\fns{
\begin{nota}[Facoltativa]
Mostriamo il risultato precedente.

\smsp

Supponiamo che $f_k \approx {\tilde f}_k$ (per esempio per via dell'arrotondamento si $f_k$). 
Generalizzando la disuguaglianza triangolare
$$|\gamma_1+\gamma_2|\leq |\gamma_1|+|\gamma_2|$$ abbiamo che 
$$|\sum_k \gamma_k| \leq \sum_k |\gamma_k|$$ da cui per $\gamma_k=a_k b_k$, visto che $|a_k b_k|=|a_k||b_k|$,
$$|\sum_k a_k b_k| \leq \sum_k |a_k b_k|=\sum_k |a_k| |b_k| \leq \sum_k (\max_k |a_k|) |b_k|=(\max_k |a_k|) \sum_k |b_k|,$$ e posti $a_k=f_k - {\tilde f}_k$, $b_k=L_k(x)$ necessariamente
\begin{equation}\label{3338}
|\sum_k (f_k - {\tilde f}_k) L_k(x)|  \leq (\max_k |f_k - {\tilde f}_k|)\sum_k |L_k(x)|.
\end{equation}
\end{nota}
}}
\end{frame}





\begin{frame}[fragile]
\frametitle{Stabilit\mya dell'interpolazione polinomiale (facoltativo)}
\begin{vuoto}
{\fns{
Visto che il polinomio
\begin{itemize}
\item ${\tilde p_n} \in {\mathbb{P}}_n$  interpola $(x_j,{\tilde f}_j)_{j=0,\ldots,n}$ \mye
{\purples{${\tilde p_n}(x)=\sum_{k=0}^{n} {\tilde f}_k L_k(x)$}},
\item ${\tilde p_n} \in {\mathbb{P}}_n$  interpola $(x_j,{ f}_j)_{j=0,\ldots,n}$ \mye {\purples{$p_n(x)=\sum_{k=0}^{n} f_k L_k(x)$}}.
\end{itemize}
da
\begin{equation}\label{3338A}
|\sum_k (f_k - {\tilde f}_k) L_k(x)|  \leq (\max_k |f_k - {\tilde f}_k|)\sum_k |L_k(x)|.
\end{equation}
abbiamo
\begin{eqnarray}
|p_n(x)-{\tilde p}_n(x)|&=& | \sum_{k=0}^{n} f_k L_k(x)-\sum_{k=0}^{n} {\tilde f}_k L_k(x)|=|\sum_{k=0}^{n} (f_k - {\tilde f}_k) L_k(x)| \nonumber \\ 
&\leq& \left( \max_k |f_k-{\tilde f}_k| \right) \sum_{k=0}^{n} |L_k(x)|, \nonumber
\end{eqnarray}
per cui
\begin{eqnarray}
\max_{x \in [a,b]}|p_n(x)-{\tilde p}_n(x)|
&\leq&
\max_{x \in [a,b]} 
\left( \max_k |f_k-{\tilde f}_k| \right) \sum_{k=0}^{n} |L_k(x)| \nonumber \\
& \leq& \left( \max_k |f_k-{\tilde f}_k| \right) \max_{x \in [a,b]} \sum_{k=0}^{n} |L_k(x)|. \nonumber
\end{eqnarray}
}}
\end{vuoto}
\end{frame}







\begin{frame}[fragile]
\frametitle{Costanti di Lebesgue}


Vediamo ora quali sono le stime delle costanti di Lebesgue per alcuni set di $n+1$ punti nell'intervallo $[-1,1]$:

\begin{itemize}
\item {\blues{punti equispaziati}}: si dimostra che asintoticamente (Turetskii, 1940)
\bc
\btc[width=6cm]
$$\Lambda_n \approx  \frac{2^{n+1}}{e n \log(n)};$$
\etc
\ec
\item {\blues{punti di Chebyshev}}: corrispondono a $ \cos\left( \frac{(2k - 1) \pi}{2(n+1)} \right) $ dove $k = 1, \ldots, n+1$; si dimostra che asintoticamente
\bc
\btc[width=10cm]
$$\Lambda_n \approx \frac{2}{\pi} \left( \log(n+1) + 0.578 +\log\left(\frac{8}{\pi} \right) \right).$$
\etc
\ec
\end{itemize}

\smsp

Questo ci fa capire, vista la crescita esponenziale dell'uno e quella logaritmica dell'altro, che dal punto della stabilit\'a dell'interpolazione \'e di gran lunga preferibile interpolare nei punti di Chebyshev.

\end{frame}


\begin{frame}[fragile]
\frametitle{Costanti di Lebesgue}

\smnsp

\footnotesize{
 
\begin{table}[h!]
\begin{center}
\begin{tabular}{c c c}
\hline
$n$&   $\Lambda^{\mbox{eq}}_n$ & $\Lambda^{\mbox{ch}}_n$  \\
\hline
 $   5 $ & $ 2.208e+00 $ & $  1.989e+00 $ \\
 	 $  10 $ & $ 1.785e+01 $ & $  2.429e+00 $ \\
 	 $  15 $ & $ 2.832e+02 $ & $  2.687e+00 $\\
 	 $  20 $ & $ 5.890e+03 $ & $  2.870e+00 $\\
 	 $  25 $ & $ 1.379e+05 $ & $  3.012e+00 $\\
 	 $  30 $ & $ 3.448e+06 $ & $  3.128e+00 $\\
 	 $  35 $ & $ 9.001e+07 $ & $  3.226e+00 $\\
 	 $  40 $ & $ 2.422e+09 $ & $  3.311e+00 $\\
 	 $  45 $ & $ 6.665e+10 $ & $  3.386e+00 $\\
 	 $  50 $ & $ 1.868e+12 $ & $  3.453e+00 $\\
 	 $  55 $ & $ 5.518e+13 $ & $  3.514e+00 $\\
 	 $  60 $ & $ 8.354e+16 $ & $  3.569e+00 $\\
 	 $  65 $ & $ 7.507e+15 $ & $  3.620e+00 $\\
 	 $  70 $ & $ 3.292e+16 $ & $  3.667e+00 $\\
 	 $  75 $ & $ 1.339e+17 $ & $  3.711e+00 $\\
 	 $  80 $ & $ 1.286e+17 $ & $  3.752e+00 $\\
 	 $  85 $ & $ 3.831e+18 $ & $  3.791e+00 $\\
 	 $  90 $ & $ 5.980e+18 $ & $  3.827e+00 $\\
 	 $  95 $ & $ 8.922e+16 $ & $  3.862e+00 $\\
 	 $ 100 $ & $ 3.790e+17 $ & $  3.894e+00 $\\
 \hline
\end{tabular}

\smnsp

\caption{\footnotesize{Valore $n$ e costanti di Lebesgue in $n$ punti equispaziati di $[-1,1]$ e nei punti di Chebyshev $\cos((2k-1\cdot \pi / (2\cdot n)))$, $k=1,\ldots,n$. Se ne evince la maggiore stabilit\mya dell'interpolazione nei nodi di Chebyshev. } }
\end{center}
\end{table}
}

\end{frame}

 
% \begin{frame}[allowframebreaks] {Bibliografia}
% \bibliographystyle{plain}
% \bibliography{bibliography/bibliography} 

\begin{frame}
\frametitle{Bibliografia}

{\scriptsize{
\begin{thebibliography}{99} 
\bibitem{ATK} K. Atkinson, {\em An Introduction to Numerical Analysis\/},
Wiley, (1989).
 \bibitem{COM} V. Comincioli, {\em{Analisi Numerica, metodi modelli
applicazioni}}, Mc Graw-Hill, 1990.
\bibitem{GAUPAP}  W. Gautschi, {\sl{Interpolation before and after Lagrange}}, Rend. Sem. Mat. Univ. Politec. Torino, Vol. 70, 4 (2012), pp.347--368.
\bibitem{WIKRI} {\href{http://it.wikipedia.org/wiki/Fenomeno\_di\_Runge}{Wikipedia, Fenomeno di Runge}}.
\bibitem{WIKIN} {\href{http://it.wikipedia.org/wiki/Interpolazione\_polinomiale}{Wikipedia, Interpolazione polinomiale}}.
\bibitem{WIKLI} {\href{https://it.wikipedia.org/wiki/Interpolazione\_di\_Lagrange}{ Wikipedia, Interpolazione di Lagrange}}
\bibitem{WIKNP} {\href{http://en.wikipedia.org/wiki/Newton\_polynomial}{Wikipedia, Newton polynomial}}.
\bibitem{WIKNC} {\href{http://it.wikipedia.org/wiki/Nodi\_di\_Chebyshev}{Wikipedia, Nodi di Chebyshev}}.
\bibitem{WIKRT} {\href{https://it.wikipedia.org/wiki/Teorema\_di\_Rolle}{Wikipedia, Teorema di Rolle}}
\bibitem{WIKV} {\href{http://en.wikipedia.org/wiki/Vandermonde\_matrix}{Wikipedia, Vandermonde matrix}}.

\end{thebibliography}
}}
\end{frame}

\end{document}



\frametitle{Esistenza e unicit\mya del polinomio interpolatore}

{\scriptsize{
\begin{nota}[Matrice di Vandermonde]
Esistono {\purples{altre dimostrazioni}} dell'esistenza e unicit\mya del polinomio interpolatore. 

Ad esempio, ci\myo \mye equivalente a mostrare che il sistema lineare {\purples{$Va=y$}} ha una e una sola soluzione $a^*$, dove 
\begin{itemize}
\item $V=(v_{i,j})=(x_i^j)$, $0\leq i,j \leq n$ \'e la {\blues{\href{https://it.wikipedia.org/wiki/Matrice\_di\_Vandermonde}{matrice di Vandermonde}}} dei nodi di interpolazione;
\item $y=(y_0,\ldots,y_n)^T$;
\item $a=(a_k)_{k=1,\ldots,n+1}$ sono i coefficienti del polinomio interpolatore $p_n(x)=\sum_{k=0}^{n} a_{k+1}x^k$.
\end{itemize}
In effetti, basta osservare che la che la $k$-sima componente di $Va$ \'e 
$$
(Va)_k=\sum_{j=0}^{n} V_{k,j} a_j=\sum_{j=0}^{n} x_{k}^j a_j=\sum_{j=0}^{n}  a_j x_{k}^j
$$
e quindi la $k$ equazione del sistema lineare $Va=y$ risulta 
{\purples{$
\sum_{j=0}^{n} a_j x_{k}^j =y_k
$}}
che per $p_n(x)=\sum_{j=0}^{n} a_j x^j $ corrisponde  a $p_n(x_k)=y_k$, ovvero alla $k$-sima condizione relativa al polinomio interpolatore.

\smsp

Visto che {\purples{$V$ \'e non singolare}} in quanto il suo determinante \mye diverso da $0$ (in effetti con qualche conto si ha $\det(A)=\prod_{0 \leq i < j \leq n} (x_j-x_i) \neq 0$), possiamo mostrare anche mediante strumenti dell'algebra lineare che il problema $Va=y$ ha una e una sola soluzione, e che quindi si pu\'o determinare il polinomio interpolatore $p_n(x)=\sum_{k=0}^{n} a_{k+1}x^k$ risolvendo un sistema lineare di dimensione $(n+1) \times (n+1)$.

\end{nota}
}}
\end{frame}
