2.5 Accélération par la méthode d’Aitken
65
On peut appliquer la méthode d’Aitken à toute méthode de point
fixe. On a en effet le théorème suivant :
Théorème 2.2 Soit x
(k+1) = φ(x
(k) ) les itérations de point fixe
(2.17) avec φ(x) = x − f(x) pour approcher les racines de f. Si f
est suffisamment régulière on a :
- si les itérations de point fixe convergent linéairement vers une racine simple de f, alors la méthode d’Aitken converge quadratiquement vers la même racine ;
- si les itérations de points fixe convergent avec un ordre p ≥ 2 vers
une racine simple de f, alors la méthode d’Aitken converge vers
la même racine avec un ordre 2p − 1 ;
- si les itérations de point fixe convergent linéairement vers une
racine de f de multiplicité m ≥ 2, alors la méthode d’Aitken
converge linéairement vers la même racine avec un coefficient
de convergence asymptotique C = 1 − 1/m.
En particulier, si p = 1 et si la racine de f est simple, la méthode
d’extrapolation d’Aitken converge même si la méthode de point fixe
correspondante diverge.
On propose dans le Programme 2.4 une implémentation de la méthode d’Aitken. Ici phi est une fonction (ou une fonction inline) qui
définit l’expression de la fonction d’itération associée à la méthode de
point fixe à laquelle on applique la méthode d’extrapolation d’Aitken. La
donnée initiale est définie par la variable x0, tandis que tol et nmax sont
respectivement le tolérance pour le critère d’arrêt (valeur absolue de la
différence entre deux itérées successives) et le nombre maximal d’itérations. Si ces quantités ne sont pas définies, elles prennent les valeurs par
défaut nmax=100 et tol=1.e-04.
Programme 2.4. aitken : méthode d’Aitken
function [x , niter ]= aitken ( phi , x0 , tol , nmax , varargin )
% AITKEN E x t r apo lati on d ’ Aitken
%
[ ALPHA , NITER ]= AITKEN ( PHI , X0) calcule une
%
a p p r oxi mati on d ’ un point fixe ALPHA d ’ une fonction
%
PHI en partant de la donnée initiale X0 à l ’ aide de
%
la méthode d ’ e x t r apol ati on d ’ Aitken . L ’ a l g o ri thme
%
s ’ arrête après 100 i t é r ations ou quand la valeur
%
absolue de la d i f f éren ce entre deux itérées
%
c o n s écut ives est plus petite que 1.e -04. PHI doit
%
être définie comme une fonction , une fonction
%
inline , une fonction anonyme ou un M - fichier .
%
[ ALPHA , NITER ]= AITKEN ( PHI ,X0 , TOL , NMAX ) permet de
%
définir la t o l éran ce pour le critère d ’ arrêt et le
%
nombre maximal d ’ i t é ra tions.
65
On peut appliquer la méthode d’Aitken à toute méthode de point
fixe. On a en effet le théorème suivant :
Théorème 2.2 Soit x
(k+1) = φ(x
(k) ) les itérations de point fixe
(2.17) avec φ(x) = x − f(x) pour approcher les racines de f. Si f
est suffisamment régulière on a :
- si les itérations de point fixe convergent linéairement vers une racine simple de f, alors la méthode d’Aitken converge quadratiquement vers la même racine ;
- si les itérations de points fixe convergent avec un ordre p ≥ 2 vers
une racine simple de f, alors la méthode d’Aitken converge vers
la même racine avec un ordre 2p − 1 ;
- si les itérations de point fixe convergent linéairement vers une
racine de f de multiplicité m ≥ 2, alors la méthode d’Aitken
converge linéairement vers la même racine avec un coefficient
de convergence asymptotique C = 1 − 1/m.
En particulier, si p = 1 et si la racine de f est simple, la méthode
d’extrapolation d’Aitken converge même si la méthode de point fixe
correspondante diverge.
On propose dans le Programme 2.4 une implémentation de la méthode d’Aitken. Ici phi est une fonction (ou une fonction inline) qui
définit l’expression de la fonction d’itération associée à la méthode de
point fixe à laquelle on applique la méthode d’extrapolation d’Aitken. La
donnée initiale est définie par la variable x0, tandis que tol et nmax sont
respectivement le tolérance pour le critère d’arrêt (valeur absolue de la
différence entre deux itérées successives) et le nombre maximal d’itérations. Si ces quantités ne sont pas définies, elles prennent les valeurs par
défaut nmax=100 et tol=1.e-04.
Programme 2.4. aitken : méthode d’Aitken
function [x , niter ]= aitken ( phi , x0 , tol , nmax , varargin )
% AITKEN E x t r apo lati on d ’ Aitken
%
[ ALPHA , NITER ]= AITKEN ( PHI , X0) calcule une
%
a p p r oxi mati on d ’ un point fixe ALPHA d ’ une fonction
%
PHI en partant de la donnée initiale X0 à l ’ aide de
%
la méthode d ’ e x t r apol ati on d ’ Aitken . L ’ a l g o ri thme
%
s ’ arrête après 100 i t é r ations ou quand la valeur
%
absolue de la d i f f éren ce entre deux itérées
%
c o n s écut ives est plus petite que 1.e -04. PHI doit
%
être définie comme une fonction , une fonction
%
inline , une fonction anonyme ou un M - fichier .
%
[ ALPHA , NITER ]= AITKEN ( PHI ,X0 , TOL , NMAX ) permet de
%
définir la t o l éran ce pour le critère d ’ arrêt et le
%
nombre maximal d ’ i t é ra tions.