Utilisateur:Tegmine/Brouillon

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é de 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 K.J 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é de 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 :

$V_{0}^{(n)}=S_{n}{\text{ }}\forall n$

$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}}{\text{ }}\forall n,k$

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 toute.

On présente traditionnellement les résultats du procédé de Overholt sous forme d'un tableau aux lignes décalés: la formule de calcul du procédé de Overholt relie ainsi les termes formant un triangle dans le tableau. Le calcul de Vk(n) nécessite la connaissance de k+2 termes de la suite originale; de Sn à Sn+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é de Overholt est bâti est:

$S_{n+1}-S_{\infty }=\sum _{k=1}^{\infty }a_{k}(S_{n}-S_{\infty })^{k}{\text{ }}n=0,1...$

avec a_k des constantes arbitraires. Le procédé de 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:

${\frac {S_{n+2}-S_{n+1}}{S_{n+1}-S_{n}}}\neq 1{\text{ }}\forall n>N$

Variantes

la variante confluente

Le procédé de 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'. On l'obtient en faisant un changement de variable x=t+n*h à l'algorithme d'origine, et en faisant tendre h vers 0. on obtient:

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

$V_{k+1}(t)=V_{k}(t)-{\frac {f'(t)}{f''(t)}}{\frac {V'_{k}(t)}{k+1}}{\text{ }}k=0,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 pour les premiers termes:

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

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

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

Exemples

Résolution d'une équation non linéaire

Le procédé de 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₀, générer l’itération:

$V_{0}^{(0)}=x_{i}{\text{ }}i=0,1,2...$

$V_{0}^{(n+1)}=g(V_{0}^{(n)}){\text{ }}n=0,1,2...m$

$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}}}{\text{ }}\forall n+k=m$

$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. Pour m=2, nous obtenons la méthode d'Aitken-Steffensen. Pour m=3, nous obtenons 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	V₁^n-2	V₂^n-3	V₃^n-4	V₄^n-5	V₅^n-6
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 bases sont en maigre; les réinjections sont en gras 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	_nV₁⁰	_nV₂⁰	_nV₃⁰	_nV₄⁰	_nV₅⁰	_nV₆⁰
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

L'accélération est encore meilleure avec les injections périodique. 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 accélération.

Exemple : interpolation polynomiale de la fonction logarithme népérien et calcul des fraction rationnelles correspondantes à l'aide de l'epsilon algorithme d'interpolation^[2]

La fonction logarithme sera interpolée en trois points: 1/2, 1 et e. Pour tester la mise en œuvre de l'algorithme dans le cas d'une interpolation d'Hermite, l'interpolation en 1/2 sera double (interpolation du logarithme et de sa dérivée), et triple en 1 (interpolation du logarithme, et de ses dérivées premières et secondes). Il s'agit d'un polynôme de degré 5 qui doit donc vérifier: P(0.5)=-ln(2); P'(0.5)=2; P(1)=0; P'(1)=1; P"(1)=-1; P(e)=1.

Calcul des différences divisées du polynôme d'interpolation :

Tableau des différences divisées pour l'interpolation polynomiale de ln(x) en 3 points
i	x_i	y_i / d₀	d₁	d₂	d₃	d₄	d₅
0	2,71828182845904	1	0,581976706869326	-0,243279819530861	0,149405165216329	-0,178413885100506	0,24817470934455
1	1	0	1	-0,5	0,545177444479562	-0,728935333122626
2	1	0	1	-0,772588722239781	0,909645111040875
3	1	0	1,38629436111989	-1,22741127776022
4	0.5	-0,693147180559945	2
5	0.5	-0,693147180559945

Les cases en italiques correspondent à des indéterminées des différences divisées (du fait des points doubles ou triples), et sont remplacés par les valeurs de la dérivée en ce point (ou de f"(x)/2! pour la différence seconde). Les cases en gras dans le tableau sont celles utiles au calcul de la forme de Newton du polynôme d'interpolation. Le polynôme s'écrit, à l'aide de la formule de Newton:

P_{5}(x)=d_{0}+d_{1}(x-x_{0})+d_{2}(x-x_{0})(x-x_{1})+d_{3}(x-x_{0})(x-x_{1})(x-x_{2})+d_{4}(x-x_{0})(x-x_{1})(x-x_{2})(x-x_{3})+d_{5}(x-x_{0})(x-x_{1})(x-x_{2})(x-x_{3})(x-x_{4})

Calcul de P₅(2), et application de l'epsilon algorithme d'interpolation

La suite des P_i(2) servant à initialiser le tableau de l'epsilon algorithme d'interpolation, est la suite de polynôme de degré 0,1,2... obtenu en retenant 1,2,3... termes du polynôme P₅(2) écrit sous la forme de Newton ci dessus. Cette suite de polynôme passent respectivement par les points d'abscisse (x0,y0); (x0,y0),(x1,y1); (x0,y0),(x1,y1),(x2,y2);...

Interpolation polynomiale de ln(2)=0,693147180559945..., et calcul de l'epsilon algorithme d'interpolation
i	x_i	P_i(x)= ε⁽ⁱ⁾₀	ε⁽ⁱ⁾₁	ε⁽ⁱ⁾₂	ε⁽ⁱ⁾₃	ε⁽ⁱ⁾₄
0	2,71828182845904	1	-2,39221119117733	0,705207033512282	-61,0702755830021	0,693879569827545
1	1	0,581976706869326	5,72267438319407	0,69023539353372	121,870014050176	0,692833802968095
2	1	0,756720180469139	-9,31836050756016	0,695317144633344	-146,585461084686
3	1	0,649405165216329	5,20217803449192	0,690925043467957
4	0.5	0,777556616828803	-2,49324571003365
5	0.5	0,51016754082086

La valeur de P₅(2), pourtant située dans l'intervalle d'interpolation, est assez éloignée de ln(2), valeur de la fonction à interpoler. Sur le graphique, on note une forte dégradation des qualités d'interpolation du polynôme entre 1.5 et e. La présence d'un pôle à proximité de l'intervalle d'interpolation, ainsi que la croissance logarithmique de la courbe se prête mal à l'interpolation par polynômes. Ceci se prête d'avantage à l'interpolation rationnelle. L'application de l'epsilon algorithme d'interpolation à ce polynôme améliore significativement les qualités d'interpolation sur cet exemple. Sur le graphique, certaines fractions rationnelles obtenues sont presque indiscernable de la fonction à interpoler, dans l'intervalle d'interpolation, et au delà. Les nombres en gras dans la table de l'epsilon algorithme représente les fraction rationnelles d'interpolation de degré 5/0, 4/1 et 3/2. Elle peut être continuée pour intégrer celles de degré 2/3, 1/4 et 0/5.

Notes

↑ K. J. Overholt, "Extended Aitken acceleration," BIT, v. 6, 1965, pp. 122-132.
↑ Guido Claessens, « Some aspects of the rational Hermite interpolation table and its applications », Ph. D. thesis, University of Antwerp,‎ 1976

Références

Claude Brezinski, Algorithmes d'accélération de la convergence: étude numérique, éditions Technip, 1978, (ISBN 2-7108-0341-0)

Voir aussi

Articles connexes

[1] K. J. Overholt, "Extended Aitken acceleration," BIT, v. 6, 1965, pp. 122-132.

[2] Guido Claessens, « Some aspects of the rational Hermite interpolation table and its applications », Ph. D. thesis, University of Antwerp,‎ 1976

[1]

[2]