Notions de calcul numérique

Calcul numérique = calcul en utilisant des nombres, en général en virgule flottante.

Calcul numérique $\neq$ calcul symbolique.

Nombre flottant : signe + mantisse (« chiffres significatifs ») + exposant.

Valeur d'un flottant = $(-1)^\mbox{signe} + 1.\mbox{mantisse} * 2^\mbox{exposant}$

Précision avec les flottants Python (double précision = 64 bits) :

  • 1 bit de signe

  • 52 bits de mantisse ($\Rightarrow$ environ 15 à 16 décimales significatives)

  • 11 bits d'exposant ($\Rightarrow$ représentation des nombres de $10^{-308}$ à $10^{308}$)

Notion de précision, exemple sur un calcul de $\pi$

On admet que (Grégory-Leibniz) :

$$\arctan(1) = \frac{\pi}{4} = \sum_{n=0}^\infty \frac{(-1)^n}{2n+1}$$

Pour calculer $\pi$ avec des nombres flottants, il y a plusieurs problèmes de précision :

  1. Le résultat attendu n'est pas un flottant représentable (il n'est même pas rationnel). Le meilleur calcul de $\pi$ possible ne pourra donner qu'un arrondi à $\approx 10^{-15}$ près.

  2. En utilisant des nombres flottants, chaque opération (/, +, ...) peut faire une erreur d'arrondi (erreur relative de $10^{-15}$). Les erreurs peuvent se cumuler.

  3. La formule mathématique est infinie. Le calcul informatique sera forcé de s'arrêter après un nombre fini d'itérations.

In [18]:
def gregory_leibniz(N):
    result = 0
    denom = 1
    signe = 1
    for k in range(N):
        result = result + signe / float(denom)
        # prepare iteration suivante:
        denom = denom + 2
        signe = -signe
    return result * 4


print(gregory_leibniz(1))
print(gregory_leibniz(10))
print(gregory_leibniz(100))
print(gregory_leibniz(1000))

4.0
3.04183961893
3.13159290356
3.14059265384
In [7]:
# Changer la précision de l'affichage (et seulement de l'affichage)
%precision 18
Out[7]:
u'%.18f'
In [8]:
gregory_leibniz(10 ** 8)
Out[8]:
3.141592643589325995
In [9]:
import math
math.pi
Out[9]:
3.141592653589793116
In [10]:
# Retour à la valeur par défaut
%precision
Out[10]:
u'%r'

Les « mauvaises » propriétés des nombres flottants

Erreurs d'arrondis

In [11]:
1.0 / 3 - 1.0 / 4 - 1.0 / 12
Out[11]:
-1.3877787807814457e-17

Non-commutativité

In [12]:
1 + 1e-16 - 1
Out[12]:
0.0
In [13]:
1 - 1 + 1e-16
Out[13]:
1e-16

Répresentation décimale inexacte

In [14]:
1.2 - 1.0 - 0.2
Out[14]:
-5.551115123125783e-17

1.2 n'est pas représentable en machine. L'ordinateur utilise « le flottant représentable le plus proche de 1.2 » à la place ...

Conséquences

  • On ne peut pas espérer de résultat exact

  • La précision du calcul dépend de beaucoup d'éléments (en particulier l'ordre d'évaluation : en général la précision est meilleure en sommant du plus petit au plus grand)

  • tester x == 0.0 avec un flottant est presque toujours une erreur.

  • Si on s'y prend bien, on perd $\approx 10^{-16}$ en précision relative à chaque calcul $\Rightarrow$ acceptable par rapport à la précision des données.

  • Si on s'y prend mal, le résultat peut être complètement faux !

Application : recherche de zéro d'une fonction par dichotomie

Soit $f$ une fonction continue qui change de signe entre $a$ et $b$ avec $f(a) < 0$ et $f(b) > 0$.

In [15]:
def zero_dichotomie(f, a, b, epsilon):
    while b - a > epsilon:
        pivot = (a + b) / 2.0
        value = f(pivot)
        if value <= 0:
            a = pivot
        else:
            b = pivot
    return a
In [16]:
zero_dichotomie(lambda x : x ** 2 - 2, 0.0, 2.0, 1e-15)
Out[16]:
1.414213562373095
In [17]:
math.sqrt(2)
Out[17]:
1.4142135623730951