Système d'équations du second degré.

[Dlzlogic]

Bonjour,
Je propose le problème suivant.
Soit un système de N équations du second degré à N inconnues. Ce système peut résulter du calcul d'un objet où interviennent des distances. On admettra que ce système est correctement écrit et le but est calculer la solution voulue. Cette solution est proche d'une solution approchée supposée connue.
La forme générale d'une équation est la suivante :
a1.x² + b1.x + c1.y² + d1.y + e1.xy + f1.z² + g1.z + h1.xz + i1.yz + ... = r1
Il y a autant d'équations que d'inconnues, les paramètres d'une équation ne sont pas tous nuls, chaque terme à gauche du signe '=' peut être une inconnue au carré ou à la puissance 1 ou produit de deux inconnues.
Toutes les valeurs concernées, paramètres et inconnues sont des réels.
-----

[CM63]

Bonjour,

Et quelle est ta question?

[CM63]

Cette solution est proche d'une solution approchée supposée connue.

[Dlzlogic]

Bonjour CM63,
Il me semblait que la question était claire : résoudre le système.
Comme la plupart du temps il y aura beaucoup de calculs, il semble préférable de le faire avec l'aide de l'outil informatique. (j'ai bien précisé "faire" et non pas "faire-faire par W...").

[A voir en vidéo sur Futura]

[CM63]

Bonjour,

Si j'avais à traiter ce problème, je tenterais la méthode de Newton-Raphson, en linéarisant le système. Lorsqu'on est dans le domaine de convergence, la convergence est quadratique. Mais la plupart du temps, évidemment on est en dehors et au mieux ça converge lentement, au pire ça part dans les choux. Pour éviter cela il faut stabiliser l'estimation de la solution en ajoutant des hypothèses supplémentaires comme par exemple : je ne veux pas que la norme de la solution dépasse telle valeur.

Mais auparavant il faut se demander si le système a au moins une solution. Pour cela je tenterais par essais erreur si la fonction change de signe sur tel intervalle (de Rⁿ), si oui, cela veut dire qu'elle passe par 0 (théorème des valeurs intermédiaires) car elle est continue.

Pour plus de renseignements rechercher "équations" "non" linaires".

[Dlzlogic]

Donc, il ne semblerait pas que l'on puisse écrire une fonction qui résolve un tel système, sachant que le système admet une solution et que l'on connait une valeur proche.
Evidemment pour écrire un tel module, il faut avoir fait l'analyse.
En fait, ma question ne concerne pas un système donné, mais une méthode de résolution d'un tel système.

[CM63]

Pour faire la linéarisation dont je parle, il y a deux méthodes possibles:
- soit calculer le gradient en dérivant les polynômes , c'est compliqué mais possible, peut-être utiliser un logiciel de calcul formel, pour vérifier,
- soit calculer un "tenseur sécant" en donnant des petites variations aux variables, c'est approché, ça va converger plus lentement, mais ça peut marcher, il faut bien entendu, encore une fois, "contrôler" les estimations (par exemple s'assurer que leur norme ne dépasse pas une certaine valeur)

[Dlzlogic]

Merci pour vos interventions.

[minushabens]

une façon detraiter le problème un peu bourrine mais efficace est la suivante: je suppose que tes équations sont mg1 = md1 ... mgN = mdN (mg = membre gauche, md = membre droit). Tu calcules la somme des carrés des erreurs, soit la quantité (mg1-md1)^2+...+(mgN-mdN)^2 C'est une fonction de tes inconnues, positive ou nulle, et qui vaut 0 ssi les N équations sont simultanément satisfaites. Tu utilises maintenant un programme de minimisation non linéaire (par exemple la fonction nlm de R) et voilà.

[Dlzlogic]

Bonjour Minushabens,
J'ai proposé le problème, mais je n'ai dit nulle part que je ne savais pas le résoudre.
Pour 3 équations, c'est à dire trois inconnues, c'est simple et ça converge rapidement. C'est à dire qu'il est tout à fait réaliste de le résoudre avec une simple calculette.
Une application possible serait de calculer le graphe en 3D connaissant des distances entre 2 points. Là, c'est un problème un peu plus compliqué mais qui utiliserait cette fonction. Ce problème a été posé pour une représentation en 2D. C'est un problème intéressant dans la mesure où il faut tenir compte de l'inégalité triangulaire, et comme il s'agit de représentation on peut (et éventuellement on doit) modifier des distances pour que le calcul soit possible, en faisant des corrections au mieux.
Bonne journée.

[minushabens]

Une application possible serait de calculer le graphe en 3D connaissant des distances entre 2 points.

ça c'est un problème connu pour lequel on a une solution exacte, "non algorithmique" (i.e. non itérative). Ca s'appelle en français "positionnement multidimensionnel" et en anglais "multidimensional scaling".

[Dlzlogic]

Si j'ai bien compris, on utilise les distances de Manhattan et non les distances euclidiennes.
Par ailleurs, on utilise la méthode des moindres carrés, régulièrement controversée.
Si on utilisait ce type de méthode (distance le Manhattan) pour le calage de plans, ou le calcul de réseau géodésique, ou le calcul de position GPS ou tout autre calcul, bonjour les dégâts !
De toute façon, ce n'était qu'un exemple.

[Evil.Saien]

Salut,

Je suis pas sûr de saisir exactement ce qui bloque... Perso ça me semble être un problème standard d'optimisation où, comme bien souvent, 3 choix cruciaux s'imposent:
1. Définir la fonction de coût
2. Choisir la méthode d'optimisation
3. Initialiser correctement

Le 3 semble ok, pour le 2 y'a pas de secret (faut tester), alors il reste que le 1. Et pour la fonction de coût, bah libre à toi d'utiliser (ou non) les moindres carrés, norme L1, etc... Je vais pas faire la liste parce qu'il y en a un sacré paquet. Si en plus tu as une idée sur la distribution des variables, j'avoue une petite préférence pour le SURE.
https://en.wikipedia.org/wiki/Stein'..._risk_estimate

[Dlzlogic]

Bonjour Evil,
Le fil ne concerne pas l'optimisation. Si tu veux, tu peux ouvrir un sujet, mais celui-ci concerne la résolution d'un système d'équations de second degré.

D'ailleurs, à propos d'optimisation, ce n'est certainement pas "comme on veut", mais le but DOIT être de calculer la valeur la plus probable. C'est d'ailleurs assez curieux comme, par tous les bouts, on en revient souvent aux probabilités.
Pour mémoire, Minushabens m'avait promis une doc sur les régressions linéaires avec 3 variables, il a dû oublier.

[Evil.Saien]

Le fil ne concerne pas l'optimisation. Si tu veux, tu peux ouvrir un sujet, mais celui-ci concerne la résolution d'un système d'équations de second degré

Alors je veux bien que tu m'expliques la différence entre "résolution numérique" et "optimisation d'une erreur"...

Sans doute ai-je mal compris et tu souhaites une solution analytique mais du coup je vois pas trop ce que ça fait ici.

[Evil.Saien]

Pour mémoire, Minushabens m'avait promis une doc sur les régressions linéaires avec 3 variables, il a dû oublier.

Je peux te filer une doc pour une regression linéaire avec autant de variables que tu veux... De manière générale, ça s'appelle un "General Linear Model"
https://en.wikipedia.org/wiki/Generalized_linear_model

[Dlzlogic]

Bon, je vais essayer d'être plus explicite.
La résolution de système d'équation linéaire a fait l'objet de plusieurs échanges, outre le fait que l'on fasse un amalgame entre "représentation matricielle" et "calcul matriciel", bien souvent on fait un mélange entre méthode de résolution et type particulier de système. Par contre, on ne parle pas souvent de système du second degré, d'où la création de ce sujet.

J'ai donné comme exemple d'utilisation de la fonction le calcul d'un graphe dont on connait des longueurs des arcs.
La réponse (positionnement multidirectionnel) est hors-sujet, puisque le sujet du fil est la résolution de système du second degré, c'est à dire une question parfaitement générale, et le "contre exemple" contourne soigneusement le second degré.
Comme il ne me suffit pas de faire une affirmation, je dis pourquoi et je précise que cette méthode est approximative et contraire à l'obligation de résultat en matière de calcul. Eh oui, ce n'est pas "comme on veut". On n'utilise pas la méthode des moindres carrés au hasard, on sait exactement pourquoi.

Puisqu'on parle français le terme "algorithme" a un rapport direct avec la logique et aucun rapport avec "itération".

La différence entre "résolution numérique" et "optimisation d'une erreur" est la même qu'entre "démonstration" et "hypothèse".
Je rappelle que le dessin du graphe était un exemple. J'en ai un autre si tu veux : "soit un objet construit avec 7 triangles rectangles isocèles accolés par leur petit côté. ils forment quelque chose qui ressemble à un ruban de Moebius. Cet objet est déformable. On veut calculer la position 3D de chaque sommet, variable suivant les déformations, dans le but d'une représentation."

[minushabens]

pauvre dlzlogic. Il ne connaît pas la régression ordinaire et tu veux lui faire apprendre les glm... pourquoi pas le modèle mixte pendant qu'on y est?

[JPL]

Attention, si cela repart une fois de plus dans la polémique la discussion sera fermée.

[Evil.Saien]

Comme il ne me suffit pas de faire une affirmation, je dis pourquoi et je précise que cette méthode est approximative et contraire à l'obligation de résultat en matière de calcul. Eh oui, ce n'est pas "comme on veut". On n'utilise pas la méthode des moindres carrés au hasard, on sait exactement pourquoi.

Désolé, je pensais que c'était évident mais par "comme tu veux", il fallait entendre "comme tu l'entends selon tes critères". Comment pourrais-je les connaître...

La différence entre "résolution numérique" et "optimisation d'une erreur" est la même qu'entre "démonstration" et "hypothèse"

Loin de moi l'idée de vouloir polémiquer, mais bien généralement la résolution numérique d'une équation consiste ni plus ni moins à minimiser quelque chose (une erreur par exemple)...

Si on cherche X tels que MX=B, on peut par exemple chercher à minimiser (MX-B)^2...

Pour revenir à ton tout premier poste, tu n'as pas défini les inconnus et les paramètres alors c'est assez confus.

[Evil.Saien]

Perso, j'utiliserais ça :
https://fr.mathworks.com/help/optim/ug/fsolve.html

Et le problème serait réglé

[emmane]

Bonjour, j'avoue que je ne comprends pas : l'optimisation consiste à calculer la solution optimale (à savoir minimisant ou maximisant une variable), et pas la plus probable, puisqu'il n'a pas du tout de contexte probabiliste. Dans le contexte de la question posée en début de sujet, minushabens a proposé de trouver la solution minimisant la quantité (mg1-md1)^2+...+(mgN-mdN)^2, car c'est en effet la solution cherchée (solution du système d'équations réel mg1=md1 , ..., mgN=mdN). On pourrait bien sûr considérer |mg1-md1|+...+|mgN-mdN| avec des valeurs absolues à la place des carrés. Pour minimiser, on peut utiliser la méthode du gradient par exemple, c'est une méthode très connues. Mais comment sait-on qu'il n'y a qu'une seule solution au système d'équations du second degré ? c'est une hypothèse ?

[JPL]

Je constate que cette discussion est uniquement mathématique et ne tend pas à déboucher sur la programmation. Je la déplace donc dans le forum de maths.

[Dlzlogic]

Bonjour,
Je voudrais réactiver la question suivante :
http://forums.futura-sciences.com/ma...d-degre-2.html
Soit un système de N équations du second degré à N inconnues.
Par un moyen quelconque, on connait une solution approchée. Par "solution" on entend bien-sûr la valeur numérique approchée des N inconnues.
Il est évident qu'il existe un grand nombre de solutions, une seule nous intéresse.
Certains outils informatiques permettent de résoudre cela, volontairement, cette question est déposée dans le forum Maths.

Je précise certains points qui apparemment n'étaient pas clairs :
- il n'est pas question d'optimisation
- on peut traduire ce problème comme un calcul d'intersection de coniques.
- la solution numérique ne peut pas être exacte, puisque les valeurs concernées sont réelles.
- il s'agit de trouver une méthode et pas de donner un lien sur le site de je ne sais qui, qui saurait le faire.

Naturellement, dans la pratique, l'écriture du module pour faire ce calcul serait intéressant à informatiser, mais ce problème est tout à fait réalisable pour un système de 3 équations, donc dans un environnement 3D, avec une simple calculette.
Une fois le problème mathématiquement résolu, l'écriture du module informatique pour le généraliser à N équation serait intéressant.

[feanorel]

Ton problème s'écrit simplement sous forme matricielle x'A_ix = b_i pour i allant de 1 à n (équations).
En trouver une solution c'est exactement la même chose que de trouver un minimum de la fonction
somme des carrés des résidus


S'il y a une solution exacte à ton système d'équations le minimimum de E(x) est 0, et un argmin est solution exacte
du problème. E(x) étant différentiable il suffit effectivement d'appeler un algo d'optim différentiable en partant de
la solution approchée.

[Dlzlogic]

Bonjour feanorel,
Je n'ai pas très bien compris ta réponse.
Dans le cas général, un système du second degré admet un certain nombre de solutions, toutes aussi exactes les unes que les autres.
On pourrait imaginer de les calculer toutes et de choisir celle qui convient.
Par contre, je me place dans le cas où on connait une valeur approximative de la solution. Par approximatif, je veux dire suffisamment précise pour ne pas tomber sur la solution d'à côté, mais pas plus.

Pour éviter toute ambiguïté sur le terme "solution exacte", l'intersection de deux droites non parallèles a une solution unique et exacte, par contre le résultat étant constitué de nombres réels, même si on l'a obtenue par une formule exacte, celui-ci ne sera jamais qu'une valeur approchée de la valeur réelle.

Le cas le plus simple à mon problème est l'intersection d'un cercle et d'une droite dans le plan. Il y 2 équations et 2 inconnues X et Y, mais, dans le cas général, il y a 2 solutions, une seule présente de l'intérêt, elle est exacte mais on ne sait que donner une valeur approchée pour X et Y.

Je ne vais pas contredire cette affirmation : "En trouver une solution c'est exactement la même chose que de trouver un minimum de la fonction
somme des carrés des résidus", mais cela demanderait justification.

E(x) étant différentiable il suffit effectivement d'appeler un algo d'optim différentiable en partant de
la solution approchée.

J'ai bien précisé dans les hypothèses que ce calcul devait pouvoir être fait avec une simple calculette, au moins pour un système de 3 équations. Et que dans le cas général il ne devait fait appel à aucun module extérieur.