2.2 Méthode de dichotomie (ou bisection)
47
si f(a
(k−1) )f(x
(k−1) ) < 0
poser a
(k) = a
(k−1) , b
(k) = x
(k−1) ;
si f(x
(k−1) )f(b
(k−1) ) < 0
poser a
(k) = x
(k−1) , b
(k) = b
(k−1) .
On définit alors x
(k) = (a
(k) + b
(k) )/2 et on incrémente k de 1.
Par exemple, dans le cas présenté sur la Figure 2.2, qui correspond à
f(x) = x
2
− 1, en prenant a
(0) = −0.25 et b
(0) = 1.25, on obtient
I
(0) =] − 0.25, 1.25[, x
(0) = 0.5,
I
(1) =]0.5, 1.25[,
x
(1) = 0.875,
I
(2) =]0.875, 1.25[, x
(2) = 1.0625,
I
(3) =]0.875, 1.0625[, x
(3) = 0.96875.
Remarquer que chaque sous-intervalle I
(k) contient le zéro α. De plus,
la suite {x
(k)
} converge nécessairement vers α puisqu’à chaque étape
la longueur |I
(k)
| = b
(k)
− a
(k) de I
(k) est divisée par deux. Comme
|I
(k)
| = (1/2)
k
|I
(0)
|, l’erreur à l’étape k vérifie
|e
(k)
| = |x
(k)
− α| <
1
2
|I
(k)
| =
1
2
k+1
(b − a).
Pour garantir que |e
(k)
| < ε, pour une tolérance ε donnée, il suffit d’effectuer k min itérations, où k min est le plus petit entier tel que
k min > log 2
b − a
ε
− 1
(2.6)
Noter que cette inégalité est générale : elle ne dépend pas du choix de la
fonction f.
La méthode de dichotomie est implémentée dans le Programme 2.1 :
fun est une chaîne de caractères (ou une fonction inline) définissant la
fonction f, a et b sont les extrémités de l’intervalle de recherche, tol est
la tolérance ε et nmax est le nombre maximal d’itérations. La fonction
fun peut avoir, en plus du premier argument, des paramètres auxiliaires.
Les paramètres de sortie sont zero, qui contient la valeur approchée
de α, le résidu res qui est la valeur de f en zero et niter qui est le
nombre total d’itérations effectuées. La commande find(fx==0) ren- find
voie les indices des composantes nulles du vecteur fx, et la commande
sign(fx) renvoie le signe de fx. Enfin, la commande varargin permet sign
varargin
à la fonction fun d’accepter un nombre variable de paramètres d’entrée.
47
si f(a
(k−1) )f(x
(k−1) ) < 0
poser a
(k) = a
(k−1) , b
(k) = x
(k−1) ;
si f(x
(k−1) )f(b
(k−1) ) < 0
poser a
(k) = x
(k−1) , b
(k) = b
(k−1) .
On définit alors x
(k) = (a
(k) + b
(k) )/2 et on incrémente k de 1.
Par exemple, dans le cas présenté sur la Figure 2.2, qui correspond à
f(x) = x
2
− 1, en prenant a
(0) = −0.25 et b
(0) = 1.25, on obtient
I
(0) =] − 0.25, 1.25[, x
(0) = 0.5,
I
(1) =]0.5, 1.25[,
x
(1) = 0.875,
I
(2) =]0.875, 1.25[, x
(2) = 1.0625,
I
(3) =]0.875, 1.0625[, x
(3) = 0.96875.
Remarquer que chaque sous-intervalle I
(k) contient le zéro α. De plus,
la suite {x
(k)
} converge nécessairement vers α puisqu’à chaque étape
la longueur |I
(k)
| = b
(k)
− a
(k) de I
(k) est divisée par deux. Comme
|I
(k)
| = (1/2)
k
|I
(0)
|, l’erreur à l’étape k vérifie
|e
(k)
| = |x
(k)
− α| <
1
2
|I
(k)
| =
1
2
k+1
(b − a).
Pour garantir que |e
(k)
| < ε, pour une tolérance ε donnée, il suffit d’effectuer k min itérations, où k min est le plus petit entier tel que
k min > log 2
b − a
ε
− 1
(2.6)
Noter que cette inégalité est générale : elle ne dépend pas du choix de la
fonction f.
La méthode de dichotomie est implémentée dans le Programme 2.1 :
fun est une chaîne de caractères (ou une fonction inline) définissant la
fonction f, a et b sont les extrémités de l’intervalle de recherche, tol est
la tolérance ε et nmax est le nombre maximal d’itérations. La fonction
fun peut avoir, en plus du premier argument, des paramètres auxiliaires.
Les paramètres de sortie sont zero, qui contient la valeur approchée
de α, le résidu res qui est la valeur de f en zero et niter qui est le
nombre total d’itérations effectuées. La commande find(fx==0) ren- find
voie les indices des composantes nulles du vecteur fx, et la commande
sign(fx) renvoie le signe de fx. Enfin, la commande varargin permet sign
varargin
à la fonction fun d’accepter un nombre variable de paramètres d’entrée.