1. #1
    Membre confirmé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 590
    Points : 450
    Points
    450

    Par défaut Trouver une racine d'un polynôme de degré 4

    Bonjour,

    vous connaissez svp un bonne algo pour trouver une racine unique d'un polynôme de degré 4 ?

  2. #2
    Membre actif
    Homme Profil pro
    Ingénieur R&D
    Inscrit en
    mai 2016
    Messages
    84
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Ingénieur R&D
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2016
    Messages : 84
    Points : 262
    Points
    262

    Par défaut

    Un polynome de degré 4 à coefficients réels peut avoir 0, 1, 2, 3 ou 4 racines réelles.

    Voir ici pour une méthode :
    http://www.alain.be/Boece/degree4algo.html

    Après, il faut voir de quel problème provient cette équation, si elle est critique dans l'application, quels sont les ordres de grandeurs des coefficients, et éventuellement réécrire les formules un peu différemment pour améliorer la stabilité numérique et la robustesse si nécessaire.

  3. #3
    Membre confirmé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 590
    Points : 450
    Points
    450

    Par défaut

    Bonjour,

    un polynome de degré 4 peut avoir 4 racines mais mon polynome ne peut en avoir qu'un. En fait Je cherche à obtenir avec précision le point d'intersection de 2 splines quadratiques A et B

    A(s) = (1-s)²P0 + 2s(1-s)P1 + s²P2, s appartenant à [0, 1].
    B(t) = (1-t)²P3 + 2t(1-t)P4 + t²P5, t appartenant à [0, 1].

    Mes splines sont telle qu'il ne peut y avoir qu'une solution

    P0 ... P5 sont des vecteurs. Par méthodes de substitution et autres j'arrive à obtenir ce polynome :

    at^4 + bt^3 + ct² + dt + e = 0

    a,b,c,d,e sont des réels

    Merci pour ta réponse, c'est une grosse galère

  4. #4
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 501
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 501
    Points : 123 992
    Points
    123 992

    Par défaut

    Citation Envoyé par guitz Voir le message
    un polynome de degré 4 peut avoir 4 racines mais mon polynome ne peut en avoir qu'un.
    Qu'une seule solution… réelle (sans compter la multiplicité des solutions). Ça a parfois son importance pour certaines méthodes. Il existe des méthodes numériques spécifiques pour les polynômes (sinon, Newton-Raphson fonctionne pas mal, surtout vu que le calcul des dérivées est très facile), comme http://www.matematika.utm.my/index.p...ewFile/662/624.
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    501
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 501
    Points : 970
    Points
    970
    Billets dans le blog
    5

    Par défaut Trouver une racine d'un polynôme de degré 4

    Bonjour,

    Un polynôme à coefficients réels de degré (4): F(t) = A*t4 + B*t3 + C*t2 + D*t + E
    comporte toujours un nombre pair de racines réelles (0, 2 ou 4), parce qu'il est possible d'apparier les quatre zéros présents à partir de l'expression canonique:
    F(t) = A*(t - t1)*(t - t2)*(t - t3)*(t - t4) = A*(t2 - S*t + P)*(t2 - S'*t + P')
    en posant: S = t1 + t2 ; P = t1 * t2 ; S' = t3 + t4 ; P' = t3 * t4 .

    Que l'on soit assuré de l'existence d'une et une seule racine réelle sur [0 ; 1] implique simplement qu'il y en ait une (ou trois) autre(s) hors du domaine, donc dépourvue(s) de signification.

    La fonction F(t) s'annulant et changeant de signe sur [0 ; 1], il est possible de déterminer le point d'intersection du graphe y = F(t) avec l'axe des abscisses par encadrements successifs; la localisation est encore plus rapide si l'on assimile le graphe à sa tangente en un point d'abscisse (s), d'équation:
    y = F(s) + F'(s)*(t - s) , avec F'(t) = 4*A*t3 + 3*B*t2 + 2*C*t + D .
    La racine cherchée est alors la limite de la suite rapidement convergente: tk+1 = tk - (F(tk) / F'(tk)) ;
    il faut partir d'une valeur médiane t0 = 0.5 , ou la calculer par interpolation: t0 = F(0) / (F(0) - F(1)) .


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  6. #6
    Membre actif
    Homme Profil pro
    Ingénieur R&D
    Inscrit en
    mai 2016
    Messages
    84
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Ingénieur R&D
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2016
    Messages : 84
    Points : 262
    Points
    262

    Par défaut

    Attention quand même aux conditions de convergence et au choix du point de départ.
    A priori, la dérivée peut s'annuler, changer de signe, même au voisinage de la solution, ce qui correspond à des pathologies du problème géométrique (intersection tangente par exemple).

  7. #7
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    501
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 501
    Points : 970
    Points
    970
    Billets dans le blog
    5

    Par défaut Trouver une racine d'un polynôme de degré 4

    La recherche du point d'intersection dans le plan de deux splines du second ordre
    S1(s) = (1-s)².P0 + 2s*(1-s).P1 + s².P2, s appartenant à [0, 1] ,
    S2(t) = (1-t)².P3 + 2t*(1-t).P4 + t².P5, t appartenant à [0, 1] ,
    conduit effectivement à une équation de degré 4, mais par des calculs probablement très lourds,
    S1(t) = S2(t) impliquant S1(t) - S2(t) = 0 (vecteur nul) , soit encore:
    S1(t) - S2(t)║2 = 0 et finalement: S1(t)2 + S2(t)2 - 2*(S1(t)│S2(t)) = 0 ;
    cette dernière expression correspond (à un facteur près) au polynôme ordonné déjà envisagé: F(t) = A*t4 + B*t3 + C*t2 + D*t + E .

    Ne pourrait-on pas faire l'économie des derniers développements, en se limitant à l'expression du carré de la norme, pour l'écart entre les deux vecteurs initiaux:
    E(t) = S1(t) - S2(t) = (1-t)².(P0 - P3) + 2t*(1-t).(P1 - P4) + t².(P2 - P5) ?

    La recherche sur [0 ; 1] du zéro de la fonction G(t) = E(t)2 s'effectue rapidement, par un procédé dichotomique.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  8. #8
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    501
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 501
    Points : 970
    Points
    970
    Billets dans le blog
    5

    Par défaut Trouver une racine d'un polynôme de degré 4

    Citation Envoyé par wolinn Voir le message
    ... A priori, la dérivée peut s'annuler, changer de signe, même au voisinage de la solution, ce qui correspond à des pathologies du problème géométrique (intersection tangente par exemple).
    Il faut effectivement que la fonction soit monotone au voisinage de la valeur recherchée.
    Ce que l'on verra tout de suite si les courbes sont préalablement affichées; un prédécoupage du domaine (en dix intervalles, par exemple) permettra de contourner à peu de frais cette difficulté.

    La probabilité de quasi-superposition du point d'intersection (I) avec l'éventuel point singulier de l'une des splines est relativement faible;
    et dans le cas d'un raccordement tangent, la convergence du procédé vers sa limite (L) est assurée: la suite obtenue vérifie
    tk - L ~ K/2k .
    Nom : Splines [2017-11-23].png
Affichages : 86
Taille : 6,3 Ko


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  9. #9
    Membre confirmé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 590
    Points : 450
    Points
    450

    Par défaut

    Citation Envoyé par wiwaxia Voir le message
    ...
    S1(t) = S2(t) impliquant S1(t) - S2(t) = 0 (vecteur nul) , soit encore:...

    Bonjour wiwaxia,

    Tu ne peux écrire ça puisque les splines S11 S12 S21 S22 obtenues par subdivision (au point d'intersection), sont telles que S11 n'a pas forcément la meme longueur que S21, et idem pour S21 et S22.
    Donc il nous faut écrire : S1(t) = S2(s)

  10. #10
    Membre actif
    Homme Profil pro
    Ingénieur R&D
    Inscrit en
    mai 2016
    Messages
    84
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Ingénieur R&D
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : mai 2016
    Messages : 84
    Points : 262
    Points
    262

    Par défaut

    Citation Envoyé par wiwaxia Voir le message
    Il faut effectivement que la fonction soit monotone au voisinage de la valeur recherchée.
    Ce que l'on verra tout de suite si les courbes sont préalablement affichées; un prédécoupage du domaine (en dix intervalles, par exemple) permettra de contourner à peu de frais cette difficulté.
    ...
    C'est bien ce que je fais en pratique, tout en gardant à l'esprit que c'est un peu douteux mathématiquement (et numériquement).
    Pourquoi 10 plutôt que 100 ou 1000 ? On peut toujours construire des cas pathologiques.
    Après tout dépend de l'application et de la robustesse recherchée. Il peut être acceptable que l'algorithme échoue une fois sur 1000 parce qu'on souhaite privilégier la vitesse.
    Ou on peut souhaiter garder une méthode simple sans gérer les pathologies, pour cause de limitation de mémoire, si on programme un micro-controleur par exemple.
    (on ne laisse pas le programme planter évidemment, mais on lui permet de retourner la réponse "intersection non trouvée". On sait que l'intersection existe mathématiquement, mais le programme a échoué à la trouver).
    Mais si on veut vraiment une méthode sans échec, il faut aller un peu plus loin dans l'analyse.

  11. #11
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    501
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 501
    Points : 970
    Points
    970
    Billets dans le blog
    5

    Par défaut Trouver une racine d'un polynôme de degré 4

    Citation Envoyé par guitz Voir le message
    ... Tu ne peux écrire ça puisque les splines S11 S12 S21 S22 obtenues par subdivision (au point d'intersection), sont telles que S11 n'a pas forcément la même longueur que S21, et idem pour S21 et S22.
    Donc il nous faut écrire : S1(t) = S2(s)
    Je me demandais depuis un moment comment (I) pouvait se situer au "milieu" de l'une des courbes, et vers une extrémité de l'autre. Je me suis effectivement fourvoyé, et une simplification des calculs en amont n'apparaît guère possible.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  12. #12
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    501
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 501
    Points : 970
    Points
    970
    Billets dans le blog
    5

    Par défaut Trouver une racine d'un polynôme de degré 4

    Citation Envoyé par wolinn Voir le message
    ... Mais si on veut vraiment une méthode sans échec, il faut aller un peu plus loin dans l'analyse.
    Sur le principe, oui. Mais faut-il absolument parer à des éventualités que l'on ne rencontrera pas ?

    Il s'agit ici de répondre à un problème particulier, dont l'énoncé est suffisamment restrictif pour exclure les difficultés habituellement rencontrées.

    a) Il y a une racine sur le domaine [0 ; 1], ce qui assure le succès de procédés mêmes rudimentaires (par dichotomie ou recours à la sécante), du fait de la continuité du polynôme étudié F(t);

    b) La solution est unique, et correspond par conséquent à la limite de toute suite convergente visant la recherche du zéro (sécante, Newton), vérifiant F(L) = 0 , et dont les valeurs appartiennent au domaine considéré; on ne trouve pas non plus d'"intersection tangente", qui correspondrait à une racine double.
    Et quand bien même l'énoncé serait à prendre d'une manière moins stricte (il n'y a pas plusieurs racines distinctes sur [0 ; 1]), il n'en découle aucune complication.
    Les réserves exprimées
    ... c'est un peu douteux mathématiquement (et numériquement)
    relèvent de scrupules inutiles.

    c) Il intervient par ailleurs des splines du second ordre, pour lesquelles les coordonnées des points sont fonctions paraboliques des paramètres (s) ou (t); on n'y trouve (malheureusement ?) aucune de ces singularités qui font les délices des amateurs: auto-intersections, points de rebroussement, boucles, sinusoïtés, etc ... À cet égard, je me suis fait piéger par le logiciel de dessin (#8), raison pour laquelle l'image a été modifiée.
    Conséquences: les variations du polynôme F(t) sont relativement lentes sur [0 ; 1], au sens où la valeur de la dérivée en tout point de ce domaine vérifie │F'(t)│ <~ (Fmax - Fmin) , et son signe change une seule fois, tout au plus.
    ... On peut toujours construire des cas pathologiques ...
    Oh mais sûrement, en y mettant le paquet, avec des splines d'ordre 3 ou 4 ... mais ce n'est pas possible dans le cas présent.

    Le découpage en 10 sous-domaines (ou même en 5), qui n'est qu'une mise en route du procédé par dichotomie, suffira pour le choix de la valeur initiale.

    L'idée d'éviter le plantage du programme (mettant en oeuvre le procédé de Newton, ou l'une de ses variantes) est en soi pertinente; cette protection pourrait être installée en début d'un programme présentant deux parties:
    1°) Localisation d'un domaine suffisamment étroit à partir de bornes régulièrement espacées, vérifiant:
    a) F(tk)*F(tk+1) < 0 (encadrement du zéro);
    b) 0.7 < (F(tk+2) - F(tk)) / (F(tk+1) - F(tk-1)) < 1.4 (dérivée de signe constant, et ne variant pas au-delà d'un rapport ~ 2).(1)
    2°) Lancement du procédé de Newton-Raphson.

    (1) Les limites sont trop larges, et les conditions à simplifier; mais c'est un détail.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #13
    Membre éprouvé

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    501
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 71
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 501
    Points : 970
    Points
    970
    Billets dans le blog
    5

    Par défaut Trouver une racine d'un polynôme de degré 4

    J'ai repris le dernier paragraphe, qui me paraissait inutilement compliqué:
    1°) Localisation d'un domaine suffisamment étroit à partir de (N + 1) bornes régulièrement espacées, vérifiant:
    a) F(tk)*F(tk+1) < 0 (encadrement du zéro, avec 0 <= k < N);
    b) 0.5 < (F(tk+1) - F(tmed)) / (F(tmed) - F(tk)) < 2 (écart de signe constant, et ne variant pas au-delà d'un rapport de 1 à 2 ;
    l'abscisse médiane est: tmed = (tk + tk+1)/2.
    En complément du document de haut niveau (il faut s'accrocher !) pointé par dourouc05, quelques liens utiles:

    # Algorithme de recherche d'un zéro d'une fonction

    # Méthode de dichotomie
    # Méthode de la sécante
    # Méthode de Newton

    # Zéros d'une fonction
    # Zéros des fonctions

    # MathWorld
    - Root
    - Root-Finding Algorithm (liste de liens)


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  14. #14
    Membre confirmé Avatar de guitz
    Homme Profil pro
    Webdesigner
    Inscrit en
    juillet 2006
    Messages
    590
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Webdesigner

    Informations forums :
    Inscription : juillet 2006
    Messages : 590
    Points : 450
    Points
    450

    Par défaut

    Merci

Discussions similaires

  1. Réponses: 2
    Dernier message: 29/12/2016, 01h41
  2. [Débutant] Trouver une racine par dichotomie
    Par Wenneguen dans le forum MATLAB
    Réponses: 1
    Dernier message: 14/12/2014, 19h53
  3. Racines d'un polynôme du 5ème degré
    Par spithi dans le forum Pascal
    Réponses: 2
    Dernier message: 05/12/2006, 21h11
  4. [CR] trouver une bonne doc
    Par ina dans le forum SAP Crystal Reports
    Réponses: 1
    Dernier message: 17/06/2004, 18h43
  5. Réponses: 3
    Dernier message: 21/01/2004, 09h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo