1. Avec les notations ci-dessus, écrire une procédure Translat modifiant P = [an, a . . . , a1, a0]

pour y placer les coefficients bn, . . . , b1, b0.

La syntaxe est Translat(P, t), et on fera appel à la procédure Quo1.

[ S ]

2. Écrire une fonction translat, renvoyant le tableau Q = [bn, . . . , b1, b0].

On utilisera la syntaxe Translat(P, t), et on ne fera pas appel à la procédure Quo1.

[ S ]

c(cid:13)EduKlub S.A.

Page 4

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Énoncé

3. Vérifier que translat nécessite 1

2(n2 − n) additions et autant de multiplications.

Écrire une autre version de cette fonction nécessitant moins de 3n multiplications.

Indication : en utilisant des homothéties de rapport t ou 1/t, se ramener à t = 1.

Cette économie se fait au prix d’un tableau supplémentaire contenant [tn, tn−1, . . . , t, 1].

[ S ]

4. Écrire une fonction derivs prenant en argument un polynôme P (représenté par le tableau

[an, . . . , a1, a0]) et un réel t, et renvoyant le tableau [P (n)(t), . . . , P 0(t), P (t)] des dérivées suc-

cessives de P au poit t (par ordre décroissant de l’ordre de dérivation.) [ S ]

IV. Règle des signes de Descartes

Considérons le polynôme P =

n

P

k=0

akX k, représenté par le tableau P = [an, an−1, . . . , a1, a0].

On appelle changement de signe dans P tout couple (i, j), avec i < j et :

– Les coefficients ai et aj sont non nuls et de signe contraire.

– Pour tout k tel que i < k < j on a ak = 0.

On observe donc un changement de signe quand deux coefficients non nuls consécutifs de P (ordonné

suivant les puissances croissantes ou décroissantes) sont de signes contraires.

Par exemple, le polynôme P = X 8 − 3X 5 + 2X 4 + X 2 − X − 1 présente 3 changements de signe.

Notons s le nombre de changements de signe de P .

La règle de Descartes affirme que le nombre r de racines réelles strictement positives de P est

inférieur ou égal à s, et plus précisément que la différence s − r est un entier pair.

Par exemple, cette règle permet d’affirmer que le polynôme P = X 8 − 3X 5 + 2X 4 + X 2 − X − 1

possède ou bien trois ou bien une seule racine(s) réelle(s) strictement positive(s).

Appliquée a P (−X), cette regle donne une indication sur les racines réelles strictement négatives.

Avec notre exemple, P (−X) = X 8 + 3X 5 + 2X 4 + X 2 + X − 1 présente un seul changement de signe.

Le polynôme P possède donc exactement une racine réelle strictement négative.

1. Écrire une fonction varsign donnant le nombre de changements de polynôme P .

[ S ]

2. Écrire une fonction rootsup donnant un majorant du nombre de racines de P strictement

supérieures à un réel donné a. On utilisera la syntaxe rootsup(P, a).

[ S ]

3. Écrire une fonction rootinf donnant un majorant du nombre de racines de P strictement

inférieures à un réel donné a. On utilisera la syntaxe rootinf(P, a).

[ S ]

c(cid:13)EduKlub S.A.

Page 5

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Énoncé

V. Méthode de Newton de résolution de P (x) = 0

Soit f : I ⊂ R → R, de classe Ck (k ≥ 1). La méthode de Newton consiste à chercher une

solution x de f (x) = 0 en formant une suite définie par x0 ∈ I et par ∀ n ∈ N, xn+1 = xn −

Dans la suite de cette question f est un polynôme P à coefficients réels.

La convergence n’est pas assurée (sauf vers la plus grande racine réelle α de P si x0 > α.)

La vitesse de convergence est quadratique vers une racine simple, et linéaire vers une racine multiple.

f (xn)

f 0(xn)

.

1. Écrire une fonction newton donnant xn+1 connaissant P et xn.

