Solveur d'equations

Version imprimable

12/05/2005, 12h14
Jbx 2.0b

Solveur d'equations

Bonjour,
J'aimerais developper (en C/C++) un solveur d'equation pouvant allez jusqu'a l'ordre 14 voir plus. J'ai entendu parler de la methode du pivot de gauss mais il semblerait qu'elle pose probléme dans certain cas, es ce que quelqu'un sait lesquels ?
Je sais aussi qu'on peut utiliser les matrices inverses pour calculer le resultat, mais comment calculer l'inverse d'une matrice 14x14 ou mieux d'ordre NxN?
Quelles sont les autres methodes existantes ?
Toute documentation serait la bienvenue.
Merci d'avance pour vos réponses.
12/05/2005, 12h37
lgirard

Une solution simple est d'utiliser les solver de PL existant sur le marché, du type XPress MP, CPlex, etc...
12/05/2005, 13h08
Charlemagne

Je suis pas trop au courant dans ce domaine, mais il semblerait que la décomposition LU d'une matrice soit une méthode courante pour résoudre les système d'équation linaire:
-plus rapide que l'inversion d'une matrice
-plus précise que le pivot de Gauss
Vérifie néanmoins mes affirmations.

Y'a de nombreuses bibliothèques qui proposent la décomposition LU
12/05/2005, 13h14
Jbx 2.0b

Je suis bien sur developpez.com ?
Non sans blaguer je veux developper un solveur et non pas en utiliser un, surtout s'il est payant. De plus je ne vois pas trop les utilisateurs de mon programme rentrer une à une les equations dans un autre logiciel puis ensuite rentrer à nouveau les resultats dans le programme pour qu'il puisse continuer son execution.
12/05/2005, 13h17
lgirard

les solvers de PL ne sont pas tous payants !!! surtout pour le type de pb que tu veux résoudre.

d'autre part, ce ne sont que des librairies de calcul, appelées par un pgme que tu écris toi...

maintenant, si tu veux ré inventer l'eau chaude, ne te gêne pas. Moi ce que j'en dis, c'est pour ne pas que tu perdes de temps ....
12/05/2005, 14h12
Charlemagne

Moi, je comprends jbx2004, je serais comme lui:

-il veut le faire lui-même
-comprendre les maths sous-jacentes
-peut-être l'intégrer à un programme déjà existant
-Peut-être que c'est pour le boulôt, dans ce cas pas le droit de réutiliser un exécutable ou du code
-ou tout plein d'autres bonne raisons...
12/05/2005, 15h22
FrancisSourd

Citation:

du type XPress MP, CPlex, etc...

Ces codes résolvent des programmes linéaires en nombres entiers, ce qui est (beaucoup) plus difficile que résoudre un simple système d'équations linéaires. Il y a des codes open source comme LAPACK ou la GNU Scientific Library. Les méthodes à disposition sont plus ou moins bien décrites dans la doc.

A mon avis, pour un système 14x14, ce n'est sans doute pas la peine de mettre en oeuvre des méthodes trop complexes à moins que la précision des calculs soit d'une extrème importance.
12/05/2005, 18h21
Jbx 2.0b

Tout d'abord merci à tous pour vos réponses. J'ai commencé à lire des docs sur la decomposition LU et il semblerait que cette méthode soit le plus optimisée. Malgrés tout, si le systéme n'a pas de solutions "vraies", elle ne permet pas de trouver une approximation. Comme les valeurs que je rentre dans mon programme sont experimentales donc entachées d'incertitudes, il est possible que je me trouve dans des cas ou le systéme soit indeterminés. En cherchant j'ai trouvé ce document : http://www.unilim.fr/pages_perso/jean.debord/math/matrices/matrices.htm#IV.D qui parle de decomposition en valeurs singuliéres qui semble pouvoir resoudre les sytémes inderterminés ou impossibles (quelle différence?) en proposant une approximation.
Si quelqu'un a des informations sur cette méthode ou d'autres, ou qui pourrait m'expliquer quand j'obtiens un systéme indeterminés ou impossible, je suis preneur.
12/05/2005, 18h36
Charlemagne

Le système est indéterminé quand au moins une des équation (ou ligne de la matrice) est la combinaison linéaire des autres.
En d'autres termes:
-le rang de la matrice est nul
-la matrice est singulière
-la matrice n'a pas d'inverse

Ca c'était à parier que dans le cas général, il fallait prévoir ce pépin. Ceci, quelque soit l'algorithme choisi.

A priori, ça n'a pas de sens de chercher une approximation dans ce cas puisqu'il y a une infinité de solutions.
C'est comme quand tu cherche le point d'intersection de 2 droites gràce à leurs équations, alors que ces droites sont confondues.
12/05/2005, 18h45
Charlemagne

A priori, pas besoin de vérifier auparavent que la matrice est régulière.
Ca coute du temps, de calculer le rang d'une matrice, alors que ce cas est probablement plutôt rare!
La page que tu sites permet de calculer les valeurs singulières, ce dont tu n'as a priori pas besoin.

Le problème devrait apparaître de lui-même au cours du pivot de gauss ou de la decomposition LU: genre division par 0.
Il suffit alors de placer judicieusement le test au cours des calculs, et par exemple de donner en retour de la fonction l'équation des points solutions du système
12/05/2005, 18h51
Charlemagne

