exercice racines de polynomes
Publié : mar. avr. 07, 2020 6:32 am
On se propose de trouver les racines approchées d'un polynome unitaire P de degré n à coefficients réels par un procédé d'homotopie. Soit Q le polynome Q=x^n-1, on considere le polynome
On connait les racines de P_0=Q. On discrétise ensuite le paramètre t en {0,h,2h,...,1} avec h=1/N, N assez grand et on calcule les racines approchées de P_h en effectuant une ou deux itérations de la méthode de Newton sur les racines de P_0, puis celles de P_(2*h) en effectuant une ou deux itérations de la méthode de Newton sur les racines de P_h, etc. jusqu'à obtenir une valeur approchée des racines de P_1=P.
Si P_t n'a pas de racines multiples, ce qui s'exprime par une condition sur le résultant de P_t et sa dérivée (en x), on peut suivre les racines de P_t le long de la discrétisation en t et obtenir des valeurs approchées des racines de Q.
S'il existe des réels t dans l'intervalle [0,1] tels que P_t a des racines multiples, on peut choisir de prendre t dans les complexes, par exemple selon les cotés non réels du triangle de sommets 0,1/2*(1+i),1.
L'exercice consiste à proposer un traitement mathématique, une illustration informatique, et une discussion sur la complexité de cette méthode (en fonction de n le degré du polynome et de N le pas de la discrétisation).
Code : Tout sélectionner
P_t:=t*P+(1-t)*Q
Si P_t n'a pas de racines multiples, ce qui s'exprime par une condition sur le résultant de P_t et sa dérivée (en x), on peut suivre les racines de P_t le long de la discrétisation en t et obtenir des valeurs approchées des racines de Q.
S'il existe des réels t dans l'intervalle [0,1] tels que P_t a des racines multiples, on peut choisir de prendre t dans les complexes, par exemple selon les cotés non réels du triangle de sommets 0,1/2*(1+i),1.
L'exercice consiste à proposer un traitement mathématique, une illustration informatique, et une discussion sur la complexité de cette méthode (en fonction de n le degré du polynome et de N le pas de la discrétisation).