acceleration de la convergence - Roland Groux

ACCELERATION DE LA CONVERGENCE. A) INTRODUCTION. Soit l une constante réelle que l'on se propose d'évaluer à l'aide d'un
algorithme adéquat.
On enclenche le processus qui au bout d'un certain temps nous fournit une
première série d'approximations de l, soit : [pic]
A ce stade des opérations il peut apparaître que la poursuite des calculs
ne soit pas rentable et ceci pour diverses raisons : . Des causes mathématiques. La structure de l'algorithme peut conduire à une convergence dite
'lente'.
C'est le cas par exemple lorsque l'écart [pic] est équivalent au
voisinage de +( à un multiple de [pic] ou pire à un multiple de [pic].
Cette notion de lenteur est relative et se définit ici par comparaison au
schéma géométrique classique.
On préférera en effet une majoration du type [pic] avec 0 ( q ( 1 à une
convergence dictée par [pic] avec ( (0 , car au voisinage de ( : [pic] et
par suite le coût pour approcher l à ( près sera donc moins élevé. . Des causes liées à la machine utilisée. Les erreurs d'arrondis peuvent conduire si la structure de l'Algorithme est
trop instable, à des débordements notoires par rapport au comportement
théorique prévu, et même amener à des divergences grossières.
Cette notion de stabilité est aussi délicate à définir proprement. Un
schéma directif assez large consiste à faire des hypothèses simplifiées sur
la propagation de l'erreur afin d'en déduire un modèle statistique que l'on
teste ensuite sur des exemples. Pour faire face aux faiblesses signalées on dispose alors essentiellement
de deux stratégies fondamentales. > Modifier l'algorithme initial pour le rendre plus performant. > Combiner astucieusement les approximations déjà évaluées pour former
[pic]
approchant mieux l que xn. Par exemple pour un procédé d'itérations successives à l'aide d'une
fonction f on pourra chercher à remplacer f par g dont le contact avec la
constante 'l ' est meilleur que celui de f ou bien après avoir obtenu un
développement asymptotique de xn, on essaiera par un barycentrage bien
choisi d'éliminer les termes dont la convergence est la plus lente.
De premier abord ces deux techniques diffèrent. > La première est de type global, on agit sur le procédé, le c?ur même de
l'Algorithme.
C'est une refonte totale. > La deuxième est de type discret, on agit sur les fruits successifs de
l'Algorithme.
C'est un affinage par retouches, sans changer le moule essentiel. Le lecteur un peu averti ne sera pourtant pas surpris de découvrir que dans
un bon nombre de cas les deux stratégies se rejoignent, venant ainsi
renforcer le caractère universel de la recherche Algorithmique.
Ainsi pour le cas des images répétées par une fonction f on sait que les
valeurs des dérivées successives de f en l conditionnent le développement
asymptotique de xn.[pic] Dans ce qui suit nous nous proposons de développer ces idées à travers une
approche progressive du mode d'accélération le plus classique : la méthode
d'Aitken - Romberg. B) LA METHODE D'AITKEN-ROMBERG. L'Algorithme analysé est supposé fournir une suite de termes [pic]
convergent vers l et supposés tous distincts de l. 1. On suppose ici que le procédé est du type itératif : (n (N [pic] , avec
f satisfaisant aux hypothèses du schéma classique du point fixe.
(Contractante sur un intervalle stable pour f ).
On sait alors que plus f est ' plate' au voisinage de l, plus rapide sera
la convergence vers le point fixe l de f.
D'où l'idée, si [pic] est non nul et connu , de remplacer f par g
construite à partir de f et satisfaisant à [pic]. La manière la plus simple est de chercher g dans le faisceau engendré par
f et l'identité, c'est-à-dire du type : [pic] Si k ( 1 on obtient bien une solution définie par la formule : [pic]
Si k est connu donc et si la fonction f a fourni les images [pic], la
suite de terme général [pic] va converger vers l plus rapidement que xn. En effet : [pic] et [pic]
On a donc bien [pic], et donc [pic] On verra en annexe quelques exercices illustrant cette méthode
élémentaire ne s'appliquant, insistons, que si la valeur de [pic] est
connue sans référence à l . 2. On suppose ici que l'Algorithme utilisé fait apparaître un développement
asymptotique du type : [pic] , avec a constante réelle non nulle et
[pic] Par décalage, au rang n+1 il vient alors : [pic]
Puis par combinaison linéaire : [pic]
Ici encore donc, et si q est connu distinct de 1, la suite de terme
général [pic] va converger vers l plus rapidement que xn puisque [pic]
et que [pic]( [pic] Cet équilibrage s'adapte bien aux suites du type [pic] avec les
conditions suivantes : f deux fois dérivable en 0 ; [pic]; A ( 0 et
[pic]
En effet partant du développement d'ordre 2 : [pic], on obtient aussitôt:
( n (N : [pic]
D'où la convergence rapide de [pic] vers [pic]
(Comme exemple d'application on pourra voir le problème sur la formule de
Viète .) 3. Plus généralement xn désigne simplement une suite convergente vers l,
sans autre indication que ( n (N xn (l. On cherche alors à améliorer la convergence par un équilibrage du type :
[pic] , A désignant ici une constante non nulle choisie arbitrairement. ( n (N : [pic]
On voit alors clairement que [pic] ne peut être négligeable devant [pic]
au voisinage de +( que si le rapport [pic] converge vers un réel k ( 1 et
que si on prend [pic]
Le terme yn est alors donné par : [pic] Dans ces trois études dont le cadre s'élargit à chaque étape, la même
formule apparaît, mais le regard porté sur la constante k s'est modifié. Au
début c'est une simple constante dépendant de l'Algorithme donné, le nombre
dérivé[pic]. Puis son interprétation comme constante asymptotique se
dessine, k semble plus lié à la suite des approximations qu'à la méthode de
création de celles-ci. La nuance est bien sûr faible, l'Algorithme
conditionne toujours ce qu'il engendre, mais elle est d'importance pour ce
qui va suivre: Le nombre k s'inscrit dans la suite qui s'élabore.
Tout est maintenant en place pour franchir le principal écueil rencontré ci
dessus : que faire lorsque la valeur de k nous est inconnue ? La réponse repose dans le constat précédent: puisque k prend corps à
travers la construction de la suite des valeurs approchées de l, on peut
essayer d'utiliser les valeurs fournies par l'Algorithme pour approcher
cette inconnue fondamentale. Entrons dans le détail. . Dans le premier cas des images successives par f, remarquons que si f est
supposée de classe C1 au voisinage de l ou plus simplement si [pic] est
supposée continue en l, on aura en vertu du théorème des accroissements
finis : [pic]
On pourra donc approcher k par les rapports [pic] convergent vers k en
l'infini.
Si on pose [pic] on aura encore convergence de zn vers le point fixe l.
La condition [pic] assure en effet que les kn seront distincts de 1 pour
n assez grand.
De plus la relation [pic] assure une convergence plus rapide que celle
de xn puisque [pic]
On aura donc bien [pic] puisque l'on est toujours sous l'hypothèse k (1 . Dans le cadre de l'évaluation asymptotique de xn, soit : [pic]
Remarquons que le quotient [pic] s'écrit alors : [pic] On aura donc encore ici : [pic] (1. (Les kn sont donc distincts de 1 pour n
assez grand).
De plus : [pic]( q en + (, ce qui montre qu'ici aussi la suite définie par
la formule [pic] converge vers l plus vite que xn. . Enfin dans le cadre plus général d'une suite quelconque convergent vers
l, nous utiliserons le résultat classique suivant obtenu dans la théorie
des séries numériques et démontré plus loin en annexe:
[pic]
Ce théorème assure que si on pose [pic]on aura encore: [pic]
Il suffit de reprendre le schéma : [pic] La Formule d'Aitken. C'est l'explicitation de la suite auxiliaire accélérée [pic], émergent dans
les trois études précédentes, lorsqu'on remplace kn par son expression
[pic]. Après simplifications il vient simplement : [pic] ( Aitken) . Expression à l'aide de l'opérateur des différences premières. Rappelons la définition de l'opérateur ( agissant sur le R espace S des
suites de réels:
( u ( S , [pic] est la suite de terme général [pic] La composée [pic] transforme u en w telle que [pic] On en déduit que pour tout entier n: [pic]
Remarquons alors que zn peut s'exprimer aussi comme :[pic]
D'où, en utilisant (, la formule : [pic] . Interprétation géométrique. Dans le plan affine Euclidien muni du repère orthonormé (O ; [pic],
[pic]) considérons la suite de points de coordonnées : [pic]
Rappelons que les termes xn sont supposés distincts deux à deux! La
droite [pic] admet alors comme équation cartésienne [pic]
Remarquons que m n'est autre que le coefficient [pic] supposé toujours
différent de 1. L'intersection de cette droite avec la première bissectrice des axes
d'équation [pic]
est donc le point In d'abscisse : [pic] La méthode d'accélération d'Aitken s'interprète donc géométriquement
comme un procédé d'interpolation linéaire. On retrouve cet éclairage dans la méthode dite de Steffensen (appelée
aussi Aitken-diagonal) que l'on trouvera exposée un peu plus loin. Théorème. Toute suite de réels telle que [pic] avec [pic] converge vers un
réel l et on a alors: [pic] La convergence est obtenue facilement avec le critère de Dallambert
appliquée à la série de terme général [pic].
Celui-ci, puisque [pic] avec [pic], assure la convergence absolue, donc la
convergence des sommes partielles [pic]
Pour la formule donnant la limite des quotients des écarts avec l nous
distinguerons trois cas. . Si 0 ( k (1 Choisissons deux réels k1 et k2 encadrant k et tels que [pic]
Posons pour faciliter la rédaction [pic]
L'hypothèse implique l'existence d'un rang n0 à partir duquel tous ces
rapports qn seront é