Methode de Newton

Version imprimable

Methode de Newton

Bonsoir,
j'ai programme la methode de Newton afin de trouver les racines d'un polynome. Cependant, mon programme ne semble pas marcher : il affiche tout le temps une iteration et la valeur renvoyee est completement fausse. J'ai eu beau verifier plusieurs fois, je ne vois pas d'ou peut provenir l'erreur.. Si quelqu'un a une idee.. Voici mon code:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cmath>
#include <iostream>
using namespace std;
 
 
// la fonction dont on cherche un zero
inline double f(double x) 
{return x*x - 2.0;};
 
// la derivee de f
inline double fderiv(double x)
{return 2*x;};
 
double Newton(double (*f)(double), double (*fderiv)(double))
{
     double epsilon;
     double itermax;
     double x0;
 
    cout << "Quelle est la precision souhaitee?";
    cin >> epsilon;
    cout << "Quelle est la valeur initiale?";
    cin >> x0;
    cout << "Quelle est le nombre d'iterations maximal?"; 
    cin >> itermax; 
 
    double x = x0;
    double xnew;
    int i = 0;
 
 
 while(i<itermax && abs(xnew-x)>=epsilon)
 {
        xnew = x - f(x) / fderiv(x);
        x = xnew;
        i++;
    }
    if(i==itermax)
    {cout << "la methode ne converge pas" << endl;}
    else
    {cout << "la methode converge en " << i <<" iterations"<< endl;};
 
    return xnew;
}
 
int main()
{
   cout << "les racines du polynome sont " << Newton(f, fderiv);
      return 0;
}

Merci

28/11/2009, 23h56
Invité

C'est dans abs(xnew-x)... regarde bien...

Francois
29/11/2009, 00h33
leetimber5

Ah ok!! Merci beaucoup.. En effet, comme ca la difference ne variait pas.. Merci encore!

Salut,

J'ai une petite question qui peut paraitre idiote, mais, pourquoi passe tu des pointeurs de fonctions (prenant un double en paramètre et renvoyant un double) à ta fonction newton :question:

Etant donné que la formule ne va pas essayer de modifier l'ordre dans lequel les fonctions sont appelées, cela n'a pas énormément de sens :P

De plus, la demande faite à l'utilisateur concernant le nombre d'itération, la valeur de départ et la précision devraient, idéalement, ne pas se trouver dans la fonction newton...

En effet, pour l'instant, tu travailles en "mode console", et tout va bien.

Mais, si, un jour, tu souhaite rajouter une interface graphique, ou utiliser un fichier dans lequel se trouve ces informations, tu devra réécrire ta fonction newton, simplement parce que... la méthode d'obtention des valeurs aura changé :P

L'idéal est donc, plutôt, de demander dans la fonction principale les différentes valeurs qui t'intéressent et de les transmettre sous la forme de paramètre à ta fonction newton :D

En gros, ton code deviendrait
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include <cmath> #include <iostream> using namespace std; // la fonction dont on cherche un zero inline double f(double x) {return x*x - 2.0;}; // la derivee de f inline double fderiv(double x) {return 2*x;}; double Newton(double epsilon, double itermax, double precision) { /* nota: je n'ai pas corrigé cette partie du code... * je me suis "contenté" de sortir ce qui n'avait rien à faire * dans cette fonction ;) */ double x = x0; double xnew; int i = 0; while(i<itermax && abs(xnew-x)>=epsilon) { xnew = x - f(x) / fderiv(x); x = xnew; i++; } if(i==itermax) {cout << "la methode ne converge pas" << endl;} else {cout << "la methode converge en " << i <<" iterations"<< endl;}; return xnew; } int main() { double epsilon; double itermax; double x0; cout << "Quelle est la precision souhaitee?"; cin >> epsilon; cout << "Quelle est la valeur initiale?"; cin >> x0; cout << "Quelle est le nombre d'iterations maximal?"; cin >> itermax; cout << "les racines du polynome sont " << Newton(epsilon, itermax, x0); return 0; }
Ainsi, si, un jour, tu venais à disposer d'un fichier contenant une série de valeurs sur lesquelles tu souhaite appliquer Newton proche de
Code:

1 2 3 4 5 <valeur initiale 1> <précision 1> <iterations 1> <valeur initiale 2> <précision 2> <iterations 2> <valeur initiale 3> <précision 3> <iterations 3> ... <valeur initiale N> <précision N> <iterations N>
tu n'aurais qu'à changer ta fonction main en:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 int main() { std::string filename; std::cout<<"veuillez introduire le nom du fichier "; std::cin>>filename; std::ifstream ifs(filename.c_str()); if(ifs) { double initiale; double precision; double iteration; int cpt = 1; /* c'est pas très sécu, mais pour l'exemple :D */ while(ifs>>initiale>>precision>>iteration) { std::cout<<"Valeurs "<<cpt<<" a calculer:"<<std::endl <<"\t valeur intiiale : "<<itiniale <<" precision : "<<precision <<" nombre d'itération :" <<iteration<<std::endl << "les racines du polynome sont " << Newton(precision, iteration, initiale); ++cpt; } } else { std::cout<<"impossible d'ouvrir le fichier "<<filename<<std::endl; } return 0; }
Et le tour serait joué :D

L'idée sous-jacente à ce conseil tient en un principe appelé la "délégation des responsabilités":

En effet, on considère que si une fonction a plus d'une responsabilité, c'est, sans doute, qu'elle en a trop, avec comme conséquence que le code devient plus difficile à maintenir et à faire évoluer selon les besoins qui finiront, tôt ou tard, par se faire jour.

Dans le code que tu donnes, ta fonction Newton a en réalité deux responsabilités (dans l'ordre dans lequel elles aparaissent):
Celle de s'occuper de l'obtention de valeurs
Celle d'effectuer le calcul
C'est une de trop...

Cela signifie qu'il faut envisager de lui en enlever une... Le choix est vite fait car il est difficilement envisageable de lui enlever la deuxième :D

29/11/2009, 16h52
Invité

Salut Koala,

Je crois qu'il faut absolument garder les pointeurs de fonction (ou des foncteurs, ou ce que tu veux) dans les paramètres de Newton(). L'algorithme de Newton, ca sert à calculer les zéros d'une fonction, il faut donc lui dire laquelle... Les trois autres paramètres, ce sont des réglages, dans une implémentation sérieuse, ils seraient déterminés par l'algorithme lui même...

En fait, le nombre maximal d'itération (qui sert à vérifier que l'algo converge) est lié à la précision souhaitée. La précision est de toutes façons liée au type de nombres utilisés (ici des double), mais elle a une importance limitée, parce que l'algorithme de newton, quand il converge, est quadratique (je crois). Donc s'il trouve la solution, la précision est acquise assez rapidement.

Reste uniquement le point de départ, problème notoirement difficile dans certains cas... En général, on laisse la machine le gérer par essais et erreurs, mais c'est le seul paramètre libre qu'on pourrait laisser

Logiquement, le squelette de cette fonction doit être quelque chose comme

Code:

double Newton(fonction f, fonction df,double x0=0.0);

Ce qui risque de changer, à l'implémentation, c'est la fonction, pas les réglages...

Francois