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.
Réponses
-
Dans un de mes cours j'ai eu le contraire. J'avais eu un exemple dans lequel la suite converge mais en pratique si on calcule les termes à l'aide d'un programme il y a de fortes chances pour que ça diverge.
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. -
Bonjour Raoul
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 -
Bonjour
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. -
Bonjour,
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\}$:################################################################### # Illustration des effets des erreurs d'arrondi ################################################################### import numpy as np import matplotlib.pyplot as plt import numpy.polynomial.polynomial as poly import matplotlib.patches as mpatches ################################################################### # Représentation graphique de f sur [1-2e-k;1+2e-k] pour k = 0 ... 4 # par les deux écritures (factorisée et développée) n=200 kmin=0 kmax=5 Fonc7=poly.polypow(poly.polyfromroots([1]),7) #print(np.poly1d(Fonc7)) for k in range(kmin,kmax): h=2*10**(-k) xmin, xmax, xpas = 1-h, 1+h, h/n x, xx = np.arange(xmin,xmax,xpas), np.linspace(xmin,xmax,5) xx, xs = np.round(xx,k), list(map(str,xx)) y, z = (x-1)**7, poly.polyval(x,Fonc7) plt.figure(figsize=(20,10),dpi=130) plt.subplot(211) plt.plot(x,y) plt.xticks(xx,xs, rotation = 17) label = mpatches.Patch(color='blue', label='n='+str(k)) lg=plt.legend(loc='upper left', fontsize='xx-large', shadow=True, fancybox = True, handles=[label]) lg.get_frame().set_facecolor('cyan') lg.get_frame().set_edgecolor('orchid') lg.get_frame().set_linewidth(5.0) plt.title('Comparaison entre formes développée et factorisée de (x-1)^7', size = 15, color = 'gold', fontweight = 'bold') plt.subplot(212) plt.plot(x,z,'r') plt.xticks(xx,xs, rotation = 17) plt.show()
Cordialement,
Rescassol -
Bonjour
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. -
J'aime beaucoup l'exemple de la relation de récurrence sur la suite d'intégrales $\int_0^1 \frac{t^n}{10-t}dt$ (prise plus ou moins sous cette forme dans Demailly). L'utilisation du binôme est tout aussi catastrophique (tester les deux avec même $n=20$)
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$. -
Un exemple est la suite de Muller qui a déjà été citée dans un fil un peu ancien : suite de Muller.
Elle semble converger vers 100 mais en réalité elle converge vers 6. -
Bonjour,
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
-
Pour les suites récurrentes qui convergent bien numériquement voir les travaux de Srinivasa RamanujanLes mathématiques ne sont pas vraies, elles sont commodes.Henri Poincaré
-
Bonjour
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 ... -
bd2017 : effectivement, le graphe de $f$ sur Wolfram sur cet intervalle fait du grand n'importe quoi. J'ai tracé la fonction sur GeoGebra, on peut zoomer dessus très longtemps et ça ne déconne pas, à se demander les différences entre les algorithmes de tracé...
-
Donc, justement, l'algo de tracé de GeoGebra est différent, et ça permet aux graphes de moins déconner.
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 jandri ! C'est bien la suite de Muller que j'avais vue !
Merci aussi à G.G. pour le lien sur l'incident du missile. -
Dans le DUFETEL on a un bel exemple aussi.
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… -
-
En lisant la première page du document de Rescassol ci-dessus on voit que le problème dans l'exemple de bd2017 vient probablement du nombre de chiffres significatifs (forcément limité) dans la représentation en virgule flottante. En effet $\cos(10^{-8})\approx 1-\dfrac{10^{-16}}{2}$ est arrondi à $1$. Par suite $1-\cos(10^{-8})$ fait $0$ pour la calculatrice ou scilab ou geogebra.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 53 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
In this Discussion
Qui est en ligne 9
9 Invités