[PDF] [PDF] Les polynômes - IGM

[PDF] Schéma de Hörner 1 Le schéma de Hörner pour le calcul de valeurs

1 Le schéma de Hörner pour le calcul de valeurs 1 1 Un exemple Soit la fonction polynôme P définie par P(x)=2x3 − 7x 2 + 4x − 1 On souhaite calculer P(a) 

[PDF] I Méthode Horner

On peut faire de nombreuses économies de calcul en suivant le schéma suivant : P(x) = anxn + ··· + a2x2 + a1x ︸ ︷︷ ︸ on met x en facteur +a0 =

[PDF] Schéma de Horner et algorithme de Newton - Grenoble Sciences

Pour aller plus loin, il vaut mieux programmer le schéma de Horner (voir le livre § 5 7 4) et la méthode de Newton Nous trouvons ensuite p(x(1))=0,0945994, p/(x(  

[PDF] Les polynômes - IGM

Schéma de Horner et dérivées Évaluation parall`ele Racines de polynômes Évaluation d'un polynôme Introduction : Soit un polynôme P(x), on veut évaluer 

[PDF] Méthode de Horner pour calculer limage dun point par un - Math93

25 jan 2006 · Comme je l'ai indiqué dans le titre, le schéma de Horner permet de calculer l' image d'un polynôme P en un point β donné Mais la force de la

[PDF] Exercice 1 Utiliser le schéma de Horner pour évaluer p(x) et ses

Utiliser le schéma de Horner pour évaluer p(x) et ses dérivées successives p (x), p (x), etc en x = -4, où p(x) = x3 + 4x2 + x - 6 Exercice 2 Trouver le PGCD(p, 

[PDF] 1 Polynômes 2 Algorithme de Horner

2 Algorithme de Horner Soient a ∈ K et P = n ∑ k=0 bkXk On souhaite calculer P(a) Naïvement, on calcule les puissances de a, on multiplie les résultats par 

[PDF] algorithme de horner python

[PDF] seuil de rentabilité cours pdf

[PDF] méthode des couts variables exercices corrigés

[PDF] exercice seuil de rentabilité corrigé pdf

[PDF] levier opérationnel calcul

[PDF] représentation graphique du seuil de rentabilité

[PDF] calcul du seuil de rentabilité avec plusieurs produits

[PDF] indice de sécurité calcul

[PDF] exercice seuil de rentabilité bts

[PDF] choix d'investissement exercices

[PDF] rentabilité des investissements cours

[PDF] calcul drci+formule

[PDF] calcul de rentabilité d'un investissement industriel

[PDF] etude de rentabilité d'une entreprise

[PDF] ratio de rentabilité commerciale

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesLes polyn^omes

Vincent Nozick

Vincent NozickLes polyn^omes1 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omes

Evaluation d'un polyn^ome

Introduction :

Soit un polyn^omeP(x), on veut evaluer ce polyn^ome enx=x0. P(x) =anxn+:::+a3x3+a2x2+a1x+a0Vincent NozickLes polyn^omes2 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omes

Evaluation d'un polyn^ome

Methode nave :

P(x0) =nX

i=0a ixi0 calculer a chaque foisxi0comporte une grosse redondance.Vincent NozickLes polyn^omes3 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner

Pour accelerer les calculs, on peut recrireP(x):

P(x0) =

:::(anx+an1)x+an2x+::: x+a1! x+a0

Comment procede-t-on? (on commence par ou?)

Vincent NozickLes polyn^omes4 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner

P(x0) =(a4x+a3)x+a2x+a1

x+a0 b 4=a4b

3=a4x0+a3b

3=b4x0+a3b

2= (a4x0+a3)x0+a2b

2=b3x0+a2b

1= ((a4x0+a3)x0+a2)x0+a1b

1=b2x0+a1b

0= (((a4x0+a3)x0+a2)x0+a1)x0+a0b

0=b1x0+a0P(x0) =b0Vincent NozickLes polyn^omes5 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner

P(x0) =(a4x+a3)x+a2x+a1

x+a0 b 4=a4b

3=a4x0+a3b

3=b4x0+a3b

2= (a4x0+a3)x0+a2b

2=b3x0+a2b

1= ((a4x0+a3)x0+a2)x0+a1b

1=b2x0+a1b

0= (((a4x0+a3)x0+a2)x0+a1)x0+a0b

0=b1x0+a0P(x0) =b0Vincent NozickLes polyn^omes5 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner

P(x0) =(a4x+a3)x+a2x+a1

x+a0 b 4=a4b

3=a4x0+a3b

3=b4x0+a3b

2= (a4x0+a3)x0+a2b

2=b3x0+a2b

1= ((a4x0+a3)x0+a2)x0+a1b

1=b2x0+a1b

0= (((a4x0+a3)x0+a2)x0+a1)x0+a0b

0=b1x0+a0P(x0) =b0Vincent NozickLes polyn^omes5 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner

P(x0) =(a4x+a3)x+a2x+a1

x+a0 b 4=a4b

3=a4x0+a3b

3=b4x0+a3b

2= (a4x0+a3)x0+a2b

2=b3x0+a2b

1= ((a4x0+a3)x0+a2)x0+a1b

1=b2x0+a1b

0= (((a4x0+a3)x0+a2)x0+a1)x0+a0b

0=b1x0+a0P(x0) =b0Vincent NozickLes polyn^omes5 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner

P(x0) =(a4x+a3)x+a2x+a1

x+a0 b 4=a4b

3=a4x0+a3b

3=b4x0+a3b

2= (a4x0+a3)x0+a2b

2=b3x0+a2b

1= ((a4x0+a3)x0+a2)x0+a1b

1=b2x0+a1b

0= (((a4x0+a3)x0+a2)x0+a1)x0+a0b

0=b1x0+a0P(x0) =b0Vincent NozickLes polyn^omes5 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner

P(x0) =(a4x+a3)x+a2x+a1

x+a0 b 4=a4b

3=a4x0+a3b

3=b4x0+a3b

2= (a4x0+a3)x0+a2b

2=b3x0+a2b

1= ((a4x0+a3)x0+a2)x0+a1b

1=b2x0+a1b

0= (((a4x0+a3)x0+a2)x0+a1)x0+a0b

0=b1x0+a0P(x0) =b0Vincent NozickLes polyn^omes5 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner

Algorithme :

SoitP(x)un polyn^ome de degresn!n+ 1coecients

On peut le representer sous forme d'un tableau de coecients : a[i]=i-eme coecient du polyn^omeP.Algorithm 1:Hornerb = a[n] fori nto0dob = bx0+ a[i] end returnbVincent NozickLes polyn^omes6 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner : en pratique

En pratique :

On peut approximer le calcul desin(x)par son developpement de

Taylor :

sin(x) =xx33! +x55! x77! +x99! x1111! +x1313! x1515! +O(x16)

!on obtient un polyn^ome dont les coecients sont :doublea0 = +1.0;doublea1 =1.666666666666666666666666666666666667e1;doublea2 = +8.333333333333333333333333333333333333e3;doublea3 =1.984126984126984126984126984126984127e4;doublea4 = +2.755731922398589065255731922398589065e6;doublea5 =2.505210838544171877505210838544171878e8;doublea6 = +1.605904383682161459939237717015494793e10;doublea7 =7.647163731819816475901131985788070444e13;Vincent NozickLes polyn^omes7 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner : en pratique

Force brute :

avec une legere optimisation : on precalculex2.doublesin1 (doublex)f

doubleresult ;doublex2 = xx ;result = a0x ; x= x2 ;result += a1x ; x= x2 ;result += a2x ; x= x2 ;result += a3x ; x= x2 ;result += a4x ; x= x2 ;result += a5x ; x= x2 ;result += a6x ; x= x2 ;result += a7x ;returnresult ;g

!16 multiplications et 7 additions.Vincent NozickLes polyn^omes8 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner : en pratique

Schema de Horner :

avec la m^eme legere optimisation : on precalculex2.doublesin2 (doublex)f doublex2 = xx ;returnx(a0+x2(a1+x2(a2+x2(a3+x2(a4+x2(a5+x2(a6+x2a7 ) ) ) ) ) ) ) ;g !9 multiplications et 7 additions.Vincent NozickLes polyn^omes9 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner : en pratique

compilationsin1sin2normale0.044 ns0.031 ns

O20.021 ns0.024 ns

!Horner est parfois plus lent !!

Explications :

Certain pipeline cpu peuvent eectuer une operation et lire la vari- able de l'operation suivante en un seul cycle, sauf si la variable suivante depend du resultat de l'operation courante. Dans ce cas, on perd a chaque fois un cycle. !sin1: 30 cycles !sin2: 48 cyclesVincent NozickLes polyn^omes10 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

Problematique :

Le schema de Horner permet aussi d'evaluer la deriveen-eme du polyn^omeP(x)enx0Vincent NozickLes polyn^omes11 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

P(x) =a3x3+a2x2+a1x+a0

P(x) = ((a3x+a2)x+a1)x+a0

b

3=a3a3=b3

b

2=b3x0+a2a2=b2b3x0

b

1=b2x0+a1,a1=b1b2x0

b

0=b1x0+a0a0=b0b1x0

P(x0) =b0a0=P(x0)b1x0

On reecrit l'equation de depart en remplacant lesai: P(x) =b3x3+ (b2b3x0)x2+ (b1b2x0)x+P(x0)b1x0Vincent NozickLes polyn^omes12 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

Developpement et factorisation :

P(x) =b3x3+ (b2b3x0)x2+ (b1b2x0)x+P(x0)b1x0

P(x) =b3x3+b2x2+b1x(b3x2+b2x+b1)x0+P(x0)

P(x) = (b3x2+b2x+b1)x(b3x2+b2x+b1)x0+P(x0)

P(x) = (b3x2+b2x+b1)(xx0) +P(x0)Vincent NozickLes polyn^omes13 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

On obtient une nouvelle ecriture du polyn^ome :

P(x) = (b3x2+b2x+b1|{z}

Q)(xx0) +P(x0)

on recommence sur le polyn^omeQ(x) =b3x2+b2x+b1 on obtient : P(x) = ((c2x+c1)(xx0) +Q(x0))(xx0) +P(x0)Vincent NozickLes polyn^omes14 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

On obtient une nouvelle ecriture du polyn^ome :

P(x) = ((c2x+c1|{z}

M)(xx0) +Q(x0))(xx0) +P(x0)

on recommence sur le polyn^omeM(x) =c2x+c1 on obtient : P(x) = ((d1(xx0)+M(x0))(xx0)+Q(x0))(xx0)+P(x0)Vincent NozickLes polyn^omes15 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

Finalement :

P(x) = ((d1(xx0)+M(x0))(xx0)+Q(x0))(xx0)+P(x0)

developpement :

P(x) =d1(xx0)3+M(x0)(xx0)2+Q(x0)(xx0) +P(x0)

soit dans l'autre sens : P(x) =P(x0) +Q(x0)(xx0) +M(x0)(xx0)2+d1(xx0)3Vincent NozickLes polyn^omes16 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

P(x) =P(x0) +Q(x0)(xx0) +M(x0)(xx0)2+d1(xx0)3

ressemble au developpement de Taylor defenx0: f(x) =f(x0)+f0(x0)(xx0)+f00(x0)2! (xx0)2+f000(x0)3! (xx0)3+:::Vincent NozickLes polyn^omes17 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

P(x) =P(x0)+Q(x0)(xx0)+M(x0)(xx0)2+d1(xx0)3+0

ressemble au developpement de Taylor defenx0: f(x) =f(x0)+f0(x0)(xx0)+f00(x0)2! (xx0)2+f000(x0)3! (xx0)3+::: par identication : P

0(x0) =Q(x0)P000(x0) =d13!

P

00(x0) =M(x0)2!:::= 0Vincent NozickLes polyn^omes18 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees Pour evaluerP(x0),P0(x0),P00(x0),P000(x0), ... il sut d'appliquer le schema de Horner plusieurs fois.

P(x) =a3x3+a2x2+a1x+a0

P(x0)Q(x0)M(x0)

a

3b3c2d1

a

2b2c1d0

a 1b1c0 a 0b0 !P(x) = (b3x2+b2x+b1)(xx0) +P(x0)Vincent NozickLes polyn^omes19 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees Pour evaluerP(x0),P0(x0),P00(x0),P000(x0), ... il sut d'appliquer le schema de Horner plusieurs fois.

P(x) =a3x3+a2x2+a1x+a0

P(x0)Q(x0)M(x0)

a

3b3c2d1

a

2b2c1d0

a 1b1c0 a 0b0 !P(x) = (b3x2+b2x+b1)(xx0) +P(x0)Vincent NozickLes polyn^omes20 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees Pour evaluerP(x0),P0(x0),P00(x0),P000(x0), ... il sut d'appliquer le schema de Horner plusieurs fois.

P(x) = (b3x2+b2x+b1)(xx0) +P(x0)

P(x0)Q(x0)M(x0)

a

3b3c2d1

a

2b2c1d0

a 1b1c0 a 0b0 !P(x) = ((c2x+c1)(xx0) +Q(x0))(xx0) +P(x0)Vincent NozickLes polyn^omes21 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees Pour evaluerP(x0),P0(x0),P00(x0),P000(x0), ... il sut d'appliquer le schema de Horner plusieurs fois.

P(x) = ((c2x+c1)(xx0) +Q(x0))(xx0) +P(x0)

P(x0)Q(x0)M(x0)

a

3b3c2d1

a

2b2c1d0

a 1b1c0 a 0b0 !P(x) = ((d1(xx0)+M(x0))(xx0)+Q(x0))(xx0)+P(x0)Vincent NozickLes polyn^omes22 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees Pour evaluerP(x0),P0(x0),P00(x0),P000(x0), ... il sut d'appliquer le schema de Horner plusieurs fois.

P(x) = ((d1(xx0)+M(x0))(xx0)+Q(x0))(xx0)+P(x0)

P(x0)Q(x0)M(x0)

a

3b3c2d1

a

2b2c1d0

a 1b1c0 a 0b0 !P(x) = ((d1(xx0)+M(x0))(xx0)+Q(x0))(xx0)+P(x0)Vincent NozickLes polyn^omes23 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesSchema de Horner et derivees

P(x0)Q(x0)M(x0)

a

3b3c2d1

a

2b2c1d0

a 1b1c0 a 0b0

P(x0) =b0P00(x0) =d02!

P

0(x0) =c0P000(x0) =d13!Vincent NozickLes polyn^omes24 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omes

Evaluation de polyn^omes en parallele

Exemple :P(x) =a0+a1x+a2x2+a3x3+a4x4+a5x5

a 0a 1a 2a 3a 4a 500a

0+a1xa

2+a3xa

4+a5x0 + 0xa

0+a1x+ (a2+a3x)x2a

4+a5x+ (0 + 0)x2a

0+a1x+ (a2+a3x)x2+ (a4+a5x+ (0 + 0)x2)x4Vincent NozickLes polyn^omes25 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omes

Evaluation de polyn^omes en parallele

Complexite :O(log2n)

Propriete :meilleurs precision numerique.Vincent NozickLes polyn^omes26 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesRacines de polyn^omes

Rappels :

Racines du polyn^omeP(x):fx=P(x) = 0g

Racines : reelles / complexesVincent NozickLes polyn^omes27 / 36

Evaluation d'un polyn^ome

Sch emade Ho rneret d eriveesEvaluation paralleleRacines de p olyn^omesRacines de polyn^omes

Degre 2 :

P(x) =ax2+bx+c

x=bpbquotesdbs_dbs22.pdfusesText_28