Sorties : Q qui est égal à P(x) sous la forme d'un polynôme de Horner 8 Algorithme 1 : Algorithme de Horner 1 6 Avec python def Horner(C,x): n=len(C )
Previous PDF | Next PDF |
[PDF] 1 Polynômes 2 Algorithme de Horner
Python 1 Polynômes Pour représenter les polynômes avec Python, on peut utiliser le module numpy • poly1d([an, ,a0]) représente le polynôme anxn +
[PDF] I Méthode Horner
Sorties : Q qui est égal à P(x) sous la forme d'un polynôme de Horner 8 Algorithme 1 : Algorithme de Horner 1 6 Avec python def Horner(C,x): n=len(C )
[PDF] Algorithmes classiques - CNRS
Ecrire en Python la fonction qui recherche un élément e dans un tableau tab Complétez l'invariant de boucle de l'algorithme de Horner : « Au début de
[PDF] Chapitre 4 Polynômes : évaluation et interpolation - Annuaire IMJ-PRG
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] IV Définition récursive de fonctions :
puissance en Python, algorithme basé sur la récursivité On peut utiliser cette formule pour calculer l'image d'un réel x0 par P C'est la méthode de Hörner
[PDF] Lalgorithme de Hörner - ACrypTA
1 mai 2010 · Nous suggérons d'autres algorithmes qui l'utilisent d'une manière plus ou moins cachée 1 2 L'algorithme de Hörner binaire (1) (2) 0 0
[PDF] Puissances et polynômes
Programmer l'algorithme de Horner : l'appel Horner(P, x) doit retourner le couple Python constate d'abord que C[0,0] est une matrice de Л1(Ê) dont l'unique
[PDF] TD : La complexité temporelle Exemple 1 : Fibonacci - Pascal
24 nov 2017 · Construire une fonction HORNER(P,alpha) calculant P(α) avec l'algorithme de Horner 3 En utilisant la fonction clock() de Python, déterminer
[PDF] Feuille 1: Introduction à la récursivité sur une - [Verimag]
Le but est (re)trouver des algorithmes simples de calculs sur les polynômes à l' aide Définition 1 Un polynôme de Horner sur la variable X est: Exercice 1 Écrire une fonction Python pour chacun des calculs ci-dessous (en estimant à
[PDF] Complexité temporelle des algorithmes - Inria
Évaluation de Polynômes, Méthode de Horner qu'un algorithme codé en Python Bref, le Quelle est la complexité (nombre de mots lus) de cet algorithme ?
[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
[PDF] rentabilité financière d'une entreprise
![[PDF] I Méthode Horner [PDF] I Méthode Horner](https://pdfprof.com/Listes/17/22861-17Horner.pdf.pdf.jpg)
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+a0Ici 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+a0Il 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-2Entrées: Les coefficientsaidans l"ordre décroissant des exposants des monômes, le monôme x1
début2 n :=degré du polynôme P.3Q :=an4
pour kallantde1ànfaire5Q:=Q?x+an-k6
fin7 Sorties: Q qui est égal à P(x) sous la forme d"un polynôme de Horner8Algorithme 1: Algorithme de Horner
1Pour faire les calculs "à la main» il est plus facile de le présenter autrement. Par exemple pour
f(x) = 4x3-8x2-7x-14 -8 -7 -1?
???x 4x(4x-8)x((4x-8)x-7)x4 (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-144 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=...... a2=......
a1=......
a n-1=...... b n-2=...... b1 =...... b0=......
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 PQ:=C[0];
pourkde1jusquenfaireQ:=(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)
24 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?
-12... ... ...
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 coefficientsHorner2(C,x):={
localQ,k,n; n:=size(C)-1;// Le degré du polynome PQ:=[];// on crée une liste vide
Q[0]:=C[0];
pourkde1jusquenfaireQ[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->NL6(1)->Q
For(K,1,N,1)
Q*X+L6(K+1)->Q
End Disp QPour afficher la liste des coefficients deQetP(x0).
Prompt X
ClrList L6
Disp ??{AN,...,A0}??
Input L6
dim(L6)-1->NFor(K,1,N,1)
L6(K)*X+L6(K+1)->L6(K+1)
EndDisp 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.
36 Avec python
defHorner(C,x): n=len(C)Q=C[0]
forkinrange(1,n):Q=Q?x+C[k]
returnQP=[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]
returnQP=[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 b1-x0b2=a2
b0-x0b1=a1
n-1=an b n-2=x0bn-1+an-1 b1=x0b2+a2
b0=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_dbs28.pdfusesText_34