[Users-fr] Racines multiples d'un polynôme.

[Samuel Gougeon]

Bonjour,

Le 28/08/2015 14:11, Lucien Povy a écrit :
> Bonjour,
> Je propose un programme "mroots.sci" donnant les racines d'un polynôme 
> et les multiplicités correspondantes (ou les racines répétées autant 
> de fois qu'il faut).
> Contrairement à Matlab ou Octave, la méthode ne fait pas la moyenne 
> des racines qui semblent
> multiples (j'ai aussi programmé cette méthode, mais elle ne me 
> satisfait pas).
> L'idée est d'utiliser le programme bezout.sci sur le polynôme P(x) et 
> le polynôme dérivé dP(x)/dx.
> Ce programme peut être utile pour les fonctions scilab factors, 
> polfacts, trzeros, pfactors,.... etc, et moyennant une réécriture, de 
> règler en partie le problème posé par pfss.sci quand il y a des 
> racines multiples. Je donne en fichier attaché, le programme mroots.sci.
> Bien cordialement à tous.
> Lucien povy
.
Partageant votre insatisfaction concernant les seuls résultats bruts de 
roots(), laquelle ne permet pas d'accéder aux valeurs et multiplicités 
des éventuelles racines multiples, j'ai écrit en 2010 une première 
version de polyroots() retournant ces valeurs. J'ai retravaillé cette 
fonction au printemps dernier afin d'en améliorer les performances -- 
essentiellement lorsque l'écart entre les racines décroît --, et l'ai 
finalement publiée sur FileExchange en juin : 
http://fileexchange.scilab.org/toolboxes/362000, accompagnée d'une aide 
et d'exemples.

polyroots() est un post-traitement des racines brutes données par 
roots(). Elle met en oeuvre un algorithme d'agrégation.
A mon sens, le principal défaut en est la lenteur, dans la mesure où il 
s'agit d'une macro écrite en Scilab.
Lors de ce travail, j'ai recherché des références équivalentes en Matlab 
ou Octave, afin de comparer les performances, mais je n'ai rien trouvé. 
Si vous avez des références écrites en Matlab/Octave, je serais ravi 
d'en prendre connaissance.

Le problème de la détermination numérique des racines polynomiales est 
"inévitablement" frustrant, puisqu'il est soumis à une incertitude 
relative finale sur la valeur des racines croissant en %eps^(1/N), où N 
est le degré du polynôme traité. La méthode de résolution que vous 
proposez est-elle affranchie de cette contrainte ? Cela ne parait pas 
possible. Comme vous l'écrivez, mroots() est basée sur bezout(). 
Celle-ci n'est pas écrite en langage Scilab dans bezout.sci mais en 
Fortran (et c++) dans SCI\modules\polynomials\src\fortran\recbez.f et 
est compilée, ce qui en fait une fonction rapide, et du coup rend 
mroots() rapide. Le code de recbez.f est bien documenté, et les 
difficultés algorithmiques y sont évoquées.

Les premiers tests avec mroots() m'ont laissé enthousiaste, avant que 
des problèmes importants se manifestent, y compris sur des cas plutôt 
simples. Voir ci-dessous. Je vous laisse en explorer les causes et au 
mieux y remédier.

Quoi qu'il en soit, je pense comme vous que l'accès aux racines 
multiples pourraient/devraient être proposé dans Scilab, même si aucun 
algorithme ne peut en l'occurrence prétendre être absolument robuste et 
mener à des résultats toujours "exacts". A cette fin, roots() pourrait 
proposer de nouvelles options.

Bonne continuation
Cordialement
Samuel Gougeon
-------------
--> p = poly(2:2:30,"x")
  p  =
                                        2 3            4            
5            6            7
   - 4.285D+16 + 7.109D+16x - 5.051D+16x + 2.071D+16x - 5.544D+15x + 
1.034D+15x - 1.397D+14x + 1.399D+13x
                         8             9 10          11         12       
13     14  15
             - 1.051D+12x + 5.940D+10x - 2.514D+09x + 78393952x - 
1747200x + 26320x - 240x + x

--> mroots(p)
  ans  =
     16.
     16.
     16.
     16.
     16.
     16.
     16.
     16.
     16.
     16.
     16.
     16.
     16.
     16.
     16.

// On attend 2:2:30 == [ 2 4 6 8 ... 28 30]