Discussion :

[Jbx 2.0b]

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.

[lgirard]

Une solution simple est d'utiliser les solver de PL existant sur le marché, du type XPress MP, CPlex, etc...

[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

[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.

[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 ....

[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...

[FrancisSourd]

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.

[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.

[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.

[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

[Charlemagne]

Erratum: Je viens de dire une bétise:

Le rang d'une matrice sigulière est inférieur strictement à N

[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

[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.

[FrancisSourd]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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]

[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.

[lgirard]

. 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

[FrancisSourd]

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

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!

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)

[FrancisSourd]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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)

[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