28
Analyse num´ erique et ´ equations diff´ erentielles
La fonction ϕ(s) = |s(s − 1) . . . (s − n)|, s ∈ [0, n], v´ erifie ϕ(n − s) = ϕ(s), donc elle
atteint son maximum dans
0,
n
2
. Comme ϕ(s − 1)/ϕ(s) = (n + 1 − s)/s > 1 pour
1 ≤ s ≤
n
2 , on voit que ϕ atteint en fait son maximum dans [0, 1], d’o` u
max
[0,n]
ϕ = max
s∈[0,1]
ϕ(s) ≤ n!
Il en r´ esulte
|f (x) − p n (x)| ≤ h
n+1
·
1
n + 1
max
[x0,...,xn]
|f
(n+1)
|.
Une application typique de ces formules est le calcul d’une valeur approch´ ee de
l’image f (x) au moyen d’une table num´ erique donnant les valeurs successives f (x i )
avec un pas constant h. Supposons par exemple que h = 10
−2 et que l’on cherche
` a ´ evaluer f (x) `
a 10
−8 pr` es. Une interpolation lin´ eaire (cas n = 1) donnerait une
erreur en h
2 = 10
−4 beaucoup trop grande. On doit ici aller jusqu’au degr´ e n = 3,
ce qui permet d’obtenir un erreur ≤ h
4 = 10
−8 pourvu que max |f
(4)
| ≤ 4.
Remarque – D’apr` es l’expression de π n+1 donn´ ee plus haut, on voit que
π n+1 [a,b] = h
n+1 max
s∈[0,n]
ϕ(s) ≤ h
n+1 n! =
n!
n n+1 (b − a)
n+1
et la formule de Stirling n! ∼
√
2πn
n
e
n montre que l’ordre de grandeur de π n+1
est
π n+1 = O
b − a
e
n+1
quand n → +∞.
Comme
ϕ
1
2
=
1
2
·
1
2
·
3
2
. . .
n −
1
2
≥
1
4
1 · 2 . . . (n − 1)
≥
1
4n
n! ≥
1
4n
√
6n
n
n
e n ≥
n
n− 1
2
e n+1
pour n grand, on voit en fait que
π n+1 ≥ h
n+1 n
n− 1
2
e n+1 =
1
n 3/2
b − a
e
n+1
.
Nous obtiendrons au § 2.2 des estimations beaucoup plus pr´ ecises. L’exercice suivant
montre l’int´ erˆ et de la formule de Newton en arithm´ etique.
Exercice
(a) Montrer que les polynˆ omes de Newton
N k (s) =
s(s − 1) . . . (s − k + 1)
k!
, 0 ≤ k ≤ n
forment une base de P n et que pour tout s ∈ Z on a N k (s) ∈ Z
[Indication : utiliser les C
k
n ou une r´ ecurrence `
a partir de la relation
N k (s) − N k (s − 1) = N k−1 (s)].
(b) Montrer qu’un polynˆ ome p ∈ P n est tel que p(s) ∈ Z pour tout s ∈ Z si et
seulement si p est combinaison lin´ eaire `
a coefficients dans Z de N 0 , . . . , N n .
Analyse num´ erique et ´ equations diff´ erentielles
La fonction ϕ(s) = |s(s − 1) . . . (s − n)|, s ∈ [0, n], v´ erifie ϕ(n − s) = ϕ(s), donc elle
atteint son maximum dans
0,
n
2
. Comme ϕ(s − 1)/ϕ(s) = (n + 1 − s)/s > 1 pour
1 ≤ s ≤
n
2 , on voit que ϕ atteint en fait son maximum dans [0, 1], d’o` u
max
[0,n]
ϕ = max
s∈[0,1]
ϕ(s) ≤ n!
Il en r´ esulte
|f (x) − p n (x)| ≤ h
n+1
·
1
n + 1
max
[x0,...,xn]
|f
(n+1)
|.
Une application typique de ces formules est le calcul d’une valeur approch´ ee de
l’image f (x) au moyen d’une table num´ erique donnant les valeurs successives f (x i )
avec un pas constant h. Supposons par exemple que h = 10
−2 et que l’on cherche
` a ´ evaluer f (x) `
a 10
−8 pr` es. Une interpolation lin´ eaire (cas n = 1) donnerait une
erreur en h
2 = 10
−4 beaucoup trop grande. On doit ici aller jusqu’au degr´ e n = 3,
ce qui permet d’obtenir un erreur ≤ h
4 = 10
−8 pourvu que max |f
(4)
| ≤ 4.
Remarque – D’apr` es l’expression de π n+1 donn´ ee plus haut, on voit que
π n+1 [a,b] = h
n+1 max
s∈[0,n]
ϕ(s) ≤ h
n+1 n! =
n!
n n+1 (b − a)
n+1
et la formule de Stirling n! ∼
√
2πn
n
e
n montre que l’ordre de grandeur de π n+1
est
π n+1 = O
b − a
e
n+1
quand n → +∞.
Comme
ϕ
1
2
=
1
2
·
1
2
·
3
2
. . .
n −
1
2
≥
1
4
1 · 2 . . . (n − 1)
≥
1
4n
n! ≥
1
4n
√
6n
n
n
e n ≥
n
n− 1
2
e n+1
pour n grand, on voit en fait que
π n+1 ≥ h
n+1 n
n− 1
2
e n+1 =
1
n 3/2
b − a
e
n+1
.
Nous obtiendrons au § 2.2 des estimations beaucoup plus pr´ ecises. L’exercice suivant
montre l’int´ erˆ et de la formule de Newton en arithm´ etique.
Exercice
(a) Montrer que les polynˆ omes de Newton
N k (s) =
s(s − 1) . . . (s − k + 1)
k!
, 0 ≤ k ≤ n
forment une base de P n et que pour tout s ∈ Z on a N k (s) ∈ Z
[Indication : utiliser les C
k
n ou une r´ ecurrence `
a partir de la relation
N k (s) − N k (s − 1) = N k−1 (s)].
(b) Montrer qu’un polynˆ ome p ∈ P n est tel que p(s) ∈ Z pour tout s ∈ Z si et
seulement si p est combinaison lin´ eaire `
a coefficients dans Z de N 0 , . . . , N n .