Thêta algorithme

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 modifier

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 modifier

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. Seules les deux dernières diagonales ascendantes sont indispensables, 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érer à 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 modifier

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 à 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 le θ-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ées d'entrée pour le θ-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.

Par exemple, la fonction Arc sinus sur $[-1, +1]$ , dont la série de Tchebychev vaut :

${\frac {\pi }{4}}Arcsin(x)=\sum _{n=0}^{\infty }{\frac {T_{2n+1}(x)}{(2n+1)^{2}}}$ devient après changement de variable la série entière :

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

dont on pourra accélérer la convergence en utilisant le θ-algorithme (avec des nombres complexes) sur les sommes partielles de cette série. La partie réelle du résultat sera la valeur accélérée de la série de Tchebychev d'origine.

Le graphique ci dessous compare la fonction Arc sinus avec sa série de Tchebychev en retenant les 7 premiers termes (série de Tchebychev de degré 13), ainsi que la valeur accélérée de cette série partielle par l'ε-algorithme et le θ-algorithme. Avec 7 termes, l'ε-algorithme a pu être poussé jusqu'à la 6ème colonne, et le θ-algorithme, jusqu'à la 4ème colonne.

Accélération de la convergence de série de Tchebychev de l'Arc sinus(x) par le thêta algorithme

La série de Tchebychev converge assez lentement (coefficients décroissant en 1/n²), du fait que la fonction Arc sinus n'est pas dérivable aux extrémités de l'intervalle. L'ε-algorithme accélère significativement la convergence, sauf dans les zones proches des extrémités. Le θ-algorithme donne de bons résultats, sur tout l'intervalle, incluant les extrémités.

Notes et références modifier

↑ Charles Brezinski, « Accélération des suites à convergence logarithmique », Comptes rendus de l'académie des sciences, Paris, vol. 273A,‎ 1971, p. 727-730
↑ Ernst Joachim Weniger, « Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series », Computer Physics Reports, vol. 10,‎ 1989, p. 189-371
↑ Samuel Lubkin, « A method of summing infinite series », Journal of research of the National Bureau of Standards, vol. 48,‎ 1952, p. 228-254
↑ Florient 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
↑ Avram Sidi, « A convergence and stability study of the iterated Lubkin transformation and the θ-algorithm », Mathematics of computation, vol. 72,‎ 2003, p. 419-433
↑ Naoki Osada, « An acceleration theorem for the ρ-algorithm », Numerische Mathematik, vol. 73,‎ 1996, p. 521-531

Annexes modifier

Bibliographie modifier

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

Articles connexes modifier

Portail de l'analyse

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

[2] Ernst Joachim 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] Samuel Lubkin, « A method of summing infinite series », Journal of research of the National Bureau of Standards, vol. 48,‎ 1952, p. 228-254

[4] Florient 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] Avram Sidi, « A convergence and stability study of the iterated Lubkin transformation and the θ-algorithm », Mathematics of computation, vol. 72,‎ 2003, p. 419-433

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

[1]

[2]

[3]

[4]

[5]

[6]