Contenu de la leçon¶

1. Erreur de représentation
2. Précision des calculs sur un ordinateur
3. Erreurs numériques
4. Conditionnement et erreurs d’approximation
5. Vérification des calculs

Erreur de représentation¶

Les nombres réels n’ont pas de représentation exacte sur un ordinateur

Exemple préliminaire¶

Calcul de la somme $S_n$ de la série convergente: $$S_n = \sum_{i=0}^n \frac{x^i}{i!} $$

Algorithme¶

Algorithme serie(x,n)
     term  = 1.
     somme = 1.
     pour i de 1 a n (exclu)
        term = term*x/i
        somme = somme + term
     fin pour
     Serie = somme

Programme Python¶

Applications¶

Pour $x < 0$ , la série converge mais numériquement le calcul diverge à cause des erreurs d’arrondis.

Solution: utilisation de la propriété $e^{-x} = 1/e^x $¶

Exercice¶

On peut améliorer la précision du calcul en notant que pour $x>0$, on peut écrire: $$e^x = (e^{x_0})^n \mbox{ avec } 0\le x_0 \le1 $$ Réécrire l’algorithme précédent en utilisant cette propriété.

Représentation des nombres sur un ordinateur¶

• nombre entier exacte (32 bits): $-2^{31}\le n \le 2^{31}$

• nombre réel: mantisse + exposant:

Réel $a\neq\ 0$ normalisé = mantisse+exposant $$\forall\ a\in\mathbb{R}\,\,\, a=\pm\ 10^{q}\sum_{i=1}^{\infty}a_{i}.10^{-i}\mbox{ avec }a_{1}\neq\ 0$$

représentation flottante (si $-N\leq\ q\leq\ M$) $$fl(a)=\pm\ 10^{q}\sum_{i=1}^{t}a_{i}.10^{-i}$$

• simple précision 32 bits: $t=7$, $-45<q<38$

• double précision 64 bits: $t=15$, $-324<q<308$

Exemple¶

Précision des calculs¶

Précision machine $\epsilon$¶

$$\frac{\left\Vert a-fl(a)\right\Vert }{\left\Vert a\right\Vert }\le\epsilon$$

Algorithme de calcul de la précision machine¶

Algorithme Precision()
    eps = 1.
    tant que 1. + eps > 1.
        eps = eps/2
    fin tant que
    Precision = 2*eps

Programme Python¶

Erreurs numériques¶

• non associativité de l’addition et soustraction

• formule exacte $\leadsto$ résultats numériques faux

• absorption $x + y = x$ si $y \ll x$

Exemple: racine d’une équation du 2nd degré¶

$$x=\frac{-b\mp\sqrt{b^{2}-4ac}}{2a}$$

programme Python de base¶

meilleur approximation¶

Calcul d’erreurs¶

règles sur les erreurs¶

$$\Delta(x+y)=\Delta x+\Delta y$$ $$\Delta(x-y)=\Delta x+\Delta y$$ $$\Delta(x*y)=\left|y\right|\Delta x+\left|x\right|\Delta y$$ $$\Delta(\frac{x}{y})=\frac{\left|y\right|\Delta x+\left|x\right|\Delta y}{y^{2}}$$

condition sur l’ erreur relative¶

$$\frac{\Delta x}{|x|} \le \epsilon $$

Conditionnement et erreurs d’approximation¶

sensibilité aux erreurs¶

Conditionnement sensibilité du résultat à une petite variation des données.

Problème mal conditionné=grande sensibilité vis à vis des données.

Stabilité sensibilité de l’algorithme vis a vis des erreurs numériques

Erreurs d’approximation¶

Soit $U^h$ une approximation de la solution $U_{ex}$ fonction d’un petit paramètre d’approximation $h$:

$$\lim_{h \rightarrow 0}{U^h} = U_{ex} $$

Erreur $E(h)$ $$ E(h) = \left\Vert U^h - U_{ex} \right\Vert \rightarrow 0 $$

Ordre d’approximation¶

Ordre $O(h^{n})$

• La fonction $E(h)$ est en $O(h^{n})$ s’il existe une constante $C>0$ telle que $\left|E(h)\right|<Ch^{n}$

Approximation d’ordre n:

• si l’erreur est en $O(h^{n})$, alors l’ approximation est d’ordre n

Exemple: calcul de $e^a$ avec des tables pour $0 < a < 1$

On précalcule $n+1$ valeurs $l_k=\log(1 + 10^{-k})$ ( pour $k=0,n$ )

