Vitesse de convergence etc.

Les histoires de $o$, $O$, développement asymptotique etc. m'incitent à essayer de comprendre cette notion-là en détail.

En soi, la plupart des nombres au-delà des fractions sont "difficiles à comprendre". Certains ont encore l'avantage d'être constructibles, comme $\sqrt{2}$, ça aide. Beaucoup d'autres ne le sont pas, et pour comprendre ceux-là... il faut réfléchir un peu plus. Par exemple, je sais que $\pi=3,14...$, mais, comment a-t-on fait pour trouver ces décimales (et surtout, s'assurer que ce sont les bonnes) ? Une méthode fréquente que je connais, c'est de trouver un développement en série du nombre en question et de commencer à calculer les sommes partielles de cette série.

Admettons que je dispose d'un développement en série d'un nombre $x$ donné : $x = \displaystyle \sum_{n=N_0}^{\infty}u_n$. Ce que j'aimerais comprendre, c'est, comment sait-on combien de termes il faut calculer pour avoir $k$ décimales exactes ?

Je connais quelques autres méthodes (par exemple la méthode de Newton, avec une fonction suffisamment régulière) où la question est la même : étant donné une suite telle que $\lim u_n=x$, comment sait-on combien de termes de la suite il faut calculer pour avoir $k$ décimales exactes ?
«13

