\documentclass{beamer}

\usepackage{beamerthemesplit}
\usepackage{graphicx}

%\usecolortheme{rose}
\useinnertheme[shadow]{rounded}
%\usecolortheme{dolphin}
%\useoutertheme{infolines}



%------------------------------------------------------------------------------------------------------------------------
% USEPACKAGE.
%------------------------------------------------------------------------------------------------------------------------

\usepackage[italian]{babel}
\usepackage{graphicx,psfrag,color,pst-grad}
\usepackage{latexsym}
\usepackage{psboxit,pstricks}
\usepackage{fancybox}
\usepackage{fancyhdr}
\usepackage{fancyvrb}

\usepackage{float}
\floatstyle{ruled}
\newfloat{program}{thp}{lop}
\floatname{program}{Codice}
\pdfpagewidth 8.5in
\pdfpageheight 11in

\usepackage{calc}
\usepackage{multicol}

\usepackage{listings}
\usepackage{color}
\usepackage{textcomp}



%------------------------------------------------------------------------------------------------------------------------
% NEW COMMAND.
%------------------------------------------------------------------------------------------------------------------------

\newcommand{\ptenm}[2]{#1\mbox{-E#2}}
\newcommand{\ptenp}[2]{#1\mbox{+E#2}}
\newcommand{\mye}{\`e }
\newcommand{\myer}{\'e }
\newcommand{\myu}{\`u }
\newcommand{\myur}{\'u }
\newcommand{\mya}{\`a }
\newcommand{\myo}{\`o }
\newcommand{\myod}{\'o }
\newcommand{\myi}{\`i }
\newcommand{\myid}{\'i }
\newcommand{\myfl}{\mbox{fl}}
\newcommand{\smsp}{\vspace{0.2cm}}
\newcommand{\smhsp}{\hspace{0.2cm}}
\newcommand{\Rset}{\mathbb{R}}
\newcommand{\bs}{\boldsymbol}
\newcommand{\mylbar}{|}
\newcommand{\myrbar}{|}
\newcommand{\reds}{\color{red}}
\newcommand{\blues}{\color{blue}}
\newcommand{\magentas}{\color{magenta}}

%\pagestyle{fancy}
%\headheight 35pt
%\rhead{}
%\chead{}
%\lhead{}
%\rfoot{}
%\cfoot{\thepage}
%\lfoot{}



%------------------------------------------------------------------------------------------------------------------------
% NEW THEOREM.
%------------------------------------------------------------------------------------------------------------------------

%\newtheorem{theorem}{Theorem}[section]
%\newtheorem{lemma}[theorem]{Lemma}
%\newtheorem{proposition}[theorem]{Proposition}
%\newtheorem{corollary}[theorem]{Corollary}
% \newtheorem{remark}[theorem]{Nota}
%\newenvironment{proof}[1][Proof]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{definition}[1][Definition:]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{example}[1][Esempio]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
%\newenvironment{remark}[1][Nota]{\begin{trivlist}
%\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
\newenvironment{teorema}[1][Teorema.]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

\newenvironment{corollario}[1][Corollario.]{\begin{trivlist}
\item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}

%------------------------------------------------------------------------------------------------------------------------
% NEW COMMAND.
%------------------------------------------------------------------------------------------------------------------------

\renewcommand{\figurename}{Figura}
%\newcommand{\qed}{\nobreak \ifvmode \relax \else
%     \ifdim\lastskip<1.5em \hskip-\lastskip
%    \hskip1.5em plus0em minus0.5em \fi \nobreak
% \vrule height0.75em width0.5em depth0.25em\fi}



%------------------------------------------------------------------------------------------------------------------------
% DEF.
%------------------------------------------------------------------------------------------------------------------------

\def\P{{\mathbb P}}
\def\n{{\mathcal N}}
\def\R{\mathbb{R}}
\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\F{{\mathcal F}}
\newcommand{\LL}{\mathcal L}
\def\C{\mathbb{C}}
\def\K{\mathbb{K}}
\def\T{\mathbb{T}}
\def\qed{\vbox{\hrule height0.6pt\hbox{%
   \vrule height1.3ex width0.6pt\hskip0.8ex
   \vrule width0.6pt}\hrule height0.6pt
  }}




\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{light-gray}{gray}{0.90}
\definecolor{floralwhite}{rgb}{1.0, 0.98, 0.94}
\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\newcommand{\bl}{\begin{lstlisting}}
\newcommand{\el}{\end{lstlisting}}
\newcommand{\ma}{{\sc Matlab }}
\newcommand{\mass}{{\sc Matlab}}
\newcommand{\mo}{{\sc Matlab/Octave }}
\newcommand{\monb}{{\sc Matlab/Octave}}
\newcommand{\oc}{{\sc Octave }}
\newcommand{\ocnb}{{\sc Octave}}
\newtheorem{Esercizio1}{Esercizio 1}
\newtheorem{Esercizio2}{Esercizio 2}
\newcommand{\ntt}{\color{blue} \tt}


\lstset{ 
language=Matlab,                % the language of the code
% basicstyle=\footnotesize,       % the size of the fonts that are used for the code
basicstyle=\scriptsize,
numbers=left,                   % where to put the line-numbers
% numberstyle=\footnotesize,      % the size of the fonts that are used for the line-numbers
numberstyle=\scriptsize,      % the size of the fonts that are used for the line-numbers
stepnumber=0,                   % the step between two line-numbers. If it's 1, each line 
                                % will be numbered
numbersep=5pt,                  % how far the line-numbers are from the code
backgroundcolor=\color{gray!35},  % choose the background color. You must add \usepackage{color}
showspaces=false,               % show spaces adding particular underscores
showstringspaces=false,         % underline spaces within strings
showtabs=false,                 % show tabs within strings adding particular underscores
frame=false,                   % adds a frame around the code
tabsize=2,                      % sets default tabsize to 2 spaces
captionpos=b,                   % sets the caption-position to bottom
breaklines=true,                % sets automatic line breaking
breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
title=\lstname,                 % show the filename of files included with \lstinputlisting;
                                % also try caption instead of title
escapeinside={\%*}{*)},         % if you want to add a comment within your code
morekeywords={*,...},            % if you want to add more keywords to the set
 identifierstyle=\ttfamily,
keywordstyle=\color[rgb]{0,0,1},
commentstyle=\color[rgb]{0.133,0.545,0.133},
stringstyle=\color[rgb]{0.627,0.126,0.941}
}


% MIO
%\lstset{ %
%  language=Matlab,                % the language of the code
%  basicstyle=%\color{red}
%              \footnotesize,           % the size of the fonts that are used for the code
%%  backgroundcolor=\color{white},      % choose the background color. You must add \usepackage{color}
%  showspaces=false,               % show spaces adding particular underscores
%  showstringspaces=false,         % underline spaces within strings
%  showtabs=false,                 % show tabs within strings adding particular underscores
%  frame=single,                   % adds a frame around the code
%  rulecolor=\color{white},        % if not set, the frame-color may be changed on line-breaks within not-black text (e.g. commens (green here))
%  tabsize=2,                      % sets default tabsize to 2 spaces
%  breaklines=true,                % sets automatic line breaking
%  breakatwhitespace=false,        % sets if automatic breaks should only happen at whitespace
%  keywordstyle=\color{blue},          % keyword style
%%  commentstyle=\color{dkgreen},       % comment style
%  commentstyle=\color{blue},       % comment style
%  stringstyle=\color{mauve},         % string literal style
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%identifierstyle=\color{magenta}
%  escapeinside={\%*}{*)},            % if you want to add a comment within your code
%  morekeywords={*,nomefun}               % if you want to add more keywords to the set
%}


\setlength{\tabcolsep}{2.5pt}
\setbeamertemplate{navigation symbols}{} %no nav symbols

\title[Splines\hspace{2em}\insertframenumber/
\inserttotalframenumber]{Splines}


\author{\'Angeles Mart\'inez Calomardo e Alvise Sommariva}
\institute{Universit\`a degli Studi di Padova}
\date{\today}

\begin{document}
\frame{\titlepage}

\begin{frame}[fragile]
\frametitle{Interpolazione nodi equispaziati e problemi}
E' noto che nel caso dell'interpolazione polinomiale,
 dati $N+1$ punti $a=x_0<\ldots<x_N=b$, e i valori $y_0,\ldots,y_N$ ivi
assunti dalla funzione $y=f(x)$, esiste unico il polinomio $p_N$ di
grado $N$ tale che
\begin{equation}
p_N(x_i)=f_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$, non si pu\'o garantire che $f-p_n$ tenda a $0$ puntualmente (si ricordi il {\reds{fenomeno di Runge}}!).

{\vspace{0.5cm}}

{\bf{Problema:}} 

{\bf{
{\magentas{
E' possibile calcolare una interpolante di tipo
polinomiale $s_N$ per cui al crescere di $N$ si abbia $s_N \rightarrow f$ puntualmente?
}}
}}

\end{frame}








\begin{frame}[fragile]
\frametitle{Splines}
Sia $[a,b] \subset {\mathbb{R}}$ chiuso e limitato, e sia $a=x_0< x_1 < \ldots < x_{n}=b$.
Una {\color{red}{spline di grado $m$}} (o {\it{ordine} $m+1$}) \mye una funzione in $C^{m-1} ([a,b])$ che in ogni intervallo $[x_i,x_{i+1}]$, con $i=0,\ldots,n-1$, \mye un polinomio di
grado $m$.

\smsp
Alcuni esempi:
\begin{itemize}
\item   {\color{red}{spline di grado $1$ (lineari)}}: una funzione in $C([a,b])$ che in ogni intervallo $[x_i,x_{i+1}]$, con $i=0,\ldots,n-1$, \mye un polinomio di
grado $1$.
\item   {\color{red}{spline di grado $3$ (cubiche)}}: una funzione in $C^2([a,b])$ che in ogni intervallo $[x_i,x_{i+1}]$, con $i=0,\ldots,n-1$, \mye un polinomio di
grado $3$.
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Splines di grado 1 e lineari a tratti}
Come anticipato sono funzioni $C([a,b])$ che in ogni intervallo $[x_i,x_{i+1}]$, con $i=0,\ldots,n-1$, \mye un polinomio di
grado $1$. Di conseguenza sono {\color{red}{funzioni continue lineari a tratti}}, essendo un segmento il grafico di un polinomio di grado $1$ in $[x_i,x_{i+1}]$.

 \begin{figure}\label{fig1}
 \centering
   {\includegraphics[scale=0.45,clip]{lineari_tratti_esempio.eps}}
 \caption{Splines grado 1 ($n=10$ intervalli di uguale ampiezza).}
 \end{figure}

\end{frame}



\begin{frame}[fragile]
\frametitle{Interpolazione con splines: alcuni fatti.}
Dati $n+1$ punti in $[a,b]$, diciamo $$a=x_0 < x_1< \ldots < x_{n-1}<x_n=b,$$ supponiamo di dover {\color{red}{interpolare}} le coppie $(x_k,y_k)$ con $k=0,\ldots,n$.
\begin{itemize}
\item {\blues{esiste unica la spline intp. $s_1$ di grado $1$ }}, cio\mye tale che $s_1(x_k)=y_k$ per $k=0,\ldots,n$. 
\item {\blues{non esiste unica la spline intp. $s_3$ di grado $3$}}, cio\mye  tale che $s_3(x_k)=y_k$ per $k=0,\ldots,n$. Servono $\color{red}{2}$ ulteriori condizioni per determinare univocamente la spline $s_3$ interpolante.
Alcune classiche richieste aggiuntive.
\begin{itemize}
\item  {\color{red}{Spline naturale}}: $s_3^{(2)}(a)=s_3^{(2)}(b)=0$.
\smsp
\item  {\color{red}{Spline periodica}}: $s_3^{(1)}(a)=s_3^{(1)}(b)$,
$s_3^{(2)}(a)=s_3^{(2)}(b)$.
\smsp
\item  {\reds{Spline vincolata}}: $s_3^{(1)}(a)=y^{\prime}_a,
\,\,s_3^{(1)}(b)=y^{\prime}_b$ (con $y^{\prime}_a,y^{\prime}_b$ assegnati).
\end{itemize}

\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Splines cubiche di tipo {\it{not-a-knot}}}
La spline cubica $s^{NAK}_3$ con vincolo {\reds{not-a-knot}} \mye definita come segue:
\begin{itemize}
\item  Interpola le coppie $(x_0,y_0)$, $\ldots$,  $(x_n,y_n)$;
\item  E' un polinomio di grado 3 nell'intervallo $[x_0,x_2]$;
\item  E' un polinomio di grado 3 nell'intervallo $[x_{n-2},x_n]$
\end{itemize}
Si osservi che per le spline cubiche generiche $s_3$ non \mye detto che la restrizione di $s_3$ a $[x_0,x_1]$ e $[x_1,x_2]$ siano lo stesso polinomio, e similmente 
che la restrizione a $[x_{n-2},x_{n-1}]$ e $[x_{n-1},x_n]$ siano lo stesso polinomio.

\smsp
Vediamo il confronto dei gradi di libert\'a. 
\begin{itemize}
\item {\bf{Richieste}}: Abbiamo $n-2$ polinomi da determinare e quindi $4(n-2)$ condizioni.
\item {\bf{Fornite}}: Interpolazione  $x_0,\ldots,x_{n}$: $n+1$ condizioni. Regolarit\mya $x_2,\ldots,x_{n-2}$: $3(n-3)$ condizioni.
\end{itemize}
Quindi il numero di gradi di libert\'a richiesto e fornito \mye lo stesso.
\end{frame}


\begin{frame}[fragile]
\frametitle{Splines lineari: stima errore}
Sia $s_{1,\Delta}:[a,b] \rightarrow \R$ una spline di grado 1, che interpola le coppie
($x_i,f(x_i)$) dove $x_0=a<x_1< \ldots <x_i < x_{i+1} < \ldots < x_N=b.$
$\Delta=\{x_i\}_{i=0,\ldots,N}$ indica la suddivisione $[a,b]=\cup_{i=0}^{n-1} [x_i,x_{i+1}]$.

Si pu\myo mostrare che 
\begin{equation}\label{errorelineare_8}
\reds{|f(x)-s_{1,\Delta}(x)| \leq    h_{i,\Delta}^2 {\frac{M_{i,\Delta}}{8}}, \smhsp x \in [x_i,x_{i+1}]}, 
\end{equation}
con
\begin{itemize}
\item $h_{i,\Delta}=x_{i+1}-x_i$,
\item $M_{i,\Delta}:=\max_{x \in [x_i,x_{i+1}]}|f^{(2)}(x)|$.
\end{itemize}
Di conseguenza, se $f \in C^2([a,b])$, per $M=\|f^{(2)}\|_{\infty}=\max_i M_i$
\begin{eqnarray}
{\blues{\max_{x \in [a,b]}|f(x)-s_{1,\Delta}(x)|}}&=&\max_{i=0,\ldots,N-1} \max_{x \in [x_i,x_i+1]}|f(x)-s_{1,\Delta}(x)| \nonumber \\
&\leq& \max_{i=0,\ldots,N-1} h_{i,\Delta}^2 {\frac{M_{i,\Delta} }{8}} {\blues{\leq   {\frac{M }{8}} (\max_i{h_{i,\Delta}})^2}} . \nonumber
\end{eqnarray}
\end{frame}

\begin{frame}[fragile]
\frametitle{Splines lineari: convergenza uniforme}
Sia ${\overline h}_{\Delta}=\max_i {h_{i,\Delta}}$. Sia fissata la famiglia di suddivisioni $\{\Delta_n\}$ con la propriet\mya che ${\overline h}_{\Delta_n} \rightarrow 0$ (suddivisioni sempre pi\myu fini). Allora la convergenza della successioni di interpolanti $s_{1,\Delta_n}$ ad una funzione $f \in C^{2}([a,b])$ \mye {\reds{uniforme}}. Infatti:
$$\|f-s_{1,\Delta_n}\| \leq {\frac{M }{8}} (\max_i{h_{i,\Delta_n}})^2=  {\frac{M }{8}} {{\overline h}_{\Delta_n}^2} {\stackrel{n}{\rightarrow}} 0.$$ 
\end{frame}


\begin{frame}[fragile]
\frametitle{Splines cubiche: stima errore}
Consideriamo di seguito spline cubiche $s_{3,\Delta_n}$ su una suddivisione $\Delta_n=\{x_i\}$ di $[a,b]$. Poniamo $h_{i,\Delta}=x_{i+1}-x_i$, $f^{(k)}$ derivata $k$-sima di $f$.
\begin{teorema}
Supponiamo $f\in C^4([a,b])$. Posto ${\overline h}_{\Delta}=\max_i {h_{i,\Delta}}$, si consideri una sudd. $\Delta=\{x_i\}$ di $[a,b]$ con $K_{\Delta}=\max_i {{\overline h}_{\Delta}/h_{i,\Delta}}$.

\smsp
Esiste una costante $c_s$ indipendente da ${\overline h}_{\Delta}$ tale che
{\bf{\blues{
\begin{equation}\label{3445}
\|f^{(s)}-s^{(s)}_{3,\Delta}\|_{\infty} \leq c_s K_{\Delta} {\overline h}_{\Delta}^{(4-s)}
||f^{(4)}||_{\infty}, \,\, s=0,1,2,3
\end{equation}
}}}
dove $\|f\|_{\infty}=\max_{x \in [a,b]}|f(x)|$.
\end{teorema}

\smsp
PS. Notare le componenti dell'errore dovute alla suddivisione (cio\mye $K_{\Delta}$ e ${\overline h}_{\Delta}$) e alla funzione $f$ (cio\mye $\|f^{(4)}\|_{\infty}$).
\end{frame}



\begin{frame}[fragile]
\frametitle{Splines cubiche: stima errore}
\begin{corollario}{\label{3445}}
Supponiamo $f\in C^4([a,b])$. Si consideri la
suddivisione $\Delta=\{x_i\}$ di $[a,b]$ con ${\overline{h}}_{\Delta}=h_{i,\Delta}=h_{\Delta}$ (cio\mye $\{x_i\}$ nodi equisp.). Allora esiste una costante $c_0$ indipendente da $h$ tale che
\begin{equation}
\reds{\|f-s_{3,\Delta}\|_{\infty} \leq c_0 \, h_{\Delta}^{4} ||f^{(4)}||_{\infty}}
\end{equation}
Inoltre esistono delle costanti $c_1$, $c_2$, $c_3$ indipendenti da $h$ tali che
\begin{eqnarray}
\|f^{(1)}-s^{(1)}_{3,\Delta}\|_{\infty} &\leq& c_1 \, h_{\Delta}^{3}
||f^{(4)}||_{\infty},  \\
\|f^{(2)}-s^{(2)}_{3,\Delta}\|_{\infty} &\leq& c_2 \, h_{\Delta}^{2}
||f^{(4)}||_{\infty},  \\
\|f^{(3)}-s^{(3)}_{3,\Delta}\|_{\infty} &\leq& c_3 \, h_{\Delta}^{1}
||f^{(4)}||_{\infty},
\end{eqnarray}
dove $\|f\|_{\infty}=\max_{x \in [a,b]}|f(x)|$.
\end{corollario}
Nel caso di spline interpolanti e vincolate si ha $c_0=5/384$, $c_1=1/24$,
$c_2=3/8$. 
\end{frame}


\begin{frame}[fragile]
\frametitle{Splines cubiche: convergenza uniforme}
Sia ${\overline h}_{\Delta}=\max_i {h_{i,\Delta}}$. Sia fissata la famiglia di suddivisioni $\{\Delta_n\}$ con la propriet\mya che $K=max_n  K_{\Delta_n} < +\infty$ e ${\overline h}_{\Delta_n} \rightarrow 0$ (suddivisioni sempre pi\myu fini). Allora {\reds{la convergenza della successioni di interpolanti $s_{3,\Delta_n}$ ad una funzione $f \in C^{2}([a,b])$ \mye uniforme}}. Infatti da ({\ref{3445}}):
$$\|f^{(s)}-s^{(s)}_{3,\Delta_n}\|_{\infty} \leq c_s K {\overline h}_{\Delta_n}^{(4-s)}
||f^{(4)}||_{\infty} {\stackrel{n}{\rightarrow}} 0.$$ 

\smsp
NB: Per $s=3$, significa che la successione di funzioni a gradino $s^{(3)}_{3,\Delta_n}$ converge a $f^{(3)}$ uniformemente. 
\end{frame}















\begin{frame}[fragile]
\frametitle{Splines lineari: esempio di Runge.}
La funzione di Runge $f(x)=1/(1+x^2)$ appartiene a $C^{\infty}([-5,5])$ e di conseguenza, nonostante la convergenza puntuale dell'interpolazione polinomiale in nodi equispaziati non sia garantita, ci\myo non si pu\myo dire per l'interpolazione mediante splines lineari o cubiche (sappiamo sussistere la conv. unif.!). Vediamo una stima dell'errore pi\myu precisa.
Nel caso lineare, se $\Delta=\{x_i\}$ \mye la {\reds{sudd. equisp.}} di ampiezza $h_{\Delta}$, se $x \in [x_i,x_{i+1}]$
\begin{equation}\label{errorelineare2aa}
|f(x)-s_{1,\Delta}(x)| \leq       h_{i,\Delta}^2 {\frac{M_{i,\Delta}}{ 8}} = h_{\Delta}^2 {\frac{M_{i,\Delta}}{ 8}}
\end{equation}
dove
$$M_{i,\Delta}=\max_{x\in(x_i,x_{i+1})}|f^{(2)}(x)|.$$
con $$f^{(2)}(x)=(8\,x^2)/(x^2+1)^3-2/(x^2+1)^2.$$
\end{frame}

\begin{frame}[fragile]
\frametitle{Splines lineari: esempio di Runge.}
Dal grafico di $|f^{(2)}|$ deduciamo che $$M_i \leq M=\|f^{(2)}\|_{\infty}=|f^{(2)}(0)|= 2$$ e quindi se $x \in [x_i,x_{i+1}]$
$$|f(x)-s_{1,\Delta}(x)| \leq    h_{\Delta}^2 {\frac{M_i }{ 8}}  \leq    h_{\Delta}^2 {\frac{M}{ 8}} \leq  {\frac{h_{\Delta}^2}{ 4}} \Rightarrow \|f-s_{1,\Delta}\|_{\infty} \leq  {\frac{h_{\Delta}^2}{ 4}}.$$ 
 \begin{figure}\label{fig1a}
 \centering
   {\includegraphics[scale=0.35,clip]{der2_runge.eps}}
 \caption{Grafico di $|f^{(2)}|$ per $f(x)=1/(1+x^2)$, in $[-5,5]$.}
 \end{figure}

\end{frame}

\begin{frame}[fragile]
\frametitle{Splines cubiche: esempio di Runge.}
Usiamo le notazioni precedenti. Sappiamo che ${\|f-s_{3,\Delta}\|_{\infty} \leq c_0 \, h_{\Delta}^{4} ||f^{(4)}||_{\infty}}$ e si pu\myo vedere che
$$f^{(4)}(x)=24/(x^2+1)^3-288 \cdot x^2/(x^2+1)^4+384 \cdot x^4/(x^2+1)^5$$ il cui massimo modulo in $[-5,5]$ \mye $|f^{(4)}(0)|=24$.
Quindi per splines cubiche intp. vincolate, essendo $c_0=5/384$
$${\|f-s_{3,\Delta}\|_{\infty}  \leq c_0 \, h_{\Delta}^{4} ||f^{(4)}||_{\infty}} \leq (120/384) h_{\Delta}^{4}.$$
 \begin{figure}\label{fig1a}
 \centering
   {\includegraphics[scale=0.3,clip]{der4_runge.eps}}
 \caption{Grafico di $|f^{(4)}|$ per $f(x)=1/(1+x^2)$, in $[-5,5]$.}
 \end{figure}

\end{frame}


\begin{frame}[fragile]
\frametitle{Splines lineari e cubiche: confronto esempio di Runge.}
 \begin{figure}\label{fig1a}
 \centering
   {\includegraphics[scale=0.35,clip]{err_runge.eps}}
 \caption{Grafico stime errori intp. splines lineari e cubiche vincolate (ascissa: $x=-log_{10}(h)$).}
 \end{figure}
\begin{lstlisting}
>> n=0:0.2:15; h=10.^(-n);
>> e1=(h.^2)/4; e3=(120/384)*(h.^4);
>> semilogy(n,e1,'r-',n,e3,'k-');
>> legend('lineare','cubica');
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
\frametitle{Splines interpolanti in Matlab/Octave: {\tt{spline}}}
Alcuni comandi per calcolare interpolazione spline in Matlab/Octave
\begin{lstlisting}
SPLINE Cubic spline data interpolation.
YY = SPLINE(X,Y,XX) uses cubic spline interpolation to find YY, the values of the underlying function Y at the points in the vector XX.
The vector X specifies the points at which the data Y is given. ...
Ordinarily, the not-a-knot end conditions are used.However,if Y contains two more values than X has entries, then the first and last value in Y are used as the endslopes for the cubic spline. 
...
\end{lstlisting}        
\end{frame}

\begin{frame}[fragile]
\frametitle{Splines interpolanti in Matlab/Octave: {\tt{spline}}}
\begin{lstlisting}
Example: This generates a sine curve, then samples the spline over a finer mesh:

x = 0:10;  y = sin(x); 
xx = 0:.25:10; yy = spline(x,y,xx); 
plot(x,y,'o',xx,yy)

Example: This illustrates the use of clamped or complete spline interpolation where end slopes are prescribed. Zero slopes at the ends of an interpolant to the values of a certain distribution are enforced:

x = -4:4; y = [0 .15 1.12 2.36 2.36 1.46 .49 .06 0];
cs = spline(x,[0 y 0]); 
xx = linspace(-4,4,101); 
plot(x,y,'o',xx,ppval(cs,xx),'-');

See also INTERP1, PPVAL, SPLINES (The Spline Toolbox).
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]
\frametitle{Splines interpolanti in Matlab/Octave: {\tt{interp1}}}
\begin{lstlisting}
INTERP1 1-D interpolation (table lookup).    
YI = INTERP1(X,Y,XI) interpolates to find YI, the values of the underlying function Y at the points in the vector XI.The vector X specifies the points at which the data Y is given. ...
YI = INTERP1(X,Y,XI,'method') specifies alternate methods.
The default is linear interpolation.  Available methods are:
'nearest'  - nearest neighbor interpolation
'linear'   - linear interpolation
'spline'   - piecewise cubic spline interpolation (SPLINE)
'pchip'    - piecewise cubic Hermite interpolation (PCHIP)
'cubic'    - same as 'pchip'
'v5cubic'  - the cubic interpolation from MATLAB 5, which does not extrapolate and uses 'spline' if Xmis not equally spaced. ...
\end{lstlisting}

\end{frame}

\begin{frame}[fragile]
\frametitle{Splines interpolanti in Matlab/Octave: {\tt{interp1}}}
\begin{lstlisting}
For example, generate a coarse sine curve and interpolate over a finer abscissa:
x = 0:10; y = sin(x); xi = 0:.25:10;
yi = interp1(x,y,xi); plot(x,y,'o',xi,yi)

See also INTERP1Q, INTERPFT, SPLINE, INTERP2, INTERP3, INTERPN.
\end{lstlisting}

\smsp
Quindi dall'help di {\tt{spline}} e {\tt{interp1}} deduciamo che: 
\begin{itemize}
\item  {\reds{spline}}: calcola spline {\bf{cubica}} intp. con vincolo {\it{not-a-knot}} e con qualche assegnazione anche {\it{vincolate}};
\item  {\reds{interp1}}: calcola spline {\bf{lineare}} o spline {\bf{cubica}} intp. con vincolo {\it{not-a-knot}} e con qualche assegnazione anche di altro tipo.
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Splines interpolanti in Matlab/Octave: esempio di Runge}
Vediamo il comportamento della spl. lineare intp. la funzione di Runge in 13 nodi equisp., ricordando che l'interpolante polinomiale $p_{12}$ su 13 nodi, aveva $\|f-p_{12}\| \approx 3.66+00$. Il file \mye {\tt{runge\_lin.m}}.

\begin{lstlisting}
n=13;
f=inline('1./(1+x.^2)'); % RUNGE.
t=linspace(-5,5,1000); % NODI TEST.
x=linspace(-5,5,n); % NODI SUDDIV.
y=feval(f,x); % (x,y) COPPIE INTP.
st=interp1(x,y,t,'linear'); 
ft=feval(f,t);
err=norm(ft-st,inf); % ERRORE |f-s3|
fprintf('\n \t err: %2.2e \n',err);
\end{lstlisting}
Otteniamo, come supposto, un migliore risultato rispetto a $p_{12}$ (stime: $\leq ((10/12)^2)/4 \approx 0.17.$)
\begin{lstlisting}
>> runge_lin
 	 err: 6.50e-02 
>> 
\end{lstlisting} 
\end{frame}

\begin{frame}[fragile]
\frametitle{Splines interpolanti in Matlab/Octave: esempio di Runge}
Vediamo il comportamento delle spline cubiche not-a-knot interpolanti la funzione di Runge in 13 nodi equispaziati (avevamo $\|f-p_{12}\| \approx 3.66+00$).
Il file \mye {\tt{runge\_cub.m}}.
\begin{lstlisting}
n=13;
f=inline('1./(1+x.^2)'); % RUNGE.
t=linspace(-5,5,1000); % NODI TEST.
x=linspace(-5,5,n); % NODI SUDDIV.
y=feval(f,x); % (x,y) COPPIE INTP.
st=interp1(x,y,t,'spline'); 
ft=feval(f,t);
err=norm(ft-st,inf); % ERRORE |f-s3|
fprintf('\n \t err: %2.2e \n',err);
\end{lstlisting}
Otteniamo, come supposto, un migliore risultato rispetto a $p_{12}$ e alle splines lineari (errore come $h^4$ e non $h^2$)
\begin{lstlisting}
>> runge_lin
 	 err: 6.91e-03
>> 
\end{lstlisting} 
\end{frame}








\begin{frame}[fragile]
\frametitle{Esercizio}
\noindent
Un esempio interessante \mye l'approssimazione del cerchio con splines.
Essendo l'equazione del cerchio
\begin{equation}
f(t)=\left(
\begin{array}{c}
\cos(t)\\
\sin(t)
\end{array}
\right)
\end{equation}
per $t=[0,2\,\pi]$. Se
$$t_k= {\frac {2 k \pi} {N} }, \, \, k=0,\ldots,N, $$
l'interpolante spline pu\'o essere facilmente calcolata via il comando
Matlab
{\tt {interp1}} applicato alla coppia di vettori {\tt{t}}, {\tt{u}} e
{\tt{t}}, {\tt{v}} dove al solito $t=(t_k)$, $u=(u(t_k))$, $v=(v(t_k))$.
\end{frame}








\begin{frame}[fragile]
\frametitle{Esercizio}
Per testare il comportamento di tale ricostruzione,
\begin{itemize}
 \item fissati dei nodi test $$t^{\ast}_k= {\frac {2 k \pi} {100} }, \, \, k=0,\ldots,100, $$, si calcolino per $M=10$ le splines $s_x$, $s_y$ lineari (o cubiche not-a-knot) interpolanti le coppie 
$$(t_k,\cos(t_k)), \, t_k= {\frac {2 k \pi} {M} }, \, \, k=0,\ldots,M, $$
$$(t_k,\sin(t_k)), \, t_k= {\frac {2 k \pi} {M} }, \, \, k=0,\ldots,M, $$
\item si plottino le coppie $(s_x(t^{\ast}_k),s_y(t^{\ast}_k))$.
\end{itemize}
Ripetere l'esercizio per $M=100$.


\end{frame}



\end{document}


\begin{frame}[fragile]
\frametitle{Titolo slide}
\begin{lstlisting}
\end{lstlisting}
\end{frame}


\begin{frame}[fragile]
\frametitle{Titolo slide}

 \begin{figure}\label{fig1}
 \centering
   {\includegraphics[scale=0.35,clip]{figura.eps}}
 \caption{Commento ...}
 \end{figure}


\end{lstlisting}
\end{frame}