Erratum: Je viens de dire une bétise:

Le rang d'une matrice sigulière est inférieur strictement à N
12/05/2005, 23h57
Jbx 2.0b

Ok je commence a comprendre. Je pourrais aussi prendre plus de données pour être sur que je ne tombe pas sur un systéme inderterminé. J'aurai plus d'equations que d'inconnues pour être sur que une de mes données n'est pas une combinaison linéaire d'une autre
13/05/2005, 09h50
Charlemagne

Si je comprends bien, tes mesures expérimentales te permettent de créer autant d'équations que tu le désires?

Dans ce cas, pourquoi pas, oui.
Si ta matrice est singulière, pourquoi pas piocher dans un réservoir à équation, jusqu'à avoir une soultion déterminée. Ca dépend de ton problème.

N'oublie pas le cas ou 2 équations sont contradictoires. (genre: point d'intersection de 2 droites strictement paralleles).
Ca devrait pas arriver si tes mesures expérimentales sont cohérentes, mais c'est pas totalement exclu si les mesures ont une marge d'erreur.
13/05/2005, 10h12
FrancisSourd
Citation:

Envoyé par jbx2004

Ok je commence a comprendre. Je pourrais aussi prendre plus de données pour être sur que je ne tombe pas sur un systéme inderterminé. J'aurai plus d'equations que d'inconnues pour être sur que une de mes données n'est pas une combinaison linéaire d'une autre

La, en revanche, tu risques de ne plus avoir de solutions (cf 3 droites dans le plan ont rarement un point d'intersection commun. Une idée est alors de trouver le point "le plus proche" de toutes les droites (s'il y a une seule solution, cela sera cette solution avec une distance nulle). Cela donne par exemple un programme linéaire. Par exemple, le système des 5 équations à trois inconnues suivant:
Code:

1 2 3 4 5 6 a1x + b1y + c1z = d1 a2x + b2y + c2z = d2 a3x + b3y + c3z = d3 a4x + b4y + c4z = d4 a5x + b5y + c5z = d5
devient le PL:
Code:

1 2 3 4 5 6 7 8 minimiser d sous les contraintes -d <= a1x + b1y + c1z -d1 <= d -d <= a2x + b2y + c2z -d2 <= d -d <= a3x + b3y + c3z -d3 <= d -d <= a4x + b4y + c4z -d4 <= d -d <= a5x + b5y + c5z -d5 <= d
Pour résoudre le PL, il faut utiliser l'algorithme de simplex. On peut citer GLPK comme librairie open source (il y a des codes commerciaux mais pour un problème de moins de 10 variables GLPK marche parfaitement).[/url]
13/05/2005, 10h30
Jbx 2.0b

Je vais essayer , le probléme c'est que je peut avoir jusqu'a 14 inconnues j'espere que GLPK peut les supporter.
13/05/2005, 10h35
lgirard

Citation:

Envoyé par FrancisSourd

. On peut citer GLPK comme librairie open source (il y a des codes commerciaux mais pour un problème de moins de 10 variables GLPK marche parfaitement).[/url]

bonjour Francis,
vous voyez qu'on y revient aux librairies open sources plutôt que de ré-écrire le simplexe :wink:
13/05/2005, 11h15
FrancisSourd

Citation:

Envoyé par FrancisSourd

pour un problème de moins de 10 variables GLPK marche parfaitement)

Citation:

Envoyé par jbx2004

c'est que je peut avoir jusqu'a 14 inconnues

Oups... Je voulais écrire que même pour 100 variables il ne devrait pas de problèmes!

Citation:

Envoyé par Igirard

on y revient aux librairies open sources plutôt que de ré-écrire le simplexe

Je suis pour l'open source;-)! En ce qui concerne la PL, c'est vrai que c'est une généralisation ô combien bien utile des systèmes d'équations linéaires.

En plus, programmer l'algo du simplexe commence à ne plus vraiment être un simple exercice qui permet de bien comprendre la méthode. En tout cas, mieux vaut avoir déjà programmé un pivot de Gauss avant de s'y lancer (pour ma part, je me suis arrêté à la programmation du pivot de Gauss, j'ai toujours utilisé CPLEX ou GLPK pour la PL)
13/05/2005, 11h26
FrancisSourd
Citation:
Envoyé par FrancisSourd

le système des 5 équations à trois inconnues suivant:

Code:

1 2 3 4 5 6 a1x + b1y + c1z = d1 a2x + b2y + c2z = d2 a3x + b3y + c3z = d3 a4x + b4y + c4z = d4 a5x + b5y + c5z = d5

devient le PL:

Code:

1 2 3 4 5 6 7 8 minimiser d sous les contraintes -d <= a1x + b1y + c1z -d1 <= d -d <= a2x + b2y + c2z -d2 <= d -d <= a3x + b3y + c3z -d3 <= d -d <= a4x + b4y + c4z -d4 <= d -d <= a5x + b5y + c5z -d5 <= d
Une précision... Pour que d représente la vraie distance, il ne faut pas oublier de normaliser les équations (la norme des vecteurs (a1,b1,c1)... doit être égale à 1)
13/05/2005, 12h21
Jbx 2.0b

Ok merci à tous pour vos réponses, je pense avoir tous les elements en main pour resoudtre mon probleme. Je marque le post resolu mais je reposterais peut-etre si je rencontre des difficultés.
A+ sur dvp.com