Procédé d'Overholt

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 $S n$ 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 $S n$ , et en calculant les autres cases à l'aide des relations suivantes :

\forall n\in \mathbb {N} ,\quad V_{0}^{(n)}=S_{n}

\forall n,k\in \mathbb {N} ,\quad V_{k+1}^{(n)}={\frac {(S_{n+k+1}-S_{n+k})^{k+1}\cdot V_{k}^{(n+1)}-(S_{n+k+2}-S_{n+k+1})^{k+1}\cdot V_{k}^{(n)}}{(S_{n+k+1}-S_{n+k})^{k+1}-(S_{n+k+2}-S_{n+k+1})^{k+1}}}=V_{k}^{(n)}+{\frac {V_{k}^{(n+1)}-V_{k}^{(n)}}{1-\left({\frac {S_{n+k+2}-S_{n+k+1}}{S_{n+k+1}-S_{n+k}}}\right)^{k+1}}}=V_{k}^{(n+1)}+{\frac {V_{k}^{(n+1)}-V_{k}^{(n)}}{\left({\frac {S_{n+k+1}-S_{n+k}}{S_{n+k+2}-S_{n+k+1}}}\right)^{k+1}-1}}

Les différentes colonnes du tableau fournissent d'autres suites convergeant sous certaines conditions plus vite que la suite $S n$ d'origine (la première colonne étant égale au Δ² de Aitken). Les différences des termes consécutifs de la suite $S n$ 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 $S n$ à $S n + k + 1$ .

{\begin{matrix}&&&&&\\&V_{0}^{(0)}=S_{0}&&&&\\&&V_{1}^{(0)}&&&\\&V_{0}^{(1)}=S_{1}&&V_{2}^{(0)}&&\\&&V_{1}^{(1)}&&V_{3}^{(0)}&\\&V_{0}^{(2)}=S_{2}&&V_{2}^{(1)}&&V_{4}^{(0)}\\&&V_{1}^{(2)}&&V_{3}^{(1)}&\cdots \\&V_{0}^{(3)}=S_{3}&&V_{2}^{(2)}&&V_{4}^{(1)}\cdots \\&\vdots &&\vdots &&\vdots \\\end{matrix}}

Propriétés

Le modèle de convergence de la suite $S n$ sur lequel le procédé d'Overholt est bâti est :

\forall n\in \mathbb {N} ,\quad S_{n+1}-S_{\infty }=\sum _{k=1}^{\infty }a_{k}(S_{n}-S_{\infty })^{k}

avec a_k 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 :

V_{k}^{(n)}-S_{\infty }=O(S_{n}-S_{\infty })^{k+1}

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 $S n$ ne présente pas ce type de convergence, le procédé d'Overholt converge vers la limite de $S n$ à partir d'un rang N si :

\forall n\geqslant N,\quad {\frac {S_{n+2}-S_{n+1}}{S_{n+1}-S_{n}}}\neq 1

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 :

V_{0}(t)=f(t)

;

\forall k\in \mathbb {N} ,\quad V_{k+1}(t)=V_{k}(t)-{\frac {f'(t)}{f''(t)}}{\frac {V'_{k}(t)}{k+1}}

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 :

V_{1}(t)=f(t)-{\frac {f'(t)^{2}}{f''(t)}}

;

V_{2}(t)=f(t)-{\frac {f'(t)^{2}}{f''(t)^{3}}}{\frac {f''(t)^{2}+f'(t)f'''(t)}{2}}

;

V_{3}(t)=V_{2}(t)-{\frac {f'(t)}{f''(t)}}{\frac {3f'(t)f'''(t)^{2}-f'(t)f''(t)f^{(4)}(t)-2f''(t)f'''(t)}{6f''(t)^{4}}}

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 $x 0$ , on génère la suite :

\forall i\in \mathbb {N} ,\quad V_{0}^{(0)}=x_{i}

\forall n\in [\![0,m]\!]V_{0}^{(n+1)}=g(V_{0}^{(n)})

\forall n+k=m,\quad V_{k+1}^{(n)}={\frac {(V_{0}^{(n+k+1)}-V_{0}^{(n+k)})^{k+1}\cdot V_{k}^{(n+1)}-(V_{0}^{(n+k+2)}-V_{0}^{(n+k+1)})^{k+1}\cdot V_{k}^{(n)}}{(V_{0}^{(n+k+1)}-V_{0}^{(n+k)})^{k+1}-(V_{0}^{(n+k+2)}-V_{0}^{(n+k+1)})^{k+1}}}

x_{i+1}=V_{m}^{(0)}

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):

Application du procédé d'Overholt à la suite x_n+1=exp(*x_n*). Solution: x=0,567143290409784...
n	x_n	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):

Réinjection périodique du procédé d'Overholt à la suite x_n+1=exp(*x_n*). Solution: x=0,567143290409784...
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,‎ 1965, 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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.