En travaillant sur un code de calcul embarqué, j’ai été confronté à une petite énigme mathématique, qui se résume par la question suivante : comment la limite d’une suite est-elle modifiée si le calcul se fait en précision limitée ?
Ce billet va aborder cette question à travers le cas d’une suite arithmético-géométrique.
- Convergence d'une suite arithmético-géométrique
- Effet des arrondis sur $a$ et $b$
- Effet des arrondis sur les opérations
Convergence d'une suite arithmético-géométrique
Suite arithmético-géométrique
Une suite arithmético-géométrique est une suite définie par
où $a$, $b$ et $c$ sont des réels.
Nous allons éliminer les cas des suites purement arithmétiques ou purement géométriques, en supposant que $a \neq 1$ et $b \neq 0$.
Convergence
Avec nos hypothèses, il y a convergence si et seulement si $|a| < 1$, et la limite est, quelque soit la valeur initiale :
Exemple
Soit la suite définie par:
Il s’agit d’une suite arithmético-géométrique et $0,95 < 1$, donc elle converge vers:
Effet des arrondis sur $a$ et $b$
Arrondis
Sur un calculateur, les nombres sont arrondis pour être stockés, à cause de la précision limitée des formats de nombres décimaux. En conséquence, la suite calculée n’est pas tout à fait la même que la suite théorique.
Concrètement, à cause des arrondis, la suite attendue :
est transformée en la suite suivante:
où $a'$ et $b'$ sont les arrondis respectifs de $a$ et $b$.
Limite
La limite de la nouvelle suite est par conséquent modifiée par l’effet des arrondis sur $a$ et $b$ :
Exemple
Reprenons notre exemple précédent, et faisons subir un arrondi à 0,05 près aux paramètres de la suite.
On obtient la suite suivante :
qui a pour limite :
Ce résultat est différent du résultat originalement attendu, qui vaut 83.
Effet des arrondis sur les opérations
Opérations en précision limitée
En plus d’arrondir les paramètres, le calcul sur ordinateur utilise également des opérations mathématiques différentes des opérations mathématiques parfaites, puisqu’elle font subir des arrondis à chaque calcul.
Concrètement, cela signifie que la suite initiale est remplacée, par l’effet des arrondis initiaux et des opérations à arrondis, par la suite suivante :
où $a'$ et $b'$ sont les arrondis respectifs de $a$ et $b$, et $(\times)$ et $(+)$ sont les versions à arrondi de $\times$ et $+$ respectivement.
Convergence
Je ne connais pas de méthode facile pour étudier la convergence, mais il est possible de le faire programmatiquement.
Exemple
En calculant avec une plus grande précision (15 chiffres significatifs) la suite arrondie à 0.05 près :
on trouve les résultats suivant :
- pour $v''_0 \leq 99,5$ : $ v''_\infty = 99,5 $,
- pour $v''_0 \geq 100,5$ : $ v''_\infty = 100,5 $,
- pour $99,5 < v''_0 < 100,5$ : $ v''_\infty = u''_0 $.
On remarque que désormais la limite dépend des conditions initiales, et qu’il y a toute une plage de points fixes. Ceci est dû au calcul en précision limitée.
Au terme de ce billet, une autre question se pose : avec quelle précision doivent être menés les calculs pour converger à une distance donnée de la véritable limite ?
