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.

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.