Ê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
Vitesse de convergence des suites
Résumé
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. C'est ce que l'on fait lorsqu'on étudie la complexité des algorithmes trouvant ce qu'ils cherchent en un nombre fini d'étapes.
Cette section décrit quelques notions de vitesse de convergence d'une suite d'un espace vectoriel normé , vers sa limite , fondées sur la comparaison de la norme de l'erreur de deux éléments successifs. L'erreur est toujours supposée non nulle : , pour tout indice . Cette hypothèse est raisonnable lorsque la suite est générée par un algorithme « bien conçu », c'est-à-dire pour lequel dès que , la suite devient stationnaire après (tous les itérés suivants sont égaux à et il n'y a plus de sens à parler de vitesse de convergence). On s'intéresse donc au quotient
où est un nombre réel strictement positif. L'intérêt pour ce quotient provient du fait qu'on peut souvent l'estimer en faisant un développement de Taylor autour de des fonctions définissant le problème que l'on cherche à résoudre et dont est solution. Évidemment, plus est grand, plus la vitesse de convergence est rapide (car asymptotiquement ).
Brièvement, on dit que le q-ordre de convergence est si le quotient ci-dessus est borné. Le préfixe q-, qui rappelle le mot quotient, est souvent omis. On dit aussi que la convergence est :
linéaire s'il existe une norme , un réel et un indice tels que pour tout , ;
superlinéaire si ;
quadratique (ordre 2) s'il existe une constante telle que pour tout indice , ;
cubique (ordre 3) s'il existe une constante telle que pour tout indice , ;
quartique (ordre 4) s'il existe une constante telle que pour tout indice ,
Les trois principales vitesses de convergence en quotient sont les vitesses de convergence linéaire, superlinéaire et quadratique.
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.