On utilisera évidemment une schéma de Horner pour évaluer P (xn) et P 0(xn).

On fera en sorte que ces deux schémas soient menés en parallèle.

[ S ]

2. On peut songer a appliquer la méthode de Newton a la fraction rationnelle f =

Ses zéros sont ceux de P et ils sont tous simples.

P

P 0 .

Cela assure une vitesse de convergence au moins quadratique pour toutes les racines de P .

Dans ce cas on doit donc utiliser la relation : xn+1 = xn −

P (xn)P 0(xn)

P 02(xn) − P (xn)P 00(xn)

.

Écrire alors une fonction newton2 donnant xn+1 connaissant P et xn. On fera en sorte que les

calculs de P (xn), P 0(xn), P 00(xn) soient menés en parallèle.

[ S ]

VI. Forme de Newton du polynôme interpolateur

Soit F une famille de n points Ak(xk, yk) du plan, avec 1 ≤ k ≤ n, d’abscisses xk distinctes.

On sait qu’il existe un polynôme unique P , de degré ≤ n−1, tel que P (xk) = yk pour tout k.

Il y a plusieurs façons d’écrire ce polynôme interpolateur, dont la forme de Newton.

Elle consiste à écrire P dans la base H1, H2, . . . , Hn de Rn−1[X] définie par :

H1 = 1, H2 = X −x1, H3 = (X −x1)(X −x2),

. . . , Hn = (X −x1)(X −x2) · · · (X −xn−1)

Le problème est double :

– Calculer les coordonnées de P sur la base H1, H2, . . . , Hn.

– Connaissant ces coordonnées, évaluer P en un point quelconque.

C’est dans ce deuxieme probleme qu’intervient un schéma de Horner.

1. Pour 1 ≤ i ≤ j ≤ n, on définit récursivement les coefficients di,j de la manière suivante :

Pour tout i de {1, . . . , n}, di,i = yi. Si i < j, on pose di,j =

Écrire une fonction dij calculant le coefficient d’indice i, j.

La syntaxe sera dij(X, Y, i, j) où X, Y sont les tableaux des abscisses et ordonnées.

La fonction dij utilisera bien sûr la définition récursive des coefficients di,j.

[ S ]

di+1,j − di,j−1

xj − xi

.

c(cid:13)EduKlub S.A.

Page 6

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Énoncé

2. Avec les notations ci-dessus, on montre que P = d1,1H1 + d1,2H2 + · · · + d1,nHn.

Écrire une fonction pnewton formant le tableau [d1,1, d1,2, . . . , d1,n] à partir des tableaux X, Y

(tous les deux indicés de 1 à n) des abscisses et ordonnées.

La fonction pnewton s’appuiera essentiellement sur la fonction dij qui calcule les coefficients

di,j (et en particulier les d1,k) de façon récursive.

[ S ]

3. La méthode précédente a un défaut : des calculs intermédiaires sont effectués plusieurs fois.

D’autre part, on voit bien qu’il suffit ici de calculer les seuls coefficients d1,k.

Écrire une procédure PNewton calculant le tableau [d1,1, d1,2, . . . , d1,n].

On n’utilisera pas la fonction récursive dij. Au contraire les coefficients d1,k seront calculés par

une méthode itérative. Voici une indication sur les premières étapes du calcul :

– On part du tableau Y = [d1,1, d2,2, . . . , dn,n].

– La première étape transforme ce tableau en [d1,1, d1,2, . . . , dj,j+1, . . . , dn−1,n].

– L’étape suivante conduit à [d1,1, d1,2, d1,3, . . . , dj,j+2, . . . , dn−2,n], etc.

A la n−1-ième étape, on aboutit donc au tableau [d1,1, d1,2, d1,3, . . . , , d1,n].

On utilisera la syntaxe PNewton(X, Y ). Les calculs seront faits dans le tableau Y .

[ S ]

