acceleration de la convergence - Roland Groux
... qui au bout d'un certain temps nous fournit une première série d'
approximations de l, soit : ..... telle que et la série entière associée , de rayon de
convergence égal à 1. ..... Cette confirmation viendra par le biais du sujet qui
nous préoccupe ...
part of the document
uation.3 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 INCORPORER Equation.3 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 cur 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. INCORPORER Equation.3
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.
LA METHODE D'AITKEN-ROMBERG.
L'Algorithme analysé est supposé fournir une suite de termes INCORPORER Equation.3 convergent vers l et supposés tous distincts de l.
On suppose ici que le procédé est du type itératif : (n (N INCORPORER Equation.3 , 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 INCORPORER Equation.3 est non nul et connu , de remplacer f par g construite à partir de f et satisfaisant à INCORPORER Equation.3 . La manière la plus simple est de chercher g dans le faisceau engendré par f et l'identité, c'est-à-dire du type : INCORPORER Equation.3 Si k ( 1 on obtient bien une solution définie par la formule : INCORPORER Equation.3 Si k est connu donc et si la fonction f a fourni les images INCORPORER Equation.3 , la suite de terme général INCORPORER Equation.3 va converger vers l plus rapidement que xn. En effet : INCORPORER Equation.3 et INCORPORER Equation.3 On a donc bien INCORPORER Equation.3 , et donc INCORPORER Equation.3 On verra en annexe quelques exercices illustrant cette méthode élémentaire ne s'appliquant, insistons, que si la valeur de INCORPORER Equation.3 est connue sans référence à l .
On suppose ici que l'Algorithme utilisé fait apparaître un développement asymptotique du type : INCORPORER Equation.3 , avec a constante réelle non nulle et INCORPORER Equation.3 Par décalage, au rang n+1 il vient alors : INCORPORER Equation.3 Puis par combinaison linéaire : INCORPORER Equation.3 Ici encore donc, et si q est connu distinct de 1, la suite de terme général INCORPORER Equation.3 va converger vers l plus rapidement que xn puisque INCORPORER Equation.3 et que INCORPORER Equation.3 ( INCORPORER Equation.3 Cet équilibrage s'adapte bien aux suites du type INCORPORER Equation.3 avec les conditions suivantes : f deux fois dérivable en 0 ; INCORPORER Equation.3 ; A ( 0 et INCORPORER Equation.3 En effet partant du développement d'ordre 2 : INCORPORER Equation.3 , on obtient aussitôt: ( n (N : INCORPORER Equation.3 D'où la convergence rapide de INCORPORER Equation.3 vers INCORPORER Equation.3 (Comme exemple d'application on pourra voir le problème sur la formule de Viète .)
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 : INCORPORER Equation.3 , A désignant ici une constante non nulle choisie arbitrairement. ( n (N : INCORPORER Equation.3 On voit alors clairement que INCORPORER Equation.3 ne peut être négligeable devant INCORPORER Equation.3 au voisinage de +( que si le rapport INCORPORER Equation.3 converge vers un réel k ( 1 et que si on prend INCORPORER Equation.3 Le terme yn est alors donné par : INCORPORER Equation.3
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é INCORPORER Equation.3 . 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 INCORPORER Equation.3 est supposée continue en l, on aura en vertu du théorème des accroissements finis : INCORPORER Equation.3 On pourra donc approcher k par les rapports INCORPORER Equation.3 convergent vers k en l'infini. Si on pose INCORPORER Equation.3 on aura encore convergence de zn vers le point fixe l. La condition INCORPORER Equation.3 assure en effet que les kn seront distincts de 1 pour n assez grand. De plus la relation INCORPORER Equation.3 assure une convergence plus rapide que celle de xn puisque INCORPORER Equation.3 On aura donc bien INCORPORER Equation.3 puisque l'on est toujours sous l'hypothèse k (1
Dans le cadre de l'évaluation asymptotique de xn, soit : INCORPORER Equation.3 Remarquons que le quotient INCORPORER Equation.3 s'écrit alors : INCORPORER Equation.3
On aura donc encore ici : INCORPORER Equation.3 (1. (Les kn sont donc distincts de 1 pour n assez grand). De plus : INCORPORER Equation.3 ( q en + (, ce qui montre qu'ici aussi la suite définie par la formule INCORPORER Equation.3 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: INCORPORER Equation.3 Ce théorème assure que si on pose INCORPORER Equation.3 on aura encore: INCORPORER Equation.3 Il suffit de reprendre le schéma : INCORPORER Equation.3
La Formule d'Aitken.
C'est l'explicitation de la suite auxiliaire accélérée INCORPORER Equation.3 , émergent dans les trois études précédentes, lorsqu'on remplace kn par son expression INCORPORER Equation.3 . Après simplifications il vient simplement : INCORPORER Equation.3 ( 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 , INCORPORER Equation.3 est la suite de terme général INCORPORER Equation.3 La composée INCORPORER Equation.3 transforme u en w telle que INCORPORER Equation.3 On en déduit que pour tout entier n: INCORPORER Equation.3 Remarquons alors que zn peut s'exprimer aussi comme : INCORPORER Equation.3 D'où, en utilisant (, la formule : INCORPORER Equation.3
Interprétation géométrique. Dans le plan affine Euclidien muni du repère orthonormé (O ; INCORPORER Equation.3 , INCORPORER Equation.3 ) considérons la suite de points de coordonnées : INCORPORER Equation.3 Rappelons que les termes xn sont supposés distincts deux à deux! La droite INCORPORER Equation.3 admet alors comme équation cartésienne INCORPORER Equation.3 Remarquons que m n'est autre que le coefficient INCORPORER Equation.3 supposé toujours différent de 1. L'intersection de cette droite avec la première bissectrice des axes d'équation INCORPORER Equation.3 est donc le point In d'abscisse : INCORPORER Equation.3 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 INCORPORER Equation.3 avec INCORPORER Equation.3 converge vers un réel l et on a alors: INCORPORER Equation.3
La convergence est obtenue facilement avec le critère de Dallambert appliquée à la série de terme général INCORPORER Equation.3 . Celui-ci, puisque INCORPORER Equation.3 avec INCORPORER Equation.3 , assure la convergence absolue, donc la convergence des sommes partielles INCORPORER Equation.3
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 INCORPORER Equation.3 Posons pour faciliter la rédaction INCORPORER Equation.3 L'hypothèse implique l'existence d'un rang n0 à partir duquel tous ces rapports qn seront éléments de l'intervalle [k1, k2]. On en déduit par multiplications que ( n ( n0 et ( p (N* : INCORPORER Equation.3 Par sommations on en déduit facilement que ( n ( n0 et ( p (N : INCORPORER Equation.3 Laissons n fixe et faisons tendre p vers l'infini. En explicitant les limites on obtient l'encadrement : INCORPORER Equation.3 On en déduit INCORPORER Equation.3 , puis INCORPORER Equation.3 A partir d'un certain rang n0 on est donc sûr que les quotients INCORPORER Equation.3 vont rentrer dans l'intervalle [k1, k2]. Or vu le choix arbitraire de k1 et k2 encadrant k, ces intervalles constituent un système fondamental de voisinages de k. On peut donc conclure conformément au schéma général de définition de limite, que l'on a bien l'égalité demandée : INCORPORER Equation.3 .
Si -1 (k ( 0
Nous reprendrons la méthode et les notations de l'étude précédente. Les modifications viennent des inversion des inégalités dans les produits puisqu'ici les quotients considérés seront négatifs.
On part en effet de k1 et k2 encadrant k et tels que INCORPORER Equation.3 A partir d'un certain rang n0 on a encore INCORPORER Equation.3 Lorsqu'on passe aux produits consécutifs et vu la balance des encadrements on aura donc: _ Si p impair : INCORPORER Equation.3 _ Si p est pair : INCORPORER Equation.3 Par sommations il vient alors si n (n0 et si p impair : INCORPORER Equation.3 En fixant n et en faisant tendre p vers l'infini on en déduit l'encadrement aux limites: INCORPORER Equation.3 Remarquons alors que les deux expressions encadrant INCORPORER Equation.3 ci dessus ont pour limite le même quotient INCORPORER Equation.3 lorsque le couple (k1, k2) tend vers (k, k). En effet INCORPORER Equation.3 On pourra donc, vu l'encadrement en question, faire rentrer à partir d'un certain rang les quotients INCORPORER Equation.3 dans tout voisinage imposé de INCORPORER Equation.3 Ceci se traduit simplement INCORPORER Equation.3 , dont on déduit facilement d'après les règles opératoires classiques : INCORPORER Equation.3
Si k=0
La stratégie diffère légèrement. Soit ( (0 donné et n0 un rang à partir duquel INCORPORER Equation.3 On a alors ( n ( n0 et ( p (N INCORPORER Equation.3 En sommant à partir de p =1 on en déduit : INCORPORER Equation.3 Supposons alors ( ( 1. En faisant tendre p vers l'infini il vient : INCORPORER Equation.3 Ceci pour tout n supérieur ou égal à n0. Le réel ( étant choisi arbitrairement tel que 0 ( ( (1, on peut donc écrire conformément au schéma classique de définition des limites, que INCORPORER Equation.3 On en déduit en passant à l'inverse que INCORPORER Equation.3 La translation par 1 suivie d'une dernière inversion donne enfin INCORPORER Equation.3
Méthode de Steffensen.
C'est le schéma des itérations successives accéléré par le procédé d'Aitken. On considère une fonction f contractante sur l'intervalle stable I, de point fixe l sur I.
Partant de x élément de I on commence par évaluer les images INCORPORER Equation.3 On arrête alors l'itération et on équilibre nos trois premières valeurs suivant la formule d'Aitken, ce qui nous donne : INCORPORER Equation.3 . Ceci bien sûr sous réserve d'un dénominateur non nul.
On redémarre les itérations à partir de y et on accélère comme précédemment et ainsi de suite tant que possible. L'algorithme peut donc se schématiser ainsi : INCORPORER Equation.3 INCORPORER Equation.3 INCORPORER Equation.3
..
D'où l'autre appellation de procédé diagonal d'Aitken.
On sait que la traduction géométrique est une simple interpolation linéaire. Le réel y , si défini, est l'abscisse du point d'intersection de la corde joignant les points de la courbe de f d'abscisses respectives x et f(x) avec la première bissectrice des axes. On pourra voir dans le problème intitulé 'méthode de Steffensen' que si f est décroissante et strictement convexe sur I, ce procédé diagonal peut se poursuivre à l'infini et converge toujours assez rapidement vers le point fixe l de f. Pour étudier cette rapidité remarquons que l'on a encore un procédé d'images successives, la fonction initiale f étant ici remplacée par g définie par la formule : INCORPORER Equation.3 Or, on peut montrer facilement que si f est de classe C1sur I, la condition INCORPORER Equation.3 suffit pour affirmer que g sera bien définie sur un voisinage de l privé de ce point. En effet la dérivée de INCORPORER Equation.3 , soit INCORPORER Equation.3 prend au point l la valeur INCORPORER Equation.3 . On en déduit qu'au voisinage de l : INCORPORER Equation.3 ( INCORPORER Equation.3 Ainsi il existe un réel ( (0 tel que : INCORPORER Equation.3 Or sur cette zone on peut écrire : INCORPORER Equation.3 En passant à la limite on obtient alors facilement INCORPORER Equation.3 La fonction g admet donc un prolongement continu et dérivable en l défini par g(l)=l Le point l fixe pour g est donc remarquablement attractif vu que INCORPORER Equation.3 , ce qui justifie la rapidité de l'algorithme diagonal.
Variante d'Aitken dans un schéma de point fixe.
Les exemples suivants correspondent à un schéma récurrent classique INCORPORER Equation.3 avec f contractante admettant l comme point fixe attractif ( INCORPORER Equation.3 ) sur un intervalle I. Cependant dans les situations examinées on peut expliciter facilement une fonction x ( ((x) telle que INCORPORER Equation.3 . La suite auxiliaire INCORPORER Equation.3 définie sûrement à partir d'un certain rang car le dénominateur à une limite non nulle en l'infini, converge alors encore vers l, et ceci plus rapidement que la suite initiale n (xn. En effet : INCORPORER Equation.3 et INCORPORER Equation.3 On a donc bien au voisinage de l'infini : INCORPORER Equation.3
INCORPORER Equation.3
Montrer que I=[0, 1] est stable pour la fonction cosinus.
Montrer que la fonction cosinus admet un seul point fixe sur I, noté l.
Montrer que pour tout entier n : INCORPORER Equation.3
Montrer que pour tout entier n : INCORPORER Equation.3 . Conclure la convergence de xn.
On pose alors pour tout n entier : INCORPORER Equation.3 Montrer que yn converge encore vers l plus rapidement que la suite xn.
INCORPORER Equation.3
Montrer que l'équation INCORPORER Equation.3 admet une et une seule solution notée l sur l'intervalle I=[3, 4]
Montrer que la suite n ( xn est croissante et que ( n (1 : INCORPORER Equation.3
Montrer que ( n (N INCORPORER Equation.3 . Conclure la convergence de xn.
On pose alors pour tout entier n : INCORPORER Equation.3
Montrer que yn converge encore vers l plus rapidement que la suite xn.
INCORPORER Equation.3
Montrer que l'équation INCORPORER Equation.3 admet une et une seule solution sur R, notée l.
Montrer que pour tout n ( 3 : INCORPORER Equation.3
Montrer que ( n (3 : INCORPORER Equation.3 . Conclure la convergence de xn.
On pose alors pour tout entier n : INCORPORER Equation.3 Montrer que yn converge encore vers l plus rapidement que la suite xn.
INCORPORER Equation.3
Montrer que pour tout entier n : INCORPORER Equation.3 Conclure la convergence de xn vers INCORPORER Equation.3
On pose alors pour tout entier n : INCORPORER Equation.3 Montrer que yn converge encore vers INCORPORER Equation.3 plus rapidement que la suite xn.
Dans les schémas précédents, l'accélération s'effectue donc simplement à partir de deux termes successifs de la suite, INCORPORER Equation.3 tandis que la méthode générale d'Aitken fait appel aux trois termes consécutifs INCORPORER Equation.3
Exemples d'accélération utilisant un développement à l'infini.
On considère ici la suite définie par : ( n (N INCORPORER Equation.3
Montrer qu'au voisinage de l'infini : INCORPORER Equation.3 En déduire la convergence de xn.
On pose alors pour tout entier n : INCORPORER Equation.3 Montrer qu'au voisinage de +( : yn - ln(2) ( INCORPORER Equation.3 Conclure que la convergence de yn vers ln(2) est plus rapide que celle de xn.
On considère ici la suite définie par ( n (N* : INCORPORER Equation.3
Montrer que ses termes peuvent s'évaluer de proche en proche à partir de la source x1=2 grâce à la relation : ( n (N* INCORPORER Equation.3
On rappelle le développement limité d'ordre 7 de la fonction sinus au voisinage de 0 : INCORPORER Equation.3 . En déduire qu'au voisinage de l'infini : INCORPORER Equation.3 Conclure la convergence de xn vers (.
On pose alors pour tout n ( 1 : INCORPORER Equation.3 Montrer qu'au voisinage de l'infini, INCORPORER Equation.3 ( INCORPORER Equation.3 En déduire la convergence plus rapide de yn vers (.
En généralisant l'accélération ci dessus, déterminer trois constantes (, (, ( telles que la suite INCORPORER Equation.3 converge encore vers ( plus rapidement que yn. au sens que l'écart entre zn et ( soit équivalent au voisinage de l'infini à un multiple de INCORPORER Equation.3 Les calculs doivent conduire à INCORPORER Equation.3 avec une évolution vers ( dictée par l'équivalence : INCORPORER Equation.3 ( INCORPORER Equation.3 Il est remarquable que le nombre INCORPORER Equation.3 approche déjà ( avec une erreur inférieure à 2.10-4
Théon de Smyrne, Bombelli et Héron d'Alexandrie.
Le principe d'accélération va nous permettre de jeter un pont entre trois procédés historiques d'approximation des racines carrées.
Théon de Smyrne. Vivant au deuxième siècle avant Jésus Christ, on lui attribue cet algorithme de manipulation de fractions sur fond d'égalité incomplète. Avec nos notations modernes cela se traduit par : INCORPORER Equation.3 . D'où la suite récurrente : ( n (N INCORPORER Equation.3 La méthode converge quelle que soit la source x0 (0. Plus précisément en remarquant que la suite auxiliaire INCORPORER Equation.3 est géométrique de raison INCORPORER Equation.3 , on obtient : INCORPORER Equation.3 Puisque INCORPORER Equation.3 on a bien INCORPORER Equation.3 pour limite, avec à l'infini : INCORPORER Equation.3 ( INCORPORER Equation.3
Bombelli.
Aux alentours de 1570, Bombelli emploie la technique suivante : Soit ( la racine carrée entière de a. (Plus grand entier de carré inférieur ou égal à a) On a alors INCORPORER Equation.3 , avec r inconnu satisfaisant à INCORPORER Equation.3 , ou encore à l'égalité INCORPORER Equation.3 . Bombelli imagine alors une suite de restes rn se rapprochant de ce r idéal et construits de proche en proche grâce à la relation INCORPORER Equation.3 Les termes INCORPORER Equation.3 sont quant à eux calculés par : INCORPORER Equation.3 . On a encore une convergence 'géométrique', de la même suite auxiliaire yn avec ici pour raison INCORPORER Equation.3 .
Héron d'Alexandrie. Ici l'idée est géométrique. On part d'un rectangle élémentaire de dimensions 1 et a. On va tenter par étapes successives de le rendre de plus en plus proche d'un carré tout en conservant son aire égale à a. Pour cela, à chaque nouveau tracé, on prendra pour une des dimensions la moyenne arithmétique des longueur et largeur de la figure précédente. On obtient alors la suite récurrente : INCORPORER Equation.3 Dans ce schéma la suite auxiliaire INCORPORER Equation.3 n'est plus géométrique mais vérifie ( n (N INCORPORER Equation.3 . D'où pour tout n INCORPORER Equation.3 et INCORPORER Equation.3 avec INCORPORER Equation.3
Liens entre les trois méthodes. On se rappelle que dans un schéma de point fixe, la convergence est d'autant plus rapide que le nombre dérivé en ce point est faible en valeur absolue. Les trois méthodes précédentes sont donc exposées par ordre croissant de performance. On va voir que le principe d'accélération permet de glisser du plus modeste au plus rapide.
Partons du procédé de Théon. La fonction f générant les images successives est localement contractante, car au point fixe INCORPORER Equation.3 on a INCORPORER Equation.3 avec INCORPORER Equation.3 Si on élargit le schéma de proportionnalité utilisé par Théon, on peut écrire pour tout ( réel : INCORPORER Equation.3 . Pour la fonction INCORPORER Equation.3 , le nombre dérivé au point fixe INCORPORER Equation.3 vaut INCORPORER Equation.3 . On a donc intérêt à choisir le paramètre ( le plus proche possible de la valeur inconnue INCORPORER Equation.3 Le choix de ( égal à la racine carré entière de a nous conduit alors à l'algorithme de Bombelli.
Reprenons maintenant l'idée essentielle de la méthode d'Aitken. Un algorithme étant lancé, donnant des approximations de INCORPORER Equation.3 , on peut utiliser les valeurs obtenues pour fignoler l'approche. Ainsi on peut songer à changer de coefficients ( au fur et à mesure que la méthode de Théon progresse. Cela suggère l'algorithme : INCORPORER Equation.3 On obtient alors la formule de Héron : INCORPORER Equation.3 Une autre voie aurait consisté à appliquer directement le procédé d'Aitken diagonal à la suite de Théon. Remarquons en effet pour trois termes consécutifs les égalités : INCORPORER Equation.3 . (La dernière si xn est toujours distinct de 1)
On en déduit INCORPORER Equation.3 Ainsi, suivant Aitken : convergence plus rapide pour INCORPORER Equation.3 La méthode de Héron se déduit bien de celle de Théon par le procédé de Steffensen. Remarquons pour finir que dans le cas d'une source INCORPORER Equation.3 , les termes de la suite de Héron sont extraits de celle de Théon car dans ce cas, suivant les notations précédentes : INCORPORER Equation.3 . Le terme de rang n dans Héron est donc celui de rang INCORPORER Equation.3 dans Théon.
Procéde d'Aitken et transformation d'Abel.
Nous considérons ici le cas d'une suite n ( an de réels non nuls telle que INCORPORER Equation.3 et la série entière associée INCORPORER Equation.3 , de rayon de convergence égal à 1. On se propose d'accélérer la convergence des sommes partielles notées INCORPORER Equation.3 . Puisque INCORPORER Equation.3 , on considérera pour INCORPORER Equation.3 conformément à la méthode d'Aitken, la suite auxiliaire notée ici INCORPORER Equation.3 .
Examinons cette combinaison.
INCORPORER Equation.3 Ceci grâce à la notation usuelle des différences premières : INCORPORER Equation.3 Plus généralement on notera pour tout couple (k, p): INCORPORER Equation.3 , conformément à l'action répétée de l'opérateur ( sur la suite initiale k (ak On sait donc que cette suite de terme général INCORPORER Equation.3 converge vers f(q) plus rapidement que la suite des sommes partielles n ( yn .
On rappelle alors la transformation dite d'Abel, véritable sommation 'par parties', utilisant ce même opérateur ( et les expressions INCORPORER Equation.3
INCORPORER Equation.3 Or : INCORPORER Equation.3 On en déduit donc : INCORPORER Equation.3 Le procédé d'Aitken rejoint donc la transformation d'Abel. INCORPORER Equation.3 On se rappelle qu'au voisinage de l'infini: INCORPORER Equation.3 , ce qui se traduit ici par l'équivalence : INCORPORER Equation.3 ( INCORPORER Equation.3 INCORPORER Equation.3
Nous allons maintenant répéter ce processus d'accélération. Pour une classe assez large de suites an , il arrive que l'on ait aussi : INCORPORER Equation.3 . C'est le cas par exemple pour INCORPORER Equation.3 ou an=F(n) avec F fraction rationnelle. On pose alors INCORPORER Equation.3 Soit INCORPORER Equation.3 De toute façon, même si la condition de limite 1 pour le quotient n'est pas conservée, la suite INCORPORER Equation.3 converge encore vers f(q) pour INCORPORER Equation.3 . En répétant la transformation initiale, on vérifie facilement qu'après un nombre p d'étapes on aura la formule : INCORPORER Equation.3 Examinons le dernier terme de la somme ci-dessus dans le cas restreint où la suite INCORPORER Equation.3 est majorée par une constante M. On montre facilement par récurrence que pour tout entier p , on a la majoration : sup{ INCORPORER Equation.3 ; n (N} ( 2p+1M On en déduit que pour INCORPORER Equation.3 : INCORPORER Equation.3 Par suite : INCORPORER Equation.3 . Le terme étudié converge à coup sûr vers 0 lorsque INCORPORER Equation.3 c'est à dire si INCORPORER Equation.3 On en déduit enfin en faisant tendre p vers l'infini : INCORPORER Equation.3 Ceci peut s'écrire plus simplement : INCORPORER Equation.3 INCORPORER Equation.3 Sous réserve de la convergence des deux séries alternées de termes INCORPORER Equation.3 , le Lemme d'Abel nous permet de passer à la limite en -1. On en déduit la formule dont Euler faisait grand usage : INCORPORER Equation.3
Procédé d'Aitken et fonction gamma incomplète.
Nous examinons ici les suites générées par la formule d'Aitken, c'est à dire par la donnée de trois sources x0 , x1 , x2 et la relation de récurrence : ( n (N INCORPORER Equation.3 Commençons par écrire INCORPORER Equation.3 . La suite auxiliaire INCORPORER Equation.3 satisfait donc à INCORPORER Equation.3 En plus de la condition de définition de la fraction (un ( un+1), supposons que un et un+1 sont non nuls. La suite quotient INCORPORER Equation.3 se construit alors par : INCORPORER Equation.3
Sous réserve de définition et de non nullité des termes successifs v0 , v1 ,
., vn , et en remarquant que INCORPORER Equation.3 , on en déduit vu la progression arithmétique INCORPORER Equation.3 , soit encore l'expression élémentaire : INCORPORER Equation.3
On vérifie en fait très facilement que si les sources x0 , x1 , x2 sont choisies de façon que INCORPORER Equation.3 soit défini, non nul et d'inverse non entier naturel, les itérations étudiées pourront se poursuivre indéfiniment.
Supposons en effet avoir construit x0 , x1 ,
., xn+2 et que les différences u0 , u1,
., un+1 soient toutes non nulles. (C'est le cas pour n=0 vu les hypothèses envisagées). Le calcul du terme suivant xn+3 exige alors un ( un+1 , soit encore INCORPORER Equation.3 . Or vu l'expression de vn à partir de v0, INCORPORER Equation.3 ce qui est exclu. Le terme xn+3 peut donc être construit et l'égalité INCORPORER Equation.3 montre qu'à son tour la différence un+2 est non nulle. Tout est donc en place au rang suivant pour définir maintenant xn+4 et pour poursuivre la construction aussi loin que l'on veut sans que les hypothèses de sécurité soient déstabilisées.
Dans toute la suite nous supposerons que cette hypothèse suffisante sur v0 est bien réalisée.
Sous cette condition on a donc (n (N INCORPORER Equation.3 . De proche en proche on en déduit alors naturellement : ( n (2 INCORPORER Equation.3 Remarquons alors que par sommation des différences : INCORPORER Equation.3 D'où pour tout entier n (3 : INCORPORER Equation.3 En posant INCORPORER Equation.3 on obtient la formule : INCORPORER Equation.3 Le terme u0 étant non nul, la convergence de la suite xn est donc directement liée à la convergence de la série de terme général INCORPORER Equation.3 Comme à partir d'un certain rang, la somme x+k sera positive, on pourra après factorisation se ramener au cas où x ( 0. Le critère des séries alternées s'applique alors sans problème et assure la convergence effective puisque la suite INCORPORER Equation.3 tend vers 0 en décroissant.
On en conclut INCORPORER Equation.3
Nous terminerons par une expression intégrale de cette limite. On vérifie d'abord facilement par intégrations par parties successives, la relation suivante : ( k (N et ( x ( 0 INCORPORER Equation.3 Par linéarité de l'intégrale il vient : INCORPORER Equation.3 Or d'après une propriété classique des séries alternées, on obtient pour t ( 0 et tout entier n la majoration : INCORPORER Equation.3 Il s'ensuit que INCORPORER Equation.3 Le majorant ci dessus tendant vers 0 en l'infini , INCORPORER Equation.3 .
Si on fait la synthèse des résultats précédents, avec les sources INCORPORER Equation.3 Si x (0 on aura bien INCORPORER Equation.3 non nul et non inverse d'entier naturel. La suite récurrente INCORPORER Equation.3 converge alors vers INCORPORER Equation.3
C'est un algorithme commode et rapide pour évaluer la fonction dite gamma incomplète.
POLYNOMES DE LAGRANGE.
Un problème classique d'interpolation.
On considère un système de n points du plan P définis par leur coordonnées dans un repère (O ; INCORPORER Equation.3 , INCORPORER Equation.3 ) , soit : k ( INCORPORER Equation.3 avec k ({1,
.,n}. On suppose les n abscisses distinctes. On se propose de déterminer une courbe simple passant par tous ces points, par exemple représentant une fonction polynôme f de degré n-1. Une solution élégante consiste à employer un système de polynômes de même degré n-1, choisis de façon que chacun s'annulera en tous les points xk excepté l'un d'entre eux sur lequel il prendra la valeur 1. Autrement dit on cherche un système (L1,
.., Ln) tel que ( k, i : INCORPORER Equation.3
Il est alors clair qu'un tel système explicité, le polynôme défini par INCORPORER Equation.3 réalisera bien l'interpolation demandée.
La construction d'un tel système est relativement simple. Il suffit de considérer tout d'abord le polynôme Q défini par INCORPORER Equation.3 . Puis on définit pour chaque indice k de {1,
.,n} le polynôme INCORPORER Equation.3 Polynôme dit d'ordre k de Lagrange relativement au système {x1,
.., xn}. Ce jeu de fonctions est effectivement solution et c'est le seul formé de fonctions polynômes de degré au plus n-1, car deux polynômes de tel degré prenant les mêmes valeurs aux points de l'ensemble {x1,
.., xn} sont nécessairement identiques. Remarquons que Lk peut aussi se définir par : INCORPORER Equation.3 On a en effet INCORPORER Equation.3 Ainsi : INCORPORER Equation.3
Interpolation d'une fonction.
Nous gardons les notations précédentes et considérons ici une fonction f définie sur un intervalle I fermé borné contenant les n réels de {x1,
.., xn}. On peut alors chercher une fonction polynôme P prenant les mêmes valeurs que f aux n points de ce système. L'étude effectuée ci dessus donne pour solution évidente INCORPORER Equation.3 On se propose alors d'étudier la déviation maximale entre f et P sur l'intervalle I. Cela peut se faire assez facilement par un schéma classique d'emploi du théorème de Rolle en cascade si on suppose f de classe Cn sur l'intervalle I.
Considérons pour cela la différence INCORPORER Equation.3 , s'annulant aux points x1,
., xn. Prenons maintenant un réel x fixé dans I distinct de ces n points et construisons la fonction ( définie sur I par : INCORPORER Equation.3 avec comme précédemment INCORPORER Equation.3 Cette fonction ( s'annule aux n+1 points x1,
., xn., x de l'intervalle I. De plus elle est de classe Cn sur cet intervalle par hypothèse sur f. On en déduit en appliquant Rolle sur chacun des n intervalles juxtaposés constitués par les n +1points de subdivision en question que la dérivée (' s'annule au moins en n points distincts de I. Le même argument repris avec (' donne une annulation de INCORPORER Equation.3 en n-1 réels distincts de I. En répétant l'opération on obtiendra donc une annulation certaine de INCORPORER Equation.3 en au moins un point c de ce même intervalle I. Or Q étant de degré n et de coefficient dominant 1, on obtient d'une part: INCORPORER Equation.3 D'autre part P étant de degré au plus n-1 on aura INCORPORER Equation.3 Ainsi sur I : INCORPORER Equation.3 La relation INCORPORER Equation.3 conduit donc à : INCORPORER Equation.3 Si Mn désigne un majorant de INCORPORER Equation.3 lorsque t décrit l'intervalle fermé borné I on peut donc conclure que la valeur absolue de l'écart entre f(x) et le polynôme d'interpolation P(x) sera majorée pour tout x de I suivant la formule :
INCORPORER Equation.3
En particulier si I=[a, b] et si les xk sont répartis régulièrement sur I avec un pas de INCORPORER Equation.3 on en déduit facilement la majoration INCORPORER Equation.3 En effet x appartient toujours à un Ik=[xk, xk+1] et sur Ik: INCORPORER Equation.3
LIENS ENTRE ACCELERATION ET INTERPOLATION.
Un principe de base étant établi pour l'accélération, il est naturel d'essayer de l'appliquer à nouveau sur la suite améliorée, puis de répéter cet affinage autant que faire se peut. Dans cette démarche le brassage de la suite initiale va s'étendre, l'équilibrage effectué va mettre en jeu un nombre de plus en plus grand de termes consécutifs. On va voir alors que les liens avec la théorie de l'interpolation, déjà suggérés par l'interprétation géométrique de la formule d'Aitken vont se consolider au fil des opérations et que la dualité entre les deux principales techniques d'accélération resurgit à nouveau de manière très nette.
Pour développer cette idée nous nous placerons dans le cadre suivant :
f désigne une fonction numérique dérivable jusqu'à l'ordre r en 0. INCORPORER Equation.3 est une suite de réels distincts deux à deux, non nuls convergent vers 0. Le but est l'approximation de f(0) à l'aide de la suite image INCORPORER Equation.3
D'après la formule de Taylor, f se développe au voisinage de 0 sous la forme : INCORPORER Equation.3 avec INCORPORER Equation.3 Introduisons les quotients INCORPORER Equation.3 Par télescopage des produits de ces taux on peut écrire pour tout entier n : INCORPORER Equation.3 INCORPORER Equation.3 Conformément à la méthode d'Aitken accélérons la convergence en posant INCORPORER Equation.3 On obtient : INCORPORER Equation.3 Avec : INCORPORER Equation.3 Examinant INCORPORER Equation.3 , on voit que l'élimination du terme d'ordre 2 nous contraint au nouvel équilibrage défini par : INCORPORER Equation.3 . Le lecteur courageux explicitant INCORPORER Equation.3 s'apercevra que l'étape suivante nécessite l'intervention du facteur INCORPORER Equation.3 pour l'élimination des termes d'ordre 3. Plus généralement il semble que ce processus d'érosion des termes de plus bas degré soit défini de proche en proche par la formule générale suivante : INCORPORER Equation.3
Notons que sa mise en uvre effective repose sur l'hypothèse que tous les termes de la suite initiale sont distincts deux à deux. Les dénominateurs des fractions concernées ne sont donc jamais nuls.
L'explicitation de ces INCORPORER Equation.3 étant délicate, il n'est pas aisé de montrer directement que la relation ci-dessus traduit bien la démarche d'élimination progressive, c'est-à-dire que si on part d'une suite initiale INCORPORER Equation.3 on obtiendra bien après k itérations INCORPORER Equation.3 . Cette confirmation viendra par le biais du sujet qui nous préoccupe essentiellement ici, c'est à dire les rapports avec les polynômes d'interpolation. On va en effet démontrer par récurrence sur k ( 1 le résultat suivant :
Théorème: ( k (N* , (n (N INCORPORER Equation.3 est la valeur en 0 du polynôme de Lagrange interpolant les points INCORPORER Equation.3
Pour k=1 on a une légère variante de l'interprétation géométrique déjà proposée pour illustrer Aitken.
La droite passant par INCORPORER Equation.3 a pour équation cartésienne : INCORPORER Equation.3 Pour x=0 on obtient donc : INCORPORER Equation.3
Supposons la propriété vraie pour k (et pour toute suite INCORPORER Equation.3 et INCORPORER Equation.3 )
Soit alors P le polynôme interpolant les points : INCORPORER Equation.3 ; INCORPORER Equation.3 ;
; INCORPORER Equation.3 Q le polynôme interpolant les points : INCORPORER Equation.3 ; INCORPORER Equation.3 ;
. ; INCORPORER Equation.3
Il est bien connu que le polynôme R défini par INCORPORER Equation.3 interpole alors le système INCORPORER Equation.3 ; INCORPORER Equation.3 ;
; INCORPORER Equation.3 . (Vérification élémentaire).
Or par hypothèse de récurrence : P(0) n'est autre que INCORPORER Equation.3 et Q(0) est INCORPORER Equation.3 Pour ce dernier point et en toute rigueur utilisons l'opérateur shift S définie par (Sy)n=yn+1 et notons INCORPORER Equation.3 l'opérateur transformant INCORPORER Equation.3 en la suite INCORPORER Equation.3 avec x la suite INCORPORER Equation.3 On vérifie facilement la commutation INCORPORER Equation.3 , ce qui justifie le décalage d'indice dans l'hypothèse de récurrence.
Après ce clin d'il aux puristes on peut donc conclure que : INCORPORER Equation.3 La récurrence est bien justifiée.
Application du théorème.
Si on prend INCORPORER Equation.3 , il est clair que le polynôme interpolant les points du système INCORPORER Equation.3 ; INCORPORER Equation.3 ;
; INCORPORER Equation.3 n'est autre que INCORPORER Equation.3 Puisque P(0)=0, on justifie donc bien ainsi l'annulation de INCORPORER Equation.3 et par suite la formule d'élimination de proche en proche.
L'étude de l'évolution des restes INCORPORER Equation.3 s'effectue avec un schéma récurrent analogue : INCORPORER Equation.3 et INCORPORER Equation.3 On vérifie alors facilement que si INCORPORER Equation.3 avec INCORPORER Equation.3 , alors on a pour tout entier k : INCORPORER Equation.3 avec INCORPORER Equation.3
Le lien entre la méthode d'Aitken et le principe d'interpolation est donc clairement établi dans le cas de la configuration étudiée.
Reprenons maintenant le problème de l'approche de f(0) en suivant l'autre voie classique de l'accélération, celle qui consiste à modifier non pas la suite mais la fonction engendrant la suite.
Conformément à la stratégie classique on cherche donc à remplacer f par une fonction g satisfaisant aux contraintes : INCORPORER Equation.3
Avec les notations précédentes, il est assez naturel de construire g par la formule : INCORPORER Equation.3
En effet les contraintes imposées à g vont se traduire par un système linéaire par rapport aux coefficients inconnus C0 , C1 ,
, Ck., quant au choix des facteurs de x il se justifie par le fait que g(x0) s'exprimera ainsi commodément à l'aide des valeurs INCORPORER Equation.3 supposées déjà explicitées.
Plus précisément le système équivaut à : INCORPORER Equation.3
Celui ci est facilement résoluble par les déterminants dits de Vandermonde. On rappelle à ce sujet que INCORPORER Equation.3 . On en déduit l'expression des Cq
INCORPORER Equation.3
En posant INCORPORER Equation.3 cela donne INCORPORER Equation.3
Or le polynôme de Lagrange interpolant les points INCORPORER Equation.3 ; INCORPORER Equation.3 ;
; INCORPORER Equation.3 est défini à partir de L par : INCORPORER Equation.3 . D'où : INCORPORER Equation.3
Or d'après le théorème précédent, P(0) n'est autre que INCORPORER Equation.3 , le k ieme accéléré à partir du système initial INCORPORER Equation.3 . On a donc vérifié que g(0)= INCORPORER Equation.3 La jonction entre les deux techniques d'accélération est donc bien réalisée, et ceci par l'intervention des polynômes d'interpolation de Lagrange.
PAGE
PAGE 24
