Discussion :

[smercier2]

Bonjour � tous,

J'ai la r�solution d'un syst�me d'�quations non lin�aires (2 �quations, 2 inconnues) du type :

f(x,y)=0
g(x,y)=0

Je travaille en C++/C...je n'arrive pas � trouver pour le moment une librairie capable de faire cel�...

Quelqu'un aurait-il un tuyau ? Un mot cl� ?


MErci par avance

Cordialement

MERCIER S�bastien

[ToTo13]

Bonjour,

il me semble pour que ce genre de probl�mes il faut utiliser la m�thode Levenberg-Marquardt. (A confirmer).

[Zavonen]

J'ai la r�solution d'un syst�me d'�quations non lin�aires (2 �quations, 2 inconnues) du type :
f(x,y)=0
g(x,y)=0

Il y a deux probl�mes distincts:
Probl�me de l'existence et du nombre des solutions (plut�t alg�brique par nature)
Probl�me du calcul d'une solution dans un ensemble particulier (souvent un rectangle o� on sait a priori qu'une solution existe (probl�me d'analyse num�rique plut�t).
Pour le premier, en toute g�n�ralit� je n'ai pas grand chose � proposer sauf peut �tre quand les �quations sont alg�briques (polynomiales). C'est dans tous les cas un pb assez (tr�s) difficile.
Pour le second les choses sont plus simples:
une �quation f(x,y)=0 d�finit le plus souvent une fonction implicite y=h(x), c'est le cas en particulier pour les fonctions continument diff�rentiables au voisinage d'un point o� la d�riv�e par rapport � la seconde variable est non nulle, on peut m�me avoir une expression approch�e de cette fonction par un d�veloppement limit� faisant intervenir cette d�riv�e partielle.
Si on est dans le cas o� on peut appliquer cela pour les deux � la fois. Le syst�me se ram�ne � h(x)=k(x) soit (h-k)(x)=0 annulation d'une fonction continue, pour ce pb les m�thodes sont nombreuses.
Le probl�me �tant sym�trique sur les deux variables on peut aussi �tre ramen� � x=k(y) et x=h(y)
ou bien
y=h(x) et x=k(y)
Dans le dernier cas on cherche un point fixe, ce qui revient encore � annuler une fonction continue.
Je ne connais aucun programme C qui fasse cela mais cela ne doit pas �tre difficile � �crire.

[Zavonen]

En fait j'aurais peut �tre �t� plus clair si j'avais utilis� un langage 'graphique'
On cherche une solution au voisinage d'un point M0(x0,y0).
On remplace localement la courbe f(x,y)=0 par sa tangente au point d'abscisse x0, la courbe g(x,y)=0 par sa tangente au point d'abscisse x0, l'intersection des deux tangentes est certainement plus pr�s du point cherch� que M0, il reste � it�rer le processus.

[pseudocode]

En fait j'aurais peut �tre �t� plus clair si j'avais utilis� un langage 'graphique'
On cherche une solution au voisinage d'un point M0(x0,y0).
On remplace localement la courbe f(x,y)=0 par sa tangente au point d'abscisse x0, la courbe g(x,y)=0 par sa tangente au point d'abscisse x0, l'intersection des deux tangentes est certainement plus pr�s du point cherch� que M0, il reste � it�rer le processus.

Bref, la methode de newton... c'est ca ?

[sidahmed]

Bonjour,

voici les m�thodes les plus utilis�es pour la r�solution des syst�mes d'�quations non lin�aires :

• M�thode de Newton
• M�thode du point fixe
• M�thode de Gauss - Siedel
• M�thode de relaxation

Bon courage.

[Zavonen]

Bref, la m�thode de Newton... c'est ca ?

Formellement non, mais on peut jouer sur les mots.
La m�thode de Newton consiste � calculer une solution de f(x)=0 au voisinage d'un point en rempla�ant la courbe par sa tangente, et en proposant comme nouvelle approximation l'intersection de cette tangente avec l'axe des x. Le fondement th�orique de newton est l'approximation locale des fonctions par des fonctions du premier degr� 'affines'.
Ici, le fondement th�orique est le th�or�me dit 'des fonctions implicites'. cela dit, l'id�e de base est la m�me.
Newton est avec Leibniz le fondateur du calcul diff�rentiel, il est donc le p�re de tout.

[FrancisSourd]

Voici une liste de librairies.
http://www.ici.ro/camo/hnp.htm

J'ai utilis� solvopt et j'en suis plut�t satisfait.

Tu peux voir ton probl�me comme la minimisation de f^2(x,y) + g^2(x,y)

Si tu trouves une solution de co�t nul, c'est gagn�!

[pseudocode]

Tu peux voir ton probl�me comme la minimisation de f^2(x,y) + g^2(x,y)

Si tu trouves une solution de co�t nul, c'est gagn�!

Oui, c'est ce que j'ai pens� aussi... mais est-ce que cette methode va converger vers les memes valeurs que "f(x,y)=0 ET g(x,y)=0".

Dans un cas on va faire intervenir les deriv�es partielles des fonctions f() et g(), et dans l'autre les deriv�es partielles de H()=f^2()-g^2(). On risque de cr�er des nouveaux minima locaux avec la fonction H(), non ?

[smercier2]

Merci � tous de vos r�ponse qui m'ont un peu �claircie...

Est-ce que "SolvOpt" n�cessite l'installation de "Matlab" ?
Ce qui voudrait dire achat d'une licence ?

MErci par avance

MERCIER S�bastien

[FR119492]

Salut.

Le mieux est d'aller regarder dans "Numerical Recipes". Dans mon �dition, qui n'est pas tr�s r�cente, avec les exemples en Fortran, c'est le paragraphe

9.6 Newton-Raphson Method for Nonlinear Systems of Equations.

Bonne chance
Jean-Marc Blanc

[sidahmed]

Bonsoir,

j'ajoute la m�thode de Newton amortie.

Bon courage.

[Kevinas]

Les �quations implicites de la forme h(x, f(x))=0.
Les deux grandes m�thodes classiques d'ordre quelconque pour d�termminer le z�ro d'une fonction sont :
- la m�thode de Householder
- la m�thode de Schr�der
Les m�thodes de Newton-Raphson (ordre 2) ou de Halley (ordre 3) en sont des cas particuliers.
Ces m�thodes donnent surtout d'excellents algorithmes pour d�terminer les fonctions alg�briques en un temps de l'ordre de la multiplication.

[FR119492]

J'ajouterais peut-�tre encore que ces m�thodes sont it�rative et qu'il importe de bien choisir les valeurs initiales sous peine d'avoir un temps de calcul prohibitif, d'avoir des it�rations qui ne convergent pas ou de tomber sur une solution qui n'est pas la bonne, car il y en a souvent plusieurs.

Jean-Marc Blanc

[souviron34]

et je rajouterais (d�pendamment du nombre d'inconnues/nombre d'�quations), la m�thode du Simplex...

[sidahmed]

Bonjour,

et je rajouterais (d�pendamment du nombre d'inconnues/nombre d'�quations), la m�thode du Simplex...

J'ai cru que la m�thode du Simplex est utilis�e exclusivement en recherche op�rationnelle ! Merci pour l'information.

[FrancisSourd]

Est-ce que "SolvOpt" n�cessite l'installation de "Matlab" ?
Ce qui voudrait dire achat d'une licence ?

Non, SolvOpt est du pur C. C'est open source mais je ne me souviens pas des termes exacts de la licence.

[FrancisSourd]

Bonjour,

J'ai cru que la m�thode du Simplex est utilis�e exclusivement en recherche op�rationnelle ! Merci pour l'information.

Il existe deux m�thodes du simplexe.
L'une pour l'optimisation lin�aire sous contrainte lin�aire.
L'autre pour l'optimisation non diff�rentiable (a priori sans contrainte).

Le premier est celui de la RO (si tu dis qu'il n'est utilis� "qu'en" recherche op�rationnelle, on peut se dire que beaucoup de probl�mes rel�vent de la recherche op�rationnelle...)
Le second est dans les "numerical recipes" et je pense que c'est celui-ci qu'il faut utiliser.

[FrancisSourd]

Oui, c'est ce que j'ai pens� aussi... mais est-ce que cette methode va converger vers les memes valeurs que "f(x,y)=0 ET g(x,y)=0".

Dans un cas on va faire intervenir les deriv�es partielles des fonctions f() et g(), et dans l'autre les deriv�es partielles de H()=f^2()-g^2(). On risque de cr�er des nouveaux minima locaux avec la fonction H(), non ?

Dans mon message, j'utilise H()=f^2()+g^2() et non "-".

Si H(x,y)=0, il faut que f^2(x,y)=0 et g^2(x,y)=0 cas f^2 et g^2 sont positives. De plus comme H est positive, H(x,y)=0 est un minimum global (donc local �galement).

[pseudocode]

Dans mon message, j'utilise H()=f^2()+g^2() et non "-".

oups. erreur de typo... il fallait bien sur lire un "+" dans mon post.

Si H(x,y)=0, il faut que f^2(x,y)=0 et g^2(x,y)=0 cas f^2 et g^2 sont positives. De plus comme H est positive, H(x,y)=0 est un minimum global (donc local �galement).

oui, je comprend bien que la solution H(x,y)=0, implique f(x,y)=0 ET g(x,y)=0.

Je me pose juste le probleme de la stabilit� des algorithmes qui utilisent les d�riv�es partielles pour trouver x et y.