Livre_silo 30 août 2013 16:32 Page 205
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
205
8 – Résolution numérique d’équations sur les réels
exemple étudier la fonction g : x →
1
2
(
x +
2
x
)
. Elle stabilise [
√
2, +∞[ et, sur cet
intervalle, g(x) ⩽ x, avec égalité si et seulement si x =
√
2 ; etc.
Le fait que la dérivée de g en x 0 =
√
2 soit nulle est fondamental : c’est grâce à cela
qu’ on a une vitesse de convergence élevée. En effet, en posant δ n = u n −
√
2, on a
δ n+1
δ n
=
g(u n ) − g(x 0 )
u n − x 0
−→
n→+∞
g
′ (x 0 ), donc plus |g
′ (x 0 )| est faible, meilleure est la vitesse de convergence. Ici, on a même plus précisément δ n+1 =
δ
2
n
2x n
⩽
δ
2
n
2
; on dit que la
convergence est quadratique, ou d’ordre 2.
newton.pdf
Figure 8.3
Les deux premières itérations du calcul approché de
√
2 par la méthode de Newton. Difficile de
visualiser au delà !
Exercice 8.3 Avec les majorations précédentes, à partir de quel n est-on certain d’avoir |δn| ⩽
1
2 1000
(autrement dit les 1 000 premiers bits significatifs de
√
2) ?
On a δ 1 ⩽
1
2
, donc 0 ⩽ δ 2 ⩽
1
2 2 (on a laissé de côté un facteur
1
2
), puis 0 ⩽ δ 3 ⩽
1
2 4 , puis par
récurrence immédiate : 0 ⩽ δn ⩽
1
2 n−1 pour tout n ⩾ 1. Pour avoir |δn| ⩽
1
2 1000 , il suffit donc
d’avoir 2 n−1 ⩾ 1000, c’est-à-dire n ⩾ 11. Relisez la conclusion : en 11 itérations, on obtient 1 000 bits
significatifs ; spectaculaire, non ?
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
205
8 – Résolution numérique d’équations sur les réels
exemple étudier la fonction g : x →
1
2
(
x +
2
x
)
. Elle stabilise [
√
2, +∞[ et, sur cet
intervalle, g(x) ⩽ x, avec égalité si et seulement si x =
√
2 ; etc.
Le fait que la dérivée de g en x 0 =
√
2 soit nulle est fondamental : c’est grâce à cela
qu’ on a une vitesse de convergence élevée. En effet, en posant δ n = u n −
√
2, on a
δ n+1
δ n
=
g(u n ) − g(x 0 )
u n − x 0
−→
n→+∞
g
′ (x 0 ), donc plus |g
′ (x 0 )| est faible, meilleure est la vitesse de convergence. Ici, on a même plus précisément δ n+1 =
δ
2
n
2x n
⩽
δ
2
n
2
; on dit que la
convergence est quadratique, ou d’ordre 2.
newton.pdf
Figure 8.3
Les deux premières itérations du calcul approché de
√
2 par la méthode de Newton. Difficile de
visualiser au delà !
Exercice 8.3 Avec les majorations précédentes, à partir de quel n est-on certain d’avoir |δn| ⩽
1
2 1000
(autrement dit les 1 000 premiers bits significatifs de
√
2) ?
On a δ 1 ⩽
1
2
, donc 0 ⩽ δ 2 ⩽
1
2 2 (on a laissé de côté un facteur
1
2
), puis 0 ⩽ δ 3 ⩽
1
2 4 , puis par
récurrence immédiate : 0 ⩽ δn ⩽
1
2 n−1 pour tout n ⩾ 1. Pour avoir |δn| ⩽
1
2 1000 , il suffit donc
d’avoir 2 n−1 ⩾ 1000, c’est-à-dire n ⩾ 11. Relisez la conclusion : en 11 itérations, on obtient 1 000 bits
significatifs ; spectaculaire, non ?