Discussion:Méthode de dichotomie

Dichotomie non constructive

Il est affirmé dans l'article que « L'avantage de la méthode est la convergence inconditionnelle si f(a) et f(b) sont de signes opposés et ce, aussi compliquée que soit la fonction f ». Il y a confusion entre démonstration du théorème des valeurs intermédiaires et mise en oeuvre algorithmique (objet de cet article). La démonstration définit deux suites convergeant vers la racine, mais cette démonstration n'est pas constructive et son application numérique ne peut traiter tous les cas, contrairement à ce que laisse penser l'article. Celui-ci devra être amélioré sur ce point.

Considérons une suite $(a_{n})$ d'entiers relatifs valant -1, 0 ou 1 et posons $\alpha =\sum _{n=1}^{\infty }{\frac {a_{n}}{3^{n}}}$. Considérons maintenant la fonction f affine sur les intervalles $\left[0,{\frac {1}{3}}\right]$, $\left[{\frac {1}{3}},{\frac {2}{3}}\right]$ et $\left[{\frac {2}{3}},1\right]$ et telle que $f(0)=-1$, $f(1)=1$, $f(1/3)=f(2/3)=\alpha$. La dichotomie demande de déterminer le signe de $f(1/2)=\alpha$. Or la détermination de ce signe peut se révéler difficile, voire impossible numériquement. Il suffirait par exemple de déterminer le signe du premier terme non nul de la suite $(a_{n})$ s'il en existe. Malheureusement, il n'existe aucun algorithme général répondant à ce genre de question.

Contrairement à ce qu'on croît, la dichotomie n'est pas un processus constructif, et d'ailleurs, le théorème des valeurs intermédiaires n'est pas admis sous cette forme en analyse constructive. (cf Erret Bishop, Douglas Bridges, Constructive analysis, Springer-Verlag (1985), p.8).

A noter que, si $\alpha >0$, la valeur c telle que f(c) = 0 est inférieure à 1/3 ; si $\alpha <0$, la valeur c telle que f(c) = 0 est supérieure à 2/3, et on est incapable en général de donner la moindre valeur approchée acceptable de c.

Exemple : Posons $a_{n}=0$ si $n^{17}+9$ et $(n+1)^{17}+9$ sont premiers entre eux, $a_{n}=1$ si $n^{17}+9$ et $(n+1)^{17}+9$ ne sont pas premiers entre eux et que n est pair, $a_{n}=-1$ si $n^{17}+9$ et $(n+1)^{17}+9$ ne sont pas premiers entre eux et que n est impair. Donner une valeur approchée de c à 1/10 près. On notera qu'on est parfaitement capable de calculer une valeur approchée de $\alpha$ à toute précision demandée, ainsi que toute valeur approchée de f(x) pourvu qu'on ait donné une valeur approchée adéquate de x.

Voir Discuter:Théorème des valeurs intermédiaires. Theon (d) 5 février 2008 à 10:38 (CET)

Je ne suis pas assez savant pour discuter ce qui précède. Cependant, il me semble que la méthode de dichotomie a été inventée pour résoudre des problèmes de calcul numérique. Dans ce cadre, la complication de ceux-ci peut être pratiquement sans limite. C'est une différence essentielle avec d'autres méthodes comme la méthode de Newton, appréciée pour sa convergence plus rapide... lorsqu'elle est utilisable. Il s'agit quand même d'un résultat important pour le lecteur à la recherche d'une méthode de calcul. Jct (d) 5 février 2008 à 11:30 (CET)

Suite de la controverse. Il est dit maintenant que On pourra alors se contenter de calculer une valeur x telle que f(x) soit en valeur absolue inférieure à une erreur donnée. En calcul numérique, sujet des deux alinéas précédents, un principe veut que l'on s'arrête lorsqu'on a atteint la précision souhaitée a priori ! Il me semble essentiel de remarquer que c'est plus facile avec la dichotomie qu'avec la plupart des autres méthodes d'approximations successives. Les références mathématiques savantes apportent certainement une information. Je maintiens que les gens qui cherchent à s'informer sur la méthode ont généralement, comme moi, une culture mathématique limitée. Ces références savantes devraient donc être disjointes de la description de la méthode de calcul numérique. Jct (d) 6 février 2008 à 11:42 (CET)

L'objection de Théon est longuement débattue dans Discuter:Théorème des valeurs intermédiaires. Elle est parfaitement fondée : elle signale juste que le fait de faire un test "donner le signe de f(...)" risque d'arrêter le processus avant que ne soit atteinte la tolérance absolue que l'on souhaite (b-a)/2ⁿ⁺¹ inférieure à un certain seuil. Il suffit d'essayer l'algorithme pour f(x)=1+(x-sqrt(2,1)¹¹-1(sans simplifier et en ne remarquant pas que la solution est x=sqrt 2,1), tu vas voir le processus s'arrêter très vite : en fait si a=1 et b=2, il t'affirme que la racine est 1.5 sur une calculatrice et 1,4375 avec un tableur ). Mais je ne pense pas que tu mettes en doute l'objection. Tu sembles cependant trouver que cela nécessiterait un paragraphe spécial du genre Limite de la méthode. Est-ce cela ? l'article pour l'instant ne comportant pas de section, Théon est resté très raisonnable et le glisse en remarque. Je me demande si on ne pourrait pas créer trois sections Principe, programmation et Limite de la méthode où Théon pourrait expliquer davantage pourquoi le terme d'algorithme est trompeur mais je crains que cela ne déséquilibre un peu plus l'article. HB (d) 6 février 2008 à 14:33 (CET)

Voyant que c'est allé plus loin qu'une remarque (les deux points de vue sont intimement mélangés dans diverses phrases), je m'apprêtais à faire la même proposition que toi ! Si personne n'y voit d'inconvénient je me propose de procéder à cette réorganisation, laissant les personnes plus savantes corriger la troisième section. Le déséquilibre ne me gêne pas (des notions compliquées nécessitent plus d'explications que des notions simples) à condition de ne pas noyer dans les premières les secondes qui constituent pour moi, et je pense pour une majorité, l'essentiel de la méthode de dichotomie. Jct (d) 7 février 2008 à 09:43 (CET)

Autre exemple : f(x) = (x - 0.3)*exp(- 1/(x-0.3)^2) sur [0,1]. Mon tableur donne fâcheusement comme limite x=0,25 (avec une précision de 15 chiffres), alors que la solution est 0,3. Theon (d) 7 février 2008 à 18:47 (CET)

En considérant les valeurs de f(x) qui varient avec un pas de 0.01 entre 0.2 et 0.4, mon tableur donne, outre #DIV/0! pour x=0.3, des résultats analogues à ceux que j'ai présentés dans Discussion Utilisateur:HB. Pour x variant de 0.27 à 0.33, le résultat est nul. Dans cet intervalle, on atteint visiblement le dépassement de capacité virgule flottante. Avec un langage de programmation tel que Fortran, celà conduit à un plantage qui avertit le programmeur de l'existence d'un problème. Avec un tableur ou une calculette, pour ne pas traumatiser l'utilisateur moyen, le résultat est arrondi à zéro.

Ceci s'applique à toute suite qui converge vers zéro : il suffit d'attendre assez longtemps pour que la pathologie apparaisse d'une manière ou d'une autre, une suite mal conditionnée ad hoc ayant l'avantage de conduire au résultat en quelques pas. Il me semble que cette limitation du calcul numérique avec un nombre de bits donné n'autorise pas à tirer des conclusions profondes.

Ces remarques élémentaires ne m'autorisent pas à prendre parti sur le théorème des valeurs intermédiaires, encore moins sur l'analyse constructive. J'ai donc été choqué lorsque j'ai vu que des notions qui me dépassent apparaissaient, non en commentaires, mais dans des corrections qui noient l'utilité pratique de la méthode. Jct (d) 8 février 2008 à 11:17 (CET)

La méthode par dichotomie appliquée sur [0,1] ne passe pas par la valeur 0.3 donc le fait que le tableur donne #DIV/0! en 0.3 n'intervient pas pour cette fonction dans l'application de l'algorithme. On pourrait de toute façon définir la fonction par SI x=0.3 ALORS 0 SINON etc... Comme tu le remarques, la valeur numérique calculée par le tableur ou la calculatrice donne 0 quand on tombe dans l'intervalle 0.27..0.33. Quand on applique la méthode par dichotomie telle qu'elle est donnée dans l'article, on applique donc le ELSE du test conditionnel, ce qui finit par nous faire tomber dans un mauvais intervalle. L'algorithme par dichotomie occulte totalement la difficulté numérique ainsi rencontrée, et cette difficulté ne peut être contournée. Il est donc nécessaire d'indiquer au lecteur qu'une telle difficulté existe, conduisant parfois à des valeurs erronées de la racine, et ne pas lui faire croire que, dans tous les cas, aussi compliquée que soit la fonction, l'algorithme conduit à la racine. C'est ce que je me suis borné à indiquer. Les explications plus compliquées, données en début de la page de discussion, ont pour but de montrer qu'hélas, cette difficulté n'est pas seulement liée à un problème d'arrondi numérique, mais relève d'un problème plus profond, celui de l'impossibilité algorithmique à tester si un réel est nul. Theon (d) 8 février 2008 à 19:16 (CET)

De manière plus naïve, il me semble que le problème est de même nature que celui qui concerne une suite géométrique de raison inférieure à 1. Mon tableur me donne 1.00E+000, 1.00E-050, 1.00E-100, 1.00E-150, 1.00E-200, 1.00E-250, 1.00E-300, 0.00E+000, 0.00E+000... Avec un langage de programmation, j'obtiendrais un message qui ressemblerait au mieux à floating underflow, au pire à rien du tout. S'agit-il vraiment d'un problème algorithmique ? Il s'agit, me semble-t-il, d'une limite que rencontre tout calcul numérique, pourquoi donc faire un sort particulier à la dichotomie ? Cette limite peut être repoussée en augmentant le nombre de bits ou rapprochée en utilisant des exemples ad hoc.

Pour revenir à la dichotomie, la phrase si on se donne la tolérance relative on connaît [en théorie] le nombre maximum d'itérations nécessaires pour satisfaire cette tolérance a été corrigée (?) par On pourra alors se contenter de calculer une valeur x telle que f(x) soit en valeur absolue inférieure à une erreur donnée., ce qui revient à dire la même chose mais de manière négative et doit satisfaire l'utilisateur de la méthode, sauf à passer de simple précision à double précision, changer de langage de programmation ou d'ordinateur.

L'expression aussi compliquée que soit la fonction f a été censurée alors qu'elle me paraît essentielle. En effet la méthode marche fort bien quels que soient le nombre et la complication des subroutines impliquées dans le calcul de f. Je ne connais pas la plupart des méthodes regroupées sous le titre Recherche d'un zéro mais je doute qu'elles réussissent cette performance. Jct (d) 9 février 2008 à 11:34 (CET)

trop de discussion nuit à l'action et à la sérénité. J'ai donc fait une proposition essayant de tenir compte de vos deux points de vue.N 'hésitez pas à reverter ou corriger. HB (d) 9 février 2008 à 15:29 (CET)

Merci d'avoir pris en compte mes remarques. Quitte à nuire une fois de plus à l'action et à la sérénité, puis-je préciser mon point de vue ?

• Le calcul numérique ne peut, en général, résoudre exactement une équation en nombres dits réels. Il s'agit en fait de nombres décimaux et c'est ce qui est, selon moi, à l'origine du problème. A quelques exceptions près (par exemple l'équation x = 0), la solution numérique n'est donc pas un nombre mais un intervalle. Dans les conditions imposées au calcul les différents termes de l'intervalle sont égaux en droits.
• Cet intervalle indifférencié peut être réduit en augmentant la précision du calcul (le nombre de bits). Il peut également être augmenté dans des proportions considérables en utilisant une équation ad hoc. Par contre, il est indépendant de l'algorithme utilisé, sauf à imaginer un algorithme ad hoc, suffisamment compliqué pour accroître significativement les erreurs.
• Cette impossibilité de résoudre exactement une telle équation conduit les programmeurs à éviter un test de la validité de (f(x) = 0), sans aucune pertinence, au profit de (|f(x)| < ε).
• Si les exemples cités avaient été programmés dans un langage classique, le programme se serait arrêté avant de donner un résultat qu'il aurait considéré comme faux. Ceci aurait conduit à s'interroger sur la validité des calculs. Je viens de découvrir qu'un tableur accepte l'underflow en mettant tranquillement à zéro ce qu'il n'est pas capable de calculer. Dans un cas d'itération vers zéro, il est donc souhaitable de s'interroger sur la signification des résultats obtenus.
• La dichotomie ne fait pas exception. Jct (d) 10 février 2008 à 17:11 (CET)

Je n'ai sans doute pas été assez clair dans mes explications. Les tests entre réels se font evidemment sur des valeurs approchées, à une précision arbitraire que peut choisir en théorie le programmeur. Or, si on se donne deux réels a et b, par exemple par des valeurs approchées à la précision que l'on voudra, il n'existe pas de test algorithmique permettant de décider si a > b ou pas, même en augmentant la précision (Exemple du préambule : on peut calculer $\alpha$ avec toute la précision voulue. Peut-on dire si $\alpha >0$ ou pas ?). Par contre, si on se donne trois réels a, b, c pour lesquels on sait a priori que a < b, il est parfaitement possible de décider algorithmiquement si a < c ou si c < b. Il suffit en effet de faire une itération sur le nombre de décimales calculées de a, b, et c. Puisque a < b, au bout d'un nombre fini de boucles (celui nécessaire pour distinguer numériquement a de b), l'une ou l'autre des conditions a < c ou c < b sera vérifiée. Rien de tel n'a lieu pour comparer directement deux réels. Il est donc possible d'écrire des algorithmes théoriques valides sur les nombres réels, mais malheureusement, la méthode de dichotomie n'entre pas dans ce cadre. Le « test » qui y est fait ne relève pas d'un algorithme. J'insiste donc : le problème que je soulève sur la méthode de dichotomie n'est pas un problème de précision due à tel ou tel logiciel, mais un problème d'ordre algorithmique. L'algorithme présenté n'en a que les apparences. Bien évidemment, on peut arrêter l'algorithme dès que $|f(x)|<\varepsilon$, mais dans ce cas, on n'a aucune garantie sur la précision obtenue de la racine, et on calcule autre chose, non pas une valeur approchée de la racine, mais un nombre dont l'image est une valeur approchée de 0. Comme indiqué dans l'article, cet énoncé est d'ailleurs la version constructive du théorème des valeurs intermédiaires. Theon (d) 10 février 2008 à 18:29 (CET)

Je n'ai sans doute pas été assez clair dans mon exposé du problème. Dans le cas de la fonction f(x) = (x - 0.3)*exp(- 1/(x-0.3)^2), un tableur donne le résultat faux 0 pour toutes les valeurs de x comprises entre 0.27 et 0.33 tandis qu'un langage de programmation classique préfèrerait ne pas donner un résultat qui dépasse la (les) capacité(s) de la machine. Quel algorithme permettrait alors de choisir entre ces diverses valeurs ? Désolé de nuire encore à la sérénité, surtout si la réponse à cette question est évidente. Jct (d) 11 février 2008 à 09:38 (CET)

Mais il me semble au vu des derniers messages que nous sommes bien d'accord. Que le logiciel donne la valeur 0 ou un message signalant un underflow, dans les deux cas, on risque de ne pas pouvoir donner de valeur précise à la racine, et il n'y a pas d'algorithme général pour cela. Il convient bien de signaler ce problème au lecteur. La méthode de dichotomie n'est pas universelle, et la restriction apportée par HB (Sous l'hypothèse que le signe de f(c) soit déterminable) cerne bien le cadre dans lequel la méthode est applicable. Ainsi, un programme plus correct aurait pu être

If ((f(xL) * f(xM)) > 0) then on jette la moitié de gauche

Else If ((f(xL) * f(xM)) < 0) then on jette la moitiè droite

Else on jette l'éponge :-). Theon (d) 11 février 2008 à 10:44 (CET)

Au risque de lasser, il me semble que je n'ai toujours pas été assez clair. Le problème que je croyais poser à plusieurs reprises est celui-ci : avec une précision donnée, quel algorithme autre que la dichotomie donnerait un résultat plus précis que ceux qui sont évoqués ? Selon moi, ce problème devrait être signalé au lecteur à propos de tout algorithme (ou presque, il y a certainement des subtilités qui m'échappent) portant sur des flottants. Pourquoi faire un sort particulier à la dichotomie ? Accessoirement, cette controverse n'aurait pas existé si l'article avait sa structure actuelle. Jct (d) 12 février 2008 à 10:19 (CET)

