Voir la source de Algorithme QR


En algèbre linéaire numérique, l' '''algorithme QR''' ou '''itération QR''' est un [[Algorithme de recherche de valeur propre|algorithme de recherche de valeurs propres]], une procédure permettant de calculer les [[Valeur propre, vecteur propre et espace propre|valeurs et vecteurs propres]] d'une [[Matrice (mathématiques)|matrice]] . L'algorithme QR a été développé à la fin des années 1950 par [[John G. F. Francis|John G.F. Francis]] et par [[Vera Kublanovskaïa|Vera N. Kublanovskaïa]], travaillant indépendamment<ref>{{Article|auteur1=Francis|prénom1=J. G. F.|titre=The QR Transformation, II|périodique=The Computer Journal|volume=4|numéro=4|pages=332–345|année=1962|doi=10.1093/comjnl/4.4.332}}</ref>. L'idée de base est d'effectuer une [[décomposition QR]], en écrivant la matrice comme un produit d'une [[matrice orthogonale]] et d'une [[matrice triangulaire]] supérieure, en multipliant les facteurs dans l'ordre inverse et en itérant.

== Algorithme QR en pratique ==
Formellement, soit {{Formule|''A''}} une matrice réelle dont on veut calculer les valeurs propres, et soit {{Formule|1=''A''<sub>0</sub> := ''A''}} . À la {{Mvar|k}} -ième étape (en commençant par {{Formule|1=''k'' = 0}} ), on calcule la [[décomposition QR]] {{Formule|1=''A''<sub>''k''</sub> = ''Q''<sub>''k''</sub>&thinsp;''R''<sub>''k''</sub>}} où {{Formule|''Q''<sub>''k''</sub>}} est une [[matrice orthogonale]] (c'est-à-dire {{Formule|1=''Q''<sup>T</sup> = ''Q''<sup>−1</sup>}} ) et {{Formule|''R''<sub>''k''</sub>}} est une matrice triangulaire supérieure. On forme alors {{Formule|1=''A''<sub>''k''+1</sub> = ''R''<sub>''k''</sub>&thinsp;''Q''<sub>''k''</sub>}} . On peut alors noter que <math display="block"> A_{k+1} = R_k Q_k = Q_k^{-1} Q_k R_k Q_k = Q_k^{-1} A_k Q_k = Q_k^{\mathsf{T}} A_k Q_k, </math> ainsi tous les {{Formule|''A''<sub>''k''</sub>}} sont [[Matrices semblables|semblables]] et ont donc les mêmes valeurs propres. L'algorithme est [[Stabilité numérique|numériquement stable]] car il procède par transformations de similarité ''orthogonales'' .

Sous certaines conditions<ref name="golubvanloan">{{Ouvrage|prénom1=G. H.|nom1=Golub|prénom2=C. F.|nom2=Van Loan|titre=Matrix Computations|lieu=Baltimore|éditeur=Johns Hopkins University Press|année=1996|isbn=0-8018-5414-8}}</ref>, les matrices ''A'' <sub>''k''</sub> convergent vers une matrice triangulaire, la [[Décomposition de Schur|forme de Schur]] de ''A'' . Les valeurs propres d'une matrice triangulaire sont ses éléments diagonaux et le problème des valeurs propres est résolu. Lors des tests de convergence, il n’est pas pratique d’exiger des zéros exacts,{{Référence nécessaire|date=July 2020}} mais le [[Théorème de Gerschgorin|théorème de Gershgorin]] fournit une limite à l'erreur.

=== En utilisant la forme de Hessenberg ===
Dans la forme brute ci-dessus, les itérations sont relativement coûteuses. Cela peut être atténué en prenant d'abord la [[Matrice de Hessenberg|forme de Hessenberg]] supérieure de la matrice {{Mvar|A}} (ce qui coûte <math display="inline">\tfrac{10}{3} n^3 + \mathcal{O}(n^2)</math> opérations arithmétiques utilisant une technique basée sur la [[Transformation de Householder|réduction de Householder]] ), avec une suite finie de transformations de similarité orthogonales, un peu comme une décomposition QR bilatérale.<ref name="Demmel">{{Ouvrage|prénom1=James W.|nom1=Demmel|lien auteur1=James W. Demmel|titre=Applied Numerical Linear Algebra|éditeur=SIAM|année=1997}}</ref>{{,}}<ref name="Trefethen">{{Ouvrage|prénom1=Lloyd N.|nom1=Trefethen|lien auteur1=Lloyd N. Trefethen|prénom2=David|nom2=Bau|titre=Numerical Linear Algebra|éditeur=SIAM|année=1997}}</ref> (Pour la décomposition QR, les réflecteurs de Householder sont multipliés uniquement à gauche, mais pour le cas de Hessenberg, ils sont multipliés à la fois à gauche et à droite.) Déterminer la décomposition QR d'une matrice de Hessenberg supérieure coûte <math display="inline">6 n^2 + \mathcal{O}(n)</math> opérations arithmétiques. De plus, comme la forme de Hessenberg est déjà presque triangulaire supérieure (elle n'a qu'une seule entrée non nulle sous chaque diagonale), son utilisation comme point de départ réduit le nombre d'étapes nécessaires à la convergence de l'algorithme QR.

Si la matrice d'origine est [[Matrice symétrique|symétrique]], alors la matrice de Hessenberg supérieure est également symétrique et donc [[Matrice tridiagonale|tridiagonale]], et il en va de même pour toutes les {{Formule|''A''<sub>''k''</sub>}} . Dans ce cas, atteindre la forme Hessenberg coûte <math display="inline">\tfrac{4}{3} n^3 + \mathcal{O}(n^2)</math> opérations arithmétiques utilisant une technique basée sur la réduction de Householder<ref name="Demmel"/>{{,}}<ref name="Trefethen"/>. Déterminer la décomposition QR d'une matrice tridiagonale symétrique coûte <math>\mathcal{O}(n)</math> opérations<ref>{{Article|auteur1=Ortega|prénom1=James M.|auteur2=Kaiser|prénom2=Henry F.|titre=The ''LL<sup>T</sup>'' and ''QR'' methods for symmetric tridiagonal matrices|périodique=The Computer Journal|volume=6|numéro=1|pages=99–101|année=1963|doi=10.1093/comjnl/6.1.99}}</ref>.

=== Phase d'itération ===
Si une matrice de Hessenberg <math>A</math> a un élément <math> a_{k,k-1} = 0 </math> pour certains <math>k</math>, c'est-à-dire que si l'un des éléments de la sous-diagonale est nul, alors il se décompose en blocs dont les problèmes propres peuvent être résolus séparément ; une valeur propre est soit une valeur propre de la sous-matrice des premières <math>k-1</math> lignes et colonnes, ou une valeur propre de la sous-matrice des lignes et colonnes restantes. Le but de l'étape d'itération QR est de réduire l'un de ces éléments <math>a_{k,k-1}</math> de sorte qu'un petit bloc le long de la diagonale soit effectivement séparé de bloc principal de la matrice. Dans le cas d'une valeur propre réelle qui est généralement un bloc <math> 1 \times 1 </math>  dans le coin inférieur droit (auquel cas l'élément <math> a_{nn} </math> contient cette valeur propre), alors que dans le cas d'une paire de valeurs propres complexes conjuguées, c'est un bloc <math> 2 \times 2 </math> dans le coin inférieur droit.

Le [[Vitesse de convergence des suites|taux de convergence]] dépend de la séparation entre les valeurs propres, donc un algorithme pratique utilisera des décalages, explicites ou implicites, pour augmenter la séparation et accélérer la convergence. Un algorithme QR symétrique typique isole chaque valeur propre (puis réduit la taille de la matrice) avec seulement une ou deux itérations, ce qui le rend efficace et robuste.{{Pas clair|date=June 2012}}<sup class="noprint Inline-Template" style="margin-left:0.1em; white-space:nowrap;">&#x5B; ''[[aide:Préciser un fait|<span title="The text near this tag may need clarification or removal of jargon. (June 2012)">clarification nécessaire</span>]]'' &#x5D;</sup>

==== Une seule itération avec décalage explicite ====
Les étapes d'une itération QR avec décalage explicite sur une matrice de Hessenberg réelle <math>A</math> sont:

# Choisir un décalage <math>\mu</math> et le soustraire de tous les éléments diagonaux, produisant la matricex <math> A - \mu I </math>. Une stratégie classique est de prendre <math> \mu = a_{n,n} </math>, mais ce choix n'est pas optimal pour accélérer la convergence. Le mieux est de choisir <math> \mu </math> proche d'une valeur propre, afin d'accélérer la convergence vers cette valeur propre.
# Calculer la suite des rotations de Givens <math> G_1, G_2, \dots, G_{n-1} </math> sur <math> A - \mu I </math>, où<math> G_i </math> agit sur les lignes <math>i</math> et <math>i+1</math>, et <math> G_i </math> est choisi pour annuler le coefficient en <math>(i+1,i)</math> de <math> G_{i-1} \dotsb G_1 (A - \mu I) </math>. Cela produit une matrice triangulaire supérieure <math> R = G_{n-1} \dotsb G_1 (A - \mu I) </math>. Le facteur orthogonal <math> Q </math> sera alors <math> G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, mais il n'est ni nécessaire ni efficace de calculer cette matrice explicitement.
# On multiplie <math> R </math> par les matrices de Givens <math> G_1^\mathrm{T} </math>, <math> G_2^\mathrm{T} </math>, …, <math> G_{n-1}^\mathrm{T} </math> à droite, où <math> G_i^\mathrm{T} </math> agit sur les colonnes <math>i</math> et <math> i+1 </math>. On obtient la matrice <math> RQ = R G_1^\mathrm{T} G_2^\mathrm{T} \dotsb G_{n-1}^\mathrm{T} </math>, qui est également une matrice de Hessenberg.
# On annule le décalage en ajoutant <math> \mu </math> à toutes les valeurs diagonales. Le résultat est alors <math> A' = RQ + \mu I </math>. Puisque <math>Q</math> commute avec <math>I</math>, on retrouve <math> A' = Q^\mathrm{T} (A-\mu I) Q + \mu I = Q^\mathrm{T} A Q </math>.

Le but du décalage est de modifier les rotations Givens choisies.

Plus en détail, la structure de l'une des matrices <math> G_i </math> est <math display="block">
 G_i = \begin{bmatrix}
  I & 0 & 0 & 0 \\
  0 & c & -s & 0 \\
  0 & s & c & 0 \\
  0 & 0 & 0 & I
 \end{bmatrix}
</math> où le <math>I</math> dans le coin supérieur gauche se trouve un bloc identité <math> (n-1) \times (n-1) </math> et les deux scalaires <math> c = \cos\theta </math> et <math> s = \sin\theta </math> sont déterminés par l'angle de rotation <math> \theta </math>  approprié pour annuler le coefficient <math>(i+1,i)</math> . Il n'est pas nécessaire d'expliciter <math> \theta </math> ; les facteurs <math> c </math> et <math> s </math> peuvent être déterminés directement à partir des éléments sur lesquels la matrice <math> G_i </math> devrait agir. Il n'est pas non plus nécessaire de produire la matrice entière ; multiplier (à gauche) par <math> G_i </math> n'affecte que les lignes <math> i </math> et <math> i+1 </math>, il est donc plus simple de simplement mettre à jour ces deux lignes directement. De même, pour la multiplication par <math> G_i^\mathrm{T} </math> à droite à l'étape 3, il suffit de calculer <math>i</math>, <math>c</math>, et <math>s</math> .

Si on utilise le facteur <math> \mu = a_{n,n} </math>, alors au début de l'étape 2, on a
<math display="block">
  A - a_{n,n} I = \begin{pmatrix}
    \times & \times & \times & \times & \times \\
    \times & \times & \times & \times & \times \\
    0 & \times & \times & \times & \times \\
    0 & 0 & \times & \times & \times \\
    0 & 0 & 0 & \times & 0
  \end{pmatrix}
</math>
où le signe <math>\times</math> désigne une valeur quelconque. La première rotation de Givens <math> G_1 </math> annuler le coefficient en <math> (i+1,i) </math>, on a alors
<math display="block">
  G_1 (A - a_{n,n} I) = \begin{pmatrix}
    \times & \times & \times & \times & \times \\
    0 & \times & \times & \times & \times \\
    0 & \times & \times & \times & \times \\
    0 & 0 & \times & \times & \times \\
    0 & 0 & 0 & \times & 0
  \end{pmatrix}
  \text{.}
</math>
Chaque nouvelle rotation annule un autre élément sous-diagonale, ce qui augmente le nombre de zéros connus jusqu'à ce que
<math display="block">
  H = G_{n-2} \dotsb G_1 (A - a_{n,n} I) = \begin{pmatrix}
    \times & \times & \times & \times & \times \\
    0 & \times & \times & \times & \times \\
    0 & 0 & \times & \times & \times \\
    0 & 0 & 0 & h_{n-1,n-1} & h_{n-1,n} \\
    0 & 0 & 0 & h_{n,n-1} & 0
  \end{pmatrix}
  \text{.}
</math>
La dernière rotation <math>G_{n-1}</math> a des valeurs <math>(c,s)</math> choisis telles que <math> s h_{n-1,n-1} + c h_{n,n-1} = 0 </math>. Si <math> |h_{n-1,n-1}| \gg |h_{n,n-1}| </math>, ce qui arrive couramment quand on arrive à la fin du processus de convergence, alors <math> c \approx 1 </math> et <math> |s| \ll 1 </math>. Ainsi, la rotation donne
<math display="block">
  R = G_{n-1} G_{n-2} \dotsb G_1 (A - a_{n,n} I) = \begin{pmatrix}
    \times & \times & \times & \times & \times \\
    0 & \times & \times & \times & \times \\
    0 & 0 & \times & \times & \times \\
    0 & 0 & 0 & \times & c h_{n-1,n} \\
    0 & 0 & 0 & 0 & s h_{n-1,n}
  \end{pmatrix}
  \text{,}
</math>
qui est la matrice triangulaire supérieure attendue. On en est alors à l'étape 3 et on effectue les rotations sur les données des colonnes. La première rotation agit sur les colonnes <math>1</math> et <math>2</math>, produisant
<math display="block">
  R G_1^\mathrm{T} = \begin{pmatrix}
    \times & \times & \times & \times & \times \\
    \times & \times & \times & \times & \times \\
    0 & 0 & \times & \times & \times \\
    0 & 0 & 0 & \times & c h_{n-1,n} \\
    0 & 0 & 0 & 0 & s h_{n-1,n}
  \end{pmatrix}
  \text{.}
</math>
Le motif attendu est que chaque rotation déplace une valeur non nulle de la diagonale vers la sous-diagonale, ramenant la matrice vers une forme de Hessenberg. Ceci s'arrête à
<math display="block">
  R G_1^\mathrm{T} \dotsb  G_{n-1}^\mathrm{T} = \begin{pmatrix}
    \times & \times & \times & \times & \times \\
    \times & \times & \times & \times & \times \\
    0 & \times & \times & \times & \times \\
    0 & 0 & \times & \times & \times \\
    0 & 0 & 0 & -s^2 h_{n-1,n} & cs h_{n-1,n}
  \end{pmatrix}
  \text{.}
</math>
Algébriquement la forme est inchangée, mais numériquement l'élément en position <math> (n,n-1) </math> est devenu bien plus petit : il y a un facteur <math> s </math> entre lui et l'élément diagonal au-dessus, mais maintenant, l'écart est plus d'un facteur <math> s^2 </math>, et une nouvelle itération amènerait à un facteur <math> s^4 </math>: il y a convergence quadratique. En pratique, cela signifie <math>O(1)</math> itérations par valeur propre suffit pour avoir la convergence, et donc en tout, on peut compléter l'algorithme en <math> O(n) </math> étapes QR, chacune d'entre elle exécutant <math> O(n^2) </math> opérations arithmétiques (ou au moins <math> O(n) </math> opérations, dans le cas où  <math> A </math> est symétrique).

== Visualisation ==
[[Fichier:QR_and_LR_visualization_illustrating_fixed_points_(corrected).gif|vignette| Figure 1 : Comment la sortie d'une seule itération de l'algorithme QR ou LR varie en fonction de son entrée]]
L'algorithme QR de base peut être visualisé dans le cas où ''A'' est une matrice symétrique définie positive. Dans ce cas, ''A'' peut être représenté comme une [[Ellipse (mathématiques)|ellipse]] en 2 dimensions ou un [[ellipsoïde]] en dimensions supérieures. La relation entre l’entrée de l’algorithme et une itération unique peut alors être représentée comme dans la figure 1. Le résultat de l'algorithme LR est représenté à côté de l'algorithme QR.

Une seule itération provoque l'inclinaison ou la « chute » de l'ellipse vers l'axe des x. Dans le cas où le grand demi-axe de l'ellipse est parallèle à l'axe des ''x'', une itération de QR ne fait rien. Une autre situation dans laquelle l'algorithme « ne fait rien » est lorsque le grand demi-axe est parallèle à l'axe des ''y'' au lieu de l'axe des ''x''. Dans ce cas, l’ellipse peut être considérée comme étant en équilibre instable sans pouvoir tomber dans un sens ou dans l’autre. Dans les deux cas, la matrice est diagonale. Une situation dans laquelle une itération de l'algorithme « ne fait rien » est appelée un [[point fixe]] . La stratégie employée par l'algorithme est une méthode du point fixe . On observe alors qu’un point fixe est stable tandis que l’autre est instable. Si l'ellipse était inclinée très légèrement par rapport au point fixe instable, une itération de l'algorithme QR entraînerait l'inclinaison de l'ellipse à l'opposé du point fixe au lieu de s'en rapprocher. Finalement, l’algorithme convergerait vers un point fixe différent, mais cela prendrait beaucoup de temps.

=== Recherche de valeurs propres ou des vecteurs propres ===
[[Fichier:Qr_lr_eigenvalue_clash.gif|vignette| Figure 2 : Comment la sortie d'une seule itération de QR ou LR est affectée lorsque deux valeurs propres se rapprochent l'une de l'autre]]
Il convient de souligner que trouver même un seul vecteur propre d'une matrice symétrique n'est pas calculable (en arithmétique réelle exacte selon les définitions de l'analyse calculable )<ref>{{Lien web |titre=linear algebra - Why is uncomputability of the spectral decomposition not a problem? |url=https://mathoverflow.net/questions/369930/why-is-uncomputability-of-the-spectral-decomposition-not-a-problem |série=MathOverflow |consulté le=2021-08-09}}</ref>. Cette difficulté existe chaque fois que les multiplicités des valeurs propres d'une matrice ne sont pas connaissables. En revanche, le même problème ne se pose pas pour trouver des valeurs propres. Les valeurs propres d'une matrice sont toujours calculables.

On peut discuter de la manière dont ces difficultés se manifestent dans l’algorithme QR de base. Ceci est illustré dans la figure 2. Il faut rappeler que les ellipses représentent des matrices symétriques définies positives. Lorsque les deux valeurs propres de la matrice d'entrée se rapprochent l'une de l'autre, l'ellipse d'entrée se transforme en cercle, soit un multiple de la matrice identité (un quasi-cercle correspond à un quasi-multiple de la matrice identité dont les valeurs propres sont presque égales aux entrées diagonales de la matrice). Par conséquent, le problème de la recherche approximative des valeurs propres s'avère facile dans ce cas. Cependant, une itération de QR (ou LR) incline de moins en moins les demi-axes à mesure que l'ellipse d'entrée se rapproche d'un cercle. Les vecteurs propres ne peuvent être connus que lorsque les demi-axes sont parallèles à l'axe des x et à l'axe des y. Le nombre d'itérations nécessaires pour obtenir un quasi-parallélisme augmente sans limite à mesure que l'ellipse d'entrée devient plus circulaire.

Bien qu'il puisse être impossible de calculer la [[Décomposition d'une matrice en éléments propres|décomposition propre]] d'une matrice symétrique arbitraire, il est toujours possible de perturber la matrice d'une quantité arbitrairement petite et de calculer la décomposition propre de la matrice résultante. Dans le cas où la matrice est représentée comme une forme quasi-circulaire, la matrice peut être remplacée par une matrice dont la représentation est un cercle parfait. Dans ce cas, la matrice est un multiple de la matrice identité et sa décomposition en valeurs propres est immédiate. Il faut alors garder à l'esprit que la [[Valeur propre, vecteur propre et espace propre|base propre]] résultante peut être assez éloignée de la base propre d'origine.

=== Accélération : Déplacement et déflation ===
Le ralentissement lorsque l'ellipse devient plus circulaire a un effet inverse : il s'avère que lorsque l'ellipse devient plus étirée - et moins circulaire - alors la rotation de l'ellipse devient plus rapide. Un tel étirement peut être induit lorsque la matrice <math>M</math> que l'ellipse représente est remplacé par <math>M-\lambda I</math> où <math>\lambda</math> est approximativement la plus petite valeur propre de <math>M</math> . Dans ce cas, le rapport des deux demi-axes de l'ellipse se rapproche de l'infini . Dans les dimensions supérieures, un tel décalage rend la longueur du plus petit demi-axe d'un ellipsoïde petite par rapport aux autres demi-axes, ce qui accélère la convergence vers la plus petite valeur propre, mais n'accélère pas la convergence vers les autres valeurs propres. Cela devient inutile lorsque la plus petite valeur propre est entièrement déterminée, la matrice doit alors être ''réduite'', ce qui signifie simplement supprimer sa dernière ligne et sa dernière colonne.

Le problème du point fixe instable doit également être résolu. L’heuristique de décalage est souvent conçue pour traiter également ce problème : les décalages pratiques sont souvent discontinus et aléatoires. Le décalage de Wilkinson, qui convient bien aux matrices symétriques comme celles visualisées supra, est particulièrement discontinu.

== Algorithme QR implicite ==
Dans la pratique informatique moderne, l'algorithme QR est exécuté dans une version implicite qui facilite l'introduction de plusieurs décalages<ref name="golubvanloan"/>. La matrice est d'abord amenée à la forme de Hessenberg supérieure <math>A_0=QAQ^{\mathsf{T}}</math> comme dans la version explicite ; puis, à chaque étape, la première colonne de <math>A_k</math> est transformée via une transformation de Householder de petite taille vers la première colonne de <math>p(A_k)</math>{{Pas clair|date=October 2022}} (ou <math>p(A_k)e_1</math> ), où <math>p(A_k)</math>, de degré <math>r</math>, est le polynôme qui définit la stratégie de changement de vitesse (souvent <math>p(x)=(x-\lambda)(x-\bar\lambda)</math>, où <math>\lambda</math> et <math>\bar\lambda</math> sont les deux valeurs propres de la queue <math>2 \times 2</math> sous-matrice principale de <math>A_k</math>, le soi-disant ''double décalage implicite''). Puis des transformations successives de taille de Householder <math>r+1</math> sont effectuées afin de renvoyer la matrice de travail <math>A_k</math> à la forme supérieure de Hessenberg. Cette opération est connue sous le nom de « ''{{lang|en|bulge chasing}}'' », en raison de la forme particulière des entrées non nulles de la matrice le long des étapes de l'algorithme. Comme dans la première version, la réduction est effectuée dès qu'une des entrées sous-diagonales de <math>A_k</math> est suffisamment petit.

=== Proposition de changement de nom ===
Étant donné que dans la version implicite moderne de la procédure, aucune [[décomposition QR]] n'est explicitement effectuée, certains auteurs, par exemple Watkins<ref>{{Ouvrage|prénom1=David S.|nom1=Watkins|titre=The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods|lieu=Philadelphia, PA|éditeur=SIAM|année=2007|isbn=978-0-89871-641-2}}</ref>, ont suggéré de changer son nom en ''algorithme de Francis'' . [[Gene H. Golub|Golub]] et [[Charles F. Van Loan|Van Loan]] utilisent le terme ''Francis QR step'' .

== Interprétation et convergence ==
L'algorithme QR peut être considéré comme une variante plus sophistiquée de l' [[Méthode de la puissance itérée|algorithme de la puissance itérée]] , qui consiste à multiplier à plusieurs reprises ''A'' par un seul vecteur, en normalisant après chaque itération. Le vecteur converge vers un vecteur propre de la plus grande valeur propre. Au lieu de cela, l'algorithme QR fonctionne avec une base complète de vecteurs, en utilisant la décomposition QR pour renormaliser (et orthogonaliser). Pour une matrice symétrique ''A'', lors de la convergence, ''AQ'' = ''Q &#x39B;'', où ''&#x39B;'' est la [[matrice diagonale]] des valeurs propres vers lesquelles ''A a'' convergé, et où ''Q'' est une composition de toutes les transformations de similarité orthogonales nécessaires pour y parvenir. Ainsi, les colonnes de ''Q'' sont les vecteurs propres.

== Histoire ==
L'algorithme QR a été précédé par l'algorithme LR, qui utilise la [[décomposition LU]] au lieu de la décomposition QR. L'algorithme QR est plus stable, donc l'algorithme LR est rarement utilisé de nos jours. Cependant, cela représente une étape importante dans le développement de l’algorithme QR.

L'algorithme LR a été développé au début des années 1950 par [[Heinz Rutishauser]], qui travaillait à l'époque comme assistant de recherche d'[[Eduard Stiefel]] à l'[[École polytechnique fédérale de Zurich|école polytechnique de Zurich]]. Stiefel a suggéré à Rutishauser d'utiliser la séquence de moments {{nobr|''y''{{indexp|0|T}}''A''<sup>''k''</sup>''x''<sub>0</sub>, ''k'' {{=}} 0, 1, ...}} (où ''x''<sub>0</sub> et ''y''<sub>0</sub> sont des vecteurs arbitraires) pour trouver les valeurs propres de ''A''. Rutishauser a pris un algorithme d'[[Alexander Aitken]] pour cette tâche et l'a développé en ''algorithme quotient-différence'' ou ''algorithme qd''. Après avoir organisé le calcul sous une forme appropriée, il a découvert que l'algorithme qd est en fait l'itération {{nobr|''A<sub>k</sub>'' {{=}} ''L<sub>k</sub>U<sub>k</sub>''}} (décomposition LU), {{nobr|''A''<sub>''k'' +1</sub> {{=}} ''U<sub>k</sub>L<sub>k</sub>''}}, appliquée sur une matrice tridiagonale, d'où découle l'algorithme LR.

== Autres variantes ==
Une variante de l'algorithme QR, l'algorithme de Golub-Kahan-Reinsch, commence par réduire une matrice générale en une matrice bidiagonale<ref>{{lien web |lang=en |auteur1=Sergey Anatolyevich Bochkanov |titre=ALGLIB User Guide - General Matrix operations - Singular value decomposition |site=ALGLIB Project |date=2010-12-11 |url=http://www.alglib.net/matrixops/general/svd.php |consulté le=18/03/2025}}</ref>. Cette variante de l'algorithme QR pour le calcul de valeur singulières a été d'abord décrit par {{harvsp|Golub|Kahan|1965}}. La routine [http://www.netlib.org/lapack/double/dbdsqr.f DBDSQR]  de la bibliothèque [[LAPACK]] implémente cette méthode itérative, avec certaines modifications pour couvrir le cas om les valeurs singulières sont très petites {{harv|Demmel|Kahan|1990}}. Après une première étape utilisant des transformations de Householder et, si approprié, une [[décomposition QR]], on obtient la routine [http://www.netlib.org/lapack/double/dgesvd.f DGESVD] pour la [[décomposition en valeurs singulières]]. L'algorithme QR peut aussi être implémenté en dimensions infinies avec des résultats de convergence équivalents<ref>{{article |lang=en |auteur1=Percy Deift |auteur2=Luenchau C. Li |auteur3=Carlos Tomei|titre=Toda flows with infinitely many variables |journal=Journal of Functional Analysis |volume=64 | numéro=3| pages=358–402 |année=1985 |doi=10.1016/0022-1236(85)90065-5|accès doi=libre }}</ref>{{,}}<ref>{{article |lang=en |auteur1=Matthew J. Colbrook |auteur2=Anders C. Hansen |titre=On the infinite-dimensional QR algorithm |journal=Numerische Mathematik |volume=143 | numéro=1| pages=17–83 |année=2019 |doi=10.1007/s00211-019-01047-5|arxiv=2011.08172|accès doi=libre }}</ref>

== Références ==
{{Traduction/Référence|en|QR algorithm|1274608839}}
{{Références}}

== Sources ==

* {{Article|auteur1=Demmel|prénom1=James|auteur2=Kahan|prénom2=William|titre=Accurate singular values of bidiagonal matrices|périodique=SIAM Journal on Scientific and Statistical Computing|volume=11|numéro=5|pages=873–912|année=1990|doi=10.1137/0911052|citeseerx=10.1.1.48.3740}}
* {{Article|auteur1=Golub|prénom1=Gene H.|auteur2=Kahan|prénom2=William|titre=Calculating the singular values and pseudo-inverse of a matrix|périodique=Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis|volume=2|numéro=2|pages=205–224|année=1965|doi=10.1137/0702016|jstor=2949777|bibcode=1965SJNA....2..205G}}

== Liens externes ==

* Eigenvalue problem at PlanetMath.
* [http://www-users.math.umn.edu/~olver/aims_/qr.pdf Notes on orthogonal bases and the workings of the QR algorithm] by [[Peter J. Olver]]
* [https://web.archive.org/web/20081209042103/http://math.fullerton.edu/mathews/n2003/QRMethodMod.html Module for the QR Method]

{{Portail|algèbre}}

[[Catégorie:Analyse numérique matricielle]]
[[Catégorie:Pages avec des traductions non relues]]