[cours-mesi.git] / pbnum.tex

Ce chapitre s'inspire de~\cite{jedrzejewski2005introduction} et 
de~\cite{bastien2003introduction}. 
On y pointe quelques erreurs classiques en calcul numérique.

On peut classer les erreurs en plusieurs groupes:
\begin{itemize}
\item les erreurs de calcul en machine: elles sont dues aux arrondis de 
  calcul pour les nombres flottants, par exemple.
\item les erreurs de méthode: elles sont dues à l'algorithme utilisé.
  Par exemple, approximation d'une somme infinie par une somme finie, 
  d'une limite d'une suite par un terme de grand indice, 
  d'une intégrale par une somme finie.
\item les erreurs sur les données (imprécision des mesures physiques, 
  résultats d'un calcul approché). Ces données ne peuvent pas être modifiées, 
  mais on peut étudier l'influence de ces erreurs sur le résultat final.
\end{itemize}




 
% \section{Représentation} 
% \begin{Def}[Nombres en base $\Beta$}
% Soit $\Beta$ un nombre entierstrictement supérieur à 1. 
% pour tout entier $n$ supérieur ou égal à 1, 
% il existe un unique entier $p$ et 
% des entiers  $d_i$ ($0 \le i \le p$) tous compris entre 0 
% et $\Beta -1$ avec $d_p \neq 0$ tels que
% $$ n = \Sum_{i=0}^p d_i \Beta^1.$$
% Lemembre de droite est la représentation de $n$ en base 
% $\Beta$

\section{Erreurs de calcul en machine sur les entiers}


On donne à la figure~\ref{script:facto:java} les codes java et python 
permettant d'évaluer la fonction factorielle.

\lstset{language=Java}
\begin{figure}
\begin{scriptsize}
\begin{minipage}{0.68\textwidth}
\begin{lstlisting}
 class TestFactorielle{    
   public static int  factorielle(int n){
     int r = 1;
     for (int i=2; i<=n ; i++){
       r = r * i;}
     return r;}

   public static void main(String args[]){
     for (int j=1; j< 36; j++){
       System.out.println(j+' '+
                          factorielle(j));
     }}}
\end{lstlisting}
\end{minipage}
\begin{minipage}{0.30\textwidth}
\lstset{language=Python}
\begin{lstlisting}
def factorielle(n):
  r=1
  i=2
  while i<=n :
    r=r*i
    i+=1
    return r

for j in range(36):
    print j, factorielle(j)
\end{lstlisting}
\end{minipage}
\end{scriptsize}
\caption{Factorielle en Java, en Python}\label{script:facto:java}
\end{figure}

En Java, on a:
\begin{eqnarray*}
5!&=& 120\\
& \vdots&\\
12! &= & 479001600 \\
13! &=& 1932053504 \\
& \vdots&\\
15! &=& 2004310016\\
16! &=&2004189184\\
17! &=&-288522240\\
 &\vdots&\\
34! & = & 0 \\
35! & = & 0 
\end{eqnarray*}

On remarque que 
\begin{itemize}
\item le résultat donné pour 13! est différent de 13 fois le résultat de 12!
\item le résultat donné pour 16! est plus petit que celui donné pour 15!
\item le résultat donné pour 17! est négatif
\item tous les résultats donnés à partir de 34! sont nuls!
\end{itemize}

Par contre en Python 2.7 on a des résultats cohérents:
\begin{eqnarray*}
12! &= &479001600\\
13! & =& 6227020800\\
& \vdots & \\
17! &=& 355687428096000\\
 & \vdots & \\
34!&=& 295232799039604140847618609643520000000 \\
35! & =&10333147966386144929666651337523200000000
\end{eqnarray*}

Les deux langages travaillent pourtant avec des entiers et ne sont donc pas 
exposés aux erreurs d'arrondis.

Expliquons l'erreur d'interprétation du langage java. 
Celui-ci code chaque entier avec 32 bits. 
Le bit le plus à gauche est celui de signe. Il reste donc 31 bits.
Cela permet de couvrir tous les entiers de l'intervalle
$\llbracket -2147483648, 2147483647, \rrbracket$. Le tableau donné à la 
figure~\ref{table:codage:entiers} donne la correspondance entre 
certains entiers et le version binaire. 


\begin{table}
\centering{
\begin{scriptsize}
$$
\begin{array}{|r|r|r|r|r|}
\hline
-2147483648&-2147483647&\ldots&-2&-1 \\

\hline
100\ldots000&100\ldots001&\ldots&111\ldots110&111\ldots111\\
\hline
\hline
0&1&2&\ldots&2147483647\\
\hline
000\ldots000&000\ldots001&000\ldots010&\ldots&011\ldots111\\
\hline
\end{array}
$$
\end{scriptsize}}
\caption{Correspondance décimaux-binaires}\label{table:codage:entiers}
\end{table}


Multiplier par un facteur revient à effectuer des opérations sur les bits.
Tant que le résultat est inférieur à la valeur maximale des entiers, 
tout se passe bien. 
Par contre dès que le résultat est supérieur, l'interpréteur 
fait n'importe quoi. C'est le cas à partir de 13!.
De plus lorsqu'on a dépassé les capacités, on peut ateindre 0 sans que cela ait 
du sens (comme à partir de 34!)

Si le langage python réussit (au moins à partir de 2.7),
c'est parce qu'il stocke les entiers
sous 64 bits et les convertit en long si besoin, dont le nombre de bits 
n'est pas borné. 
Python 3, dont le type int équivaut au long de la version 2.7 n'a pas un 
nombre borné de bits pour les entiers. Il ne faillit pas dans ce calcul.


\section{Erreurs de calcul en machine sur les flottants}

Un ordinateur  représente chaque nombre réel sur
un nombre fini de bits. 
Ceci  ne permet la représentation exacte que d'un petit sous-ensemble des réels.
La plupart des calculs sur les réels conduisent ainsi à des résultats approchés
qui résultent de la discrétisation de la représentation.


Le tableau~\ref{table:xpl:flottants} donne 
des exemples de nombres réels et leur représentation 
par des flottants en java et en python.

\begin{table}
\centering{
\begin{scriptsize}
\begin{tabular}{|l|l|l|l|}
\hline
Nombre & Représentation        & Valeur approchée &   Erreur \\
\hline
$\frac{1}{7}$   & $0,\overline{142 857}\ldots$  & 0.14285714285714285 & $7.10^{-18}+\frac{10^{-19}}{7}$ \\
\hline 
$\ln 2$ &     0.693147180559945309417232121458\ldots &  0.6931471805599453  & $\approx 10^{-17}$ \\
\hline 
$\sqrt{2}$ &  1.414213562373095048801688724209\ldots & 1.4142135623730951 & $ >  10^{-17}$ \\
\hline 
$\pi$ &       3.141592653589793238462643383279\ldots& 3.141592653589793& $ >  10^{-17}$ \\
\hline 
\end{tabular}
\end{scriptsize}
}\caption{Interprétation erronée de nombres réels particuliers}\label{table:xpl:flottants}
\end{table}

On constate que les deux langages utilisent 64 bits dont 1 pour le signe, 
53 pour le contenu et 11 pour l'exposant de la puissance de 10. Ils peuvent
donc mémoriser au plus 17 chiffres significatifs. 



\section{Adaptation de la méthode pour contourner 
les approximations }

\begin{Exo}
Soit l'équation $x^2 +bx +c = 0$ avec $b$ et $c$ strictement positifs.
On suppose que le discriminant $\Delta$ est strictement positif et proche 
numériquement de $b^2$.
\begin{enumerate}
\item Exprimer les deux racines $x_1$ et $x_2$ ($x_1 < x_2$).
\item Que dire du signe du numérateur de $x_2$ en théorie? 
\item En pratique quelle va être sa valeur si l'interpréteur fait des 
  approximations. 
\item Cette erreur d'arrondi est-elle effectuée dans le calcul de $x_1$?
\item Montrer qu'on pourrait calculer la racine $x_2$ avec $x_2= \frac{c}{x_2}$.
\item Cette nouvelle méthode permet-elle de trouver le signe de $x_2$, et 
est-elle plus précise?
\end{enumerate}   
\end{Exo}

\begin{TP}
Soit l'équation $x^2+1.5.10^{9}x +1 = 0$. Donner une réponse pratique  
aux questions précédentes en effectuant les calculs en java.
\end{TP}



\section{Erreurs sur les données}

Les données provenant de mesures physiques sont souvent entachées d'erreurs.
Par exemple, un traceur GPS ne peut avoir une précision inférieure à 8m 


\begin{Def}[conditionnement]
Soit $A$ une matrice inversible. Le  \emph{conditionnement} de $A$, noté 
$\textit{cond}(A)$ est défini par 
$$ 
\textit{cond}(A) = ||A||~||A^{-1}||.
$$
Une matrice $A$ est dite bien conditionnée si son conditionnement 
$\textit{cond}(A)$ est proche de 1.
\end{Def}



\begin{TP}
On considère les matrices 
$$ A = \left( 
\begin{array}{llll}
4 & 1 & 0 & 0 \\
1 & 4 & 1 & 0 \\
0 & 1 & 4 & 1 \\
0 & 0 & 1 & 4 \\
\end{array}
\right) ,
A' = \left( 
\begin{array}{llll}
4 & 1 & 0,1 & 0,2 \\
1,08 & 4,04 & 1 & 0 \\
0 & 0,98 & 3,89 & 1 \\
-0,01 & -0,01 & 1 & 3,98 \\
\end{array}
\right) , 
B = \left(
\begin{array}{l}
5 \\
6 \\
6 \\
5 \\
\end{array}
\right) \textrm{ et } 
B' = \left(
\begin{array}{l}
5,1 \\
5,9 \\
6,1 \\
4,9 \\
\end{array}
\right).  
$$ 

\begin{enumerate}
\item Que dire de $A$ et $A'$, $B$ et $B'$.
\item Résoudre à l'aide de numpy le système $AX_1=B$.
\item Résoudre à l'aide de numpy le système $AX_2=B'$.
\item Résoudre à l'aide de numpy le système $A'X_3=B$.
\item Que dire des différents vecteurs $X_1$, $X_2$ et $X_3$?
\item Calculer le conditionnement de $A$.
\item Reprendre les questions précédentes avec 
 
$$ A = \left( 
\begin{array}{llll}
10 & 7 & 8 & 7 \\
7 & 5 & 6 & 5 \\
8 & 6 & 10 & 9 \\
7 & 5 & 9 & 10 \\
\end{array}
\right) ,
A' = \left( 
\begin{array}{llll}
10 & 7 & 8,1 & 7,2 \\
7,08 & 5,04 & 6 & 5 \\
8 & 5,98 & 9,98 & 9 \\
6,99 & 4,99 & 9 & 9,98 \\
\end{array}
\right) , 
B = \left(
\begin{array}{l}
32 \\
23 \\
33 \\
31 \\
\end{array}
\right) \textrm{ et } 
B' = \left( 
\begin{array}{l}
32,1 \\
22,9 \\
33,1 \\
30,9 \\
\end{array}
\right)  
$$ 
\item Que peut-on en conclure?
\end{enumerate}

\end{TP}