Discussion :

[guitz]

Bonjour,

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

[wolinn]

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.

[guitz]

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

[dourouc05]

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.

[wiwaxia]

Bonjour,

Un polynôme à coefficients réels de degré (4): F(t) = A*t⁴ + B*t³ + C*t² + 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 - t₁)*(t - t₂)*(t - t₃)*(t - t₄) = A*(t² - S*t + P)*(t² - S'*t + P')
en posant: S = t₁ + t₂ ; P = t₁ * t₂ ; S' = t₃ + t₄ ; P' = t₃ * t₄ .

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*t³ + 3*B*t² + 2*C*t + D .
La racine cherchée est alors la limite de la suite rapidement convergente: t_k+1 = t_k - (F(t_k) / F'(t_k)) ;
il faut partir d'une valeur médiane t₀ = 0.5 , ou la calculer par interpolation: t₀ = F(0) / (F(0) - F(1)) .

[wolinn]

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).

[wiwaxia]

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)║² = 0 et finalement: S1(t)² + S2(t)² - 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*t⁴ + B*t³ + C*t² + 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)² s'effectue rapidement, par un procédé dichotomique.

[wiwaxia]

... 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
t_k - L ~ K/2^k .

[guitz]

...
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)

[wolinn]

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.

[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 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.

[wiwaxia]

... 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)│ <~ (F_max - F_min) , 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(t_k)*F(t_k+1) < 0 (encadrement du zéro);
b) 0.7 < (F(t_k+2) - F(t_k)) / (F(t_k+1) - F(t_k-1)) < 1.4 (dérivée de signe constant, et ne variant pas au-delà d'un rapport ~ 2).⁽¹⁾
2°) Lancement du procédé de Newton-Raphson.

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

[wiwaxia]

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(t_k)*F(t_k+1) < 0 (encadrement du zéro, avec 0 <= k < N);
b) 0.5 < (F(t_k+1) - F(t_med)) / (F(t_med) - F(t_k)) < 2 (écart de signe constant, et ne variant pas au-delà d'un rapport de 1 à 2 ;
l'abscisse médiane est: t_med = (t_k + t_k+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)

[guitz]

Merci