4. Avec la forme du Newton, il est très facile d’ajouter un nouveau point A0(x0, y0).

Écrire une fonction newpoint passant du polynôme interpolateur P de (x1, y1), . . . , (xn, yn)

(écrit sous sa forme de Newton) à celui des n + 1 points (x0, y0), (x1, y1), . . . , (xn, yn).

Avec la syntaxe newpoint(X, P, x0, y0), où X est la liste des n abscisses initiales, le résultat

sera le tableau de la forme de Newton du polynôme interpolant A0, . . . , An.

[ S ]

5. Écrire une fonction evalnewton calculant la valeur en un point x quelconque du polynôme

d’interpolation P des n points Ak(xk, yk). La syntaxe sera evalnewton(X, P, x), où X est la

liste des n absicsses et où P est le tableau de taille n représentant la forme de Newton du

polynôme interpolateur.

[ S ]

VII. Autour du théorème chinois

Dans cette partie (réservée aux éleves de MP*), on s’intéresse au “théoreme chinois”.

– Soient m, n dans N∗, avec m ∧ n = 1. On sait qu’il existe une infinité de couples (u, v) de Z2 tel

que um + vn = 1. On dit que u et v sont des coefficients de Bezout de m et n.

Il existe en particulier un couple (u, v) unique tel que |u| ≤ n

Il est obtenu par l’algorithme d’Euclide (divisions successives) appliqué au couple (m, n).

2 et |v| ≤ m

2 .

– On se donne r entiers strictement positifs n1, n2, . . . , nr premiers entre eux deux à deux.

Soit n =

r

Q

k=1

nk. On considère l’application ϕ de Z/nZ dans

r

Q

k=1

Z/nkZ définie par :

∀ x ∈ Z/nZ, ϕ(x) = (x mod n1, x mod n2, . . . , x mod nr)

c(cid:13)EduKlub S.A.

Page 7

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Cette application est un morphisme d’anneaux, injectif car son noyau est réduit à 0.

Il est donc bijectif pour des raisons de cardinal.

En particulier, pour tous entiers a1, . . . , ar : ∃ ! x ∈ [ 0, . . . , n−1 ],

Ce résultat est communément appelé théorème chinois.

1. Calcul des coefficients de Bezout.

Énoncé

(S)







x mod n1 = a1

x mod n2 = a2

. . .

x mod nr = ar

(a) Écrire une fonction récursive bezout recevant les entiers positifs m, n et renvoyant dans un

tableau [u, v, u ∧ v] les coefficients u, v tels que um + vn = u ∧ v. Pour cela, et si m = nq + r

est la division de m par n, on notera comment passer d’un couple de coefficients de Bezout

de (n, r) à un couple de coefficients de Bezout de (m, n).

[ S ]

(b) Écrire une version itérative de la fonction bezout.

Indication : considérer les équations (Eδ) : am + bn = δ, d’inconnue (a, b) dans Z2.

Le triplet (1, 0) est solution de (Em), et (0, 1) est solution de (En).

Soit α = qβ + r la division euclidienne d’un entier α par un entier β.

On suppose que (a1, b1) est solution de (Eα) et que (a2, b2) est solution de (Eβ).

On remarque alors que (a1 − qa2, b1 − qb2) est solution de (Er).

[ S ]

2. Solution d’un système de congruences

(a) Pour tous i, j de {1, . . . , r} (avec i 6= j) on note ui,j et uj,i tels que ui,j ni + uj,i nj = 1.

Pour tout j de {1, . . . , r}, on note Mj = Q

ui,j ni, et on pose x =

i6=j

(cid:17)

ajMj

(cid:16) r

P

j=1

mod n.

Montrer que l’entier x est l’unique solution du système (S).

