Instabilité numérique

mardi 14 septembre 2010
par  Alain BUSSER

L’introduction des TICE doit s’assortir de signaux d’alarme du genre « il faut se méfier de ce qu’on voit sur l’écran ». Les meilleurs exemples sont les suites dont on peut démontrer qu’elles convergent et dont on a l’impression, numériquement, qu’elles divergent ou que leur limite est différente de la limite théorique. Seulement ces exemples sont quelque peu difficiles à trouver.


Premier exemple

La suite "à la Fibonacci" $u_{n+1}=u_n+u_{n-1}$ avec $u_0=1$ et $u_1=\frac{1-\sqrt{5}}{2}$ est géométrique de raison $\frac{1-\sqrt{5}}{2}$ donc tend vers 0. Théoriquement...

Si on calcule ses 20 premiers termes avec IDLE :

on trouve qu’elle a bien l’air de tendre vers 0, mais si on pousse un peu plus loin :

le 100ième terme a l’air plutôt ... divergent :

Le problème en Première est que classiquement, pour prouver que la suite est géométrique, on utilise le raisonnement par récurrence, qui est déjà considéré comme difficile en Terminale...

Mais une fois de plus, on peut (en attendant la Terminale) demander aux élèves de faire confiance en un logiciel de calcul formel, par exemple Maxima et son merveilleux module "solve_rec" :

Une autre difficulté posée par cet exemple est que la récurrence se fait sur deux termes ($u_{n+1}$ fonction de $u_n$ et de $u_{n-1}$). Plus simple en Première serait un exemple où $u_{n+1}$ ne dépend que de $u_n$. Mais un autre exemple de récurrence sur deux termes est cité ici.


Commentaires

samedi 24 mars 2012 à 08h20

Pour répondre à Marc Jambon : il n’y a aucune erreur dans le code Python pour le calcul de fibo donné par l’auteur. En Python a, b = b, a+b fera exactement la même chose que si on avait introduit une 3e variable.

Le problème vient des erreurs d’arrondis. La norme IEEE-754 double précision n’est pas suffisante ici pour traiter correctement de si petits nombres. Grosso modo la suite doit osciller entre une valeur positive et une valeur négative or à un moment une valeur qui aurait dû être positive devient une valeur négative (proche certes mais ça change tout) et c’est la catastrophe. Il faut donc s’arrêter avant d’atteindre les limites de la représentation des nombres flottants en machine.

Voir : http://docs.python.org/tutorial/flo...

Logo de Marc Jambon
vendredi 3 décembre 2010 à 12h23 - par  Marc Jambon

Réponse au commentaire du 28 novembre 2010.

Je ne connaîs pas Python et il est possible qu’il accepte une substitution directement sur deux variables (là je ne m’engage pas), toutefois, j’ai fait le calcul sur Mathematica avec les 100 premiers termes, les calculs se font avec 6 décimales affichées jusqu’au 23e terme, puis avec un nombre décimal à 6 décimales multipliée par une puissance de 10 négative, la suite est alternée et décroissante en valeur absolue jusqu’au 50e terme qui est de l’ordre de 10^(–12), puis deux termes consécutifs sont négatifs à partir du 51e, on a une croissance en valeur absolue à partir du 57e terme, les puissances de 10 négatives deviennent inutiles à partir du 77e terme. Pour le 100e terme, Mathematica donne –0.929201, ce qui est complèment différent de ce qui est donné par Python, la gestion des arrondis est sûrement différente, c’est la seule explication qu’on puisse donner en admettant que le programme Python soit correct.

De toute façon, ceci confirme qu’il ne faut pas se fier à des calculs où l’on remplace valeur exacte par valeur approchée, les erreurs d’arrondis à partir d’un certain rang deviennent supérieures aux erreurs théoriques. Imaginons qu’on propose sur Mathematica une boucle « tant que la valeur absolue du terme de la suite est supérieure à 10^(–13) », le programme tournera sans fin, contrairement à ce qu’on pouvait attendre. Sûrement de même avec un autre logiciel en adaptant le test d’arrêt.

En tout cas, le sujet de l’article est particulièrement intéressant et les essais sont convaicants, beaucoup d’utilisateurs s’imaginent que les erreurs sont « négligeables » et ont une confiance aveugle dans leur calculateur ! Félicitation à son auteur.

Logo de marc JAMBON
lundi 29 novembre 2010 à 07h29 - par  marc JAMBON

Un exemple de suite définie par récurrence instable :
Un+1 = Un^2 + Un – 5

Si la valeur initiale est Rac[5], la suite est constante, pour une valeur approchée de Rac[5], la suite est divergente.

Logo de Alain BUSSER
dimanche 28 novembre 2010 à 11h36 - par  Alain BUSSER

Je persiste et signe : Il n’y a pas de « faute de programmation » (du moins ici) ; s’il est possible en Python d’utiliser une troisième variable (comme avec les autres langages de programmation), ce n’est pas nécessaire. Cette puissante fonctionnalité, Python la partage avec Lua et Ruby , ainsi d’ailleurs que JavaScript, qui grâce au paradigme des CaRScripts, permet ce genre d’affectation simultanée en bougeant un point dans le plan.

La perturbation engendrée par la valeur approchée n’est pas de nature algorithmique, elle est dûe à la combinaison

  1. du caractère fini de la précision en machine (Python étant plus précis, la divergence est plus lente) ;
  2. d’une dépendance sensible aux conditions initiales.
Logo de marc JAMBON
samedi 27 novembre 2010 à 07h53 - par  marc JAMBON

Quand, on remplace un nombre réel, ici : (1 –Rac[5])/2, par une valeur approchée, un résultat valable pour le nombre réel, ne l’est pas forcément pour son approximation. Là il n’y a aucun doute.

Toutefois, ici, il y a une faute (malheureusement classique) dans la programmation, au lieu de :

(a, b) = (b, a + b)

il aurait fallu introduire une variable auxiliaire c

c = a

(a, b) = (b, c + b)

Je soupçonne alors que la perturbation engendrée par la valeur approché serait nettement moindre.

Un exemple de perturbation plus convaincant pourrait être :

Un = sin(nπ)

La suite ainsi définie est constamment nulle, mais

Vn = sin(n*3,14)

n’est sûrement pas une suite constante.

Un autre exemple :

Un = ((Rac[2])^2n) / 2^n

remplacer Rac[2] par 1,414 ou 1,415 ...