Discuter:Théorème des valeurs intermédiaires

Un article de Wikipédia, l'encyclopédie libre.

WikiProjet Mathématiques
 Théorème des valeurs intermédiaires fait partie du projet Mathématiques, qui a pour but d'enrichir le contenu de Wikipédia sur les sujets liés aux mathématiques. Si vous voulez participer, vous pouvez modifier cet article ou visiter la page du projet, où vous pourrez vous joindre au projet et consulter la liste des tâches et des objectifs. Le portail Mathématiques pourrait aussi vous intéresser.
B Cet article a été classé comme d'Avancement B selon le Tableau d'évaluation du projet. (Voir les statistiques)
Maximum Cet article a été classé comme d'Importance maximum selon le Tableau d'évaluation du projet.

Niveau (indicatif): < Bac +2 Démonstration: < Bac +2 Compréhension: Bac -1, Bac

Sommaire

[modifier] Dichotomie non constructive

Il est affirmé dans l'article que la démonstration par dichotomie fournit un algorithme du calcul approché du zéro de la fonction. Il n'en est hélas rien et cette partie de l'article devra être corrigée (je peux m'en charger mais plus tard).

Considérons une suite (an) d'entiers relatifs valant -1, 0 ou 1 et posons a=\sum_{n=1}^\infty \frac{a_n}{3^n}. Considérons maintenant la fonction f affine sur les intervalles [0, \frac{1}{3}], [\frac{1}{3}, \frac{2}{3}] et [\frac{2}{3}, 1] et telle que f(0) = − 1, f(1) = 1, f(1 / 3) = f(2 / 3) = a. La dichotomie demande de déterminer le signe de f(1 / 2) = a. Pour cela il suffit de déterminer le signe du premier terme non nul de la suite (an) 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 que, si a>0, la valeur c telle que f(c) = 0 est inférieure à 1/3 ; si a<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 potable de c.

Exemple : Posons an = 0 si n17 + 9 et (n + 1)17 + 9 sont premiers entre eux, an = 1 si n17 + 9 et (n + 1)17 + 9 ne sont pas premiers entre eux et que n est pair, an = − 1 si n17 + 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 a à 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. Theon (d) 29 janvier 2008 à 18:35 (CET)

[modifier] Le terme n'est pas si impropre

L'article suppose que pour la fonction f étudiée, il existe une méthode de connaître parfaitement la valeur d'une image si l'antécédent est connue. Cette hypothèse est très largement supposée pour ce que l'on appelle les algorithmes d'extraction de racines. On parle aussi d'algorithmes par exemple pour la méthode de Newton qui suppose qu'il est possible d'expliciter non seulement la valeur de la fonction mais aussi la dérivée.

Si par exemple la fonction est définie par f(x) = x2 - 2, définie sur l'intervalle [0, 2]. La première étape montre qu'une racine se situe entre 1 et 2, la deuxième entre 1 et 1,5 la troisième entre 1,25 et 1,5 etc...

Si les informations possédées sur f ne sont que l'appartenance à une famille de fonctions sans plus de précision, il apparaît que cette démarche n'est pas systématiquement opérationnelle. Je ne connais pas d'algorithme qui résiste à cela, en revanche, le terme d'algorithme pour l'extraction d'une racine est largement utilisé. Une telle approche est nécessaire par exemple pour programmer une petite calculette la fonction extraction de racine, qui ne sera néanmoins pas capable de réaliser du calcul formel. La méthode décrite ici est parfois utilisée. Jean-Luc W (d) 29 janvier 2008 à 19:42 (CET)

