[PDF] [PDF] Évaluation dun polynôme - IGM





Previous PDF Next PDF



[PDF] 1 Polynômes 2 Algorithme de Horner

Pour représenter les polynômes avec Python on peut utiliser le module numpy évalue le polynôme p au point a (en utilisant l'algorithme d'Horner)



[PDF] POLYNOMES : METHODE DE HORNER - efreidocfr

L'algorithme de la méthode Horner est implanté de la manière suivante pour un polynôme représenté par un tableau pour ses coefficients et un entier pour son 



[PDF] I Méthode Horner

Appliquer cet algorithme avec les polynômes suivants f(x)=4x3 ? 8x2 ? 7x ? 1 Sorties : Q qui est égal à P(x) sous la forme d'un polynôme de Horner



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

1 sept 2018 · Considérons un polynôme P dont une racine est égale à a On schématise l'algorithme de HÖRNER à l'aide d'un tableau :



[PDF] Évaluation dun polynôme - IGM

Schéma de Horner et dérivées Évaluation parall`ele Racines de polynômes Schéma de Horner Algorithme : Soit P(x) un polynôme de degrés n ? n + 1 



[PDF] Chapitre 4 Polynômes : évaluation et interpolation

Algorithme 1: Evaluation de Horner L'algorithme est de complexité linéaire en n Exercice 4 1 1 Programmez l'évaluation d'Horner en Python et en xcas verifiez 



[PDF] Algorithme de Horner compensé en précision finie et applications

Plan de l'exposé 1 Motivations 2 Évaluation précise de polynômes 3 Applications S Graillat (Univ Paris 6) Algorithme de Horner compensé



[PDF] Puissances et polynômes

d] 12 Algorithme de Horner-Ruffini Soit f0 une fonction polynomiale à coefficients entiers On suppose que d0 est un entier tel que



[PDF] Algorithmes efficaces pour les grands nombres et polynômes : Partie 2

Ecrire une fonction qui calcule la somme de deux polynômes Evaluation d'une valeur donnée : O(n) (Algorithme de Horner)



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

1 sept 2018 · Considérons un polynôme P dont une racine est égale à a La méthode de HÖRNER va nous permettre de trouver les coefficients du polynôme Q 



[PDF] POLYNOMES : METHODE DE HORNER - efreidocfr

L'algorithme de la méthode Horner est implanté de la manière suivante pour un polynôme représenté par un tableau pour ses coefficients et un entier pour son 



[PDF] I Méthode Horner

4 Utilisation de cet algorithme Nous avons démontré que P(x)=(x ? x0)Q(x) + P(x0) où Q(x) est le polynôme obtenu avec l'algo- rithme de Hörner



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

4 nov 2015 · par la méthode de Horner Soit la polynôme P1 défini par : P1(x) = 3x On souhaite automatiser le procédé par un algorithme



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

On admet que l'écriture précédente de P(x) nommée schéma de Hörner se généralise `a un pôlynome de dégré quelconque 1 2 Présentation pratique En pratique 



[PDF] Lalgorithme de Hörner

1 mai 2010 · L'algorithme de Hörner intervient dans de nombreuses situations : 1 évaluation d'un polynôme en un point 2 traduction binaire - décimal



[PDF] Algorithme de Horner compensé en précision finie et applications

Plan de l'exposé 1 Motivations 2 Évaluation précise de polynômes 3 Applications S Graillat (Univ Paris 6) Algorithme de Horner compensé



Méthode Horner PDF Polynôme Mathématiques discrètes - Scribd

Sorties : Q qui est gal P(x) sous la forme dun polynme de Horner Algorithme 1 : Algorithme de Horner n:=size(C)-1; // Le degr du polynome P Q:=C[0];



[PDF] Analyse et implantation dalgorithmes rapides pour lévaluation

16 jui 2006 · La méthode de Horner est l'algorithme le plus classique pour évaluer un polynôme en un point Son comportement numérique sur les nombres 

  • Comment faire la méthode de Horner ?

    qui est appelée méthode de Horner. Un élément de la ligne inférieure s'obtient en multipliant l'élément qui le préc? par le nombre figurant dans la première colonne, en pla?nt le résultat dans sa colonne et en effectuant la somme de deux premiers nombres de la colonne.

  • Comment utiliser la méthode Horner ?

    La méthode de Horner consiste à combiner les deux itérations précédentes en une seule en effectuant le calcul comme suit : . Le nombre de produits est alors réduit à n et l'on peut montrer que ce nombre est minimal : il n'est pas possible d'évaluer une fonction polynomiale en moins de n produits en toute généralité.

  • Comment évaluer un polynôme ?

    La méthode de Horner est l'algorithme le plus classique pour évaluer un polynôme en un point. Son comportement numérique, sur les nombres flottants en tenant compte des erreurs d'ar- rondi, est relativement bien compris, et il s'av`ere qu'en termes de précision, ce schéma semble satisfaisant.16 jui. 2006
  • Cette méthode permet de calculer l'image d'un polynôme P en un point x o x_o xo. En outre, elle permet d'obtenir la division euclidienne de P ( x ) P(x) P(x) par ( x ? x o ) (x-x_o) (x?xo), utile pour la factorisation des polynômes.
[PDF] Évaluation dun polynôme - IGM

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 4aquotesdbs_dbs33.pdfusesText_39
[PDF] modele quantique de bohr

[PDF] polynome scindé a racines simples

[PDF] modèle quantique de l'atome wikipedia

[PDF] modèle quantique de l'atome exercices corrigés

[PDF] modele planetaire schrodinger

[PDF] modèle plum pudding

[PDF] modèle atomique bohr

[PDF] modele atomique rutherford bohr

[PDF] modèle atomique simplifié potassium

[PDF] modèle atomique simplifié lithium

[PDF] modèle atomique simplifié calcium

[PDF] périodicité des propriétés

[PDF] modèle atomique simplifié hydrogène

[PDF] notation de lewis

[PDF] protocole infirmier medecine du travail