On a donc $e^{l_k} = 1 + 10^{-k}$

On décompose ensuite $a$ sous la forme

$$ a = \sum_{k=0}^{n} a_k l_k + \epsilon \mbox{ avec } a_k\in \mathbb{N} \mbox{ et } |\epsilon| \lt 10^{-n}$$

ce qui donne (en utilisant $e^{a+b}=e^a e^b $) :

$$ e^a = \left[\prod_{k=0}^{n}\left(1 + 10^{-k}\right)^{a_k}\right] e^\epsilon$$

En approximant $e^\epsilon \simeq 1+ \epsilon$, on obtiens une approximation de $e^a$ $$ e^a \simeq \left[\prod_{k=0}^{n}\left(1 + 10^{-k}\right)^{a_k}\right] ( 1 + \epsilon) $$ avec une erreur relative $\epsilon^2$ $$ \frac{\Delta e^a}{e^a} = \frac {e^\epsilon- 1 - \epsilon}{e^\epsilon} \simeq \theta(\epsilon^2)$$

Algorithme: approximation de exp(a) à l’aide de tables¶

Algorithme Exp(a)
    n = 8  # nbre de valeurs de la table
    L = [ln(1),ln(1+0.1),ln(1+0.01),...ln(1+10^-7)]
    x = a  # valeur a decomposer (a, a-a0*l0, a-a0*l0-a*l1,...)
    y = 1  # valeur de exp(a)
    pour k de 0 a n-1
       # Calcul de ak par decomposition 
       # de x = a - a0*L[0]-a1*L[1]-..ak-1*L[k_1]
       ak = 0
       tant que x>L[k] faire
           x = x - L[k]
           y = y*(1+10^-k)
           ak = ak + 1
       fin calcul ak 
     fin boucle k
     # prise en compte du reste ici x
     y = y*(1+x)
     retour y

Programme Python¶

comparaison avec le calcul utilisant les séries entières¶

Remarques

• on peut améliorer la précision en utilisant la fonction numpy log1p(x) qui calcul log(1+x) avec une plus grande précision pour x petit
• attention le calcul précis des fonctions élémentaires est un problème complexe (voir l’article sur la précsion de l’instruction fsin des processeurs Intel)

Exercice:¶

Utiliser le principe de l’algorithme précédent pour calculer $log(a)$ pour $a>1$. On pourra décomposer $a$ sous la forme: $$ a = \left[\prod_{k=0}^{n}\left(1 + 10^{-k}\right)^{a_k}\right] (1+\epsilon)$$ En déduire une approximation de $log(a)$ avec une erreur relative de $\epsilon^2$

Vérification des calculs¶

• une simulation numérique calcule une approximation

• toute simulation numérique doit être validée

• vérification et validation font partie intégrante du calcul scientifique

La validation d’une simulation numérique peut utiliser

• une vérification de la convergence

• une comparaison avec une solution analytique ou une solution de référence

validation de la simulation d’alunissage¶

comparaison avec une solution analytique

Dans la modélisation de alunissage on a utiliser une approximation de la solution de l’équation du mouvement: $$ \frac{d^2 Z}{dt^2} = -g + \frac{Qe*Ue}{M_0-Q_e*t}$$ sous la forme $$ Z = Z_0 - V_0 t - g \frac{t^2}{2} + t U_e (\frac{X}{2} + \frac{X^2}{6} + \frac{X^3}{12} + \frac{X^4}{20} + \frac{X^5}{30})$$ avec $X=t/t_0$ et $t_0=M_0/Q_e$

Cette équation admet une solution analytique: $$ Z_e = Z_0 - V_0 t - g \frac{t^2}{2} + U_e t_0 (1-X)ln(1-X) + U_e t $$

L’approximation correspond à un DL de $ln(1-X)$ a l’ordre 5, et l’erreur doit etre en $\theta(X^7)$

programme Python¶

Validation du calcul de $exp(a)$ avec $n$ valeurs tabulées¶

vérification de la convergence

erreur relative $err \simeq \epsilon^2$ avec $\epsilon \lt 10^{-n}$

programme Python¶

Bibliographie¶

1. Calcul des fonctions usuelles sur une calculatrice (blog prépa Dupuis de Lome)

2. Calcul scientifique (J. Erhel INRIA -Rennes)

3. Intel Underestimates Error Bounds by 1.3 quintillion for the fsin instruction

4. Collection of software bugs

5. J. P. Demailly. “Analyse Numérique et Equations Différentielles”, PUG, 1994.

FIN¶

</div>