Tu n'as pas tort... Pour les exemples cités, je ne vois, avec ma faible expérience, aucun autre algorithme performant. Le problème était l'impression de toute puissance de la méthode qui émanait de la première version de l'article (on arrive toujours au résultat, même lentement). Par exemple, la méthode de Newton pose dès le départ les limites de son action : une dérivée non nulle au voisinage de la racine, dérivée calculable, ne pas se situer trop loin de la racine au risque de boucler ... En présentant les limites de la méthode de dichotomie, on rétablit un équilibre. C'est une bonne méthode mais, comme toutes les autres, elle ne peut pas résoudre tous les cas. HB (d) 12 février 2008 à 10:49 (CET)

Il faut distinguer ce qui relève d'un problème dû à une utilisation des flottants à une précision donnée, et ce qui relève d'un problème algorithmique quelle que soit la précision utilisée. Par exemple, si on suppose que la fonction est strictement croissante, alors il existe un algorithme par trichotomie qui assure la convergence vers la racine. Cet algorithme utilise le fait que, si x < y et si z est donné, alors on peut décider de manière certaine si x < z ou si z < y. L'algorithme est du genre :

 répéter 
   si x < z alors sortir
   sinon si z < y alors sortir
   sinon augmenter la précision du calcul
 

Le fait qu'on sache a priori que x < y garantit que la boucle se terminera. L'algorithme fonctionne avec des flottants en précision limitée, mais qu'on peut augmenter à son gré. La différence avec la dichotomie est que, si on écrit :

  répéter
     si ((f(xL) * f(xM)) > 0) alors sortir
     sinon si ((f(xL) * f(xM)) < 0) alors sortir
     sinon augmenter la précision du calcul

alors, on risque d'entrer dans une boucle infinie avec une augmentation indéfinie du nombre de décimales dans le cas malheureux où l'on est incapable de déterminer le signe de f(xM). Le problème n'est donc pas un problème numérique d'utilisation des flottants, mais un problème algorithmique d'utilisation de tests qui ne permettent pas de tirer de conclusion avec les flottants, quelle que soit la précision utilisée. La méthode de dichotomie entre dans ce dernier cadre, et contrairement à ce qu'on croit, elle n'est pas une méthode algorithmique universelle. A ma connaissance, il n'existe aucun algorithme traduisant le théorème des valeurs intermédiaires basé uniquement sur l'hypothèse f(a) < 0 < f(b). Theon (d) 13 février 2008 à 11:07 (CET)

Comment la trichotomie (ou toute autre méthode numérique) réussirait-elle à accomplir le miracle de trier des valeurs qui sont indiscernables (non calculables ou mises arbitrairement à zéro) ? Je commence à entrevoir pourquoi nous ne parlons pas de la même chose. En calcul numérique, à cause du nombre de bits fini, l'augmentation indéfinie du nombre de décimales est impossible. Il n'y existe donc pas, si j'ai bien compris le sens de cette expression, de méthode algorithmique universelle. Dans mon langage cela conduit à accepter d'obtenir des résultats d'autant plus imprécis que le problème est plus mal conditionné. Les gens qui font du calcul numérique l'acceptent comme ils acceptent d'avoir des difficultés dans l'inversion de matrices dont le déterminant est proche de zéro. L'analyse constructive se situe dans le monde idéal des mathématiques, très éloigné de la plupart des gens qui ont les mains dans le cambouis. Actuellement, il existe deux articles Dichotomie et celui-ci, ce qui ne me paraît pas vraiment indispensable. A l'inverse, je ne serais pas choqué si on distinguait un article Dichotomie (mathématiques) de celui-ci qui concerne une méthode aux possibilités limitées, qui peuvent être quantifiées, comme toutes celles qui portent sur des flottants. Jct (d) 13 février 2008 à 15:41 (CET)

