[Programmation] Trois équations à trois inconnues

Discussions générales concernant les mathématiques.
[forum modéré par les modérateurs globaux du site]
Règles du forum
Merci de soigner la rédaction de vos messages et de consulter ce sujet avant de poster. Pensez également à utiliser la fonction recherche du forum.
coraya
Utilisateur débutant
Utilisateur débutant
Messages : 5
Inscription : vendredi 25 août 2006, 23:15

[Programmation] Trois équations à trois inconnues

Message par coraya »

Bonsoir,

Je suis programmeur autodidacte mais je n'ai plus fait de maths depuis bien 15 ans ... ! Bref, je sèche complètement depuis ce matin.

Contexte : pour coder des équations de plans pour des volumes parallélipipédiques dans un format informatique spécifique, je dois résoudre ce système :

$\left\{ \begin{array}{l} xA + yB +zC = 0 \\ xD + yE + zF =0 \\ xG + yH + zI = 0 \end{array} \right.}$


Avec A, B, C, D, E, F, G, H et I définis mais bien sur différents suivant les volumes rencontrés.

Question : que vaut x, y et z dans le cas général ?

Je tombe toujours sur x = y = z = 0 qui ne me convient évidemment pas.


Mes souvenirs de maths sont devenus inaccessibles ... ;-)
Merci de voter aide !

MB
Administrateur
Administrateur
Messages : 7134
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Message par MB »

Tu peux regarder la méthode du pivot de Gauss : ici.
Par contre si ta matrice est inversible (si il n'y a qu'une seule solution donc), c'est normal que tu trouves toujours le vecteur nul comme solution.

coraya
Utilisateur débutant
Utilisateur débutant
Messages : 5
Inscription : vendredi 25 août 2006, 23:15

Message par coraya »

Je vous remercie mais c'est du chinois, je n'ai pas le moindre souvenir de ça. Peut-être est-ce une histoire de notation que je ne traduits pas ?
J'ai recherché sur la méthode du pivot de gauss mais je n'ai pas avancé sur mon problème.

Merci pour votre réponse

MB
Administrateur
Administrateur
Messages : 7134
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Message par MB »

Le but du pivot de Gauss est de modifier le système pour le rendre triangulaire et ainsi pour le résoudre aisément. C'est une méthode très classique et tu trouveras facilement des algorithmes pour l'implémenter.

Par contre, vu que chaque ligne est égale à 0, si tu n'as qu'une seule solution à ton système, c'est normal que ça soit toujours 0.
MB (Pas d'aide en Message Privé)
Merci d'utiliser MathJax (voir ici) et d'éviter le style SMS pour la lisibilité des messages.

nirosis
Administrateur
Administrateur
Messages : 1803
Inscription : samedi 28 mai 2005, 14:48
Localisation : Orsay, France

Message par nirosis »

Effectivement, il est normal que tu trouves toujours x=0, y=0 et z=0 dans ton système. Si ça ne convient pas, c'est plutôt sur la véracité de ton système qu'il faut chercher...

Sinon, comme le dit MB, tu peux essayer de triangulariser ton système avec le pivot de Gauss. La méthode est simple, il suffit de faire de remplacer la ligne 1 du système par une combinaison linéaire bien choisie eds 3 lignes de ton système.

exemple: Ligne1 <- Ligne 1 - A/D * Ligne2 (avec tes notations)

Ainsi la variable x disparait dans cette nouvelle ligne. L'idée est que tu modifies pas les solutions du système en remplaçant l'ancienne ligne 1 par une ligne équivalente.
J'espère que tu comprends l'idée :wink:

coraya
Utilisateur débutant
Utilisateur débutant
Messages : 5
Inscription : vendredi 25 août 2006, 23:15

Message par coraya »

C'est bien ce qui me chiffone, ce résultat à 0 ...

J'ai 6 plans au départ (6 pour chacune des faces d'un volume cubique).
Pour chaque plan, j'ai une équation : $ax + by +zc = d$.
Si je prend trois points appartenant à ce plan (je connaitrais tjrs au moins trois points par face si ce n'est les 4, ce sont les sommets de mon volume), j'aurais :

$\left\{ \begin{array}{l} ax1 + by1 +cz1 = d \\ ax2 + by2 +cz2 =d \\ ax3 + by3 +cz3 = d \end{array} \right.}$


En faisant L1 - L2, L2 - L3 et L3 - L1, je tombe bien sur mon système que j'ai posté au départ

$\left\{ \begin{array}{l} a.(x1-x2) + b.(y1-y2) + c.(z1-z2) = 0 \\ a.(x2-x3) + b.(y2-y3) + c.(z2-z3) = 0 \\ a.(x3-x1) + b.(y3-y1) + c.(z3-z1) = 0 \end{array} \right.}$


je connais les couples (x1, y1, z1) etc .., ce sont a, b, c et d que je dois trouver.
Me suis-je trompé ?

(oui, désolé, j'avais changé les notations pour les rendre plus "classiques" dans mon premier post)

MB
Administrateur
Administrateur
Messages : 7134
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Message par MB »

Tu as commencé un début de pivot de Gauss à la main, mais il n'est pas correct.
Tu peux implémenter ton pivot de Gauss (l'algorithme est simple et se trouve un peu partout je pense) et l'appliquer directement au système suivant :

$$\left\{ \begin{array}{l} ax1 + by1 +cz1 = d \\ ax2 + by2 +cz2 =d \\ ax3 + by3 +cz3 = d \end{array} \right.}$$

Pour le pivot de Gauss, seules les opérations suivantes sont autorisées :
  • échange de deux lignes,
  • multiplication d'une ligne par un nombre non nul,
  • addition d'un multiple d'une ligne à une autre ligne.
On fait une opération par étape pour conserver toujours des système équivalents. La première étape est donc L1 - L2, la seconde L2 - L3 et la dernière L3 - L1 mais le L1 a déjà été modifié à la première étape. Il faut donc utiliser celui-ci.

coraya
Utilisateur débutant
Utilisateur débutant
Messages : 5
Inscription : vendredi 25 août 2006, 23:15

Message par coraya »

Merci, je vais reprendre avec la correction de mon erreur.

Comme je l'ai dit, je suis autodidacte en la matière et récupérer un algo tout fait ne m'intéresse pas. J'ai d'ailleurs trouvé une classe en C pour la résolution d'un tel système ! Mais ce n'est pas le but recherché :-) Surtout que ce n'est pas à but professionnel.

Cela dit, je me retrouve avec 4 inconnues (a, b, c et d) pour trois équations, ce qui m'inquiète un peu ! Je vais voir ça ...

MB
Administrateur
Administrateur
Messages : 7134
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Message par MB »

coraya a écrit :Cela dit, je me retrouve avec 4 inconnues (a, b, c et d) pour trois équations, ce qui m'inquiète un peu ! Je vais voir ça ...
En fait, tous ces nombres sont définis à un coefficient près. Par exemple, si $x+2y+y=1$ est une équation d'un plan, alors $2x+4y+2x=2$ est aussi une équation de ce même plan. Il n'y a donc en fait que 3 inconnues.

coraya
Utilisateur débutant
Utilisateur débutant
Messages : 5
Inscription : vendredi 25 août 2006, 23:15

Message par coraya »

Je n'y suis pas parvenu :( C'est dommage, j'ai pris une classe toute faite mais je reste sur ma faim.

Arnaud
Modérateur global
Modérateur global
Messages : 7095
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne

Message par Arnaud »

Voici une proprosition ( avec les notations du premier post ) :

D'abord définir une variable $det$ qui vaut $A \times (E \times I-F \times H)-B \times (D \times I-F \times G) + C \times (D \times H-E \times G)$.
Si elle vaut $0$, le système n'a pas de solutions, ou une infinité ( on peut ajouter de quoi savoir si c'est l'un ou l'autre ).

Le déterminant est aux matrices, ce qu'est le discriminant $\Delta$ au polynômes du second degré : sa valeur nous permet de savoir rapidement à quoi on a affaire.

2e étape : si $det \not= 0$
Il faut éliminer les inconnues de façon à obtenir un système triangulaire, c'est-à-dire de façon à ce que la troisième équation n'aie qu'une seule inconnue, la deuxième équation 2 inconnue, avec celle qu'on peut trouver dans la troisième équation, .....

Premier test : voir lequel de $A$, $D$, $G$ est non-nul, puis changer la place des variables si il s'agit de $D$ ou de $G$, de façon à ce que ce soit la première équation ave laquelle on travaillera ( donc avec $A$ ).

On fait les opérations ( 1ère équation ajoutée aux 2 autres ): $D=0$, $G=0$, $E=E+B \times \frac{D}{A}$, $H=H+B \times \frac{G}{A}$, ....

On obtient alors un système de la forme :
$$\left\{
\begin{array}{r}
xA+yB+zC=0\\
yE+zF=0\\
yH+zI=0
\end{array} \right.$$

On refait la même chose avec E et H : au-moins l'un est non-nul, donc on pourra éliminer l'autre, et on obtient :

$$\left\{
\begin{array}{r}
xA+yB+zC=0\\
yE+zF=0\\
zI=0
\end{array} \right.$$

On trouve $z$, puis $y$, puis $x$.

C'est long comme méthode, mais la plus simple pour commencer :D

rebouxo
Modérateur global
Modérateur global
Messages : 6962
Inscription : mercredi 15 février 2006, 13:18
Localisation : le havre

Message par rebouxo »

Tant qu'a calculer le déterminant, il existe des formules donnant la solution du système grâce à celui-ci. Je sais dans quel livre c'est (Lelong-ferrand), mais il est inaccessible !
Ton cas est l'un des seuls où l'utilisation du determinant permet en pratique de résoudre un système. Je pense que l'on ne calcule pas le déterminant lorsque que l'on effectue le pivot de Gauss. En effet calculer le déterminant est très long alors que le pivot est un algo efficace.

Olivier
A line is a point that went for a walk. Paul Klee.
Par solidarité, pas de MP.

Arnaud
Modérateur global
Modérateur global
Messages : 7095
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne

Message par Arnaud »

En fait je voulais que les formules soient assez simples, c'est pourquoi je n'ai pas voulu donné de recette de cuisine ( autre que le déterminant ) pour la recherche de la matrice inverse.

Dans le programme, le déterminant ne fait office que de test de validité pour la suite du programme.

C'est pas super cohérent mathématiquement, mais cela permet de faire un programme de résolution sans trop rentrer dans la théorie.
Arnaud
Un peu d'info - Pyromaths - Pas d'aide en MP (non plus)

la main gauche
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 274
Inscription : jeudi 30 mars 2006, 08:44
Localisation : selon l'idéal de la liberté

Message par la main gauche »

Arnaud a écrit : C'est long comme méthode, mais la plus simple pour commencer :D
Hmm, je ne crois pas que cela soit très long, pour une matrices de taille nxn la méthode du pivot orend envriron n^3 opérations, les méthodes plus malines font quuelque chose comme n^2.8, autrement dit, tant qu'on a pas affaire à des systèmes linéaires très grands comme en AN.

Ensuite on se rend compte qu'une matrice n'est pas inversible lorsqu'on ne trouve pas de pivot non nul dans la phase de recherche de pivot, il n'est donc pas utile de calculer auparavent le déterminant du système. D'autant plus que les méthodes raisonnables de calcul de déterminant utilisent la métyhode du pivot de gauss.
la Main Gauche

rebouxo
Modérateur global
Modérateur global
Messages : 6962
Inscription : mercredi 15 février 2006, 13:18
Localisation : le havre

Message par rebouxo »

Il me semblait bien. La méthode tirée de la définition du déterminant n'est-elle pas en $n!$ ou quelque chose comme cela ?
A line is a point that went for a walk. Paul Klee.
Par solidarité, pas de MP.

guiguiche
Modérateur global
Modérateur global
Messages : 8074
Inscription : vendredi 06 janvier 2006, 15:32
Statut actuel : Enseignant
Localisation : Le Mans

Message par guiguiche »

Cela dit, pour un système $3\times3$, les formules de Cramer ne sont pas si terribles à écrire.

Arnaud
Modérateur global
Modérateur global
Messages : 7095
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne

Message par Arnaud »

coraya a écrit :Je vous remercie mais c'est du chinois, je n'ai pas le moindre souvenir de ça.
Je répète que mon post avait pour but d'expliquer simplement les choses, de façon à ce que chaque étape soit compréhensible.
Il n'y a pas de difficulté quant à l'écriture des formules de Cramer, mais quant à leur compréhension pour un non-initié :)

L'utilisation du déterminant est clairement superflue, mais elle évite de laisser tourner le programme pour rien ( bien que cela ne fasse pas une grande différence au vue des processeurs actuels ). :wink:
Arnaud
Un peu d'info - Pyromaths - Pas d'aide en MP (non plus)

la main gauche
Utilisateur éprouvé
Utilisateur éprouvé
Messages : 274
Inscription : jeudi 30 mars 2006, 08:44
Localisation : selon l'idéal de la liberté

Message par la main gauche »

Arnaud a écrit :L'utilisation du déterminant est clairement superflue, mais elle évite de laisser tourner le programme pour rien
Désolé d'être lourd mais le pivot de Gauss est une méthode pratique pour calculer les déterminants, donc le calculer avant c'est faire au moins deux fois plus de calculs, donc le faire avant c'est laisser tourner le programme pour rien.
( bien que cela ne fasse pas une grande différence au vue des processeurs actuels ). :wink:
Même les trés gros processeurs flanchent devant les grandes complexités, genre n!.
Avec un ordinateur IL NE FAUT PAS utilsier les formules de Cramer, cela n'a aucun avantage et plein d'inconvénients. Ces formules sont des outils mathématiques inadaptés au traitement numérique.

Arnaud
Modérateur global
Modérateur global
Messages : 7095
Inscription : lundi 28 août 2006, 13:18
Localisation : Allemagne

Message par Arnaud »

Il me semble qu'on parle dans ce topic d'une matrice $3 \times 3$, donc le calcul du déterminant nécessite 5 additions et 9 multiplications.

Je ne parlais évidemment pas d'une matrice $n \times n$ pour laquelle ma proposition n'est absolument pas adaptée.
Je ne pense pas être capable de fournir un algorithme optimisé dans ce cas, j'ai toujours programmé à la brute.... :D

PS : je n'ai d'ailleurs pas compris pourquoi ma formule LaTeX du déterminant n'est pas passée dans l'un de mes posts précédents.
Arnaud
Un peu d'info - Pyromaths - Pas d'aide en MP (non plus)

MB
Administrateur
Administrateur
Messages : 7134
Inscription : samedi 28 mai 2005, 14:23
Statut actuel : Enseignant

Message par MB »

Arnaud a écrit :PS : je n'ai d'ailleurs pas compris pourquoi ma formule LaTeX du déterminant n'est pas passée dans l'un de mes posts précédents.
Oui, je viens de le constater. Il s'agit de ce code :

Code : Tout sélectionner

$A \times (E \times I-F \times H)-B \times (D \times I-F \times G) + C \times (D \times H-E \times G)$
A priori pas de problème pourtant ... mais j'ai déjà eu des trucs bizarres du genre. Je ne sais pas encore pourquoi, mais on dirait que c'est la formule qui est trop longue car en séparant en 2 partie ça fonctionne.

Il va falloir se pencher sur ce problème ...
Dernière modification par MB le mercredi 13 septembre 2006, 15:29, modifié 1 fois.