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]

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

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

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