Système du second degré

[Dlzlogic]

Bonjour,
Je cherche à écrire un module qui calcule la solution d'un système de N équations du second degré à N inconnues.
Tout ce qui concerne la multiplicité éventuelle des solutions est hors-sujet, puisque on considère qu'on connait une valeur approchée de la solution.
Pas de souci pour l'aspect informatique.
La méthode par dichotomie est difficile à utiliser, puisque la solution est un ensemble de valeurs (ie un vecteur).
Je n'ai pas réussi à faire une approche basée sur la méthode de Newton.
Voila. Ca fait environ 3 semaines que je suis sur ce problème et là, je tourne en rond.
Pour être précis, si N = 3, alors une équation est de la forme générale :
ax² + bx + cy² + dy + ez² + fz + gxy + hxz + iyz + u =0
Dans la pratique, c'est à dire pour résoudre mon problème précis, N est de l"ordre de 10, avec quelques paramètres nuls, mais c'est sans grande importance.
Enfin, il n'y a ni simplification, ni astuce à chercher.

Merci d'avance.
-----

[leon1789]

Salut Dlzlogic

Je cherche à écrire un module qui calcule la solution d'un système de N équations du second degré à N inconnues.
Tout ce qui concerne la multiplicité éventuelle des solutions est hors-sujet, puisque on considère qu'on connait une valeur approchée de la solution.

Tu dis LA solution, tu es donc certain d'avoir une et une seule solution à ton système d'équations ? C'est donc un cas particulier, car si on considère simplement une équation du second degré à une inconnue (N=1), alors il peut y avoir 0,1 ou 2 solutions ... Avec N équations en N variables, c'est bien plus compliqué en général. Mais là, puisque tu parles de LA solution (existence et unicité), c'est que tu es dans un cas particulier que tu n'as pas précisé. Lequel est-ce ?

Pour être précis, si N = 3, alors une équation est de la forme générale :
ax² + bx + cy² + dy + ez² + fz + gxy + hxz + iyz + u =0

Tu veux résoudre cela : ax² + bx + cy² + dy + ez² + fz + gxy + hxz + iyz + u =0
Mais c'est l'équation d'une quadrique ( voir https://fr.wikipedia.org/wiki/Quadrique ) : qu'entends-tu par "résoudre cette équation" ?

la solution est un ensemble de valeurs (ie un vecteur)

Ne confondons pas "ensemble" et "vecteur" : ces sont deux notions bien précises et très différentes.

[leon1789]

Tu veux résoudre cela : ax² + bx + cy² + dy + ez² + fz + gxy + hxz + iyz + u =0
Mais c'est l'équation d'une quadrique ( voir https://fr.wikipedia.org/wiki/Quadrique ) : qu'entends-tu par "résoudre cette équation" ?

Je suis bête : tu as 3 équations de ce type, donc tu cherches l'intersection de 3 quadriques. Mais cela est relativement compliqué, et il est rare qu'il n'y ait qu'une et une seule solution...

[inviteb3412e7c]

Pourquoi ne pas utiliser "une méthode de gradient à pas" optimal ou non? Tu pose une fonction à N variables f à valeurs dans ou chaque composante est le carré du membre de gauche d'une équation. Tu auras donc le minimum de f qui est ta solution cherchée. Comme f étant clairement différentiable, tu peux appliquer la méthode.

[A voir en vidéo sur Futura]

[leon1789]

Pourquoi ne pas utiliser "une méthode de gradient à pas" optimal ou non?
Tu pose une fonction à N variables f à valeurs dans ou chaque composante est le carré du membre de gauche d'une équation. Tu auras donc le minimum de f qui est ta solution cherchée.

Tu parles du minimum d'une fonction f à valeur de : tu mets quel ordre sur pour parler du minimum (unique ?) de f ?

Tu dis << ta solution cherchée >> : comment sais-tu qu'il y a une et une seule solution ? En toute généralité, un système d'équations possède entre 0 et une infinité de solutions. Il faut donc se placer dans une situation restreinte pour parler de LA solution.

Comme f étant clairement différentiable, tu peux appliquer la méthode.

N'y a-t-il pas des conditions supplémentaires pour assurer la convergence vers une/la solution ?

[inviteb3412e7c]

Erf je me suis trompé, merci de me reprendre je ne devais pas être réveillé quand j'ai écrit cela. Effectivement la fonction f n'est pas dans mais dans et est défini par la somme des carrés des membres de gauches des équations considérées.

Après mon raisonnement se tient, le minimum de f est bien 0, f est différentiable, donc on applique une méthode de gradient à pas à partir de la valeur approchées de la solution cherchée en supposant qu'elle est suffisamment proche pour que tout se passe bien.

[leon1789]

Ok

partir de la valeur approchées de la solution cherchée en supposant qu'elle est suffisamment proche pour que tout se passe bien.

On est d'accord, il faut déjà connaitre une valeur suffisamment approchée d'une solution (celle que l'on vise, si on a choisi). Ce n'est pas rien comme hypothèse. Mais ce n'est pas tout : celle-ci doit être isolée dans l'ensemble des solutions.
Exemple sur l'intersection de trois quadriques : un cylindre x² + y² - 1 = 0, un cône x² + y² - z²= 0 , la sphère x² + y² + z² - 2 = 0
Tu proposes de considérer la fonction f (x,y,z) = (x² + y² - 1)² + (x² + y² - z²)² + (x² + y² + z² - 2)² dont le minimum est 0 (car l'intersection des trois quadrique n'est pas vide. Ici, c'est deux cercles...).
Visons la solution (1,1,1). Pour cela on peut prendre une première approximation comme (1.1, 1, 0.9) ? On risque de tomber sur une autre solution juste à coté, voire carrément diverger, non ?

[leon1789]

Visons la solution (1,1,1). Pour cela on peut prendre une première approximation comme (1.1, 1, 0.9) ? On risque de tomber sur une autre solution juste à coté, voire carrément diverger, non ?

Pardons, (1,1,1) n'est pas solution... Disons, visons la solution (1,0,1) : peut-on partir de triplet (1.1, 0, 0.9) en étant certain qu'on va tomber sur (1,0,1) ?

[inviteb3412e7c]

En fait, le gradient à pas permet d'atteindre un minimum local. Comme un minimum local est un bassin d'attraction, la méthode va converger dès qu'on se trouve dans le bassin d'attraction, c'est à dire près de la valeur cherchée.

Si on trouve un compact F dont la frontière est une ligne de niveau de f, si f atteint son maximum sur F sur la frontière, et si f admet un unique minimum local 0, alors on est sur que si on part de tout point de F on va obtenir la solution cherchée. Dans la pratique, il suffit de chercher un ensemble borné F où f est borné par un nombre suffisamment petit. A ce moment là la méthode est sure de converger.

[leon1789]

si f admet un unique minimum local 0

Ceci est aussi une hypothèse forte. C'est ce que je disais, il faut que la solution cherchée (visée) soit isolée des autres solutions (ce qui n'est pas vrai en toute généralité, confer mon exemple "intersection cercle, cône, cylindre").

Si on trouve un compact F dont la frontière est une ligne de niveau de f, si f atteint son maximum sur F sur la frontière, et si f admet un unique minimum local 0, alors on est sur que si on part de tout point de F on va obtenir la solution cherchée.

Tu as ajouté quelques hypothèses, ok, mais tu n'as pas peur des points où le gradient pourrait être le vecteur nul sans que l'on soit sur le minimum local 0 ?

[inviteb3412e7c]

Effectivement c'est un peu plus compliqué que je ne le pensais.

Si la solution n'est pas isolée, le problème est donc mal posé. Puis-ce qu'il y a une recherche à partir d'une solution approchée, on ne peut pas privilégier une solution plutôt qu'une autre sans informations supplémentaires sur la solution cherchée.

Le gradient nul ne pose pas de problème, car comme on travaille dans , soit on est à un minimum local et la méthode se termine, ou alors on a affaire à un point critique et il suffit de tester vecteurs formant une base pour continuer la méthode suivant le vecteur qui fait apparaitre une valeur inférieure à sur .

[leon1789]

ok.

On verra ce qu'il en est quand Dlzlogic repassera.

[inviteb3412e7c]

Oui attendons de voir ce qu'il en pense.

[azizovsky]

Bonjour, je crois qu'il faut d'abord réduire les formes quadratiques sous forme des somme de carrés (une représentation) si c'est possible avant d'attaquer le problème .