Quantcast

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

classic Classic list List threaded Threaded
6 messages Options
Lucien Povy Lucien Povy
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

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


_______________________________________________
users-fr mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users-fr

mroots.sci (6K) Download Attachment
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Racines multiples d'un polynôme.

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]

_______________________________________________
users-fr mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users-fr
Lucien Povy Lucien Povy
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Racines multiples d'un polynôme.



Le 12/09/2015 18:38, Samuel Gougeon a écrit :
> p = poly(2:2:30,"x")
Bonjour,
Je rentre juste de voyage, et je suis surpris par votre résultat :
Voici ce que me donne la fonction mroots.sci  avec scilab 5.5.2 et linux.

-->mroots(p)
AVERTISSEMENT : The polynomial has only singles roots.
  ans  =

     2.
     4.
     6.
     8.
    10.
     12.
     14.
     16.000002
     17.999994
     20.00001
     21.999987
     24.000011
     25.999994
     28.000002
     30.
Le programme roots donne :
        -->roots(p)
  ans  =

     30.
     28.000002
     25.999994
     24.000011
     21.999987
     20.00001
     17.999994
     16.000002
     14.
     12.
    10.
     8.
     6.
     4.
     2.

  Execution done.

C'est normal d'obtenir la même réponse avec roots et mroots car il n'y a
que des racines simples et mroots n'utilise pas  dans ce cas, la
fonction bezout.sci qui est effectivement écrite en fortran (programme
de Serge Steer).
Cordialement
Lucien Povy
PS :
Mon fichier joint avec mon précédent courriel est peut être bogué ???
_______________________________________________
users-fr mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users-fr
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Racines multiples d'un polynôme.

Bonjour,

Le 13/09/2015 09:43, Lucien Povy a écrit :
> .../...
> PS : Mon fichier joint avec mon précédent courriel est peut être bogué
> ???
Pourriez-vous confirmer que, avec la version que vous avez postée le
28/8, vous obtenez bien le résultat posté hier?
J'utilise pour ma part Scilab 5.5.2 / MSWindows.

S. Gougeon

_______________________________________________
users-fr mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users-fr
Lucien Povy Lucien Povy
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Racines multiples d'un polynôme.



Le 13/09/2015 15:04, Samuel Gougeon a écrit :

> Bonjour,
>
> Le 13/09/2015 09:43, Lucien Povy a écrit :
>> .../...
>> PS : Mon fichier joint avec mon précédent courriel est peut être
>> bogué ???
> Pourriez-vous confirmer que, avec la version que vous avez postée le
> 28/8, vous obtenez bien le résultat posté hier?
> J'utilise pour ma part Scilab 5.5.2 / MSWindows.
>
> S. Gougeon
>
> _______________________________________________
> users-fr mailing list
> [hidden email]
> http://lists.scilab.org/mailman/listinfo/users-fr
>
Re-bonjour
Je confirme le résultat posté ce matin avec le programme posté le 28/8
cordialement.
L Povy
_______________________________________________
users-fr mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users-fr
Samuel GOUGEON Samuel GOUGEON
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Racines multiples d'un polynôme.

Bonjour,

Le 13/09/2015 16:15, Lucien Povy a écrit :
> Re-bonjour
> Je confirme le résultat posté ce matin avec le programme posté le 28/8

Après tests comparés sur Fedora, et analyse de mroots(), il s'avère que
le problème vient de bezout(), laquelle ne produit pas la même réponse
sous MSWindows et sous Linux.
Ce dysfonctionnement est maintenant documenté ici :
http://bugzilla.scilab.org/show_bug.cgi?id=14162

Samuel Gougeon

_______________________________________________
users-fr mailing list
[hidden email]
http://lists.scilab.org/mailman/listinfo/users-fr
Loading...