En álgebra lineal numérica , el algoritmo QR o iteración QR es un algoritmo de valor propio : es decir, un procedimiento para calcular los valores propios y los vectores propios de una matriz . El algoritmo QR fue desarrollado a finales de la década de 1950 por John GF Francis y Vera N. Kublanovskaya , trabajando de forma independiente. [1] [2] [3] La idea básica es realizar una descomposición QR , escribiendo la matriz como un producto de una matriz ortogonal y una matriz triangular superior , multiplicar los factores en orden inverso e iterar.
El práctico algoritmo QR
Formalmente, dejó un ser una matriz real de la cual queremos calcular los valores propios, y deja un 0 : = A . En el k -ésimo paso (comenzando con k = 0), calculamos la descomposición QR A k = Q k R k donde Q k es una matriz ortogonal (es decir, Q T = Q −1 ) y R k es un triángulo superior matriz. Entonces formamos A k +1 = R k Q k . Tenga en cuenta que
por lo que todos los A k son similares y, por lo tanto, tienen los mismos valores propios. El algoritmo es numéricamente estable porque procede de transformaciones de semejanza ortogonal .
Bajo ciertas condiciones, [4] la matrices A k convergen en un triangular de la matriz, la forma Schur de A . Los valores propios de una matriz triangular se enumeran en la diagonal y se resuelve el problema de valores propios. Al probar la convergencia, no es práctico requerir ceros exactos, [ cita requerida ] pero el teorema del círculo de Gershgorin proporciona un límite al error.
En esta forma cruda, las iteraciones son relativamente caras. Esto se puede mitigar llevando primero la matriz A a la forma superior de Hessenberg (que cuestaoperaciones aritméticas que utilizan una técnica basada en la reducción del amo de casa ), con una secuencia finita de transformaciones de semejanza ortogonal, algo así como una descomposición QR de dos lados. [5] [6] (Para la descomposición QR, los reflectores Householder se multiplican solo a la izquierda, pero para el caso de Hessenberg se multiplican tanto a la izquierda como a la derecha). Determinar la descomposición QR de una matriz superior de Hessenberg cuestaoperaciones aritmeticas. Además, debido a que la forma de Hessenberg ya es casi triangular superior (solo tiene una entrada distinta de cero debajo de cada diagonal), usarla como punto de partida reduce el número de pasos necesarios para la convergencia del algoritmo QR.
Si la matriz original es simétrica , entonces la matriz de Hessenberg superior también es simétrica y, por lo tanto , tridiagonal , al igual que todas las A k . Este procedimiento cuestaoperaciones aritméticas utilizando una técnica basada en la reducción de jefes de hogar. [5] [6] Determinar la descomposición QR de una matriz tridiagonal simétrica cuestaoperaciones. [7]
La tasa de convergencia depende de la separación entre los valores propios, por lo que un algoritmo práctico utilizará cambios, ya sean explícitos o implícitos, para aumentar la separación y acelerar la convergencia. Un algoritmo QR simétrico típico aísla cada valor propio (luego reduce el tamaño de la matriz) con solo una o dos iteraciones, lo que lo hace eficiente y robusto. [ aclaración necesaria ]
El algoritmo QR implícito
En la práctica computacional moderna, el algoritmo QR se realiza en una versión implícita que facilita la introducción del uso de múltiples turnos. [4] La matriz se lleva primero a la forma superior de Hessenberg.como en la versión explícita; luego, en cada paso, la primera columna de se transforma a través de una transformación de similitud de jefe de hogar de tamaño pequeño a la primera columna de (o ), dónde , de grado , es el polinomio que define la estrategia de cambio (a menudo , dónde y son los dos valores propios del final submatriz principal de , el llamado doble turno implícito ). Luego, sucesivas transformaciones de tamaño de los jefes de hogar se realizan para devolver la matriz de trabajo a la forma superior de Hessenberg. Esta operación se conoce como persecución de protuberancias , debido a la forma peculiar de las entradas distintas de cero de la matriz a lo largo de los pasos del algoritmo. Como en la primera versión, la deflación se realiza tan pronto como una de las entradas sub-diagonales de es suficientemente pequeño.
Propuesta de cambio de nombre
Dado que en la versión implícita moderna del procedimiento no se realizan explícitamente descomposiciones QR , algunos autores, por ejemplo Watkins, [8] sugirieron cambiar su nombre a algoritmo Francis . Golub y Van Loan utilizan el término Francis QR step .
Interpretación y convergencia
El algoritmo QR puede verse como una variación más sofisticada del algoritmo básico de valor propio de "potencia" . Recuerde que el algoritmo de potencia multiplica A repetidamente por un solo vector, normalizándose después de cada iteración. El vector converge en un vector propio del valor propio más grande. En cambio, el algoritmo QR funciona con una base completa de vectores, utilizando la descomposición QR para renormalizar (y ortogonalizar). Para una matriz simétrica A , tras la convergencia, AQ = QΛ , donde Λ es la matriz diagonal de valores propios a los que A convergió, y donde Q es una combinación de todas las transformadas de semejanza ortogonal necesarias para llegar allí. Por tanto, las columnas de Q son los autovectores.
Historia
El algoritmo QR fue precedido por el algoritmo LR , que utiliza la descomposición LU en lugar de la descomposición QR. El algoritmo QR es más estable, por lo que el algoritmo LR rara vez se usa hoy en día. Sin embargo, representa un paso importante en el desarrollo del algoritmo QR.
El algoritmo LR fue desarrollado a principios de la década de 1950 por Heinz Rutishauser , quien trabajaba en ese momento como asistente de investigación de Eduard Stiefel en ETH Zurich . Stiefel sugirió que Rutishauser utilizar la secuencia de momentos y 0 T A k x 0 , k = 0, 1, ... (donde x 0 y y 0 son vectores arbitrarios) para encontrar los valores propios de A . Rutishauser tomó un algoritmo de Alexander Aitken para esta tarea y lo desarrolló en el algoritmo de cociente-diferencia o algoritmo qd . Después de organizar el cálculo en una forma adecuada, descubrió que el algoritmo qd es de hecho la iteración A k = L k U k (descomposición LU), A k +1 = U k L k , aplicada en una matriz tridiagonal, a partir de la cual sigue el algoritmo LR. [9]
Otras variantes
Una variante del algoritmo QR , el algoritmo Golub-Kahan-Reinsch comienza con la reducción de una matriz general en una bidiagonal. [10] Esta variante del algoritmo QR para el cálculo de valores singulares fue descrita por primera vez por Golub y Kahan (1965) . La subrutina LAPACK DBDSQR implementa este método iterativo, con algunas modificaciones para cubrir el caso donde los valores singulares son muy pequeños ( Demmel & Kahan 1990 ) . Junto con un primer paso utilizando las reflexiones de Householder y, en su caso, la descomposición QR , esto forma la rutina DGESVD para el cálculo de la descomposición del valor singular . El algoritmo QR también se puede implementar en dimensiones infinitas con los correspondientes resultados de convergencia. [11] [12]
Referencias
- ^ JGF Francis, "The QR Transformation, I", The Computer Journal , 4 (3), páginas 265-271 (1961, recibido en octubre de 1959). doi: 10.1093 / comjnl / 4.3.265
- ^ Francis, JGF (1962). "La Transformación QR, II" . The Computer Journal . 4 (4): 332–345. doi : 10.1093 / comjnl / 4.4.332 .
- ^ Vera N. Kublanovskaya, "Sobre algunos algoritmos para la solución del problema de valor propio completo", URSS Matemáticas Computacionales y Física Matemática , vol. 1, no. 3, páginas 637–657 (1963, recibido en febrero de 1961). También publicado en: Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki , vol.1, no. 4, páginas 555–570 (1961). doi: 10.1016 / 0041-5553 (63) 90168-X
- ^ a b Golub, GH; Van Loan, CF (1996). Cálculos matriciales (3ª ed.). Baltimore: Prensa de la Universidad Johns Hopkins. ISBN 0-8018-5414-8.
- ^ a b Demmel, James W. (1997). Álgebra lineal numérica aplicada . SIAM.
- ^ a b Trefethen, Lloyd N .; Bau, David (1997). Álgebra lineal numérica . SIAM.
- ^ Ortega, James M .; Kaiser, Henry F. (1963). "Los métodos LL T y QR para matrices tridiagonales simétricas" . The Computer Journal . 6 (1): 99–101. doi : 10.1093 / comjnl / 6.1.99 .
- ^ Watkins, David S. (2007). El problema del valor propio de la matriz: métodos del subespacio GR y Krylov . Filadelfia, PA: SIAM. ISBN 978-0-89871-641-2.
- ^ Parlett, Beresford N .; Gutknecht, Martin H. (2011), "De qd a LR, o, ¿cómo se descubrieron los algoritmos qd y LR?" (PDF) , IMA Journal of Numerical Analysis , 31 (3): 741–754, doi : 10.1093 / imanum / drq003 , hdl : 20.500.11850 / 159536 , ISSN 0272-4979
- ^ Bochkanov Sergey Anatolyevich. Guía del usuario de ALGLIB - Operaciones generales de la matriz - Descomposición de valores singulares. Proyecto ALGLIB. 2010-12-11. URL: http://www.alglib.net/matrixops/general/svd.php . [ enlace muerto permanente ] Consultado: 2010-12-11. (Archivado por WebCite en https://www.webcitation.org/5utO4iSnR?url=http://www.alglib.net/matrixops/general/svd.php
- ^ Deift, Percy; Li, Luenchau C .; Tomei, Carlos (1985). "Toda fluye con infinitas variables" . Revista de análisis funcional . 64 (3): 358–402. doi : 10.1016 / 0022-1236 (85) 90065-5 .
- ^ Colbrook, Matthew J .; Hansen, Anders C. (2019). "Sobre el algoritmo QR de dimensión infinita" . Numerische Mathematik . 143 (1): 17–83. doi : 10.1007 / s00211-019-01047-5 .
enlaces externos
- "Problema de valores propios" . PlanetMath .
- Notas sobre bases ortogonales y el funcionamiento del algoritmo QR por Peter J. Olver
- Módulo para el método QR
- Biblioteca C ++