Suite trompeuse du calcul numérique
Bonjour,
Il y a plusieurs années, j'ai pu lire une présentation ppt très intéressante portant sur les limites du calcul numérique par ordinateur.
Un exemple de suite définie par récurrence simple donnait l'air de converger en faisant des essais numériques, de manière très flagrante, mais une étude mathématique de la suite nous détrompait totalement.
Il était aussi fait référence à un incident pendant la guerre du Golfe. Un algorithme de détection de missiles devait incrémenter une variable toutes les $10^{-n}$ secondes (oublié le nombre mais vous voyez l'idée). A force, le décalage horaire accumulé rendit l'algorithme infonctionnel, avec pour conséquence une erreur de détection de quarante kilomètres, et donc plein de morts.
Bref, si vous aviez un exemple d'une telle suite ou que vous voyez le ppt dont il est question je vous serais très reconnaissant.
Il y a plusieurs années, j'ai pu lire une présentation ppt très intéressante portant sur les limites du calcul numérique par ordinateur.
Un exemple de suite définie par récurrence simple donnait l'air de converger en faisant des essais numériques, de manière très flagrante, mais une étude mathématique de la suite nous détrompait totalement.
Il était aussi fait référence à un incident pendant la guerre du Golfe. Un algorithme de détection de missiles devait incrémenter une variable toutes les $10^{-n}$ secondes (oublié le nombre mais vous voyez l'idée). A force, le décalage horaire accumulé rendit l'algorithme infonctionnel, avec pour conséquence une erreur de détection de quarante kilomètres, et donc plein de morts.
Bref, si vous aviez un exemple d'une telle suite ou que vous voyez le ppt dont il est question je vous serais très reconnaissant.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
C'était la suite définie par : $u_{n+2}=u_{n+1}+u_n/4$ avec $u_0=1$ et $u_1=\dfrac{1-\sqrt{2}}{2}$
Cette suite converge vers $0$. Mais un calcul python montre qu'arrivés au alentours du 600 ième terme on obtiens -4.543396112786175e+28.
ton équation récurrente s'écrit $4u_{n+2} - 4u_{n+1} - u_n = 0$ dont le polynôme caractéristique est 4r² - 4r - 1 = 0
de racines $r_1 = \frac{1 + \sqrt{2}}{2}$ et $r_2 = \frac{1- \sqrt{2}}{2}$
la première est positive supérieure à 1, la seconde est négative
le terme général s'écrit $u_n = A.(r_1)^n + B.(r_2)^n$
les constantes réelles A et B dépendent des conditions initiales $u_0$ et $u_1$
ici on constate que A = 0 et B = 1 et donc ta suite est géométrique de raison $q = \frac{1 - \sqrt{2}}{2}$ comprise entre - 1 et 0
la convergence de la suite géométrique est implosive vers 0 comme tu l'écris
ce qui se passe avec python est qu'il calcule et raisonne dans le cas général
sans tenir compte des deux termes initiaux $u_0$ et $u_1$
il considère A et B constantes non nulles et dans ce cas la suite diverge vers + ou - oo
son comportement est mécanique et primaire, on doit se méfier des machines !
Cordialement
La triste histoire du missile se trouve ici
https://www-users.cse.umn.edu/~arnold/disasters/patriot.html
https://www-users.cse.umn.edu/~arnold/disasters/disasters.html
Dans le domaine des EDO il y a les pb raides aussi, dès qu'on utilise la méthode d'Euler explicite. J'imagine qu'il y aussi des choses autour des matrices mal conditionnées.
Bon courage pour la recherche du ppt.
Ces problèmes d'arrondis font partie de tout cours d'analyse numérique.
Le gestion des erreurs est même un domaine à part entière.
On peut demander aussi à Python la représentation graphique de $x\mapsto (x-1)^7$ sur l'intervalle $[1-\epsilon; 1+\epsilon]$ pour $\epsilon = 2\times 10^{-k}$ et $k\in\{0...4\}$: Cordialement,
Rescassol
Dans l'exemple donné par @Raoul, l'explication est simple.
Si tu remplace $u_0$ par $v_0=1$ et $u_1$ par $v_1=u_1+\epsilon$ où $\epsilon$ représente
l'erreur que fait le logiciel pour approché $u_1.$
Si maintenant on calcule la suite $v_n$ qui suit la même realation de récurrence que la suite $u_n$
il est facile de comparer $u_n$ et $v_n$ (à faire ) et on doit trouver quelque chose
de la forme $|u_n-v_n|=a_n \epsilon $ avec $a_n$ qui tend vers l'infini.
J'ai un exemple très différent que je donnerai plus tard dès que j'aurai un peu de temps.
Si je pose $u_n=\frac{1000^n}{n!}$, un logiciel de calcul numérique va répondre à côté concernant la convergence et la divergence des séries de terme général $u_n$ et $1/u_n$.
Elle semble converger vers 100 mais en réalité elle converge vers 6.
Voilà les images correspondant au code Python ci-dessus, avec $k=2$ et $k=3$.
(le $n$ du cartouche est en réalité $k$).
Cordialement,
Rescassol
Voici un exemple concernant les limites du calcul numérique par ordinateur.
Les exemples donnés ci-dessus concernent des effets instables où l'erreur initiale amplifie. L'exemple ci-dessous est d'une autre nature.
On considère la fonction $f$ définie par $f(x)=\dfrac{1-\cos(x)}{x^2}$.
On sait que la limite de $f$ quand $x$ tend vers $0$ est $1/2.$
Mais avec un logiciel de calcul numérique (ici avec scilab) je trouve
$f(10^{-8}) =0.$ alors que scilab travaille en double précision.
De même demandez à Wolfram de représenter $f$ pour $x\in[0,10^{-5}] $ et voir le graphique ...
Demande à Geogebra la valeur de $g(10^{-8}) $ et vois ce qu'il affiche...
Au moins, dans cette situation. Quand on lui donne à tracer une fonction qui varie très fort très vite, il galère aussi.
Merci aussi à G.G. pour le lien sur l'incident du missile.
C’est le bouquin d’analyse qui était (l’est-il encore ?) utilisé pour la préparation au CAPES par le CNED.
J’essaye de trouver ça…
Un peu de lecture.
Cordialement,
Rescassol