Borner Newton Raphson

Version imprimable

salut tous,

j'ai une question, comment borner à N-R les valeurs à rechercher ?

Voici pourquoi je vous demande ceci:
- j'ai un polynôme et je dois trouver une racine de ce dernier
- la racine que je cherche est entre 0 et une valeur (typiquement 0,02), il y en a peux etre d'autres negatives mais je ne dois pas aller dans ce domaine
==> le probleme est que lorsque je lance mon alog (cf. plus bas) la valeur qu'il me trouve est du genre 1e-12 ce qui lui permet de sortir de la boucle de N-R mais ce n'est pas la solution que je cherche !

j'aimerai donc borner l'espace de recherche par les valeurs 1e-5 et 0,02, savez vous comment je peux faire ceci ? j'ai entendu parler de conditions de Kuhn et Tucker mais comment implementer ceci?

voici mon algo en C++:
Code:

1 2 3 4 5 6 7 8 9 10 double xM=0.0001, residu=10, Xsolution=0; residu= a*pow(xM,(Y-X)/Y)+b*pow(xM,-X/Y)+c*xM+d; //Newton algorithm while ( residu >1e-9 || countt > MAX_ITERATION_NR) { xM=xM-(a*pow(xM,(Y-X)/Y)+b*pow(xM,-X/Y)+c*xM+d )/( a*((Y-X)/Y)*pow(xM,-X/Y)+b*(-X/Y)*pow(xM,(-X-Y)/Y)+c); residu= a*pow(xM,(Y-X)/Y)+b*pow(xM,-X/Y)+c*xM+d; } Xsolution=xM;
je vous remercie d'avance pour l'aide que vous pourrez m'apporter !

A+ :-)

27/10/2011, 15h26
prgasp77

Bonjour,

Citation:

la racine que je cherche est entre 0 et [0,02]

1e-12 est entre 0 et 0,02.

Citation:

j'aimerai donc borner l'espace de recherche par les valeurs 1e-5 et 0,02

Es-tu sûr de l'existence d'une racine entre ces deux valeurs ?
27/10/2011, 15h52
membreComplexe12

merci d'avoir pris le temps de repondre !

1°) tout d'abord je sens que je me suis mal exprimé :-( désolé, pour etre certains qu'il n'y a pas de quiproquo je vais reformuler.

==> je sais que mon probleme à une solution qui est entre 0 et 0.02, le probleme est que N-R m'amene parfois vers des valeurs tres proche de 0 du genre 1e-12 et qui font que mon residu est tres faible et je sors de l'algo sans avoir trouvé la solution qui est plutot proche de 0.01

==> je voudrais donc borner l'espace de recherche entre 1e-12 et 0.02 (ca pourrait etre entre 0.01 et 0.02 mais par securité je prefere agrandir un peu ce domaine d'où le 1e-12)

2°) oui je suis certain qu'il y a une solution entre 0 et 0.02 ça vient d'un phenomene physique.

