Suite trompeuse du calcul numérique — Les-mathematiques.net The most powerful custom community solution in the world

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.

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,

    Rescassol126542
    126544
  • Pour les suites récurrentes qui convergent bien numériquement voir les travaux de Srinivasa Ramanujan
  • 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é...
  • @HT, Je ne pense pas que Geogebra calcule $g(10^{-8}) $ pour le tracé.
    Demande à Geogebra la valeur de $g(10^{-8}) $ et vois ce qu'il affiche...
  • 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…
  • Bonjour,

    Un peu de lecture.

    Cordialement,

    Rescassol
  • 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.
Success message!