Utilisateur:Tegmine/Brouillon2

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 θ-algorithme est un algorithme non linéaire d'accélération de la convergence d'une suite numérique dû à C. Brezinski^[1]. C'est un algorithme hybride entre l'ε-algorithme et le ρ-algorithme de P. Wynn, qui ajuste automatiquement un facteur de relaxation pour optimiser l'accélération de la convergence. C'est un algorithme particulièrement polyvalent, capable d'accélérer des suites divergentes, à convergence linéaires ou logarithmiques.

Description de l'algorithme

L'ε-algorithme et le ρ-algorithme, bien que issus de théories différentes et ayant des applications complémentaires, ont une structure algorithmique très proche. La seule différence entre les algorithmes est la valeur du numérateur dans la formule de récurrence (égale à 1 pour l'ε-algorithme et k+1 pour le ρ-algorithme). L’idée du θ-algorithme est de proposer un numérateur qui optimise l'accélération de la convergence, se calculant automatiquement avec l'évolution des termes de la suite à accélérer.

L'algorithme part de la structure générale:

$\theta _{-1}^{(n)}=0{\text{ }}\theta _{0}^{(n)}=S_{n}{\text{ }}\forall n$

$\theta _{k+1}^{(n)}=\theta _{k-1}^{(n+1)}+{\frac {\omega _{k}^{(n)}}{\theta _{k}^{(n+1)}-\theta _{k}^{(n)}}}{\text{ }}\forall n,k$

Ou S_n est la suite numérique dont on cherche à connaitre la limite S. Le numérateur ωⁿ_k est à déterminer pour optimiser au mieux la convergence. Brezinski a démontré que le numérateur optimal pour accélérer les colonnes paires était:

$\omega _{2k+1}^{(n)}=1{\text{ et }}\omega _{2k}^{(n)}=-\lim _{n\to \infty }{\frac {\theta _{2k}^{(n+2)}-\theta _{2k}^{(n+1)}}{D_{2k+1}^{(n+1)}-D_{2k+1}^{(n)}}}{\text{ }}\forall k$

${\text{ avec }}D_{k}^{(n)}={\frac {1}{\theta _{k}^{(n+1)}-\theta _{k}^{(n)}}}{\text{ }}\forall n,k$

Ce choix nécessitant l'évaluation d'une limite dépendant de S_n, il est en pratique remplacé dans le θ-algorithme par sa meilleure approximation disponible, compte tenu des termes de S_n déjà calculés.

$\omega _{2k+1}^{(n)}=1{\text{ et }}\omega _{2k}^{(n)}=-{\frac {\theta _{2k}^{(n+2)}-\theta _{2k}^{(n+1)}}{D_{2k+1}^{(n+1)}-D_{2k+1}^{(n)}}}{\text{ }}\forall k,n$

${\text{ avec }}D_{k}^{(n)}={\frac {1}{\theta _{k}^{(n+1)}-\theta _{k}^{(n)}}}{\text{ }}\forall n,k$

Finalement, le θ-algorithme 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 :

$\theta _{-1}^{(n)}=0{\text{ }}\theta _{0}^{(n)}=S_{n}{\text{ }}\forall n$

$\theta _{2k+1}^{(n)}=\theta _{2k-1}^{(n+1)}+D_{2k}^{(n)}{\text{ }}\forall n,k$

$\theta _{2k+2}^{(n)}={\frac {D_{2k+1}^{(n+1)}\theta _{2k}^{(n+1)}-D_{2k+1}^{(n)}\theta _{2k}^{(n+2)}}{D_{2k+1}^{(n+1)}-D_{2k+1}^{(n)}}}{\text{ }}\forall n,k$

${\text{ avec }}D_{k}^{(n)}={\frac {1}{\theta _{k}^{(n+1)}-\theta _{k}^{(n)}}}{\text{ }}\forall n,k$

La formule de calcul du θ-algorithme permet de calculer les termes du tableau de haut en bas et de gauche à droite.

Les différentes colonnes d'indice k paires du tableau fournissent d'autres suites convergeant en général plus vite que la suite S_n d'origine. Les colonnes d'indice impaires sont considérés comme des intermédiaires de calcul. Il faut connaître 3 termes supplémentaires de la suite S_n pour passer d'une colonne paire du tableau à une autre. Ceci diffère de l'ε-algorithme et du ρ-algorithme, ou seulement 2 termes étaient nécessaires (dans le cas présent, un terme est utilisé pour estimer le facteur de relaxation).

Mises en œuvre

Mise en œuvre classique

Après chaque calcul d'un nouveau terme de la suite initiale, une diagonale montante du tableau du θ-algorithme est initiée. L'ajout de trois termes de la suite initiale permet de finaliser deux diagonales montantes du tableau. Pour faire des économies de mémoire, il est inutile de mémoriser l'intégralité du tableau dans ce cas d'utilisation. Seule les deux dernières diagonales ascendantes sont indispensable, ainsi que l'usage de trois variables auxiliaires^[2].

Itération du θ-2

Chaque colonne paire du θ-algorithme génère une sous-suite qui converge vers la limite recherchée. Une possibilité est de partir d'une de ces sous-suites, et de lui appliquer de nouveau le θ-algorithme, de la même manière que pour la suite initiale. Plusieurs procédés peuvent être envisagés en fonction de la sous-suite choisie et l'utilisation de l'algorithme qu'on en fait. Le plus utilisé est l'itération de la 2ème colonne du θ-algorithme, appelé algorithme θ-2 (par analogie au Delta-2 d'Aitken, étant l'itéré de la 2ème colonne de l'ε-algorithme), ou transformation W itéré de Lubkin^[3] . La procédure consiste à arrêter le développement du θ-algorithme à 2ème colonne, et de repartir de la suite de cette colonne comme point de départ pour appliquer à nouveau le θ-2. L'algorithme θ-2 bénéficie de plusieurs résultats théorique de convergence^[4]^[5], dont le θ-algorithme est dépourvu, d'où son intérêt.

optimisation par colonne

Lorsque la suite à accélérée à notre disposition comprend un nombre restreint de termes, il est utile d'optimiser au mieux leur usage pour approcher leur limite. Le θ-algorithme de base utilise 3 termes pour progresser de 2 colonnes (un des termes est sacrifié pour fournir une estimation du paramètre de relaxation ωⁿ_k). Dans l'idéal, le paramètre de relaxation optimal pour la colonne k est la limite de ωⁿ_k quand n tend vers l'infini. Une possibilité de modification est de calculer colonne par colonne. La première colonne étant calculée jusqu'au dernier terme disponible, colonne des facteurs de relaxation ωⁿ₁ en est déduite. Ceci permet d'estimer la limite de la suite ωⁿ₁, en retenant son dernier terme (ou en utilisant un accélérateur de convergence à cette suite). Cette valeur limite estimée est utilisée pour calculer la deuxième colonne de l'algorithme. Le calcul de cette colonne nécessite un terme de moins que dans la mise en œuvre classique. Les colonnes suivantes sont calculées de la même manière.

Exemples

Accélération de la convergence d'une suite numérique

La série suivante, série dite du problème de Bâle,

