216
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
ne garantit pas la r´ eduction monotone de l’erreur absolue d’une it´ eration `
a
l’autre. Autrement dit, on ne peut pas assurer a priori que
|e
(k+1)
| ≤ M k |e
(k)
|
pour tout k ≥ 0,
(6.10)
avec M k < 1. Comme la propri´ et´ e (6.10) n’est pas satisfaite, la m´ ethode de
dichotomie n’est pas une m´ ethode d’ordre 1 au sens de la D´ efinition 6.1.
Exemple 6.3 V´ erifions les propri´ et´ es de convergence de la m´ ethode de dichotomie pour l’approximation de la racine α = 0.9062 . . . du polynˆ ome de Legendre de
degr´ e 5,
L5(x) =
x
8
(63x
4 − 70x
2 + 15),
dont les racines se situent dans l’intervalle ] − 1, 1[ (voir Section 9.1.2). On ex´ ecute
le Programme 42 en prenant a = 0.6, b = 1 (donc L5(a) · L5(b) < 0), nmax =
100, tol = 10
−10 . La convergence est obtenue en 32 it´ erations, conform´ ement `
a
l’estimation th´ eorique (6.9) (m ≥ 31.8974). L’historique de la convergence rapport´ ee
sur la Figure 6.1 (` a droite) montre que l’erreur est r´ eduite (en moyenne) d’un facteur
deux et que la suite {x
(k) } a un comportement oscillant.
•
La lente convergence de la m´ ethode de dichotomie sugg` ere de n’utiliser cet algorithme que pour s’approcher de la racine. En effet, apr` es quelques it´ erations
de dichotomie, on obtient une approximation raisonnable de α qu’on peut utiliser comme point de d´ epart pour une m´ ethode d’ordre sup´ erieur qui fournira
alors une convergence rapide vers la solution avec une pr´ ecision donn´ ee. Nous
pr´ esenterons un exemple de cette technique ` a la Section 13.3.
L’algorithme de dichotomie est impl´ ement´ e en MATLAB dans le Programme 42. Les param` etres en entr´ ee, ici et dans le reste du chapitre, sont
les suivants : a et b sont les extr´ emit´ es de l’intervalle de recherche, fun est la
variable contenant l’expression de la fonction f, tol est une tol´ erance fix´ ee et
nmax le nombre maximum d’it´ erations.
En sortie, les vecteurs xvect, xdif et fx contiennent respectivement les
suites {x
(k)
}, {|x
(k+1)
−x
(k)
|} et {f(x
(k) )}, pour k ≥ 0, tandis que nit d´ esigne
le nombre d’it´ erations n´ ecessaire ` a satisfaire le crit` ere d’arrˆ et. Dans le cas
de la m´ ethode de dichotomie, le code s’arrˆ ete d` es que la demi-longueur de
l’intervalle est inf´ erieure ` a tol.
Programme 42 - bisect : M´ ethode de dichotomie
function [xvect,xdif,fx,nit]=bisect(a,b,tol,nmax,fun)
%BISECT M´ ethode de dichotomie
% [XVECT,XDIF,FX,NIT]=BISECT(A,B,TOL,NMAX,FUN) tente de trouver un z´ ero
% de la fonction continue FUN sur l’intervalle [A,B] en utilisant la
% m´ ethode de dichotomie. FUN accepte une variable r´ eelle scalaire x et
% renvoie une valeur r´ eelle scalaire.
% XVECT est le vecteur des it´ er´ ees, XDIF est le vecteur des diff´ erences
% entre it´ er´ ees cons´ ecutives, FX est le r´ esidu. TOL est la tol´ erance de
% la m´ ethode.
6 R´ esolution des ´ equations et des syst` emes non lin´ eaires
ne garantit pas la r´ eduction monotone de l’erreur absolue d’une it´ eration `
a
l’autre. Autrement dit, on ne peut pas assurer a priori que
|e
(k+1)
| ≤ M k |e
(k)
|
pour tout k ≥ 0,
(6.10)
avec M k < 1. Comme la propri´ et´ e (6.10) n’est pas satisfaite, la m´ ethode de
dichotomie n’est pas une m´ ethode d’ordre 1 au sens de la D´ efinition 6.1.
Exemple 6.3 V´ erifions les propri´ et´ es de convergence de la m´ ethode de dichotomie pour l’approximation de la racine α = 0.9062 . . . du polynˆ ome de Legendre de
degr´ e 5,
L5(x) =
x
8
(63x
4 − 70x
2 + 15),
dont les racines se situent dans l’intervalle ] − 1, 1[ (voir Section 9.1.2). On ex´ ecute
le Programme 42 en prenant a = 0.6, b = 1 (donc L5(a) · L5(b) < 0), nmax =
100, tol = 10
−10 . La convergence est obtenue en 32 it´ erations, conform´ ement `
a
l’estimation th´ eorique (6.9) (m ≥ 31.8974). L’historique de la convergence rapport´ ee
sur la Figure 6.1 (` a droite) montre que l’erreur est r´ eduite (en moyenne) d’un facteur
deux et que la suite {x
(k) } a un comportement oscillant.
•
La lente convergence de la m´ ethode de dichotomie sugg` ere de n’utiliser cet algorithme que pour s’approcher de la racine. En effet, apr` es quelques it´ erations
de dichotomie, on obtient une approximation raisonnable de α qu’on peut utiliser comme point de d´ epart pour une m´ ethode d’ordre sup´ erieur qui fournira
alors une convergence rapide vers la solution avec une pr´ ecision donn´ ee. Nous
pr´ esenterons un exemple de cette technique ` a la Section 13.3.
L’algorithme de dichotomie est impl´ ement´ e en MATLAB dans le Programme 42. Les param` etres en entr´ ee, ici et dans le reste du chapitre, sont
les suivants : a et b sont les extr´ emit´ es de l’intervalle de recherche, fun est la
variable contenant l’expression de la fonction f, tol est une tol´ erance fix´ ee et
nmax le nombre maximum d’it´ erations.
En sortie, les vecteurs xvect, xdif et fx contiennent respectivement les
suites {x
(k)
}, {|x
(k+1)
−x
(k)
|} et {f(x
(k) )}, pour k ≥ 0, tandis que nit d´ esigne
le nombre d’it´ erations n´ ecessaire ` a satisfaire le crit` ere d’arrˆ et. Dans le cas
de la m´ ethode de dichotomie, le code s’arrˆ ete d` es que la demi-longueur de
l’intervalle est inf´ erieure ` a tol.
Programme 42 - bisect : M´ ethode de dichotomie
function [xvect,xdif,fx,nit]=bisect(a,b,tol,nmax,fun)
%BISECT M´ ethode de dichotomie
% [XVECT,XDIF,FX,NIT]=BISECT(A,B,TOL,NMAX,FUN) tente de trouver un z´ ero
% de la fonction continue FUN sur l’intervalle [A,B] en utilisant la
% m´ ethode de dichotomie. FUN accepte une variable r´ eelle scalaire x et
% renvoie une valeur r´ eelle scalaire.
% XVECT est le vecteur des it´ er´ ees, XDIF est le vecteur des diff´ erences
% entre it´ er´ ees cons´ ecutives, FX est le r´ esidu. TOL est la tol´ erance de
% la m´ ethode.