En 2000, J. Dongarra et F. Sullivan établirent une liste des 10 plus importants algorithmes du XXe siècle. Quelle que soit la part d’arbitraire d’un tel choix, chacun de ces algorithmes a changé notre monde par ses nombreuses applications. Plusieurs d’entre eux ont fait ou feront l’objet d’un article dans cette rubrique.
L’algorithme QR, conçu par l’anglais John Francis en 1959, fait partie de la liste. Le rapporteur de l’article soumis par Francis fut tellement surpris par la preuve de convergence qu’il garda le manuscrit sous le coude pendant près de deux ans. La publication n’intervint donc qu’en 1961, ce qui laissa le temps à une concurrente russe, Vera Kublanovskaïa, d’élaborer sa propre version.
John Francis
Matrices et valeurs propres
Un vecteur est une liste de valeurs numériques, qui décrit par exemple l’état d’un système physique. Une matrice est un tableau de nombres, qui dit comment passer d’un vecteur à un autre, dans un contexte linéaire. Ce dernier est pertinent quand on traite des petites échelles. La situation est particulièrement intéressante lorsque les vecteurs décrivent deux états successifs d’un même système ; on peut itérer le processus ad libitum. On voit alors apparaître des vecteurs particuliers, dits propres, sur lesquels la matrice agit par simple multiplication. Les facteurs correspondants sont les valeurs propres. Ces nombres sont responsables de la stabilité, ou de l’instabilité, du système, ainsi que de ses oscillations le cas échéant.
Il est donc crucial de pouvoir calculer les valeurs propres d’une matrice et c’est ce que fait l’algorithme QR.
Valeurs propres et équation polynomiales
La recherche des valeurs propres d’une matrice est équivalente à celle des racines d’un polynôme. D’une part, on associe à une matrice son polynôme caractéristique, dont les valeurs propres sont les racines. De même, on associe à un polynôme sa matrice compagnon. On pourrait donc penser naïvement que le calcul effectif de valeurs propres est un sous-produit de celui de racines. Il n’en est rien. Au contraire, l’algorithme QR est tellement performant qu’il est utilisé aussi pour résoudre les équations polynômiales.
L’algorithme QR
Une matrice carrée \(A\) se factorise sous la forme \(A = QR\) où \(Q\) est une matrice orthogonale (sa transposée est égale à son inverse) et \(R\) est triangulaire supérieure à diagonale positive. Cette factorisation est même unique si \(A\) est inversible.
La matrice \(A’= RQ\) est semblable à \(A\) car \(A’ = Q^{-1}AQ\). Elle a donc les mêmes valeurs propres. Le procédé \(A\mapsto A’\) est la brique de base de l’algorithme~QR. Le premier résultat de Francis dit que sous des hypothèses raisonnables sur la matrice initiale, la forme de la matrice itérée tend à devenir triangulaire supérieure, les valeurs propres se lisant alors sur sa diagonale.
Il faudrait dire plus, mais c’est plus compliqué. Une fois le théorème démontré, Francis a expliqué comment implémenter l’algorithme de façon efficace. Si la preuve et l’efficacité ne faisaient aucun doute, il a fallu une vingtaine d’années pour comprendre ce qui le faisait «vraiment» fonctionner. De plus, dans des versions plus récentes (Braman, Byers et Mathias, 2002, cf. ici et là), la transformation QR cède le premier rôle à des idées plus sophistiquées.
Le principal intérêt de QR est sa stabilité, due au fait que \(A’\) est unitairement conjuguée à \(A\). Cette propriété garantit que les erreurs d’arrondi ne sont pas amplifiées.
Les articles originaux, {The QR transformation a unitary analogue to the LR transformation}, Part 1 & 2, sont publiés dans {The Computer Journal}, volume 4, respectivement en 1961 (pp 265-271) et 1962 (pp 332-345).
En 2011, David Watkins a également écrit un article sur l’algorithme QR de John Francis dans « The American Mathematical Monthly ». On peut le trouver ici.
Né à Londres en 1934, Francis quitta le lycée pour un service militaire de deux ans, qui l’emmena jusqu’en Corée. À son retour en 1954, il entra à la National Research Development Corporation (NRDC), un organisme gouvernemental chargé du transfert de technologie du secteur public vers le privé. Il reprit alors des études à Cambridge, mais la coupure avait été trop longue et il abandonna au bout d’un an, retournant à la NRDC. C’est là qu’il mit au point l’algorithme QR. Mais comme cela n’entrait pas dans sa mission, la NRDC ne déposa pas de brevet ; on n’ose imaginer les sommes colossales ainsi perdues !
John Francis en juillet 2008
Francis ne revint jamais vers le secteur académique. Lorsqu’il prit sa retraite, aucun scientifique en activité ne l’avait jamais rencontré. Au début des années 2000, deux mathématiciens, G. Golub et F. Uhlig entreprirent, chacun de son côté, de retrouver sa trace. Mais comment localiser quelqu’un portant un nom aussi commun que John Francis ? Uhlig trouva au Musée des sciences et de l’industrie de Manchester les archives d’une compagnie où l’on savait que Francis avait travaillé après 1961. Il en retira une date de naissance, et surtout le “middle name”. Muni de ce complément, mais sans grand espoir, Uhlig fit une recherche sur internet. À sa grande surprise, il obtint une réponse pertinente : Francis avait signé de son nom complet une pétition dans une paroisse de Hove, petite ville côtière sur la Manche, près de Brighton.
Peu après, Golub et Uhlig, se rencontrant lors d’une conférence, découvrirent leur intérêt commun et échangèrent leurs informations. Le 7 août 2007, Golub rendit visite à Francis, en l’absence d’Uhlig qui n’était pas disponible. Golub rendit compte de cet entretien à quelques collègues, mais en novembre de la même année, il s’éteignait. À nouveau, Francis était totalement coupé de la communauté scientifique ! Ce n’est qu’en juillet 2008 qu’Uhlig put rétablir le contact. Finalement, il le convainquit d’accepter une invitation à un symposium organisé à Glasgow en 2009, pour célébrer le 50e anniversaire de QR. Puis Francis reçut un doctorat Honoris causa en juillet 2015 à l’Université du Sussex.
Gene Golub et Frank Uhlig, découvrant qu’ils savent tous deux retrouver John Francis
Le plus remarquable dans ce conte de fées est que Francis fut retrouvé en partie grâce à son algorithme. Aux débuts de Google, dans un modeste garage de la baie de San Francisco, L. Page et S. Brin, qui cherchaient à créer un algorithme de recherche sur internet vraiment efficace, rencontrèrent Golub. Celui-ci les orienta vers son propre algorithme de calcul des valeurs singulières (SVD) d’une matrice. Et de fait, SVD est une spécialisation de QR pour les matrices bi-diagonales. Ceux qui ont connu internet avant 1998 savent à quel point l’algorithme PageRank a changé la face du monde.
John Francis à la conférence consacrée à l’algorithme QR
Public
Post-scriptum
Ce texte est largement inspiré du témoignage de Frank Uhlig, “Finding John Francis who found QR fifty years ago”, publié dans le numéro 43 d’IMAGE en 2009.
Images des mathématiques remercie Frank Uhlig pour les photographies de John Francis et l’autorisation de les utiliser.
Retrouvez tous les billets publiés à l’occasion des 80 ans du CNRS.
ÉCRIT PAR
Denis Serre
Professeur émérite - Unité de Mathématiques Pures et Appliquées, Ecole Normale Supérieure de Lyon
Il est possible d’utiliser des commandes LaTeX pour rédiger des commentaires — mais nous ne recommandons pas d’en abuser ! Les formules mathématiques doivent être composées avec les balises .
Par exemple, on pourra écrire que sont les deux solutions complexes de l’équation .
Si vous souhaitez ajouter une figure ou déposer un fichier ou pour toute autre question, merci de vous adresser au secrétariat.