\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}={\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+{\frac {1}{4^{2}}}+\cdots ={\frac {\pi ^{2}}{6}}\approx 1,64493406684822643...

converge très lentement. Le θ-algorithme peut être utilisé pour accélérer la convergence des sommes partielles de cette série. Voici le résultat :

θ-algorithme appliqué au problème de Bâle. Limite = π²/6 ≈ 1,64493406684823...
n	S_n	ω₂⁽ⁿ⁾	θ₂⁽ⁿ⁾	ω₄⁽ⁿ⁾	θ₄⁽ⁿ⁾	ω₆⁽ⁿ⁾	θ₆⁽ⁿ⁾	ω₈⁽ⁿ⁾	θ₈⁽ⁿ⁾
0	1,00000000000000	1,9444444	1,63888888888891	1,3358954	1,64493509070143	1,1811819	1,64493408315835	0,6662549	1,64493406677259
1	1,25000000000000	1,9687500	1,64236111111109	1,3353508	1,64493455097273	1,1834367	1,64493406496746
2	1,36111111111111	1,9800000	1,64361111111141	1,3349346	1,64493431165107	1,1970989	1,64493407348733
3	1,42361111111111	1,9861111	1,64416666666690	1,3346262	1,64493419979124	1,2475889	1,64493408582860
4	1,46361111111111	1,9897959	1,64445011337757	1,3343933	1,64493414313700
5	1,49138888888889	1,9921875	1,64460955215264	1,3342185	1,64493411323898
6	1,51179705215420	1,9938272	1,64470600277549	1,3340978	1,64493409819462
7	1,52742205215420	1,9950000	1,64476773116677
8	1,53976773116654	1,9958678	1,64480905347269
9	1,54976773116654	1,9965278	1,64483774954862
10	1,55803219397646
11	1,56497663842090
12	1,57089379818422

La suite a accélérer est la somme partielle de la série, en ajoutant un terme à la fois. On constate que les colonnes paires convergent vers la limite, et ceci plus rapidement que la suite d'origine. De même, chaque colonne paire converge plus rapidement que la colonne paire précédente: le mécanisme d'estimation du facteur de relaxation s'avère performant dans ce cas.

Les colonnes impaires ne représentant que des intermédiaires de calcul, elles ont été remplacées dans le tableau par les colonnes des coefficients de relaxation déduits. Ceci permet d'exposer les rouages de l'algorithme et d’observer vers quelles valeurs les coefficients de relaxation convergent. Les valeurs des coefficients de relaxation semblent converger vers 2/1, 4/3, 6/5... Ceci suggère que le ρ-algorithme avec la suite auxiliaire 1,2,3,4,5,6... (le ρ-algorithme "classique" ) serait l'algorithme de choix pour accélérer cette suite. L'utilisation du θ-algorithme permet d'éviter à rechercher le bon algorithme avec la bonne suite auxiliaire.

En comparant les résultats obtenus avec l'ε-algorithme et le ρ-algorithme, on obtient:

Comparatif d'algorithmes sur le problème de Bâle
Sn	ε-algorithme	ρ-algorithme	θ-algorithme
1	1,00000000000	1,00000000000	1,000000000000
1,25000000	1,25000000000	1,25000000000	1,250000000000
1,36111111	1,45000000000	1,65000000000	1,361111111111
1,42361111	1,50396825397	1,64682539683	1,638888888889
1,46361111	1,55161744023	1,64489489489	1,642361111111
1,49138889	1,57176738855	1,64492258652	1,643611111111
1,51179705	1,59030541362	1,64493437612	1,644935090703
1,52742205	1,59998415515	1,64493414537	1,644934550988
1,53976773	1,60908690628	1,64493406438	1,644934311644
1,54976773	1,61447429527	1,64493406633	1,644934082200
1,55803219	1,61960991326	1,64493406662	1,644934070374

Les meilleurs résultats sont obtenus avec le ρ-algorithme, ce qui était prévisible d'après les facteurs de relaxation du θ-algorithme. Celui-ci paye sa polyvalence en étant légèrement moins performant que le ρ-algorithme. L'ε-algorithme est inefficace à accélérer cette suite.

Le problème de Bâle est un cas particulier de la fonction zêta de Riemann, correspondant à ζ(2). Pour les abscisses fractionnaires de cette fonction, le ρ-algorithme classique n'est plus efficace: il nécessite une suite auxiliaire spécifique, ou une variante^[6]. Par exemple, pour ζ(1,5),

$\zeta (1,5)=\sum _{n=1}^{\infty }{\frac {1}{n^{1,5}}}={\frac {1}{1^{1,5}}}+{\frac {1}{2^{1,5}}}+{\frac {1}{3^{1,5}}}+{\frac {1}{4^{1,5}}}+\cdots \approx 2,612375348685...$

En comparant les résultats des trois algorithmes, on obtient:

Comparatif d'algorithmes sur ζ(1.5)=2,612375348685...
Sn	ε-algorithme	ρ-algorithme	θ-algorithme
1,000000000	1,000000000	1,000000000	1,000000000
1,353553391	1,353553391	1,353553391	1,353553391
1,546003480	1,775899683	2,198245975	1,546003480
1,671003480	1,902656249	2,259309017	2,590822715
1,760446199	2,045614205	2,404014686	2,601914784
1,828487581	2,111353957	2,426590977	2,606396840
1,882482506	2,183417384	2,482950273	2,612446232
1,926676680	2,223747272	2,493248485	2,612404116
1,963713717	2,267202413	2,525945382	2,612388971
1,995336493	2,294494880	2,528505664	2,612375406
2,022746616	2,323562864	2,520536481	2,612375375

Le seul algorithme accélérant significativement la série est le θ-algorithme.

Pour la série de Leibniz :

{\frac {\pi }{4}}=\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n+1}}\approx 0,7853981633974...

