[PDF] Les polynômes Schéma de Horner et





Previous PDF Next PDF



horner.pdf - Schéma de Hörner

La derni`ere ligne du tableau précédent ne nous livre pas seulement la valeur de P(a). En effet si construit en utilisant les trois premiers cœfficients de 



Méthode de Horner pour calculer limage dun point par un polynôme

25 janv. 2006 Je suis tr`es surpris de constater que la méthode (ou schéma) de Horner n'est pas tr`es utilisée par les lycéens. Le principe est pourtant ...



La méthode de Hörner

1 sept. 2018 Bien entendu il existe d'autres méthodes



Algorithmes compensés en arithmétique flottante : précision

Nous proposons une version compensée du schéma de Horner : la précision du résultat compensé produit par cet algorithme est la même que s'il avait été 



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)



Complexité des algorithmes [cx] Exercices de cours

2.2 Schéma de Hörner. Utilise Complexités en temps ?. Durée estimée 15 min ?. Schéma de Hörner. Le schéma de Hörner évalue la valeur d'un polynôme pour 



Schéma de Horner et algorithme de Newton

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



Les polynômes

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 



Variations sur le schéma de Horner.

Variations sur le schéma de Horner. (Programmation avec Maple). Préparation `a la nouvelle épreuve d'informatique de l'École Polytechnique.



Introduction à lalgorithmique et la complexité (et un peu de CAML

Évaluation de Polynômes Méthode de Horner. Exponentiation rapide. Recherche dans un tableau. Outline. 1. Introduction à la complexité temporelle.



[PDF] La méthode de Hörner - Mathwebfr

1 sept 2018 · La méthode de HÖRNER va nous permettre de trouver les coefficients du polynôme Q tel que : P (x)=(x ?a)Q(x)



[PDF] Schéma de Hörner - Amiens Python

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



[PDF] Méthode de Horner pour calculer limage dun point par un polynôme

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é



[PDF] I Méthode Horner

I Méthode Horner 1 Le principe Prenons l'exemple de P(x)=3x5 ? 2x4 + 7x3 + 2x2 + 5x ? 3 Pour calculer P(x) le calcul classique nécessite 



[PDF] méthode de Horner

12 déc 2011 · La méthode dite de Horner (William George Horner 1786-1837) est une méthode très pratique utilisée pour factoriser un polynôme



[PDF] 4 Polynômes - Apprendre-en-lignenet

Le schéma de Horner utilise un tableau pour calculer P(r) où P est un polynôme Sa force est que tout en calculant P(r) on peut obtenir une factorisation 



Méthode de Horner (ou schéma de Horner) - Mathforu

Cours de maths complet sur la méthode de Horner ou Schéma de Horner Très peu utilisée elle est pourtant simple rapide et permet aussi de factoriser les 



[PDF] Calcul dune image dun polynôme par la méthode de Horner

4 nov 2015 · c) Comment remplit-on le tableau suivant dont on a détaillé 3 étapes ? Que calcule-t-il ? 3 -5 7 8



[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

:

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
[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