exercice racines de polynomes

Forum pour les étudiants de la préparation agreg option C de Grenoble

Modérateur : xcasadmin

parisse
Messages : 5344
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

exercice racines de polynomes

Message par parisse » 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

Code : Tout sélectionner

P_t:=t*P+(1-t)*Q
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).

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: exercice racines de polynomes

Message par megarbane » mer. avr. 08, 2020 9:52 am

J'ai un petit soucis avec mon algorithme : je pars des racines de Q, mais en itérant les méthodes de Newton je converge parfois vers la même racine de P... Je vais y réfléchir un peu plus pour le modifier et je t'enverrai ça quand j'aurai amélioré mon algo.

parisse
Messages : 5344
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice racines de polynomes

Message par parisse » mer. avr. 08, 2020 9:57 am

D'après mes quelques tests, il faut une discrétisation de pas assez fin, surtout si on prend un polynome aléatoire par défaut avec des coefficients entre -99 et 99 et donc des racines qui peuvent etre assez loin du cercle unité.
Dans ma session "corrigé" j'ai pris h=1/1000 et j'ai fait 3 itérations de Newton.

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: exercice racines de polynomes

Message par megarbane » mer. avr. 08, 2020 9:58 am

Juste pour être sûr de ne pas avoir fait d'erreur, mon programme est le suivant :

(où les notations sont les mêmes que l'énoncer, et j'ai rajouté un paramètre "p" pour le nombre d'itérations de Newton que je fais)

Code : Tout sélectionner

fonction Racines(P,n,N,x,p)
  local xn,j,k,v,h,Q,Pt,t,l;
  h:=1/N ;
  Q:=x^n-1;
  v:=seq(evalf(exp(2*i*k*pi/n),40),k,0,n-1);
  pour k de 0 jusque (N-1) faire
    t:=(k+1)/N;
    Pt:=t*P+(1-t)*Q;
    pour j de 0 jusque (n-1) faire
      pour l de 1 jusque p faire
        xn:=v[j];
        v[j] := -subst(Pt,x,xn)/subst(Pt',x,xn) + xn;
      fpour
    fpour;
  fpour;
  retourne v;
ffonction:;

megarbane
Messages : 21
Inscription : mer. mars 25, 2020 8:54 am

Re: exercice racines de polynomes

Message par megarbane » mer. avr. 08, 2020 10:00 am

Je commence un peu à fatiguer donc je vais m'arrêter là pour aujourd'hui, mais je vais peut-être poster des choses sur le forum dans la semaine (en reprenant un peu les deux problèmes).

A bientôt,
Thomas

parisse
Messages : 5344
Inscription : mar. déc. 20, 2005 4:02 pm
Contact :

Re: exercice racines de polynomes

Message par parisse » mer. avr. 08, 2020 10:14 am

J'ai rajouté la balise de code (boutons juste au-dessus: </>) pour rendre ton programme plus facile à lire.
Améliorations possibles:
* ne pas passer n en paramètre, n:=degree(P)
* calculer Pt' une seule fois et le mettre dans une variable, par exemple Pt1
* utiliser horner au lieu de subst (ca montre au jury qu'on connait l'algorithme pour evaluer un polynome en un point)
Je n'ai pas eu besoin d'utiliser 40 chiffres de précision dans evalf (peut-etre parce que j'ai juste testé avec un polynome de degré 4)
Il faut bien faire attention à ce qu'il n'y ait pas de racine multiple de Pt lorsque t parcourt [0,1], sinon pour t proche d'une valeur t0 ou Pt0 aurait une racine multiple, la méthode de Newton part en sucette.
N'hésite pas à discuter de l'exo pendant la semaine, je regarde le forum au moins une fois par jour.
à+!

Répondre