6.2 Une approche g´ eom´ etrique de la d´ etermination des racines
219
f(x)
y
f(x)
x
(−1)
x
(0)
x
x
(1)
x
(2)
y
x
(0)
x
x
(−1)
x
(1)
x
(2)
x
(2)
Sec
Fig. 6.3. Les deux premi` eres ´ etapes de la m´ ethode de la fausse position pour deux
fonctions diff´ erentes
f(x
(k) ) < 0. Plus pr´ ecis´ ement, une fois trouv´ ees deux valeurs x
(−1) et x
(0)
telles que f(x
(−1) ) · f(x
(0) ) < 0, on pose
x
(k+1) = x
(k)
−
x
(k)
− x
(k
)
f(x (k) ) − f(x (k ) )
f(x
(k) )
∀k ≥ 0.
(6.15)
Ayant fix´ e une tol´ erance absolue ε, les it´ erations (6.15) se terminent `
a l’´ etape
m quand |f(x
(m) )| < ε. Remarquer que la suite d’indice k
est croissante ; pour
trouver la nouvelle valeur de k
` a l’it´ eration k, on peut donc s’arrˆ eter ` a la valeur
k
d´ etermin´ ee ` a l’´ etape pr´ ec´ edente, ´ evitant ainsi de parcourir l’ensemble des
valeurs ant´ erieures de la suite. Nous montrons sur la Figure 6.3 (` a gauche) les
deux premi` eres ´ etapes de (6.15) dans le cas particulier o` u x
(k
) co¨ ıncide avec
x
(−1) pour tout k ≥ 0.
La m´ ethode de la fausse position, bien qu’ayant la mˆ eme complexit´ e que la
m´ ethode de la s´ ecante, a une convergence lin´ eaire (voir, par exemple, [RR78]
p. 339-340). N´ eanmoins, contrairement ` a la m´ ethode de la s´ ecante, les it´ er´ ees construites par (6.15) sont toutes contenues dans l’intervalle de d´ epart
[x
(−1) , x
(0) ].
Sur la Figure 6.3 (` a droite), on a repr´ esent´ e les deux premi` eres it´ erations
des m´ ethodes de la s´ ecante et de la fausse position obtenues en partant des
mˆ emes donn´ ees initiales x
(−1) et x
(0) . Remarquer que la valeur x
(1) calcul´ ee
par la m´ ethode de la s´ ecante co¨ ıncide avec celle calcul´ ee par la m´ ethode de la
fausse position, tandis que la valeur x
(2) obtenue avec la m´ ethode de la s´ ecante
(not´ ee x
(2)
Sec ) se trouve ` a l’ext´ erieur de l’intervalle de recherche [x
(−1) , x
(0) ].
La m´ ethode de la fausse position peut ˆ etre vue comme une m´ ethode globalement convergente, tout comme celle de dichotomie.
219
f(x)
y
f(x)
x
(−1)
x
(0)
x
x
(1)
x
(2)
y
x
(0)
x
x
(−1)
x
(1)
x
(2)
x
(2)
Sec
Fig. 6.3. Les deux premi` eres ´ etapes de la m´ ethode de la fausse position pour deux
fonctions diff´ erentes
f(x
(k) ) < 0. Plus pr´ ecis´ ement, une fois trouv´ ees deux valeurs x
(−1) et x
(0)
telles que f(x
(−1) ) · f(x
(0) ) < 0, on pose
x
(k+1) = x
(k)
−
x
(k)
− x
(k
)
f(x (k) ) − f(x (k ) )
f(x
(k) )
∀k ≥ 0.
(6.15)
Ayant fix´ e une tol´ erance absolue ε, les it´ erations (6.15) se terminent `
a l’´ etape
m quand |f(x
(m) )| < ε. Remarquer que la suite d’indice k
est croissante ; pour
trouver la nouvelle valeur de k
` a l’it´ eration k, on peut donc s’arrˆ eter ` a la valeur
k
d´ etermin´ ee ` a l’´ etape pr´ ec´ edente, ´ evitant ainsi de parcourir l’ensemble des
valeurs ant´ erieures de la suite. Nous montrons sur la Figure 6.3 (` a gauche) les
deux premi` eres ´ etapes de (6.15) dans le cas particulier o` u x
(k
) co¨ ıncide avec
x
(−1) pour tout k ≥ 0.
La m´ ethode de la fausse position, bien qu’ayant la mˆ eme complexit´ e que la
m´ ethode de la s´ ecante, a une convergence lin´ eaire (voir, par exemple, [RR78]
p. 339-340). N´ eanmoins, contrairement ` a la m´ ethode de la s´ ecante, les it´ er´ ees construites par (6.15) sont toutes contenues dans l’intervalle de d´ epart
[x
(−1) , x
(0) ].
Sur la Figure 6.3 (` a droite), on a repr´ esent´ e les deux premi` eres it´ erations
des m´ ethodes de la s´ ecante et de la fausse position obtenues en partant des
mˆ emes donn´ ees initiales x
(−1) et x
(0) . Remarquer que la valeur x
(1) calcul´ ee
par la m´ ethode de la s´ ecante co¨ ıncide avec celle calcul´ ee par la m´ ethode de la
fausse position, tandis que la valeur x
(2) obtenue avec la m´ ethode de la s´ ecante
(not´ ee x
(2)
Sec ) se trouve ` a l’ext´ erieur de l’intervalle de recherche [x
(−1) , x
(0) ].
La m´ ethode de la fausse position peut ˆ etre vue comme une m´ ethode globalement convergente, tout comme celle de dichotomie.