3°) pour borner je pensais pondérer le résidu (si xM<1e-12 alors residu=residu*10000) mais j'ai entendu que ce type de methode pouvais parfois poser des problemes à l'algo N-R (ca peut l'eloigner de la solution rechercher si on est trop pret de la borne)

==> j'ai donc cherché et il existerai une methode beaucoup plus propre, il faut faire respect à la solution des conditions de Kuhn et Tucker (KKT) le probleme est que j'ai regardé sur le net et je n'ai pas compris :-( alors je vois encore moins comment implementer ceci dans N-R :calim2:

ps: au fait, quel est l'epsilon que vous mettez en general pour l'algo de N-R ?
comment connaitre l'ordre de grandeur? je vous demande ceci car parfois je vois que mon residus est a 1e-27 alors que je n'ai pas la solution recherchée :-(
27/10/2011, 19h08
Zavonen

Peut-on connaître les valeurs des constantes a,b,c,d,X,Y ?
De toutes façons c'est déjà maladroit de recalculer toutes les constantes comme par exemple
a*((Y-X)/Y)
à chaque tour de boucle.
27/10/2011, 20h29
FR119492
Salut!
On croit souvent que les polynômes sont des fonctions "gentilles". En fait, ce sont souvent des "sales bêtes", et les méthodes utilisées pour rechercher les zéros d'autres fonctions sont mal adaptées dans ce cas. Je pense que la moins mauvaise méthode consisterait à:
1. construire la "matrice compagnon" du polynôme;
2. calculer ses valeurs propres;
3. choisir celle qui satisfait aux conditions imposées.
Jean-Marc Blanc
27/10/2011, 21h38
membreComplexe12
salut tous, merci beaucoup de votre aide!!!

Citation:

Envoyé par Zavonen

Peut-on connaître les valeurs des constantes a,b,c,d,X,Y ?
De toutes façons c'est déjà maladroit de recalculer toutes les constantes comme par exemple
a*((Y-X)/Y)
à chaque tour de boucle.

en fait à chaque pas de temps j'appel cette fonction qui contient mes iteration de N-R, à chaque pas de temps a,b,c,d sont différents du pas de temps precedent.

pour chaque pas de temps je fais ce calcul pour trois cas:
X=2 Y=1 ; X=18 Y=10 ; X=5 Y=6
d'où l'intéret de caluler pour chaque cas ces choses

Citation:

Envoyé par FR119492

On croit souvent que les polynômes sont des fonctions "gentilles". En fait, ce sont souvent des "sales bêtes", et les méthodes utilisées pour rechercher les zéros d'autres fonctions sont mal adaptées dans ce cas.

c'est vrai que c des sales betes :( :cry:
par contre j'aurais pensé que N-R etait le plus adapté pour faire ceci (en bornant d'une maniere ou d'une autre l'espace de recherche)

[quote=FR119492;6317268]Je pense que la moins mauvaise méthode consisterait à:
salut tous, merci beaucoup de votre aide!!!

Citation:

Envoyé par Zavonen

Peut-on connaître les valeurs des constantes a,b,c,d,X,Y ?
De toutes façons c'est déjà maladroit de recalculer toutes les constantes comme par exemple
a*((Y-X)/Y)
à chaque tour de boucle.

en fait à chaque pas de temps j'appel cette fonction qui contient mes iteration de N-R, à chaque pas de temps a,b,c,d sont différents du pas de temps precedent.

pour chaque pas de temps je fais ce calcul pour trois cas:
X=2 Y=1 ; X=18 Y=10 ; X=5 Y=6
d'où l'intéret de caluler pour chaque cas ces choses

Citation:

Envoyé par FR119492

On croit souvent que les polynômes sont des fonctions "gentilles". En fait, ce sont souvent des "sales bêtes", et les méthodes utilisées pour rechercher les zéros d'autres fonctions sont mal adaptées dans ce cas.

c'est vrai que c des sales betes :( :cry:
par contre j'aurais pensé que N-R etait le plus adapté pour faire ceci (en bornant d'une maniere ou d'une autre l'espace de recherche)

Citation:

Envoyé par FR119492

Je pense que la moins mauvaise méthode consisterait à:

en effet ça semble meilleur comme methode car je calcul toutes les solutions du polynome avec ça (c bien ça ?)

par contre si j'ai des racines complexes ça peut pas poser probleme numeriquement ? (je demande car j'ai jamais essayer cette methode)

==> as tu un lien vers un cours ou un tuto qui presente cette methode car je n'ai jamais fait ceci... merci
Citation:
Envoyé par FR119492

construire la "matrice compagnon" du polynôme;
calculer ses valeurs propres;
choisir celle qui satisfait aux conditions imposées.

Jean-Marc Blanc
=> ok, la premiere etape devrait etre facile
=> par contre je n'ai jamais programmé une recherche de valeur propre peux tu me donner des indices / mot cles ou me donner un exemple ?
=> derniere etape OK

