Méthode Horner - Free PDF Ouvrer xcas et dans un

Lalgorithme de Hörner

1 mai 2010 a mod c si le bit A[i]=1 et dans ce cas on a une élévation au carré suivie d'une multiplication. 4 Considération des bits de bas en haut. Dans l ...

Analyse et implantation dalgorithmes rapides pour lévaluation

10 déc. 2006 la même borne d'erreur que l'algorithme de Horner. ... En notant C(p) le coût d'évaluation d'un polynôme de degré n = 2p ?1 ...

Travaux Pratiques de programmation no7

Implémentez l'algorithme de Horner. (c) La méthode de Horner possède un autre avantage. Construisez le polynôme X10 ?99X9 et évaluez-le pour X = 100 avec

Analyse Numérique

2.3.1.2 Evaluation d'un polynôme : algorithme de Hörner . . . 35 C'est donc un souci qui nous accompagnera tout au long de ce cours. 9 ...

livre-algorithmes EXo7.pdf

(c) Écrire une fonction qui calcule P(?) par l'algorithme de Horner. 2. On formalise le calcul précédent en définissant la suite : bn = an puis pour.

I Méthode Horner

Appliquer cet algorithme avec les polynômes suivants. Algorithme 1 : Algorithme de Horner ... n:=size(C)-1; // Le degré du polynome P. Q:=C[0];.

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

Évaluation de Polynômes Méthode de Horner. Exponentiation rapide Lorsqu'on demande : “Mais c'est quoi un algorithme efficace ???"

Licence de Mathématiques Fondamentales Calcul Scientifique

de Lagrange associés à E. On munit C([a b]

Notes de programmation (C) et dalgorithmique

3 jan. 2022 1.2 Structure et interprétation d'un programme C . . ... La r`egle de Horner est un autre algorithme pour évaluer un polynôme de degré n ...

Analyse et implantation dalgorithmes rapides pour lévaluation

la même borne d'erreur que l'algorithme de Horner. En notant C(p) le coût d'évaluation d'un polynôme de degré n = 2p ?1 sachant que l'on conna?t.

Ouvrer xcas et dans un environnement de programme (Alt+p) taper : Horner(Cx):={local Qkn; //les variables locales n:=size(C)-1; // Le degré du polynome P Q:=C[0]; pour k de 1 jusque n faire Q:=(Q*x)+C[k]; fpour; retourne(Q)} Compiler ce programme (F9) et dans une autre entrée tester le avec : L:=[3-2725-3] Horner(L2) Horner(L10000

Searches related to algorithme de horner en c PDF

Algorithme de Horner compensé en précision ?nie et applications Stef Graillat LIP6/PEQUAN - Université Pierre et Marie Curie (Paris 6) Séminaire SPIRAl/SALSA 1 juin 2007 Paris S Graillat (Univ Paris 6) Algorithme de Horner compensé 1 / 40

Comment fonctionne l’algorithme de Hörner ?

Dans l’algorithme de Hörner donné précédemment, on a traitéles bits de la “puissance” en com-mençant par ceux de poids forts. Peut on décrire un algorithme fondé sur un principe analogue quitraiterait d’abord les bits de poids faible ?

Comment calculer la méthode de Horner ?

Une présentation de la méthode de Horner dans un tableau montre la simplicité de l'algorithme : chaque coefficient de Q s'obtient en multipliant le coefficient de la case de gauche par a et en lui ajoutant le coefficient de la case du dessus.

Comment fonctionne l’algorithme d’apprentissage ?

La machine peut automatiser les tâches en fonction des situations. En fonction des données d’expérimentation que prendra l’algorithme d’apprentissage en entrée, il déduira par lui-même une hypothèse de fonctionnement. Il utilisera cette dernière pour de nouveaux cas, et affinera son expérience au fil du temps.

Comment calculer l’algorithme de Hörner binaire ?

Par exemple, si l’opération?est l’addition des entiers avec son élément neutre0, et sia= 1, l’al-gorithme est exactement l’algorithme de Hörner binaire, dereconstitution de l’entiernà partir de sesbits, que nous avons décrit précédemment. qui ae= 1pour élément neutre, l’algorithme calculeanmodc.

IMéthode Horner

1 Le principe

Prenons l"exemple deP(x) = 3x5-2x4+ 7x3+ 2x2+ 5x-3. Pour calculer P(x) le calcul classique nécessite ......multiplications et ......additions. De même si on généralise Pour calculerP(x) =anxn+an-1xn-1+···+a1x+a0 il faut ..................multiplications et ...............additions. Dem : On peut faire de nombreuses économies de calcul en suivant leschéma suivant :

P(x) =anxn+···+a2x2+a1x?

on metxen facteur+a0 anxn-1+···+a3x+a2? on metxen facteur+a1)) x+a0 = (...(((anx+an-1)x+an-2)x+an-3)...)x+a0

Ici cela donneP(x) = 3x5-2x4+ 7x3+ 2x2+ 5x-3

= (3x4-2x3+ 7x2+ 2x+ 5)x-3 Avec cette forme deP(x) il y a ......multiplications et ......additions. Dans le cas généralP(x) = (...(((anx+an-1)x+an-2)x+an-3)...)x+a0