Écrire une fonction chinese calculant x (syntaxe chinese([a1, . . . , ar], [n1, . . . , nr]).

[ S ]

(b) Dans cette question, on calcule la solution x, au moyen de deux schémas de Horner.

On pose b1 = a1, puis b2 = (a2 − b1)u1,2 mod n2, etc, et finalement

br = [([(ar − b1)u1,r − b2]u2,r − b3) · · · − br−1] ur−1,r mod nr

Montrer que la solution x du système (S) s’écrit x =

(cid:16)

r

P

k=1

bk

k−1

Q

i=1

(cid:17)

.

ni

Vérifier que x peut être calculé en utilisant un schéma de Horner.

En déduire une nouvelle version de la fonction chinese.

Remarque : Cette deuxième méthode a l’avantage de minimiser le nombre de “modulos”

[ S ]

à calculer, et de ne produire aucun calcul intermédiaire qui sortirait de [0, . . . , n−1].

VIII. Algorithmes “compte-gouttes”

Dans cette section, on étudie des algorithmes permettant de déterminer une à une les décimales de

e et de π. Connus sous le nom d’algorithmes “compte-gouttes”, leur particularité est de n’utiliser

que l’arithmétique des “petits” entiers, et de donner une à une les décimales successives du nombre

considéré sans réutiliser les décimales déja calculées. Ces algorithmes operent une conversion d’un

c(cid:13)EduKlub S.A.

Page 8

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Énoncé

systeme de numération “a base variable” vers la numération décimale (ou en base 10p si on veut p

chiffres a la fois.) Cette conversion s’effectue en utilisant des calculs “a la Horner”.

1. Une numération à base variable, adaptée au nombre e

On note B l’ensemble des suites d’entiers (bn)n≥1 telles que

– Pour tout n ≥ 2, bn ∈ {0, . . . , n − 1}, mais b1 est quelconque dans Z.

– Pour tout n ≥ 1, il existe m ≥ n tel que bm < n − 1.

On va voir que tout x s’écrit d’une manière unique x =

On pourra alors noter x = (b1, b2, . . . , bn, . . .)b.

On peut comparer ce développement avec la représentation décimale.

Notons en effet D l’ensemble des suites d’entiers (dn)n≥1 telles que

– Pour tout n ≥ 2, dn ∈ {0, . . . , 9}, mais d1 est quelconque dans Z.

– Pour tout n ≥ 1, il existe m ≥ n tel que dm < 9.

∞

P

n=1

bn

n! , où la suite (bn) est dans B.

On sait qu’on a une unique écriture x =

∞

P

n=1

dn

10n−1 , où la suite (dn)n≥1 est dans D.

Plus précisément, on a d1 = [x] et, pour tout n ≥ 2, dn = [10n−1x] mod 10.

Ce qui distingue les deux types de numération, c’est que l’écriture décimale utilise la base

fixe d = 10 (et on décompose sur des puissances successives de 1/10n) alors que l’écriture

x = (b1, b2, . . . , bn, . . .)b utilise une “base” variable 1, 2, 3, . . ., et une décomposition sur les 1/n!

∞

P

k=2

Un algorithme de conversion de la base variable b a la base 10 (ou mieux a une base 10p),

permettra donc de récupérer les chiffres décimaux du nombre e.

(a) Soit (bn)n≥1 une suite de B. Montrer que P

1

k! c’est-à-dire e = (2, 1, 1, . . . , 1, . . .)b.

Evidemment pour e = exp(1), on a : e = 2 +

bk

k! converge. On note x sa somme.

bk

k! .

bk

k! (par convention, x0 = 0) et rn =

k≥1

∞

P

k=n+1

n

P

k=1

Pour tout n ≥ 0, on pose xn =

Montrer que pour tout n de N∗, on a : 0 ≤ rn < 1

n!

En déduire que b1 = [x] et, pour tout n ≥ 2, bn = [n!x] − n!xn−1 = [n!x] mod n.

[ S ]

(b) Soit x un nombre réel.

∀ n ≥ 1, xn =

n

P

k=1

Montrer qu’il existe une suite unique (bn)n≥1 de B telle que x =

bk

k! .

bk

k! est alors une valeur approchée de x par défaut à 1

n

bk

P

k! à partir du tableau B = [b1, . . . , bn].

k=1

n! près.

[ S ]

∞

P

k=1

(c) Écrire une fonction todec calculant xn =

On utilisera la syntaxe todec(B, n), sans vérifier si le tableau B est correct. [ S ]

(d) Écrire une fonction tovar renvoyant B = [b1, . . . , bn] à partir de xn =

On utilisera la syntaxe tovar(xn, n).

[ S ]

n

P

k=1

bk

k! .

c(cid:13)EduKlub S.A.

Page 9

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Énoncé

2. Le calcul des décimales du nombre e

(a) Soit x un nombre réel. On sait que x s’écrit de manière unique x =

Pour tout n ≥ 2, on note xn =

n

P

k=1

bk

k! = (b1, b2, . . . , bn)b.

+∞

P

k=1

bk

k! avec (bn) ∈ B.

Soit m dans N∗. On se propose de trouver la partie entière de 10mxn =

Il est bien sûr possible d’écrire 10mxn = (10m b1, 10m b2, . . . , 10m bn)b.

Mais dans cette écriture, les 10m bk (pour k ≥ 2) ne sont en général pas dans {0, . . . , k−1}.

On doit donc convertir cette écriture vers la base B.

Notons 10mxn = (r1, r2, . . . , rn)b l’écriture de 10mxn dans cette base.

Imaginer un algorithme permettant de passer de (b1, b2, . . . , bn)b à (r1, r2, . . . , rn)b.

Indication : procéder par divisions successives avec report de retenue, de bn à b2.

[ S ]

.

n

P

k=1

10m bk

k!

(b) Écrire une procédure goutte :

– Prenant en argument le tableau X = [b1, b2, . . . , bn] et l’entier m ≥ 1.

– Plaçant le tableau [r1, r2, . . . , rn] dans la variable X.

Remarque : cette méthode donne en particulier la partie entière r1 de 10mxn.

[ S ]

(c) Montrer l’inégalité 1

n! < 10−(n+1) pour n ≥ 27. En déduire une fonction chiffres e

donnant les n premieres décimales de e, avec la syntaxe chiffres e(n, m), le parametre

m indiquant que les décimales sont obtenues par blocs de m chiffres successifs.

Le résultat sera donné sous la forme d’une chaˆıne de caractères.

[ S ]

3. Le calcul des décimales de π

On admet l’égalité suivante : π

Le terme général de cette série s’écrit uk = 1 · 2 · 3 ··· k

(cid:16)

2 =

(k!)2 2k

(2k+1)!.

(cid:16)

+∞

P

k=0

3 · 5 · 7 ··· (2k+1).

1 + 3

1 + 2

7

5

(cid:16)

Ainsi π

3 + 1 · 2

2 = 1 + 1

3 · 5 + 1 · 2 · 3

3 · 5 · 7 + · · · = 1 + 1

On peut donc considérer le systeme de numération P a base variable 1, 1

Dans ce système de numération, on a visiblement : π = (2, 2, 2, 2, . . .)P.

Plus généralement, on considère des développements de la forme suivante :

9 (1 + · · ·)

1 + 4

3

(cid:17)(cid:17)(cid:17)

.

3 · 5 , 1 · 2 · 3

3 , 1 · 2

3 · 5 · 7, . . .

x =

+∞

P

k=0

pk uk = p0 +

+∞

P

k=1

pk

1 · 2 · 3 ··· k

3 · 5 · 7 ··· (2k+1) = p0 + 1

3

(cid:16)

p1 + 2

5

(cid:16)

p2 + 3

7

(cid:16)

p3 + 4

9 (p4 + · · ·)

(cid:17)(cid:17)(cid:17)

On notera x = (p0, p1, p2, . . .)P le réel représenté par ce développement infini, avec p0 ∈ Z.

On dit qu’un tel développement est régulier si pk ∈ {0, . . . , 2k}, pour tout k ≥ 1, et si pour

tout entier n ≥ 1, il existe m ≥ n tel que pm < 2k.

On notera alors xn = (p0, p1, p2, . . . , pn−1, 0, 0, . . .)P, pour tout n ≥ 1.

c(cid:13)EduKlub S.A.

Page 10

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Énoncé

(a) Montrer qu’un développement régulier (0, p1, p2, p3, . . .)P converge vers un réel de [0, 2[.

La partie entiere de (p0, p1, p2, p3, . . .)P est donc égale a p0 ou à p0 + 1.

Montrer qu’il n’y a pas unicité de la représentation d’un réel x dans le système P.

[ S ]

(b) Écrire une fonction todec2 calculant xn =

pk uk à partir de X = [p0, . . . , pn−1].

On utilisera la syntaxe todec2(X), sans vérifier si le tableau X est correct.

[ S ]

n−1

P

k=0

(c) Soit xn = (p0, p1, p2, . . . , pn−1, 0, . . .)P la somme d’un développement régulier fini.

Soit m un entier strictement positif. Imaginer un algorithme permettant d’obtenir un

développement régulier de 10mxn.

[ S ]

(d) Ecrire une fonction goutte2, comme celle de la question (2b), réalisant la conversion

étudiée à la question précédente. Vérifier qu’une application répétée de cette fonction

donne par exemple les 30 premières décimales de π21 = (2, 2, 2, . . . , 2)P = 2

(e) On sait que π = 2

uk. Pour tout m ≥ 1, on pose πm = 2

+∞

P

k=0

Vérifier que 0 < π − πm < 4um (observer que uk < 1

Montrer en outre que um est strictement inférieur à 2

En déduire que si m ≥ 10

3 n, alors 0 < π − πm < 5 · 10−n.

2uk−1 pour tout k ≥ 1.)

3 2−m, pour m ≥ 1.

[ S ]

20

P

k=0

uk.

[ S ]

m−1

P

k=0

uk.

(f) Déduire de ce qui précede une fonction chiffres pi donnant les n premieres décimales

de π, avec la syntaxe chiffres pi(n, m), le paramètre m indiquant que les décimales sont

calculées par groupes de m chiffres consécutifs.

Le résultat sera donné sous la forme d’une chaˆıne de caractères.

[ S ]

c(cid:13)EduKlub S.A.

Page 11

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Corrigé

Corrigé

I. Évaluation d’un polynôme

Deux versions de l’algorithme de Horner :

1. Le polynôme P =

n

P

k=0

akX k est représenté par le tableau P = [an, an−1, . . . , a1, a0].

Le calcul de y = P (t) s’effectue en posant d’abord y = 0, puis successivement :

y ← yt + an = an,

y ← yt + an−2 = ant2 + an−1t + an−2, . . . ,

y ← yt + an−1 = ant + an−1,

y ← yt + a0 = P (t)

Voici donc la fonction itérative evalh qui calcule y = P (t) :

> evalh:=proc(P::array(numeric),t::numeric)

>

>

>

> end:

local y,k; y:=0;

for k to size (P) do y:=y*t+P[k] od; # boucle de calcul de y = P (t)

RETURN(y)

renvoie la valeur calculée

initialisation

On calcule ici la valeur du polynôme P = 3X 4 − 5X 2 + 2X + 1 au point t = 100 :

> P:=array([3,0,-5,2,1]): evalh(P,100);

299950201

Il est clair que l’algorithme précédent nécessite n additions et n multiplications.

[ Q ]

2. Soit P =

n

P

k=0

akX k, et le quotient Q =

n−1

P

k=0

ak+1X k dans la division de P par X.

Pour tout réel t, on a donc y = P (t) = tQ(t) + a0.

Les polynômes P et Q sont représentés par les tableaux

(cid:26) P = [an, an−1, . . . , a2, a1, a0]

Q = [an, an−1, . . . , a2, a1]

On voit que pour calculer y = P (t), il suffit de calculer z = Q(t) et de poser y = tz + a0.

Pour évaluer Q(t), on peut encore utiliser le tableau initial P , à condition de se limiter aux

n + 1 premiers coefficients, c’est-a-dire a an, an−1, . . . , a2, a1.

Il en découle la fonction evalhr, version récursive de l’algorithme de Horner.

Tout le travail est effectué par la fonction locale h, qui utilise toujours le tableau P représentant

le polynôme initial, mais qui reçoit en argument la longueur du sous-tableau de P représentant

l’un polynômes quotients successifs. Pour calculer y = P (t), il suffit donc d’un appel initial à

cette fonction locale, en lui transmettant la taille du tableau P .

> evalhr:=proc(P::array(numeric),t::numeric)

>

>

>

>

>

> end:

end:

RETURN(h(size(P)));

if m=1 then P[1] else h(m-1)*t+P[m] fi;

appel initial, sur tout la longueur de P

local h;

h:=proc(m)

c(cid:13)EduKlub S.A.

Page 12

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation

individuelle et privée sont interdites.

www.klubprepa.net

Jean-Michel Ferrard

Algorithmique avec Maple

Variations sur le schéma de Horner

Corrigé

On reprend l’exemple qui a servi à illustrer la version récursive de l’algorithme :

> P:=array([3,0,-5,2,1]): evalhr(P,100);

299950201

Remarque : si on s’en tient aux directives des concepteurs de la nouvelle épreuve d’informatique

de l’X, on doit éviter d’emboˆıter les fonctions. Il faut donc “sortir” la fonction locale h.

Une premiere solution est de réécrire la fonction evalhr de la maniere suivante, en modifiant la

syntaxe d’appel et en confiant donc à l’utilisateur le soin de préciser la taille du tableau initial :

> evalhr2:=proc(P::array(numeric),n::integer,t::numeric)

>

> end:

On reprend encore le même exemple (remarquer que les syntaxes d’appel sont différentes.)

> P:=array([3,0,-5,2,1]): evalhr2(P,5,100);

if n<=1 then P[1] else evalhr2(P,n-1,t)*t+P[n] fi;

[ Q ]

299950201

3. Voici la fonction evalhc, directement calquée sur la version itérative de evalh.

local u,v,k,t; u:=0; v:=0;

for k to size(P) do

On utilise les variables locales u et v pour désigner la partie réelle et la partie imaginaire du

nombre complexe qui finira par être égal à P (x + iy).

> evalhc:=proc(P::array(numeric),x::numeric,y::numeric)

>

>

>

>

>

> end:

On calcule ici P (−11 + 8i), avec P = 3X 4 − 5X 2 + 2X + 1.

> P:=array([3,0,-5,2,1]): evalhc(P,-11,8);

od;

RETURN(array([u,v]))

t:=ux-vy+P[k]; v:=uy+vx; u:=t;

[−83487, −59296]

On vérifie tout de même que le résultat est correct :

> p:=x->evalc(3x^4-5x^2+2x+1): p(-11+8I);

−83487 − 59296I

On voit que l’algorithme précédent nécessite 3n additions et 4n multiplications de réels.

[ Q ]

4. Posons r = 2Re (z) = 2x et m = |z|2 = x2 + y2.

Considérons la division du polynôme P =

n

P

k=0

akX k par B = (X − z)(X − ¯z) = X 2 − rX + m.

Cette division euclidienne s’écrit P = (X 2 − rX + m)

n−2

P

k=0

bk+2X k + b1X + b0.

Avec ces notations, on a bien sûr P (z) = b1z + b0 = (b1x + b0) + ib1y.

c(cid:13)EduKlub S.A.

Page 13

Tous droits de l’auteur des œuvres réservés. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consul...