Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Système équations non linéaires, résolution ?
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
Bonjour,
il me semble pour que ce genre de problèmes il faut utiliser la méthode Levenberg-Marquardt. (A confirmer).
Il y a deux problèmes distincts:Envoyé par smercier2
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.
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 ?
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.
Formellement non, mais on peut jouer sur les mots.Bref, la méthode de Newton... c'est ca ?
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.
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é!
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 ?
SolvOpt ?
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
Système équations non linéaires
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
Bonsoir,
j'ajoute la méthode de Newton amortie.
Bon courage.
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.
Système équations non linéaires
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
et je rajouterais (dépendamment du nombre d'inconnues/nombre d'équations), la méthode du Simplex...
Bonjour,
J'ai cru que la méthode du Simplex est utilisée exclusivement en recherche opérationnelle ! Merci pour l'information.
Non, SolvOpt est du pur C. C'est open source mais je ne me souviens pas des termes exacts de la licence.
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.
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).
oups. erreur de typo... il fallait bien sur lire un "+" dans mon post.
oui, je comprend bien que la solution H(x,y)=0, implique f(x,y)=0 ET g(x,y)=0.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).
Je me pose juste le probleme de la stabilité des algorithmes qui utilisent les dérivées partielles pour trouver x et y.
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager