Système d'équations non linéaires

[Médiat]

Bonjour,

Quelqu'un pourrait-il m'aider à trouver une solution dans au système suivant :



Merci d'avance ...
-----

[inviteaf1870ed]

J'imagine que c'est lié à ton article sur les quaternions, et que ça décrit un quaternion unitaire ?

[Médiat]

J'imagine que c'est lié à ton article sur les quaternions, et que ça décrit un quaternion unitaire ?

Pas exactement, mais pas loin, en fait je cherche à démontrer que si A est la -algèbre engendrée par un élément tel que , alors la -algèbre engendrée par e et i (i n'appartenant pas à A et tel que ) est isomorphe à la -algèbre engendrée par un élément tel que .

Le calcul précédent correspond au cas n = 3 (pour n=1 et n=2, c'est facile), avec quelques simplifications.

Toutes les -algèbres considérées sont associatives et commutatives.

[invite986312212]

bonsoir,

je ne sais pas résoudre cette équation, mais avec un programme de minimisation, ça prend moins d'une seconde pour trouver une solution approchée, par exemple celle-ci : 0.1802400 -0.2126075 0.3181896 -0.9061274

malheureusement ces nombres ne me disent rien.

[A voir en vidéo sur Futura]

[Médiat]

Bonjour,

Merci, le fait qu'ils existent est déjà une bonne indication

[SULREN]

Bonjour,
Désolé de faire du déterrage de discussion …..aussi profond dans le temps. En voici les raisons.

Depuis que je suis à la retraite mes « bricolages » m’ont amené à devoir résoudre des systèmes d’équations non-linéaires.
Comme je n’avais pas d’outils logiciels pour le faire, je m’en suis créé un petit, de type « agricole », qui m’a permis jusqu’ici de toujours m’en sortir, mais qui n’est pas l’idéal et qui un jour, dans un cas tordu, pourrait me laisser sur le bord du chemin.
Une discussion récente sur ce forum, sur la résolution d’une « équation avec des racines cubiques», m’a poussé à utiliser la fonction recherche.

Je suis tombé sur le problème ci-dessus posé par Médiat en 2011 et je m’en suis servi pour dérouiller ma « batteuse », qui n’avait pas servi depuis quelques temps.
Elle m’a trouvé 6 solutions dans la plage {-1, +1} pour chaque inconnue.

En voici une, qui donne au résultat des équations une précision absolue meilleure que 3 10^-7
a = -0,9061273932
b= -0,3181895912
c= -0,2126076072
d= -0,1802400053
Les autres solutions ont exactement les mêmes valeurs numériques en valeur absolue, mais affectées différemment aux inconnues, et parfois avec le signe +.

Mediat a dû résoudre son problème depuis bien longtemps.
Mon intervention n’a donc pour but que les questions suivantes:
- Quels algorithmes doit on utiliser pour résoudre ces systèmes d’équations non linéaires, quand on n'y parvient pas par la méthode analytique. Pour une équation unique on connait l’algorithme de Newton, la méthode par dichotomie, etc. Mais pour un système ?
- Les méthodes numériques permettent bien sûr d’en venir à bout. Mais sur quels outils, si possible pas trop chers, tournent elles ? Matlab ? Scilab ? …… ?

Merci d’avance pour vos éclaircissements.

[invite9dc7b526]

une solution "bourrine" consiste à minimiser la somme des carrés des écarts : tu écris chaque équation sous la forme "quelque-chose = 0" et tu minimises la somme des "quelque-chose" au carré. Je fais parfois comme ça parce que j'ai à ma disposition un programme de minimisation efficace (qui vient avec le logiciel R).

[invite6710ed20]

Bonjour
Pour répondre à Sulren -

Quels algorithmes doit on utiliser pour résoudre ces systèmes d’équations non linéaires, quand on n'y parvient pas par la méthode analytique. Pour une équation unique on connait l’algorithme de Newton, la méthode par dichotomie, etc. Mais pour un système ?

Pour un système il y a l'équivalent de la méthode de Newton. C'est à dire la méthode de Newton-Raphson. Le principe est le même:

Soit (F assez régulière) . Formellement le système s'écrit On cherche une approximation numérique d'une solution notée A.

Si X_0 est une valeur approchée. On pose donc

Donc c'est à dire. et on recommence avec

D'où la suite


On retrouve bien sûr les mêmes avantages et inconvénients de la méthode de Newton. En particulier cela ne permet pas de connaître toutes les solutions. Pour cela une analyse est nécessaire.
La convergence est rapide.
Il faut pouvoir calculer la matrice Jacobienne et surtout son inverse. Maintenant il y a des variantes comme dans le cas 1-dimensionnel pour ne pas la calculer.

Quant au logiciel Matlab ou Scilab c'est pareil du point de vue numérique.
Pour le problème ici, pour faire vite j'utiliserai un logiciel de calcul formel (Xcas, Mathematica, Mapple) pour calculer la matrice Jacobienne )

[invite6710ed20]

Rebonjour
Je ne suis pas tout à fait d'accord avec les propositions précédentes. En effet j'ai vérifié les solutions proposées et ce ne sont pas des solutions.
Si on remplace l'équation initiale F(X)=0 par un problème de minimisation, peut être que les solutions obtenues sont bien des minimums d'une certaine fonctionnelle (que je ne connais pas puisque elle n'a pas été donnée) mais ou bien la fonctionnelle n'est pas correcte ou bien le minimum recherché doit valoir 0 et ce n'est peut être pas le cas. Pouvez vous vérifier?
Pour ma part je conjecture qu'il n'y a pas de solution. En effet j'ai appliqué la méthode de Newton comme je l'ai expliqué dans un post précédent et elle ne converge pas. En général (i.e dans la pratique) même si on part de loin (i.e X_0 n'est pas proche de A) la méthode converge toujours vers une solution.
D'où ma conjecture.

[SULREN]

Bonjour,

Merci pour vos réponses à mes questions.
Je vais essayer d’écrire un programme mettant en oeuvre l’algorithme de Newton-Raphson pour remplacer mon programme actuel, type force brute, écrit sur un coin de table un jour pour résoudre une système et que je n’ai fait qu’améliorer un peu depuis, sans reprendre la réflexion à la base.
Son principal défaut est son temps d’exécution qui croît bien sûr exponentiellement avec la résolution demandée. J'arrive à le réduire par des astuces, mais cela ne vaut pas un algorithme à convergence rapide.

@JB2017 : à votre remarque sur le fait que les solutions que Invite986312312 et moi-même avons proposées ne sont pas de vraies solutions, mais juste la minimisation d’un certain critère, je ne peux que répondre :
- Que je n’ai pas un niveau suffisant pour entrer valablement dans cette discussion.
- Mais que j’apprécie votre remarque, car ma formation d’ingénieur m’a amené à considérer peut-être un peu vite qu’un jeu de valeurs des inconnues était une solution parce qu’il donnait aux quatre équations du système posé une valeur extrêmement proches de 0.

Avec :
a= -0,906127393246
b= -0,318189591169
c= -0,212607562542
d= -0,180239975452

On arrive à :
F1 = -1,0688 E-07
F2 = -9,75815 E-08
F3= -1,32935 E-8
F4= 3,91559 E-9

Pour un ingénieur ces valeurs peuvent être considérées comme égales à 0, mais en toute rigueur ce n’est pas 0. Je l’admets.

[invite6710ed20]

Rebonjour
Non @SULREN je ne crois pas que tu m'a compris.
Je précise mon propos. On a un système non linéaire de 4 équations à 4 inconnues. A priori on ne sait pas si il y a des solutions ou pas.
Pour en avoir une idée nous mettons en oeuvre une méthode numérique qui ne sont pas les mêmes. Pour l'instant là n'est pas le problème.

Une solution numérique (s'il y a des solution) est une valeur approchée de la (ou une) solution mais pas une valeur exacte. Là on est d'accord et ce n'est pas là n'est pas le problème.

Ce que je veux dire c'est que la solution approchée que vous fournissez est :
a0 = -0.9061273932
b0 = -0.3181895912
c0 = -0.2126076072
d0 = -0.1802400 et
et quand je vérifie je trouve F(a_0,b_0,c_0,d_0)={-7.91052*10^-8, -1.59109*10^-7, 0.112085, 1.57716} (qui n'est pas proche de 0.)
avec F(a,b,c,d)={-1 + a^2 + b^2 + c^2 + d^2, a b - a c - b d - c d,
b^2 - c^2 + 2 (-a c + a d + b d), a^2 - d^2 + 2 (a b + b c + c d)} qui correspond au système donné.

Tandis que vous vous arrivez à
On arrive à :
F1 = -1,0688 E-07
F2 = -9,75815 E-08
F3= -1,32935 E-8
F4= 3,91559 E-9

ce que je ne retrouve pas et pourtant j'ai bien pris votre solution et le système de départ. C'est là qu'est le problème.
Donc pensant que vous avez fait une erreur j'ai essayé d'interpréter l'erreur mais je ne peux rien dire de plus car il me manque des éléments.
Pour être sûr il faut donc remplacer votre solution dans F et on doit trouver quelque chose proche de (0,0,0,0).
Là il s'agit de (re)vérifier simplement, je ne comprends pas la différence. Moi, j'ai vérifié 2 fois. Je peux me tromper mais j'ai tout écrit ici.
Es-tu sûr du F3 et F4?

Maintenant j'emploie une méthode différente, bien connu mais qui ne converge pas. Donc nous avons des résultats différents.
Simplement quelqu'un a fait une erreur. Il faut se mettre d'accord.

En conclusion, il s'agit ici de revérifier si votre solution donnée vérifie bien l'équation. Ou alors je me suis trompé mais j'ai donné la fonction F et vérifié 2 fois.

[SULREN]

Bonjour,
JB2017, si notre désaccord ne porte que sur l’application numérique nous devrions vite trouver d’où il provient.

Tu as écrit :
"avec F(a,b,c,d)={-1 + a^2 + b^2 + c^2 + d^2, a b - a c - b d - c d,
b^2 - c^2 + 2 (-a c + a d + b d), a^2 - d^2 + 2 (a b + b c + c d)} qui correspond au système donné".

Ce qui ne correspond pas au système de départ, qui est :
F(a,b,c,d)={-1 + a^2 + b^2 + c^2 + d^2, a b - a c - b d - c d,
b^2 - c^2 - 2 (-a c + a d + b d), a^2 - d^2 - 2 (a b + b c + c d)}.

Il y a un signe moins sur le 3eme terme de F3 et de F4.

En rentrant les valeurs :
a= -0,906127393246
b= -0,318189591169
c= -0,212607562542
d= -0,180239975452

Je trouve bien dans Excel (je pourrais joindre le fichier si nécessaire).
F1 = -1,0688 E-7
F2 = -9,75815 E-8
F3 = -1,32935 E-8
F4 = +3,91559 E-9

Excel travaille en double précision. C’est la calculette la plus précise que j’aie pu trouver jusqu’à présent.
Mon programme de recherche de solutions trouve aussi les mêmes valeurs.

[invite6710ed20]

@Bonjour Oui tout à fait d'accord. J'ai dû être aveugle.
J'ai vérifié, tu donnes bien une solution. Remarque si X0 est solution -X0 est solution.
En voici d'autres
{0.0746578, 0.51328, -0.768178, -0.37533}

{0.37533, -0.768178, -0.51328, 0.0746578}

{-0.212608, -0.906127, 0.18024, -0.31819}

{0.18024, -0.212608, 0.31819, -0.906127}

{0.51328, -0.37533, 0.0746578, 0.768178}

[invite6710ed20]

D'autre part je ne savais pas que l'on pouvait résoudre un tel système avec excel.
Pour moi excel est un tableur et je ne le voyais pas comme un logiciel de calcul numérique.
Mais le programme n'est pas tout fait avec excel?

[SULREN]

Re,
C’est classique. On fait plusieurs vérifications et chaque fois on passe sur l’erreur sans la voir.

En fait, seulement dans l’intervalle {-1 ; +1 } je trouve, comme je l’ai dit dans un post plus haut, 6 solutions basées sur les valeurs :
a= 0,906127393246
b= 0,318189591169
c= 0,212607562542
d= 0,180239975452

{+c, +a, -d, +b} ; {+d, -c, +b, -a} ; {-d, +c, -b, +a} ; {-c, -a, +d, -b} ; {-b, -d, -a, +c} ; {-a, -b, -c, -d}

Dans le système posé, avec la symétrie dans les équations et la présence de carrés il est normal que –Xo soit solution si Xo est solution.

Si on élargit l’intervalle balayé par les inconnues on doit trouver une foule d’autres solutions approchées, mais peut-être aucune solution rigoureuse au sens mathématique.

Par exemple si on considère le système ultra simple :
y= x^2 + 0,000001 (la parabole décalée vers le haut d’un pouillème.
y= - x^2 (la parabole inversée)

On l’écrit :
y - x^2 - 0,000001 =0
y+ x^2 =0
La recherche numérique (dont ma «bidouille ») va donner y=0 , x=0 comme solution, avec une approximation de 0,000001 , alors que le système n’a pas de solution exacte, mathématique. Les deux paraboles ne se coupent pas.
Voilà pourquoi j’avais pris très au sérieux la remarque de ton post # 9.

Mais j’ai failli en tirer une conclusion erronée….. fatale.
J’en avais déduit que l’algorithme de Newton ne convergeait peut-être que vers les solutions exactes et pas vers les solutions approchées, donc qu’il n’était pas approprié à mes besoins.

En effet, hormis dans les cas d’exercice de style comme dans la présente discussion, je n’ai à résoudre des équations non linéaires que pour des réalisations pratiques et les solutions approchées me conviennent très bien, même avec des approximations de seulement 10^-2.

La continuation de notre discussion, suite à une erreur de signe, aura au moins eu le mérite de tirer cela au clair.

[SULREN]

Re,
@ JB2017 qui a écrit:

D'autre part je ne savais pas que l'on pouvait résoudre un tel système avec excel.
Pour moi excel est un tableur et je ne le voyais pas comme un logiciel de calcul numérique.
Mais le programme n'est pas tout fait avec excel?

Dans la résolution des systèmes d’équations je n’utilise Excel que comme calculette de vérification des résultats, en partant du principe que les résultats calculés par un outil (i.e. mon « programme » ; on dit plutôt « code » aujourd’hui) doivent être vérifiés sur un outil différent, afin d’éviter les erreurs de mode commun.
J’ai entendu dire (mais est-ce la réalité ?), que les systèmes de commande de la Navette Spatiale étaient redondants, ce qui est un minimum du point de vue de la sécurité, mais que de plus, les redondances étaient réalisées par des calculateurs de marques différentes, avec des programmes conçus par des équipes d’analystes différentes, et écrits dans des langages différents. Il fallait cela pour éviter les pannes de mode commun.

Ce n’est pas Excel, mais un bout de code que j’ai écrit, qui recherche les solutions.
J’ai décidé d’utiliser la méthode de bourrin, « la force brute », déjà parce qu’elle me sied très bien , et aussi pour être sûr de ne rater aucune solution.

Mon intérêt pour la force brute est né en 2005.
Je suis passionné d’horlogerie et aussi d’horloges astronomiques. En 2005 j’ai voulu vérifier les trains de rouages des horloges astronomiques dont j’avais les schémas, en particulier celle de Strasbourg.
Son créateur, ce génie de Jean Baptiste Schwilgué, calculait par la méthode des fractions continues, les trains d’engrenages devant réaliser des rapports de transmission extrêmement précis (10^-6, voire 10^-9 en précision relative).
Il existait une autre méthode de calcul de ces trains, élaborée par l’horloger Achille Brocot, mathématicien à ses heures, et qu’il destinait à ses collègues horlogers non matheux, mais sachant quand même utiliser les quatre opérations de base : +, -, :, x .

J’ai eu l’impression que ces deux méthodes pouvaient rater des solutions et j’ai donc vérifié tout cela par la force brute, qui ne peut rien rater, mais dont le temps d’exécution est malheureusement exponentiel en fonction de la précision visée. On peut le réduire par des astuces d’analyse.
De même, j’ai craint que l’algorithme de Newton puisse rater des solutions.

[invite6710ed20]

Bonsoir

@Sulren Je suis d'accord avec ce que tu dis.
Le code ne me dit pas la méthode que tu utilises. A mon avis cela doit être une méthode de minimisation. C'est à dire que (ce que je pense)
l'équation initiale F(X)=0 est transformée par une fonctionnelle à minimiser. Comme par exemple J(X)=<F(X),F(X)>. Ici J(X)=0 ssi F(X)=0.
L'inconvénient c'est que tu peux trouver un minimum local qui ne sera pas J(X)=0. Ensuite on emploi souvent une méthode du gradient ou un équivalent.
De toute façon quelque soit la méthode, il y un principe commun général qui consiste à créer une suite qui converge vers la solution et l'on s'arrête par exemple quand 2 valeurs consécutives sont proches où mieux quand le résidu (i.E F(x) ou J(X) ) en norme est plus petit que la
précision souhaitée.
Il faut savoir que la méthode de Newton Raphson est très rapide 6 ou 7 itération donne la précision maximale. L'algo me trouve une solution en une fraction de seconde.

Maintenant quand on veut obtenir toutes les solutions on fait un balayage de la zone cherchée. C'est à dire comme ici le domaine des solutions possibles est [-1,1]^4. Donc je fais un quadrillage de cette zone et pour chaque extrémité du quadrillage je choisi une valeur initiale qui va converger (en général ) vers une solution ou une autre. Si la solution a déjà été obtenue je ne la garde pas. Il y a peu de chance qu'une solution échappe.

Pour conclure sur ce post, je dirai que tout ce qui est dit ci-dessus doit malgré tout être associé à une analyse car effectivement on peut penser avoir une solution qi est fausse comme dans l'exemple que tu as cité.

Ha, oui, j'ai cherché toutes les solutions mais je n'en ai trouvé que 2 modulo les permutations et change de signe. les voici

{0.9061274463528878`, 0.31818964514320847`, 0.2126075236918141`, \
0.18023995550173696`}


{-0.0746578340503426`, -0.5132799671593368`, 0.7681777567114163`, \
0.37533027751786524`}

[SULREN]

Bonjour,

@JB2017
Merci pour ces informations et la qualité de ton aide tout au long de cette discussion.

Il n’y a pour moi aussi que deux solutions dans l’intervalle {-1 , +1}, qui se déclinent chacune en 8 combinaisons (d’affectation aux inconnues et de signe), donc 16 au total.
Lors de ma première analyse je n’en avais vu que 6 parce que mon code n’en conservait pas plus. Dans les problèmes que j’ai traités jusqu’à présent il n’y a jamais eu « mise bas d’une portée aussi nombreuse de solutions » et j’avais oublié cette limite.

La méthode Newton Raphton converge en effet de façon quadratique. Elle est ultra rapide.
Et la précision atteinte est impressionnante. On approche le 0 du second membre à mieux de 10^-15, avec les chiffres que tu as donnés. C’est à la limite des possibilités de Excel pour vérifier les résultats.

Je vais m’efforcer de l’utiliser.
Il faudra peut-être que j’abandonne le langage de programmation que j’utilise depuis 2005, pas créé pour le calcul scientifique (PureBasic). C’est celui qui correspondait le mieux à mes critères de choix de époque, dont : la possibilité d’acheter une licence à vie pour pas cher, la grande vitesse d’exécution, les énormes possibilités graphiques……
Ce serait l’occasion de revenir au Fortran de mes origines, mais en up-to-date version.
(Je programmais en Fortran IV dans les années 1960, pendant mes études…… et on résolvait encore les systèmes d’équations différentielles sur une calculatrice analogique, basée sur des amplificateurs opérationnels,…… machine de légende dont je garde un excellent souvenir).

[invite6710ed20]

@ sulren Le fortan, C++ tout cela c'est bien, j'en ai fait un peu mais comme je ne pratique pas beaucoup cela me demanderait un gros travail à faire pour ma petite utilisation personnelle.
Tout dépend de ce que l'on veut faire. Quand on ne travaille pas sur de gros projet un peu comme ici on peut utiliser Scilab (un équivalent de Matlab mais gratuit) pour le calcul numérique.

Mais on peut aussi utiliser un logiciel de calcul Formel (ce que j'ai fait ici ) car cela m'a permis de calculer la matrice Jacobienne et son inverse sans me fatiguer.

[SULREN]

Bonjour,

JB2017, je ne cherche pas à réinventer la roue à tous les détours de chemins.

Mais je tiens à garder la main en programmation pour plusieurs raisons :
- Avec des microprocesseurs comme Arduino on peut réaliser des choses utiles : commande des axes de sa petite machine d’usinage multifonctions, surveillance périmétrique astucieuse de sa propriété, etc
- J’ai pu créer des outils sur PC que je ne trouvais pas sur le marché, en tous cas pas dans la forme qui me convenait, comme le calcul de trains d’engrenages réalisant un rapport de transmission extrêmement précis. Quelques dizaines de lignes de code. Je l’ai beaucoup utilisé, y compris pour aider autrui (Usineux qui voulaient réaliser des filetages spéciaux sur leur tour, concepteurs d’horloges à complications, etc).
- J’ai pu créer des fonctionnalités qui existent dans des logiciels du marché, mais ceux-ci coûtent cher et nécessitent une longue période de formation, tels que Solideworks, Tellwatch, etc.
Ex : génération de profil d’engrenages en développante, en introduisant le module, le nombre de dents et la valeur du déport de denture s’il y a lieu, de profils d’engrenages épicycloïdaux. C’était pour réaliser des fly-cutters d’usinage de ces engrenages, ou simplement pour identifier une denture à partir d’une photo dans le cas de pièces à remplacer (cas posés sur des forums d’usinage).

Il y a aussi l’aspect intellectuel : avant de « pisser » du code, comme on dit, il faut faire l’analyse de son problème, chercher l’algorithme, optimiser l’exécution, penser au debuggage. Cela vaut largement les Sodoku dont les retraités sont friands, tant ils craignent Alzheimer.

Il ne faut pas perdre de vue non plus qu’il existe des bibliothèques de codes où on peut piocher les briques qu’on a pas envie de créer soi-même : « vous voulez du Runge Kutta, de la recherche d’extremum, du Newton, telle routine ou tel utilitaire graphique,……voici, il n’y a qu’à copier le code ».

Dans le cas de notre sujet, j’ai déjà une bidouille pour traiter les rares cas qui se présentent à moi. Aller vers Newton Raphton est plus une bonne occasion de faire les choses bien, et de réviser certaines notions…..si ce n’est pas déjà trop tard ?

NB : Pour la petite histoire cette bidouille a vu le jour pour les besoins d’une discussion passionnée sur un forum d’astronomie, à propos du calendrier et de la recherche des années exceptionnelles où l’épacte augmenterait de 13 jours : conjonction du Nombre d’Or à 1, de l’équation solaire (métempose) et de l’équation lunaire (proemptose.
J’ai trouvé les années: 15 200, 38 000, 60 800 etc ….. avec une périodicité de 22 800 ans.

La bidouille a progressivement évolué, jusqu’à me servir à la résolution de systèmes d’équations.