Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Transformation de Shanks
Résumé
En analyse numérique, la transformation de Shanks est une méthode non linéaire d'accélération de la convergence de suites numériques. Cette méthode est nommée d'après Daniel Shanks, qui l'exposa en 1955, bien qu'elle ait été étudiée et publiée par R. J. Schmidt dès 1941. C'est une généralisation de l'algorithme Delta-2 d'Aitken.
Soit une suite numérique (An) dont on cherche à connaitre la limite A.
La transformée de Shanks d'ordre k de cette suite est donnée par le rapport de deux déterminants :
avec et
La transformée de Shanks d'ordre k donne exactement la limite de la suite d'origine A si celle-ci vérifie l'équation aux différences linéaire à coefficients constants d'ordre k du type :
avec les constantes arbitraires ap telles que
Ce modèle de comportement de convergence possède 2k + 1 inconnues. En évaluant l'équation ci-dessus pour A, A, ..., A, on obtient l'expression de la transformée de Shanks e(A) en résolvant l'inconnue A dans le système obtenu.
En résolvant l'équation aux différences linéaire, on peut expliciter la forme de A pour laquelle la transformée de Shanks d'ordre k fournit la limite exacte :
Les λp étant les m racines du polynôme , Qpkp(n) étant un polynôme arbitraire en n, dont le degré kp est la multiplicité de la racine λp. Les racines pouvant être complexes, le comportement de An englobe de nombreuses formes : combinaisons linéaires d'exponentielles décroissantes ou croissantes avec des sinusoïdes amorties ou amplifiées.
Lorsque la suite à accélérer est la somme partielle d'un développement en série entière d'une fonction :
alors, les différentes transformées de Shanks de la suite constituent le tableau de Padé de la série :
avec l'approximant de Padé d'indice (k + n, k) de f(x) (la fraction rationnelle de degré n + k au numérateur et k au dénominateur dont le développement limité coïncide avec celui de f(x) jusqu'au degré 2k + n). La transformation de Shanks fournit donc un moyen de calculer les différents approximants de Padé d'une fonction dont on connait le développement limité.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (7)
Concepts associés (2)
Extrapolation de Richardson
En analyse numérique, le procédé d'extrapolation de Richardson est une technique d'accélération de la convergence. Il est ainsi dénommé en l'honneur de Lewis Fry Richardson, qui l'a popularisé au début du . Les premières utilisations remontent à Huygens en 1654 et Takebe Kenkō en 1723, pour l'évaluation numérique de π. Ce procédé est notamment utilisé pour définir une méthode numérique d'intégration : la méthode de Romberg, accélération de la méthode des trapèzes.
Vitesse de convergence des suites
En analyse numérique — une branche des mathématiques — on peut classer les suites convergentes en fonction de leur vitesse de convergence vers leur point limite. C'est une manière d'apprécier l'efficacité des algorithmes qui les génèrent. Les suites considérées ici sont convergentes sans être stationnaires (tous leurs termes sont même supposés différents du point limite). Si une suite est stationnaire, tous ses éléments sont égaux à partir d'un certain rang et il est alors normal de s'intéresser au nombre d'éléments différents du point limite.