Réponses

  • Encore plus généralement qu'une série qui converge vers un nombre réel $r$ que l'on souhaite approximer, on a une suite $(u_n)_{n\in\N}$ qui converge vers ledit nombre. Exemples standards :
    • le cas d'une série, c'est quand la suite est la suite des sommes partielles associée à une autre suite $(v_n)_{n\in\N}$, c'est-à-dire $u_n=\sum_{k=0}^nv_k$ pour tout $n$ ;
    • calcul approché d'une intégrale : les méthodes des rectangles, des trapèzes, etc., consistent à définir des suites qui convergent vers l'intégrale ;
    • résolution numérique d'une équation par dichotomie, par la méthode de Newton, etc. : on définit une suite qui converge vers la (une) solution.
    La seule façon de savoir jusqu'à quel indice aller, c'est d'avoir une majoration de l'erreur $\bigl(|u_n-r|\bigr)_{n\in\N}$, c'est-à-dire une suite « simple » $(e_n)_{n\in\N}$ qui tend vers zéro, aussi petite que possible, telle que \[|u_n-r|\le e_n.\] Si on veut avoir $r$ avec une précision $\varepsilon$, on cherche $n$ aussi petit que possible tel que $e_n\le\varepsilon$.

    Après, on peut estimer la vitesse de convergence par comparaison à des situations classiques. On parle de
    • convergence (au moins) lente : $|u_n-r|\le\frac1{n^a}$ pour $a>1$ donné ;
      exemple : méthodes habituelles pour les intégrales : rectangles ($a=1$), trapèzes ($a=2$), Simpson ($a=4$)...
    • convergence (au moins) géométrique : $|u_n-r|\le k|u_n-r|$ pour $k\in\left]0,1\right[$ donné ;
      exemple : suite $u_{n+1}=f(u_n)$ pour un point fixe attractif non super-attractif ($0<|f'(r)|<1$)
    • convergence rapide : $|u_{n+1}-r|=o(u_n-r)$ ;
    • convergence (au moins) quadratique : $|u_{n+1}-r|\le C|u_n-r|^2$ pour $C>0$ donné ;
      exemple : suite $u_{n+1}=f(u_n)$ pour un point fixe super-contractant ($|f'(r)|=0$, $f''(r)\ne0$) ; Newton entre dans ce cadre ;
    • etc.
    Notons $d_n=-\log|u_n-r|$, où $\log$ est le logarithme décimal : sa partie entière est le nombre de décimales exactes quand on approxime $r$ par $u_n$, puisque $10^{-\lfloor d_{n+1}\rfloor}<|u_n-r|\le10^{-\lfloor d_n\rfloor}$. Voyons ce que dit chaque situation :
    • en cas de convergence lente, $d_n$ est a priori de l'ordre de grandeur de $a\log n$ (du moins, on ne peut pas affirmer mieux). Pour avoir $D$ chiffres significatifs, il faut environ $n=D^{1/a}$ termes de la suite : c'est mauvais !
    • en cas de convergence géométrique, on a $d_{n+1}\ge d_n+\log k$ : chaque itération apporte un nombre à peu près constant de chiffres significatif ($\log k$) ; c'est mieux ; pour avoir $D$ chiffres significatifs, il faut environ $D/\log(k)$ termes de la suite ;
    • en cas de convergence rapide, $d_{n+1}-d_n$ tend vers l'infini : prometteur ;
    • en cas de convergence quadratique, $d_{n+1}\ge 2d_n+C'$ : en gros, on double le nombre de décimales exactes à chaque itération ; pour avoir $D$ chiffres exacts, il faut de l'ordre de $\log(D)$ itérations : c'est très rapide !
  • Je prends tes notations. J'ai déjà lu des choses comme ce que tu as raconté, dans un cours d'analyse numérique, mais en soi, ça ne répond aucunement à la question selon moi, ça ne fait que transformer un problème que je ne sais pas résoudre en un autre problème que je ne sais pas résoudre.

    $r$, c'est donc le nombre dont je veux connaître un développement décimal. Donc a priori, je ne sais rien de $r$, ou presque rien. Donc je ne connais pas forcément sa partie entière, ni ses premières décimales... je vis dans un monde ou la calculatrice a besoin que je lui apprenne comment approximer $r$.

    Je connais miraculeusement une suite $(u_n)_n$ qui converge vers $r$ : donc je sais que $|u_n - r| \longrightarrow 0$.

    Les $k$ premiers chiffres de $u_n$ sont exacts si, et seulement si, les $k$ premiers chiffres de $|u_n-r|$ sont $0$.

    Le problème que j'ai avec ça, c'est que $r$, justement, j'essaie de trouver qui c'est ! Donc comment je pourrais connaitre les chiffres de $|u_n-r|$ ?

    Les chiffres de $(u_n)_n$, si cette suite a la gentillesse d'être calculable algébriquement, on peut les connaître. Mais puisqu'on essaie de trouver ceux de $r$, $|u_n-r|$ n'est pas une information utilisable, si ? Comment fait-on pour connaitre la vitesse de convergence d'une suite vers sa limite si cette suite doit justement servir à découvrir qui est sa limite ?
  • Tu sais des choses sur $r$ en général et tu définis la suite $(u_n)_n$ à partir de ça. Par exemple, tu sais que (voire tu définis) $e = \sum_{n=0}^{+\infty} \frac{1}{n!}$, donc un choix naturel est de prendre $u_n = \sum_{k=0}^n \frac{1}{k!}$. Alors $$|e-u_n| = \sum_{k=n+1}^{+\infty} \frac{1}{k!}.$$ Un petit exercice que tu devrais faire montre que $|e-u_n| \leq \frac{1}{(n+1)!}\left(1+\frac{1}{n}\right)$. En particulier, si tu veux $10$ décimales de $e$, il te suffit donc de calculer les $10$ premières décimales de $u_n$, dès que $\frac{2}{(n+1)!} < 10^{-10}$, i.e. $n \geq 13$.
  • Il s'agit donc majorer la valeur absolue du reste de la série, $R_n=U_n-r$, en fonction de $n$ (avec $U_n$ somme partielle)

    Il n'y a pas de méthode générale, je te cite cependant deux exemples classiques et basiques :

    1. $(u_n)_n$ est le terme général d'une série alternée satisfaisant la décroissance de $(|u_n|)_n$. Dans ce cas, ton cours dit que la limite est comprise entre deux termes consécutifs, et qu'en plus l'erreur est du signe du premier terme négligé. Supposant par exemple que les $u_n$ soient positifs pour les $n$ pairs, on a ainsi $U_{2n-1} \leq r \leq U_{2n}$ de sorte que par exemple $0\leq r-U_{2n-1}\leq U_{2n}-U_{2n-1}=u_{2n}$, il te suffit donc de majorer $u_{2n}$ par $10^{-k}$ ce qui te donne un $n$ convenant.

    2. $u_n=f(n)$ avec $f$ décroissante continue de limite nulle. L'encadrement entre intégrales va te donner (vérifies les indices) un encadrement du type $\int_{n+1}^{+\infty} f(t)dt\leq R_n \leq \int_{n}^{+\infty} f(t)dt$, il te suffit donc de majorer $\int_{n}^{+\infty} f(t)dt$ par $10^{-k}$.

    EDIT : j'ai répondu uniquement dans le cas des séries (je n'avais pas lu l'ensemble du post). Ne pas oublier non plus que la démonstration du théorème du point fixe pour les applications contractantes donne une majoration explicite de l'erreur.
  • Il te faut une majoration de l'erreur. Elle est donnée par une analyse mathématique du contexte précis, je ne sais pas donner une réponse générique. Dans les morceaux d'analyse numérique que tu as déjà étudiés, il y avait sans doute la structure suivante : présentation du problème, idée de la solution, formules définissant la suite $(u_n)$, majoration de l'erreur commise (en termes des données, faisant par exemple intervenir des sup de fonctions qu'il est parfois délicat de calculer explicitement mais qu'on peut estimer).

    Je ne sais pas donner de réponse universelle à la question « comment trouver une majoration de l'erreur ? ». Voici des exemples en revanche :
    • si $(u_n)$ est la suite de la méthode des rectangles, $|u_n-r|\le\frac{M(b-a)^2}{n}$, où $M=\sup_{[a,b]}|f'|$ (ça vient sans doute des accroissements finis) ;
    • si $u_n=\sum_{k=0}^n\frac{(-1)^k}{k+1}$ alors $|u_n-\ln 2|\le\frac{1}{n+2}$ (par le critère spécial des séries alternées) ;
    • si $(u_n)$ est la suite définie par la méthode de Newton (pour $f$ définie sur $I$, la méthode étant supposée converger) et si $K=\frac{\sup_I|f''|}{2\sup_I|f'|}$, alors $K|u_n-r|\le\bigl(K|u_0-r|\bigr)^{2^n}$ (encore une formule de Taylor et une récurrence).
  • Je crois qu'il y a plusieurs problèmes.

    1) Soit $A$ l'ensemble des nombres réels $x$ tels qu'il existe un algorithme qui prend en entrée un entier $n$ et qui renvoie un couple de rationnels $(a_n,b_n)$ tels que
    - la suite $a$ est croissante
    - la suite $b$ est décroissante
    - $\forall n \in \mathbb{N}, \quad a_n \leq x \leq b_n$
    - $\lim b_n - a_n = 0$.

    Alors $A$ est dénombrable ! Ca m'a fait un choc quand j'ai entendu ça. Bref, un réel qui appartient à $A$, c'est un réel très particulier.

    2) Pour tout élément $x$ de $A$, il existe un algorithme qui prend un entier $n$ en entrée et qui calcule la $n$-ème décimale de $x$ : on calcule $a_k$ et $b_k$ jusqu'à ce que $b_k - a_k < 10^{-n}$ et on renvoie la $n$-ème décimale de $a_{k_0}$ (où $k_0$ est le rang où on s'est arrêtés).

    3) La question suivante peut être une formalisation de ta question, et je n'ai pas la réponse.

    Soit $E$ l'ensemble des algorithmes qui prennent un entier en entrée et donnent un rationnel en sortie, et sorte que la suite de rationnels ainsi produite est convergente. Existe-t-il un algorithme qui prend en entrée un algorithme de $E$ et qui le classe dans la liste des vitesses de convergences de Math Coss (ou dans toute autre qui semblerait judicieuse) ?

    4) Dernière chose plus terre à terre : dans les exemples que tu mentionnes, tu disposes d'une démonstration que telle suite converge vers tel réel ! Dans un tel cas, tu ne peux pas dire que tu ne "sais rien" sur la limite... puisque tu as démontré que la suite était convergente.
  • @ Georges : bah oui, ton point 1) est tout à fait raisonnable, je n'y avais même pas pensé ! Merci
  • Je me rends compte en vous lisant que le problème est globalement assez compliqué. C'est à se demander comment ceux qui ont programmé les premières calculatrices ont fait (en soi, c'est vraiment ça la question que je pose). Si l'on part du principe que tout nombre irrationnel est "compliqué" parce qu'on n'a pas de méthode simple et universelle pour déterminer son développement décimal, on s'arrache vite les cheveux.

    Tout le monde répond pendant que j'essaie de formuler un message, au secours !

    Poirot : Petit laïus sur l'exponentielle. J'essaie d'être constructiviste au possible, donc pour moi, $\exp$ est la bijection réciproque de la primitive de $x \longmapsto \dfrac{1}{x}$ qui s'annule en $1$, c'est la manière la moins "parachutée" pour introduire $\exp$ dans un cours (selon moi, dire "on a une primitive pour tout $x^{\pm n}$ sauf celle-là, alors on la définit nous-mêmes par intégrale", c'est infiniment mieux que "tiens, si on regardait une équa diff au pif juste pour avoir une excuse de parler de $\exp$"). Je ne définis jamais $\exp$ par sa série, ça c'est un théorème (ne serait-ce que parce qu'on (re)définit $\exp$ en première année alors qu'on voit les séries entières en deuxième année). Si mes souvenirs sont bons, c'est en appliquant le théorème de Taylor qu'on trouve le développement en série de $\exp$, je ne crois pas qu'on a besoin d'avoir une approximation de $e$ pour ça. Ou a la rigueur, on peut montrer que $e \in [2;3]$ assez tôt dans ce genre de cours.

    Mais à part ça, à partir du moment où l'on dispose du DSE de $\exp$, je suis d'accord qu'on peut utiliser ta formule qui donne $|e - u_n|$ comme le reste d'une série convergente... à condition qu'on soit capable d'exprimer cette somme en fonction de $n$, ce qui devrait être le cas ici puisque c'est une somme de fractions. Après, on cherche $n$ tel que le reste est suffisamment petit, OK.

    math2 : ton exemple avec les encadrements par intégrales, c'est encore une fois un exemple de "remplacer un problème de machin à savoir calculer en un problème d'un autre machin à savoir calculer". Dans certains cas, ça va effectivement marcher parce qu'on trouvera une fonction $f$ dont on "sait calculer" les intégrales (selon ma définition ici : le résultat est rationnel).

    La question est toujours de savoir ce qu'on considère comme "calculable". J'essaie en principe de comprendre comment une calculatrice fait pour donner des valeurs décimales quand on lui demande un truc. Je trouve ça d'autant plus intriguant/fascinant que Poirot doit faire tout un paragraphe pour un nombre. L'absence de méthode générale est d'autant plus intriguante que je me demande comment on fait tenir les choses dans la mémoire finie d'une calculatrice.

    Le message de Georges Abitbol tombe à point, avec ses histoires d'algorithmes sur des rationnels. J'ai trouvé ça très intéressant... les suites adjacentes sont très pratiques pour contourner le problème de "calculer l'erreur entre la suite approximante et la limite qu'on essaie justement d'écrire". Très jolie trouvaille, si tu as une source où je peux lire une démonstration que ton ensemble $A$ est dénombrable, je prends !

    Mais pour ton point $4$ : le problème est le suivant... oui, je sais que la suite tend vers le réel que j'essaie d'écrire. Mais si je ne sais pas à quelle vitesse, je ne sais en principe rien (peut-être que même après 10 milliards de termes, je n'ai toujours aucun chiffre exact, comment je pourrais savoir ça ?). Donc il me faut une suite qui converge vers le réel que je cherche, et sa vitesse de convergence vers ce réel, sauf que cette vitesse, je la détermine comment si je ne connais pas la valeur exacte de la limite (ce qui est mon cas, puisque je m'intéresse à la suite pour déterminer la valeur décimale de sa limite) ? C'est justement ça qui me pose problème. Et la réponse semble être "ben ça dépend".
  • Pour ce que font les calculatrices, la partie 4 opérations est simple (même si l'algorithme de division n'est pas élémentaire); les puissances sont généralement calculées avec l'exponentielle; les racines aussi, sauf parfois la racine carrée qui a un algorithme direct efficace (et idem s'il y a une touche racine cubique); pour les fonctions sin, cos, exp, ln, voir l'algorithme Cordic.

    Mais c'est de l'analyse numérique et de la programmation. L'analyse numérique s'appuie sur les résultats d'analyse généraux, mais est spécifique.

    Cordialement.
  • Un algorithme est une suite finie de symboles pris dans un alphabet fini donc il n'y en a qu'un nombre dénombrable.

    Plus explicitement, le nombre d'algorithmes est inférieur au cardinal de $\N^{(\N)}$ (l'ensemble des suites finies de naturels ou, ce qui revient à peu près au même, l'ensemble des suites entières nulles à partir d'un certain rang), qui est dénombrable (pour tout $n$, l'ensemble des suites nulles à partir du rang $n$ est en bijection avec $\N^n$, qui est dénombrable, et une réunion dénombrable de dénombrable l'est aussi).

    Pour l'exponentielle, nous sommes sans doute nombreux à penser que tu te trompes. D'abord tu fais des mathématiques pour toi, pas pour un cours, et ce qui est naturel pour un cours de terminale n'est pas souvent ce qui est le plus efficace pour un mathématicien plus avancé. Ensuite, l'exponentielle a vocation à s'appliquer aux complexes (même pour les élèves de terminale : $\mathrm{e}^{\mathrm{i}\theta}$ – au moins au temps où tu étais en terminale), aux matrices et autres opérateurs (flot d'une équation différentielle). Surtout, pour l'élégance de l'introduction par la série, cf. le préambule du livre de Rudin Analyse réelle et complexe souvent évoqué ici.
  • Il n'y a rien de magique dans les calculatrices, elles ne peuvent pas tout calculer. 'est simplement qu'en pratique il y a une petite liste de fonctions qui sont implémentées, et pour chacune de ces fonctions, on dispose (depuis le $17$ème siècle en général !) de méthodes permettant de calculer autant de décimales que l'on veut pour les valeurs prises par ces fonctions.

    La question de la calculabilité des nombres réels est intéressantes, et on se heurte toujours au même problème : il ne peut y avoir qu'un nombre dénombrable de réels calculables, quelle que soit la manière à peu près raisonnable de définir cette notion.

    J'ai l'impression que tu idéalises la possibilité de tout calculer dans les réels !
  • MC : Tu ne m'as pas encore convaincu de changer d'avis au sujet de la définition de l'exponentielle. Je ne me souviens plus de ce que fait Rudin, mais peu importe. Je trouve ma définition (enfin, ce n'est pas la mienne, mais celle que je préfère) plus naturelle et moins parachutée, peu importe si elle requiert ensuite plus de travail pour établir les résultats fondamentaux (et encore, je ne suis pas sûr de ça). Effectivement, pour les nombres complexes et les matrices, on est obligé de passer par la série, mais je ne suis peut-être pas non plus d'accord sur quelles maths sont enseignées à tel ou tel niveau et comment. Enfin bref. Il faudra qu'on "agree to disagree".

    gerard0 : il faudrait que je voie plus en détail ce que tu entends par "calculer avec l'exponentielle". J'ai essayé de lire un peu sur l'algorithme CORDIC et ça m'a l'air compliqué, je n'ai pas vraiment compris comment c'est censé fonctionner.

    Poirot : je n'idéalise rien du tout, je me demande comment c'est fait "en détail", parce que je n'en ai aucune idée. Je ne sais pas du tout comment on calcule une approximation décimale de $\cos(e)$ ou je ne sais quoi. La calculatrice sait le faire mais je ne sais pas du tout comment elle fait.
  • C'est simple comme bonjour : Si $\tilde e$ est une approximation de $e$ à $10$ décimales près disons, on a $$|\cos(e) - \cos(\tilde e)| \leq |e-\tilde e| < 10^{-10}$$ par le théorème des accroissements finis, et $\left|\cos(\tilde e) - \sum_{k=0}^n \frac{(-1)^k \tilde{e}^{2k}}{(2k)!} \right| \leq \frac{\tilde{e}^{2n+2}}{(2n+2)!}$ par le théorème des séries alternées. On prend $n$ assez grand pour avoir les $10$ premières décimales de $\cos(\tilde e)$, et c'est terminé.

    Bien sûr, il y a certainement des méthodes beaucoup plus efficaces pour faire ce genre de calcul, et elles sont sûrement implémentées dans nos calculatrices, mais tout ça pour dire qu'il n'y a besoin que de connaître un peu d'analyse élémentaire pour l'immense majorité des calculs que l'on peut demander à une calculatrice.
  • Oui... mais pour chaque calcul, il va falloir trouver une autre méthode, c'est ça qui rend la chose compliquée. Si je t'en demande 25 autres, au pif, ça te prendra peut-être vraiment très longtemps pour trouver. La calculatrice le fait en un instant, je suis fasciné par le fait qu'on ait trouvé des méthodes qui marchent qui marchent aussi bien.
  • Ben... C'est surtout que la calculatrice peut faire des milliers d'opérations par seconde. :-D
  • Je sais bien, mais il faut quand même lui apprendre lesquelles sont les bonnes !
  • Une aune pour mesurer la qualité d'une définition, c'est sa généralité. La puissance d'un concept, c'est en particulier le nombre et la variété de ce qu'il arrive à capturer. À ce titre, la définition par série de l'exponentielle l'emporte avec plusieurs longueurs d'avance.

    Pour calculer l'exponentielle d'un nombre, une chose est sûre : la série est en général très inefficace. Prenons par exemple $\exp(-30)\simeq9{,}36\cdot10^{-14}$ : le terme le plus grand est $\frac{30^{30}}{30!}$, qui d'après la formule de Stirling est de l'ordre de $\exp(30)$... On somme des nombres dont la partie entière a 14 chiffres pour calculer un nombre dont la première décimale non nulle est en position 14. Il faut donc une précision d'au moins 28 chiffres pour chaque terme pour obtenir... la première décimale !
  • Comme dit plus haut, c'est un programme informatique, et il n'y a pas besoin d'implémenter des milliers de calculs différents. Avec la liste suivante, on peut déjà faire l'immense majorité des calculs que tu as déjà du demander à une calculatrice : additions, soustractions, multiplications, divisions, fonctions exponentielle, racines, logarithme, cosinus, sinus, tangente, méthodes d'approximations d'intégrale. Et tout ça ne nécessite qu'un tout petit peu d'analyse élémentaire.
  • hum, pour évaluer numériquement $e^{-30}$, je calcule $\exp (-1)$ avec la série alternée puis je prends la puissance 30 avec la suite $u_{n+1} = \exp (-1)\times u_n$ et $ u_0 = 1$; il suffit de contrôler l'erreur sur le premier calcul.
    A demon  wind propelled me east of the sun
  • HT : " il faudrait que je voie plus en détail ce que tu entends par "calculer avec l'exponentielle"." ?? C'est pourtant du programme de terminale : Pour $a>0,\ a^x=\exp(x\ln(a))$.
    Par moments, tu es déconcertant, tu sembles ne pas connaître certains classiques de lycée ou L1.

    Cordialement.
  • HT : "Oui... mais pour chaque calcul, il va falloir trouver une autre méthode" ??? Quand on a un algorithme pour calculer $\cos(x)$, c'est le même à chaque appel de $\cos$. C'est une des bases de l'informatique !
  • Séries alternées et algorithme de Horner fournissent pour tout entier $n$ et tout réel $x$ positif l'inégalité suivante: $$\left |1 - x\left (1 - \frac x 2 \left (1 - \frac x 3 \left (1 - \frac x 4\left (... \left (1 - \frac x n \right ) \right) \right) \right) \right) - \exp (-x) \right| \leq \frac{x^{n+1}}{(n+1)!}$$
    Il faudrait estimer l'erreur commise pendant l'évaluation de l'expression parenthésée ci-dessus cependant.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • gerard : Arrête de me prendre pour un con, je n'apprécie pas. Je pense avoir plus que prouvé sur ce forum que je ne suis pas un abruti. J'ai des problèmes de concentration, pas d'intelligence. Peut-être pourrais-tu envisager un instant que tu as mal compris ce que je voulais dire ?

    Pour calculer $a^b$, une calculatrice doit d'abord avoir une approximation décimale de $a$. Ensuite, elle doit calculer une approximation de $\ln(a)$. Ensuite, elle doit calculer une approximation de $b\ln(a)$. Ensuite, elle doit calculer une approximation de $e^{b\ln(a)}$. En tout, ça fait 4 étapes "principales" que la calculatrice doit savoir faire. Je me fiche complètement du fait qu'elle le fait en un clin d'oeil, elle a besoin d'une méthode spécifique pour chacune de ces étapes. Il lui faut un algorithme de calcul pour un paquet de fonctions de référence, et je ne connais pas ces algorithmes-là en détail. C'est de ça que je parlais.
  • Foys : au moins avec ça, dès qu'on connait $x$, le reste n'est qu'un jeu de multiplication et division, donc pour approximer une exponentielle avec ça, ça ne m'a pas l'air compliqué à comprendre. Forcément, l'erreur qu'on commet va dépendre du nombre de décimales connues de $x$. C'est une autre question, ça, la quantité d'erreur qu'on fait en effectuant des opérations sur des approximations. Si je connais $x$ avec $n$ chiffres, combien de chiffres "exacts" je perds en calculant $f(x)$ avec tel algorithme... je trouve ça intéressant.
  • Jouons avec l'algorithme de Horner avec des données de type calculatrice : calcul avec 50 chiffres dyadiques, soit une précision de l'ordre de $10^{-15}$. Pas top.
    sage: def H(x,k):
    ....:     y = 1
    ....:     for j in range(k):
    ....:         y = 1-y*x/(k-j)
    ....:         print y
    ....:     return y
    ....: 
    sage: H(30.n(50),30)
    0.00000000000000
    1.0000000000000
    -0.071428571428571
    1.0793650793651
    -0.24542124542124
    1.2945054945055
    -0.61813186813187
    1.8062589584329
    -1.4630803978630
    3.0901148540900
    -3.6351722811350
    6.7397457070553
    -10.232909511759
    19.058075608986
    -34.733891766849
    70.467783533698
    -150.00239328650
    347.15936912268
    -866.89842280670
    2365.2684258365
    -7094.8052775094
    23650.350925031
    -88687.815968868
    380091.63986658
    -1.9004571993329e6
    1.1402744195997e7
    -8.5520580469980e7
    8.5520580569979e8
    -1.2828087084497e10
    3.8484261253591e11
    3.8484261253591e11
    
    sage: H(30.n(50),100)
    0.70000000000000
    0.78787878787879
    0.75881261595547
    [...]
    0.12085925478650
    0.093555589101272
    0.064444108987279
    0.033338365190819
    -0.00015095572458357
    -0.00015095572458357
    
    Vous préférez $3\cdot10^{11}$ ou $-10^{-4}$ comme approximation de $\exp(-30)$ ?
  • Homo Topi a écrit:
    Si je connais $x$ avec $n$ chiffres, combien de chiffres "exacts" je perds en calculant $f(x)$ avec tel algorithme... je trouve ça intéressant.

    Eh bien on ne connaît pas tout de tête, mais on t'a donné des pistes dans ce fil. Ce sont des choses abordées en analyse numérique, et il doit exister beaucoup de ressources dédiées entièrement à ce genre de choses.
  • @ Georges : j'ai trouvé ton point 1 très joli, même (je croyais) simple de démonstration, cependant je me rends compte qu'il est plus subtil que je ne croyais.

    Soit $x$ un réel arbitraire. Je pose $a_n=\frac{E(nx)}{10^n}$ (développement décimal tronqué au rang $n$ et arrondi par défaut), et $b_n=\frac{E(nx)+1}{10^n}$ (développement décimal tronqué au rang $n$ et arrondi par excès).

    Ces suites me semblent satisfaire les hypothèses, donc $x\in A$ ; à moins que l'aspect dénombrable apparaisse dans le terme algorithme, ou que je dise une grosse bêtise ?
  • Oui, je me doute bien. Je ne demandais pas qu'on me fasse un cours particulier, hein.

    Je reste cependant perplexe face au dernier message de MC... l'algo de Foys est mauvais ?
  • Il est certain que l'on n'a pas de réponse universelle à tes questions, mais en tout cas on en dispose dans beaucoup de situations "pratiques".

    Pour moi, le principal problème est après l'implantation numérique. Il est intéressant de voir que des exemples comme $\int_0^1 \frac{t^{20}}{10-t}dt$ (par récurrence ou par binôme), $\sum_{n=0}^{+\infty} \frac{1000^n}{n!}$ vont mal fonctionner numériquement. Je me souviens aussi avoir fait foirer matlab vers la fin des années 90 sur le système $x_{n+1}=4x_n(1-x_n)$ (système chaotique). J'avais demandé $x_{100}$ d'abord par itération puis par la formule de $x_n=\sin^2(2^n \arcsin(\sqrt{x_0}))$, en faisant $n=100$. Dans le second cas, on s'attendait à une erreur du fait que les chiffres significatifs réduits modulo $2\pi$ ne soient pas les bons, mais en partique Matlab avait carrément donné un nombre très supérieur à 1 pour le sinus d'un réel !
  • J'ai toujours détesté l'analyse numérique, peut-être que je vais réussir à m'y réintéresser positivement maintenant. math2, c'est marrant ça ! Je n'ai jamais utilisé Matlab mais j'ai déjà eu des problèmes tordus moi aussi. Comme quoi, les ordis c'est bien, mais seulement quand ça ne déconne pas :-D
  • J'ai enseigné il y a plusieurs années de cela une initiation à l'analyse numérique avec TD sur ordinateur. Et plutôt que d'en faire des virtuoses de la machine ou de leur apprendre des kilos de méthodes, je leur avais appris à se montrer perplexes quant aux résultats et de toujours avoir une méthode pour confirmer ce que dit la machine (j'avais eu aussi des bugs de maple même en calcul formel d'ailleurs).

    J'ai quand même eu dans cet enseignement un chargé de td, CV "bien comme il faut" (normalien en thèse) exprimer sa surprise car nous avions une matrice à coefficients entiers (donc il en est de même du déterminant), visiblement non inversible, mais dont SCILAB ne donnait pas $0$ pour le déterminant. Ca ne lui a pas traversé l'esprit qu'un nombre entier, dont un logiciel numérique dit qu'il vaut $10^{-12}$, bah en fait c'est $0$ !
  • Math Coss : Pour $x>0$, on peut calculer $\exp(-x)$ avec une précision correcte en procédant ainsi :
    def H2(x, n):
        p = int(x)+1
        x0 = x/p
        y = 1
        for j in range(n,0,-1):
            y = 1 - y*x0/j
        return pow(y, p)
    
    On calcule en fait $(\exp(-\frac{x}{p}))^p$ où $p=\lfloor x\rfloor +1$.

    Avec $n=17$, on obtient 14 chiffres exacts.

    On obtient un tout petit mieux en procédant légèrement différemment :
    def H3(x, n):
        p = int(x)+1
        x0 = x/p
        y = 1
        for j in range(n,0,-1):
            y = 1 + y*x0/j
        return pow(y, -p)
    
    On calcule cette fois $(\exp(\frac{x}{p}))^{-p}$ où $p=\lfloor x\rfloor +1$ et cette fois, avec $n=17$, on obtient 15 chiffres exacts.
  • math2 : j'ai bien ri à ton anecdote, elle prouve qu'un CV ne fait clairement pas tout et que les résultats numériques doivent toujours être soumis à la critique. Un peu comme l'élève qui te trouve une distance Terre-Lune de 150.000 mètres ou une masse négative, et qui passe à la question d'après comme si de rien n'était.
  • Article sur les réels calculables https://fr.wikipedia.org/wiki/Nombre_réel_calculable, ça donne envie de regarder de plus près si on ne connait pas trop.


    PS. Dire que j'avais acheté et en partie lu un bouquin sur la calculabilité et j'ai tout oublié...
  • Je l'ai mis dans mes favoris, comme ça je pourrai y retourner quand moi aussi, j'aurai oublié :-D

    Plus sérieusement, je ne sais pas si j'ai les bases en informatique pour comprendre la mise en pratique de ces notions maintenant, mais c'est intéressant, et ça amoindrit un peu mon dégoût de la programmation/de l'analyse numérique. A conserver pour plus tard...
  • Homo Topi a écrit:
    Je reste cependant perplexe face au dernier message de MC... l'algo de Foys est mauvais ?

    Tout le problème est contenu dans cette phrase:
    Foys a écrit:
    Il faudrait estimer l'erreur commise pendant l'évaluation de l'expression parenthésée ci-dessus cependant.
    cf http://www.les-mathematiques.net/phorum/read.php?4,2271522,2271706#msg-2271706

    La précision des calculs de séquences de simples additions et multiplications relève de l'analyse numérique et ces calculs se comportent déjà mal sur ces exemples.
    Une fonction est un ensemble $f$ de couples tel que pour tous $x,y,z$, si $(x,y)\in f$ et $(x,z)\in f$ alors $y = z$.
  • Homo topi a écrit:
    Comme quoi, les ordis c'est bien, mais seulement quand ça ne déconne pas :-D

    Comme dit le dicton, le problème est souvent entre la chaise et le clavier. Autre formulation, les ordinateurs sont seulement aussi intelligents (ou bêtes, c'est selon) que leur utilisateur. Demander à scilab d'inverser une matrice qui ne l'est pas ce n'est pas très malin, surtout quand on sait que les matrices inversibles sont denses dans $\mathcal M_n(\C)$ et que scilab ne fait que des calculs approchés.

    Pour en revenir à la question du début : comment a-t-on trouvé les décimales de $\pi$ ? En partant de l'intégrale $\int_0^{1/2} \sqrt{1-x^2} \mathrm d x$ qu'on calcule géométriquement puis en développant en série entière la racine carrée et en réarrangeant le tout on trouve
    \[\pi = 12 \sum_{k=0}^\infty \left(\prod_{l=0}^{k-1}(1/2-l )\right)\frac{(-1)^k}{k! 4^k} \left( \frac{1}{4k+2}-\frac{1}{4} \right).\]
    Le $n$-ème terme de cette série est de l'ordre de $4^{-n}$ et donc en sommant $n$ termes on a une erreur de l'ordre de $1/4^n$. En travaillant un peu plus finement on peut estimer les restes de cette série en les comparant à des séries géométriques. Il parait que c'est Newton qui a trouvé cette formule avant de l'utiliser pour calculer une dizaine de décimales de $\pi$... à la main, évidemment :-P
  • Il aurait pu utiliser un ordinateur, il serait allé plus vite !

    Tu es sûr de la borne $1/2$ dans ton intégrale ? Je connais l'intégrale de $0$ à $1$ qui vaut $\dfrac{\pi}{4}$... et quand tu dis que tu "calcules géométriquement" l'intégrale, comment ça ? Géométriquement, le résultat (avec la borne $1/2$ ne m'a pas l'air si facile à comprendre que ça... et avec la borne $1$, on peut juste la calculer "calculatoirement". Le reste de ce que tu racontes n'en devient pas moins intéressant pour autant, cela dit.
  • Homo Topi a écrit:
    gerard : Arrête de me prendre pour un con, je n'apprécie pas. Je pense avoir plus que prouvé sur ce forum que je ne suis pas un abruti. J'ai des problèmes de concentration, pas d'intelligence. Peut-être pourrais-tu envisager un instant que tu as mal compris ce que je voulais dire ?
    Comment voudrais-tu que je sache ce que tu voulais dire ? Je n'ai que ce que tu écris ! Là c'est toi qui me prends pour un con, et la suite de ton message ne vaut pas mieux. Bien sûr que la calculatrice fait ça (sauf trouver une approximation décimale de $a$ puisque c'est justement ce qui est donné par l'utilisateur), mais ça ne pose aucun problème ! Sauf à toi.

    Bon, je vois que tu bloques sur des évidences, parce que c'est de l'analyse (numérique ou pas), je te laisse, je n'ai aucun goût pour le débat dans ces conditions.

    Cordialement.
  • Homo Topi : Oui, il faut bien mettre 1/2 pour la borne, si on prend $1$ on obtient une série qui converge très lentement, le reste est de l'ordre de $1/n$ si je me souviens bien. Pour le calcul géométrique je veux dire que l'intégrale en question est égale à l'aire d'un bout de disque, on peut calculer cette aire avec un tout petit peu géométrie.
  • gerard0 : Tu n'es juste pas sur la même longueur d'onde que moi. Au lieu de dire que tout est de ma faute et que je suis stupide (puisque ce n'est pas le cas, les autres ont très bien compris de quoi je parlais visiblement, tu es le seul à avoir mal compris), tu ne pourrais pas juste admettre qu'on ne s'est pas compris ? Ça te parait vraiment cohérent que je ne savais pas que $a^b = e^{b\ln(a)}$ ? Je ne suis pas un random du Shtam quand même ! Tu m'insultes ! Et tu le répètes en plus ! Je ne reste poli ici que pour respecter les règles du forum, tu as vraiment dépassé les bornes sur ce coup-là. A croire qu'un "mea culpa" de ta part de vaudrait le déshonneur ici. Moi, quand je m'étais pris la tête avec quelqu'un, je m'étais platement excusé, au moins. Peut-être que je ne me suis pas exprimé de manière parfaitement claire, mais mes messages n'ont posé de problème à personne d'autre, alors comment voulais-tu que je me rende compte qu'il y a un problème ? Je ne pense pas être quelqu'un qui cause beaucoup de "drama" sur le forum, en tout cas ce n'est pas ce que j'essaie de faire. Je pense aussi avoir montré que j'ai un minimum de compétences mathématiques, et ça fait 3 ans que je viens ici, alors le fait que tu aies tout jeté à la poubelle comme ça en un clin d'oeil sans prendre le moindre recul de "hein, est-ce que c'est vraiment ça qu'il a voulu dire" et que tu me traites d'idiot en disant que je "bloque sur des évidences", je ne vois pas dans quel univers tu pensais que je pouvais bien le prendre. J'ai le droit à des excuses.

    Quand tu disais qu'on "calcule les choses avec l'exponentielle, les racines etc", moi dans ma tête c'est quelque chose qu'on a d'abord dû apprendre à faire à la calculatrice, donc la question que moi je me posais à ce stade-là c'était comment on avait fait, comment une calculatrice fait-elle pour calculer $\exp(x)$ ou $\sqrt{x}$ pour un $x$ donné. Je demandais quel est l'algorithme de calcul pour les fonctions de référence. C'est de ce genre de choses dont on parle depuis un moment ici.

    Si tu préfères faire le fier et ne pas admettre que toi aussi, tu as une part de responsabilité dans l'embrouille, soit. Moi je préfère qu'on règle les choses comme des adultes. J'ai essayé de réexpliquer clairement de quoi j'essayais de parler. Si tu considères toujours que je suis un abruti, et que tu n'as pas fait le moindre faux pas dans tes réponses dans ce fil, alors je préfère continuer sans ton aide.
  • Renart : j'ai passé mon bac en 2009, je te laisse deviner quelles sont mes compétences en géométrie par rapport aux gens un peu plus anciens qui ont encore eu un semblant de vrai enseignement de maths. Je ne sais pas comment calculer l'aire de ce genre de portion de disque.
  • Ce fil est amusant, même s'il est un peu décousu. Je contribue encore un peu au désordre...

    J'ai appris en faisant les calculs que la méthode de Horner avec $x=30$, qui évite en principe de faire apparaître les nombres très grands ($30^k/k!$ pour $k$ voisin de $30$), se passe mal quand même dans certaines conditions (en augmentant la précision, on finit par calculer l'exponentielle comme il faut).

    Le calcul que propose bisam revient à l'idée de Gilles Benson : on calcule l'exponentielle d'un nombre proche de $\pm1$, par exemple avec la méthode de Horner indiquée par Foys, et on élève à une puissance $p$ idoine (plutôt avec un algorithme qui utilise des élévations au carré qu'en multipliant $p$ fois).

    Ce qui me semble remarquable, c'est que des questions très simples, qui semblent battues et rebattues du côté analytique, prennent tout à coup un nouveau relief quand il s'agit de faire des calculs numériques « pour de vrai ». (Notez que je n'ai pas inventé la remarque sur la série et je ne comprends pas mieux CORDIC qu'Homo Topi.)


    Pour la calculabilité, on se donne $x$ et on forme les suites $\Bigl(\frac{\lfloor 10^nx\rfloor}{10^n}\Bigr)_{n\in\N}$ et $\Bigl(\frac{\lceil 10^nx\rceil}{10^n}\Bigr)_{n\in\N}$. Le problème est de décrire une façon de calculer ces suites sans être obligé de faire la liste des décimales de $x$. Pour certains réels $x$, c'est possibles (exemples : $\exp1$, $\sqrt2$, $\pi$, un rationnel, un nombre algébrique, etc.). En revanche, pour la plupart des réels (tous sauf un nombre dénombrable), il n'y a pas de donnée finie qui puisse « résumer » (permettre de retrouver) la liste des décimales de $x$. Ça se comprend, non ?

    Tiens, la rubrique du mois de Jean-Paul Delahaye dans Pour la Science parle de choses qui me semblent reliées, en fait (pour le lire, désactivez javascript).
  • MC a écrit:
    Ce qui me semble remarquable, c'est que des questions très simples, qui semblent battues et rebattues du côté analytique, prennent tout à coup un nouveau relief quand il s'agit de faire des calculs numériques « pour de vrai ».

    C'est un peu ça que je sous-entendais quand je disais à Poirot que si je lui donnais 25 nombres au pif dont je lui réclamais les décimales, il devra me sortir 25 bidouilles différentes. Les humains sont limités par leur mémoire, alors, lui, peut-être qu'il se rappelle tous les théorèmes nécessaires pour ça, ou au pire, il a des bouquins à disposition. Une calculatrice, elle ne sait faire que ce qu'on lui a appris, donc elle est limitée par sa "banque" d'algorithmes de calcul. Du coup, pour chaque opération qu'on peut demander à la calculatrice, il faut lui avoir donné un algorithme pour effectivement calculer le truc, et il faut un moyen de vérifier que le résultat est correct (donc dans l'absolu, il faut avoir testé les algorithmes à la main au moins sur quelques exemples vérifiables géométriquement). Pour moi, la partie "vérifier que la calculatrice donne effectivement le bon résultat" c'est limite plus important et plus difficile que de trouver des algorithmes pour lui permettre de calculer $\pi$, des $\exp$, des $\sqrt{\phantom{a}}$ etc. C'est tout un travail ! On n'y pense pas quand on achète une calculatrice aujourd'hui, on a de la chance que des gens très doués ont tout implémenté et vérifié que ça marche pour nous.
  • Bonsoir.

    Une discussion récente où il était question de CORDIC ainsi que du stockage de toutes les constantes de l'Univers.

    Philou22 a programmé la méthode sur tableur.

    À noter que la méthode s'appuie sur des valeurs précalculées une fois pour toutes pour fournir un résultat à précision fixée et fait les opérations comme une sorte de dichotomie qui s'approche de plus en plus de la valeur demandée en argument, ce qui fait que la méthode est particulièrement rapide (et adaptable en cours de calcul à une variation de l'argument, ce qui a permis son essor dans l'aviation ou de légères modifications de cap doivent être faites en permanence, à l'époque l'algorithme était câblé sur un support physique qui permet ce genre de choses).

    Cerise sur le gâteau : l'algorithme en lui-même est un seul et unique bout de code, seule change la liste de valeurs précalculées suivant la fonction voulue entre les fonctions trigonométriques (y compris hyperboliques, ce qui donne aussi l'exponentielle très facilement en ne jouant qu'avec des arguments réels, au moyen entre autres de $e^x = sinh(x) + cosh(x)$ ainsi que sa fonction réciproque).

    L'algorithme fonctionne même pour les multiplications et divisions, à une petite restriction près sur l'amplitude d'un des facteurs.

    C'est pour toutes ces raisons là que les calculettes peuvent, à moindre frais, donner la plupart des fonctions courantes (même les élévations à la puissance via la propriété déjà mentionnée plus haut de l'exponentielle), ce ne sont que des combinaisons plus ou moins sophistiquées des mêmes calculs, la précision étant contrôlée en cours de route via divers artifices comme le calcul de plus de chiffres que ce que permet l'affichage et une grande part de l'analyse numérique est de déterminer le contrôle de cette précision au fur et à mesure des calculs, sous peine de calculer des choses ineptes (il existe d'ailleurs des tests d'initié pour déterminer la précision du codage de l'algorithme et le nombre de valeurs précalculées, ce qui donne indirectement des informations sur le matériel utilisé et permet de 'classer' les calculettes suivant certaines catégories).

    Aussi, pour finir avec ce mythe, n'oubliez pas que les calculettes ne peuvent renvoyer qu'un nombre fini de valeurs, liées à la précision implémentée et à l'étendue des valeurs possibles.
    A l'heure actuelle, avec les logiciels qui fournissent des résultats en précision arbitraire, on aurait tendance à penser que le nombre de valeurs possibles à renvoyer est incommensurable, mais même dans ce cas il est fini (et lié à la quantité de mémoire disponible).

    À bientôt.

    [Édit : Correction de quelques coquilles et ajout d'éléments de contexte.]

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • @math2 : Le problème dans ton raisonnement concluant à "tout réel est calculable" est bien l'oubli du mot "algorithme", oui.

    @autres : Sur le lien Wikipédia donné par raoul, on apprend que l'égalité entre réels calculables n'est pas décidable, ce que je comprends par : il n'existe pas d'algorithme, qui, quand on lui donne le programme de deux algorithmes calculant chacun une suite de rationnels convergeant vers deux réels $x$ et $y$, répond correctement sur toutes les entrées à la question "$x=y$ ?". Je suis un peu scotché, je ne le savais pas.
  • Pour Georges Abitbol : oui, et c'est très facile à comprendre.

    Imaginons que tu aies deux suites de rationnels convergeant vers $\sqrt{2}$, l'une par valeurs plus grandes, l'autre par valeurs plus petites, un algorithme qui les analyseraient ne donnerait le bon résultat qu'en terminant sur la même valeur finale.

    L'infini, c'est long, surtout sur la fin.

    À bientôt.

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • @Dreamer : Mmmmh c'est plus compliqué que ça : tu dis que l'algo qui consiste à laisser tourner les deux algos et voir si ça colle ne termine pas ; alors que ce que j'ai compris de ce que dit Wiki, c'est qu'aucun algo ne fonctionne.
  • Bonjour.

    Que signifie "ne pas fonctionner" pour un algorithme ?
    Qu'il est nécessairement déficient ?

    Ce que je connais comme problème, c'est le problème de l'arrêt (voir le fameux article de Turing sur les nombres calculables qui traite de ce problème, il est vraiment facile à trouver).

    À bientôt.

    Cherche livres et objets du domaine mathématique :

    Intégraphes, règles log et calculateurs électromécaniques.

  • Georges : un algorithme qui teste $x=y$, concrètement, ça marche comment ? Est-ce que c'est un truc du genre, il calcule $|x-y|$ et compte le nombre de zéros dans le développement décimal ?

    Si tu prends deux algorithmes différents, l'un qui te dit que $(u_n)_n$ tend vers $x$, et l'autre qui te dit que $(u_n)_n$ tend vers $y$, ça ne me paraît pas si absurde qu'un ordinateur ait du mal à tester $x=y$... rien ne nous dit que le procédé de calcul des deux algorithmes est "suffisamment similaire", donc il y a certainement des décimales qui diffèrent vers la fin des développements décimaux de $x$ et $y$ dans un bon nombre de cas. Le reste dépend de la précision de l'algorithme qui teste $x=y$ j'imagine.

    Peut-être que je suis complètement hors-sujet, je ne sais pas.
Connectez-vous ou Inscrivez-vous pour répondre.