% 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
% MERCH%ANTABILITY 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[9pt]{beamer}
\input{hal_prefs}
\setlength{\tabcolsep}{2.5pt}
\setbeamertemplate{navigation symbols}{} %no nav symbols
\title[Approssimazione polinomiale \hspace{2em}\insertframenumber/
\inserttotalframenumber]{Approssimazione polinomiale}
\author{Alvise Sommariva}
\institute{Universit\`a degli Studi di Padova\\Dipartimento di Matematica Pura e Applicata}
\date{\today}
\begin{document}
\frame{\titlepage}


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

\begin{problema}
Siano date 
\begin{itemize}
\item le ascisse $x_1 < x_2 < \ldots< x_N$;
\item le ordinate $y_1,\ldots,y_N$.
\end{itemize}

\begin{enumerate}
\item Nel caso dell'interpolazione polinomiale si \'e cercato un polinomio $p_m$ di grado $m=N-1$, tale che $p_m(x_k)=y_k$ per $k=1,\ldots,N$.
\item Nel caso cerchiamo di approssimare questi dati con un polinomio di grado strettamente inferiore a $m$, cosa risulta meglio fare?
\end{enumerate}
\end{problema}

\begin{esempio}
Date le ascisse $$x_1=0,x_2=h,x_3=2 h,\ldots,x_{20}=2 \pi, \smhsp {\mbox{ con }} h=\frac{2 \pi}{19}$$ e i valori $y_k=\sin(x_k)$ con $k=1,\ldots,20$, cercare il polinomio di grado $3$ che meglio approssima (in qualche senso da definire, che diremo poi {\em{ai minimi quadrati}}) i dati.
\end{esempio}


Si noti che nell'esempio, il grado \'e 4 e i punti non sono 5 come nell'interpolazione polinomiale bens\'i 20 ed \'e quindi improbabile soddisfare tutti i vincoli richiesti.


\end{frame}


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

 \begin{figure}[ht!]\label{fig123434543}
 \centering
 {\includegraphics[scale=0.4,clip]{esempio_2020.eps}}
 \caption{ In nero il grafico di $f(x)=\sin(x)$, in rosso un polinomio approssimante (in qualche senso ancora da definire, che sar\'a detto in seguito {\em{ai minimi quadrati}}) di grado $m=4$, in verde le coppie $(x_k,y_k)$, con $y_k=f(x_k)$ per $k=1,\ldots,20$.}
 \end{figure}
\end{frame}





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

\smnsp
\smnsp
{\small{
\begin{vuoto}[Motivazione]
Dato un campionamento $\{(x_i,y_i)\}$, $i=1,2,\ldots,N$, dove $x_i \neq x_j$ se $i \neq j$, nell'approssimazione ai {\purples{minimi quadrati}} si cerca inizialmente un polinomio $${\cal{L}}_m(x)=\sum_{k=0}^m a_k \, x^k=a_0+a_1 \cdot x+ \ldots + a_m x^m$$ di grado {\purples{$m < N$}}, in cui tipicamente $m \ll N$, per cui i coefficienti $a_0, a_1,\ldots,a_m$ risolvano
$$
\left\{
\begin{array}{l}
a_0+a_1 \cdot x_1 +\ldots + a_m \cdot x^m_1= y_1 \\
a_0+a_1 \cdot x_2 +\ldots  + a_m \cdot x^m_2= y_2 \\
\ldots \\
a_0+a_1 \cdot x_N +\ldots +  a_m \cdot x^m_N= y_N \\
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{l}
a_0+a_1 \cdot x_1 +\ldots  a_m \cdot x^m_1- y_1=0 \\
a_0+a_1 \cdot x_2 +\ldots  a_m \cdot x^m_2- y_2=0 \\
\ldots \\
a_0+a_1 \cdot x_N +\ldots  a_m \cdot x^m_N- y_N=0  \\
\end{array}
\right.
$$


Tale problema sovradeterminato (pi\'u equazioni che incognite) pu\'o non avere soluzione. Si nota

\smnsp

$$
\left\{
\begin{array}{l}
a_0+a_1 \cdot x_1 +\ldots  a_m \cdot x^m_1- y_1=0 \\
a_0+a_1 \cdot x_2 +\ldots  a_m \cdot x^m_2- y_2=0 \\
\ldots \\
a_0+a_1 \cdot x_N +\ldots  a_m \cdot x^m_N- y_N=0  \\
\end{array}
\right.
\Leftrightarrow
\left\{
\begin{array}{l}
(a_0+a_1 \cdot x_1 +\ldots  a_m \cdot x^m_1- y_1)^2=0 \\
(a_0+a_1 \cdot x_2 +\ldots  a_m \cdot x^m_2- y_2)^2=0 \\
\ldots \\
(a_0+a_1 \cdot x_N +\ldots  a_m \cdot x^m_N- y_N)^2=0  \\
\end{array}
\right.
$$

$$
\Leftrightarrow
(a_0+a_1 \cdot x_1 +\ldots  a_m \cdot x^m_1- y_1)^2+\ldots+(a_0+a_1 \cdot x_N +\ldots  a_m \cdot x^m_N- y_N)^2=0
$$
Cos\'i si cercano i coefficienti $a_0, a_1,\ldots,a_m$ per cui sia minima (ovvero pi\'u vicina a $0$)

\smnsp
\smnsp

{\reds{
$$
\sum_{i=1}^N (y_i-{\cal{L}}_m(x_i))^2=(a_0+a_1 \cdot x_1 +\ldots  a_m \cdot x^m_1- y_1)^2+\ldots+(a_0+a_1 \cdot x_N +\ldots  a_m \cdot x^m_N- y_N)^2.
$$
}}
\end{vuoto}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale}
{\small{
Quindi, 
\begin{itemize}
\item dato un campionamento $\{(x_i,y_i)\}$, $i=1,2,\ldots,N$, dove $x_i \neq x_j$ se $i \neq j$, 
\item ricordato che se ${\bf{v}}=(v_1,\ldots,v_n)$ allora $\|{\bf{v}}\|_2=\sqrt{\sum_{k=1}^n v^2_k}$,
\end{itemize}
nell'approssimazione ai {\purples{minimi quadrati}} si cerca un polinomio ${\cal{L}}_m(x)=\sum_{k=0}^m a_k \, x^k$ di grado $m < N$, in cui tipicamente $m \ll N$, tale che sia minima 
$$
\sum_{i=1}^N (y_i-{\cal{L}}_m(x_i))^2
$$
o equivalentemente, posto ${\bf{y}}=(y_i)_i$, quando lo \'e 
\begin{eqnarray}
\|{\bf{y}}-({\cal{L}}_m(x_i))_{i=1,\ldots,N}\|_2:&=&\sqrt{\sum_{i=1}^N (y_i-{\cal{L}}_m(x_i))^2} \nonumber \\
&=& \sqrt{ \sum_{i=1}^N (y_i-(a_0+a_1 x_i+\ldots+a_m x_i^m))^2 } \nonumber
\end{eqnarray}
 ovvero che risolva il problema di ottimizzazione in $m+1$ variabili ${\bf{a}}=(a_0,\ldots,a_m)$
{\purples{
\begin{equation}\label{001ls_pre}
\min_{{\bf{a}} \in \R^{m+1}}\sqrt{ \sum_{i=1}^N (y_i-(a_0+a_1 x_i+\ldots+a_m x_i^m))^2 }.
\end{equation}
}}


}}
\end{frame}








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

\begin{teorema}[Esistenza ed unicit\'a]
\begin{enumerate}
\item Se $\{x_k\}_{k=1,\ldots,N}$ sono punti a 2 a 2 distinti, allora l'approssimante ai minimi quadrati di grado $m < N$ delle coppie 
$\{(x_k,y_k)\}_{k=1,\ldots,N}$ esiste ed \'e unica. 

{\vspace{-0.125cm}}

\item Il polinomio ${\cal{L}}_m(x)=\sum_{k=0}^m a^*_k \, x^k$ \mye soluzione ai minimi quadrati se e  solo se, posto ${\bf{y}}=(y_j)$, il vettore ${\bf{a}}=(a^*_i)$   {\purples{risolve}} il sistema delle {\purples{equazioni normali}} 

\smnsp

{\purples{$$\boxed{ V^TV{\bf{a}}=V^T{\bf{y}} }$$}}

\smnsp

dove $V$ \' la matrice di Vandermonde rettangolare di dimensione $N \times (m+1)$ 

$$
V=
\begin{bmatrix} 
1 & x_1 & x^2_1 & \ldots & x^m_1 \\
\ldots & \ldots & \ldots & \ldots & \ldots \\
1 & x_{N-1} & x^2_{N-1} & \ldots & x^m_{N-1} \\
1 & x_N & x^2_N & \ldots & x^m_N
\end{bmatrix} 
$$


\end{enumerate}

\end{teorema}

\begin{nota}

\begin{itemize}
\item La matrice $V^T$ \'e la trasposta della matrice $V$ ovvero $(V^T)_{i,j}=V_{j,i}$.
\item Si noti che $V^T V \in {\mathbb{R}}^{m \times m}$, $V^T y \in {\mathbb{R}}^{m \times 1}$, ovvero il sistema delle equazioni normali \'e di piccole dimensioni visto che tipicamente $m \ll N$.
\end{itemize}

\end{nota}

\end{frame}


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

\begin{dimostrazione}[Facoltativa]

 Sia $V$ la matrice di Vandermonde rettangolare di dimensione $N \times (m+1)$ 

$$
V=
\begin{bmatrix} 
1 & x_1 & x^2_1 & \ldots & x^m_1 \\
\ldots & \ldots & \ldots & \ldots & \ldots \\
1 & x_{N-1} & x^2_{N-1} & \ldots & x^m_{N-1} \\
1 & x_N & x^2_N & \ldots & x^m_N
\end{bmatrix} 
$$


\begin{itemize}
\item Si mostra che {\purples{$V^T V \in {\mathbb{R}}^{(m + 1) \times (m+1)}$}} \mye  {\purples{simmetrica e definita positiva}} (e quindi {\purples{non singolare}} poich\'e tutti gli autovalori $\lambda_i >0$ e quindi $\det(V^TV)=\prod_{i=1}^{m+1} \lambda_i >0$).

{\vspace{-0.1cm}}

\item si vede che il polinomio ${\cal{L}}_m(x)=\sum_{k=0}^m a^*_k \, x^k$ \mye soluzione ai minimi quadrati se e  solo se il vettore ${\bf{a}}=(a^*_i)$   {\purples{risolve}} il sistema delle {\purples{equazioni normali}} 
{\purples{$$\boxed{V^TV{\bf{a}}=V^T{\bf{y}}}$$}}

{\vspace{-0.25cm}}

\noindent per ${\bf{y}}=(y_i)$, ed essendo $V^TV$ non singolare, necessariamente la soluzione ${\bf{a}}$ \mye unica.
\end{itemize}
\end{dimostrazione}


\end{frame}






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

\smnsp


\begin{teorema}[Minimi quadrati qualora $m=N-1$]
Nelle ipotesi fissate, se {\purples{$m=N-1$}} allora la soluzione del problema ai minimi quadrati coincide col polinomio interpolatore le coppie $(x_k,y_k)$, $k=1,\dots,N-1$.
\end{teorema}

{\small{
\begin{traccia}[Facoltativo]
Si osservi che per {\purples{$m=N-1$}}, 
\begin{itemize}
\item la soluzione ai minimi quadrati ${\cal{L}}_m(x)=a^*_0+a^*_1 x_i+\ldots+a^*_m x_i^m$ \'e la soluzione del problema

\smnsp

\begin{equation}\label{001lsd}
0\leq \min_{{\bf{a}} \in \R^{m+1}} \sum_{i=1}^N (y_i-(a_0+a_1 x_i+\ldots+a_m x_i^m))^2;
\end{equation}
\item essendo $m=N-1$ possiamo determinare il polinomio interpolatore 
$p_m(x)={\bar{a}}_0+{\bar{a}}_1 x_i+\ldots+{\bar{a}}_m x_i^m$ e visto che \'e tale che $p_m(x)=y_i$ per $i=1,\ldots,N$ necessariamente
$${\bar{a}}_0+{\bar{a}}_1 x_i+\ldots+{\bar{a}}_m x_i^m=y_i, \qquad i=1,\ldots,N,$$
e quindi 

\bignsp

$$
\sum_{i=1}^N (y_i-({\bar{a}}_0+{\bar{a}}_1 x_i+\ldots+{\bar{a}}_m x_i^m))^2=\sum_{i=1}^N 0^2=0.
$$
\end{itemize}
Di conseguenza, da (\ref{001lsd}), {\purples{per $m=N-1$ si ha che la soluzione ai minimi quadrati ${\cal{L}}_m(x)$ coincide col polinomio $p_m$ di grado $m$ che interpola le coppie $(x_i,y_i)_{i=1,\ldots,N}$}}.
\end{traccia}
}}
\end{frame}









\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale}
\begin{nota}[Storica]

\begin{itemize}

\item Inizialmente la scoperta venne attribuita a Legendre nel 1805 che la pubblic\'o in {\it{Nouvelles m\'ethodes pour la d\'etermination des orbites des com\myesh tes}}, ed era pubblicata in molti manuali gi\'a nel 1870.

\item Gauss, sostenne di aver sviluppato quel metodo gi\'a prima di Legendre, nel 1795. Tale discussione port\'o ad una aspra disputa tra i due noti matematici.

\item In seguito, unendo tali concetti a questioni probabilistiche, Gauss
permise di migliorare il calcolo delle orbite celesti.

\item D'altra parte gi\mya nel 1801 fu in grado di predire (dopo 100 ore di calcoli!) la complicata orbita dell'asteroide Ceres, di cui aveva solo 22 osservazioni dell'astronomo italiano Piazzi (cf. {\blues{\href{https://sites.math.rutgers.edu/\~cherlin/History/Papers1999/weiss.html}{Gauss and Ceres}}}). L'orbita predetta da Gauss era particolarmente diversa da quella suggerita da altri astronomi ma si rivel\'o esatta, rendendolo apprezzato anche al di fuori della matematica.

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





\begin{frame}[fragile]
\frametitle{Minimi quadrati e curve fitting}
\begin{proposito}[Curve fitting e dati inesatti]
\begin{itemize}

\item Forniti i dati ($x_k,y_k$), $k=1,\ldots,N$, lo scopo del {\purples{curve fitting}} degli scopi \mye quello di determinare una funzione $f \in {\cal{F}}$, con ${\cal{F}}$ fissato, tale che $f$ meglio approssimi i dati ($x_k,y_k$), $k=1,\ldots,N$ in qualche senso da definire.

\smsp

{\bf{Esempio}}: posta ${\cal{F}}=\{ f: f(x)=a+b \exp(c \cdot x), \, a,b,c \in {\mathbb{R}} \}$, determinare $a$, $b$, $c$ tali che $f(x)=a+b \exp(c \cdot x)$ meglio approssimi i dati ($x_k,y_k$), $k=1,\ldots,N$ in qualche senso da definire.


\item In questa sezione consideriamo il caso in cui {\purples{${\cal{F}}={\mathbb{P}}_m$}}, ovvero i polinomi di grado al pi\myu $m$, e determiniamo una funzione $f \in {\mathbb{P}}_m$, tale che $f$ meglio approssimi i dati nel senso dei minimi quadrati.

\smsp

\item Nelle scienze applicate capita frequentemente che gli esperimenti producano set di dati $\{(x_i,y_i)\}_{i=1,\ldots,N}$ dove le ascisse sono distinte. 

\smsp

In particolare spesso i valori $y_i$ sono inesatti, ad esempio per errori di misura o approssimazione. Il curve fitting permette in qualche senso di evidenziare una curva, tra un insieme di potenziali candidate, che meglio li approssima, {\purples{filtrando il rumore}}.

\end{itemize}
\end{proposito}
\end{frame}







\begin{frame}[fragile]
\frametitle{Regressione lineare}

\begin{definizione}[Regressione lineare]
Se ${\cal{F}}={\mathbb{P}}_1$, ovvero calcoliamo la soluzione ai minimi quadrati ${\cal{L}}_1$, si parla di {\purples{regressione lineare}}. 
\end{definizione}

\begin{esempio}
Si considerino i dati della seguente tabella

 \begin{table}[h!]\label{tab11}
\begin{center}
\begin{tabular}{| c | c c c c c |}
\hline
$x_i$ & $1$ & $3$ &  $4$ & $6$ & $7$   \\
$y_i$ & $-2.1$ & $-0.9$ &  $-0.6$ & $0.6$ & $0.9$   \\
  \hline
\end{tabular}
\end{center}
\end{table}

Si disegni il grafico della soluzione al problema di regressione lineare.
\end{esempio}
\smsp

I risultati sono evidenziati in figura, dove la retta di regressione \mye quella che {\purples{meglio}} approssima i dati nel senso dei minimi quadrati.
\end{frame}








\begin{frame}[fragile]
\frametitle{Regressione lineare}

 \begin{figure}[ht!]\label{fig11}
 \centering
   %{\includegraphics[scale=0.35,clip]{exreg.eps}}
   {\includegraphics[scale=0.35,clip]{regressione.eps}}
 \caption{Dati e retta di regressione lineare. In questo esempio la soluzione risulta $p_1(x)=0.505263157894737 \cdot x -2.542105263157894$.}
 \end{figure}
\end{frame}



\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale: esempio}
{\small{
\begin{esempio}
Data la tabella 
\begin{center}
\begin{tabular}{|c|c||c|c|}
\hline
1.0 & -1.945 & 2.2 & -0.424 \\
1.2 & -1.253 & 2.4 & -0.012\\
1.4 & -1.140 & 2.6 & -0.190\\
1.6 & -1.087 & 2.8 & +0.452\\
1.8 & -0.760 & 3.0 & +0.337\\
2.0 & -0.682 & 3.2 & +0.764 \\
\hline
\end{tabular}
\end{center} 
calcolare la retta che approssima i dati nel senso dei minimi quadrati.
\end{esempio}
}}

\begin{figure}[ht!]\label{fig123434543}
 \centering
 {\includegraphics[scale=0.25,clip]{regr_01.eps}}

\smnsp 
 
 \caption{In verde i dati di campionamento, in rosso l'approssimante ai minimi quadrati di grado $m=1$ (retta che meglio approssima i punti nel senso dei minimi quadrati).}
 \end{figure}

\end{frame}

\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale: esempio}

\smnsp

{\small{
\begin{nota}
Negli esempi precedenti ovviamente {\purples{non esiste una retta che interpola tutti i punti}}, visto che geometricamente non giacciono su una retta. Valutiamo quanto succede nell'ultimo esempio.

\smsp

Se una tale retta esistesse, allora detta {\purples{$y=a_0+a_1 x$}} la soluzione al problema ai minimi quadrati, avremmo che per ogni coppia $(x_k,y_k)$ della tabella sarebbe $a_0+a_1 x_k=y_k$, $k=1,\ldots,12$ ovvero che sarebbe risolvibile il sistema in $N=2$ incognite e $m=12$ equazioni
$$
\left\{
\begin{array}{l}
a_0+a_1 \cdot 1 = -1.945 \\
a_0+a_1 \cdot 1.2 = -1.253 \\
a_0+a_1 \cdot 1.4 = -1.140 \\
\ldots \\
a_0+a_1 \cdot 3.0 = +0.337 \\
a_0+a_1 \cdot 3.2 = +0.764 \\
\end{array}
\right.
$$
mentre putroppo si verifica facilmente che non ne ha (basta prendere le prime 3 equazioni e notare che non hanno una soluzione comune).

\smsp

Ci\'o nonostante esiste la retta di miglior approssimazione ai minimi quadrati, ovvero il grafico delle coppie $(x,{\cal{L}}_1(x))$, con ${\cal{L}}_1(x)=a_0+a_1 \cdot x$ minimizzante

$$
\sqrt{(a_0+a_1 \cdot 1 - (-1.945))^2 + (a_0+a_1 \cdot 1.2 -( -1.253))^2 + \ldots +  (a_0+a_1 \cdot 3.2 -0.764)^2}
$$

Si calcola numericamente che 
$$
{\cal{L}}_1(x) \approx -2.780034965034965+1.088111888111888\cdot x.
$$
\end{nota}
}}
\end{frame}



\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale e dati inesatti}

In alcuni problemi, i dati sono soggetti a rumore e uno vuole in qualche senso {\purples{togliere il rumore}}. 

\begin{esempio}
Consideriamo quali dati $(x_i,y_i)_{i=1,\ldots,40}$ in cui
\begin{itemize}
\item  $x_i=-1+ (i-1) \cdot \frac{2}{39} \in [-1,1]$,
\item $y_i=\sin(10 \cdot x_i)+10^{-3} \mu_i$ 
\end{itemize}
dove $\mu_i$ \mye un numero random in $[-0.5,0.5]$. 

\smsp

Determinare il polinomio di miglior approssimazione per $m=5,10,15,30$ e vedere come approssima $f^*(x)=\sin(10 \cdot x)$.
\end{esempio}

In qualche modo simuliamo dei dati $y^*_i=\sin(x_i)$ cui abbiamo aggiunto il rumore $10^{-3} \mu_i$.
\begin{itemize}
\item L'intento \mye approssimare la funzione $f^*(x)=\sin(10 x)$ {\purples{togliendo}} il rumore. 
\item {\purples{Non ha senso calcolare l'interpolante polinomiale}}, perche' si riprodurrebbero i rumori e non la funzione cercata.
\end{itemize}

In figura, mostriamo i risultati ottenuti utilizzando le approssimanti ${\cal{L}}_m$ ai minimi quadrati di grado rispettivamente $m=5$, $m=10$, {\purples{$m=15$}}, $m=30$.
\end{frame}


\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale e dati inesatti}

 \begin{figure}[ht!]\label{fig12}
 \centering
 {\includegraphics[scale=0.25,clip]{esempio_rumore.eps}}
   {\includegraphics[scale=0.25,clip]{esempio_rumore_zoom.eps}}
 \caption{Figura a sinistra. Funzione $f^*(x)=\sin(10 \cdot x)$ e i campionamenti inesatti.

\smsp

Figura a destra. Funzione $f^*(x)=\sin(10 \cdot x)$ in un intorno di $x=-0.128$ e dato inesatto.

\smsp

Le pendenze non coincidono per la grafica di Matlab.

 }
 \end{figure}
\end{frame}


\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale e dati inesatti}

 \begin{figure}[ht!]\label{fig12}
 \centering
 {\includegraphics[scale=0.25,clip]{esempio_5.eps}}
   {\includegraphics[scale=0.25,clip]{esempio_10.eps}}
   {\includegraphics[scale=0.25,clip]{esempio_15.eps}}
   {\includegraphics[scale=0.25,clip]{esempio_30.eps}}
 \caption{Dati inesatti (in {\bf{\greens{verde}}}) e in {\bf{\reds{rosso}}} approssimanti ai minimi quadrati di grado $m=5$, $m=10$, $m=15$, $m=30$. In {\bf{nero}} $f(x)=\sin(10x)$. }
 \end{figure}
\end{frame}


\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale e dati inesatti}
 \begin{figure}[ht!]\label{fig12B}
 \centering
 {\includegraphics[scale=0.4,clip]{errore_rumore.eps}
 \caption{Rappresentazione grafica di $E_m(x)=|p_m(x)-f(x)|$, dove $p_m$ \'e l'approssimante di grado $m=5$, $m=10$, $m=15$, $m=30$ (in blu) nel ricostruire $f^*(x)=\sin(10 \cdot x)$, noti dati inesatti.}}
 \end{figure}
\end{frame}













\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale e dati inesatti}
\begin{itemize}
\item In virt\myu dei $6$ cambi di convessit\mya / concavit\mya della funzione $f^*$, \mye chiaro che un {\purples{polinomio di grado basso non fornisca risultati apprezzabili}}. 

Ad esempio un polinomio di grado $5$ pu\myo avere al pi\myu $4$ cambi di convessit\mya / concavit\myash, e non pu\myo essere adatto allo scopo. 
\item Un polinomio ${\cal{L}}_m$ di {\purples{grado $m$ troppo alto approssimerebbe la funzione con rumore}} e non $f^*$. 
\item Nel nostro esempio, $m=15$ sembra essere un {\purples{buon compromesso}}.
\item Si noti come a grado $m=30$ comincino a sorgere oscillazioni agli estremi. Inoltre per problemi dovuti a {\tt{polyfit}}, il risultato non \mye quello corretto teoricamente.
\end{itemize}



\smsp

La tabella che segue, mostra gli errori
$$E_m(f^*)=\max_{x \in [-1,1]} |f^*(x)-{\cal{L}}_m(x)|, \smhsp E_m({\bf{y}})=\sum_{i=1}^{40} |y_i-{\cal{L}}_m(x_i)|^2,$$
con ${\bf{y}}=(y_i)_i$ vettore dei dati perturbati, evidenziando un miglioramento di entrambe fino a grado $m=20$ e un peggioramento nell'approssimare la funzione {\purples{senza rumore}} $f^*$ pur approssimando sempre meglio i dati (nel senso dei minimi quadrati). 

\end{frame}











\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale e dati inesatti}
 \begin{table}[h!]\label{34}
\begin{center}
\begin{tabular}{| c c  c |}
\hline
$m$&   $E_m(f^*)$ & $E_m({\bf{y}})$  \\
\hline
 	 $  5$ & $1.2e+00$ & $4.0e+00$ \\
 	 $ 10$ & $3.3e-01$ & $1.2e+00$ \\
 	 $ 15$ & $4.0e-03$ & $5.1e-03$ \\
 	 $ 20$ & $5.7e-03$ & $2.3e-03$ \\
 	 $ 25$ & $3.6e-02$ & $2.2e-03$ \\
 	 $ 30$ & $1.7e+00$ & $1.8e-03$ \\
  \hline
\end{tabular}
\caption{Grado $m$ ed errori 

\smsp

$\bullet \smhsp E_m(f^*)=\max_{x \in [-1,1]} |f^*(x)-{\cal{L}}_m(x)|$, 

\smsp

$\bullet \smhsp  E_m({\bf{y}})=\sum_{i=1}^{40} |y_i-{\cal{L}}_m(x_i)|^2$, 

\smsp

dove $f^*(x)=\sin(10 x)$, ${\bf{y}}=(y_i)_i$ con $y_i=f^*(x_i)+10^{-3}$. 

\smsp

Il valore $E_m(f^*)$ evidenzia un valore ottimo $m=15$ nell'approssimare la funzione $f^*$ non affetta da rumore. 

\smsp

Il valore $E_m({\bf{y}})$, come atteso, mostra un costante miglioramento nell'approssimare i dati affetti da rumore. }
\end{center}


\end{table}
\end{frame}






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

\begin{center}
{\Huge{Appendice facoltativa}}
\end{center}

\end{frame}



\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale: convergenza uniforme e minimi quadrati}

\begin{teorema}[Qualit\'a dell'approssimazione, (punti equispaziati)]
Sia ${\cal{L}}_m$ \mye la miglior approssimante polinomiale ai minimi quadrati di grado $m > 0$, relativamente alle coppie
$$(x_1,f(x_1)), (x_2,f(x_2)), \ldots, (x_{N_m},f(x_{N_m}))$$
con
\begin{itemize} 
\item {\purples{$x_j=a+(j-1) h$}}, in cui $j=1,\ldots,N_m$, $h=\frac{b-a}{N_m-1}$
\item {\purples{$N_m \geq 2m^2+1$}}.
\end{itemize} 

\smsp

Se {\purples{$f \in C^k([a,b])$}}, $k > 1$, allora esiste una costante $c_k$, indipendente da $m$, per cui

{\purples{
$$
\|{\cal{L}}_m-f\|_{\infty}=\max_{x \in [a,b]} |{\cal{L}}_m(x)-f(x)| \leq c_k m^{1-k}= c_k. {\frac{1}{m^{k-1}}}
$$
}}

\end{teorema}

\begin{itemize}
\item Il teorema dice che nelle condizioni fissate, pi\'u la funzione \'e {\purples{regolare}} e pi\'u \'e {\it{lecito}} aspettarsi un errore pi\'u piccolo (ammesso $c_k$ non cresca troppo).
\item Si noti che nelle ipotesi indicate, per il teorema dei due carabinieri, per $n \rightarrow \infty$ la successione di polinomi ${\cal{L}}_m$ {\purples{converge uniformemente}} a $f$.
\end{itemize}
\end{frame}


\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale: convergenza uniforme e minimi quadrati}

\smnsp

\begin{esempio}
Calcolare le approssimazioni ${\cal{L}}_m$ ai minimi quadrati delle funzioni
\begin{enumerate}
\item $f_1(x)=x^{30} \in C^{\infty}([0,1])$,
\item $f_2(x)=x^{7/2}\in C^{3}([0,1])$,
\item $f_3(x)=\exp(x)\in C^{\infty}([0,1])$.
\end{enumerate}
in $N_m=2m^2+1$ nodi equispaziati, con $m=1,2,\ldots,9,10,15,20$.

\smsp

Verificare {\purples{numericamente}} la convergenza uniforme di ${\cal{L}}_m$ a $f$, al crescere di $m$.
\end{esempio}

\smsp

Come richiesto, al variare di $m$, sceglieremo $N_m=2m^2+1$, ovvero quali ascisse di campionamento $${\purples{x_k=a+kh}}, {\mbox{ con }} \, k=1,\ldots,N_m$$ dove $$ {\purples{h}}=\frac{b-a}{n_m-1}=\frac{1}{2m^2+1-1}={\purples{\frac{1}{2m^2}}}.$$
\end{frame}




\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale: esempi}

\begin{itemize}
\item Il calcolo della soluzione ai minimi quadrati viene eseguito utilizzando la funzione Matlab {\purples{\tt{polyfit}}};
\item se le ordinate sono valutazioni di una funzione $f$ nei punti $x_1<\ldots<x_N$, ovvero $y_k=f(x_k)$, negli esperimenti che seguono, per avere una stima dell'errore commesso 
$$E_m(f)=\|{\cal{L}}_m-f\|_{\infty} =\max_{x \in [0,1]} |{\cal{L}}_m(x)-f(x)|,$$
lo valutiamo in una discretizzazione $ \Delta$ {\it{sufficientemente fitta}} di $[0,1]$, ovvero $$ \Delta=\{x_j=(j-1)/9999, \,\,\,k=1,\ldots,10000\},$$ 
ottenendo
$$E^*_m(f)=\max_{x_j \in \Delta}|{\cal{L}}_m(x_j)-f(x_j)| \approx \max_{x \in [0,1]} |{\cal{L}}_m(x)-f(x)|=  E_m(f).$$
\end{itemize}

\end{frame}



\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale: esempi}

I risultati sono rappresentati in tabella. 

\smsp

Si noti che
\begin{itemize}
\item Visto che $f_1(x)=x^{30}  \in C^{\infty}([0,1])$ ci aspettiamo che per $m\geq 30$, poich\'e $f_1$ \'e un polinomio di grado $30$, sia in aritmetica esatta 
${\cal{L}}_m=f_1$. Quindi per $m \geq 30$ ci aspettiamo un errore $E^*_m(f)=\max_{x \in [0,1]} |{\cal{L}}_m(x)-f_1(x)|$  nullo.
\item Visto che $f_2(x)=x^{7/2} \in C^3([0,1])$ ci aspettiamo dalle stime teoriche del teorema precedente una {\purples{convergenza non troppo rapida}}.
\item Visto che $f_3(x)=\exp(x) \in C^{\infty}([0,1])$ ci aspettiamo  dalle stime teoriche del teorema precedente una {\purples{convergenza molto rapida}}.
\end{itemize}






\end{frame}





\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale}
 \begin{table}[h!]
\begin{center}
\begin{tabular}{| c | c  c c | c |}
\hline
$m$&   $E^*_m(f_1)$ & $E^*_m(f_2)$&   $E^*_m(f_3)$  & $N_m$ \\
\hline
  	  $  1$& $6.9e-01$ & $3.0e-01$ & $1.4e-01$  & $         3$ \\
 	 $  2$& $4.0e-01$ & $5.2e-02$ & $9.6e-03$  & $         9$ \\
 	 $  3$& $3.4e-01$ & $4.3e-03$ & $7.3e-04$  & $        19$ \\
 	 $  4$& $2.8e-01$ & $3.2e-04$ & $4.1e-05$  & $        33$ \\
 	 $  5$& $2.1e-01$ & $6.2e-05$ & $1.9e-06$  & $        51$ \\
 	 $  6$& $1.4e-01$ & $1.7e-05$ & $7.3e-08$  & $        73$ \\
 	 $  7$& $8.6e-02$ & $6.1e-06$ & $2.5e-09$  & $        99$ \\
 	 $  8$& $4.9e-02$ & $2.5e-06$ & $7.2e-11$  & $       129$ \\
 	 $  9$& $2.6e-02$ & $1.1e-06$ & $1.9e-12$  & $       163$ \\
 	 $ 10$& $1.3e-02$ & $5.6e-07$ & $4.5e-14$  & $       201$ \\
 	 %$ 11$& $5.8e-03$ & $3.0e-07$ & $1.8e-15$  & $       243$ \\
 	 %$ 12$& $2.5e-03$ & $1.7e-07$ & $8.9e-16$  & $       289$ \\
 	 %$ 13$& $9.5e-04$ & $9.7e-08$ & $4.4e-16$  & $       339$ \\
 	 %$ 14$& $3.4e-04$ & $5.9e-08$ & $1.3e-15$  & $       393$ \\
 	 $ 15$& $1.1e-04$ & $3.7e-08$ & $2.0e-15$  & $       451$ \\
 	 %$ 16$& $3.3e-05$ & $2.4e-08$ & $2.0e-15$  & $       513$ \\
 	 %$ 17$& $9.0e-06$ & $1.6e-08$ & $1.3e-15$  & $       579$ \\
 	 %$ 18$& $2.2e-06$ & $1.1e-08$ & $1.8e-15$  & $       649$ \\
 	 %$ 19$& $4.9e-07$ & $7.6e-09$ & $2.7e-15$  & $       723$ \\
 	 $ 20$& $9.4e-08$ & $5.4e-09$ & $1.8e-15$  & $       801$ \\
  \hline
\end{tabular}
\caption{Nella tabella indichiamo il grado $m=1,\ldots,10,15,20$, gli errori compiuti dalle approssimazioni ai minimi quadrati $E^*_m(f_1),E^*_m(f_2),E^*_m(f_3)$ e il numero di punti di campionamento. Non deve sorprendere la {\purples{prima colonna}}, visto che stiamo approssimando un polinomio di grado $30$ con altri di grado minore. Si ricordi che $f_1(x)=x^{30}$, $f_2(x)=x^{7/2}$, $f_3(x)=\exp(x)$, $x \in [0,1]$.}
\end{center}
\end{table}


\end{frame}
















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

\smnsp
{\small{
\begin{teorema}[Errore approssimante ai minimi quadrati su opportuni campionamenti]
Se ${\cal{L}}_m$ \mye la miglior approssimante polinomiale di grado $m > 0$, relativamente alle coppie
$(x_1,f(x_1))$, $(x_2,f(x_2))$, $\ldots$, $(x_N,f(x_N))$ con $a \leq x_1 <\ldots < x_N \leq b$ e
\begin{itemize}
\item ${\purples{h_m}}=\max_{i=1,\ldots,N-1}(x_{i+1}-x_i) {\purples{\leq \theta (b-a)/m^2}}$, 
\item ${\purples{\theta \in (0,1)}}$ (indipendente da $m$), 
\end{itemize}
allora per ogni {\purples{$f \in C^k([a,b])$}}, $k > 1$, esiste una costante $c_k$, indipendente da $m$, per cui

\smnsp

{\purples{
$$
\max_{x \in [a,b]} |{\cal{L}}_m(x)-f(x)| \leq c_k m^{1-k}.
$$
}}
\end{teorema}



\begin{corollario}[Punti equispaziati]
Se ${\cal{L}}_m$ \mye la miglior approssimante polinomiale di grado $m > 0$, relativamente alle coppie
$(x_1,f(x_1))$, $(x_2,f(x_2))$, $\ldots$, $(x_{N_m},f(x_{N_m}))$ con
\begin{itemize} 
\item $x_j=a+(j-1) \frac{b-a}{N_m-1}$, $j=1,\ldots,N_m$, 
\item {\purples{$N_m \geq 2m^2+1$}}.
\end{itemize} 
Allora per ogni {\purples{$f \in C^k([a,b])$}}, $k > 1$, esiste una costante $c_k$, indipendente da $m$, per cui

\smnsp

{\purples{
$$
\|{\cal{L}}_m-f\|_{\inf}=\max_{x \in [a,b]} |{\cal{L}}_m(x)-f(x)| \leq c_k m^{1-k}.
$$
}}

\end{corollario}
}}


\end{frame}








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

{\small{
\begin{esempio}
Sia $f \in C^{\purples{5}}([a,b])$ (ovvero ${\purples{k=5}}$ nel corollario precedente). Se disponiamo dei dati  $\{(x_{k},f(x_{k}))\}_{k=1,\ldots,N_m}$ con $N_m \geq 2 m^2+ 1$, sappiamo che $ \|{\cal{L}}_m(x)-f\|_{\inf} \leq c_k m^{1-k}$.

\smsp

{\purples{(a)}} Supponiamo 
\begin{itemize} 
\item di disporre di ${\purples{N_m=20}}$ punti equispaziati $\{x_k\}_{k=1,\ldots,20}$ in $[a,b]$,
\item di calcolare l'approssimante ${\cal{L}}_3$ ai minimi quadrati delle coppie $(x_k,f(x_k))$, $k=1,\ldots,20$, ovvero ${\purples{m=3}}$ nel corollario precedente.
\end{itemize}
Essendo $20={\purples{N_m \geq 2 m^2+ 1}} =19$, risulta
$$
\max_{x \in [a,b]} |{\cal{L}}_m(x)-f(x)| \leq c_k m^{1-k}=c_k 3^{1-5}=\frac{c_k}{81}.
$$ 

{\purples{(b)}} Supponiamo 
\begin{itemize} 
\item di disporre di ${\purples{N_m=300}}$ punti equispaziati $\{x_k\}_{k=1,\ldots,300}$ in $[a,b]$,
\item di calcolare l'approssimante ${\cal{L}}_{10}$ ai minimi quadrati delle coppie $(x_k,f(x_k))$, $k=1,\ldots,300$, ovvero ${\purples{m=10}}$ nel corollario precedente.
\end{itemize}
Essendo $300={\purples{N_m \geq 2 m^2+ 1}} =201$, risulta
$$
\max_{x \in [a,b]} |{\cal{L}}_m(x)-f(x)| \leq c_k m^{1-k}=c_k 10^{1-5}=\frac{c_k}{10^4}.
$$ 
\end{esempio}
}}

\end{frame}











\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale}
\begin{commento}[]
\begin{itemize}
\item Il teorema asserisce che la soluzione ai minimi quadrati ${\cal{L}}_m$ di grado $m$, su un {\purples{set di nodi sufficientemente fitti}} (ovvero l'intervallo di ampiezza maggiore \'e sufficientemente piccolo), dar\'a
\begin{itemize} 
\item [(a)] {\purples{uniformemente}} una buona approssimazione della funzione $f$ da approssimare, 
\item [(b)] tendenzialmente {\purples{migliore se la funzione \mye molto regolare}} vista la presenza di $m^{1-k}$, supponendo $c_k$ non cresca troppo.
\end{itemize} 
\item Non dice molto del valore della costante $c_k$, e quindi il termine $c_k m^{1-k}$ non \mye direttamente valutabile.

\item Al crescere di $m$, il fattore $c_k m^{1-k} \rightarrow 0$ e quindi per set di nodi $\{x_k\}_{k=1}^{N}$ sufficientementi fitti, la successione $\{{\cal{L}}_m\}_m$ converge uniformente a $f \in C^{k}([a,b])$, qualora sia $k>1$.

\end{itemize}
\end{commento}

\end{frame}








\begin{frame}[fragile]
\frametitle{Approssimazione polinomiale}
{\small{
\begin{esempio}[. Minimi quadrati e set di nodi equispaziati suff. fitti]
Supponiamo che al variare di $m$, si calcoli l'approssimante polinomiale ${\cal{L}}_m$ delle coppie $(x_k,f(x_k))_{k=1,\ldots,N_m}$, in cui
\begin{itemize}
\item $f \in C^{k}([a,b])$, $k > 1$;
\item $x_j=a+(b-a)\cdot \frac{j-1}{N_m-1}$ con $j=1,\ldots,N_m=2m^2+1$, ovvero $N_m$ punti equispaziati in $[a,b]$, con passo $h_m=\frac{b-a}{N_m-1}$.
\end{itemize}
In virt\'u del precedente corollario si ha
\begin{equation}\label{234234}
0\leq \max_{x \in [a,b]} |{\cal{L}}_m(x)-f(x)| \leq c_k m^{1-k}.
\end{equation}
Se si considera in particolare una sequenza di approssimazioni $\{{\cal{L}}_m\}_{m=1,2,\ldots}$ con queste proprieta', allora da (\ref{234234}) abbiamo che per il teorema del confronto $$\lim_{m \rightarrow +\infty}\|{\cal{L}}_m-f\|_{\infty}=\lim_{m \rightarrow +\infty} \max_{x \in [a,b]} |{\cal{L}}_m(x)-f(x)| =0,$$
ovvero {\purples{la successione di polinomi $\{{\cal{L}}_m\}_{m=1,2,\ldots}$ converge uniformemente a $f$ in $[a,b]$}}.
\end{esempio}
}}
\end{frame}










\end{document}

 \begin{figure}[ht!]\label{fig1aaaahjtfty}
 \centering
   {\includegraphics[scale=0.2725,clip]{....eps}}
 \caption{...}
 \end{figure}


 \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$ \\
  \hline
\end{tabular}
\caption{....}
\end{center}
\end{table}