Comparatif d'algorithmes sur la série de Leibniz
Sn	ε-algorithme	ρ-algorithme	θ-algorithme
1	1,00000000000	1,00000000000	1,000000000000
0,66666667	0,66666666667	0,66666666667	0,666666666667
0,86666667	0,79166666667	0,91666666667	0,866666666667
0,72380952	0,78333333333	0,70000000000	0,786666666667
0,83492063	0,78558558559	0,88176733781	0,785034013605
0,74401154	0,78534798535	0,71766827509	0,785537918871
0,82093462	0,78540372671	0,86219245010	0,785400136439
0,75426795	0,78539682540	0,72882941447	0,785397646798
0,81309148	0,78539832797	0,84953428508	0,785398327505
0,76045990	0,78539812632	0,73660230402	0,785398164205
0,80807895	0,78539816826	0,84062277444	0,785398163152

Cette fois ci, l'ε-algorithme donne de bons résultats, de même que le θ-algorithme.

Ces exemples exposent la polyvalence du θ-algorithme par rapport aux deux algorithmes dont il est issu.

Accélération de la convergence des séries de Fourier et de Tchebychev

Les sommes partielles des séries de Fourier ou de Tchebychev peuvent fournir une suite qui peut être accélérée par l'ε-algorithme. Cependant, une manière plus efficace de procéder est de transformer, par un changement de variable, ces séries en une série entière. Les sommes partielles de ces séries entières seront les donnés d'entrée pour l'ε-algorithme.

La série de Fourier :

f(\theta )={\frac {a_{0}}{2}}+\sum _{n=1}^{\infty }(a_{n}\cos {n\theta }+b_{n}\sin {n\theta })

ou celle de Tchebychev:

f(x)={\frac {c_{0}}{2}}+\sum _{n=1}^{\infty }c_{n}T_{n}(x)

