 %% 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[Numeri macchina \hspace{2em}\insertframenumber/
\inserttotalframenumber]{Numeri macchina e propagazione degli errori}
\author{Alvise Sommariva}
\institute{Universit\`a degli Studi di Padova}
\date{\today}
\begin{document}
\frame{\titlepage}
\begin{frame}[fragile]
\frametitle{Numeri macchina e loro propriet\mya}

\begin{vuoto}[Rappresentazione floating point dei numeri reali]
Fissato un numero naturale $\beta > 1$ \mye possibile vedere che ogni numero reale $x \neq 0$ ha una unica rappresentazione del tipo
{\purples{
\begin{equation}\label{E1}
x=\sgn(x)  \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}, \hspace{0.3cm} 0 < d_1 , \, 0\leq d_k \leq \beta-1, \, e\in{\mathbb{Z}}
\end{equation}
}}
dove 
$$\sgn(y)=\left\{ \begin{array}{l}1, \hspace{0.575cm} y > 0 \\ -1, \hspace{0.3cm} y <0 \\ 0, \hspace{0.575cm} y = 0.  \end{array} \right.$$
\mye la funzione segno.
\end{vuoto}
\end{frame}



\begin{frame}[fragile]
\frametitle{Numeri macchina e loro propriet\mya}

\begin{esempio}[Base binaria e decimale]
Casi particolari di 
{\purples{
\begin{equation}\label{E1a}
x=\sgn(x)  \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}, \hspace{0.3cm} 0 < d_1 , \, 0\leq d_k \leq \beta-1, \, e\in{\mathbb{Z}}
\end{equation}
}}

\begin{itemize}
\item in base $2$ (detta anche {\purples{base binaria}}, usato nello standard IEEE 754-1985),
$$
x=\sgn(x) \cdot  2^e  \sum_{k=1}^{+\infty} d_k \cdot 2^{-k}, \hspace{0.3cm}  d_1=1 , \, d_k=0,1, \, e\in{\mathbb{Z}}
$$
\item in base $10$ (detta anche {\purples{base decimale}}, usata nella vita quotidiana),
$$
x=\sgn(x)  \cdot 10^e  \sum_{k=1}^{+\infty} d_k \cdot 10^{-k}, \hspace{0.3cm}  d_1=1,\ldots,9, \, d_k=0,\ldots,9, \, e\in{\mathbb{Z}}
$$
\end{itemize}
\end{esempio}
\end{frame}





\begin{frame}[fragile]
\frametitle{Numeri macchina e loro propriet\mya: esempio 1.}
\begin{esempio}
Rappresentare il numero 
$$
\pi=3,14159 26535 89793 238 \ldots
$$
nella forma 
$$\sgn(\pi)  \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}, \hspace{0.3cm} 0 < d_1 , \, 0\leq d_k \leq \beta-1, \, e\in{\mathbb{Z}}$$
per $\beta=10$ e $\beta=2$.
\end{esempio}




\end{frame}





\begin{frame}[fragile]
\frametitle{Numeri macchina e loro propriet\mya: esempio 1.}

\begin{vuoto}
{\bf{Base 10}}: $3,14159 26535 89793 238 \ldots$ secondo la rappresentazione $$\sgn(\pi)  \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}, \hspace{0.3cm} 0 < d_1 , \, 0\leq d_k \leq \beta-1, \, e\in{\mathbb{Z}}$$
risulta
$$
+1 \cdot 10^1 \cdot (3 \cdot 10^{-1} + 1  \cdot 10^{-2} + 4 \cdot 10^{-3} + \ldots)
$$
che viene spesso denotato come
$$
\pi=(+1) \cdot (0.314159 26535 89793 238 \ldots)_{10} \cdot 10^1;
$$

{\bf{Base 2}}: il numero $\pi$, si scrive come
{\footnotesize{
$$
+1  \cdot 2^2 \cdot (1 \cdot 2^{-1} + 1  \cdot 2^{-2} + 0 \cdot 2^{-3}  + 0 \cdot 2^{-4} \ldots )=+4(1/2+1/4+\ldots),
$$
}}
che viene spesso denotato come
$$
\pi=(+1) \cdot (0.110010010000111111011010101000100010000101 \ldots)_2 \cdot 2^2.
$$
\end{vuoto}
\end{frame}



\begin{frame}[fragile]
\frametitle{Numeri macchina e loro propriet\mya: esempio 2.}
\begin{esempio}
Rappresentare il numero 
$$
\exp(10)=22026.46579480671789497137 \ldots
$$
nella forma 
$$\sgn(\exp(10))  \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}, \hspace{0.3cm} 0 < d_1 , \, 0\leq d_k \leq \beta-1, \, e\in{\mathbb{Z}}$$
per $\beta=10$.
\end{esempio}

Per quanto visto
\begin{eqnarray}
\exp(10) &=& (+1) \cdot 10^5 \cdot (2\cdot 10^{-1}+2\cdot  10^{-2}+0 \cdot 10^{-3}+ 2 \cdot 10^{-4}+ \ldots). \nonumber \\
&=& (+1) \cdot 10^5 \cdot (0.2202646579480671789497137 \ldots)_{10} \nonumber
\end{eqnarray}



\end{frame}



\begin{frame}[fragile]
\frametitle{Numeri macchina e loro propriet\mya}
La particolarit\mya della sommatoria in (\ref{E1}), ovvero
\begin{equation}\label{E1R}
x=\sgn(x)  \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}, \hspace{0.3cm} 0 < d_1 , \, 0\leq d_k \leq \beta-1, \, e\in{\mathbb{Z}}
\end{equation}
 \mye ovviamente tale che $x$ potrebbe essere non rappresentabile esattamente dal calcolatore se esistono infiniti $d_k >0$, in quanto {\purples{il calcolatore \mye capace di immagazzinare solo un numero finito di tali $d_k$}}. 
 
 \smsp
 
 Ad esempio, non \mye difficile vedere che:
\begin{itemize}
\item {\purples{i numeri irrazionali}} come $\pi$, indipendentemente dalla base $\beta$, hanno sempre un {\underline{numero infinito di cifre $d_k$}};
\item in base $10$ {\purples{alcuni numeri razionali}} hanno un  numero {\underline{infinito}} di cifre $d_k$ (si pensi ai numeri periodici come $1/3=0.333\ldots$), ma comunque in certe basi possono avere una rappresentazione finita (nel nostro esempio $1/3=1 \cdot 3^{-1}$ per $\beta=3$).
\end{itemize}

\end{frame}


\begin{frame}[fragile]
\frametitle{Numeri floating point}

\smnsp

\begin{definizione}[Numeri macchina]
L'{\blues{{\href{https://it.wikipedia.org/wiki/Numero\_in\_virgola\_mobile}{insieme dei numeri macchina}}}} {\purples{$F(\beta,t,L,U)$}} di $\mathbb{R}$ \mye costituito da quei numeri $y$ che sono $0$ oppure sono rappresentati con il {\it{sistema a virgola mobile normalizzata o floating point normalizzato}} da 

\smnsp

$$y=\sgn(y) \cdot {\overbrace{(0.d_1 \ldots d_t)_{\beta}}^{\mbox{\tiny{mantissa}}}} \beta^e= \sgn(y) \cdot \beta^e \sum_{k=1}^{t} d_k \beta^{-k}, \hspace{0.3cm} d_1 >0, $$

\smnsp

con $0\leq d_k \leq \beta-1$ dove

\begin{itemize}
\item $\beta > 1$ numero naturale detto {\it{base}}, $t$ numero prefissato di cifre di {\purples{mantissa}},  
\item $e \in \mathbb{Z}$ l'{\purples{esponente}} intero tale che $L \leq e \leq U$. 
\end{itemize}

\begin{enumerate}
\item La parola {\purples{normalizzato}} sottolinea che $d_1 > 0$ e comporta l'unicit\'a della rappresentazione.
\item Ogni elemento di $F(\beta,t,L,U)$ \mye detto {\purples{numero macchina}}.
\item Ogni numero macchina \'e {\purples{razionale}}.
\item Si pu\myo provare che $\sum_{k=1}^{t} d_k \beta^{-k}<1$ e quindi {\purples{$e={\tt{floor}}(1+{\log_{\beta}}(y))$}}.
\end{enumerate}
\end{definizione}

\end{frame}


\begin{frame}[fragile]
\frametitle{Numeri floating point}

\smnsp
Osserviamo che se $e > 0$ allora 
\begin{eqnarray}
y&=&\sgn(y) \cdot (0.d_1 \ldots d_t)_{\beta} \beta^e= \sgn(y) \cdot \beta^e \sum_{k=1}^{t} d_k \beta^{-k} \nonumber \\
&=&\sgn(y) \cdot ( \underbrace{\sum_{k=1}^{e} d_k \beta^{e-k}}_{\mbox{parte intera}} +\underbrace{ \sum_{k=e+1}^{t} d_k \beta^{e-k})}_{\mbox{parte frazionaria}} \nonumber
\end{eqnarray}
dove l'ultima somma \mye nulla per definizione se $t < e+1$.

\smsp

In altri termini, se $e >0$, {\purples{le prime "e" cifre determinano la parte intera, le altre la parte frazionaria}}.

\begin{nota}
{\footnotesize{
Si noti che la parte intera ha potenze non negative di $\beta$ e quindi effettivamente \mye un numero naturale, mentre la parte frazionaria \mye somma di potenze negative di $\beta$, che si mostra con un po' di tecnica essere un numero in $[0,1)$.
}}
\end{nota}

\end{frame}


\begin{frame}[fragile]
\frametitle{Numeri floating point}

\smnsp

\begin{esempio}
Con riferimento a
\begin{eqnarray}
\exp(10)= (+1) \cdot 10^5 \cdot (0.2202646579480671789497137)_{10}. \nonumber
\end{eqnarray}

visto che $e=5 >0$, le prime 5 cifre della mantissa sono relative alla parte intera, le altre alla parte frazionaria.

In effetti
$$
\exp(10)=22026.46579480671789497137 \ldots
$$

\end{esempio}
\begin{nota}
Si osservi che il sistema floating-point \mye solo una delle scelte possibili, in quanto una volta si utilizzava un sistema a {\purples{virgola fissa}}, ovvero con un {\purples{numero fissato di cifre prima della virgola e un certo numero di cifre dopo la virgola}}, abbandonato (nonostante presentasse alcuni vantaggi) perch\mye l'intervallo di valori rappresentati \mye modesto e la precisione dei numeri frazionari scarsa.
\end{nota}

\end{frame}


\begin{frame}[fragile]
\frametitle{Numeri floating point}

Di ogni numero macchina $x$

$$x=\sgn(x) \cdot {\overbrace{(0.d_1 \ldots d_t)_{\beta}}^{\mbox{\tiny{mantissa}}}} \beta^e= \sgn(x) \cdot \beta^e \sum_{k=1}^{t} d_k \beta^{-k}, \hspace{0.3cm} d_1 >0, $$

\noindent
si immagazzinano

\vspace{0.3cm}

\begin{itemize}
\item una cifra per il segno (ovvero $0$ per positivo e $1$ per negativo), 
\item le cifre dell'esponente, diciamo $m$,
\item le cifre della mantissa, diciamo $t$.
\end{itemize}

\begin{center}
\begin{tabular}[h!]{| c | c | c |}
\hline
${\mbox{segno}}$ & ${\mbox{esponente}}$ & ${\mbox{mantissa}}$ \\
\hline
$1 {\mbox{ cifra}}$ & $m {\mbox{ cifre}}$ & $t {\mbox{ cifre}}$ \\
\hline
\end{tabular}
\end{center}

\vspace{0.3cm}

\begin{itemize}
\item Ognuna di queste cifre \mye detta {\purples{bit}}. 
\item Ogni numero \mye registrato in un vettore detto {\purples{parola}} di un certo numero di $M$ {\purples{bits}}. 
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Numeri floating point}

\begin{nota}
Nella notazione binaria normalizzata, immagazzinate le cifre $(1,d_1,\ldots,d_{t-1})_{\beta}$ e l'esponente "$e$", a volte si intende

\smnsp

\begin{eqnarray}
y&=&\sgn(y) \cdot (1.d_2 \ldots d_{t})_{\beta} \beta^e= \sgn(y) \cdot \beta^e(1+ \sum_{k=2}^{t} d_k \beta^{-k}) 
\end{eqnarray}

\smnsp

e non come in precedenza

\smnsp

\begin{eqnarray}\label{nots}
y&=&\sgn(y) \cdot (1.d_1 \ldots d_{t-1})_{\beta} \beta^e \nonumber \\ 
&=& \sgn(y) \cdot \beta^e(\beta^{-1}+\sum_{k=2}^{t} d_{k-1} \beta^{-k}).
\end{eqnarray}

Questo potenzialmente pu\myo creare qualche confusione. Scegliamo di utilizzare (\ref{nots}) perch\mye pi\myu frequente nei manuali di analisi numerica.
\end{nota}
\end{frame}

\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$}

Vediamo di seguito, alcune propriet\'a di $F(\beta,t,L,U)$.

\vspace{0.25cm}

\begin{proposizione}
Il {\underline{pi\'u piccolo}} numero macchina positivo (normalizzato) \'e {\purples{$\beta^{L-1}$}}.
\end{proposizione}

%\vspace{0.25cm}

\begin{proof} 
Ricordiamo che un generico numero macchina $x$ \'e
$$
x=\sgn(x) \beta^e \sum_{k=1}^{t} d_k \beta^{-k}, \, d_1 > 0, L \leq e \leq U. 
$$
Ponendo $d_1=1$, $d_2=\ldots=d_{t}=0$ ed $e=L$, otteniamo che il pi\myu piccolo numero macchina (e quindi normalizzato!) positivo rappresentabile \mye 
$$
x^*=\beta^L (1 \cdot \beta^{-1}+\sum_{k=2}^{t} 0 \cdot \beta^{-k})=\beta^{L-1}.
$$

\smnsp

\end{proof} 

\end{frame}


\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$}

\smnsp

\begin{proposizione}
La {\underline{somma relativa alla mantissa}}, cio\mye {\purples{$\sum_{k=1}^{t} d_k \beta^{-k}$}}, appartiene all'intervallo {\purples{$(0, 1-\beta^{-t}]$}} e quindi positiva e strettamente minore di $1$.
\end{proposizione}

\smnsp

\begin{proof}[Dimostrazione facoltativa]
La somma $\sum_{k=1}^{t} d_k \beta^{-k}$ risulta piu' grande possibile quando $d_k=\beta-1$. Essendo {\purples{$$\sum_{k=1}^{t} \gamma^k=\frac{\gamma^{t+1}-1}{\gamma-1}-1$$}} necessariamente tale numero $m^*$ \'e
\begin{eqnarray}
m^*&=&\sum_{k=1}^{t} (\beta-1) \beta^{-k}= (\beta-1) \sum_{k=1}^{t}  \beta^{-k} =(\beta-1) \left( \frac{\beta^{-(t+1)}-1}{\beta^{-1}-1}  - 1\right) \nonumber \\
&=&(\beta-1) \left(\beta  \frac{\beta^{-(t+1)}-1}{1-\beta}  - 1\right) = -\beta^{-t}+\beta-\beta+1 = 1 -\beta^{-t}, \nonumber
\end{eqnarray}
con $1-\beta^{-t} < 1$ in quanto $\beta \geq 2$, $t \geq 1$.
\end{proof}

\end{frame}




\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$}


\begin{proposizione}
Il {\underline{pi\'u grande}} numero macchina (normalizzato) \'e {\purples{$\beta^U (1-\beta^{-t})$}}, dove $t$ \'e il numero di cifre della mantissa.
\end{proposizione}

%\vspace{0.25cm}

\begin{proof}[Dimostrazione facoltativa]
Osserviamo che
\begin{itemize}
\item ponendo $d_k=\beta-1$, per $k=1,\ldots,t$ ed $e=U$  in $\beta^e \sum_{k=1}^{t} d_k \beta^{-k}$, \item essendo la somma massima relativa alla mantissa \mye $1-\beta^{-t}$,
\end{itemize}
otteniamo che il massimo numero macchina rappresentabile $M^*$ \mye 
$$M^*=\beta^U (1-\beta^{-t}).$$
\end{proof} 

\end{frame}



\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$}

\smnsp

\begin{proposizione}
L'insieme dei numeri macchina $F(\beta,t,L,U)$ ha un numero finito di elementi e  la sua {\blues{\href{https://it.wikipedia.org/wiki/Cardinalità}{cardinalit\myash}}} \mye
{\purples{
$$2 (\beta-1) \beta^{t-1}(U-L+1).$$
}}

\smnsp
\smnsp

\end{proposizione}

\smnsp

\begin{proof}[Dimostrazione facoltativa.]
{\scriptsize{
Per una fissata mantissa, a $t$ cifre, il numero pi\'u piccolo che possiamo scrivere \mye
{\purples{
$
(1 \, 0 \ldots \,0 \,0)_{\beta}
$
}}
mentre il pi\myu grande \mye
{\purples{
$$
(\underbrace{\beta-1 \, \beta-1 \ldots \,\beta-1 \, \beta-1}_{t})_{\beta}.
$$
}}

Cos\myi non \mye difficile vedere che i numeri scrivibili con $t$ cifre di mantissa sono quelli in cui la prima cifra va da $1$ a $\beta-1$ e le altre da $0$ a $\beta-1$, e quindi la loro cardinalit\mya risulta

\smnsp

$$
(\beta-1) \cdot \underbrace{\beta \ldots \beta \beta}_{t-1}= (\beta-1) \beta^{t-1}.
$$

\smnsp

Quindi, al variare dell'esponente $e$ in $L,L+1,\ldots,U-1,U$, e del segno $+$ o $-$, i numeri floating-point sono
{\purples{
$
2 (\beta-1)  \beta^{t-1} (U-L+1).
$
}}
}}
\end{proof}

\smnsp

\begin{nota}
{\footnotesize{
La cardinalit\'a di $F(\beta,t,L,U) \cup \{0\}$ \'e  $2 (\beta-1) \beta^{t-1}(U-L+1)+1$. In realt\'a i numeri rappresentati dal computer sono di pi\'u se si considera che per approssimare alcune quantit\'a molto piccole o grandi in modulo, si usano numeri di tipo non normalizzato.
}}
\end{nota}

\end{frame}

\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$}

\begin{proposizione}
\begin{enumerate}
\item I numeri macchina sono numeri {\purples{razionali}}. 
\item I numeri macchina che hanno {\underline{esponente $e \geq t$}} sono {\purples{interi}}.
\end{enumerate}
\end{proposizione}

%\vspace{0.25cm}

\begin{proof}[Dimostrazione facoltativa.]
{\footnotesize{
La scrittura dei numeri floating-point come somma di un numero finito di numeri frazionari implica che i numeri risultanti siamo razionali.

Per vedere se $e \geq t$ allora sono interi, da
$$
x={\mbox{sgn(x)}} \beta^e \sum_{i=1}^t d_i \beta^{-i} = {\mbox{sgn(x)}} \sum_{i=1}^t d_i \beta^{e-i}
$$
visto che per $i=1,\ldots,t \geq e$ che $\beta^{e-i}$ \mye intero, come d'altra parte i $d_i$, lo \mye anche $x$.
}}
\end{proof}

\end{frame}

\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$}

\begin{proposizione}
L'insieme dei numeri macchina $F(\beta,t,L,U)$ {\purples{non consiste di punti equispaziati}}.
\end{proposizione}

%\vspace{0.25cm}

\begin{proof}[Dimostrazione facoltativa]
{\footnotesize{
Per capirlo, il numero positivo pi\myu piccolo, e quindi pi\myu vicino a $0$ \mye $\beta^{L-1} \ll 1$ mentre i numeri floating-point che hanno esponente $e \geq t$ sono interi e quindi la distanza di due tali numeri successivi \mye sicuramente maggiore o uguale $1$.

In definitiva, due numeri successivi vicino a $0$ distano molto poco, e due numeri successivi con esponente molto grande distano molto, e quindi l'insieme dei floating-point non consiste di punti equispaziati.
}}
\end{proof}

\end{frame}

\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$}

\begin{esempio}
In Matlab, in precisione doppia, 
\begin{itemize}
\item il numero successivo a $0$ \mye circa $2.2251 \cdot 10^{-308}$,
\item i due numeri pi\'u grandi distano l'uno dall'altro $\approx 1.9958\cdot 10^{+292}$. 
\end{itemize}

Di conseguenza l'insieme numerico del Matlab non consiste di punti equispaziati perch\mye $$ 1.9958 \cdot 10^{292} \gg 2.2251 \cdot 10^{-308}.$$
\end{esempio}


\end{frame}











\begin{frame}[fragile]
\frametitle{Riassunto delle propriet\'a di $F(\beta,t,L,U)$}
\begin{vuoto}[Riassunto]
\begin{itemize}
\item Il {\underline{pi\'u piccolo}} numero macchina positivo (normalizzato) \'e {\purples{$\beta^{L-1}$}}.
\item Il {\underline{pi\'u grande}} numero macchina (normalizzato) \'e {\purples{$\beta^U (1-\beta^{-t})$}}, dove $t$ \'e il numero di cifre della mantissa.
\item L'insieme dei numeri macchina $F(\beta,t,L,U)$ ha un numero finito di elementi e  la sua {\underline{cardinalit\myash}} \mye
{\purples{
$$2 (\beta-1) \beta^{t-1}(U-L+1)+1.$$
}}
\item I numeri macchina sono numeri {\purples{razionali}}. 
\item I numeri macchina che hanno {\underline{esponente $e \geq t$}} sono {\purples{interi}}.
\item L'insieme dei numeri macchina $F(\beta,t,L,U)$ {\purples{non consiste di punti equispaziati}}.
\end{itemize}
\end{vuoto}
\end{frame}







\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$. Osservazione facoltativa.}

\smnsp

\begin{osservazione}[facoltativa: Matlab e rappresentazione dei numeri]
{\footnotesize{
Nel caso della notazione 

\bignsp

\begin{eqnarray}
y&=&\sgn(y) \cdot (1.d_2 \ldots d_{t})_{\beta} \beta^e= \sgn(y) \cdot \beta^e(1+ \sum_{k=2}^{t} d_k \beta^{-k}) 
\end{eqnarray}

\smnsp

abbiamo i seguenti risultati per $F(\beta,t,L,U)$:
\begin{itemize}
\item la somma degli elementi della mantissa $(1,d_1\ldots d_{t-1}$ \mye un numero nell'intervallo $[1, 2-\beta^{-(t-1)}] \subset [1,2)$;
\item Il pi\myu piccolo numero positivo \mye $\beta^{L}$ (usare quale mantissa $(1.0\ldots0)$);
\item Il pi\myu grande numero positivo \mye $(2-\beta^{-(t-1)}) \cdot \beta^{U}$; 
\end{itemize}
Gli altri asserti sono uguali a quelli visti per la notazione classica.

Matlab utilizza questa notazione e quindi per quanto riguarda ad esempio la precisione doppia $F(2,53,-1022,1023)$:
\begin{itemize}
\item la somma degli elementi della mantissa $(1,d_1\ldots d_{52})$ \mye un numero nell'intervallo $[1, 2-\beta^{-(52)}] \approx [1,2-2.22 \cdot 10^{-16}]$;
\item Il pi\myu piccolo numero positivo \mye $\beta^{L}=2^{-1022} \approx 2.225073858507201e-308$;
\item Il pi\myu grande numero positivo \mye $(2-\beta^{-(t-1)}) \cdot \beta^{U}=(2-\beta^{-(52)}) \cdot 2^{1023}=1.797693134862316e+308$.
\end{itemize}
}}
\end{osservazione}
\end{frame}


\begin{frame}[fragile]
\frametitle{Alcune propriet\'a di $F(\beta,t,L,U)$. Osservazione facoltativa.}
\begin{vuoto}
{\footnotesize{
Di seguito faremo esempi di queste quantit\'a relativamente agli insiemi $F(2,24,-126,127)$ e  $F(2,53,-1022,1023)$.

\smsp

Per quanto riguarda numeri speciali
\begin{itemize}
\item per rappresentare {\tt{+inf}} si utilizza il segno pari a $0$, tutte le cifre degli esponenti uguali a $1$ e tutta la mantissa uguale a $0$;
\item per rappresentare {\tt{-inf}} si utilizza il segno pari a $1$,  tutte le cifre degli esponenti uguali a $1$ e tutta la mantissa uguale a $0$;
\item per rappresentare lo $0$ si distingue $+0$ da $-0$ (generalmente utilizzati per denotare un numero troppo piccolo in modulo che viene arrotondato a $0$, pur mantenendo il segno); a parte il segno (positivo di default), tutte le altre cifre di esponente e mantissa sono uguali a $0$;
\item per rappresentare con {\tt{NaN}} il risultato di un'operazione (numerica) eseguita su operandi non validi (specialmente in calcoli in virgola mobile). Secondo IEEE 754 i NaN sono rappresentati con il campo dell'esponenziale riempito di "$1$" e un numero diverso da zero nel campo della mantissa. 
\end{itemize}
}}
\end{vuoto}

\end{frame}

\begin{frame}[fragile]
\frametitle{Precisione singola e doppia}

Descriviamo di seguito i pi\myu comuni insiemi di numeri floating-point. 

\smsp

{\purples{1.}} Usualmente se $M$ \mye il numero di bits necessari per un numero in precisione {\purples{singola}}, nel caso di precisione {\purples{doppia}} questo \mye usualmente composto da 2 {\purples{parole}} di $M$ bits. 

\smsp

{\purples{2.}} Classici esempi sono per quanto riguarda i processori che seguono lo standard IEEE754 (inizialmente proposto da INTEL, studiato dal 1977 e introdotto nel 1985), e i successivi aggiornamenti fino all'attuale versione 2008 e alle proposte di IEEE854,

\vspace{0.3cm}

\begin{itemize}
\item in precisione singola $F(2,24,-126,127)$, ogni numero macchina occupa 32 bit (o 4 byte essendo un byte pari a 8 bit) 
\item in precisione  doppia $F(2,53,-1022,1023)$, ogni numero macchina occupa $64$ bit. 
\end{itemize}

\end{frame}


\begin{frame}[fragile]
\frametitle{Precisione singola}

\vspace{0.25cm}

\begin{vuoto}[Precisione singola]
Nel caso della precisione singola $F(2,24,-126,127)$,
\begin{itemize}
\item Si usa la base $2$.
\item Si usa {\underline{un bit}} per il {\purples{segno}}.
\item Si usa una {\purples{mantissa di $24$ cifre binarie}}, ma visto che si utilizza la notazione normalizzata, {\underline{solo $23$ sono necessarie}}.
\item Visto che si compone di $32$ bits, di cui $24$ per mantissa e segno, {\purples{$8$}} possono essere dedicate all'{\purples{esponente}} (quindi si possono rappresentare numeri interi da $0$ a $255$). 

{\purples{(a)}} Dato che i numeri $0$ e $255$ vengono utilizzati per significati speciali, sono utilizzati esclusivamente gli interi $N_e$ da $1$ a $254$. 

{\purples{(b)}} Fissato {\tt{bias}}=$127=2^7-1$  per ottenere gli esponenti $e$ li si codifica con $N_e$ tale che
{\purples{
$
e=N_e-{\mbox{\tt{bias}}}.
$
}}

\smsp

Evidentemente 
\begin{itemize}
\item il pi\'u piccolo esponente $e_{min}=1-127=-126$, 
\item  il pi\'u grande esponente \'e $e_{max}=254-127=127$.
\end{itemize}
\end{itemize}
\end{vuoto}

\end{frame}

\begin{frame}[fragile]
\frametitle{Precisione singola}

\begin{nota}[Sulla precisione singola in Matlab]
Nell'implementazione Matlab, 

\vspace{0.25cm}

\begin{itemize}
\item Il minimo numero positivo in precisione singola \'e
$$
x_{min}=1.1754944e-38;
$$
\item Il massimo numero positivo in precisione singola \'e
$$
x_{max}=3.4028235e+38;
$$
\item la cardinalit\mya dell'insieme $F(2,24,-126,127)$ \mye 
$$ \approx 4.2950e+09.$$
\end{itemize}
\end{nota}
\end{frame}



\begin{frame}[fragile]
\frametitle{Precisione doppia}

\begin{vuoto}[Precisione doppia]
Nel caso della precisione doppia $F(2,53,-1022,1023)$,
\begin{itemize}
\item Si usa la base $2$.
\item Si usa {\underline{un bit}} per il {\purples{segno}}.
\item Si usa una {\purples{mantissa di $53$ cifre binarie}}, ma visto che si utilizza la notazione normalizzata, {\underline{solo $52$ sono necessarie}}.
\item Visto che si compone di $64$ bits, di cui $53$ per mantissa e segno, {\purples{$11$}} possono essere dedicate all'{\purples{esponente}} (quindi si possono rappresentare numeri interi da $0$ a $2047$). 

{\purples{(a)}} Dato che i numeri $0$ e $2047$ vengono utilizzati per significati speciali, sono utilizzati esclusivamente gli interi  $N_e$ da $1$ a $2046$.

{\purples{(b)}} Fissato {\tt{bias}}=$1023=2^{10}-1$  per ottenere gli esponenti $e$ li si codifica con $N_e$ tale che{\purples{
$
e=N_e-{\mbox{\tt{bias}}}.
$
}}

\smsp

Evidentemente 
\begin{itemize}
\item il pi\'u piccolo esponente \mye $e_{min}=(1-1023)=-1022$
\item il pi\'u grande esponente \mye $e_{max}=2046-1023=1023$.
\end{itemize}
\end{itemize}
\end{vuoto}
\end{frame}

\begin{frame}[fragile]
\frametitle{Precisione doppia}

\begin{nota}[Sulla precisione doppia in Matlab]
Nell'implementazione Matlab, 

\vspace{0.25cm}

\begin{itemize}
\item Il minimo numero positivo in precisione doppia \'e
$$
x_{min}=2.225073858507201e-308;
$$
\item Il massimo numero positivo in precisione doppia \'e
$$
x_{max}=1.797693134862316e+308;
$$
\item la cardinalit\mya dell'insieme $F(2,53,-1022,1023)$ \mye 
$ \approx 3.7038e+19.$
\end{itemize}
\end{nota}

\end{frame}

\begin{frame}[fragile]
\frametitle{Precisione doppia. Nota facoltativa}

\begin{osservazione}[facoltativa]
Si pu\myo credere che i numeri utilizzati per le precisioni singole e doppie siano sempre stati questi, ma non \mye cos\'i.
In altri sistemi, differentemente da IEEE754, il numero di cifre per esponente e mantissa sono risultati molteplici, ad esempio su
\begin{itemize}
\item Zuse Z1 ($\approx 1936$), la mantissa corrispondeva a $22$ cifre (14 per la mantissa e 8 per l'esponente),
\item IBM 3033 in precisione doppia si aveva, oltre alla base $\beta=16$, una mantissa di $14$ cifre,
\item PRIME 850, che lavorava in base $\beta=2$, si aveva in precisione singola $23$ cifre di mantissa, mentre in precisione doppia $47$ cifre di mantissa, \cite[p.13]{ATK}.
\end{itemize}
\end{osservazione}

\end{frame}

\begin{frame}[fragile]
\frametitle{Troncamento e arrotondamento}
Se $x$ \mye il numero reale $$x=\sgn(x)  (0.d_1, \ldots d_t,\ldots)_{\beta} \beta^e= \sgn(x)  \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}, \hspace{0.3cm} d_1 > 0$$ allora con $\myfl(x)$ denotiamo
$$fl(x)=\sgn(x)  (0.d_1, \ldots,d_{t-1},\overline{d_t}) \beta^e= {\purples{\sgn(x)  \beta^e  (\sum_{k=1}^{t-1} d_k \beta^{-k}+\overline{d_t} \beta^{-t}) }}$$ 
 
\noindent in cui 
\begin{itemize} 
\item se si effettua il {\purples{troncamento}} $$\overline{d_t} = d_t;$$  
\item se viene effettuato l'{\purples{arrotondamento}}.
 $$\overline{d_t} =\left \{ \begin{array}{l} d_t, \, \hspace{0.75cm} d_{t+1} < \beta/2 \\   d_t+1, \, \hspace{0.17cm}  d_{t+1} \geq  \beta/2 \end{array} \right.$$  
 \end{itemize}
 
 La scelta tra troncamento o arrotondamento \mye eseguita a priori dal sistema numerico utilizzato dal calcolatore. L'ultima, \mye la pi\myu diffusa.
 
\end{frame}



\begin{frame}[fragile]
\frametitle{Troncamento e arrotondamento: base 10}

\smnsp

 Se in particolare la base \mye 10 e $$x=\sgn(x)  (0.d_1, \ldots d_t,\ldots)_{10} 10^e= \sgn(x)  \cdot 10^e  \sum_{k=1}^{+\infty} d_k \cdot 10^{-k}, \hspace{0.3cm} d_1 > 0$$ allora con $\myfl(x)$ denotiamo
 
 \smnsp
 
 $$fl(x)=\sgn(x)  (0.d_1, \ldots,d_{t-1},\overline{d_t}) \cdot 10^e= \sgn(x)  10^e  (\sum_{k=1}^{t-1} d_k \cdot 10^{-k}+\overline{d_t} \cdot 10^{-t})$$ 
 
\smnsp
 
 in cui se viene effettuato l'{\purples{arrotondamento}}.
 $$\overline{d_t} =\left \{ \begin{array}{l} d_t, \, \hspace{0.75cm} d_{t+1} < 5 \\   d_t+1, \, \hspace{0.17cm}  d_{t+1} \geq  5 \end{array} \right.$$  

 

 
\end{frame}





\begin{frame}[fragile]
\frametitle{Troncamento e arrotondamento: esempio}


\begin{esempio}
Si consideri $$\pi=(+1) \cdot (0.314159 26535 \ldots \ldots)_{10} \cdot 10^1.$$ 
\begin{itemize}
\item Se lo {\purples{tronchiamo}} alla quarta cifra decimale otteniamo che il corrispondente numero {\it{floating point}} \mye
$$fl(\pi)=+1 \cdot (0.3141)_{10} \cdot 10^1,$$
\item se lo {\purples{arrotondiamo}} otteniamo che il corrispondente numero {\it{floating point}} \mye
$$fl(\pi)=+1 \cdot (0.3142)_{10} \cdot 10^1.$$
\end{itemize}
\end{esempio}

\begin{nota}
Evidentemente, per effettuare un arrotondamento, il calcolatore deve immagazzinare in un extra-bit la cifra $d_{t+1}$ (rifletterci un po').
\end{nota}

\end{frame}



\begin{frame}[fragile]
\frametitle{Troncamento e arrotondamento: osservazione}

Se l'esponente $e$ del numero $x$ \mye 
\begin{itemize}
\item minore del minimo esponente $L$, si commette un'errore di {\purples{underflow}},  
\item maggiore del massimo esponente $U$, si commette un'errore di {\purples{overflow}}. 
\end{itemize}
Se invece 
\begin{itemize}
\item $e \in [L,U]$, 
\item $x= \pm \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}$,
\item per qualche $t^{\ast} > t$ si ha $d_{t^{\ast}} > 0$ 
\end{itemize}
allora si commette un errore di {\purples{troncamento}} o {\purples{arrotondamento}} a seconda si effettui l'uno o l'altro. 

\begin{osservazione}
Osserviamo che esistono numeri denormalizzati, il cui range estende quello dei normalizzati. 
II pi\'u piccolo numero positivo denormalizzato \'e $0.494\cdot 10^{-323}$, permettendo di passare {\purples{gradualmente}} dall'underflow allo $0$.
\end{osservazione}

\end{frame}

\begin{frame}[fragile]
\frametitle{La precisione di macchina}

{\small{

Una delle costanti rilevanti all'interno del sistema floating point \mye la precisione di macchina.

\vspace{0.25cm}

\begin{definizione}
Si dice {\purples{precisione di macchina}}, quel numero {\tt{eps}}=$\beta^{1-t}$ che rappresenta la {\purples{distanza}}
tra $1$ ed il successivo numero in virgola mobile.  
\end{definizione}

\vspace{0.25cm}
Si vede facilmente che il numero $x^*$ (normalizzato!) successivo a $1$ ha mantissa $d_1={\purples{1}},d_2=0,d_3=0,\ldots,d_{t-1}=0,d_t={\purples{1}}$ e esponente $e=1$ e quindi \mye $$x^* =\beta \sum_{k=1}^t d_k\beta^{-k}= \beta^1(1 \cdot {\beta}^{-1}+ 1  \cdot \beta^{-t})=1+\beta^{1-t},$$
per cui 
{{
$
{\mbox{}\tt{eps}}=(1+\beta^{1-t})-1=\beta^{1-t}.
$
}}

}}

\begin{nota}
Si noti che {\tt{eps}} non \mye il numero ${{x}}^* > 1$ e pi\'u vicino a 1, ovvero ${{x}}^*=1+\beta^{1-t}$, bens\i' $|{{x}}^*-1|=\beta^{1-t}$.
\end{nota}
\end{frame}


\begin{frame}[fragile]
\frametitle{La precisione di macchina}

Si sottolinea che la precisione di macchina {\purples{{\tt{eps}}}} {\underline{non coincide}} in generale con il {\underline{pi\myu piccolo numero positivo}} rappresentabile dal calcolatore, in quanto se $t \neq 2-L$, come accade per la precisione singola e doppia, allora
$$
{\mbox{\tt{eps}}}:= \beta^{1-t} \neq \beta^{L-1}.
$$


In Matlab, supposto si usi la precisione doppia, $x_{min}$ \mye molto inferiore di {\tt{eps}}, in quanto
\begin{itemize}
\item il pi\'u {\purples{piccolo numero positivo}} in modulo \mye $$x_{min} = 2^{-1022}=2.225073858507201 \cdot 10^{ {\purples{-308}}},$$
\item la {\purples{precisione di macchina}}  \mye $${\mbox{\tt{eps}}}=2^{-52}=2.220446049250313 \cdot 10^{ {\purples{-16}}}.$$
\end{itemize}


\end{frame}



\begin{frame}[fragile]
\frametitle{Errori relativi e assoluti}


Si supponga  di approssimare un numero $x^{\ast} \in {\mathbb R}$, con $x \in {\mathbb R}$ (ad esempio $x=fl({x^{\ast}})$).

{\vspace{0.3cm}}

\begin{definizione}[Errore assoluto e relativo]
Si definisce
\begin{enumerate}
\item errore {\purples{assoluto}} tra $x$ e $x^{\ast}$ la quantit\mya
$$|x-x^{\ast}|$$
\item errore {\purples{relativo}} tra $x$ e $x^{\ast} \neq 0$ la quantit\mya 
$$ {\frac{|x-x^{\ast}|}{|x^{\ast}|}}.$$
\end{enumerate}
\end{definizione}

\begin{osservazione}
Si noti che se ${|x^{\ast}|}=0$, cio\mye ${x^{\ast}}=0$, allora non ha senso la scrittura propria dell'errore relativo. 
\end{osservazione}
\end{frame}




\begin{frame}[fragile]
\frametitle{Errori relativi e assoluti}

\smnsp
\smnsp

\begin{esempio}
Si consideri {\purples{$
\pi=3.141592653589793 \ldots$}}.

\smsp


In precisione singola 

\smnsp
\smnsp

$$
\myfl(\pi)=3.1415927
$$
e abbiamo che, ponendo nella definizione precedente $x^{\ast}=\pi$, $x=\myfl(\pi)$
\begin{itemize}
\item l'errore assoluto \mye$
|x-x^{\ast}|=|\myfl(\pi)-\pi| \approx 8.7422777\cdot 10^{-8}
$
\item l'errore relativo \mye
$
{\frac{|x-x^{\ast}|}{|x^{\ast}|}}=\frac{|fl(\pi)-\pi|}{\pi} \approx 2.7827534\cdot 10^{-8}.
$
\end{itemize}
Si osservi che, come diremo in seguito, la precisione di macchina per precisione singola di Matlab (che usa l'{\purples{arrotondamento}}!) \mye ${\tt{eps}}_S \approx 1.1920929\cdot 10^{-7}$ e si ha
$$
2.7827534\cdot 10^{-8} \approx \frac{|\pi-\myfl(\pi)|}{\pi} \leq {\purples{\tt{eps}}_S/2} \approx 5.9604645 \cdot 10^{-8}.
$$
Quindi l'errore relativo compiuto \'e inferiore o al pi\'u uguale a ${\tt{eps}}_S/2$
\end{esempio}
\end{frame}





\begin{frame}[fragile]
\frametitle{Errori relativi e assoluti}
{\small{
\noindent
\begin{nota}
Fissato un vettore {\purples{$x^{\ast}=(x^{\ast}_1,\ldots,x^{\ast}_n) \in {\mathbb R}^n,$}} approssimato da $x$
si definisce

\begin{enumerate}
\item errore {\purples{assoluto}} tra $x$ e $x^{\ast}$ la quantit\mya
$\|x-x^{\ast}\|$
dove 
\begin{itemize}
\item $\|\cdot\|$ \mye una norma (cf. {\cite{WIKNRM}}); ad esempio $\|\cdot\|$ pu\'o essere la cosidetta norma $2$ o euclidea, ovvero se $y=(y_1,\ldots,y_n)$ allora $\|y\|_2=\sqrt{\sum_{i=1}^n y_i^2}$,
\item se $x=(x_1,\ldots,x_n)$ allora $x-x^*=(x_1-x^{\ast}_1,\ldots,x_n-x^{\ast}_n)$.
\end{itemize}
{\smsp}
\item errore {\purples{relativo}} tra $x$ e $x^{\ast} \neq 0$ la quantit\mya 
$$ {{\|x-x^{\ast}\|}/{\|x^{\ast}\|}}.$$
\end{enumerate}
\end{nota}
\begin{osservazione}
{\footnotesize{
Si noti che se ${\|x^{\ast}\|}=0$, cio\mye ${x^{\ast}}=0$ per la propriet\mya delle norme {\cite[p.481]{ATK}}, allora non ha senso la scrittura propria dell'errore relativo. Inoltre se il vettore ha un solo componente, allora la norma $\|\cdot\|$ coincide con l'usuale valore assoluto $|\cdot|$. 
}}
\end{osservazione}
}}

\end{frame}

\begin{frame}[fragile]
\frametitle{Errori relativi e assoluti}

{\small{
\begin{proposito}
Intendiamo {\purples{calcolare l'errore relativo tra un numero reale e il suo floating point associato}}, nel caso si usi il troncamento o l'arrotondamento.
\end{proposito}
\smsp

Sia $x^* \in {\mathbb{R}}$, con $$x^* = \sgn(x^*) \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k} \neq 0, \hspace{0.3cm} d_1 >0$$ e $x=fl(x^*)$ la sua approssimazione in virgola mobile, ovvero
\begin{eqnarray}
fl(x^*)&=&\sgn(x^*)  (0.d_1, \ldots,d_{t-1},\overline{d_t}) \beta^e \\ &=& \sgn(x^*)  \beta^e  (\sum_{k=1}^{t-1} d_k \beta^{-k}+\overline{d_t} \beta^{-t}), \hspace{0.3cm} d_1 >0. \nonumber
\end{eqnarray} 

Visto che $d_1 \geq 1$, $d_k \geq 0$, $\beta > 0$, abbiamo $$\sum_{k=1}^{+\infty} d_k \beta^{-k}= d_1 \beta^{-1}+d_2 \beta^{-2} +\ldots \geq d_1 \beta^{-1} \geq \beta^{-1}$$

\noindent e quindi visto che i numeri macchina sono normalizzati 
$${\purples{|x^*|}}=\beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k} \geq \beta^e \cdot \beta^{-1}=  {\purples{\beta^{e-1}}}.$$
}}
\end{frame}









\begin{frame}[fragile]
\frametitle{Errori relativi e assoluti}
{\small{
\begin{itemize}
\item Da $$|x^*| \geq \beta^{e-1}$$ ricaviamo immediatamente dividendo ambo i membri per $|x^*|$ e $\beta^{e-1}$ $$\frac{1}{|x^*|} \leq \frac{1}{\beta^{e-1}};$$ 
\item osserviamo che $ \sum_{k=1}^{+\infty} d_k \beta^{-k}- \sum_{k=1}^{t-1} d_k \beta^{-k}= \sum_{k=t}^{+\infty} d_k \beta^{-k}$.
\end{itemize}

\smsp

Quindi essendo $|\sgn(x^*)|=1$,
\begin{eqnarray}
\frac{|x^*-fl(x^*)|}{|x^*|} &\leq&  \frac{| \sgn(x^*) \beta^e  \sum_{k=1}^{+\infty} d_k \beta^{-k}-(\sgn(x^*)\beta^e  (\sum_{k=1}^{t-1} d_k \beta^{-k}+\overline{d_t} \beta^{-t}))|}{\beta^{e-1} } \nonumber \\
&\leq&  \frac{| \sgn(x^*) \beta^e ( \sum_{k=1}^{+\infty} d_k \beta^{-k}-  (\sum_{k=1}^{t-1} d_k \beta^{-k}+\overline{d_t} \beta^{-t}))|}{\beta^{e-1}) } \nonumber \\
&=& \frac{|\sgn(x^*)| \cdot \beta^e  \cdot |   \sum_{k=1}^{+\infty} d_k \beta^{-k}-  \sum_{k=1}^{t-1} d_k \beta^{-k}-\overline{d_t} \beta^{-t})|}{ \beta^{e-1} } \nonumber \\ &=&
 \beta \cdot \left| \sum_{k=t}^{+\infty} d_k \beta^{-k}-\overline{d_t} \beta^{-t} \right|. \nonumber
\end{eqnarray}
}}
\end{frame}







\begin{frame}[fragile]
\frametitle{Errori relativi e assoluti}
{\small{
Nel caso si effettui il {\underline{troncamento}}, visto che ${\overline{d_t}}=d_t$, ricaviamo dalla precedente 
\begin{center}
\begin{tcolorbox}[width=7cm]
\smnsp
\smnsp
$$\frac{|x^*-fl(x^*)|}{|x^*|} \leq  \beta \cdot \left| \sum_{k=t}^{+\infty} d_k \beta^{-k}-\overline{d_t} \beta^{-t} \right| $$
\smnsp
\smnsp
\end{tcolorbox}
\end{center}

Osserviamo pure che
\begin{center}
\begin{tcolorbox}[width=7cm]
\smnsp
$$\sum_{k=t+1}^{+\infty} d_k \beta^{-k} \leq \beta^{-t}$$
\smnsp
\end{tcolorbox}
\end{center}

In effetti, 
\begin{eqnarray}
\sum_{k=t+1}^{+\infty} d_k \beta^{-k}&=&d_{t+1}\beta^{-(t+1)}+d_{t+2}\beta^{-(t+2)}+d_{t+3}\beta^{-(t+3)}+\ldots 
\nonumber \\ &=&\beta^{-t}(d_{t+1}\beta^{-1}+d_{t+2}\beta^{-2}+d_{t+3}\beta^{-3}+\ldots)
=\beta^{-t} (0.d_{t+1} d_{t+2} \ldots)_\beta \nonumber \\ &\leq& \beta^{-t} 
\end{eqnarray}
in quanto $(0.d_{t+1} d_{t+2} \ldots)_\beta$ \'e una mantissa e quindi \'e una quantit\'a in $[0,1)$.
}}
\end{frame}

\begin{frame}[fragile]
\frametitle{Errori relativi e assoluti}

In conclusione si ha  

\begin{eqnarray}  
\frac{|x^*-fl(x^*)|}{|x^*|} & \leq &\beta \cdot \left| \sum_{k=t}^{+\infty} d_k \beta^{-k}-{\purples{\overline{d_t}}} \beta^{-t} \right|  = \beta \cdot \left| \sum_{k=t}^{+\infty} d_k \beta^{-k}-{\purples{d_t}} \beta^{-t} \right| \nonumber \\
&=& \beta   \sum_{k=t+1}^{+\infty} d_k \beta^{-k} 
\leq \beta \cdot \beta^{-t}=\beta^{1-t}={\mbox{\tt{eps}}} \nonumber
\end{eqnarray}

Dalla precedente si conclude che nel caso si effettui il troncamento
{\purples{$$\frac{|x^*-fl(x^*)|}{|x^*|} \leq {\mbox{\tt{eps}}} .$$}}

\end{frame}

\begin{frame}[fragile]
\frametitle{Errori relativi e assoluti}


Da  {\purples{$$\frac{|x^*-fl(x^*)|}{|x^*|} \leq  \beta \cdot \left| \sum_{k=t}^{+\infty} d_k \beta^{-k}-\overline{d_t} \beta^{-t} \right|, 
$$}} nel caso si effettui l'{\underline{arrotondamento}} abbiamo dopo alcuni calcoli che 
{\purples{$$\frac{|x^*-fl(x^*)|}{|x^*|} \le \frac{\beta^{1-t}}{2}= \frac{{\mbox{\tt{eps}}}}{2}.$$}}
\noindent La quantit\mya ${{\mbox{\tt{eps}}}}/{2}$ \mye detta {\purples{unit\mya di arrotondamento}} ed \mye ovviamente inferiore alla precisione di macchina {\tt{eps}}.


\begin{osservazione}
Da queste stime sull'errore relativo compiuto nell'approssimare $x$ con $fl(x)$ via arrotondamento e troncamento, si capisce perch\mye il primo risulti il sistema sia pi\myu utilizzato.
\end{osservazione}
\end{frame}







\begin{frame}[fragile]
\frametitle{Operazioni con i numeri macchina}

\vspace{0.25cm}

\noindent
Indicato con ${\mbox{fl}}(x)$ il numero macchina che {\purples{corrisponde}} a \mydla $x$", denotiamo con 

\begin{eqnarray}
x \oplus y &:=& \myfl (\myfl(x)+\myfl(y)) \\
x \ominus y &:=& \myfl (\myfl(x)-\myfl(y)) \\
x \otimes y &:=& \myfl (\myfl(x) \cdot \myfl(y)) \\
x \oslash y &:=& \myfl (\myfl(x)/\myfl(y)) 
\end{eqnarray}

\noindent
e per ${\odot}$ una delle operazioni precedentemente introdotte, cio\mye una tra $\oplus$, $\ominus$, $\otimes$, $\oslash$ corrispondenti a {\tt{op}} cio\mye una tra $+$, $-$, $\cdot$, $:$. Inoltre porremo
$$
\epsilon_x:=\frac{|x-\myfl(x)|}{|x|} ,\smhsp \epsilon_{x,y}^{\odot}:=\frac{| (x \, {\mbox{op}}  \, y )-(x \, {\odot}  \, y )|}{|x \, {\mbox{op}} \, y|}
$$
\end{frame}


\begin{frame}[fragile]
\frametitle{Operazioni con i numeri macchina}

\begin{osservazione}
Osserviamo, che a volte nei manuali si trova qualcosa di diverso. Ad esempio, 
$$
x \oplus y = \myfl (x+y) .
$$
In realt\mya il sistema floating point, utilizzando ulteriori bits nei calcoli, garantisce che sia 
$$
x \oplus y = \myfl (\myfl(x)+\myfl(y)) = \myfl (x+y).
$$ 
\end{osservazione}
\end{frame}

\begin{frame}[fragile]
\frametitle{Propriet\'a commutativa, associativa e distributiva delle operazioni floating point}

Per prima cosa osserviamo che alcune propriet\mya caratteristiche di $+$, $-$, $\cdot$ e $:$ non valgono per i corrispettivi $\oplus$, $\ominus$, $\otimes$, $\oslash$. 

\smsp

Infatti per la somma $\oplus$ e il prodotto $\otimes$ 
\begin{itemize}
\item {\underline{vale}} la propriet\mya {\purples{commutativa}},
\item {\underline{non valgono}} quella {\purples{associativa}} e {\purples{distributiva}}. 
\end{itemize}

Quindi l'{\purples{ordine}} in cui sono eseguite le operazioni pu\myo variare il risultato.

\smsp

Inoltre esistono l'{\purples{elemento neutro}} della moltiplicazione, divisione, addizione e sottrazione, come pure l'{\purples{opposto}} di ogni numero floating-point.


\end{frame}




\begin{frame}[fragile]
\frametitle{Propriet\'a commutativa, associativa e distributiva delle operazioni floating point: esempio}

Mostriamo come {\underline{non}} valga la propriet\mya {\purples{associativa}} della somma. 

\begin{esempio}
Consideriamo {\purples{$F(10,4,-10,+10)$}} con {\purples{fl}} basato sul troncamento. Sia $a=2000$, $b=2.5$, $c=7.8$. Allora non \mye vero che 

$$
(a \oplus b) \oplus c =  a \oplus (b \oplus c)
$$

\noindent
in quanto

\smnsp
\smnsp

\begin{eqnarray}
(a \oplus b) \oplus c &=& 0.2002 \cdot 10^4 \oplus 0.7800 \cdot 10^1 = 0.2009 \cdot 10^4 \nonumber \\
 a \oplus (b \oplus c)&=& 0.2000 \cdot 10^4 \oplus 0.1030 \cdot 10^2 = 0.2010 \cdot 10^4 \nonumber
\end{eqnarray}
e quindi $(a \oplus b) \oplus c \neq  a \oplus (b \oplus c)$.
\end{esempio}
\end{frame}



\begin{frame}[fragile]
\frametitle{Propriet\'a commutativa, associativa e distributiva delle operazioni floating point: esempio}

Mostriamo come {\underline{non}} valga la propriet\mya {\purples{distributiva}}. 
\begin{esempio}
{\small{
In {\purples{$F(10,6,-10,+10)$}}, posti 

\begin{itemize}
\item $a=0.800000 \cdot 10^9$, 
\item $b=0.500009 \cdot 10^4$, 
\item $c=0.500008 \cdot 10^4$,
\end{itemize}

Allora non \mye vero che {\purples{$
a \otimes (b \ominus c) =  (a \otimes b) \ominus (a \otimes c) $
}} in quanto

\smnsp
\smnsp


\begin{eqnarray}
a \otimes (b \ominus c) &=& 0.800000 \cdot 10^9 \otimes 0.1 \cdot 10^{-2} = 0.800000 \cdot 10^6 \nonumber \\
(a \otimes b) \ominus (a \otimes c) &=& (0.800000 \cdot 10^9 \otimes 0.500009 \cdot 10^4)  \nonumber \\ &&\ominus (0.800000 \cdot 10^9 \otimes 0.500008 \cdot 10^4) \nonumber \\ &\rightarrow& {\mbox{NaN}} \nonumber
\end{eqnarray}
(il {\tt{NaN}} \mye dovuto al fatto che in $F(10,6,-10,+10)$, si ha che $0.8 \cdot 10^9 \otimes 0.500009 \cdot 10^4 \approx 0.8 \cdot 10^9 \otimes 0.500008 \cdot 10^4 \approx 0.4 \cdot 10^{13}>10^{10}$ sono overflow!).
}}
\end{esempio}
\end{frame}

\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione}

\smnsp

\begin{teorema}[cf. {\cite[p.78]{COM}}]
{\footnotesize{
Valgono le seguenti stime

\smnsp
\smnsp

\begin{eqnarray}
\epsilon_{x,y}^{\oplus} &=& \frac{|(x+y)-(x \oplus y)|}{|x+y|} \leq  \left| {\frac{x}{x+y} } \right| \epsilon_x +  \left| {\frac{y}{x+y} } \right| \epsilon_y, \smhsp x+y \neq 0 \\
\epsilon_{x,y}^{\ominus} &=& \frac{|(x-y)-(x \ominus y)|}{|x-y|} \leq   \left| {\frac{x}{x-y} } \right| \epsilon_x +  \left| {\frac{y}{x-y} } \right| \epsilon_y, \smhsp x-y \neq 0 \\
\epsilon_{x,y}^{\otimes} &=& \frac{|(x \cdot y)-(x \otimes y)|}{|x \cdot y|} \lessapprox \epsilon_x + \epsilon_y, {\mbox{  }}x\cdot y \neq 0 \\
\epsilon_{x,y}^{\oslash} &=& \frac{|(x / y)-(x \oslash y)|}{|x / y|} \lessapprox  \left| \epsilon_x - \epsilon_y \right|, {\mbox{  }}  y \neq 0, {\mbox{  }} x / y \neq 0
\end{eqnarray}

\noindent dove per ogni operazione floating point $\odot$ relativamente alla generica operazione {\tt{op}} (ovvero $+$, $-$, $*$, $/$)

\smnsp
\smnsp

\begin{eqnarray}
 \epsilon_x&=&|x-fl(x)|/|x|, \nonumber \\
 \epsilon_y&=&|y-fl(y)|/|y|,  \nonumber \\
\epsilon_{x,y}^{\odot}&=&|(x \odot y)-(x {\mbox{\tt{ op }}} y)|/|x {\mbox{\tt{ op }}} y|  \nonumber 
\end{eqnarray}
}}
\end{teorema}
\end{frame}


\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione}

Proviamo di seguito sotto opportune ipotesi il caso della somma, sottrazione e della moltiplicazione, lasciando al lettore quello della divisione. Con $a \lessapprox b$ si intende $a$ {\purples{inferiore}} o uguale circa a $b$.

\begin{proposizione}
Posto
\begin{enumerate}
\item $\epsilon_x=|x-fl(x)|/|x|$, 
\item $\epsilon_y=|y-fl(y)|/|y|$, 
\item $\epsilon_{x,y}^{\oplus}=|(x\oplus y)-(x+y)|/|x+y|$
\end{enumerate}
se
\begin{enumerate}
\item $x+y \neq 0$, $x \neq 0$, $y \neq 0$, 
\item  $\myfl (\myfl(x)+\myfl(y))= \myfl(x)+\myfl(y)$,
\end{enumerate}
allora
\begin{center}
\begin{tcolorbox}[width=5cm]
\smnsp
\smnsp
$$\epsilon_{x,y}^{\oplus} \leq  \left| {\frac{x}{x+y} } \right| \epsilon_x +  \left| {\frac{y}{x+y} } \right| \epsilon_y.$$
\end{tcolorbox}
\end{center}
\end{proposizione}
\end{frame}


\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione}

\smnsp

{\footnotesize{
\begin{proof}
Nelle ipotesi precedenti, visto che 
\begin{itemize}
\item $\epsilon_x=|x-fl(x)|/|x|$,  
\item $\epsilon_y=|y-fl(y)|/|y|$,  
\item $\myfl (\myfl(x)+\myfl(y))= \myfl(x)+\myfl(y)$,
\item $|a+b|\leq |a|+|b|$, $a,b, \in {\mathbb{R}}$,
\end{itemize}
\begin{eqnarray}
{\purples{\epsilon_{x,y}^{\oplus}}}&=&\frac{|(x+y)-(x \oplus y)|}{|x+y|}=\frac{|(x+y)-\myfl (\myfl(x)+\myfl(y))|}{|x+y|} \nonumber \\
&=&\frac{|(x+y)- (\myfl(x)+\myfl(y))|}{|x+y|} =   \frac{|(x-\myfl(x))+(y-\myfl(y))|}{|x+y|}  \nonumber \\
  &{\purples{ \leq}}  &  \frac{|x-\myfl(x)|+|y-\myfl(y)|}{|x+y|}  = \frac{|x-\myfl(x)|}{|x+y|}  + \frac{|y-\myfl(y)|}{|x+y|}  \nonumber \\
  &=& \frac{|x|}{|x+y|}  \cdot  \frac{|x-\myfl(x)|}{|x|}+  \frac{|y|}{|x+y|} \cdot \frac{|y-\myfl(y)|}{|y|} 
  = {\purples{\left| {\frac{x}{x+y} } \right| \epsilon_x +  \left| {\frac{y}{x+y} } \right| \epsilon_y }} \nonumber
\end{eqnarray}

\smnsp
\end{proof}

\smnsp



}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione}
\begin{nota}[Cancellazione]
{\small{
Si noti che per $x+y \approx 0$ da
\begin{eqnarray}
{\purples{\epsilon_{x,y}^{\oplus}}} &\leq& {\purples{\left| {\frac{x}{x+y} } \right| \epsilon_x +  \left| {\frac{y}{x+y} } \right| \epsilon_y }} \nonumber
\end{eqnarray}

abbiamo che per piccoli errori sui dati $\epsilon_x$, $\epsilon_y$ possono aversi errori rilevanti in $\epsilon_{x,y}^{\oplus}$ (fenomeno noto come {\purples{cancellazione}}). 
}}
\end{nota}

\begin{nota}[Facoltativa e tecnica]
{\small{
Nel precedente asserto, abbiamo supposto che 
$\myfl (\myfl(x)+\myfl(y))= \myfl(x)+\myfl(y)$.
Richiesto che si effettui l'arrotondamento per determinare l'approssimante floating-point, per qualche $\delta\in [0,{\tt{eps}}/2)$, 
$$\myfl (\myfl(x)+\myfl(y))= (\myfl(x)+\myfl(y)) (1+\delta)$$
ma il risultato che otteniamo, a parte di aumentare la difficolt\mya nei calcoli, \mye essenzialmente lo stesso.
}}
\end{nota}
\end{frame}



\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione}

% SOTTRAZIONE

\begin{proposizione}
Posto
\begin{enumerate}
\item $\epsilon_x=|x-fl(x)|/|x|$, 
\item $\epsilon_y=|y-fl(y)|/|y|$, 
\item $\epsilon_{x,y}^{\ominus}=|(x\ominus y)-(x-y)|/|x-y|$
\end{enumerate}
se
\begin{enumerate}
\item $x-y \neq 0$, $x \neq 0$, $y \neq 0$, 
\item  $\myfl (\myfl(x)-\myfl(y))= \myfl(x)-\myfl(y)$,
\end{enumerate}
allora
\begin{center}
\begin{tcolorbox}[width=5cm]
\smnsp
\smnsp
$$\epsilon_{x,y}^{\ominus} \leq  \left| {\frac{x}{x-y} } \right| \epsilon_x +  \left| {\frac{y}{x-y} } \right| \epsilon_y.$$
\end{tcolorbox}
\end{center}
\end{proposizione}

\end{frame}


\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione}

\begin{proof}[Facoltativa]
Nelle ipotesi precedenti, visto che 
\begin{itemize}
\item $\epsilon_x=|x-fl(x)|/|x|$,  
\item $\epsilon_y=|y-fl(y)|/|y|$,  
\end{itemize}
abbiamo, visto che $\myfl (\myfl(x)-\myfl(y))= \myfl(x)-\myfl(y)$,
{\footnotesize{
\begin{eqnarray}
\epsilon_{x,y}^{\ominus}&=&\frac{|(x-y)-(x \ominus y)|}{|x-y|}=\frac{|(x-y)-\myfl (\myfl(x)-\myfl(y))|}{|x-y|} \nonumber \\
&=&\frac{|(x-\myfl(x))-(y-\myfl(y))|}{|x-y|} \leq \frac{|x|}{|x-y|}  \cdot  \frac{|x-\myfl(x)|}{|x|}+  \frac{|y|}{|x-y|} \cdot \frac{|y-\myfl(y)|}{|y|}  \nonumber \\
  &=&  \left| {\frac{x}{x-y} } \right| \epsilon_x +  \left| {\frac{y}{x-y} } \right| \epsilon_y
\end{eqnarray}
}}
\end{proof}

\end{frame}


\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione}


Nuovamente, per $x-y \approx 0$ abbiamo che per piccoli errori sui dati $\epsilon_x$, $\epsilon_y$ possono aversi errori rilevanti in $\epsilon_{x,y}^{\ominus}$. Qualora ci\myo accada, si parla nuovamente di {\purples{fenomeno di cancellazione}}.

\begin{esempio}[Cancellazione]
{\footnotesize{
Consideriamo il sistema $F(10,5,-5,+5)$ (con arrotondamento) e i due numeri 
$$a=0.73415776, {\hspace{0.5cm}}b=0.73402350.$$
Facilmente, 
\begin{itemize}
\item $\myfl{(a)}=0.73416, {\hspace{0.5cm}}\myfl{(b)}=0.73402$
\item $a-b=0.00013426, {\hspace{0.5cm}} a \ominus b=0.00014$;
\item $\epsilon_a \approx 3.051115 \cdot 10^{-6}$, $\epsilon_b \approx 4.768240 \cdot 10^{-6}$,
\item $
\frac{|a|}{|a-b|} \approx 5468.1793534956, \,\, \frac{|b|}{|a-b|} \approx  5467.1793534956,
$
\end{itemize}
Si verifica numericamente che $\epsilon_{a,b}^{\ominus} = |a|/|a-b| \epsilon_a + |b|/|a-b| \epsilon_b$ e che l'errore
$$
\epsilon_{a,b}^{\ominus}=\frac{|(a-b)- (a \ominus b)|}{|a-b|}\approx 0.0427528675710549
$$
e' notevole rispetto $\epsilon_a$, $\epsilon_b$, a causa dei rilevanti {\it{fattori di amplificazione}} $\frac{|a|}{|a-b|}$, $\frac{|b|}{|a-b|}$.
}}
\end{esempio}

\end{frame}



\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione: prodotto}

\begin{proposizione}
Se
\begin{enumerate}
\item  $x \neq 0$, $y \neq 0$, $|fl(y)|/|y| \approx 1$,
\item $\myfl (\myfl(x) \cdot \myfl(y))= \myfl(x) \cdot \myfl(y)$, 
\end{enumerate}
posto 
\begin{itemize}
\item $\epsilon_x=\frac{|x-\myfl(x)|}{|x|}$,
\item $\epsilon_y=\frac{|y-\myfl(y)|}{|y|}$,  
\item $
\epsilon_{x,y}^{\otimes} =|x \otimes y - x \cdot y|/|x \cdot y|
$
\end{itemize}
allora
\begin{center}
\begin{tcolorbox}[width=5cm]
$$
\epsilon_{x,y}^{\otimes} \lessapprox \epsilon_x + \epsilon_y .
$$
\end{tcolorbox}
\end{center}
dove $ \lessapprox$ significa {\purples{inferiore o circa uguale}}.
\end{proposizione}

\end{frame}


\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione: prodotto}




\begin{proof}
Nelle ipotesi precedenti abbiamo
\begin{eqnarray}
\epsilon_{x,y}^{\otimes}&=&\frac{|x\cdot y-x \otimes y|}{|x \cdot y|}=\frac{|x\cdot y-\myfl (\myfl(x) \cdot \myfl(y))|}{|x\cdot y|}=\frac{|x\cdot y - \myfl(x) \cdot \myfl(y)|}{|x\cdot y|} \nonumber \\
&=& \frac{|x\cdot y {\purples{- x\cdot \myfl (y)+ x\cdot \myfl (y)}}- \myfl(x) \cdot \myfl(y)|}{|x\cdot y|} \nonumber \\
&=&  \frac{| x\cdot (y-\myfl (y))+\myfl(y) \cdot (x-\myfl(x)) | }{|x\cdot y|}  \nonumber \\
&\leq&  \frac{| x\cdot (y-\myfl (y))|+|\myfl(y) \cdot (x-\myfl(x)) | }{|x\cdot y|}  \nonumber \\
&=&  \frac{| x\cdot (y-\myfl (y))|}{|x\cdot y|}+
\frac{|\myfl(y) \cdot (x-\myfl(x))|}{|x\cdot y|}  
\nonumber \\
&=&    \underbrace { \frac{| y-\myfl (y)|}{| y|} }_{\epsilon_y} + \underbrace {\frac{|\myfl(y)|}{|y|}}_{\approx 1} \cdot \underbrace { \frac{|x-\myfl(x) | }{| x|}  }_{\epsilon_x} \approx   \epsilon_x + \epsilon_y. \nonumber
\end{eqnarray}

\smnsp
\end{proof}

\end{frame}



\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione: divisione}


\begin{facoltativo}
Per quanto riguarda la divisione $x/y$, forniamo una traccia. Basta 
\begin{itemize}
\item studiare il caso $1/y$,
\item ricordare i risultati del prodotto $x \cdot {\frac{1}{y}}$.
\end{itemize}
per ottenere nelle ipotesi precedenti
$$\epsilon_{x,y}^{\oslash} = \frac{|(x / y)-(x \oslash y)|}{|x / y|} \lessapprox  \left| \epsilon_x - \epsilon_y \right|, {\mbox{  }}  y \neq 0, {\mbox{  }} x / y \neq 0.$$
\vspace{0.25cm}
\end{facoltativo}

\end{frame}

\begin{frame}[fragile]
\frametitle{Errori nelle operazioni e loro propagazione: divisione}

\begin{osservazione}[Difficile, necessario aver seguito il corso di Analisi II]
{\footnotesize{
Osserviamo che dalla formula di Taylor in due variabili, posto per brevit\mya di notazione $f^{\prime}_x=\partial f / \partial x$, $f^{\prime}_y=\partial f / \partial y$,
\begin{equation}\label{T2D}
f(x,y) \approx f({\overline{x}},{\overline{y}})+f_x^{\prime}({\overline{x}},{\overline{y}}) (x-\overline{x})+f_y^{\prime}({\overline{x}},{\overline{y}}) (y-\overline{y}) 
\end{equation}
necessariamente, se $x,y,f(x,y) \neq 0$ allora posti $\epsilon_x=|x-\overline{x}|/|x|$, $\epsilon_y=|y-\overline{y}|/|y|$ gli errori relativi sui dati
\begin{eqnarray}\label{T2D1}
\frac
{|f(x,y)- f( {\overline{x}} , {\overline{y}})|}
{|f(x,y)|}  
&\lessapprox& 
\frac{|f_x^{\prime}({\overline{x}},{\overline{y}})||x-\overline{x}||x|}
{|f(x,y)||x|}+\frac{ |f_y^{\prime}({\overline{x}},{\overline{y}})||y-\overline{y}||y|}{|f(x,y)||y|} \nonumber \\
&=&\frac{|f_x^{\prime}({\overline{x}},{\overline{y}})||x|}
{|f(x,y)|} \cdot \epsilon_x+\frac{ |f_y^{\prime}({\overline{x}},{\overline{y}})||y|}{|f(x,y)|} \cdot \epsilon_y
\end{eqnarray}
Da (\ref{T2D1}), si possono ottenere risultati simili ai precedenti per $\oplus$, $\otimes$. Uno dei vantaggi \mye che si possono studiare operazioni pi\myu generali come ad esempio cosa succeda se si esegue $exp(x+y)$.
}}
\end{osservazione}

\end{frame}


\begin{frame}[fragile]
\frametitle{Alcune problematiche numeriche}

\vspace{0.25cm}

Si consideri un problema scientifico che abbia a che fare con una procedura di calcolo. Sussitono varie tipologie di errore nei calcoli:
\begin{itemize}
\item  {\purples{errori di modellizzazione}}: vengono utilizzate equazioni per rappresentare un evento fisico, e il modello matematico \mye solo una semplificazione di quello reale;
\item  {\purples{errori di tabulazione}}: vengono immessi dal programmatore o dal programma dati errati (cosa che ad esempio era comune una volta quando bisognava tabulare manualmente numeri con molte cifre). 

\smsp

Errori di questo tipo hanno causato nel 1996 la perdita del razzo Ariane 5 per una cattiva conversione di un numero, il crollo di una piattaforma petrolifera nel mare del Nord (Norvegia) nel 1991 e la distruzione del veicolo spaziale Mars Climate orbiter nel 1999 (cf. \cite{A1}, \cite{A2}).
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Alcune problematiche numeriche}
\begin{itemize}
\item {\purples{errori dovuti a misure fisiche}}: sono dovuti a una {\underline{imprecisa osservazione sperimentale}}, spesso dovuta agli strumenti utilizzati, ad esempio la velocit\'a della luce nel vuoto \mye
$$
c=(2.997925+\epsilon)\cdot 10^{10} cm/s, \,\,\, |\epsilon| \leq 0.000003
$$
e quindi nei calcoli che hanno a che vedere con $c$ necessariamente si compie un errore;
\item  {\purples{errori di rappresentazione e di aritmetica di macchina}}: sono errori dovuti {\underline{all'arrotondamento o troncamento di un numero}}, e sono inevitabili quando si usa l'aritmetica floating-point; sono la sorgente principale di errore di alcuni problemi come ad esempio la soluzione di sistemi lineari. 
\end{itemize}

Di seguito vediamo alcune problematiche dovute agli errori di rappresentazione e di aritmetica di macchina. Per una buona serie di esempi si veda {\cite[p.46]{ATKHAN}}.

\end{frame}


\begin{frame}[fragile]
\frametitle{Valutazione di una funzione}

\vspace{0.25cm}

Nel valutare una funzione continua $$f: \Omega \subseteq \mathbb{R}  \rightarrow \mathbb{R} $$ in un punto $x \in \Omega$ bisogna tener conto che il dato $x$ pu\myo essere per varie ragioni affetto da errori
\begin{itemize}
\item misura e/o
\item di rappresentazione al calcolatore,
\end{itemize} 
cos\myi da essere approssimato con un certo ${{x}}_C$. 

\smsp

Di conseguenza, {\purples{invece di $f(x)$ si valuta $f({{x}}_C)$}} e ci si domanda se ci siano {\underline{considerevoli differenze nei risultati}}.
\end{frame}


\begin{frame}[fragile]
\frametitle{Valutazione di una funzione}
Una funzione $f$ risulta {\underline{difficile}} da valutare al calcolatore nel punto $x \neq 0$ in cui $f(x) \neq 0$ qualora a {\underline{piccoli errori (relativi) sui dati}}  $$\epsilon_{(x,x_C)}=\frac{|x-x_c|}{|x|}$$ corrispondano {\underline{grandi errori (relativi) sui risultati}} $$\epsilon_{(f(x),f(x_C))}=\frac{|f(x)-f(x_c)|}{|f(x)|}.$$ Quindi \mye importante discutere la quantit\mya
\begin{center}
\begin{tcolorbox}
\smnsp
\smnsp
$$ {\cal{K}}(f,x,x_c):=\frac{\epsilon_{(f(x),f(x_C))}}{\epsilon_{(x,x_C)}}=\frac{ |f(x)-f(x_c)|/|f(x)|}{|x-x_c|/|x|}= 
\frac{ |f(x)-f(x_c)||x|}{|x-x_c||f(x)|}
 .$$
\end{tcolorbox}
\end{center}
La valutazione di $f$ in un punto $x$ si dice {\purples{bencondizionata}} se a piccole variazioni relative sui dati corrispondono piccole variazioni sui risultati,  {\purples{malcondizionata}}  se ci\myo non avviene.
\end{frame}




\begin{frame}[fragile]
\frametitle{Valutazione di una funzione}
Se $f$ \mye derivabile con continuit\mya nel pi\myu piccolo intervallo $\cal{I}$ aperto contenente $x$ ed $x_c$, per il teorema della media (o di {\blues{\href{https://it.wikipedia.org/wiki/Teorema\_di\_Lagrange}{Lagrange}}}) abbiamo $${\purples{  {f(x)-f(x_c)=f^{\prime}(\xi) \cdot (x-x_c), \,\, \xi \in {\cal I},  }}}$$ e quindi da 
$$\frac{|f(x)-f(x_c)|}{|x-x_c|}= \frac{|f^{\prime}(\xi) \cdot (x-x_c)|}{|x-x_c|} =\frac{|f^{\prime}(\xi)| \cdot |x-x_c|}{|x-x_c|}= |f^{\prime}(\xi)| \approx |f^{\prime}(x)|$$ ricaviamo per

\smnsp

\begin{center}
\begin{tcolorbox}[width=5cm]
\smnsp
$${\cal{K}}(f,x)=\frac{|f^{\prime}(x)| |x|}{|f(x)|}$$
\end{tcolorbox}
\end{center}

che

\smnsp

\begin{eqnarray}
{\purples{{\cal{K}}(f,x,x_c)}}&=&\frac{ |f(x)-f(x_c)||x|}{|x-x_c||f(x)|} = \frac{|f(x)-f(x_c)|}{|x-x_c|} \cdot  \frac{|x|}{|f(x)|} \nonumber \\
&{\purples{\approx}}& {\purples{\frac{|f^{\prime}(x)| |x|}{|f(x)|}:={\cal{K}}(f,x)}}. \nonumber
\end{eqnarray}
\end{frame}




\begin{frame}[fragile]
\frametitle{Valutazione di una funzione}
\begin{itemize}
\item La quantit\mya $${\cal{K}}(f,x)=\frac{|f^{\prime}(x)| |x|}{|f(x)|}$$ si chiama {\purples{condizionamento}} di $f$ nel punto $x$. 

\item In virtu' della definizione di ${\cal{K}}(f,x,x_C)$, essendo $${\cal{K}}(f,x) \approx {\cal{K}}(f,x,x_C),$$ pi\myu piccola risulta ${\cal{K}}(f,x)$ e meno la funzione amplifica un piccolo errore sul dato $x$. 
\item Naturalmente la funzione pu\myo essere {\purples{bencondizionata}} su un certo dato $x_1 \in \Omega$ e {\purples{malcondizionata}} su un certo altro $x_2  \in \Omega$.
\item Il condizionamento di una funzione non dipende dall'algoritmo con cui viene valutata, ma \mye inerente alla funzione stessa $f$ e al dato $x$.
\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Valutazione di una funzione: esempio 1}

\begin{esempio}

Data la funzione
$$f_1(x)=1-\sqrt{1-x^2}$$
calcoliamo analiticamente il {\purples{condizionamento}}
$${\cal{K}}(f_1,x)=\frac{|  x| \cdot |f_1^{\prime}(x)|}{|f_1(x)|} $$
Ricordiamo che
$$
f^{\prime}_1(x)={\frac{-1}{2 \sqrt{1-x^2}}} (-2x)={\frac{x}{\sqrt{1-x^2}}}
$$

\noindent da cui per $x \in (-1,1)$, essendo $|x|^2=x^2$,
$${\cal{K}}(f_1,x)=\frac{|  x |\cdot |f_1^{\prime}(x)|}{|f_1(x)|} = \frac{|  x| \cdot   |{\frac{x}{\sqrt{1-x^2}}}   |}{|1-\sqrt{1-x^2}|} = \frac{x^2}{|1-\sqrt{1-x^2}|\sqrt{1-x^2} }.$$
\end{esempio}
\end{frame}

\begin{frame}[fragile]
\frametitle{Valutazione di una funzione: esempio 1}
\begin{esperimento}
{\small{
Se 
\begin{itemize}
\item $x=1-{\mbox{\tt{eps}}} = 0.9999999999999998\ldots$, 
\item $x_C=1-3 \cdot {\mbox{\tt{eps}}}=0.9999999999999993\ldots$, 
\end{itemize}
pur essendo l'errore relativo tra $x$ e $x_C$ pari a $$\epsilon_{(x,x_C)} \approx 4.4 \cdot 10^{-16}$$ abbiamo che
\begin{itemize}
\item $f_1(x)=0.9999999789265758\ldots$,
\item $f_1(x_C)=0.9999999634997585\ldots$,
\end{itemize}

\smsp

con un maggior error relativo sulle valutazioni della funzione ovvero $$\epsilon_{(f_1(x),f_1(x_C))}\approx 1.5 \cdot 10^{-8}.$$ 
Questo fenomeno \'e prevedibile visto che
\begin{itemize}
\item ${\cal{K}}(f_1,x,x_C)  \approx 3.47 \cdot 10^7$, 
\item ${\cal{K}}(f_1,x) \approx 4.74 \cdot 10^7$.
\end{itemize}
}}
\end{esperimento}
\end{frame}

\begin{frame}[fragile]
\frametitle{Valutazione di una funzione: esempio 1}
\noindent Dal grafico di tale funzione nella Figura, si vede che la funzione {\purples{$f_1$ \mye ben condizionata in $(-0.9,0.9)$, ma non lo \mye per valori prossimi a $-1$, $+1$}}.

 \begin{figure}[h!]\label{fig1_cond}
 \centering
   {\includegraphics[scale=0.15,clip]{cond_1C.jpg}}
   {\includegraphics[scale=0.15,clip]{cond_1_zoomC.jpg}}
 \caption{A sinistra il grafico di ${\cal{K}}(f_1,x)$ in $(-1,1)$, a destra quello di ${\cal{K}}(f_1,x)$ in $(1-10^{-4},1)$ (
 per $|x| \approx 1$).}
 \end{figure}


\end{frame}


\begin{frame}[fragile]
\frametitle{Valutazione di una funzione: esempio 2}

\begin{esempio}
 Consideriamo quale esempio
 $$f_2(x)=1-x.$$
 Non \mye difficile vedere che $f^{\prime}_2(x)=-1$ e quindi
 $${\cal{K}}(f_2,x)=\frac{|  x \cdot f_2^{\prime}(x)|}{|1-x|}=\frac{|  x \cdot (-1)|}{|1-x|}=\frac{|  x \cdot (-1)|}{|1-x|}.$$
 \begin{itemize}
 \item Dal grafico di tale funzione nella Figura, si vede che la funzione {\purples{$f_2$ \mye ben condizionata ovunque eccetto per valori prossimi a $1$}}. 
 \item Si osservi che per vicini a tale valore, in effetti, si ha il fenomeno di cancellazione.
  \end{itemize}
\end{esempio}
\end{frame}


\begin{frame}[fragile]
\frametitle{Valutazione di una funzione: esempio 2}
 \begin{figure}[h!]\label{fig2_cond}
 \centering
   {\includegraphics[scale=0.20,clip]{cond_2.jpg}}
 \caption{Il grafico di ${\cal{K}}(f_2,x)$ in $(-2,2)$ (malcondizionamento per $x \approx 1$).}
 \end{figure}
 


\end{frame}



\begin{frame}[fragile]
\frametitle{Stabilit\mya}

Nell'analisi del condizionamento ${\cal{K}}(f,x)$ di una funzione continua $f$ in un punto $x$ del suo dominio, abbiamo supposto che $f$ sia valutabile esattamente e quindi che ${\cal{K}}(f,x)$ non dipenda dall'algoritmo utilizzato.

\begin{definizione}[Algoritmo stabile]
Un algoritmo per la risoluzione di un certo problema si dice {\purples{stabile}} se amplifica {\purples{poco}} gli errori di arrotondamento introdotti dalle singole operazioni. 
\end{definizione}

\begin{itemize}
\item Il problema non \mye necessariamente la valutazione di una funzione continua in un punto, ma pu\myo essere la risoluzione di una equazione di secondo grado, il calcolo di $\pi$ greco, la valutazione di una successione, etc. 
\item Osserviamo inoltre che nel caso della valutazione in un punto $x$ di una funzione $f$ bencondizionata, si possono ottenere risultati non sufficientemente corretti se il problema \mye affrontato con un algoritmo instabile. 
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 1: Calcolo di una radice in una equazione di secondo grado}


Vediamo un esempio concreto in cui l'introdurre una sottrazione potenzialmente pericolosa conduce effettivamente a problemi di 
instabilit\mya della soluzione e come rimediare.

\begin{esempio}
Dato il polinomio di secondo grado $x^2 + 2\,p x -q$, con 
{\purples{$q \geq 0$}} (e quindi $p^2+q \geq 0$), calcolare la 
radice maggiore
\begin{center}
\begin{tcolorbox}[width=7cm]
\begin{equation}\label{quadeq}
y=-p+{\sqrt{p^2+q}}.
\end{equation}
\end{tcolorbox}
\end{center}
\end{esempio}

Osserviamo che 
\begin{itemize}
\item essendo ${{p^2+q}}\geq 0$ le radici 
\begin{equation}\label{quadeq2}
y=-p \pm {\sqrt{p^2+q}}.
\end{equation}
dell'equazione sono {\purples{reali}};
\item la soluzione descritta in (\ref{quadeq}) \mye la {\purples{maggiore}} di quelle presenti in (\ref{quadeq2}) poich\'e $\sqrt{p^2+q} \geq 0$,
\item \mye {\purples{non negativa}} visto che se $q > 0$ allora $\sqrt{p^2+q} > p$. 
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 1: Calcolo di una radice in una equazione di secondo grado}

\begin{enumerate}
\item Si osserva subito che se $p \geq 0$ allora la valutazione $y=-p+{\sqrt{p^2+q}}$ \mye {\purples{potenzialmente instabile per $p \gg q$}} a causa della sottrazione tra $p$ e $ {\sqrt{p^2+q}} \approx |p|$. 

\smsp

A tal proposito, dopo averla implementata in Matlab, verificheremo numericamente la perdita di accuratezza per opportune scelte dei 
coefficienti $p$ e $q$. 
\item Risultati migliori si ottengono con una formula alternativa (e stabile) ricavata {\purples{razionalizzando}} $y=-p+{\sqrt{p^2+q}}$:
\begin{eqnarray}\label{quadeqr}
y&=&-p+{\sqrt{p^2+q}}={\frac{(-p+{\sqrt{p^2+q}})(p+{\sqrt{p^2+q}})}{p+{\sqrt{p^2+q}}}} \nonumber \\ &=&\frac{-p^2+(p^2+q)} {p+{\sqrt{p^2+q}}}={\frac{q} {p+{\sqrt{p^2+q}}} }.
\end{eqnarray}
\end{enumerate}
\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 1: Calcolo di una radice in una equazione di secondo grado e condizionamento}

Ricordiamo ora che un {\underline{\purples{problema}}} si dice {\purples{bencondizionato}} (o {\purples{malcondizionato}}) a seconda che nel particolare contesto le perturbazioni sui dati non influenzino (o influenzino) eccessivamente i risultati. 

\smsp

Nel caso di un {\underline{\purples{algoritmo}}}, per indicare un simile comportamento rispetto alla propagazione degli errori dovute alle perturbazioni sui dati, si parla rispettivamente di
\begin{itemize}
\item {\purples{algoritmo bencondizionato}} o stabile, 
\item {\purples{algoritmo malcondizionato}} o instabile {\cite[p. 66]{COM}}.
\end{itemize}

\smsp

\begin{importante}
Seguendo {\cite[p. 10]{COM}}, {\cite[p. 78]{COM}}, indipendentemente dall'algoritmo utilizzato, {\purples{il problema}} della determinazione della radice $y=-p+{\sqrt{p^2+q}}$ \mye
\begin{itemize}
\item {\purples{bencondizionato}}  per $q>0$,
\item {\purples{malcondizionato}} per $q \approx -p^2$. 
\end{itemize}
Di conseguenza il problema che abbiamo considerato era bencondizionato (in quanto si supponeva $q > 0$).
\end{importante}

\end{frame}



\begin{frame}[fragile]
\frametitle{Esempio 1: Calcolo di una radice in una equazione di secondo grado e condizionamento}
Usando dei classici ragionamenti dell'analisi numerica si mostra che (cf. {\cite{STO}}, p. 21, {\cite{COMESE}}, p. 11)
{\smsp}
\begin{enumerate}
\item il primo algoritmo (\ref{quadeq2}) non \mye {\purples{numericamente stabile}} qualora $p \gg q > 0$; 
{\smsp}
\item  il secondo algoritmo (\ref{quadeqr}) \mye {\purples{numericamente stabile}} qualora $p \gg q  > 0$. 
\end{enumerate}
nonostante in queste ipotesi il problema sia stabile.
\end{frame}



\begin{frame}[fragile]
\frametitle{Esempio 1: Calcolo di una radice in una equazione di secondo grado, test 1}

\noindent Vediamo alcuni casi rilevanti, effettuati in doppia precisione.

\vspace{0.25cm}


{\purples{1.}}  In {\cite[p.22]{STO}}, si suggerisce un test interessante per $$p=1000, \, q=0.018000000081$$ la cui soluzione esatta \mye $0.9 \,\cdot\,10^{-5}$. Si ha $p \gg q$.

\smsp

Lavorando in doppia precisione otteniamo

\vspace{0.25cm}

\begin{center}
\begin{tabular}{| c | c | c |}
\hline
{\mbox{algoritmo}}  & {\mbox{valore}} & {\mbox{err. rel.}} \\
\hline
$1$ &  $0.0000089999999772772$ & $2.52\cdot 10^{-9}$ \\
$2$ & $ 0.0000090000000000000 $ & $0$ \\
\hline
\end{tabular}
\end{center}

\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 1: Calcolo di una radice in una equazione di secondo grado, test 2}

{\purples{2.}} Secondo {\cite[p.11]{COMESE}}, \mye notevole l'esperimento in cui $$p=4.999999999995 \cdot 10^{+4}, \, q=10^{-2}$$ avente soluzione esatta $10^{-7}$.
Nuovamente $p \gg q$.

\smsp

Lavorando in doppia precisione otteniamo

\begin{center}
\begin{tabular}{| c | c | c |}
\hline
{\mbox{algoritmo}}  & {\mbox{valore}} & {\mbox{err. rel.}} \\
\hline
$1$ &  $0.0000001000007614493$ & $7.61\cdot 10^{-6}$ \\
$2$ & $ 0.0000001000000000000 $ & $0$ \\
\hline
\end{tabular}
\end{center}

\vspace{0.25cm}

\end{frame}


\begin{frame}[fragile]
\frametitle{Esempio 2: Approssimazione di $\pi$}

\smnsp

\begin{esempio}
{\footnotesize{
Studiamo le successioni {\purples{$\{u_n\}$}}, {\purples{$\{z_n\}$}}, definite rispettivamente come
$$\left\{ \begin{array} {l}  
s_1=1, \, \, s_2=1+{\frac {1}{4}} \\
u_1=1, \, \, u_2=1+{\frac {1}{4}} \\
s_{n+1} = s_{n} +{\frac {1}{(n+1)^2}} \\
{\purples{u_{n+1}}}= {\sqrt {6 \, s_{n+1} }} 
\end{array} \right.$$
e
$$\left\{ \begin{array} {l}  
z_1=1, \, \, z_2=2 \\
z_{n+1} = 2^{n- { \frac {1} {2} } }      { \sqrt { 1 - \sqrt{1-4^{1-n} 
\cdot z_n^2}   } } 
\end{array} \right.$$
che {\purples{teoricamente}} convergono a $\pi=3,14159 26535 89793 238 \ldots.$

\smsp

Implementiamo di seguito una terza successione, diciamo {\purples{$\{y_{n}\}$}}, che si ottiene 
{\purples{razionalizzando}} $z_n$, cio\mye moltiplicando numeratore e denominatore 
per 
$$ { \sqrt { 1 + \sqrt{1-4^{1-n} \cdot z_n^2}   } } $$
e calcoliamo $u_m$, $z_m$ e $y_m$ per $m=2,3,\ldots,40$ (che teoricamente dovrebbero approssimare $\pi$).
}}
\end{esempio}
\end{frame}



\begin{frame}[fragile]
\frametitle{Esempio 2: Approssimazione di $\pi$}
Si ottengono i seguenti risultati, che tabuliamo per semplicit\mya esclusivamente per $n=5,10,15,20,25,30,35,40$.

\vspace{0.35cm}

\begin{tabular}{| c | c | c | c |}
\hline
$n$  & $u_n$ & $z_n$ & $y_n$ \\
\hline
 	 $  5$ & $2.963387701038571$ & $3.121445152258050$ & $3.121445152258053$ \\
 	 $ 10$ & $3.049361635982070$ & $3.141572940365566$ & $3.141572940367093$ \\
 	 $ 15$ & $3.079389826032086$ & $3.141592633463248$ & $3.141592634338565$ \\
 	 $ 20$ & $3.094669524113704$ & $3.141594125195191$ & $3.141592653570997$ \\
 	 $ 25$ & $3.103923391700576$ & $3.142451272494133$ & $3.141592653589779$ \\
 	 $ 30$ & $3.110128728141262$ & $4.000000000000000$ & $3.141592653589798$ \\
 	 $ 35$ & $3.114578862293132$ & $0.000000000000000$ & $3.141592653589798$\\
 	 $ 40$ & $3.117926198299378$ & $0.000000000000000$ & $3.141592653589798$\\
\hline
\end{tabular}

\end{frame}



\begin{frame}[fragile]
\frametitle{Esempio 2: Approssimazione di $\pi$}

 \begin{figure}[h!]\label{pigreco}
 \centering
   {\includegraphics[scale=0.35,clip]{pigreco2.eps}}
 \caption{Errori relativi delle tre successioni  $u_n$ (puntino nero), $z_n$ (punto magenta), $y_n$ (cerchietto rosso). Risulta evidente che $z_n$ diverge, nonostante fino a $n \approx 14$ dia circa gli stessi valori di $y_n$ che invece converge.}
 \end{figure}
 
\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 2: Approssimazione di $\pi$}

Dalla figura e dalla tabella, consegue che
\begin{itemize}
\item la convergenza della {\purples{prima successione}} \mye estremamente {\underline{lenta}}, mentre quella della terza \mye pi\myu rapida;
\item la {\purples{seconda successione}} {\underline{non converge numericamente}}, seppure converga teoricamente; il principale problema \mye la cancellazione che si ha nell'argomento della radice quadrata pi\myu esterna di 
$$
z_{n+1} = 2^{n- { \frac {1} {2} } }      { \sqrt { 1 - \sqrt{1-4^{1-n} \cdot z_n^2}   } } ;
$$
\end{itemize}


\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 2: Approssimazione di $\pi$}

In tabella evidenziamo i valori assunti da $\sqrt{1-4^{1-n} \cdot z_n^2}$, per $n=5,10,15,\ldots,40$.

\begin{center}
\begin{tabular}{| c | c | c |} %\label{tabrad}
\hline
$n$  & $     \sqrt{1-4^{1-n} \cdot z_n^2} $ & $       { \sqrt { 1 - \sqrt{1-4^{1-n} \cdot z_n^2}   } }  $ \\
\hline
 	 $ 5$ & $9.8078528040323054160154470e-01$ & $1.38617e-01$ \\
 	 $10$ & $9.9998117528260110908888691e-01$ & $4.33875e-03$\\
 	 $15$ & $9.9999998161642922323011362e-01$ & $1.35586e-04$\\
 	 $20$ & $9.9999999998204724960260137e-01$ & $4.23707e-06$\\
 	 $25$ & $9.9999999999998245847621092e-01$ & $1.32444e-07$\\
 	 $30$ & $1.0000000000000000000000000e+00$ & $0.00000e+00$\\
 	 $35$ & $1.0000000000000000000000000e+00$ & $0.00000e+00$\\
 	 $40$ & $1.0000000000000000000000000e+00$ & $0.00000e+00$\\
\hline
\end{tabular} 	 
\end{center}
\vspace{0.35cm}

L'ultima colonna evidenzia che per $n \geq 30$ si ha che $z_n=0$, in quanto $
z_{n+1} = 2^{n- { \frac {1} {2} } }      { \sqrt { 1 - \sqrt{1-4^{1-n} \cdot z_n^2}   } } 
$.

\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 3: Successione ricorrente}

In questa sezione mostriamo come alcune formule di ricorrenza in avanti possano essere instabili, mentre d'altro canto le relative versioni all'indietro possono essere stabili. 

\smsp 

Problemi simili con una precisa discussione della propagazione dell'errore sono trattati pure in {\cite[p. 23, problema 11]{FRO}}
\begin{esempio}
Si valuti numericamente la successione
\begin{center}
\begin{tcolorbox}[width=6cm]
\smnsp
\begin{equation}\label{321}
I_n=e^{-1} \int_0^1 x^n \, e^x \, dx
\end{equation}
\end{tcolorbox}
\end{center}
\end{esempio}

\smnsp

\begin{proposizione}
La successione $I_n$ \mye positiva,  decrescente e infinitesima (cio\mye $\lim_n I_n=0$) ed \'e 
\begin{center}
\begin{tcolorbox}[width=7cm]
\smnsp
\smnsp
$$I_{n+1} =1-(n+1)\, I_n, \,\,\, I_0=1-e^{-1}.$$
\end{tcolorbox}
\end{center}
\end{proposizione}

\end{frame}


\begin{frame}[fragile]
\frametitle{Esempio 3: Successione ricorrente}

\begin{itemize}
\item Essendo 
$$I_{n+1} =1-(n+1)\, I_n, \,\,\, I_0=1-e^{-1},$$
abbiamo che tutti i termini sono valutabili ricorsivamente, ad esempio
\begin{eqnarray}
I_1&=&1-I_0=1-(1-e^{-1})=e^{-1}, \nonumber \\
I_2&=&1-2 \cdot I_1=1-2 \cdot e^{-1}. \nonumber 
\end{eqnarray}
\item Portando $I_{n+1} $ e $-(n+1)\, I_n$ risp. a primo e secondo membro, si ha
$$I_{n+1} =1-(n+1)\, I_n \Leftrightarrow
(n+1)\, I_n =1-I_{n+1} 
$$
e dividendo ambo i membri di quest'ultima per $n+1$
$$
I_n =\frac{1-I_{n+1}}{n+1}
$$
per cui visto che per $n^* \gg 0$ si ha $I_{n^*} \approx 0$, in quanto la successione \mye infinitesima, si pu\myo considerare la successione {\purples{all'indietro}}

\begin{center}
\begin{tcolorbox}[width=7cm]
\smnsp
\smnsp
$$I_n =\frac{1-I_{n+1}}{(n+1)}, I_{n^*}=0, \,\, n=n^*-1,\ldots,1.$$
\end{tcolorbox}
\end{center}
\end{itemize}
\end{frame}




\begin{frame}[fragile]
\frametitle{Esempio 3: Successione ricorrente}

Riassumendo, se desideriamo {\purples{calcolare $I_1,\ldots,I_{100}$}}:

\smsp

{\purples{1.}} Come primo tentativo calcoliamo $I_n$ per $n=1,\ldots, 100$ mediante la successione {\purples{in avanti}}
$$\left\{ \begin{array}{l}  
s_1=e^{-1}\\
s_{n+1} = 1-(n+1) \, s_{n}
\end{array} \right.$$

{\purples{2.}} Come alternativa, fissato $m=500$, calcoliamo la successione {\purples{all'indietro}}
$\{t_n\}_{n=1,\ldots,500}$ definita come 
$$\left\{ \begin{array}{l}  
t_{500}=0\\
t_{n-1} = {\frac {1-t_n} {n}}
\end{array} \right.$$
Si osservi che per raggiungere tale obiettivo bisogna calcolare i termini 
$$t_{500}, \,t_{499},\ldots,t_{100},t_{99},\ldots,t_2,t_1.$$
\end{frame}


\begin{frame}[fragile]
\frametitle{Esempio 3: Successione ricorrente}

Dopo aver eseguito i calcoli, otteniamo per $n=10,20,\ldots,100$ la seguente tabella in cui si evince che in effetti 
\begin{itemize}
\item {\purples{$s_n$}} a differenza di $I_n$ non \mye infinitesima, positiva e decrescente, 
\item {\purples{$t_n$}} fornisce risultati compatibili con le propriet\'a della successione.
\end{itemize}

\smsp

La motivazione di tale comportamento consiste nel fatto che la prima successione, cio\mye quella in avanti, amplifica enormemente l'errore in avanti mentre la seconda, detta all'indietro, fa esattamente il contrario.


\vspace{0.35cm}

\begin{center}
\begin{tabular}{| c | c | c |} %\label{tab45}
\hline
$n$  & $  s_n $ & $  t_n $\\
\hline
 	 $ 10$ & $8.387707005829270e-02$ & $8.387707010339417e-02$ \\
 	 $ 20$ & $-3.019239488558378e+01$ & $4.554488407581805e-02$\\
 	 $ 30$ & $-3.296762455608386e+15$ & $3.127967393216808e-02$\\
 	 $ 40$ & $-1.014081007335147e+31$ & $2.382272866903348e-02$\\
 	 $ 50$ & $-3.780092725853228e+47$ & $1.923775443433938e-02$\\
 	 $ 60$ & $-1.034194991387092e+65$ & $1.613316466384628e-02$\\
 	 $ 70$ & $-1.488787166378969e+83$ & $1.389153285400528e-02$\\
 	 $ 80$ & $-8.895191521232202e+101$ & $1.219691454831806e-02$\\
 	 $ 90$ & $-1.846559775027300e+121$ & $1.087083605943215e-02$\\
 	 $100$ & $-1.159928542966359e+141$ & $9.804855005376052e-03$\\
\hline
\end{tabular} 	 
\end{center}

\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 3: Successione ricorrente}
{\footnotesize{
\begin{osservazione}[Facoltativa]
In effetti anche se operassimo in aritmetica esatta, supponiamo
\begin{itemize}
\item {\purples{successione esatta}}: $$I_{n+1}=1-(n+1)I_n,  {\mbox{       }} I_0=1-e^{-1},$$
\item {\purples{successione valutata esattamente ma con errore iniziale}}: $$I^*_{n+1}=1-(n+1)I^*_n,  {\mbox{       }} I^*_0=I_0+\epsilon=(1-e^{-1})+\epsilon,$$
\end{itemize}
allora si vede che 
\begin{center}
\begin{tcolorbox}[width=4cm]


$$I^*_n-I_n=n! \epsilon$$

\end{tcolorbox}
\end{center}
 in quanto
\begin{itemize}
\item l'asserto $I^*_n-I_n=n! \epsilon$ vale per $n=0$, visto che $I^*_0-I_0 =0! \epsilon=\epsilon$;
\item se supponiamo $I^*_n-I_n=n! \epsilon$, ovvero $I^*_n=I_n-n! \epsilon$ allora
\begin{eqnarray}
I^*_{n+1}&=&1-(n+1)I^*_{n}=1-(n+1)(I_n-n! \epsilon) \nonumber \\ 
&=&1-(n+1)I_n+(n+1) \cdot (n! \epsilon) = I_{n+1}+(n+1)! \epsilon. \nonumber 
\end{eqnarray}
\end{itemize}
\end{osservazione}
}}
\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 4: sulla somma ${\frac {(1+\eta)-1} {\eta} }$}

\begin{esempio}
Calcoliamo l'errore relativo tra $1$ e il valore che si ottiene
valutando in doppia precisione 
\begin{center}
\begin{tcolorbox}[width=5cm]
\smnsp
\smnsp
$$f(\eta)={\frac {(1+\eta)-1} {\eta} }$$   
\end{tcolorbox}
\end{center}

con $\eta=10^{-1}, 10^{-2}, \ldots, 10^{-15}$. 
\end{esempio}

Ovviamente il risultato esatto di questa divisione \mye sempre $1$, per qualsiasi $\eta$. 

\smsp

Si tratta di una {\purples{funzione ben condizionata}} visto che $f(x)=1$, che per\myo pu\myo essere valutata in forme diverse, pi\myu o meno favorevoli (come nel nostro caso). 

\smsp

Risulta quindi importante capire che nell'esempio in questione, il fatto che avremo {\purples{risultati inaspettati}}, differentemente da quanto visto per funzioni $f$ malcondizionate, {\purples{sar\'a dovuto all'algoritmo di calcolo}}.

\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 4: sulla somma ${\frac {(1+\eta)-1} {\eta} }$}

\begin{itemize}
\item Notiamo che il calcolatore effettuer\mya invece
$f^*(\eta) $
ottenuta
\begin{enumerate}
\item valutando $a_1=fl(fl(1)+fl(\eta))$;
\item valutando $a_2=fl(fl(a_1)-fl(1))$;
\item valutando $a_3=fl(fl(a_2) / fl(\eta))$.
\end{enumerate}
in cui ovviamente $fl(1)=1$, $fl(a_1)=a_1$, $fl(a_2)=a_2$ visto che $a_1$, $a_2$ sono numeri floating point.

\item Per $\eta \approx 0$, avremo problemi a calcolare correttamente il numeratore $(1+\eta)-1$, causa il fenomeno di cancellazione.
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 4: sulla somma ${\frac {(1+\eta)-1} {\eta} }$}

\begin{center}
\begin{tabular}[h!]{| c | c | c |} 
\hline
$\eta$  & $f^*(\eta)$ & ${\mbox{rel.err.}}$ \\
\hline
 	 $1.00e-01$ & $1.000000000000001e+00$ & $8.881784e-16$ \\
 	 $1.00e-02$ & $1.000000000000001e+00$ & $8.881784e-16$ \\
 	 $1.00e-03$ & $9.999999999998899e-01$ & $1.101341e-13$ \\
 	 $1.00e-04$ & $9.999999999998899e-01$ & $1.101341e-13$ \\
 	 $1.00e-05$ & $1.000000000006551e+00$ & $6.551204e-12$ \\
 	 $1.00e-06$ & $9.999999999177334e-01$ & $8.226664e-11$ \\
 	 $1.00e-07$ & $1.000000000583867e+00$ & $5.838672e-10$ \\
 	 $1.00e-08$ & $9.999999939225290e-01$ & $6.077471e-09$ \\
 	 $1.00e-09$ & $1.000000082740371e+00$ & $8.274037e-08$ \\
 	 $1.00e-10$ & $1.000000082740371e+00$ & $8.274037e-08$ \\
 	 $1.00e-11$ & $1.000000082740371e+00$ & $8.274037e-08$ \\
 	 $1.00e-12$ & $1.000088900582341e+00$ & $8.890058e-05$ \\
 	 $1.00e-13$ & $9.992007221626409e-01$ & $7.992778e-04$ \\
 	 $1.00e-14$ & $9.992007221626409e-01$ & $7.992778e-04$ \\
 	 $1.00e-15$ & $1.110223024625157e+00$ & $1.102230e-01$ \\
\hline
%\caption{I valori assunti per valutare numericamente per certi $\eta$ la quantit\mya ${\frac {(1+\eta)-1} {\eta} }$.}
\end{tabular}
\end{center}

\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 4: sulla somma ${\frac {(1+\eta)-1} {\eta} }$}

\smnsp

\begin{nota}[Facoltativa]

La perdita di precisione \mye dovuta essenzialmente al fenomeno di cancellazione, visto che per $\eta \approx 0$ si ha $1+\eta \approx 1$. 

Ricordato che {\tt{eps}} \mye un numero macchina e che per numeri pi\myu piccoli $\eta$ in modulo di {\tt{eps}} si ha $1+x=1$ non sorprende inoltre sia

\vspace{0.25cm}

\begin{center}
\begin{tabular}[h!]{| c | c | c |} 
\hline
$\eta$  & $f^*(\eta)$ & ${\mbox{rel.err.}}$ \\
\hline
 ${\mbox{{\tt{eps}}}}$ & $1.000000000000000e+00$ & $0.000000e+00$ \\
 	 ${\mbox{{\tt{eps/2}}}}$ & $0.000000000000000e+00$ & $1.000000e+00$ \\
 	 ${\mbox{{\tt{eps/3}}}}$ & $0.000000000000000e+00$ & $1.000000e+00$ \\
\hline
%\caption{I valori assunti per valutare numericamente per certi $\eta$ la quantit\mya ${\frac {(1+\eta)-1} {\eta} }$.}
\end{tabular}
\end{center}

In effetti, per questi ultimi valori $\eta$ pi\myu piccoli in modulo di {\tt{eps}}, visto che comunque $fl(\eta) > 0$ (pensarci su!),
$$
{\frac {(1+fl(\eta))-1} {fl(\eta)} }={\frac {1-1} {fl(\eta)} }=0.
$$

\smsp

\end{nota}
\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 5: Sulla valutazione di $\tan(\arctan(x))=x$}

\begin{esempio}
Siano $f(x):=\tan(x)$ e $g(x):=\arctan(x)$. Si consideri la funzione composta 

\begin{center}
\begin{tcolorbox}[width=10.5cm]
\smnsp
\smnsp
$$F(x):=f \circ g(x):=f(g(x))=\tan(\arctan(x))=x, \,\,x \in (-\infty,+\infty).$$ 
\end{tcolorbox}
\end{center}

Ci domandiamo se l'implementazione numerica di questa funzione goda ancora di questa propriet\'a.
\end{esempio}

Valutiamo la funzione $F=f \circ g$ numericamente, mediante la corrispettiva versione numerica $F^*$ per
$$x=10^{k}, {\mbox{ per }}  k=-20,-16,-12,-8,\dots,8,12,16,20,$$ 
nonch\mye l'errore relativo {\tt{rel.err.}} compiuto, ovvero $${\mbox{{\tt{rel.err.}}}}:=|F(x)-F^*(x)|/|F(x)|,$$ notando che $F(x) \neq 0$ visto che nei casi in questione si ha $x \neq 0$.

\end{frame}

\begin{frame}[fragile]
\frametitle{Esempio 5: Sulla valutazione di $\tan(\arctan(x))=x$}
Descriviamo questi risultati nella tabella che segue.

\begin{center}
\begin{tabular}[h!]{| c | c | c |} 
\hline
$x$  & $F^*(x)$ & ${\mbox{rel.err.}}$ \\
\hline
 	 $1.0e-20$ & $1.000000000000000e-20$ & $0.00000e+00$ \\
 	 $1.0e-16$ & $1.000000000000000e-16$ & $0.00000e+00$ \\
 	 $1.0e-12$ & $1.000000000000000e-12$ & $0.00000e+00$ \\
 	 $1.0e-08$ & $1.000000000000004e-08$ & $0.00000e+00$ \\
 	 $1.0e-04$ & $1.000000000000000e-04$ & $0.00000e+00$ \\
 	 $1.0e+00$ & $9.999999999999999e-01$ & $1.11022e-16$ \\
 	 $1.0e+04$ & $9.999999999990539e+03$ & $9.46056e-13$ \\
 	 $1.0e+08$ & $9.999999999542369e+07$ & $4.57631e-11$ \\
 	 $1.0e+12$ & $1.000071916854289e+12$ & $7.19117e-05$ \\
 	 $1.0e+16$ & $1.633123935319537e+16$ & $3.87677e-01$ \\
 	 $1.0e+20$ & $1.633123935319537e+16$ & $6.12223e+03$\\
 	 \hline
\end{tabular}
\end{center}

\end{frame}






\begin{frame}[fragile]
\frametitle{Esempio 5: Sulla valutazione di $\tan(\arctan(x))=x$}

Osserviamo che i valori critici sono tra $1$ e $10^4$. In effetti un ulteriore analisi propone

\vspace{0.25cm}

\begin{center}
\begin{tabular}[h!]{| c | c | c |} 
\hline
$x$  & $F^*(x)$ & ${\mbox{rel.err.}}$ \\
\hline
$1.000000000000000e+00$ & $9.999999999999999e-01$ & $1.11022e-16$ \\
 	 $2.511886431509580e+00$ & $2.511886431509580e+00$ & $0.00000e+00$\\
 	 $6.309573444801933e+00$ & $6.309573444801929e+00$ & $7.03834e-16$\\
 	 $1.584893192461114e+01$ & $1.584893192461114e+01$ & $1.12081e-16$\\
 	 $3.981071705534973e+01$ & $3.981071705534988e+01$ & $3.56961e-15$\\
 	 $1.000000000000000e+02$ & $1.000000000000010e+02$ & $1.00897e-14$\\
 	 $2.511886431509580e+02$ & $2.511886431509614e+02$ & $1.38042e-14$\\
 	 $6.309573444801930e+02$ & $6.309573444802187e+02$ & $4.07210e-14$\\
 	 $1.584893192461114e+03$ & $1.584893192461186e+03$ & $4.54778e-14$\\
 	 $3.981071705534973e+03$ & $3.981071705533795e+03$ & $2.95849e-13$\\
 	 $1.000000000000000e+04$ & $9.999999999990539e+03$ & $9.46056e-13$\\
 	 \hline
\end{tabular}
\end{center}

Quindi numericamente $F$ e $F^*$ non coincidono, anche per valori non eccessivi di $x$.


\end{frame}


\begin{frame}[fragile]
\frametitle{Complessit\mya computazionale}

\begin{itemize}
\item Descriviamo in questa sezione alcuni problemi in cui mostriamo come pur fornendo in aritmetica esatta lo stesso risultato, abbiano {\purples{complessit\mya computazionale}} diversa, ovvero compiono un numero diverso di operazioni. 

\item Tipicamente, visto che nei primi computer il costo tra {\purples{operazioni moltiplicative}} e somme era molto diverso, si considerano solo prodotti (e quindi potenze) e divisioni.

\item Valuteremo alcuni algoritmi per la valutazione di polinomi in un punto, per la potenza di un numero e per il calcolo del determinante di una matrice.

\end{itemize}
\end{frame}





\begin{frame}[fragile]
\frametitle{Valutazione di polinomi: algoritmo 1}


Si supponga di dover valutare il polinomio di grado $n=4$
$$
p_4(x)=a_0 + a_1 x +a_2 x^2 + a_3 x^3 +a_4 x^4.
$$

{\purples{1.}} Se si implementa un metodo brutale, necessitano 

\begin{itemize}
\item $4$ somme;
\item $3$ potenze, e visto che 
\begin{eqnarray}
x^2&=&x \cdot x, \nonumber \\
x^3&=&x \cdot x \cdot x, \nonumber \\
x^4&=&x \cdot x \cdot x \cdot x,\nonumber
\end{eqnarray}
necessitano $1+2+3$ prodotti;
\item $4$ prodotti del tipo $a_k \cdot x^k$.
\end{itemize}
Quindi, per $n=4$ servono $4$ operazioni additive e $10$ moltiplicative.
\end{frame}

\begin{frame}[fragile]
\frametitle{Valutazione di polinomi}
Con questa tecnica in generale servono per valutare un polinomio di grado $n$
$$
p_n(x)=a_0 + a_1 x +\ldots +a_n x^n.
$$
nel generico punto $x$
\begin{itemize}
\item $n$ somme;
\item $n-1$ potenze, e visto che $x^k=x \cdot \ldots \cdot x $, necessitano $1+\ldots+(n-1)=(n-1)n/2$ prodotti.
\item $n$ prodotti del tipo $a_k \cdot x^k$.
\end{itemize}
e quindi {\purples{$\frac{(n-1)n}{2}+n=\frac{(n+1)n}{2} \approx \frac{n^2}{2}$ operazioni moltiplicative}}.

\smsp
\smsp

In effetti nell'esempio precedente, per ${\overline{n}}=4$ facevamo $10$ operazioni moltiplicative e in questo caso 

\begin{itemize}
\item $\frac{({\overline{n}}+1) \cdot {\overline{n}} }{2}=\frac{5 \cdot 4}{2}=10$;
\item $\frac{{\overline{n}}^2}{2}=\frac{16}{2}=8$.
\end{itemize}
\end{frame}




\begin{frame}[fragile]
\frametitle{Valutazione di polinomi: algoritmo 2}

Facendo un p\'o di attenzione \mye facile osservare che in realt\myash, per valutare $p_4$ servano
\begin{itemize}
\item $4$ somme;
\item $3$ potenze, e visto che $x^2=x \cdot x$, $x^3=x^2 \cdot x$, $x^4=x^3 \cdot x$, necessitano solo $3$ prodotti;
\item $4$ prodotti del tipo $a_k \cdot x^k$.
\end{itemize}

Quindi, il numero di operazioni moltiplicative con un algoritmo pi\myu furbo \mye pari a $7$. 

\smsp 

In generale, si vede che con questa tecnica servono {\purples{$2n-1$ operazioni moltiplicative}} per valutare un {\underline{polinomio}} $p$ {\underline{di grado esattamente $n$}}, nel generico punto $x$.
\end{frame}

\begin{frame}[fragile]
\frametitle{Valutazione di polinomi}

Osserviamo che nel caso dell'esempio del polinomio di grado $4$, 
\begin{eqnarray}\label{hb}
p_4(x)&=&a_0 + {\purples{a_1 x +a_2 x^2 + a_3 x^3 +a_4 x^4}} \nonumber \\
&=& a_0+x(a_1+ {\purples{a_2 x + a_3 x^2 +a_4 x^3}}) \nonumber \\
&=& a_0+x(a_1+x ( a_2 + {\purples{a_3 x +a_4 x^2}})) \nonumber \\
&=& \underbrace{a_0+x\underbrace{(a_1+x \underbrace{(a_2 + x \underbrace{ ( {{a_3+a_4 x}})}_{ {b_3}} }_{b_2}}_{b_1})}_{b_0} \nonumber 
\end{eqnarray}
e quindi {\it{valutate le parentesi}}, dalla pi\'u interna alla pi\'u esterna
\begin{itemize}
\item $b_3:=a_3+a_4 x$,
\item $b_2:=a_2+b_3 x$,
\item $b_1:=a_1+b_2 x$,
\item $b_0:=a_0+b_1 x$,
\end{itemize}
otteniamo {\purples{$p_4(x)=b_0$}}.

\end{frame}





\begin{frame}[fragile]
\frametitle{Valutazione di polinomi}
Quindi per valutare il polinomio nel generico punto $x$ servono {\purples{$4$ somme e solo $4$ prodotti}}, operazioni necessarie per calcolare nell'ordine $b_3,\ldots,b_0$, contro 
\begin{itemize}
\item le $4$ somme e i $10$ prodotti del primo algoritmo precedente,
\item le $4$ somme e i $7$ prodotti del secondo algoritmo precedente.
\end{itemize}
\smsp

Non \mye difficile vedere che in generale, con questa regola, usualmente detta di {\purples{Ruffini-Horner}} {\cite{WIKIHO}}, occorrono {\purples{$n$ operazioni moltiplicative}} per valutare il polinomio $p$ di grado $n$ nel generico punto $x$, quindi in numero inferiore rispetto
\begin{itemize}
\item ai $  \frac{(n+1)n}{2}$ prodotti del primo algoritmo precedente,
\item ai $2n-1$ prodotti del secondo algoritmo precedente.
\end{itemize}
\end{frame}



\begin{frame}[fragile]
\frametitle{Valutazione di polinomi}
\begin{esempio}
Valutare il polinomio $p_3(x)=2 x^3 +4 x^2 +5 x+7$ nel punto $x=2$, mediante l'algoritmo di Ruffini-Horner.
\end{esempio}
La {\purples{valutazione diretta}} comporta che per $x=2$
$${\purples{x^2}}=4, \smhsp {\purples{x^3}}=x^2 \cdot x=4 \cdot 2=8.$$

\smsp

Quindi 
$$
p_3(2)=2 \cdot 2^3 +4 \cdot 2^2 +5\cdot 2+7=16+16+10+7=49.
$$
Se contiamo i prodotti eseguiti, sono $2$ per le potenze e $3$ per la valutazione del polinomio, ovvero $5$ moltiplicazioni.
\end{frame}


\begin{frame}[fragile]
\frametitle{Valutazione di polinomi}
Valutiamo ora il polinomio $p_3(x)=2 x^3 +4 x^2 +5 x+7$ nel punto $x=2$, mediante l'algoritmo di {\purples{Ruffini-Horner}}.

\smsp

Essendo $a_0=7$, $a_1=5$, $a_2=4$, $a_3=2$, valutiamo in sequenza:

\begin{itemize}
\item $b_2:=a_2+a_3 x=4+2 \cdot 2=8$,
\item $b_1:=a_1+b_2 x=5+8 \cdot 2=21$,
\item $b_0:=a_0+b_1 x=7+21 \cdot 2=49$,
\end{itemize}

\noindent
raggiungendo il risultato con $3$ moltiplicazioni (invece delle $5$ del metodo diretto).

\end{frame}





\begin{frame}[fragile]
\frametitle{Calcolo delle potenza}

\begin{esempio}
Si calcoli {\red{$a^n$}} dove $a \in \R$ e $n \in \N$.
\end{esempio}

{\purples{1.}} Un metodo brutale, osservato che
$$
a^n=a \cdot \ldots \cdot a
$$
richiede $n-1$ operazioni moltiplicative.


{\purples{2.}} Sia $n=\sum_{j=0}^{m} c_j 2^j=c_0 2^0+c_1 2^1+\ldots c_m 2^m$ con $m=\lfloor \log_{2} n \rfloor$, la codifica binaria di $n$, allora 
\begin{eqnarray}\label{pf}
a^n&=&a^{c_0 2^0+c_1 2^1+c_2 2^2+\ldots c_m 2^m} =  a^{c_0 2^0} \cdot a^{c_1 2^1} \cdot a^{c_2 2^2} \ldots \ldots \cdot a^{c_m 2^m} \nonumber \\ &=& a^{c_0} \cdot ({a^{2}})^{c_1} \cdot ({a^{2^2}})^{c_2} \ldots \cdot ({a^{2^m}})^{c_m} \nonumber
\end{eqnarray}
Notiamo che $a^2=a \cdot a$, $a^4=a^2 \cdot a^2$, e in generale
$$a^{2^k}=a^{2^{k-1}} \cdot a^{2^{k-1}}$$
e quindi per calcolare {\purples{tutte}} le potenze $a^2,a^4,\ldots,a^{2^m}$ necessitano $m=\lfloor \log_{2} n \rfloor$ prodotti.
\end{frame}

\begin{frame}[fragile]
\frametitle{Calcolo delle potenza}
{\small{
Osserviamo inoltre che 
\begin{itemize}
\item se $c_j = 0$ allora $a^{c_j 2^j}=1$,
\item se $c_j =1$ allora ${a^{2^j}}^{c_j}={a^{2^j}}$.
\end{itemize}

I prodotti di termini della forma $ ({a^{2^k}})^{c_k}$ in ({\ref{pf}}) sono infine $m$.

\smsp

Un codice che implementa la conversione di un numero naturale da forma decimale a binaria \mye

\begin{lstlisting}
function c=dec2bin(n)
j=1; t=n;
while t > 0 % se m=floor(log2(n)), esegue il ciclo m+1 volte.
    q=t/2; t=floor(q);
    if t == q
        c(j)=0;
    else
        c(j)=1;
    end
    j=j+1;
end
\end{lstlisting}

\bignsp

\noindent che richiede 
\begin{itemize}
\item $m+1$ divisioni per determinare i coefficienti $c_{k}$ con $k=0,\ldots,m$, 
\item $m+1$ somme,
\item $m+1$ parti intere che sono indicate con {\tt{floor}} e hanno un costo molto inferiore alla divisione e alla somma.
\end{itemize}
}}
\end{frame}




\begin{frame}[fragile]
\frametitle{Calcolo delle potenza}
Ne ricaviamo che, per $m=\log_2(n)$, calcolare la potenza richiesta serve al pi\'u un numero di operazioni moltiplicative pari a
\begin{center}
\begin{tcolorbox}[width=5cm]
\smnsp
\smnsp
$$3m+1=3 \lfloor \log_2(n) \rfloor+1$$
\smnsp
\smnsp
\smnsp
\end{tcolorbox}
\end{center}
in quanto
\begin{itemize}
\item la {\purples{valutazione dei coefficienti}} $c_0, \ldots,c_m$ richiede {\purples{$m+1$}} divisioni;
\item la {\purples{valutazione delle potenze}} $a^{2^k}$, $k=0,\ldots,m$ consta di {\purples{$m$}} operazioni moltiplicative (notare che per $k=0$ non serve fare calcoli);
\item calcolate le potenze, la {\purples{valutazione finale}} di ({\ref{pf}}), necessita al pi\myu {\purples{$m$}} operazioni moltiplicative (alcuni coefficienti $c_j$ potrebbero essere nulli e quindi $a^{c_j 2^j}=1$). 
\end{itemize}
\end{frame}

\begin{frame}[fragile]
\frametitle{Calcolo delle potenza}
In tabella descriviamo 
\begin{itemize}
\item $n$ che \mye circa la complessit\mya del primo algoritmo (era $n-1$),
\item  $3m+1=3 \lfloor \log_2(n) \rfloor+1$, 
\end{itemize}

\smsp

Si vede che per esponenti relativamente grandi il secondo algoritmo sia di gran lunga da preferire visto che $3 \lfloor \log_2(n) \rfloor+1 \ll n-1$. 

\smsp

Con un po' pi\myu di attenzione, si vede che ci\myo accade per $n > 11$.

\begin{center}
\begin{tabular}{| c | c |} %\label{tabrad}
\hline
$n$  & $    3 \lfloor \log_2(n) \rfloor+1  $ \\
\hline
 $    1.0e+01 $ &  $   10$\\
  $   1.0e+02   $ &  $ 19$\\
    $ 1.0e+03   $ &   $28$\\
   $  1.0e+04   $ &   $40$\\
   $  1.0e+05   $ &   $49$\\
   $  1.0e+06  $ &    $58$\\
  $   1.0e+07   $ &   $70$\\
   $  1.0e+08  $ &    $79$\\
  $   1.0e+09  $ &    $88$\\
  $   1.0e+10   $ &   $100$\\
\hline
\end{tabular} 	 
\end{center}
\vspace{0.35cm}
\end{frame}

\begin{frame}[fragile]
\frametitle{Calcolo delle potenza}

\smnsp

\begin{osservazione}[Facoltativa]
{\scriptsize{
Notiamo che se $B,C$ sono due matrici quadrate di ordine $s$,  il prodotto $B \cdot C$ richiede $s^2$ moltiplicazioni e $(s-1)s \approx s^2$ somme. Quindi per determinare

\smnsp

 $$A^n=\underbrace{A\cdot \ldots \cdot A}_{n}$$

\smnsp 
 
servono $n-1$ prodotti di matrici di dimensione "$s$" ovvero $(n-1)s^2$ moltiplicazioni.
Se usiamo il secondo algoritmo
\begin{itemize}
\item la {\purples{valutazione dei coefficienti}} $c_0, \ldots,c_m$ richiede $m+1$ divisioni;
\item la {\purples{valutazione delle potenze}} $a^{2^k}$, $k=0,\ldots,m$ necessita la determinazione di "$m$" potenze di matrici (si noti che non si devono fare calcoli per ricavare $A^0=I$, $A^1=A$) e quindi $m s^2$ moltiplicazioni (e circa le stesse somme);
\item calcolate le potenze, la {\purples{valutazione finale}} di ({\ref{pf}}), necessita al pi\myu $m$ prodotti di matrici (alcuni coefficienti $c_j$ potrebbero essere nulli e quindi $a^{c_j 2^j}=1$), e bisogna eseguire circa $m s^2$ operazioni moltiplicative come pure additive.
\end{itemize}
Di conseguenza l'applicazione del secondo algoritmo richiede al pi\myu

\smnsp

$$
(m+1)+2m s^2 \approx 2m s^2 = 2 \lfloor \log_2(n) \rfloor s^2
$$

\smnsp

operazioni moltiplicative come pure additive.
Quindi il secondo metodo \mye da preferirsi qualora $2 \lfloor \log_2(n) \rfloor s^2 < (n-1)s^2 $ ovvero quando $2 \lfloor \log_2(n) \rfloor < n-1$, che si verifica  
per $n > 4$ mentre per $n=4$ la complessit\mya \mye la stessa.
}}
\end{osservazione}
\end{frame}



\begin{frame}[fragile]
\frametitle{Calcolo delle potenza}

\smnsp

\begin{esempio}
Valutare $3^{14}$.
\end{esempio}

{{
{\purples{Metodo 1}}. Utilizzando il metodo diretto, mediante {\purples{$13$}} prodotti abbiamo
$$
3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3 \cdot 3  \cdot 3=
4782969$$

{\purples{Metodo 2}}. Dalla rappresentazione in binario di $14$ 
$$14=0 \cdot 2^0 + 1 \cdot 2^1 + 1 \cdot 2^2 +1 \cdot 2^3$$
abbiamo
$$
3^{14}=(3^1)^0 \cdot  (3^2)^1 \cdot (3^4)^1 \cdot (3^8)^1= (3^2)^1 \cdot (3^4)^1 \cdot (3^8)^1.
$$
Essendo
$$
{\purples{3^2}}=3 \cdot 3=9, \smhsp {\purples{3^4}}=3^2 \cdot 3^2=9 \cdot 9 = 81, \smhsp {\purples{3^8}}=3^4 \cdot 3^4=81 \cdot 81 = 6561
$$
abbiamo 
$$
3^{14}=  (3^2)^1 \cdot (3^4)^1 \cdot (3^8)^1  = 9 \cdot 81 \cdot 6561=4782969
$$
Cos\myi per ottenere $3^{14}$ abbiamo eseguito solo {\purples{$9$}} operazioni moltiplicative (di cui $5$ prodotti e $4=	\lfloor \log_2(14)\rfloor +1$ necessarie per la codifica di $14$ in binario).
}}

\end{frame}


\begin{frame}[fragile]
\frametitle{Calcolo del determinante}

\smnsp

\begin{esempio}
Sia la matrice quadrata $A=(a_{i,j}) \in \R^{n \times n}$. Si calcoli il suo determinante $\det(A)$.
\end{esempio}
Sia

\begin{itemize}
\item $A^{(n-1)}_{ij} \in \R^{(n-1) \times (n-1)}$, la sottomatrice  estratta da $A$ cancellando la $i$-esima riga e la $j$-esima colonna.
\item $\det(A^{(n-1)}_{ij})$, il {\purples{minore complementare}} di indici $(i,j)$;
\item $(-1)^{i+j} \det(A^{(n-1)}_{ij})$, il {\purples{complemento algebrico}} di indici $(i,j)$
\end{itemize}

Il primo teorema di Laplace afferma che

\begin{center}
\begin{tcolorbox}[width=10cm]
\smnsp

$$\det (A) = \sum_{j=1}^{n} (-1)^{i+j}a_{ij}\det(A^{(n-1)}_{ij}), \,\,\, i,j=1,\ldots,n.$$
\smnsp
\smnsp
\end{tcolorbox}
\end{center}
\smnsp

\noindent il cui costo computazionale \mye maggiore di {\purples{$n!$}} flops. 
\end{frame}

\begin{frame}[fragile]
\frametitle{Calcolo del determinante}

Se $A=LU$ ottenibile ad esempio mediante {\blues{\href{https://it.wikipedia.org/wiki/Decomposizione_LU}{fattorizzazione LU senza pivoting}}} (cf. {\cite{WIKILU}}), con 
\begin{itemize}
\item $L=(l_{i,j})$ triangolare inferiore, ovvero $l_{i,j}=0$ se $i < j$, con componenti diagonali uguali a $1$,
\item $U=(u_{i,j})$ triangolare superiore, ovvero $u_{i,j}=0$ se $i > j$,
\end{itemize}

Osserviamo che se $T=(t_{i,j}) \in \R^{n \times n}$ \mye una matrice triangolare arbitraria allora il suo determinante \mye il prodotto delle componenti sulla diagonale, ovvero $$
\det(T)=t_{1,1} \cdot t_{2,2} \cdot \ldots \cdot t_{n,n}
$$
e quindi da
$$\det(L)=1 \cdot \ldots 1=1, \smhsp \det(U)=u_{1,1} \cdot u_{2,2} \cdot \ldots \cdot u_{n,n}$$
per il teorema di Binet 
$$
\det(A)=\det(LU)=\det(L) \cdot \det(U) = u_{1,1} \cdot u_{2,2} \cdot \ldots \cdot u_{n,n}.
$$

\end{frame}

\begin{frame}[fragile]
\frametitle{Calcolo del determinante}
Visto che 
\begin{itemize}
\item $\det(A)= u_{1,1} \cdot u_{2,2} \cdot \ldots \cdot u_{n,n}.$ necessita solo di $n-1$ operazioni moltiplicative, 
\item la fattorizzazione $A=LU$ ha complessit\mya dell'{\underline{ordine}} di $n^3/3$, 
\end{itemize}
deduciamo che il calcolo del determinante pu\myo essere effettuato con circa {\purples{$n^3/3$}} operazioni moltiplicative.

\smsp
\begin{nota}
Si tenga conto che per matrici generiche esiste sempre una fattorizzazione $PA=LU$ con $P$ matrice di permutazione.

\smsp

In particolare, si pu\'o facilmente generalizzare quanto visto sopra visto che si puo' calcolare $\det(P)$ con poche operazioni non di natura moltiplicativa.
\end{nota}
\end{frame}

\begin{frame}[fragile]
\frametitle{Calcolo del determinante}

 \begin{table}[!ht]
\begin{center}
\begin{tabular}{|| c | c | c  || c | c | c ||}
\hline
$n$&   $CPU_L$ & $CPU_{LU}$&   $n$&   $CPU_L$ & $CPU_{LU}$  \\
\hline
 	 $  5$ & $6.0e-17$ sec & $2.1e-17$  sec & $ 75$ & $1.2e+91$ anni & $7.0e-14$  sec \\
 	 $ 10$ & $1.8e-12$  sec & $1.7e-16$  sec & $100$ & $4.7e+139$ anni & $1.7e-13$  sec \\
 	 $ 25$ & $9.0e+01$ anni & $2.6e-15$  sec & $125$ & $9.4e+190$ anni & $3.3e-13$  sec \\
 	 $ 50$ & $1.8e+41$ anni & $2.1e-14$  sec & $150$ & $2.9e+244$ anni & $5.6e-13$  sec \\
 	   \hline
\end{tabular}
\caption{In questa tabella paragoniamo indicativamente il tempo di calcolo $CPU_L$, $CPU_{LU}$ necessario a un {\blues{\href{https://en.wikipedia.org/wiki/Supercomputer}{supercomputer}}} come El Capitan che eroga circa 2 exaflops, ovvero $2 \cdot 10^{18}$ operazioni al secondo, per calcolare il determinante di una matrice generica di ordine $n$, rispettivamente con la regola di Laplace e via fattorizzazione $LU$. 

\smsp
Si osservi che 

\smsp
1. si ritiene che l'et\'a dell'universo sia dell'ordine di $1.3787 \cdot 10^{10}$ anni con una incertezza di circa 20 milioni di anni;

\smsp
2. un battito di ciglia dura circa $3 \cdot 10^{-1}$ secondi.
}
\end{center}
\end{table}


\end{frame}


\begin{frame}[fragile]
\frametitle{Valutazione dell'esponenziale (facoltativo)}

\begin{esempio}
Si valuti $f(x)=e^x$, per $x > 1$. 
\end{esempio}

\smsp

{\purples{Metodo 1.}} Posto
$$
S^{(1)}_n(x)=\sum_{i=0}^n \frac{x^i}{i!}.
$$
abbiamo che, dal teorema di Lagrange,
$$
E^{(1)}_n(x)=|f(x)-S^{(1)}_n(x)|=\frac{\xi^{n+1}}{(n+1)!}, \,\,\, \xi \in (1,x)
$$
e se $x$ \mye grande, il numeratore potrebbe essere abbastanza rilevante da rendere l'errore $E^{(1)}_n(x)$ non troppo piccolo, vista la presenza di $\xi > 1$.


\end{frame}


\begin{frame}[fragile]
\frametitle{Valutazione dell'esponenziale (facoltativo)}
{\purples{Metodo 2.}}  Per un numero naturale $m \geq x$ possiamo scrivere 

{\purples{
$$
e^x=(e^{x/m})^m
$$
}}
e quindi procedere valutando prima $a=e^{x/m}$ e poi eseguire $a^m$ con l'algoritmo mostrato nell'esempio precedente.

\smsp

Quindi  valutiamo
\begin{equation}
S^{(2)}_{n,m}(x)=\left(\sum_{i=0}^n \frac{({\purples{x/m}})^i}{i!} \right)^m \approx e^{x}.
\end{equation}

Si noti che dal teorema di Lagrange,
$$
E^{(2)}_{n,m}:=\left|\exp(x/m)-\sum_{i=0}^n \frac{({\purples{x/m}})^i}{i!} \right|=\frac{\xi^{n+1}}{(n+1)!}, \,\,\, \xi \in [0,1]
$$
che \mye molto favorevole rispetto alla stima del metodo precedente.

\end{frame}









\begin{frame}[fragile]
\frametitle{Valutazione dell'esponenziale (facoltativo)}
{\small{
Quale esempio calcoliamo $$e^{10 \cdot  \pi} \approx 4.403150586063198e+13,$$ con 
\begin{itemize}
\item il primo algoritmo;
\item il secondo algoritmo, in cui utilizziamo quali parametri $m_1=32$, $m_2=36$, $m_3=41$, che sono maggiori di $10 \pi \approx 31.4$.
\end{itemize}
In tabella, mostriamo al variare di $n$ i rispettivi errori {\purples{relativi}} degli algoritmi
\begin{eqnarray}
{\tilde{E}}_n^{(1)}&=&E^{(1)}_n/e^{10\cdot \pi} \nonumber \\
{\tilde{E}}_{n,m_k}^{(2)}&=&E^{(2)}_{n,m_k}/e^{10 \cdot \pi}, \,\,\, k=1,2,3,  \nonumber
\end{eqnarray}
che evidenziano i vantaggi del secondo approccio.

\begin{center}
\begin{tabular}{| c | c c c c |} %\label{tabrad}
\hline
$n$  & ${\tilde{E}}_n^{(1)}$ & ${\tilde{E}}_{n,m_1}^{(2)}$  & ${\tilde{E}}_{n,m_2}^{(2)}$  & ${\tilde{E}}_{n,m_3}^{(2)}$ \\
\hline
 	 $  5$ & $1.0e+00$ & $1.6e-02$ & $1.0e-02$ & $5.7e-03$ \\
 	 $ 10$ & $1.0e+00$ & $2.4e-07$ & $8.2e-08$ & $2.5e-08$ \\
 	 $ 15$ & $1.0e+00$ & $3.7e-13$ & $6.6e-14$ & $5.9e-15$ \\
 	 $ 20$ & $9.8e-01$ & $6.6e-15$ & $9.0e-15$ & $2.7e-15$ \\
\hline
\end{tabular} 	 
\end{center}

}}
\end{frame}


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



\begin{thebibliography}{99} 
\setbeamertemplate{bibliography item}[triangle]
\small{
\bibitem{A1} D. Arnold, {\href{http://www.ima.umn.edu/~arnold/disasters/}{http://www.ima.umn.edu/~arnold/disasters/}}
\bibitem{ATK} K. Atkinson, {\em An Introduction to Numerical Analysis\/}, Wiley, (1989).
\bibitem{ATKHAN} K. Atkinson and W. Han, {\em Elementary Numerical Analysis\/}, third edition, Wiley, (2004).
\bibitem{BOth} N. Brisebarre and collaborators {\em {Floating-Point Arithmetic}}, 2009. {\href{https://perso.ens-lyon.fr/jean-michel.muller/chapitre1.pdf}{https://perso.ens-lyon.fr/jean-michel.muller/chapitre1.pdf}}
\bibitem{COM} V. Comincioli, {\purples{Analisi Numerica, metodi modelli applicazioni}}, Mc Graw-Hill, 1990. 
\bibitem{COMESE} V. Comincioli, {\purples{Problemi di analisi numerica}}, Mc Graw-Hill, 1991.
\bibitem{FRO} M. Frontini e E. Sormani, {\purples{Fondamenti di Calcolo Numerico, problemi in laboratorio}}, Apogeo, 2005.
\bibitem{GAUB} W. Gautschi, {\purples{Numerical Analysis}}, second edition, Birkh\"auser, 2012.
\bibitem{GOLD} D. Goldberg, {\purples{What Every Computer Scientist Should Know About Floating-Point Arithmetic}},  Association for Computing Machinery, Inc, Computing Surveys, March 1991.
\bibitem{HUC} T. Huckle, {\href{http://wwwzenger.informatik.tu-muenchen.de/persons/huckle/bugse.html}{http://wwwzenger.informatik.tu-muenchen.de/persons/huckle/bugse.html}}. 
\bibitem{A2} Mars Program, \\ {\href{http://marsprogram.jpl.nasa.gov/msp98/orbiter}{http://marsprogram.jpl.nasa.gov/msp98/orbiter}}
\bibitem{MF} J.H. Mathews e K.D. Fink, {\purples{Numerical Methods using Matlab}}, Prentice Hall, 1999. 
\bibitem{OBI} Network Theory, {\purples{GNU Octave Manual Version}}, {\href{http://www.network-theory.co.uk/docs/octave3/octave\_160.html}{http://www.network-theory.co.uk/docs/octave3/octave\_160.html}}.  
\bibitem{STO} J. Stoer, {\purples{Introduzione all'analisi numerica}}, Zanichelli, 1984. 
\bibitem{MOL} The MathWorks Inc., \\{\purples{Numerical Computing with Matlab}},{\href{http://www.mathworks.com/moler}{http://www.mathworks.com/moler}}.
\bibitem{TRENUM} 
L.N. Trefethen, {\purples{Numerical Analysis}}, \\{\href{http://people.maths.ox.ac.uk/trefethen/NAessay.pdf}{http://people.maths.ox.ac.uk/trefethen/NAessay.pdf}}.
\bibitem{UNIPO} Web Page , \\ {\href{http://utenti.quipo.it/base5/numeri/pigreco.htm}{http://utenti.quipo.it/base5/numeri/pigreco.htm}}.
\bibitem{WIKAR} Wikipedia (Archimede), \\ {\href{http://it.wikipedia.org/wiki/Archimede}{http://it.wikipedia.org/wiki/Archimede}}
\bibitem{WIKILU} Wikipedia (Decomposizione LU),\\   {\href{https://it.wikipedia.org/wiki/Decomposizione\_LU}{https://it.wikipedia.org/wiki/Decomposizione\_LU}}
\bibitem{WIKIDET} Wikipedia (Determinante),\\   {\href{https://it.wikipedia.org/wiki/Determinante}{https://it.wikipedia.org/wiki/Determinante}}
\bibitem{WIKFL} Wikipedia (Floating Point), \\ \href{http://it.wikipedia.org/wiki/Floating\_point}{http://it.wikipedia.org/wiki/Floating\_point}
\bibitem{WIKFL2} Wikipedia (IEEE 754), \\ \href{http://it.wikipedia.org/wiki/IEEE\_754}{http://it.wikipedia.org/wiki/IEEE\_754}
\bibitem{WIKFL3} Wikipedia (IEEE 754r), \\ \href{http://it.wikipedia.org/wiki/IEEE\_754r}{http://it.wikipedia.org/wiki/IEEE\_754r}
\bibitem{WIKNRM} Wikipedia (Norma), \\ \href{https://it.wikipedia.org/wiki/Norma\_(matematica)}{https://it.wikipedia.org/wiki/Norma\_(matematica)}
\bibitem{WIKPI} Wikipedia (Pi Greco), \\ {\href{http://it.wikipedia.org/wiki/Pi\_greco}{http://it.wikipedia.org/wiki/Pi\_greco}}
\bibitem{WIKIHO} Wikipedia (Regola di Horner), \\ {\href{https://it.wikipedia.org/wiki/Regola\_di\_Horner}{https://it.wikipedia.org/wiki/Regola\_di\_Horner}}
\bibitem{WIKILAP} Wikipedia (Teorema di Laplace),\\   {\href{https://it.wikipedia.org/wiki/Teorema\_di\_Laplace}{https://it.wikipedia.org/wiki/Teorema\_di\_Laplace}}.
\bibitem{WIKCI} Wikipedia (Teorema Fondamentale del Calcolo Integrale), \\ \href{http://it.wikipedia.org/wiki/Teorema\_fondamentale\_del\_calcolo\_integrale}{http://it.wikipedia.org/wiki/Teorema\_fondamentale\_del\_calcolo\_integrale}
\bibitem{WIKIPS} Wikipedia (TOP500),\\   {\href{https://en.wikipedia.org/wiki/TOP500}{https://en.wikipedia.org/wiki/TOP500}}.
\bibitem{WOL} Wolfram (Archimedes' Algorithm), \\ \href{http://mathworld.wolfram.com/ArchimedesAlgorithm.html}{http://mathworld.wolfram.com/ArchimedesAlgorithm.html}
}
\end{thebibliography}
\end{frame}

\end{document}





Alcuni siti utili per la comprensione della lezione:
{\smsp}
\begin{enumerate}
\item \href{http://it.wikipedia.org/wiki/Archimede}{http://it.wikipedia.org/wiki/Archimede}
{\smsp}
\item \href{http://utenti.quipo.it/base5/numeri/pigreco.htm}{http://utenti.quipo.it/base5/numeri/pigreco.htm}
{\smsp}
\item \href{http://it.wikipedia.org/wiki/Pi\_greco}{http://it.wikipedia.org/wiki/Pi\_greco}
{\smsp}
\item \href{http://it.wikipedia.org/wiki/Teorema\_fondamentale\_del\_calcolo\_integrale}{http://it.wikipedia.org/wiki/Teorema\_fondamentale\_del\_calcolo\_integrale}
{\smsp}
\item \href{http://it.wikipedia.org/wiki/Floating\_point}{http://it.wikipedia.org/wiki/Floating\_point}
{\smsp}
\item \href{http://it.wikipedia.org/wiki/IEEE\_754r}{http://it.wikipedia.org/wiki/IEEE\_754r}
{\smsp}
\item \href{http://it.wikipedia.org/wiki/IEEE\_754}{http://it.wikipedia.org/wiki/IEEE\_754}
{\smsp}
\item \href{https://en.wikipedia.org/wiki/IEEE\_754-1985}{https://en.wikipedia.org/wiki/IEEE\_754-1985}
{\smsp}
\item \href{http://mathworld.wolfram.com/ArchimedesAlgorithm.html}{http://mathworld.wolfram.com/ArchimedesAlgorithm.html}
\end{enumerate}





\begin{frame}[fragile]
\frametitle{Valutazione dell'esponenziale, facoltativo}

\smnsp

{\footnotesize{

\begin{teorema}[Facoltativo]
Sia $x > 1$ e $m > \lceil x \rceil$. Poniamo 
$$
S^{(2)}_{n,m}(x)=(\sum_{i=0}^n \frac{x^i}{i! m^i})^m.
$$
Allora 
$$
|f(x)-S^{(2)}_{n,m}(x)| \approx \frac{m}{e^x} \cdot \frac{ \xi_2^{n+1}}{(n+1)!}, \,\,\, \xi_2 \in (1/m,x/m).
$$
\end{teorema}

\begin{nota}[Facoltativa]
La quantit\mya 
$$
\frac{m}{e^x} \cdot \frac{ \xi_2^{n+1}}{(n+1)!}, \,\,\, \xi_2 \in (1/m,x/m).
$$
\mye favorevole perch\mye 
\begin{itemize}
\item $\xi_2 \in (1/m,x/m) \subset (1/m,1)$ e quindi la potenza $\xi_2^{n+1}$ diventa {\purples{piccola}} al crescere di $n$;
\item se scegliamo $x < m < e^x$ abbiamo $m/e^x < 1$.
\end{itemize}
\end{nota}
}}
\end{frame}
