Algoritmo QR

En álgebra lineal numérica, el algoritmo QR o la iteración QR es un algoritmo de valores propios: 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 G. F. Francis y Vera N. Kublanovskaya, trabajando de forma independiente. La idea básica es realizar una descomposición QR, escribir la matriz como producto de una matriz ortogonal y una matriz triangular superior, multiplicar los factores en orden inverso e iterar.

El algoritmo QR práctico

Formalmente, sea A una matriz real de la cual queremos calcular los valores propios, y sea < i>A₀:= 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⁻¹) y R _k es una matriz triangular superior. Luego formamos A_k+1 = R_k Q_k. Tenga en cuenta que

$${displaystyle ¿Qué? {T}A_{k}Q_{k}$$

Bajo ciertas condiciones, las matrices A_k convergen en una matriz triangular, la forma Schur de A. Los valores propios de una matriz triangular se enumeran en la diagonal y el problema de valores propios está resuelto. Al probar la convergencia no es práctico exigir ceros exactos, pero el teorema del círculo de Gershgorin proporciona un límite al error.

En esta forma cruda las iteraciones son relativamente costosas. Esto puede ser mitigado por primera vez trayendo la matriz A al formulario Hessenberg superior (que cuesta ${fnMicroc} {} {3}n}n^{3}+{mathcal {0}(n^{2}}} {cHFF}$ operaciones aritméticas utilizando una técnica basada en la reducción de los accionistas), con una secuencia finita de semejanza ortogonal transforma, algo como una descomposición QR de dos caras. (Para la descomposición de QR, los reflectores de marcadores se multiplican sólo a la izquierda, pero para el caso Hessenberg se multiplican tanto a la izquierda como a la derecha). Determinación de la descomposición QR de una matriz de Hessenberg superior ${textstyle 6n^{2}+{mathcal {0}(n)}$ operaciones aritméticas. Además, debido a que la forma Hessenberg ya es casi superior-triangular (tiene sólo una entrada no cero debajo de cada diagonal), el uso como punto de partida reduce el número de pasos requeridos 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 así tridiagonal, y así son todos los A_k. Este procedimiento cuesta ${fnMicroc} {4} {3}n^{3}+{mathcal {O}(n^{2}}} {c}}$ operaciones aritméticas utilizando una técnica basada en la reducción de los accionistas. Determinación de la descomposición QR de una matriz tridiagonal simétrica cuesta ${displaystyle {Mathcal}(n)}$ operaciones.

La tasa de convergencia depende de la separación entre 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.

Visualización

El algoritmo QR básico se puede visualizar en el caso en que A sea una matriz simétrica definida positiva. En ese caso, A se puede representar como una elipse en 2 dimensiones o un elipsoide en dimensiones superiores. La relación entre la entrada al algoritmo y una sola iteración se puede representar como en la Figura 1 (haga clic para ver una animación). Tenga en cuenta que el algoritmo LR se muestra junto al algoritmo QR.

Una sola iteración hace que la elipse se incline o "caiga"; hacia el eje x. En el caso de que el semieje mayor de la elipse sea paralelo al eje x, una iteración de QR no hace nada. Otra situación en la que el algoritmo "no hace nada" es cuando el semieje grande es paralelo al eje y en lugar del eje x. En ese caso, se puede pensar que la elipse se equilibra precariamente sin poder caer en ninguna dirección. En ambas situaciones, la matriz es diagonal. Una situación en la que una iteración del algoritmo "no hace nada" se llama punto fijo. La estrategia empleada por el algoritmo es la iteración hacia un punto fijo. Observe que un punto fijo es estable mientras que el otro es inestable. Si la elipse estuviera inclinada hacia afuera del punto fijo inestable en una cantidad muy pequeña, una iteración de QR haría que la elipse se inclinara hacia afuera del punto fijo en lugar de acercarse. Sin embargo, eventualmente el algoritmo convergería a un punto fijo diferente, pero llevaría mucho tiempo.

Encontrar valores propios versus encontrar vectores propios

Vale la pena señalar que encontrar incluso un solo vector propio de una matriz simétrica no es computable (en aritmética real exacta según las definiciones del análisis computable). Esta dificultad existe siempre que no se pueden conocer las multiplicidades de los valores propios de una matriz. Por otro lado, no existe el mismo problema para encontrar valores propios. Los valores propios de una matriz siempre son computables.

Ahora discutiremos cómo se manifiestan estas dificultades en el algoritmo QR básico. Esto se ilustra en la Figura 2. Recuerde que las elipses representan matrices simétricas definidas positivas. A medida que los dos valores propios de la matriz de entrada se acercan, la elipse de entrada se transforma en un círculo. Un círculo corresponde a un múltiplo de la matriz identidad. Un casi círculo corresponde a un casi múltiplo de la matriz identidad cuyos valores propios son casi iguales a las entradas diagonales de la matriz. Por lo tanto, se demuestra que el problema de encontrar aproximadamente los valores propios es fácil en ese caso. Pero observe lo que sucede con los semiejes de las elipses. Una iteración de QR (o LR) inclina cada vez menos los semiejes a medida que la elipse de entrada se acerca a ser un círculo. Los vectores propios solo se pueden conocer cuando los semiejes son paralelos a los ejes x e y. El número de iteraciones necesarias para lograr un casi paralelismo aumenta sin límite a medida que la elipse de entrada se vuelve más circular.

