[Programmation] Trois équations à trois inconnues

Discussions générales concernant les mathématiques.
[ce forum est modéré par les modérateurs globaux du site]
Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Pour obtenir de l'aide sur un exercice ou un problème, consulter cette section. (ce forum est destiné aux discussions plutôt théoriques)

[Programmation] Trois équations à trois inconnues

Messagepar coraya » Vendredi 25 Août 2006, 22:38

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 :

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

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 !
coraya
Utilisateur
 
Messages: 5
Inscription: Vendredi 25 Août 2006, 22:15

Publicité

Messagepar MB » Samedi 26 Août 2006, 00:20

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.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Messagepar coraya » Samedi 26 Août 2006, 11:26

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
coraya
Utilisateur
 
Messages: 5
Inscription: Vendredi 25 Août 2006, 22:15

Messagepar MB » Samedi 26 Août 2006, 12:42

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 $\LaTeX$ (voir ici) et d'éviter le style SMS pour la lisibilité des messages.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Messagepar nirosis » Samedi 26 Août 2006, 14:06

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:
nirosis
Administrateur
 
Messages: 1806
Inscription: Samedi 28 Mai 2005, 13:48
Localisation: Orsay, France
Statut actuel: Actif et salarié | Maître de conférence

Messagepar coraya » Samedi 26 Août 2006, 15:07

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 :

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

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

[center]$\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.}$[/center]

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)
coraya
Utilisateur
 
Messages: 5
Inscription: Vendredi 25 Août 2006, 22:15

Messagepar MB » Samedi 26 Août 2006, 16:48

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.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Messagepar coraya » Samedi 26 Août 2006, 17:12

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 ...
coraya
Utilisateur
 
Messages: 5
Inscription: Vendredi 25 Août 2006, 22:15

Messagepar MB » Samedi 26 Août 2006, 18:35

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.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Messagepar coraya » Mardi 05 Septembre 2006, 21:04

Je n'y suis pas parvenu :( C'est dommage, j'ai pris une classe toute faite mais je reste sur ma faim.
coraya
Utilisateur
 
Messages: 5
Inscription: Vendredi 25 Août 2006, 22:15

Messagepar Arnaud » Mardi 05 Septembre 2006, 22:09

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
Arnaud
Modérateur
 
Messages: 7115
Inscription: Lundi 28 Août 2006, 12:18
Localisation: Allemagne
Statut actuel: Actif et salarié | Enseignant

Messagepar rebouxo » Mercredi 06 Septembre 2006, 08:33

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
rebouxo
Modérateur
 
Messages: 6958
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Messagepar Arnaud » Mercredi 06 Septembre 2006, 10:02

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
LaTeX - Exemples de formules LaTeX

Pas d'aide en MP (non plus)
Arnaud
Modérateur
 
Messages: 7115
Inscription: Lundi 28 Août 2006, 12:18
Localisation: Allemagne
Statut actuel: Actif et salarié | Enseignant

Messagepar la main gauche » Jeudi 07 Septembre 2006, 18:03

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
la main gauche
Méga-utilisateur
 
Messages: 274
Inscription: Jeudi 30 Mars 2006, 07:44
Localisation: selon l'idéal de la liberté

Messagepar rebouxo » Jeudi 07 Septembre 2006, 20:15

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
rebouxo
Modérateur
 
Messages: 6958
Inscription: Mercredi 15 Février 2006, 13:18
Localisation: le havre
Statut actuel: Actif et salarié | Enseignant

Messagepar guiguiche » Jeudi 07 Septembre 2006, 20:18

Cela dit, pour un système $3\times3$, les formules de Cramer ne sont pas si terribles à écrire.
guiguiche
Modérateur
 
Messages: 8071
Inscription: Vendredi 06 Janvier 2006, 15:32
Localisation: Le Mans
Statut actuel: Actif et salarié | Enseignant

Messagepar Arnaud » Jeudi 07 Septembre 2006, 21:13

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
LaTeX - Exemples de formules LaTeX

Pas d'aide en MP (non plus)
Arnaud
Modérateur
 
Messages: 7115
Inscription: Lundi 28 Août 2006, 12:18
Localisation: Allemagne
Statut actuel: Actif et salarié | Enseignant

Messagepar la main gauche » Mercredi 13 Septembre 2006, 13:25

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.
la main gauche
Méga-utilisateur
 
Messages: 274
Inscription: Jeudi 30 Mars 2006, 07:44
Localisation: selon l'idéal de la liberté

Messagepar Arnaud » Mercredi 13 Septembre 2006, 13:35

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
LaTeX - Exemples de formules LaTeX

Pas d'aide en MP (non plus)
Arnaud
Modérateur
 
Messages: 7115
Inscription: Lundi 28 Août 2006, 12:18
Localisation: Allemagne
Statut actuel: Actif et salarié | Enseignant

Messagepar MB » Mercredi 13 Septembre 2006, 13:47

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 édition par MB le Mercredi 13 Septembre 2006, 14:29, édité 1 fois.
MB
Administrateur
 
Messages: 6892
Inscription: Samedi 28 Mai 2005, 13:23
Localisation: Créteil
Statut actuel: Actif et salarié | Enseignant

Suivante

Retourner vers Tribune des mathématiques

 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 5 invités