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 3^e 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...

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 23^e 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 50^e terme qui est de l’ordre de 10^(–12), puis deux termes consécutifs sont négatifs à partir du 51^e, on a une croissance en valeur absolue à partir du 57^e terme, les puissances de 10 négatives deviennent inutiles à partir du 77^e terme. Pour le 100^e 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.

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.

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.

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 ...