Limites de suites et précision limitée - Partie 1

Comment la limite d’une suite est-elle modifiée si le calcul se fait en précision limitée ?

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

Suite arithmético-géométrique

Une suite arithmético-géométrique est une suite définie par

$$ u_0 = c ~~\mathrm{ et }~~ u_{n+1} = a u_n + b ,$$

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 :

$$ u_\infty = \frac{b}{1-a} .$$

Exemple

Soit la suite définie par:

$$ v_0 = 0 $$
$$ v_{n+1} = 0,94 \times v_n + 4,98 $$

Il s’agit d’une suite arithmético-géométrique et $0,95 < 1$, donc elle converge vers:

$$ v_\infty = \frac{4,98}{1-0,94} = 83 $$

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 :

$$ u'_{n+1} = a u'_n + b $$

est transformée en la suite suivante:

$$ u'_{n+1} = a' u'_n + b' $$

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$ :

$$ u'_\infty = \frac{b'}{1-a'} $$

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 :

$$ v'_{n+1} = 0,95 \times v'_n + 5 $$

qui a pour limite :

$$ v'_\infty = \frac{5}{1 - 0,95} = 100 $$

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 :

$$ u''_{n+1} = a' ~(\times)~ u''_n ~(+)~ b' $$

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 :

$$ v''_{n+1} = 0,95 ~(\times)~ v''_n ~(+)~ 5 ,$$

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 ?

2 commentaires

Chouette billet !

En fait, je pense qu’il est à mettre en rapport avec des notions comme les ensembles de Julia.

Si $f$ est méromorphe, ce qui est par exemple le cas de $f(x) = ax+b$, alors la suite $u_n = f(u_{n-1})$ donne lieu à un ensemble de Julia, qui est caractérisé par le fait (en des termes simples) qu’une erreur de calcul est grave.

Heureusement, la plupart du temps, cet ensemble (toujours compact) est de mesure nulle, et donc une petite erreur de calcul ne change pas la convergence.

Cependant, tu noteras que je parle d’erreur de calcul lors de l’évaluation de $f$ et non de $f$ elle-même. Je suppose donc ici, par exemple, que tes paramètres $a$ et $b$ sont parfaitement disponibles.

La question de la vitesse de convergence et de la dépendance des conditions initiale est très difficile. Même si ton cas de figure est relativement simple, il me paraît déjà assez peu probable d’arriver à un résultat formel.

La plupart du temps en systèmes dynamiques, on se retrouve à ne pouvoir étudier que des comportements locaux, ou faiblement quantifiés globalement.

+2 -0

Je suis pas un spécialiste du domaine, mais ça me fait furieusement penser aux présentations reliées à l’outil Polyspace, ou encore Fluctuat (les papiers seront peut être plus facilement disponibles). Leur dada, c’est faire de l’interprétation abstraite notamment dans le contexte des flottants. Et si je me souviens bien, ils ont des trucs qui traitent du calcul de point fixe et de la précision du widening dans le cas des boucles.

Parce qu’évidemment, ils sont obligés de calculer une sur-approximation, mais il faut justement qu’ils fassent gaffe à ne pas trop sur-approximer (sinon leur analyse sert à rien).

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte