TPs Calcul Numérique

VII.1 - Méthode De Graeffe

Objectif : Recherche d'une racine d'un polynôme

On considère un polynôme P_n(x) de degré n et possède n racines distinctes.

n

P_n(x) = > a)xⁿ⁶⁾

t=o

On a si les racines sont éloignées (i. e|r₁ | z |r₂ | z z |r₃ |) on

peut les calculer de manière approchée comme suit : r) { - (@

ai_1 ; j: 1, 2

Le but de cette méthode est de rendre les racines distinctes non- éloignés en des racines éloignées par la multiplication de f(x) par f (-x)

On a P(x) = (x - a₁)(x - a₂) ... (x - a_n)

P(--x) = (~1)ⁿ(x + a₁)(x + a2) ... (x + a_n)

Alors

P(x) P(--x) = (_1)ⁿ(x² - a₁ ²)(x² - a2²) ... (x² - a_n²)

Après K itérations on obtient un nouveau polynôme

n

Q_n(y) = > ~)yⁿ⁶⁾

t=o

b@

ses racines sont y) { - ; i: 1, 2

b@c5

alors les racines de P(x) sont : x) { }y)

~b ; i: 1, 2

Le programme

//TP12 Calcul Numerique //Methode de Graeffe

#include<iostream.h>

#include<alloc.h>

#include<math.h>

#include<conio.h>

#define carre(x) (x * x)

//le polynome est represente par un tableau

double *DefPoly(int dgr)//allocation dynamique d'un tableau

{double *tmp=(double*)malloc((dgr+1 )*sizeof(double));

return tmp;

}

void LirePoly(double *p,int dgr)//lecture des coefficients du polynome {for(int i=0;i<=dgr;i++)

{ cout<<"Entrer Le Coefficient a"<<i<<":";

cin>>p[i];

}

}

void PrintSol(double *s,int dgr)

{for(int i=0;i<dgr;i++)

cout<<"La Solution X"<<i<<": "<<s[i]<<endl;

}

//-1 a la puissance de k

int MoinUn(int k)

{if(k%2) return -1;

else return 1;

}

//transformation du polynome P(x) vers P(x)*P(-x)

void Trans(double *poly,int dgr)

{double *b=DefPoly(dgr);

b[0]=carre(poly[0]);

for(int i=2;i<=dgr+1 ;i++)

{double som=0;

for(int j=1 ;j<=i-1 ;j++)

{if((i+j)>(dgr+1)) break;

som+=MoinUn(j)*poly[i+j-1] *poly[i-j -1];

}

b[i- 1 ]=MoinUn(i- 1 )*(carre(poly[i-1 ])+2*som);

}

for(i=0;i<=dgr;i++) poly[i]=b[i];

free(b);

}

//methode de Graeffe k fois

void graeffe(double *poly,int dgr,int Kmax)

{for(int k=0;k<Kmax;k++) Trans(poly,dgr); }

/*calcul des racines a partir de relation de newton en cas de coefficients eloignes telque racine Xi=Ai- 1 /Ai /Ai=coef i=0,n */ double *RelNewton(double *poly,int dgr)

{double *sol=DefPoly(dgr-1);

for(int i=0;i<dgr;i++)

sol[i]=(- 1 )*(poly[ i+1 ]/poly[i]); return sol;

}

//la racine 2*k des solutions

void racine(double *sol,int dgr,int k) {for(int i=0;i<dgr;i++)

sol[i]=pow(fabs(sol[i]), 1/(2*k));

}

//test de solution

int test(double *p,int dgr,double *sol,double eps=0.1)

{int ok=0;

for(int i=0;i<dgr;i++)

if(fabs(poly(sol[i] ,dgr,p))<=eps)

{ cout<<"Solution = "<<sol[i]<<endl;

return (ok=1);

}

for(i=0;i<dgr;i++)

if(fabs(-poly(sol[i] ,dgr,p))<=eps)

{ cout<<"Solution = "<<-sol[i]<<endl;

return (ok=1);

}

return ok;

}

void main()

{clrscr();

cout<<"\t\tMethode de Graeffe\n";

cout<<"Entrer Le Degre Du Polynome :";int dgr;cin>>dgr;

double *poly=DefPoly(dgr);

LirePoly(poly,dgr);//lecture des coefs

double *p=DefPoly(dgr);//affecter poly a p pour l'utiliser dans le test

for(int i=0;i<=dgr;i++) p[i]=poly[dgr-i];

//tantque Kmax augmente le risque de debordement augmente

int ok=0,Kmax=4;

i=1;

//si les coef sont eloignes

double *sol=RelNewton(poly,dgr); ok=test(p,dgr,sol);

//sinon(coefs ne sont pas eloignes) while((!ok) && (i<Kmax))

{graeffe(poly,dgr,i);

sol=RelNewton(poly,dgr);

racine(sol,dgr,i);

ok=test(p,dgr,sol);

free(sol);

i++;

}

free(sol);

if(!ok) cout<<"Aucune Solution Trouvee! ! !";

getch();

}