Procédé d'Overholt
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b0/F_of_x.svg/45px-F_of_x.svg.png)
Cet article est une ébauche concernant l’analyse.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En analyse numérique, le procédé d'Overholt est une méthode non linéaire d'accélération de la convergence de suites numériques. Cet algorithme a été proposé par Kjell Jørgen Overholt[1]. C'est une généralisation de l'algorithme Delta-2 d'Aitken.
Présentation
Soit une suite numérique Sn dont on cherche à connaitre la limite S. Le procédé d'Overholt consiste à calculer un tableau en initialisant la première colonne par la suite Sn, et en calculant les autres cases à l'aide des relations suivantes :
Les différentes colonnes du tableau fournissent d'autres suites convergeant sous certaines conditions plus vite que la suite Sn d'origine (la première colonne étant égale au Δ² de Aitken). Les différences des termes consécutifs de la suite Sn apparaissant à de multiples reprises dans l'algorithme, il est judicieux de les calculer une fois pour toutes.
On présente traditionnellement les résultats du procédé d'Overholt sous forme d'un tableau aux lignes décalées: la formule de calcul du procédé d'Overholt relie ainsi les termes formant un triangle dans le tableau. Le calcul de V(n)
k nécessite la connaissance de k+2 termes de la suite originale, de Sn à Sn + k + 1.
Propriétés
Le modèle de convergence de la suite Sn sur lequel le procédé d'Overholt est bâti est :
avec ak des constantes arbitraires. Le procédé d'Overholt permet d'éliminer un à un les termes d'ordre k. Le modèle de convergence du Δ² d'Aitken étant égal au premier terme de celui du procédé d'Overholt, il en est un cas particulier.
Si la suite à accélérer suit le modèle de convergence du procédé d'Overholt, on a :
La suite accélérée est donc d'ordre k. Ce type de modèle de convergence se rencontre notamment pour les suites issues d'une formule de récurrence de type point fixe, où la fonction de récurrence est k fois différentiable. Le procédé d'Overholt sera donc très efficace pour accélérer la convergence de méthodes itératives de recherche de zéros de fonctions. Il est une généralisation de la méthode de Steffensen.
Lorsque la suite Sn ne présente pas ce type de convergence, le procédé d'Overholt converge vers la limite de Sn à partir d'un rang N si :
Variantes
Variante confluente
Le procédé d'Overholt classique accélère une suite numérique, c'est-à-dire une fonction d'une variable discrète n. La version confluente de cet algorithme accélère la convergence d'une fonction d'une variable continue t. Elle s'obtient en faisant un changement de variable x = t + nh à l'algorithme d'origine, et en faisant tendre h vers 0. On obtient :
- ;
- .
Cet algorithme est utilisé par exemple pour l'évaluation des intégrales impropres lorsque les dérivées de la fonction sont accessibles, ou à l'élaboration de séries asymptotiques pour certaines fonctions.
La dérivée des termes apparaissant dans la formule peuvent se ramener aux dérivées de la fonction de base f(t) par calcul formel. On obtient par exemple pour les premiers termes :
- ;
- ;
- .
Exemples
Résolution d'une équation non linéaire
Le procédé d'Overholt étant une généralisation du Delta-2 d'Aitken, il fournit aussi une généralisation de la méthode d'Aitken-Steffensen pour la résolution numérique d'une équation non linéaire. L'ordre de la méthode peut être arbitrairement choisi en fonction du nombre de colonnes calculés.
La méthode consiste à écrire l'équation à résoudre f(x) = 0 sous la forme g(x) = x. A partir d'une valeur initiale de la racine x0, on génère la suite :
Deux techniques peuvent être employées avec cet algorithme : l'accélération en parallèle de la suite originale, et l'injection périodique du résultat de l'algorithme dans la suite initiale. Dans ce dernier cas, si le résultat de la colonne m est injecté, la méthode obtenue sera d'ordre m. Le cas m = 2 correspond à la méthode d'Aitken-Steffensen. Pour m = 3, on trouve une méthode du même ordre que celle de Halley, mais ne nécessitant pas la connaissance des dérivées premières et secondes.
Par exemple, pour résoudre l'équation exp(x) = x, en initialisant l'itération avec x = 0 :
- Technique 1
- accélération en parallèle de la suite originale (les chiffres corrects sont en gras):
n | xn | Vn-2 1 | Vn-3 2 | Vn-4 3 | Vn-5 4 | Vn-6 5 |
---|---|---|---|---|---|---|
0 | 0 | |||||
1 | 1 | |||||
2 | 0,367879441171442 | 0,612699836780282 | ||||
3 | 0,692200627555346 | 0,582226096995623 | 0,571338046118197 | |||
4 | 0,500473500563637 | 0,571705767527252 | 0,566054029276901 | 0,566958775047447 | ||
5 | 0,606243535085597 | 0,568638805864466 | 0,567297063612060 | 0,567118366865691 | 0,567134657534919 | |
6 | 0,545395785975027 | 0,567616994846635 | 0,567111546919251 | 0,567141218391841 | 0,567144029145037 | 0,567143473642271 |
7 | 0,579612335503379 | 0,567296752488634 | 0,567148656593343 | 0,567143054064078 | 0,567143258010325 | 0,567143299061987 |
8 | 0,560115461361089 | 0,567192427887207 | 0,567142270414790 | 0,567143267441413 | 0,567143292585929 | 0,567143290626724 |
9 | 0,571143115080177 | 0,567159133834001 | 0,567143472075663 | 0,567143287953763 | 0,567143290292488 | 0,567143290417986 |
10 | 0,564879347391049 | 0,567148379226958 | 0,567143256823608 | 0,567143290160588 | 0,567143290416985 | 0,567143290410035 |
Le nombre de chiffres exacts passe de 2 dans la suite initiale, à 10 après application du procédé d'Overholt (il aurait fallu 45 itérations de base pour obtenir la même précision)
- Technique 2
- réinjection du résultat de la colonne m, après m itérations de base (les itérations de base sont en maigre; les réinjections sont soulignées dans le tableau):
n | V0 1 | V0 2 | V0 3 | V0 4 | V0 5 | V0 6 |
---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 0,367879441171442 | 0,367879441171442 | 0,367879441171442 | 0,367879441171442 | 0,367879441171442 | 0,367879441171442 |
3 | 0,612699836780282 | 0,692200627555346 | 0,692200627555346 | 0,692200627555346 | 0,692200627555346 | 0,692200627555346 |
4 | 0,541885888907111 | 0,571338046118197 | 0,500473500563637 | 0,500473500563637 | 0,500473500563637 | 0,500473500563637 |
5 | 0,581650289552568 | 0,564769245604983 | 0,566958775047447 | 0,606243535085597 | 0,606243535085597 | 0,606243535085597 |
6 | 0,567350857702887 | 0,568491313492426 | 0,567247946714562 | 0,567134657534919 | 0,545395785975027 | 0,545395785975027 |
7 | 0,567025582228799 | 0,566379283228498 | 0,567083938394566 | 0,567148186507974 | 0,567143473642271 | 0,579612335503379 |
8 | 0,567210051743956 | 0,567143289125034 | 0,567176952505934 | 0,567140513627344 | 0,567143186490718 | 0,567143293361668 |
9 | 0,567143294830715 | 0,567143291138421 | 0,567124199499133 | 0,5671448652455 | 0,567143349346788 | 0,567143288735643 |
10 | 0,567143287902483 | 0,567143289996542 | 0,567143290409784 | 0,567142397252977 | 0,567143256984058 | 0,567143291359262 |
11 | 0,567143291831783 | 0,567143290644151 | 0,567143290409784 | 0,5671437969579 | 0,56714330936696 | 0,567143289871294 |
12 | 0,567143290409784 | 0,567143290409784 | 0,567143290409784 | 0,567143290409784 | 0,567143279658349 | 0,567143290715185 |
La réinjection périodique du terme V(0)
m après m itérations permet d'obtenir une vitesse de convergence d'ordre m (typiquement, le nombre de chiffres exacts est multiplié par m). Cependant, atteindre cet ordre nécessitant m itérations, l'optimum en termes de quantité de calcul est obtenu dans notre exemple avec un ordre entre 2 et 4. Ici, la peine précision est obtenue dans certains cas avec 8 itérations de base, au lieu de 10 avec le procédé classique, et une centaine sans l'utilisation du procédé d'Overholt.
Notes et références
- ↑ Kjell Overholt, « Extended Aitken acceleration », BIT Numerical Mathematics, vol. 6, , p. 122-132
Voir aussi
Bibliographie
Claude Brezinski, Algorithmes d'accélération de la convergence : étude numérique, éditions Technip, 1978 (ISBN 2-7108-0341-0)
Articles connexes
- Delta-2
- ε-algorithme
- Extrapolation de Richardson
Portail de l'analyse
Portail des mathématiques