Prolégomènes à l’algorithmique

Prolégomènes à l’algorithmique

Vitesse de convergence des suites

In those days, we needed faster convergence to get results in the few hours between expected failures of the Avidac’s large roomful of a few thousand bytes of temperamental electrostatic memory. W.C. Davidon, dans la nouvelle introduction de son article fondateur des méthodes de quasi-Newton, écrit en 1959, mais qui ne fut publié qu’en 1991, lors de la parution du premier numéro de la revue SIAM Journal on Optimization [155, 156]. Les algorithmes d’optimisation génèrent des suites {xk}k>1 convergeant vers une solution x∗ du problème (dans les bons cas !). Ils procèdent ainsi parce que, dans la plupart des problèmes que nous allons rencontrer, il n’est pas possible de calculer une solution en un nombre fini d’opérations arithmétiques. Les éléments xk de la suite générée sont appelés des itérés. Étant donné un itéré xk, on calcule l’itéré suivant xk+1 de telle sorte que celui-ci soit, si possible, plus proche de la solution cherchée x∗ que ne l’est xk. Se pose alors le problème de comparer l’efficacité des algorithmes par l’examen des suites qu’ils génèrent, dans le pire des cas. La notion de vitesse de convergence permet de qualifier le comportement asymptotique (pour xk proche de x∗) d’une suite. On distingue deux classes de vitesses de convergence : les vitesses de convergence en quotient (section 5.1.1) et en racine (section 5.1.2). Ces notions sont motivées par des considérations pratiques : on peut en effet démontrer que les suites générées par les algorithmes étudiés dans cet ouvrage ont de telles vitesses de convergence. 

Vitesses de convergence en quotient

Dans cette section, on cherche à qualifier la vitesse de convergence d’une suite {xk} d’un espace normé E, de norme notée k· k, en comparant la norme de l’erreur xk −x∗ de deux itérés successifs, c’est-à-dire en comparant kxk − x∗k et kxk+1 − x∗k. On supposera toujours que l’erreur ne s’annule pas (xk 6= x∗, pour tout indice k). Cette hypothèse est raisonnable, car dans les algorithmes bien conçus, dès que xk = x∗, la suite devient stationnaire après xk (tous les itérés suivants sont égaux à x∗) et il n’y a plus de sens à parler de vitesse de convergence. On s’intéresse donc au quotient kxk+1 − x∗k kxk − x∗k α , (5.1) où α est un entier non nul. 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 x∗ des fonctions définissant le problème que l’on cherche à résoudre et dont x∗ est solution. Les noms des vitesses de convergence de cette section seront préfixés par « q- » pour rappeler qu’il s’agit de vitesse de convergence en quotient. Numériquement, plus rapide est la convergence, plus vite augmente le nombre de chiffres significatifs corrects de xk, c’est-à-dire de chiffres significatifs identiques à ceux de x∗. Donnons une définition plus précise de cette notion. Si xk est un vecteur, on ne peut pas définir par un scalaire la correction des chiffres significatifs de toutes ses composantes, mais on peut le faire en moyenne au sens de la norme sur E. On suppose que x∗ 6= 0 car on ne peut définir ce que sont les chiffres significatifs de zéro. Si kxk − x∗k/kx∗k vaut 10−4 , on dira que xk a 4 chiffres significatifs corrects. Ceci conduit à la définition suivante.

Définition 5.1 (nombre de chiffres significatifs corrects)

Le nombre de chiffres significatifs corrects de xk par rapport à x∗ 6= 0 est le nombre réel défini par σk := − log10 kxk − x∗k kx∗k . ✷ Lorsque x∗ 6= 0, on peut exprimer les vitesses de convergence en quotient en utilisant σk plutôt que le quotient (5.1), ce que nous ferons. Il est parfois intéressant de vérifier numériquement que les suites générées par un algorithme ont bien la vitesse de convergence attendue, celle démontrée théoriquement pour l’algorithme considéré. Bien sûr, c’est une manière de vérifier que l’algorithme est bien implémenté, mais il y a une autre motivation. Par exemple, sous certaines hypothèses de régularité, on verra que l’algorithme de Newton converge qquadratiquement (théorème 10.2) ; cet algorithme procède par linéarisation de la fonction qu’il cherche à annuler ; vérifier que la convergence des suites générées est bien q-quadratique est alors une indication sur la correction du calcul des dérivées. Comme on ne connaît pas la solution, on ne peut vérifier la vitesse de convergence en quotient attendue par l’examen du quotient (5.1), qu’en résolvant deux fois le problème ; la première fois pour calculer une approximation précise de la solution x∗, la seconde pour faire l’examen des quotients susmentionnés ; c’est dommage. On pourrait aussi mémoriser tous les itérés et considérer que le dernier itéré est la solution, mais en grande dimension, cette une opération est bien trop gourmande en place mémoire. On peut éviter cette double résolution ou la mémorisation des itérés si l’on arrive à exprimer la vitesse de convergence en termes d’une quantité dont la limite est connue, typiquement nulle. Il en est ainsi si l’algorithme cherche à annuler une fonction F : E → E,