Je ne sais pas ce que veut dire connaître parfaitement la valeur d'une image. Pour des fonctions d'une variable réelle et le calcul numérique, je ne connais qu'un seul sens raisonnable : pouvoir calculer f(x) à une précision donnée sachant que x peut lui-même être connu à toute précision souhaitée. Cela me paraît la seule définition raisonnable. C'est ce que fait mon exemple. Bien entendu, on peut appeler algorithme toute démonstration même si elle est en défaut dans les calculs pratiques, mais il y a tromperie sur la marchandise. C'est pour cela que le mot méthode me paraît mieux adapté. Une méthode, on fait ce qu'on peut avec, et c'est exactement à cela que servent les méthodes de résolution d'équation. A titre d'exemple, je note que J.P. Demailly, Analyse numérique et équations différentielles, titre l'un de ses chapitres méthodes itératives pour la résolution d'équations. Theon (d) 30 janvier 2008 à 09:12 (CET)
Ta définition me va très bien. Soit ε > 0 une précision. Ton exemple permet en effet de calculer la valeur de f(x) à la précision ε. Si f(1/2) est égale à 0 (à ε près) alors la racine est déterminée (à ε près, l'objectif recherché). Si f(1/2) est strictement supérieure à ε, alors il existe une racine dans l'intervalle [0, 1/2[, et je réitère le processus sur la valeur 1/4. Si elle est strictement inférieure, alors je réitère sur la valeur 3/4 car je sais qu'il existe une racine dans l'intervalle ]1/2, 1]. Je trouverais donc une racine à ε près en un temps fini. Pour être précis, comme la dérivée de ta fonction (définie presque partout) est majorée en valeur absolue par 6, si n est le plus petit entier tel que (1/2)n est strictement plus petit que 6ε, alors il suffit de n étapes pour trouver la racine. En fait, avec cette définition je ne vois pas où est le problème.
Pourrais tu m'indiquer quel est selon toi la définition du mot algorithme et me donner un exemple ?

Merci de ta précision. Jean-Luc W (d) 30 janvier 2008 à 10:09 (CET)

Dans ton explication, on peut noter que ce n'est pas la racine c qui est connue à ε près. Reprenons l'exemple de la fonction affine par morceaux et valant a entre 1/3 et 2/3. Supposons a non nul (c'est d'ailleurs le cas dans mon exemple, mais je ne dirai pas s'il est positif ou négatif), mais inférieur en valeur absolue à la précision du calcul ε. En valeur approchée, a sera considéré comme nul et la méthode par dichotomie donnera 1/2 comme valeur approchée de c. Supposons maintenant qu'on décide d'augmenter la précision du calcul de façon qu'avec cette nouvelle précision, on s'aperçoit non seulement que a est non nul, mais qu'il est positif. Brutalement, la valeur de c passe en dessous de 1/3. Ce n'est donc pas la valeur de c qui est calculée de façon pertinente, puisque la méthode par dichotomie lui fera subir des variations importantes en fonction de la précision du calcul. Il faudrait donc cesser de faire croire que la démonstration par dichotomie (qui n'est qu'une démonstration) soit un algorithme numérique donnant une valeur approchée de c. C'est faux. La version numérique de la méthode par dichotomie ne donne pas une valeur approchée de la racine c, mais une valeur c dont l'image est une valeur approchée de 0. C'est tout à fait différent. Enoncé sous cette forme, je veux bien qu'on parle d'algorithme. Ainsi, si algorithme il y a, c'est celui qui donne une valeur de c telle que son image soit inférieure en valeur absolue à une borne ε > 0 donnée. C'est d'ailleurs ce résultat que tu énonces, et c'est également ce dernier énoncé qui est la version du théorème des valeurs intermédiaires en analyse constructive. Mais la valeur ainsi trouvée de c peut se trouver fort éloignée de la racine exacte de f. Theon (d) 30 janvier 2008 à 10:40 (CET)

Si tu définis les algorithmes d'extractions de racine comme une méthode qui offre une approximation aussi précise que souhaitée sur l'abscisse et non sur l'ordonnée et sur n'importe quelle fonction continue, alors tu as raison. Cette définition me semble néanmoins un peu tirée par les cheveux, en tout cas elle est à ma connaissance rarement utilisée. Je ne vois plus à quoi appliquer la locution d'algorithme d'extraction de racine. Je me demande même dans quel contexte ce mot reste utilisable. Tu as néanmoins raison, dans les articles spécialisés sur cette question, il faut préciser que l'algorithme donne une bonne approximation de l'image et nécessite des informations sur un minimum de la norme de la dérivée au voisinage de la racine. En revanche, je me demande un peu ce que cette remarque vient faire sur un article dont le sujet est le théorème des valeurs intermédiaires et non pas l'algorithmique. De plus pour les articles algorithmiques, je préconise de ne pas utiliser cette définition bien restrictive et de continuer à utiliser la définition commune. Le mot serait banni de WP alors qu'il est largement utilisé (Recuit simulé, Méthode de Monte-Carlo, Méthode de Newton, Test de primalité de Miller-Rabin qui est probabiliste etc...). Jean-Luc W (d) 30 janvier 2008 à 14:00 (CET)
 : Si j'ai bien compris ce que tu nous essaies de nous dire, c'est que la méthode de dichotomie fournit un encadrement d'une racine d'amplitude (1/2)n tant que l'on peut donner avec certitude le signe de f(a_n). Comme en pratique, la valeur de f(a_n) n'est connu qu'avec une certaine imprécision, il existe un N au dela duquel le signe de f(a_n) ne peut pas être donné, la recherche s'arrête donc et c n'est connu qu'avec une précision de (1/2)N ? Je pense que cette remarque doit en effet figurer dans l'article. Ton contrexemple en revanche est peut-être un peu ardu pour le niveau de celui-ci. Enfin, tu sembles avoir une définition très précise du terme algorithme que j'emploie moi avec le sens de "recette". S'il existe une définition officielle d'algorithme, il serait bon de compléter l'article en question de wikipédia. ou de d'y signaler l'usage abusif que l'on fait semble-t-il parfois de ce mot. HB (d) 30 janvier 2008 à 14:08 (CET)
(conflit avec HB) je débarque sur cet échange et je dois avouer que je suis d'accord avec les dernières remarques pratiques de Jean-Luc. Il faudrait définir ce qu'on entend par "racine" en analyse numérique ; ça me paraîtrait naturel d'exiger une notion de racine de la forme tout réel x tel que |f(x)|<\varepsilon ', avec a priori \varepsilon '\neq \varepsilon (précision voulue sur l'abscisse). En tout cas, ça correspond plus à une logique numérique. Peps (d) 30 janvier 2008 à 14:14 (CET)

Je prends note que vous proposez d'appeler racine tout réel x tel que |f(x)|<\varepsilon. Je ne suis pas sûr que le lecteur à qui s'adresse cet article comprenne que le mot racine est pris dans ce sens puisque cela n'a pas été expliqué. Pour lui, une racine est un nombre c tel que f(c)=0 et une valeur approchée de la racine c à 1/1000 près est une valeur x telle que |x - c| < 1/1000 et absolument pas une valeur x telle que |f(x)| < 1/1000. Quand on demande une valeur approchée à 1/1000 de \sqrt{2}, on attend un nombre x tel que |\sqrt{2} - x|<1/1000 et pas tel que | x2 − 2 | < 1 / 1000. Plus généralement, si on cherche une valeur approchée d'un nombre z à un millième près et qu'on s'aperçoive que z est solution d'une équation f(x) = 0, je ne pense pas qu'on puisse se satisfaire comme valeur approchée de z d'un x tel que |f(x)| < 1/1000. D'ailleurs la lecture de l'article, qui précise On finit alors par trouver un encadrement « assez fin » de la solution, partage ce point de vue puisqu'on prétend restreindre l'intervalle relatif à l'abscisse et absolument pas celui relatif à l'ordonnée. La correction apportée par Jean-Luc W sous la forme : La dichotomie est un algorithme simple pour déterminer une approximation de la valeur de c, ne corrige malheureusement pas cette ambiguïté. Ceci dit, je ne souhaite pas nécessairement parler d'algorithme dans cet article, mais si on en parle, qu'on le fasse sans créer de confusion sur ce qu'on appelle calculer une racine. Je propose donc :

  • de reformuler le paragraphe qui commence par En général, un théorème d'existence ne donne aucun moyen de trouver l'un des éléments dont il affirme l'existence, puisque, pas plus que la première démonstration, la deuxième ne donnera de valeur précise de la racine c.
  • de garder le mot algorithme si vous le souhaitez, mais à condition de préciser que la méthode par dichotomie ne donne pas une valeur approchée de la racine, mais seulement une valeur x telle que son image soit inférieure à une précision donnée, et qui peut être éloignée de la racine réelle c.
  • de préciser que ce problème provient de la difficulté (voire l'impossibilité) à effectuer numériquement le test f(mn) = k.

Cela aurait le mérite d'avertir le lecteur sur la difficulté souvent omise de calculer une racine à une précision donnée. Theon (d) 30 janvier 2008 à 18:08 (CET)

apparemment tu ne prends pas en compte qu'il y a deux "erreurs" \varepsilon '\neq \varepsilon :
en fait je pensais à l'utilisation suivante :
"La démonstration par dichotomie se traduit facilement sous forme algorithmique, à l'exception du test f(mn) = k, qu'on ne saurait vérifier exactement alors que l'on procède à des calculs numériques approchés. On peut vérifier une condition |f(m_n) - k| < \varepsilon_1, où \varepsilon_1 est une quantité donnée à l'avance. Pour que l'algorithme ait un intérêt, il faut donc se placer dans des conditions telles que la relation |f(x) - k|< \varepsilon_1, entraîne que la valeur x est proche de la valeur exacte c d'une racine : |f(x) - k|< \varepsilon_1\Rightarrow \exists c, f(c)=0 et |x - c|< \varepsilon, erreur donnée à l'avance."
il me semble que c'est en ce sens qu'on peut parler d'algorithme (comme les autres, c'en est un moyennant d'avoir le contexte adéquat) Peps (d) 31 janvier 2008 à 17:48 (CET)

Oui, j'ai bien vu qu'il y avait deux erreurs. Le test d'arrêt consiste à regarder si |f(x) - k|< \varepsilon' ou si la largeur de l'intervalle encadrant la racine est inférieure à \varepsilon, mais je n'ai pas voulu alourdir l'article. Il me semble que le fait de souligner qu'on ne trouve pas nécessairement une valeur proche de c est suffisant. Je pense que des détails supplémentaires peuvent être apportés dans l'article Méthode de dichotomie, d'autant plus que, dans ce dernier article également, on laisse penser qu'on peut obtenir la racine à toute précision voulue, sans aucune restriction. Theon (d) 31 janvier 2008 à 19:13 (CET)

[modifier] Action sur l'article

Je crois en effet, que l'algorithmique n'est pas le sujet de cette article. Préciser ici que la distance entre l'approximation et la racine décroit exponentiellement avec le nombre d'itérations me semble largement suffisant. Le fait qu'une situation où le temps de détermination du signe de f(x) devient prohibitif soit imaginable me semble un problème typiquement d'algorithmique et touche peu le thème des valeurs intermédiaires.

Pour les autres article traitant du sujet, il est peut être utile de rappeler que la méthode dichotomique est considérée comme très résistante. Elle permet d'approximer la racine s'il est possible de déterminer suffisamment rapidement le signe de f(x), ce qui est le cas par exemple s'il existe une borne inférieure de la valeur absolue du taux d'accroissement au voisinage de la racine (qui correspond à un cas fréquent en analyse numérique) si le temps de calcul de l'image n'est pas trop cher (ce qui est beaucoup plus rare si l'espace de départ est de grande dimension) et si l'on connait une image strictement positive et une strictement négative (ce que je n'ai pas vu souvent). Cette résistance est en général abandonnée au bénéfice d'une convergence plus rapide et au détriment d'un ensemble de fonctions sur lequel l'algorithme est efficace un peu différent (la fonction est souvent supposée de classe C2 avec les algos quadratiques, mais on ne suppose pas connue une valeur strictement positive et une strictement négative).

La notion de vitesse de convergence mérite d'être mieux traitée dans les articles d'algorithmiques. Le phénomène du dôme autour de la racine (obtenue par exemple avec une équation du type |a(x)| = 0 ou a est une application la plus linéaire possible sur un vaste espace) est un frein fréquent dans la pratique. Il touche les méthodes de Newton, quasi-Newton, Monté Carlo, recuit simulé etc... .Jean-Luc W (d) 30 janvier 2008 à 19:23 (CET)

[modifier] Théorème de Bolzano

J'ai été assez surpris lorsque j'ai vu que le Théorème de Bolzano redirigeait vers le TVI. Pour moi, le théorème de Bolzano énonce le fait que de toute suite réelle bornée on puisse extraire une suite convergente... C'est un cas particulier de Bolzano Weierstrass mais il me semble qu'il porte le nom de Bolzano seul... --Vinky (d) 9 avril 2008 à 19:30 (CEST)