Comment faire un calcul d'erreur ?
Bonjour,
J’ai écrit par distraction une calculatrice à mille décimales.
Je prends un exemple, voilà comment je calcule $e^{\sqrt{x}}$:
$\sqrt{x}$ est calculée par la méthode de Héron, initialisée comme suit :
$u = max(x,1)$
tant $u^2 \geq x$ [le test assure que la suite du Héron reste décroissante ]
$u = \frac{1}{2} \left( u + \frac{x}{u} \right)$
fin tant que
retourner $u$
Il y a un arrondi à la millième décimale dans tous les calculs intermédiaires,
ce qui fait que les fractions donnent "autant" d'erreur que les irrationnels.
Puis exp(x) est calculée, comme somme de sa série, par :
$e=1$
$n=1$
$v=1$
$\epsilon=10^{-1000}$
tant que $v > \epsilon$
$v=v*x/n$
$e=e+v$
$n=n+1$
fin tant que
retourner $e$
Là aussi, tous les calculs intermédiaires sont arrondis à la millième décimale.
Comment puis-je majorer à-priori l’erreur sur $e^{\sqrt{x}}$ connaissant l’erreur $\Delta(x)$ portant sur $x$ en entrée ?
Par exemple, sur l'identité:
$ \cos \left( \frac{2 \pi }{ 5} \right) - \left( \frac {\sqrt{5}-1} {4} \right) = 0 $
Le cosinus étant calculé avec une série de même nature et la racine
par la méthode de Héron, la calculatrice me renvoie une erreur de
$228 \times 10^{-1000}$. Puis-je la prévoir ?
Plus généralement, je souhaiterais avoir un algorithme pour suivre un majorant de l’erreur « à la trace » au cours des calculs.
Comment évaluer ces erreurs pour pouvoir encadrer un résultat final ?
J’ai pensé à des formules de différentielles de physique
$\Delta(u+v) \leq \Delta(u)+\Delta(v)$
$\Delta(uv) \leq |u| \Delta(v)+ |v| \Delta(u)$
$\Delta (\frac{1}{u}) \sim \frac{\Delta u} {u^2}$, ce qui me donnerait pour les calculs itératifs $u_{n+1}=f(u_{n})$ une récurrence sur l’erreur :
$v_{n+1} = f^{'} (u_{n}) \times v_{n}$
Puis-je utiliser, par ailleurs, les probas et stats pour obtenir une estimation de l’erreur, en estimant que l'arrondi suit une loi de probabilité ?
Par ailleurs, peut-on transformer les calculs d'erreur en calculs de probabilités ?
Toutes vos idées sont les bienvenues.
Cordialement,
J’ai écrit par distraction une calculatrice à mille décimales.
Je prends un exemple, voilà comment je calcule $e^{\sqrt{x}}$:
$\sqrt{x}$ est calculée par la méthode de Héron, initialisée comme suit :
$u = max(x,1)$
tant $u^2 \geq x$ [le test assure que la suite du Héron reste décroissante ]
$u = \frac{1}{2} \left( u + \frac{x}{u} \right)$
fin tant que
retourner $u$
Il y a un arrondi à la millième décimale dans tous les calculs intermédiaires,
ce qui fait que les fractions donnent "autant" d'erreur que les irrationnels.
Puis exp(x) est calculée, comme somme de sa série, par :
$e=1$
$n=1$
$v=1$
$\epsilon=10^{-1000}$
tant que $v > \epsilon$
$v=v*x/n$
$e=e+v$
$n=n+1$
fin tant que
retourner $e$
Là aussi, tous les calculs intermédiaires sont arrondis à la millième décimale.
Comment puis-je majorer à-priori l’erreur sur $e^{\sqrt{x}}$ connaissant l’erreur $\Delta(x)$ portant sur $x$ en entrée ?
Par exemple, sur l'identité:
$ \cos \left( \frac{2 \pi }{ 5} \right) - \left( \frac {\sqrt{5}-1} {4} \right) = 0 $
Le cosinus étant calculé avec une série de même nature et la racine
par la méthode de Héron, la calculatrice me renvoie une erreur de
$228 \times 10^{-1000}$. Puis-je la prévoir ?
Plus généralement, je souhaiterais avoir un algorithme pour suivre un majorant de l’erreur « à la trace » au cours des calculs.
Comment évaluer ces erreurs pour pouvoir encadrer un résultat final ?
J’ai pensé à des formules de différentielles de physique
$\Delta(u+v) \leq \Delta(u)+\Delta(v)$
$\Delta(uv) \leq |u| \Delta(v)+ |v| \Delta(u)$
$\Delta (\frac{1}{u}) \sim \frac{\Delta u} {u^2}$, ce qui me donnerait pour les calculs itératifs $u_{n+1}=f(u_{n})$ une récurrence sur l’erreur :
$v_{n+1} = f^{'} (u_{n}) \times v_{n}$
Puis-je utiliser, par ailleurs, les probas et stats pour obtenir une estimation de l’erreur, en estimant que l'arrondi suit une loi de probabilité ?
Par ailleurs, peut-on transformer les calculs d'erreur en calculs de probabilités ?
Toutes vos idées sont les bienvenues.
Cordialement,
Réponses
-
un calcul d'erreur, chuis pas fort, mais une erreur de calcul la ca va je domine
bon désolé ::o je =======>
t-mouss (pas drole ^^) -
excellent. X:-(
-
bonjour,
Soit x un réel $\geq 1$.
Il est bien connu que la suite
$u_{0}=x$
$u_{n+1}=\frac{1}{2} \left( u_{n}+ \frac{x}{u_{n}} \right)$
converge vers $\sqrt{x}$.
Soit k un entier non nul. Soit la suite $v$ définie par:
$v_{0}={10^{-k}} E \left( x \times 10^{k} \right)$
et pour $n \geq 1$, la récurrence :
$x_{n} = {10^{-k}} E \left( v_{n} \times 10^{k} \right)$
$y_{n} = {10^{-k}} E \left( \frac{x}{v_{n}} \times 10^{k} \right) $
$v_{n+1}=\frac{1}{2} \left( x_{n}+ y_{n}} \right)$
Je voudrai majorer la différence $|u_{n}-v_{n}|$ en fonction de l'entier k ?
Cordialement. -
Déplacez ce fil vers l'analyse. Il n'a rien à faire en informatique.
On n'y traite pas de format, de place mémoire ou d'optimisation,
mais de majoration et minoration. Selon Dieudonné (Jean), c'est de la pure
analyse.
[Voilà le fil est dans la section Analyse.
Mais calculer la propagation de l'erreur d'arrondi m'apparaissait plutôt comme relevant de Math/Info ? AD] -
je suis d'accord formellement avec vous, AD.
c'est un problème issu de l'informatique, mais qui doit être abordé par des méthodes d'analyse ou de statistiques. c'est pour cela que je souhaitais poser ma question dans la rubrique "analyse".
Avec toutes mes excuses. -
N'as tu pas un moyen, en choisissant convenablement les valeurs initiales, d'approximer les valeurs recherchées par "en haut" et par "en bas" ? Ainsi tu obtiendrais un encadrement garanti du résultat au lieu d'une simple valeur. C'est la base de l'analyse par intervalle...
[edit]
C'est curieux, mais j'ai peur que ton test sur la méthode de Héron ne risque d'entrainer une boucle infinie... Accessoirement, tu peux tout simplement calculer
\[
\epsilon=|u^2-x|
\]
qui te donnera une indication raisonnable de l'erreur, non ? Et du coup arrêter ta boucle quand $\epsilon$ devient plus petit qu'une valeur donnée... -
Bonjour JobHertz,
merçi pour ta réponse. Je crois que nous pouvons discuter des problèmes d'arrondis dans les calculs, sur l'exemple de la méthode de Héron car cette méthode est paradigmatique (exemplaire) pour plusieurs raisons:
1) La méthode de Héron est l'itération de Newton
$$u_{n+1}= u_{n} - \frac{ f(u_{n})}{f'(u_{n})}$$
appliquée au zéro de la fonction $y \longrightarrow y^2-x$ quand on souhaite calculer le nombre $\sqrt{x}$
Or tout nombre peut être probablement considéré comme le zéro d'une équation bien choisie.
2)
De plus, la méthode itérative de Newton est auto-correctrice et les erreurs d'arrondi dans les calculs intermédiaires ne la font pas "dévier" de sa limite.
En théorie, c'est à dire sans s'occuper d'arrondi dans les calculs intermédiaires,
l'égalité:
$u_{n+1}-u_{n}= \frac {x-u_{n}^2}{2 u_{n}}$
garantit que la suite est strictement décroissante,ie, que l'algorithme "avance",
tant que le carré de $u_{n}$ reste strictement supérieur à x.
Si l'arrondi pratiqué sur $u_{n}$ avant d'itérer augmente $u_{n}$, la suite risque
de devenir périodique (elle est discrète puisque nous ne considérons pas de valeurs décimales plus fines que la discrétisation 10^{-k}, k étant fixé=1000).Mais si l'arrondi diminue $u_{n}$, deux cas sont possibles:
La convergence est accélérée si $u_{n}$ reste supérieure au réel $\sqrt{x}$ ou bien $u_{n}$ devient inférieure à sa limite et la suite , périodique en colimaçon.
Le problème est donc d'évaluer l'écart entre $u_{n}$ et sa limite, dès que la suite est devenue périodique.
Concernant les intervalles, j'en suis arrivé à la même question: faut il remplacer
les nombres par des intervalles et les calculs sur les nombres (addition, multiplication, inverse) par des calculs sur les intervalles. ça pose quelques problèmes. Il y a la définition du nombre zéro comme intervalle ]-10^{-k};10^{k}[ et le fait que dès qu'un nombre, donc un intervalle, intersecte l'intervalle zéro, il devient lui-même zéro.
Une autre question: doit on envisager le problème des arrondis de manière "macroscopique" , cad, au niveau de la méthode itérative (j'ai remarqué que l'approximation du log,fonction concave, produit des valeurs par défaut). Ou bien au contraire de manière "microscopique" sur les les quatre opérations de base (addition, soustraction, multiplication ,inverse) ?
Y a t il un moyen d'introduire un zeste de probabilité (et des stats) sur l'arrondi ?
Cordialement, -
Bonjour,
Pour la méthode de Newton, il faut tout d'abord rappeler que la convergence n'est que locale : elle ne converge en général que si la valeur initiale est déjà assez proche de la valeur cherchée.
Si on appelle $w_n$ l'erreur entre la valeur théorique et la valeur calculée par la méthode de Newton à l'étape $n$ on a : $w_{n+1} \leq w_n^2$. Ceci permet d'obtenir une majoration intéressante (si $w_0 < 1$) de l'erreur à l'étape $n$ : $w_n \leq (w_0)^{2^n}$.
Cela permet également de voir que l'on a l'inégalité : $log_{10}(w_{n+1}) \leq 2 log_{10}(w_n)$, et si $w_n < 1$ ($log_{10}(w_n) < 0$) pour avoir à partir d'un certain rang, on peut alors affirmer que le nombre de chiffres exacts après la virgule double à chaque itération (au pire !).
Je suis conscient de n'avoir pas répondu à la question car je n'ai pas tenu compte de l'erreur machine. Mais j'espère que cela pourra aider.
Pour plus d'infos sur ce que je viens d'écrire, je recommande la lecture du livre d'Analyse Numérique de M. Schatzman.
J'ai également trouvé un lien vers un pdf assez intéressant que je vous soumets : \lien{http://math.univ-lyon1.fr/\~{}filbet/Papers/book.pdf}
On y parle entre autre de la méthode de Newton (p87) et également de stabilité par rapport aux erreurs (p133) (à laquelle me font penser furieusement ces erreurs machines qui se cumulent de proche en proche).
[Lien réparé. AD] -
je relance la discussion..
si $\epsilon=10^{-1000}$,
la calculatrice que j'ai écrite me renvoie ,sur les identités remarquables suivantes, au lieu de zéro :
$1- {\cos \left( \frac{\pi}{4} \right)}^2 - {\sin \left( \frac{\pi}{4} \right)}^2 = 9 \epsilon$
$\ln \left( e \right) -1 = 708 \epsilon $
$ \frac{ \sqrt{5} - 1}{4} - \cos \left( \frac{2 \pi}{5} \right) = 8371 \epsilon $
$1000 \ln \left( 2 \right) - \ln \left( 2^{1000} \right) = 491455 \epsilon$
$\frac{ \pi}{4} - 4 \arctan \left( \frac{1}{5} \right) + \arctan \left( \frac{1}{239} \right) = 22797 \epsilon$
Quant à $\left( \left( \pi ^ {30} \right) ^ 3 \right) ^ 2 - \left( \left( \pi ^ {30} \right) ^ 2 \right) ^ 3$ , c'est la Bérésina
puisque au lieu de zéro, le résultat est de l'ordre de $10^{90} \epsilon$.
Quelles méthodes puis-je employer pour majorer a-priori ces erreurs ?
Cordialement,
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.2K Toutes les catégories
- 9 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
- 64 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
- 314 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
- 773 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres
Qui est en ligne 25
+18 Invités