Il y a au maximum ............multiplications et ............additions (voir moins avec les zéros).

Appliquer cet algorithme avec les polynômes suivants. f(x) = 4x3-8x2-7x-1g(x) = 4x4-23x2-15x-2

Entrées: Les coefficientsaidans l"ordre décroissant des exposants des monômes, le monôme x1

début2 n :=degré du polynôme P.3

Q :=an4

pour kallantde1ànfaire5

Q:=Q?x+an-k6

fin7 Sorties: Q qui est égal à P(x) sous la forme d"un polynôme de Horner8

Algorithme 1: Algorithme de Horner

Pour faire les calculs "à la main» il est plus facile de le présenter autrement. Par exemple pour

f(x) = 4x3-8x2-7x-1

4 -8 -7 -1?

???x 4x(4x-8)x((4x-8)x-7)x

4 (4x-8) (4x-8)x-7 ((4x-8)x-7)x-1

Par exemple pour calculer f(2). Calculer de même pourf(3),P(2). f4 -8 -7 -1? ???2 8 0-14

4 0-7-15

Doncf(2) =-15.

f4 -8 -7 -1? ???3 ... ... ...

Doncf(3) =......

P3 -2 7 2 5 -3?

???2 ... ... ... ... ...

DoncP(2) =......

2 Démonstration

SoitPun polynôme de degrén,x0un réel.

On cherche à déterminer un polynômeQ(x) tel queP(x) = (x-x0)Q(x) +P(x0). Qest forcément un polynôme de degrén-1 et on a : ➔P(x) =anxn+···+a1x+a0 ➔Q(x) =bn-1xn-1+···+b1x+b0. ➔P(x) = (x-x0)Q(x) +P(x0). Exprimer les coefficients deQen fonction des coefficients dePet deP(x0) (x-x0)Q(x) +P(x0) = (x-x0)(bn-1xn-1+bn-2xn-2+···+b1x+b0) =anxn+ ( )xn-1+···+ ( )x2+ ( )x+ ( ) n=...... a n-1=...... a

2=......

1=......

a n-1=...... b n-2=...... b1 =...... b

0=......

P(x0) =......

P anan-1...a2a1a0?

???x0... ... ... ... ... bn-1bn-2...b1b0P(x0) coefficient est bienP(x0). On a démontré l"existence et l"unicité du polynômeQ(x).

3 Expérimentation avec xcas

Ouvrer xcas et dans un environnement de programme (Alt+p) taper :