se transforment chacune en une série entière (d'une variable complexe)

F(z)={\frac {a_{0}}{2}}+\sum _{n=1}^{\infty }(a_{n}-\mathrm {i} b_{n})z^{n}{\text{ avec }}z=\mathrm {e} ^{\mathrm {i} \theta }

ou

F(z)={\frac {c_{0}}{2}}+\sum _{n=1}^{\infty }c_{n}z^{n}{\text{ avec }}z=\mathrm {e} ^{\mathrm {i} \theta };\theta =Arcos(x)

dont la partie réelle est la série d'origine. Les T_n(x) représentent les polynômes de Tchebychev de 1ère espèce.

Ces séries se prêtent idéalement à l'accélération de la convergence par l'ε-algorithme (avec des nombres complexes) sur leurs sommes partielles. La partie réelle du résultat sera la valeur accélérée de la série de Fourier ou de Tchebychev d'origine.

Par exemple, la fonction Logarithme sur $[1, 9]$ , dont la série de Tchebychev vaut^[7] :

$\ln(1+8x)-2\ln 2=\sum _{n=1}^{\infty }{\frac {(-1)^{n-1}}{n.2^{n-1}}}T_{n}(y)\qquad avec\ y=2x-1\qquad 0\leqslant x\leqslant 1$

devient après changement de variable la série entière :

f(z)-2\ln 2=\sum _{n=1}^{\infty }{\frac {(-1)^{n-1}z^{n}}{n.2^{n-1}}}{\text{ avec }}z=\mathrm {e} ^{\mathrm {i} \theta };\theta =Arcos(2x-1)

Le graphique ci contre compare la fonction Logarithme avec sa série de Tchebychev en retenant les termes jusqu'au degré 6, ainsi que la valeur accélérée de cette série partielle par l'ε-algorithme. On note une nette amélioration de la convergence (erreur divisée par 80 ou plus). Le résultat accéléré conserve les caractéristiques typiques des approximations de Tchebychev: les oscillations d'amplitudes approximativement égales de l'erreur sur l'intervalle concerné (à peine perceptible sur le graphique).

Formellement, l'ε-algorithme transforme la série auxiliaire en approximant de Padé. En explicitant les calculs, l'approximant de Padé ici vaut:

$f(z)-2\ln 2={\frac {22z^{3}+240z^{2}+480z}{3z^{3}+72z^{2}+360z+480}}$

dont la partie réelle, en revenant à la variable d'origine, vaut:

$\ln(1+8x)\simeq 2\ln 2+{\frac {14080x^{3}+83040x^{2}+107328x+21862}{3840x^{3}+47520x^{2}+129744x+97971}}$

Cette fraction a les caractéristiques proches de la fraction min-max, optimale pour l'approximation: elle peut fournir un bon point de départ pour initialiser l'algorithme de Remez rationnel.

Alternative à la méthode de Romberg:

L'intégrale

$\int \limits _{0}^{1}{\sqrt {x}}.dx={\frac {2}{3}}=0.66666666666...$

possède une singularité algébrique en zéro, qui ralenti la convergence de la méthode de Romberg. L'utilisation de l'ε-algorithme à la place de l'extrapolation de Richardson dans cette méthode donne de meilleurs résultats:

Méthode de Romberg et l'ε-algorithme
subdivisions	Trapèzes	Romberg	ε-algorithme
1	0,5	0,5	0,5
2	0,603553390593274	0,638071187457699	0,603553390593274
4	0,643283046242747	0,657756603281563	0,668014371343285
8	0,658130221624454	0,663607569112292	0,666989411481855
13	0,663581196877228	0,665592865129466	0,666661304912164
32	0,665558936278942	0,666287699033842	0,666666280204189
64	0,666270811378507	0,666532741199894	0,666666671581115

Notes

↑ Brezinski, « Accélération des suites à convergence logarithmique », Comptes rendus de l'académie des sciences, Paris, vol. 273A,‎ 1971, p. 727-730
↑ Weniger, « Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series », Computer Physics Reports, vol. 10,‎ 1989, p. 189-371
↑ Lubkin, « A method of summing infinite series », Journal of research of the National Bureau of Standards, vol. 48,‎ 1952, p. 228-254
↑ Cordellier, « Caractérisation des suites que la première étape du θ-algorithme transforme en suites constantes », Compte rendu de l'académie des sciences, Paris, vol. 290A,‎ 1977, p. 389-392
↑ Sidi, « A convergence and stability study of the iterated Lubkin transformation and the θ-algorithm », Mathematics of computation, vol. 72,‎ 2003, p. 419-433
↑ Osada, « An acceleration theorem for the ρ-algorithm », Numerische Mathematik, vol. 73,‎ 1996, p. 521-531
↑ Luke, « On the computation of Log Z and Arc tan Z », Mathematical Tables and Other Aids to Computation, vol. 11,‎ 1957, p. 16-18

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

Extrapolation de Richardson

ε-algorithme

ρ-algorithme

[1] Brezinski, « Accélération des suites à convergence logarithmique », Comptes rendus de l'académie des sciences, Paris, vol. 273A,‎ 1971, p. 727-730

[2] Weniger, « Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series », Computer Physics Reports, vol. 10,‎ 1989, p. 189-371

[3] Lubkin, « A method of summing infinite series », Journal of research of the National Bureau of Standards, vol. 48,‎ 1952, p. 228-254

[4] Cordellier, « Caractérisation des suites que la première étape du θ-algorithme transforme en suites constantes », Compte rendu de l'académie des sciences, Paris, vol. 290A,‎ 1977, p. 389-392

[5] Sidi, « A convergence and stability study of the iterated Lubkin transformation and the θ-algorithm », Mathematics of computation, vol. 72,‎ 2003, p. 419-433

[6] Osada, « An acceleration theorem for the ρ-algorithm », Numerische Mathematik, vol. 73,‎ 1996, p. 521-531

[7] Luke, « On the computation of Log Z and Arc tan Z », Mathematical Tables and Other Aids to Computation, vol. 11,‎ 1957, p. 16-18

[1]

[2]

[3]

[4]

[5]

[6]

[7]