Algoritmo QR

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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. Kublanovskaya (URSS), de forma independiente.[1]

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[editar]

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

 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 Ak 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[2] las matrices Ak 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[editar]

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 =  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[editar]

Reducción del coste computacional[editar]

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 \begin{matrix}\frac{10}{3}\end{matrix} n^3 + O(n^2) operaciones aritméticas usando la transformación de Householder[3] [4] Determinar la descomposición QR de una matriz de Hessenberg lleva 6 n^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 Ak. Entonces el proceso ocupa \begin{matrix}\frac{4}{3}\end{matrix} n^3 + O(n^2) operaciones, usando una técnica basada en la reducción de Householder.[3] [4] Determinar la descomposición QR de una matriz simétrica tridiagonal cuesta O(n) operaciones.[5]

Otras variantes[editar]

Una variante del algoritmo QR es el algoritmo Golub-Kahan-Reinsch, que empieza reduciendo una matriz a bidiagonal.[6] 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[editar]

El algortimo 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 algortimo 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 y0T Ak x0, k = 0, 1, … (donde x0 e y0 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 algortimo era en realidad la iteración Ak = LkUk (Descomposición LU), Ak+1 = UkLk, aplicado sobre una matriz tridiagonal de la que deriva el algoritmo LR.[7]

Referencias[editar]

  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. Golub, G. H. and Van Loan, C. F.: Matrix Computations, 3rd ed., Johns Hopkins University Press, Baltimore, 1996, ISBN 0-8018-5414-8.
  3. a b James W. Demmel, Applied Numerical Linear Algebra (SIAM, 1997).
  4. a b Lloyd N. Trefethen and David Bau, Numerical Linear Algebra (SIAM, 1997).
  5. James M. Ortega and Henry F. Kaiser, "The LLT and QR methods for symmetric tridiagonal matrices," The Computer Journal 6 (1), 99–101 (1963).
  6. 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 http://www.webcitation.org/5utO4iSnR)
  7. 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, doi:10.1093/imanum/drq003, ISSN 0272-4979 

Enlaces externos[editar]