Horner(C,x):={

localQ,k,n;//les variables locales n:=size(C)-1;// Le degré du polynome P

Q:=C[0];

pourkde1jusquenfaire

Q:=(Q*x)+C[k];

fpour; retourne(Q) Compiler ce programme (F9) et dans une autre entrée tester leavec :

L:=[3,-2,7,2,5,-3]

Horner(L,2)

Horner(L,10000)

Horner(L,x)

4 Utilisation de cet algorithme

Nous avons démontré queP(x) = (x-x0)Q(x) +P(x0) oùQ(x) est le polynôme obtenu avec l"algo-

Six0est une racine dePalors On trouvep(x0) =......et doncP(x) =.........

Par exemple calculerf?-1

2? en complétant le tableau ci dessous.

4 -8 -7 -1?

-1

2... ... ...

Donner alors une première factorisation def(x). En déduire une factorisation "complète» def(x).

Nous allons donc modifier le programme précédent pour faire apparaitre tous les coefficients

Horner2(C,x):={

localQ,k,n; n:=size(C)-1;// Le degré du polynome P

Q:=[];// on crée une liste vide

Q[0]:=C[0];

pourkde1jusquenfaire

Q[k]:=(Q[k-1]*x)+C[k];

fpour; retourne(Q)

En utilisant cette fois le programme que nous avons crée calculerg(-2) en déduire une factorisation

deP. CalculerQ? -1 2? . En déduire une factorisation deQ(x) puis deP(x).

5 Avec une calculatrice TI

PGRM➔NEW➔HORNER

Pour afficher seulementP(x0).

Prompt X

ClrList L6

Disp ??{AN,...,A0}??

Input L6

dim(L6)-1->N

L6(1)->Q

For(K,1,N,1)

Q*X+L6(K+1)->Q

End Disp QPour afficher la liste des coefficients deQet

P(x0).

Prompt X

ClrList L6

Disp ??{AN,...,A0}??

Input L6

dim(L6)-1->N

For(K,1,N,1)

L6(K)*X+L6(K+1)->L6(K+1)

End

Disp L6

On écrira seulement le deuxième programmecar il donne la liste des coefficients deQ(x). Pour tester plus facilement le programme écrire dans la listeL1 les coefficients 4-8-7-1.

Exécuter le programme par exemple pour-0,5. Horner2➔-0.5➔L1 et vous devez obtenir 0 pour le

premier programme et pour le deuxième la liste qui est enL6 ={4-10-2 0}. On a doncP(-0.5) = 0 etP(x) = (x+ 0,5)(4x2-10x-2). On peut aussi modifier le programme pour faire afficher des fractions.

Ce programme fonctionne aussi avec des complexes.

6 Avec python

defHorner(C,x): n=len(C)

Q=C[0]

forkinrange(1,n):

Q=Q?x+C[k]

returnQ

P=[4,-8,-7,-1]

print(Horner(P,0)) defHorner(C,x): n=len(C)

Q=[0]?n;

Q[0]=C[0];

forkinrange(1,n):

Q[k]=Q[k-1]?x+C[k]

returnQ

P=[4,-8,-7,-1]

print(Horner(P,-0.5))

7 Correction de la démonstration

SoitPun polynôme de degrén,x0un réel.

On cherche à déterminer un polynômeQ(x) tel queP(x) = (x-x0)Q(x) +P(x0). Qest forcément un polynôme de degrén-1 et on a : ➔P(x) =anxn+···+a1x+a0 ➔Q(x) =bn-1xn-1+···+b1x+b0. ➔P(x) = (x-x0)Q(x) +P(x0). (x-x0)Q(x) +P(x0) = (x-x0)? b n-1xn-1+···+b1x+b0? +P(x0) =bn-1xn+···+b1x2+b0x-x0bn-1xn-1- ··· -x0b1x-x0b0+P(x0) =bn-1xn+ (bn-2-x0bn-1)n-1+···+ (b1-x0b2)x2+ (b0-x0b1)x-x0b0+P(x0)

On a donc par identification

?b n-1=an b n-2-x0bn-1=an-1 b

1-x0b2=a2

0-x0b1=a1

n-1=an b n-2=x0bn-1+an-1 b

1=x0b2+a2

0=x0b1+a1

P(x0) =x0b0+a0

bienP(x0).

Pour la programmation nous avons utilisé les listes [anan-1...a1a0] qui sont numérotées [p0p1p2...pn-1pn]

car les listes commencent à 0 (ou 1 pour la TI). 4quotesdbs_dbs4.pdfusesText_8

[PDF] module 1 rencontres 1ére année

[PDF] exposé sur le film intouchable

[PDF] texte au hasard d une rencontre 1ére année

[PDF] objet et methode de lanthropologie

[PDF] analyse anthropologique définition

[PDF] intouchables résumé

[PDF] démarche anthropologique définition

[PDF] enquête de terrain anthropologie

[PDF] enquête anthropologique

[PDF] observation participante anthropologie

[PDF] écrire des dialogues scénario

[PDF] méthode de la sécante exemple

[PDF] méthode de dichotomie exercices corrigés

[PDF] mots argot jeunes

[PDF] méthode de la sécante matlab

[PDF] Méthode Horner - Free Ouvrer xcas et dans un

Comment fonctionne l’algorithme de Hörner ?

Comment calculer la méthode de Horner ?

Comment fonctionne l’algorithme d’apprentissage ?

Comment calculer l’algorithme de Hörner binaire ?

IMéthode Horner

1 Le principe

P(x) =anxn+···+a2x2+a1x?

Ici cela donneP(x) = 3x5-2x4+ 7x3+ 2x2+ 5x-3

Q :=an4

Q:=Q?x+an-k6

Algorithme 1: Algorithme de Horner

4 -8 -7 -1?

4 (4x-8) (4x-8)x-7 ((4x-8)x-7)x-1

4 0-7-15

Doncf(2) =-15.

Doncf(3) =......

P3 -2 7 2 5 -3?

DoncP(2) =......

2 Démonstration

SoitPun polynôme de degrén,x0un réel.

2=......

1=......

0=......

P(x0) =......

P anan-1...a2a1a0?

3 Expérimentation avec xcas

Horner(C,x):={

Q:=C[0];

Q:=(Q*x)+C[k];

L:=[3,-2,7,2,5,-3]

Horner(L,2)

Horner(L,10000)

Horner(L,x)

4 Utilisation de cet algorithme

Par exemple calculerf?-1

4 -8 -7 -1?

2... ... ...

Horner2(C,x):={

Q:=[];// on crée une liste vide

Q[0]:=C[0];

Q[k]:=(Q[k-1]*x)+C[k];

5 Avec une calculatrice TI

PGRM➔NEW➔HORNER

Pour afficher seulementP(x0).

Prompt X

ClrList L6

Disp ??{AN,...,A0}??

Input L6

L6(1)->Q

For(K,1,N,1)

Q*X+L6(K+1)->Q

P(x0).

Prompt X

ClrList L6

Disp ??{AN,...,A0}??

Input L6

For(K,1,N,1)

L6(K)*X+L6(K+1)->L6(K+1)

Disp L6

Ce programme fonctionne aussi avec des complexes.

6 Avec python

Q=C[0]

Q=Q?x+C[k]

P=[4,-8,-7,-1]

Q=[0]?n;

Q[0]=C[0];

Q[k]=Q[k-1]?x+C[k]

P=[4,-8,-7,-1]

7 Correction de la démonstration

SoitPun polynôme de degrén,x0un réel.

On a donc par identification

1-x0b2=a2

0-x0b1=a1

1=x0b2+a2

0=x0b1+a1

P(x0) =x0b0+a0