Si bien puede ser imposible calcular la descomposición propia de una matriz simétrica arbitraria, siempre es posible perturbar la matriz en una cantidad arbitrariamente pequeña y calcular la descomposición propia de la matriz resultante. En el caso de que la matriz se represente como un círculo cercano, la matriz se puede reemplazar por una cuya representación sea un círculo perfecto. En ese caso, la matriz es múltiplo de la matriz identidad y su descomposición propia es inmediata. Sin embargo, tenga en cuenta que la base propia resultante puede estar bastante lejos de la base propia original.

Acelerando: Cambios y deflación

La desaceleración cuando el elipse consigue más circular tiene un converso: Resulta que cuando la elipse se estira más - y menos circular - la rotación de la elipse se vuelve más rápida. Tal estiramiento se puede inducir cuando la matriz ${displaystyle M}$ que representa el elipse se reemplaza con ${displaystyle M-lambda Yo...$ Donde ${displaystyle lambda }$ es aproximadamente el valor más pequeño de ${displaystyle M}$. En este caso, la relación de los dos semi-axes de la elipse se acerca ${displaystyle infty }$. En dimensiones superiores, el cambio de esta manera hace que la longitud del semi-eje más pequeño de un pequeño ellipsoide relativo a los otros semi-axies, que acelera la convergencia al menor eigenvalue, pero no acelera la convergencia a los otros eigenvalues. Esto se vuelve inútil cuando el valor más pequeño es totalmente determinado, por lo que la matriz debe ser entonces deflado, que simplemente significa eliminar su última fila y columna.

También es necesario abordar el problema del punto fijo inestable. La heurística de los cambios suele estar diseñada para abordar también este problema: los cambios prácticos suelen ser discontinuos y aleatorios. El desplazamiento de Wilkinson, que es muy adecuado para matrices simétricas como las que estamos visualizando, es particularmente discontinuo.

El algoritmo QR implícito

En la práctica computacional moderna, el algoritmo QR se realiza en una versión implícita que facilita el uso de múltiples cambios. La matriz se trae primero a la forma superior Hessenberg ${displaystyle A_{0}=QAQ^{mathsf {T}$ como en la versión explícita; entonces, a cada paso, la primera columna de ${displaystyle A_{k}$ se transforma a través de una pequeña transformación de la similitud de los propietarios de la casa a la primera columna de ${displaystyle p(A_{k})}$ (o ${displaystyle p(A_{k})e_{1}$), donde ${displaystyle p(A_{k})}$, de grado ${displaystyle r}$, es el polinomio que define la estrategia de cambio (a menudo ${displaystyle p(x)=(x-lambda)(x-{bar {lambda }}}}$, donde ${displaystyle lambda }$ y ${fnMicrosoft {fnMicrosoft {fnMicrosoft {\fnMicrosoft {\fnMicrosoft {\\fnMicrosoft {\\\\\\\\\\\\\fnMicrosoft\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\ }$ son los dos eigenvalues de los senderos ${displaystyle 2times 2}$ submatrix principal ${displaystyle A_{k}$, el llamado doble turno implícito). Luego sucesivas transformaciones de tamaño del accionistas ${displaystyle r+1}$ se realizan para devolver la matriz de trabajo ${displaystyle A_{k}$ hasta la forma de Hessenberg superior. Esta operación se conoce como bulto persiguiendo, debido a la forma peculiar de las entradas no 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 subdiagonales ${displaystyle A_{k}$ es suficientemente pequeño.

Propuesta de cambio de nombre

Dado que en la versión implícita moderna del procedimiento no se realizan descomposiciones QR explícitamente, algunos autores, por ejemplo Watkins, sugirieron cambiar su nombre a algoritmo de Francis. Golub y Van Loan utilizan el término paso Francis QR.

Interpretación y convergencia

El algoritmo QR puede verse como una variación más sofisticada del algoritmo básico de "potencia" Algoritmo de valores propios. Recuerde que el algoritmo de potencia multiplica repetidamente A por un solo vector, normalizándose después de cada iteración. El vector converge a 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, al converger, AQ = QΛ, donde Λ es la matriz diagonal de valores propios a cual A convergió y donde Q es un compuesto de todas las transformaciones de similitud ortogonal necesarias para llegar allí. Por tanto, las columnas de Q son los vectores propios.

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 utiliza 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 usara la secuencia de momentos y₀^T A^k x₀, k = 0, 1,… (donde x ₀ y y₀ 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 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 se deriva el algoritmo LR.

Otras variantes

Una variante del algoritmo QR, el algoritmo Golub-Kahan-Reinsch comienza reduciendo una matriz general a una bidiagonal. Esta variante del algoritmo QR para el cálculo de valores singulares fue descrita por primera vez por Golub & Kahan (1965). La subrutina LAPACK DBDSQR implementa este método iterativo, con algunas modificaciones para cubrir el caso en el que los valores singulares son muy pequeños (Demmel y Kahan 1990). Junto con un primer paso que utiliza reflexiones de Householder y, si corresponde, 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 infinitas dimensiones con los correspondientes resultados de convergencia.