Multiplication inexplicable

[Algorithmique]

Sujet résolu

3 août 2011 à 12:49:11

Bonjour,

Je suis en train de lire le tutoriel « Algorithmique pour l'apprenti programmeur » et j'en suis au chapitre « Une classe d'algorithmes non naïfs : diviser pour mieux régner ». J'en suis au calcul approximatif de la racine de 2, dont un exemple est donné en php. Je l'ai codé en c++ et il fonctionne ; mais je ne comprends pas entièrement son fonctionnement : pour y a-t-il besoin de multiplier fonction(valeur_moyenne) par fonction(début) ?

if (f($a) * f($m) < 0)

Pourquoi ne suffit-il pas de calculer fonction(valeur_moyenne) ?
Bien sûr, cette méthode ne fonctionne pas. Mais pourquoi ? Pourriez-vous m'expliquer l'utilité de cette multiplication ?

Merci d'avance,
bouboudu21

bluestorm

3 août 2011 à 13:18:54

L'algorithme repose sur l'hypothèse que les deux bornes de l'intervalle de recherche donnent un résultat de signe opposé : par exemple f($a) est négatif, et f($b) positif, ou l'inverse. On se sert de ça pour savoir dans quelle moitié chercher ensuite (celle qui préserve cette différence de signes). Tester (f($a) * f($b) < 0) est une façon astucieuse de vérifier que les deux valeurs sont de signes opposés.

cbasile06

3 août 2011 à 13:20:12

Le test f($a) * f($m) < 0 sert en fait à regarder si f($a) et f($m) sont de même signe ou non.
C'est cela qui permet de déterminer l'intervalle où appliquer la prochaine itération de l'algorithme : en effet, il faut que l'évaluation de la fonction en chacune des deux bornes donne des résultats de signes différents pour être « sûr » qu'il y a un zéro de la fonction entre les deux (avec le théorème des valeurs intermédiaires, puisque notre fonction est continue).

Je reconnais que le tutoriel n'explique pas très clairement ce point.
Dans cette partie :

Citation : Tutoriel

On constate que f(0) est négatif et que f(2) est positif. Comme notre fonction est continue, l'équation f(x) = 0 possède nécessairement une solution entre 0 et 2. En utilisant la dichotomie, on peut réduire l'intervalle et donc améliorer la qualité de l'approximation.

Comme pour la recherche d'un mot dans le dictionnaire, on sélectionne une nouvelle valeur m positionnée au milieu de l'intervalle [a;b]. Si f(m) est positif, on peut en déduire que la solution est comprise dans l'intervalle [a;m]; sinon, elle se trouve dans l'intervalle [m; b].

Il faut bien se rendre compte que l'on choisit les intervalles de façon à ce que, dans un cas <math>$f(a) < 0$</math> et <math>$f(m) > 0$</math>, ou alors <math>$f(m) < 0$</math> et <math>$f(b) > 0$</math> : dans tous les cas, les valeurs prises par <math>$f$</math> aux deux bornes de l'intervalle sont de signes opposés !
Cela aurait peut-être été plus clair en précisant « Si f(m) est positif, c'est-à-dire du signe de f(b), ... »

bouboudu21

3 août 2011 à 13:35:05

Bonjour,

Merci tout d'abord pour vos réponses, j'ai compris à quoi servait cette opération. Mais le code du tutoriel pourrait être un petit peu simplifié : pourquoi ne pas tester directement si fonction(valeur_moyenne) est supérieur ou inférieur à 0 ? Cela nous donne directement la « direction » à prendre (entre début et valeur_moyenne, ou entre valeur_moyenne et fin) :

if(fonction(valeurMoyenneActuelle) > 0)
{
      return trouverZero(debut, valeurMoyenneActuelle, precision);
}
else
{
      return trouverZero(valeurMoyenneActuelle, fin, precision);
}

Dans mon précédent mail, je dis que cette méthode ne fonctionne pas. Mais c'est parce que je ne m'étais pas rendu compte qu'il faut inverser « < » et « > ». Maintenant, cela fonctionne.

Merci encore pour vos réponses.
bouboudu21

bluestorm

3 août 2011 à 13:43:52

Ça ne marche pas si la fonction est globalement décroissante, si f(début) est positif et f(fin) négatif.

bouboudu21

3 août 2011 à 13:45:39

Oui, c'est vrai.

Cygal

10 août 2011 à 13:43:59

Nous avons mis à jour le tutoriel pour clarifier ce passage. Merci du retour !