Algoritmo QR

El algoritmo QR es un algoritmo usado en álgebra lineal para el cálculo de valores y vectores propios de una matriz.

Se basa en la descomposición QR, desarrollada en la década de 1950 por John G.F. Francis (Reino Unido) y Vera N. Kublánovskaya (URSS), de forma independiente.^[1]​ Esto es, usa la oportunidad de representar cualquier matriz regular H en forma de producto de ${\displaystyle H=QR}$ de una matriz ortogonal Q por una matriz triangular superior R.^[2]​ La idea básica es usar dicha descomposición para reescribir la matriz como el producto de una matriz ortogonal y una matriz triangular superior. Si se multiplica a la inversa, la matriz resultante sigue teniendo los mismos valores propios e iterando se puede llegar a una matriz que los contenga en la diagonal.

Descripción del algoritmo

Formalmente, sea A una matriz real de la que queremos calcular los valores propios, se asigna A₀:=A. En adelante se calculan las siguientes iteraciones de forma:

• A_k=Q_kR_k dondeQ_k es una matriz ortogonal y R_k es una matriz triangular superior.
• A_k+1 = R_kQ_k. Se ha de notar que

${\displaystyle A_{k+1}=R_{k}Q_{k}=Q_{k}^{T}Q_{k}R_{k}Q_{k}=Q_{k}^{T}A_{k}Q_{k}=Q_{k}^{-1}A_{k}Q_{k},}$ 

luego todas las A_k son matrices semejantes y por tanto tienen los mismos valores propios. El algoritmo es numéricamente estable porque opera por transformaciones ortogonales.

Bajo ciertas condiciones^[3]​ las matrices A_k convergen a una matriz triangular que es la triangulación de Schur de A. Dado que los valores propios de una matriz triangular están listados en su diagonal, se pueden obtener directamente entonces. Comprobar su convergencia es impráctico, pero se puede acotar el error por el Teorema de Gerschgorin.

Interpretación

El algoritmo QR se puede considerar una versión más sofisticada del método de las potencias. Ambos métodos multiplican repetidamente un vector por la matriz de la que se quieren conocer los valores propios, normalizando después de cada iteración. Así este converge a los valores deseados.

Sin embargo, mientras que el método de las potencias solo proporciona el mayor de los valores propios, el método QR usa la descomposición homónima para normalizar y ortogonalizar tras cada iteración. Así para el valor final cuando converge AQ=QΛ se obtiene la matriz diagonal Λ que contiene todos los valores propios y por tanto Q queda con los vectores propios en las columnas.

Variantes del algoritmo

Reducción del coste computacional

En la forma más simple, este algoritmo es muy costoso computacionalmente. Se puede mitigar esto convirtiendo A en una matriz de Hessenberg, lo que ocupa ${\displaystyle {\begin{matrix}{\frac {10}{3}}\end{matrix}}n^{3}+O(n^{2})}$  operaciones aritméticas usando la transformación de Householder^[4]​^[5]​ Determinar la descomposición QR de una matriz de Hessenberg lleva ${\displaystyle 6n^{2}+O(n)}$  operaciones. Sin embargo, la matriz de Hessenberg es casi triangular, por lo que su uso como punto de partida reduce el número de iteraciones para que el algoritmo converja.

Si la matriz original es una matriz simétrica, la matriz de Hessenberg es también simétrica y por tanto tridiagonal. Como ella, lo serán todas las A_k. Entonces el proceso ocupa ${\displaystyle {\begin{matrix}{\frac {4}{3}}\end{matrix}}n^{3}+O(n^{2})}$  operaciones, usando una técnica basada en la reducción de Householder.^[4]​^[5]​ Determinar la descomposición QR de una matriz simétrica tridiagonal cuesta ${\displaystyle O(n)}$  operaciones.^[6]​

Otras variantes

Una variante del algoritmo QR es el algoritmo Golub-Kahan-Reinsch, que empieza reduciendo una matriz a bidiagonal.^[7]​ Dicha variante fue descrita por primera vez por Golub y Kahan (1965).

La subrutina LAPACK de DBDSQR implementa este método iterativo con algunas modificaciones para cubrir el caso de que los valores sean demasiado pequeños (Demmel y Kahan, 1990). Junto a un primer paso usando reflexiones de Householder y, si procede, la descomposición QR, esto forma la rutina DGESVD para el cálculo de la descomposición en valores singulares.

Historia

El algoritmo QR fue precedido por el algoritmo LR, que se apoya en la descomposición LU. El algoritmo QR es en comparación más estable así que le desplazó y el LR es poco usado hoy en día. Sin embargo, fue el primer paso hacia las técnicas actuales QR.

El algoritmo LR fue desarrollado en los comienzos de la década de 1950 por Heinz Rutishauer, que trabajaba como asistente de Eduard Stiefel en la Escuela Politécnica Federal de Zúrich. Stiefel sugirió que Rutishauer usara la secuencia de momentos y₀^T A^k x₀, k = 0, 1, … (donde x₀ e y₀ son vectores arbitrarios) para encontrar los valores propios de A. Rutishauer usó un algoritmo de Alexander Aitken para esta tarea y lo desarrolló en un algoritmo de cociente-diferencia (quotient–difference algorithm), de donde deriva el término algoritmo qd.

Tras formularlo de una forma apropiada computacionalmente, descubrió que el algoritmo era en realidad la iteración A_k = L_kU_k (Descomposición LU), A_k+1 = U_kL_k, aplicado sobre una matriz tridiagonal de la que deriva el algoritmo LR.^[8]​

Referencias

1. J.G.F. Francis, "The QR Transformation, I", The Computer Journal, vol. 4, no. 3, pages 265-271 (1961, received Oct 1959) online at oxfordjournals.org;
   J.G.F. Francis, "The QR Transformation, II" The Computer Journal, vol. 4, no. 4, pages 332-345 (1962) online at oxfordjournals.org.
   Vera N. Kublanovskaya, "On some algorithms for the solution of the complete eigenvalue problem," USSR Computational Mathematics and Mathematical Physics, vol. 1, no. 3, pages 637–657 (1963, received Feb 1961). Also published in: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, vol.1, no. 4, pages 555–570 (1961).
2. V. Boss Lecciones de matemática tomo 3 Álgebra lineal Editorial URSS Moscú (2011)
3. Golub, G. H. and Van Loan, C. F.: Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996, ISBN 0-8018-5414-8.
4. James W. Demmel, Applied Numerical Linear Algebra (SIAM, 1997).
5. Lloyd N. Trefethen and David Bau, Numerical Linear Algebra (SIAM, 1997).
6. James M. Ortega and Henry F. Kaiser, "The LL^T and QR methods for symmetric tridiagonal matrices," The Computer Journal 6 (1), 99–101 (1963).
7. Bochkanov Sergey Anatolyevich. ALGLIB User Guide - General Matrix operations - Singular value decomposition . ALGLIB Project. 2010-12-11. URL:http://www.alglib.net/matrixops/general/svd.php. Accessed: 2010-12-11. (Archived by WebCite at)
8. Parlett, Beresford N.; Gutknecht, Martin H. (2011), «From qd to LR, or, how were the qd and LR algorithms discovered?», IMA Journal of Numerical Analysis 31: 741-754, ISSN 0272-4979, doi:10.1093/imanum/drq003 .

Enlaces externos

• Eigenvalue problem en PlanetMath.
• Prof. Peter Olver's notes on orthogonal bases and the workings of the QR algorithm

•   Datos: Q453132