2 pièce(s) jointe(s)

Citation:

pour chaque pas de temps je fais ce calcul pour trois cas:
X=2 Y=1 ; X=18 Y=10 ; X=5 Y=6
d'où l'intéret de caluler pour chaque cas ces choses

Citation:

à chaque pas de temps a,b,c,d sont différents du pas de temps precedent.

Mais alors là on n'est plus du tout dans les conditions d'applications de N-R qui est une méthode itérative pour UNE fonction bien précise, pas pour une famille paramétrée de fonctions.
Cependant je ne comprends pas bien car dans le morceau de code qui est donné en exemple a,b,c,d,X et Y ne varient pas
Code:

1 2 3 4 5 while ( residu >1e-9 || countt > MAX_ITERATION_NR) { xM=xM-(a*pow(xM,(Y-X)/Y)+b*pow(xM,-X/Y)+c*xM+d )/( a*((Y-X)/Y)*pow(xM,-X/Y)+b*(-X/Y)*pow(xM,(-X-Y)/Y)+c); residu= a*pow(xM,(Y-X)/Y)+b*pow(xM,-X/Y)+c*xM+d; }
Maintenant il semble que cette boucle soit située dans une autre structure itérative, enfin on ne connait qu'un bout de l'histoire. En tout cas si on veut diagnostiquer pourquoi N-R ne marche pas (ce qui arrive, voir wikipedia) il serait bon d'avoir un exemple numérique précis de façon à vérifier f et sa dérivée.
Voir par exemple: http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Newton
Il me semble de plus qu'il y a une erreur dans le calcul de la dérivée :

27/10/2011, 23h50
membreComplexe12

en fait je me suis mal exprimé:
=> j'ai une fonction precise pour un pas de temps et je resous cette fonction pour ce pas de temps
=> pour un autre pas de temps, j'ai une autre fonction où j'applique N-R de nouveau pour avoir la solution de mon probleme en ce pas de temps

pour resumé:
=> pour chaque pas de temps j'ai une fonction à resoudre où a,b,c,d sont les constantes
=> la pas de temps suivant c valeurs changent donc la fonction n'est pas la meme

sinon, voici mon polynome:
P(xM)= a.xM^{(Y-X)/Y}+b.xM^{-X/Y}+c.xM+d

=> je vais verifier m'a derivée, au fait savez vous comment mettre des bornes à N-R ?

EDIT:
- je vais faire un autre poste pour la recherche des racines de polynomes avec la methode de la matrice compagnon
28/10/2011, 18h04
Aleph69

Bonjour,

ce n'est pas l'algorithme qu'il faut modifier mais la formulation du problème initial, à savoir en ajoutant les contraintes connues et en utilisant (par exemple) des multiplicateurs de Lagrange pour les prendre en compte.
28/10/2011, 21h22
membreComplexe12

merci pour ta reponse, oui en effet c'est ce que j'avais compris mais je ne sais pas trop comment ça se met en place quand c'est des contraintes d'inegalité :oops:

voici ce que je sais

1°) cas des contraintes d'egalités
=> je veux minimiser: [TEX]f(x,y)=3x^9+9y^2+9[/TEX]
=> je dois respecter ces contraintes h(x,y): [TEX]9x+y=5[/TEX] g(x,y): [TEX]9y=5[/TEX]

il suffit donc de cherche le minimum de [TEX]f(x,y)-\lambda.h(x,y)-\nu.h(x,y)[/TEX]
=> si c'est faisable analytiquement on cherche à annuler le gradient
=> sinon on utilise par l'algorithme de Newton Raphson

2°) cas des contraintes d'inegalités
=> je veux minimiser: [TEX]f(x,y)=3x^9+9y^2+9[/TEX]
=> je dois respecter ces contraintes h(x): [TEX]x>0[/TEX] g(x,y): [TEX]9x+y<5[/TEX]

comment dois je formuler le probleme et comment dois je proceder pour minimiser ma fonction ??