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

%\usepackage{movie15}
\usepackage{multimedia}

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



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

\begin{vuoto}
Si \`e visto che nel caso dell'interpolazione polinomiale,
\begin{itemize}
\item dati $n+1$ punti $a=x_0<\ldots<x_n=b$, 
\item dati i valori $y_0,\ldots,y_n$, ad esempio ivi
assunti da una funzione $y=f(x)$, 
\end{itemize}
esiste uno ed un solo polinomio $p_n$ di
grado $n$ tale che
\begin{equation}
p_n(x_i)=y_i, \, \, i=0,\ldots,n.
\end{equation}

Nel caso di nodi equispaziati
\begin{equation}
x_k=a+ k \, {\frac {(b-a) } {n}   }, \, \, k=0,\ldots,n ;
\end{equation}
al crescere di $n$, {\purples{non si pu\'o garantire che $f(x)-p_n(x)$ tenda uniformemente a $0$}}
(si ricordi il fenomeno di Runge!).
\end{vuoto}
\end{frame}






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

\smnsp

\begin{vuoto}
Per un teorema di Faber (cf. {\cite[p.132]{COM}}, qualsiasi sia l'insieme di nodi
relativi all'intervallo limitato $[a,b]$,
esiste $f \in C([a,b])$ tale che l'interpolante $p_n$ in tale insieme
di punti non converge uniformemente a $f$ (per $n\rightarrow \infty$).

\smsp

Quindi, senza ulteriori informazioni, non si pu\'o affermare con certezza che sia
$$ \lim_{n \rightarrow \infty}  \max_{x \in [a,b]} |f(x)-p_n(x)| \rightarrow 0.$$
\end{vuoto}

Di conseguenza sorge spontaneo porsi il seguente

\begin{problema}
Qualora
\begin{itemize}
\item $[a,b]$ sia un intervallo limitato,
\item si possegga un numero arbitrario di punti, anche equispaziati in $[a,b]$,
\item $f \in C^{k}([a,b])$ per $k$ sufficientemente grande,
\end{itemize}
calcolare una famiglia di approssimanti di {\purples{tipo
polinomiale}} $\pi_n$ per cui si abbia 
$$ \lim_{n \rightarrow \infty}  \max_{x \in [a,b]} |f(x)-\pi_n(x)| \rightarrow 0.$$
\end{problema}
\end{frame}






\begin{frame}[fragile]
\frametitle{Funzioni polinomiali a tratti}

\smnsp
\small{
\begin{definizione}[Funzioni polinomiali a tratti]
Sia dato un intervallo $[a,b]$ e sia $a=t_0 < t_1 <\ldots < t_n=b$. 
Una funzione $f$ si dice {\purples{polinomiale a tratti}} se la sua restrizione ad ogni intervallo $[t_k,t_{k+1}]$, $k=0,\ldots,n-1$ \mye un polinomio.
\end{definizione}

\smnsp

 \begin{figure}[ht!]\label{fig1aaaahjtfty}
 \centering
   {\includegraphics[scale=0.25,clip]{fct_1.eps}}
   {\includegraphics[scale=0.25,clip]{fct_2.eps}}
   
   \smnsp
   
 \caption{{\blues{Sinistra}}: polinomio a tratti di grado 1. {\blues{Destra}}: polinomio a tratti di grado 2.}
 \end{figure}
 
 \smnsp
 
\begin{nota}[Continuit\'a]
Si osservi che mentre un polinomio \'e sicuramente una funzione appartenente a $C^{\infty}([a,b])$, in generale non \'e detto che un polinomio a tratti sia una funzione continua (vedi figure).
\end{nota}
 }
\end{frame}
 
\begin{frame}[fragile]
\frametitle{Funzioni polinomiali a tratti}

\smnsp
\small{
\begin{definizione}[Interpolante polinomiale a tratti di grado $s$]

\begin{itemize}
\item Siano $t_0=a < t_1 <\ldots < t_n=b$ punti che definiscono la suddivisione di $[a,b]$ mediante intervalli $[t_k,t_{k+1}]$, $k=0,\ldots,n-1$. 
\item Nell'intervallo $[t_k,t_{k+1}]$ siano definiti i punti $\{x_j^{(k)} \}_{j=0,\ldots,s}$ tali che
$$t_k=x^{(k)}_{0} < x^{(k)}_{1} < \ldots <x^{(k)}_{s-1} < x^{(k)}_{s} =t_{k+1}.$$ 
\end{itemize}

Si consideri la funzione $\pi_s$ tale che la sua restrizione $\pi_s|_{[t_k,t_{k+1}]}$ ad ogni subintervallo $[t_k,t_{k+1}]$, $k=0,\ldots,n-1$, sia un polinomio di grado $s$ e interpolante i dati $(x^{(k)}_{j},y^{(k)}_{j})$, $j=0,\ldots,s$.


\smsp

Tale $\pi_s$ si chiama {\purples{funzione polinomiale a tratti di grado $s$, interpolante}} le coppie $(x^{(k)}_{j},y^{(k)}_{j})$, $k=0,\ldots,n-1$. $j=0,\ldots,s$ (relativamente alla suddivisione definita da $t_0,\ldots,t_n$).
\end{definizione}

In altri termini $p_s^*$ si ottiene {\it{incollando}} per continuit\mya interpolanti polinomiali di grado $s^*$ in sottointervalli $[t_{k},t_{{k+1}}]$ ove in generale i punti di raccordo sono $t_1=x_s^{(0)}=x_0^{(1)}, t_2=x_s^{(1)}=x_0^{(2)}, \ldots$ 
}
\end{frame}






\begin{frame}[fragile]
\frametitle{Funzioni polinomiali a tratti}

\smnsp

 \begin{figure}[ht!]\label{fig1aaaahjtfty}
 \centering
   {\includegraphics[scale=0.23,clip]{fct_1_intp.eps}}
   {\includegraphics[scale=0.23,clip]{fct_3_intp.eps}}
 \caption{La funzione di Runge (in nero). A sinistra la interpolante polinomiale a tratti $p^*_1$ a tratti di grado $1$, a destra, la interpolante polinomiale a tratti $p^*_3$ a tratti di grado $3$, entrambe in rosso, in 4 subintervalli equispaziati. In verde le coppie da interpolare.}
 \end{figure}

\end{frame}






\begin{frame}[fragile]
\frametitle{Funzioni polinomiali a tratti: esistenza ed unicit\mya}

\smnsp

{\small{

\begin{teorema}[Esistenza e unicit\'a interpolanti a tratti]
\begin{itemize}
\item Siano $t_0=a < t_1 <\ldots < t_n=b$ punti che definiscono la suddivisione di $[a,b]$ mediante intervalli $[t_k,t_{k+1}]$, $k=0,\ldots,n-1$. 
\item Nell'intervallo $[t_k,t_{k+1}]$ siano definiti i punti $\{x_j^{(k)} \}_{j=0,\ldots,s}$ tali che
$$t_k=x^{(k)}_{0} < x^{(k)}_{1} < \ldots <x^{(k)}_{s-1} < x^{(k)}_{s} =t_{k+1}.$$ 
\end{itemize}

Sia  $\pi_s$ la funzione polinomiale a tratti di grado $s$, interpolante le coppie $(x^{(k)}_{j},y^{(k)}_{j})$, $k=0,\ldots,n-1$. $j=0,\ldots,s$ (relativamente alla suddivisione definita da $t_0,\ldots,t_n$).

\smsp

Tale funzione polinomiale a tratti di grado $s$ {\reds{esiste ed \'e unica}}.
\end{teorema}

\begin{dimostrazione}
Osservando che in ogni subintervallo $[t_k,t_{k+1}]$ l'interpolante richiesta di grado $s$ esiste ed \mye unica  (ci sono $s+1$ ascisse a due due distinti da interpolare), necessariamente {\purples{tali interpolanti}} relativamente ai dati $(x^{(k)}_j,y^{(k)}_j)_{k=0,\ldots,n, j=0,\ldots,s}$ {\purples{esistono e sono uniche}}.
\end{dimostrazione}

\smsp

Il primo caso \`e quello delle {\purples{interpolanti polinomiali a tratti di grado $1$}}, cio\`e funzioni che in ogni intervallo $[t_k,t_{k+1}]$ (per $k=0,\ldots,n-1$) sono polinomi di grado $m^*=1$ (e globalmente funzioni continue).
Inoltre {\blues{$t_k=x^{(k)}_{0} < x^{(k)}_{1} =t_{k+1}$}}.
}}
\end{frame}






\begin{frame}[fragile]
\frametitle{Errore dell'interpolante polinomiale a tratti di grado $1$}

\smnsp


\begin{teorema}
Sia $\pi_1:[a,b] \rightarrow \R$ la funzione interpolante a tratti di {\purples{grado 1}} relativamente alle coppie
($t_i,f(t_i)$) dove $$t_0=a<t_1< \ldots <t_i < t_{i+1} < \ldots < t_n=b.$$
Allora se 
\begin{enumerate}
\item $x \in [t_i,t_{i+1}]$, 
\item $h_i=t_{i+1}-t_i$, 
\item la funzione $f$ \mye derivabile due volte con continuit\mya ed \mye
$$M_i=\max_{t \in[t_i,t_{i+1}]}|f^{(2)}(t)|,$$
\end{enumerate}
abbiamo
\begin{equation}\label{errorelineare}
|f(x)-\pi_1(x)| \leq   M_i  {\frac{h_i^2 }{ 8}}.
\end{equation}
\end{teorema}
\end{frame}






\begin{frame}[fragile]
\frametitle{Errore dell'interpolante polinomiale a tratti di grado $1$}

\smnsp

{\small{
\begin{vuoto}[Dimostrazione]
Supponiamo $x \in [t_i,t_{i+1}]$. 

\smsp

L'errore $|f(x)-\pi_1(x)|$ coincide con l'errore compiuto dall'interpolante polinomiale nell'approssimare in $x$ la funzione $f$ mediante il polinomio di grado 1 che interpola le coppie 
$(t_i,f(t_i))$, $(t_{i+1},f(t_{i+1}))$.

\smsp

Dal teorema dell'errore dell'interpolazione polinomiale di grado $1$, 
\smnsp

\begin{equation}\label{2a}
f(x)-\pi_1(x)= f^{(2)}(\xi) {\frac { (x-t_i) (x-t_{i+1})  }{2}}, \,\,
\xi \in (t_i,t_{i+1})
\end{equation}

\noindent
e quindi osservato che
\begin{itemize}
\item  $\left|f^{(2)}(\xi) \right| \leq \max_{t \in [t_i,t_{i+1}]} |f^{(2)}(t) |=M_i$
\item $ \left| {\frac { (x-t_i) (x-t_{i+1})  }{2}} \right| \leq \max_{t \in [t_i,t_{i+1}]} \left| {\frac { (t-t_i) (t-t_{i+1})  }{2}} \right| = \max_{t \in [t_i,t_{i+1}]}  {\frac { |(t-t_i) (t-t_{i+1})  |}{2}} $
\end{itemize}
ricaviamo
\begin{eqnarray}\label{2a1}
|f(x)-\pi_1(x)| &=& \left|f^{(2)}(\xi) {\frac { (x-t_i) (x-t_{i+1})  }{2}}
\right| = \left|f^{(2)}(\xi) \right|  \left| {\frac { (x-x_i)
(x-t_{i+1})
}{2}} \right| \nonumber \\
              &\leq& M_i \cdot  \max_{t \in [t_i,t_{i+1}]}  {\frac { |(t-t_i) (t-t_{i+1})  |}{2}} \nonumber
\end{eqnarray}
\end{vuoto}
}}
\end{frame}






\begin{frame}[fragile]
\frametitle{Errore dell'interpolante polinomiale a tratti di grado $1$}

\smnsp
{\small{
\begin{vuoto}
Quindi abbiamo per $x \in  [t_i,t_{i+1}]$
\begin{equation}\label{4.5}
|f(x)-\pi_1(x)| \leq M_i \cdot  \max_{t \in [t_i,t_{i+1}]}  {\frac { |(t-t_i) (t-t_{i+1})  |}{2}} 
\end{equation}
e si tratta di trovare una maggiorazione di $ \max_{t \in [t_i,t_{i+1}]}  {\frac { |(t-t_i) (t-t_{i+1})  |}{2}} $.

\smsp

Si vede facilmente che 
\begin{itemize}
\item posto $c=(t_i+t_{i+1})/2$ si ha 
{\footnotesize{
$$ {\frac { |(c-t_i) (c-t_{i+1}) | }{2}}=\max_{t \in [t_i,t_{i+1}]}{\frac { |(t-t_i) (t-t_{i+1}) | }{2}}=\max_{t \in [t_i,t_{i+1}]} \left(-\frac{(t-t_i) (t-t_{i+1})}{2}\right)$$
}}
\item $h_i=t_{i+1}-t_i$, $|c-t_i|=|c-t_{i+1}|=h_i/2$,
\end{itemize}

e quindi

\smnsp
\smnsp

\begin{eqnarray}
\max_{t \in [t_i,t_{i+1}]} {\frac {| (t-t_i) (t-t_{i+1}) | }{2}} & = & {\frac {|(c-t_i) (c-t_{i+1}) | }{2}}= {\frac {|c-t_i| | c-t_{i+1} | }{2}} \nonumber \\
&=& \frac{(h_i/2)(h_i/2)}{2} ={\frac {h_i^2}{8}}. \nonumber
\end{eqnarray}

da cui si ottiene per ({\ref{4.5}}) la tesi dell'asserto.

\end{vuoto}
}}


\end{frame}






\begin{frame}[fragile]
\frametitle{Errore dell'interpolante polinomiale a tratti di grado $1$}

\smnsp

{\small{
\begin{nota}

\begin{enumerate}
\item Il teorema precedente, vale per $h_i$ generica. 
\item Il massimo $M_i=\max_{s \in(t_i,t_{i+1})}|f^{(2)}(s)|$ dipende solo dal $i$-simo intervallo che \mye quello in cui si esamina l'errore compiuto nel punto $x$. 

\smsp

A priori uno potrebbe utilizzare 
\begin{itemize}
\item $M=\max_{s \in [a,b]}|f^{(2)}(s)| \geq M_i=\max_{s \in[t_i,t_{i+1}]}|f^{(2)}(s)|$ 
\item $h=\max_{i=1,\ldots,n} h_i$
\end{itemize}
ma la disuguaglianza 
$$
|f(x)-\pi_1(x)| \leq   M   {\frac{h^2}{ 8}}
$$
sarebbe meno precisa di
$$
|f(x)-\pi_1(x)| \leq   M_i   {\frac{h_i^2}{ 8}}.
$$
\end{enumerate}
\end{nota}
}}
\end{frame}

\begin{frame}
\frametitle{Errore dell'interpolante polinomiale a tratti di grado $1$}
\smnsp
{\small{
\begin{corollario}
Sia $[a,b]$ un intervallo limitato e supponiamo 
\begin{itemize}
\item $f \in C^2([a,b])$,
\item  {\purples{$M=\max_{t\in[a,b]}|f^{(2)}(t)|$}}.
\item $\pi^{(n)}_{1} :[a,b] \rightarrow \R$ la funzione lineare a tratti interpolante le coppie
($t_k,f(t_k)$), dove $t_k=a+k \frac{b-a}{n}$, $k=0,\ldots,n$.
\end{itemize}
Allora 

\smnsp

\begin{equation}\label{errorelineare2}
0 \leq \max_{x \in [a,b]} |f(x)-\pi^{(n)}_{1}(x)| \leq  M   {\frac{ (b-a)^2 }{ 8n^2}}. \nonumber
\end{equation}
\end{corollario}

\smnsp

\begin{dimostrazione}
Osserviamo che 
\begin{itemize}
\item $
M=\max_{t\in[a,b]}|f^{(2)}(t)| \geq M_i=\max_{t\in[t_i,t_{i+1}]}|f^{(2)}(t)|
$;
\item essendo, $h=h_i$, per $i=1,\ldots,n$, si ha $
{\purples{|f(x)-\pi^{(n)}_{1}(x)|}} \leq   M_i   {\frac{h_i^2}{ 8}} {\purples{\leq M {\frac{h^2}{ 8}}}}.
$
\end{itemize}
Visto che $M {\frac{h^2}{ 8}}$ non dipende da $x$, $h=(b-a)/n$

\smnsp

$$
0 \leq \max_{x \in [a,b]}|f(x)-\pi^{(n)}_{1}(x)| \leq  M {\frac{h^2}{ 8}}=M   {\frac{ (b-a)^2 }{ 8n^2}}.
$$
\end{dimostrazione}
}}
\end{frame}





\begin{frame}[fragile]
\frametitle{Errore dell'interpolante polinomiale a tratti di grado $1$}

\smnsp
\begin{importante}[Convergenza uniforme]
Indicato con {\reds{$\pi^{(n)}_{1}$}} il polinomio a tratti interpolante $n+1$ nodi equispaziati di $[a,b]$, essendo $h=(b-a)/n$, ricaviamo per $M=\|f^{(2)}\|_{\infty}$
\bc
\btc[width=9cm]
\begin{equation}
0 \leq \max_{t \in [a,b]} |f(t)-\pi^{(n)}_{1}(t)| \leq     {\frac{ (b-a)^2 M }{ 8n^2}}.
\end{equation}
\etc
\ec
da cui si evince che se $f \in C^2([a,b])$, $-\infty < a < b < +\infty$ e il numero di punti equispaziati nell'intervallo $[a,b]$ tende ad infinito allora, visto che $$ \lim_{n \rightarrow \infty}\frac{ (b-a)^2 M }{ 8n^2} = 0,$$ per il teorema del confronto, per $n \rightarrow +\infty$
$$
\|f-\pi^{(n)}_{1}\|_{\infty}:=\max_{t \in [a,b]} |f(t)-\pi_{1}(t)|  \rightarrow 0
$$

\smnsp

ovvero la successione $\pi^{(1)}_{1}, \pi^{(2)}_{1},\ldots,\pi^{(n)}_{1},\ldots$ {\purples{converge uniformemente a $f$}}.
\end{importante}
\end{frame}






\begin{frame}[fragile]
\frametitle{Il controesempio di Runge}

\smnsp
 {\small{
\begin{vuoto}
Si consideri
\begin{itemize}
\item la funzione di Runge $
 f(x)=\frac {1}  {1+x^2}, \,\,\, x \in [-5,5];
 $
 \item la funzione lineare a tratti $\pi_1^{(n)}$ interpolante $f$ in $n$ punti equispaziati
$$
t_k=-5+\frac{10k}{n}, \,\,\, k=0,\ldots,n,
$$
\end{itemize}
 
\smnsp
 
Dopo qualche calcolo si vede che
% \begin{itemize}
%\item 
$$f^{(1)}(x)=\frac {2x}  {(1+x^2)^2}, {\hspace{0.75cm}} f^{(2)}(x)=\frac{2\cdot(3x^2 - 1)}{(x^2 + 1)^3}$$
%\item $f^{(3)}(x)=\frac {-24x(x^2 - 1)}{(x^2 + 1)^4}$.
%\end{itemize}
 e quindi  visto che
 \begin{itemize} 
 \item $h_i=t_{i+1}-t_i=h=10/n$,
 \item $\max_{s \in [-5,5]} |f^{(2)}(x)| = 2$,
  \end{itemize} 
  
{\vspace{-0.1cm}}
  
 ricaviamo che per $x \in [t_i,t_{i+1}]$ l'errore di interpolazione verifica
\begin{eqnarray}
 |f(x)-\pi_1^{(n)}(x)| &\leq&  \frac {h_i^2}{8} \max_{s \in [t_i,t_{i+1}]} |f^{(2)} (s) | \\
&\leq& \frac {h^2}{8} \max_{s \in [a,b]} |f^{(2)} (s) | = {\frac{1}{8} }\left(\frac{10}{n} \right)^2 \cdot 2= \frac{100 \cdot 2}{8n^2}.
\end{eqnarray}
\end{vuoto}
}}
\end{frame}






\begin{frame}[fragile]
\frametitle{Il controesempio di Runge}

\smnsp
\begin{vuoto}
Di conseguenza, da
$$0 \leq |f(x)-\pi_1^{(n)}(x)| \leq  \frac{100 \cdot 2}{8n^2}$$
abbiamo
$$
0 \leq \max_{x \in [-5,5]} |f(x)-p^*_{1,n}(x)| \leq \frac{200}{8n^2}.
$$ 
e come detto sopra deduciamo per il teorema del confronto che
$$
\lim_n \max_{x \in [-5,5]} |f(x)-\pi_1^{(n)}(x)| = 0,
$$
ovvero la successione $\{\pi_1^{(n)}\}$ converge uniformemente a $f$.
\end{vuoto}
\end{frame}






\begin{frame}[fragile]
\frametitle{Il controesempio di Runge}

\smnsp
\begin{table}[h!]
\begin{center}
\begin{tabular}{| c c  | c c |}
\hline
$n$&   $E_n$ & $n$&   $E_n$  \\
\hline

 $       2$ & $9.62e-01$ & $   16384$ & $9.31e-08$ \\
 	 $       4$ & $7.35e-01$ & $   32768$ & $2.32e-08$ \\
 	 $       8$ & $3.38e-01$ & $   65536$ & $5.79e-09$ \\
 	 $      16$ & $1.00e-01$ & $  131072$ & $1.45e-09$ \\
 	 $      32$ & $2.54e-02$ & $  262144$ & $3.63e-10$ \\
 	 $      64$ & $6.26e-03$ & $  524288$ & $9.08e-11$ \\
 	 $     128$ & $1.55e-03$ & $ 1048576$ & $2.27e-11$ \\
 	 $     256$ & $3.84e-04$ & $ 2097152$ & $5.67e-12$ \\
 	 $     512$ & $9.55e-05$ & $ 4194304$ & $1.42e-12$ \\
 	 $    1024$ & $2.38e-05$ & $ 8388608$ & $3.54e-13$ \\
 	 $    2048$ & $5.95e-06$ & $16777216$ & $8.78e-14$ \\
 	 $    4096$ & $1.49e-06$ & $33554432$ & $2.23e-14$ \\
 	 $    8192$ & $3.71e-07$ & $67108864$ & $5.66e-15$ \\
 \hline
\end{tabular}
\caption{Grado $n$ ed errore $E_n=\max_{x \in [-5,5]} |f(x)-\pi_1^{(n)}(x)|$ con $\pi_1^{(n)}$ interpolante $f$ di tipo lineare a tratti, in $n+1$ nodi equispaziati. Si osservi come numericamente $E_n \rightarrow 0$.}
\end{center}
\end{table}

\end{frame}



\begin{frame}[fragile]
\frametitle{Il controesempio di Runge}


 \begin{figure}[ht!]\label{fig1aaaa4}
 \centering
\movie[externalviewer]{ \includegraphics[width=\textheight, keepaspectratio]{runge_unif_lin.eps}} {runge_spline_09.avi}

 \caption{Funzione di Runge e interpolanti a tratti di grado 1 (in 2,4,8 suddivisioni equispaziate).}
 \end{figure}




\end{frame}







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

\smnsp

Una risposta generale al citato problema di convergenza uniforme \`e stata data nel 1946 da Schoenberg, generalmente considerato lo scopritore delle splines (cf. {\cite{WIKIS}} {\cite{WIKFS}}, {\cite{WIKSD}}, {\cite{WIKSM}}). 

\begin{definizione}[Spline di ordine $m$, \cite{ATK}, p.166]
Si considerino i punti $a=t_0 < t_1 <\ldots < t_n=b$. 

\smsp

Una funzione $s$ tale che
\begin{itemize}
\item $s$ \mye un polinomio di grado al pi\myu {\purples{$m-1$}} in ogni subintervallo $[t_{i-1},t_i]$;
\item $s \in C^{{\purples{(m-2)}}}([a,b])$;
\end{itemize}
si dice {\purples{spline}} di {\underline{ordine}} $m$ (o equivalentemente di {\underline{grado}} $m-1$).

\smsp

Se in particolare interpola le coppie $$(t_k,y_k), {\hspace{0.3cm}} k=0,\ldots,n,$$ si dice {\purples{interpolante}} tali dati. 
\end{definizione}

\end{frame}


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

\smnsp
 \begin{figure}[ht!]\label{fig1aaaa1}
 \centering
   {\includegraphics[scale=0.4,clip]{esempio_spline3.eps}}
 \caption{\scriptsize{La funzione $f(t)=\sin(t) + \cos(2\cdot t) -\cos(t)/3$ in $[-\pi,\pi]$ e una spline $s_3$ di ordine $4$ interpolante $f$, nei punti $x_k=-\pi+k \cdot \frac{2\pi}{6}$, $k=0,\ldots,6$, ovvero interpolante le coppie ($x_k$, $f(x_k)$), $k=0,\ldots,6$.}}
 \end{figure}


\end{frame}





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

\smnsp

\begin{esempio}
Il primo caso \`e quello delle {\purples{splines di grado $m^*=1$}}, ovvero ordine $m=m^*+1=2$ cio\`e funzioni che
\bit
\item in
ogni intervallo $[x_i,x_{i+1}]$ (per $i=0,\ldots,n-1$) sono polinomi di
grado $m^*=1$, 
\item globalmente funzioni di classe $C^{m^*-1}([a,b]) =C^0([a,b])$, cio\`e
continue. 
\eit
Evidentemente coincidono con le funzioni lineari a tratti, relativamente a $[x_i,x_{i+1}]$, $i=0,\ldots,n-1$.
\end{esempio}

\begin{esempio}
Per grado $m^*=3$, ovvero ordine $m=m^*+1=4$ otteniamo le cosidette {\purples{splines cubiche}} $s_3$, cio\`e funzioni che 
\bit
\item in ogni intervallo
$[x_i,x_{i+1}]$ (per $i=0,\ldots,n-1$) siano polinomi di grado $m^*=3$,
\item globalmente funzioni di classe $C^{m^*-1}([a,b])=C^2([a,b])$. 
\eit
Come vedremo dopo, per garantirne l'unicit\mya si chiedono condizioni aggiuntive.
\end{esempio}
\end{frame}




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

\smnsp
{\small{
\begin{commento}[Funzioni polinomiali a tratti e splines: differenze]
Esistono molte {\purples{differenze tra interpolanti spline e interpolanti polinomiali a tratti}}. Ne citiamo alcune.
\begin{itemize}
\item Possono avere {\purples{diversa regolarit\myash}}. Osserviamo che {\bf{non sempre}} le funzioni polinomiali a tratti di grado $s$ sono di classe $C^{s-1}$ come invece lo sono le splines.
\item Mentre le funzioni interpolanti polinomiali a tratti di grado $s$ richiedono che il {\purples{numero di punti da interpolare}} sia $$sm+1$$ per qualche numero di suddivisioni $m$, le splines di grado $s$ sono {\purples{definite su un insieme di punti arbitrari}}, indipendentemente dal grado. 
\end{itemize}
\end{commento}

\begin{esempio}
Dati 6 punti $(x_k,y_k)$, con $k=0,\ldots,5$:
\begin{itemize}
\item \'e possibile calcolare una spline cubica che interpoli tali dati;
\item una interpolante cubica polinomiale a tratti, introdotta precedentemente, su una sola suddivisione richiede 4 punti, su 2 suddivisioni richiede 7 punti, altrimenti almeno 10 punti, e quindi non \'e adatta a interpolare solo 6 punti.
\end{itemize}
\end{esempio}
}}




\end{frame}





\begin{frame}[fragile]
\frametitle{Interpolazione spline (spline cubiche e interpolanti polinomiali a tratti)}

\smnsp
 \begin{figure}[ht!]\label{fig1aaaa}
 \centering
   {\includegraphics[scale=0.4,clip]{runge_plots.eps}}
   
   
   
 \caption{\scriptsize{
 
{\vspace{0.1cm}}
 
In {\bf{nero}} la funzione di Runge, in {\bf{\reds{rosso}}}, una interpolante spline cubica $s_3$ (avente $s_2^{(2)}(a)=s_2^{(2)}(a)=0$), nei punti $x_k=-5+k \cdot 10/9$, $k=0,\ldots,9$. In {\bf{\blues{blu}}}, la interpolante polinomiale $p^*_3$ a tratti di grado $3$, con suddivisione $[0,x_3]$. $[x_3,x_6]$, $[x_6,x_9]$. Si osservi che i punti $x_3 =-1.{\overline{6}}$, $x_6=1.{\overline{6}}$ sono angolosi per $p^*_3$. Le derivate infatti valgono $\lim_{x \rightarrow x_3^-} (p^*_3)^{\prime}(x) \approx 0.1990$, $\lim_{x \rightarrow x_3^+} (p^*_3)^{\prime}(x) \approx 0.6743$, $\lim_{x \rightarrow x_6^-} (p^*_3)^{\prime}(x) \approx -0.6736$, $\lim_{x \rightarrow x_6^+} (p^*_3)^{\prime}(x) \approx -0.1992$.
}}
 \end{figure}


\end{frame}



\begin{frame}[fragile]
\frametitle{Interpolazione spline: cubiche}

\smnsp

\begin{vuoto}[Unicit\'a splines cubiche]
Nel caso delle splines cubiche $s_3$, {\purples{l'unicit\'a dell'interpolante}} \`e legata (ma non solo!) all'aggiungere
alcune propriet\'a
di $s_3$ agli estremi $x_0$, $x_n$. 

\smsp

Osserviamo infatti che in ogni intervallo $[x_i,x_{i+1}]$ le spline si
possano rappresentare
come
$$s_3(x)=c_{1,i}+c_{2,i}(x-x_i)+c_{3,i}(x-x_i)^2+c_{4,i}(x-x_i)^3,
\,\,i=0,\ldots,n-1$$
e quindi per determinare $s_3$ in $\{x_i\}_{i=0,\ldots,n}$ servano {\purples{$4n$}}
valori $c_{i,j}$, ovvero $4$ valori per ogni indice $i$.

\smsp

Da ragionamenti sulle propriet\'a della {\purples{regolarit\'a}} della spline
interpolante si vede che sono disponibili {\purples{$4n-2$ condizioni}}:
\begin{itemize}
\item funzione continua nei punti di {\it{giunzione}} $x_1, \ldots,x_{n-1}$;
\item derivata prima continua in $x_1, \ldots,x_{n-1}$;
\item derivata seconda continua in $x_1, \ldots,x_{n-1}$;
\item interpolazione dei dati in $x_0, \ldots,x_{n}$;
\end{itemize}

\smsp

\end{vuoto}
\end{frame}





\begin{frame}[fragile]
\frametitle{Interpolazione spline: cubiche}
\begin{figure}[ht!]\label{fig1ZA}
 \centering
   {\includegraphics[scale=0.3,clip]{spl_unicity.png}}
 \caption{\small{Unicit\'a delle splines cubiche. Esempio dei vincoli.}}
 \end{figure}
\end{frame}





\begin{frame}[fragile]
\frametitle{Interpolazione spline: cubiche}

\smnsp

\begin{vuoto}
Visto che {\purples{mancano $2$ condizioni}} (ovvero $4n-(4n-2)$), usualmente si procede richiedendo una delle seguenti propriet\'a aggiuntive a $s_3$:
\smsp
\begin{itemize}
\item {\purples{Spline naturale}}: $s_3^{(2)}(a)=s_3^{(2)}(b)=0$.
\smsp
\item {\purples{Spline periodica}}: $s_3^{(1)}(a)=s_3^{(1)}(b)$,
$s_3^{(2)}(a)=s_3^{(2)}(b)$.
\smsp
\item {\purples{Spline vincolata}}: $s_3^{(1)}(a)=f^{(1)}(a),
\,\,s_3^{(1)}(b)=f^{(1)}(b)$.
\end{itemize}
\end{vuoto}
\end{frame}












\begin{frame}[fragile]
\frametitle{Interpolazione spline: cubiche}

\smnsp
{\small{
\begin{nota}[Storica]
Storicamente le {\it{splines}} sono state degli importanti strumenti di disegno, ad esempio utilizzate per progettare navi. 

\smsp

Prendendo spunto da questo strumento, Schoenberg ha introdotto compiutamente questo concetto matematico nel 1946, che ha cominciato ad avere un impatto nel mondo automobilistico negli anni 60 (studi rivelatisi poi importanti in aziende come Citro\"en, Renault, General Motors).

\smsp


Tali studi e loro modifiche hanno permesso di definire i moderni strumenti di grafica, come pure applicazioni in svariati campi, come ad esempio il disegno di fonts.
\end{nota}
}}

\begin{figure}[ht!]\label{fig1Z}
 \centering
   {\includegraphics[scale=0.25,clip]{spline_tool.jpg}}
      {\includegraphics[scale=0.085,clip]{boeing.jpg}}
 \caption{\tiny{Lo strumento noto come {\it{spline}}, di uso comune tra i disegnatori del dopoguerra.}}
 \end{figure}
\end{frame}





\begin{frame}[fragile]
\frametitle{Interpolazione spline: cubiche}

\smnsp
{\scriptsize{
\begin{nota}[Splines not-a-knot]
La spline con vincolo {\purples{not-a-knot}}  forza $s_3^{{\purples{(3)}}}$ ad essere continua nel secondo e nel penultimo nodo (e di conseguenza si pu\myo mostrare che ci\myo impone che i polinomi nei primi e negli ultimi due intervalli siano uguali) (cf. {\cite{ATK}}, p. 171). 

\smsp

In altre parole, 
\begin{itemize}
\item la suddivisione \mye data da $n-2$ subintervalli ${\purples{[x_0,x_2]}}$, $[x_2,x_3]$, $\ldots$, ${\purples{[x_{n-2},x_n]}}$,
\item si interpolano i dati $y_0,\ldots,y_n$ nei nodi $x_0,\ldots,x_n$.
\end{itemize}

\smsp

Si osservi che, nel caso della condizione {\it{knot-a-knot}} se i punti da interpolare sono $x_0,\ldots,x_n$ e gli $n-2$ intervalli della suddivisione sono $[x_0,x_2]$, $[x_2,x_3]$, $\ldots$, $[x_{n-2},x_n]$ allora necessitano {\purples{$4(n-2)$}} condizioni per determinare la spline cubica. 

\smsp

Le condizioni dovute
\begin{itemize}
\item all'interpolazione sono $n+1$, 
\item alla regolarit\mya sono $3(n-3)$, poich\mye gli $n-3$ punti che sono estremi di subintervalli {\it{interni}} sono $x_2,\ldots,x_{n-2}$,
\end{itemize}
e quindi sono pure {\purples{$4(n-2)$}}, ovvero quelle necessarie  per determinare la spline cubica. 

\smsp

Visto che 
\begin{itemize}
\item la restrizione del polinomio $s_3|_{[x_0,x_2]}$ in 
$[x_0,x_2]$ \'e sicuramente un polinomio in 
$[x_0,x_1]$ e $[x_1,x_2]$ e ovviamente essendo $s_3|_{[x_0,x_2]} \in C^{\infty}([x_0,x_2])$ e quindi $C^{2}([x_0,x_2])$;
\item la restrizione di un polinomio in 
$[x_{n-2},x_n]$ \'e sicuramente un polinomio in 
$[x_{n-2},x_{n-1}]$ e $[x_{n-1},x_n]$ e ovviamente essendo di classe $s_3|_{[x_{n-2},x_n]} \in C^{\infty}[x_{n-2},x_n]$ e quindi $C^{2}([x_{n-2},x_n])$;
\end{itemize}
si deduce che le splines cubiche not-a-knot sono splines cubiche relativamente alla suddivisione data dai punti $x_0$, $x_1$,$\ldots$, $x_{n-2}$, $x_{n-1}$, $x_{n}$.
\end{nota}
}}
\end{frame}






\begin{frame}[fragile]
\frametitle{Errore dell'interpolante spline cubica.}

{\small{
Analizziamo l'errore effettuato da una spline cubica $s_{3,n}:[a,b] \rightarrow \R$ che interpola le coppie
($x_i, f(x_i)$) dove $x_k=a+k \frac{(b-a)}{n}$, $k=0,\ldots,n$ \mye un set di punti equispaziati (con spaziatura $h=(b-a)/n$). Si mostra (non facile!) che:
\begin{teorema} Supponiamo $f\in C^4([a,b])$. Sia $s_{3,n}$ una spline cubica, che interpola le coppie $(x_k,f(x_k))$, $k=0,\ldots,n$, con $x_k=a+k \frac{(b-a)}{n}$ (ad esempio di tipo "naturale", o "periodica", o "vincolata").

\noindent
Allora esistono le costanti $c_0$, $c_1$, $c_2$, indipendenti da $h=\frac{(b-a)}{n}$ tale che
\begin{eqnarray}
\max_{x \in [a,b]}|f(x)-s_{3,n}(x)| &\leq& c_0 \, h^{4}
||f^{(4)}||_{\infty}= {c_0 (b-a)^4||f^{(4)}||_{\infty}}/{n^{4}},  \\
\max_{x \in [a,b]}|f^{(1)}(x)-s^{(1)}_{3,n}(x)|  &\leq& c_1 \, h^{3}
||f^{(4)}||_{\infty}= {c_1 (b-a)^3||f^{(4)}||_{\infty}}/{n^{3}},  \\
\max_{x \in [a,b]}|f^{(2)}(x)-s^{(2)}_{3,n}(x)|  &\leq& c_2 \, h^{2}
||f^{(4)}||_{\infty}= {c_2 (b-a)^2||f^{(4)}||_{\infty}}/{n^{2}}
\end{eqnarray}
dove $\|f\|_{\infty}=\max_{x \in [a,b]}|f(x)|$.
\end{teorema}

 \begin{nota}
 Nel caso di spline interpolanti e vincolate si ha $c_0=5/384$, $c_1=1/24$,
$c_2=3/8$. 
% \item Nel caso di splines di tipo {\it{Hermite}} si ha $c_0=1/384$
% (cf. {\cite{SULI}}, p. 301).


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









\begin{frame}[fragile]
\frametitle{Errore dell'interpolante spline cubica}
{\footnotesize{
\begin{nota}[Ordine]
Le spline cubiche si dicono di {\purples{ordine 4}} proprio perch\'e
$$
\max_{x \in [a,b]} |f(x)-s_{3,n}(x)| \leq c_0 \, h^{\purples{4}}
||f^{(4)}||_{\infty}.
$$
\end{nota}
 
\smnsp 

\begin{nota}[Convergenza uniforme e derivate]
 Si noti come in quest'ultimo teorema si afferma che se $f \in C^4([a,b])$ e le suddivisioni sono uniformi, allora non solo la spline
approssima la funzione, ma pure le sue {\purples{derivate
 convergano {\it{uniformemente}}}} alle rispettive derivate della funzione $f$, qualora $n $ tenda ad infinito.
 \end{nota}
 
\smnsp 
 
 
 \begin{nota}[Approssimazione di funzione ma non di sue derivate]
Se $f \approx g$, non e' detto $f^{\prime} \approx g^{\prime}$. A tal proposito si considerino per $x \in [0,10^{-8}\pi/2]$
 $$f(x) \equiv 0, {\mbox{            }}g(x)={10^{-8}}\sin(10^{8}x)$$

Essendo $g$ crescente e non negativa in $[0,10^{-8}\pi/2]$, si vede che 
$$\max_{x \in [0,10^{-8}\pi/2]} |f(x)-g(x)|=|0-10^{-8} \sin(10^{8} \cdot 10^{-8}\pi/2)|=10^{-8}.$$ 
D'altra parte, essendo  
$f^{\prime}(x) \equiv 0$ e $g^{\prime}(x)=\cos(10^{8}x)$,  in virt\'u del fatto che $g^{\prime}$ \'e decrescente e non negativa in $[0,10^{-8}\pi/2]$,
$$\max_{x \in [0,10^{-8}\pi/2]} |f^{\prime}(x)-g^{\prime}(x)|=\max_{x \in [0,10^{-8}\pi/2]} g^{\prime}(x)=\cos(10^{8} \cdot 0)=1.$$

\smnsp  

 \end{nota}
 
\smnsp  
 

 }}
\end{frame}





\begin{frame}[fragile]
\frametitle{Il controesempio di Runge e splines cubiche}
 
{\fns{
\begin{esempio}[Splines cubiche e funzione di Runge]
Analizzare la convergenza delle splines cubiche $s_{3,n}$ interpolanti (con vincoli {\it{naturali}}, oppure {\it{vincolati}}, oppure. {\it{periodici}}) in $n$ punti equispaziati
$$
x_k=-5+\frac{10k}{n}, \,\,\, k=0,\ldots,n,
$$
la funzione di Runge
 $$
 f(x)=\frac {1}  {1+x^2}, \,\,\, x \in [-5,5].
 $$
 \end{esempio}
 
 \begin{svolgimento}
Dopo qualche calcolo si vede che
% \begin{itemize}
%\item 
%$$f^{(1)}(x)=\frac {2x}  {(1+x^2)^2}$$
%$$f^{(2)}(x)=\frac{2\cdot(3x^2 - 1)}{(x^2 + 1)^3}$$
%\item $f^{(3)}(x)=\frac {-24x(x^2 - 1)}{(x^2 + 1)^4}$.
$$f^{(4)}(x)= \frac{24(5x^4 - 10x^2 + 1)}{(x^2 + 1)^5}, {\hspace{0.75cm}} ||f^{(4)}||_{\infty}=\max_{x \in [-5,5]} |f^{(4)}(x)|=24$$
%\end{itemize}
e che quindi per un qualche $c_0$ indipendente da $n$
\begin{eqnarray}
0\leq \|f-s_{3,n}\|_{\infty} &:=& \max_{x \in [-5,5]}|f(x)-s_{3,n}(x)\|_{\infty} \leq c_0 \, h^{4}
||f^{(4)}||_{\infty} \nonumber \\
&=& c_0 \frac{(b-a)^4}{n^4} \cdot 24.
\end{eqnarray}
\end{svolgimento}
}}
\end{frame}






\begin{frame}[fragile]
\frametitle{Il controesempio di Runge e splines cubiche}
\begin{vuoto}
Essendo
\begin{eqnarray}
0\leq \|f-s_{3,n}\|_{\infty} &:=& \max_{x \in [-5,5]}|f(x)-s_{3,n}(x)\|_{\infty} \leq c_0 \frac{(b-a)^4}{n^4} \cdot 24 \nonumber
\end{eqnarray}
per il teorema del confronto
$$
\lim_n \|f-s_{3,n}\|_{\infty} =0
$$
ovvero le spline cubiche $s_{3,n}$ che interpolano nei nodi 
$$
x_k=-5+k\frac{10}{n}, \,\,\,\, k=0,\ldots,n
$$
la funzione di Runge $f$, sono tali che la successione $\{s_{3,n}\}$ converge uniformemente a $f$. 
\end{vuoto}
\end{frame}






\begin{frame}[fragile]
\frametitle{Il controesempio di Runge e splines cubiche}
 \begin{table}[h!]
\begin{center}
\begin{tabular}{| c c  | c c |}
\hline
$n$&   $E_n$ & $n$&   $E_n$  \\
\hline
  	 $       2$ & $9.62e-01$ & $     512$ & $1.58e-07$ \\
 	 $       4$ & $7.01e-01$ & $    1024$ & $3.93e-08$ \\
 	 $       8$ & $2.46e-01$ & $    2048$ & $9.82e-09$ \\
 	 $      16$ & $3.09e-02$ & $    4096$ & $2.45e-09$ \\
 	 $      32$ & $1.31e-03$ & $    8192$ & $2.15e-10$ \\
 	 $      64$ & $4.81e-05$ & $   16384$ & $2.98e-11$ \\
 	 $     128$ & $2.56e-06$ & $   32768$ & $6.95e-13$ \\
 	 $     256$ & $6.36e-07$ & $   65536$ & $3.08e-15$ \\
  \hline
\end{tabular}
\caption{Grado $n$ ed errore $E_n=\max_{x \in [-5,5]} |f(x)-s_{3,n}(x)|$ con $s_{3,n}(x)$ interpolante $f$ di tipo spline cubica naturale, in $n+1$ nodi equispaziati. Si osservi come numericamente $E_n \rightarrow 0$ e di come la convergenza sia molto pi\myu rapida che nel caso delle spline interpolanti di grado $1$.}
\end{center}
\end{table}
\end{frame}




\begin{frame}[fragile]
\frametitle{Il controesempio di Runge}

\smnsp
 \begin{figure}[ht!]\label{fig1aaaa}
 \centering
   {\includegraphics[scale=0.4,clip]{runge_unif_cub.eps}}
   
   
   
 \caption{Funzione di Runge e interpolanti spline cubiche naturali (in 2,4,8 suddivisioni equispaziate).}
 \end{figure}


\end{frame}



\begin{frame}[fragile]
\frametitle{Il controesempio di Runge}

\smnsp
 \begin{figure}[ht!]\label{fig1aaaa}
 \centering
{\includegraphics[scale=0.25,clip]{runge_unif_cub_errsA.eps}}
   
   \smnsp
   
 \caption{Funzione di Runge e interpolanti spline cubiche naturali (in 2,4,8,16,32 suddivisioni equispaziate). Errori puntuali e massimi errori (rispettivamente e approssimativamente $4.8e-1$, $2.7e-1$, $5.6e-2$, $3.7e-3$, $7.8e-4$).}
 \end{figure}


\end{frame}







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

\begin{thebibliography}{99} 
\bibitem{ATK} K. Atkinson, {\it{Introduction to Numerical Analysis}}, Wiley, 1989.
\bibitem{COM} V. Comincioli, {\it{Analisi Numerica, metodi modelli
applicazioni}}, Mc Graw-Hill, 1990.
\bibitem{DEBS}  {\href{http://pages.cs.wisc.edu/\~deboor/draftspline.html}{Carl DeBoor, {\it{personal homepage}}}}.
\bibitem{SULI} A. Suli e D. Mayers, {\it{An Introduction to Numerical Analysis}}, Cambridge University Press, 2003.
\bibitem{ALA} A. Townsend, On the Spline, {\url{http://www.alatown.com/spline/\#more-809}}.
\bibitem{WIKFS} {\href{http://it.wikipedia.org/wiki/Funzione\_spline}{Wikipedia, Funzione Spline}}.
\bibitem{WIKSD}  {\href{http://en.wikipedia.org/wiki/Spline\_\%28device\%29}{Wikipedia, Spline Device}}.
\bibitem{WIKSM} {\href{http://en.wikipedia.org/wiki/Spline\_\%28mathematics\%29}{Wikipedia, Spline Mathematics}}.
\bibitem{WIKIS} {\href{http://it.wikipedia.org/wiki/Interpolazione\_spline}{Wikipedia, Interpolazione Spline}}.

\end{thebibliography}
\end{frame}

\end{document}