La trichotomie peut décider si x < z ou z < y même avec un nombre fini de décimales. Si on sait que x < y, cela signifie qu'on est capable de distinguer x de y avec un nombre donné n de décimales par exemple. Si on calcule z avec n décimales, alors on saura déterminer si x < z ou si z < y. Aucune démarche comparable n'existe pour la dichotomie (et précisément parce que l'augmentation indéfinie du nombre de décimales est impossible. C'est bien pour cela que la méthode par dichotomie n'est pas un algorithme universel acceptable). Par ailleurs, en calcul numérique, on travaille avec un nombre fini de bits, mais on peut augmenter ce nombre (utilisation de tableaux ou de listes pour stocker les décimales successives). Donc le problème n'est pas le nombre de décimales. Le problème est de savoir si, avec un nombre fini de décimales on peut effectuer tel ou tel test. En dichotomie, non ; en trichotomie, oui.

Pour prendre un autre exemple, celui de la suite géométrique $(x_{n})$ convergeant vers 0, on peut parfaitement déterminer n tel que $|x_{n}|<\varepsilon$ (énoncé 1). Mais il était erroné de dire dans le présent article que la méthode permettait de donner une valeur approchée de la racine à moins de $\varepsilon$ près (énoncé 2). Mais il est parfaitement exact de dire que la même méthode de dichotomie permet de trouver x tel que $|f(x)|<\varepsilon$ (énoncé 3). On voit donc que, même avec des nombres flottants, certains énoncés sont satisfiables, d'autres ne le sont pas. La différence est qu'il existe ou pas des algorithmes travaillant sur des flottants avec un nombre fini (même s'il est arbitraire) de décimales. Il en existe pour l'énoncé 1 ou 3, pas pour l'énoncé 2. Une fois de plus, il ne s'agit pas d'utilisation ou non de nombres flottants, mais d'existence ou non d'algorithme. Si on ajoute que f est strictement croissante dans l'énoncé 2, alors il existe des algorithmes.

Quant à l'analyse constructive, elle se situe à un niveau beaucoup plus concret que les mathématiques classiques. Ces dernières démontrent un théorème des valeurs intermédiaires mais la démonstration ne peut pas recevoir de traduction algorithmique. L'analyse constructive démontre le théorème des valeurs intermédiaires dans le cas d'une fonction strictement croissante par trichotomie, et celle-ci peut recevoir une traduction algorithmique (je ne dis pas que ce soit forcément plus efficace que d'autres méthodes, je dis seulement que c'est possible, contrairement à la démonstration usuelle par dichotomie).

Au sujet des deux articles Dichotomie, l'un (celui dont nous parlons ici) est spécifique à la méthode de dichotomie pour résoudre une équation. L'autre me paraît plus général et peut s'appliquer à d'autres domaines. Je ne suis pas favorable à leur fusion. Par ailleurs, le présent débat concerne uniquement la méthode de dichotomie appliquée à la résolution des équations. Il va de soi par exemple qu'une méthode de dichotomie sur les entiers ne pose pas de problème. Theon (d) 13 février 2008 à 18:37 (CET)

Les phrases Dans quelques cas, il peut arriver que la valeur de f(c) soit si proche de 0 que la précision du logiciel de calcul ne permette plus de déterminer le signe de f(c) (le logiciel de calcul assimile f(c) à 0). L'application de l'algorithme risque alors de conduire à l'élimination erronée d'une moitié de l'intervalle et à la convergence vers une valeur éloignée de la racine. me paraissent bien décrire le problème numérique, mis à part le fait qu'un logiciel sérieux refuserait de continuer quelle que soit la méthode, seul concerné par les premières moutures de l'article. Pourquoi refuser d'admettre qu'un autre problème se pose lorsqu'on autorise l'augmentation indéfinie du nombre de décimales, l'utilisation de tableaux ou de listes pour stocker les décimales successives n'étant pas une technique de calcul numérique connue ? Jct (d) 14 février 2008 à 09:57 (CET)

Mais les deux problèmes sont abordés dans l'article, d'abord le problème numérique (Dans quelques cas, ... une valeur éloignée de la racine), puis le problème algorithmique (D'une manière générale...), expliquant que ce problème numérique est inhérent à l'algorithme et pas à la précision du calcul. Il me semble que l'article est bien complet comme cela et je ne saisis pas trop ce qui ne convient pas. Theon (d) 14 février 2008 à 11:13 (CET)

L'état actuel de l'article me convient, comme je l'ai dit précédemment à deux reprises. Depuis que je l'ai admis, la discussion ne porte, pour moi, que sur la signification des exemples présentés dans cette discussion. Ils montrent d'une manière spectaculaire, donc pédagogique, qu'un calcul numérique ne peut fournir une précision infinie quelle que soit la méthode utilisée. Pour savoir ce qui se passerait avec une méthode donnée au-delà de leur limite, il faut donc faire un raisonnement mathématique indépendant des résultats divers obtenus avec tel tableur, telle calculette ou tel langage de programmation. Jct (d) 15 février 2008 à 10:06 (CET)

Je n'ai jamais prétendu obtenir une précision infinie. J'ai seulement demandé d'obtenir une précision donnée (cf mon premier message : Donner une valeur approchée de c à 1/10 près. Toujours dans ce premier message, je ne demande pas de connaître $\alpha$ avec une précision infinie, je signale seulement qu' on est parfaitement capable de calculer une valeur approchée de $\alpha$ à toute précision demandée, ainsi que toute valeur approchée de f(x) pourvu qu'on ait donné une valeur approchée adéquate de x , ce qui est la moindre des choses en calcul numérique). Formulé autrement, soit $\varepsilon$ une marge d'erreur que l'on se fixe. Considérons deux algorithmes T et D de résolution d'équation. L'algorithme T est tel que, pour toute fonction, on puisse déterminer un entier n tel que, si on effectue le calcul avec n décimales, alors la racine de l'équation est trouvée avec une précision $\varepsilon$. Par contre, l'algorithme D est tel qu'il existe une fonction pour laquelle on ne connaisse pas d'entier n ayant la même propriété (ou pire, un tel entier n n'existe pas). Dans le premier cas, on peut dire qu'on a éventuellement un problème numérique si la précision du logiciel est inférieure à n, mais que ce problème peut être résolu en augmentant cette précision. En tout cas, ce n'est pas un problème d'ordre algorithmique. Dans le second cas, le problème est non seulement d'ordre numérique, mais également algorithmique, puisque, quelle que soit la précision utilisée, on n'est pas certain d'atteindre le résultat cherché. Theon (d) 15 février 2008 à 11:10 (CET)

C'est ma dernière intervention dans un débat qui tourne en rond. Qu'ajouter quand on refuse obstinément de comprendre que les deux exemples présentés posent un problème numérique, facile à analyser car indépendant de la technique de calcul ? Qu'en conséquence la marge d'erreur observée (et attendue) n'apporte aucune information sur le choix de cette technique de calcul (pour ne pas ajouter à la confusion je dois bannir le mot algorithme de mon vocabulaire, le sens que lui donnent quotidiennement les informaticiens étant prohibé) ? J'ai tenté depuis le début d'identifier ce qui nous séparait et je croyais y être arrivé. C'est plus simple que cela : j'ai tort. Jct (d) 15 février 2008 à 16:07 (CET)

Je suis désolé si je n'ai pas compris le message précédent. Les exemples sont d'ordre différent. En ce qui concerne mon premier (celui affine par morceaux), je ne connais pas d'algorithme donnant la racine à moins de $\epsilon$ près, $\epsilon$ étant une marge d'erreur donnée à l'avance. En ce qui concerne mon deuxième exemple (celui avec l'exponentielle) qui est une fonction strictement croissante, j'en connais un (celui par trichotomie). Il en est de même en ce qui concerne l'exemple de HB. Theon (d) 16 février 2008 à 08:28 (CET)

~histoire de signe

Je tombe par hasard sur une intéressante question visiblement polémique (et on ne m'en averti même pas ...). A mon avis la question est beaucoup plus profonde qu'une simple question de précision numérique. Comme il a déjà été dit, il n'existe pas d'algorithme qui permette de déterminer le signe d'un nombre "théorique". Donnons un exemple. Je définis le nombre z ainsi: il prend la valeur 1 si le chiffre suivant la première suite de 50000 zéros dans le développement décimal de pi est supérieur ou égal à 6. à zéro si c'est un 5. à -1 si c'est un chiffre compris entre 0 et 4. Quel est le signe de ce nombre z ? il est clairement défini cependant. Il existe même un algorithme qui donne le n-ième chiffre décimal de pi pour tout n ! Claudeh5 (d) 16 février 2008 à 11:32 (CET)

Au lieu de 1 ou -1, il serait plus intéressant de définir z comme valant 1/10ⁿ ou -1/10ⁿ avec n le rang du chiffre cherché, car alors, non seulement on n'est pas certain de pouvoir donner le signe de z, mais pourtant on peut en donner des valeurs approchées aussi précises qu'on veut. Ce nombre z peut alors être source d'exemples ou de contre-exemples fort divers. Theon (d) 16 février 2008 à 18:54 (CET)

Article sur même sujet

Cette page est techniquement plus précise que Dichotomie, pourquoi ne pas les fusionner ?Jct 15 novembre 2006 à 14:58 (CET)

Voir Dichotomie, cet article ici et mieux, je pense, on pourrait les unifier. -- Saippuakauppias ⇄ 15 juin 2009 à 23:34 (CEST)

En fait, le présent article se limite à l'utilisation de la dichotomie pour la recherche d'une solution à une équation, le titre méthode de dichotomie étant le nom de cette méthode. L'autre article dichotomie ne se limite pas à cet aspect et a apparemment pour vocation de lister tous les domaines où la dichotomie peut être utilisée. C'est pourquoi je ne suis pas sûr qu'il soit pertinent de fusionner les deux articles. Theon (d) 16 juin 2009 à 08:38 (CEST)

Tolérance relative ou absolue

 Treizav : cela fait trois fois que vous tentez une correction qui est trois fois annulée. Il vaut donc mieux en discuter ici.

Le choix de l'article est de trouver un indice permettant de majorer l'erreur absolue de façon à ce qu'elle soit inférieure $\epsilon (b-a)$. Le choix de la notation ε n'est peut-être pas très heureux mais peut se comprendre. ε est alors la tolérance relative à la taille de l'intervalle (i.e. rapport entre la tolerance absolue et la taille de l'intervalle).

En effet tout le reste de la démonstration consiste à dire que puisque l'erreur absolue est majorée par ${\frac {b-a}{2^{n+1}}}$ il suffit de prendre ${\frac {1}{2^{n+1}}}$ inférieur à ε (tolérance relative) pour que tout marche.

Si ce vocabulaire suscite de la confusion on peut voir à s'en passer mais surtout pas corriger à mauvais escient. HB (discuter) 15 décembre 2022 à 12:27 (CET)

Dans ce cas, il faut revoir la rédaction de cette partie de l'article. Même mes étudiants ont été troublés de cette utilisation abusive de l'adjectif "absolu". Treizav (discuter) 15 décembre 2022 à 21:26 (CET)

je voulais dire "relative" (à force...) Treizav (discuter) 15 décembre 2022 à 21:27 (CET)

J'ai supprimé la référence à l'erreur relative. Est-ce que cela te convient? HB (discuter) 15 décembre 2022 à 22:49 (CET)

Je ne veux pas imposer ma vision ! C'était juste le terme "relatif" qui me semblait inapproprié.

Pour moi, le rapport (b-a)/ε est égal (à l'unité près) à 2^N, N étant le nombre d'itérations nécessaires pour atteindre une incertitude absolue ε, d'où N = sup(log2((b-a)/ε)), sup signifiant "entier immédiatement supérieur à". Treizav (discuter) 16 décembre 2022 à 08:58 (CET)

Si $x_{0}$ est la racine exacte et x une valeur approchée, l'erreur absolue est $|x-x_{0}|$. Cette erreur n'étant pas majorée par ε mais par (b-a)ε, ε ne peut être qualifiée d'erreur absolue. Theon (discuter) 16 décembre 2022 à 10:54 (CET)