Algoritmo de autovalores de divide y vencerás

Los algoritmos de autovalores de divide y vencerás son una clase de algoritmos para matrices simétricas hermíticas o reales que recientemente (alrededor de la década de 1990) se han vuelto competitivos en términos de estabilidad y eficiencia con algoritmos más tradicionales como el algoritmo QR . El concepto básico detrás de estos algoritmos es el enfoque de divide y vencerás de la informática . Un problema de autovalores se divide en dos problemas de aproximadamente la mitad del tamaño, cada uno de ellos se resuelve recursivamente y los autovalores del problema original se calculan a partir de los resultados de estos problemas más pequeños.

Este artículo aborda la idea básica del algoritmo tal como lo propuso originalmente Cuppen en 1981, la cual no es numéricamente estable sin mejoras adicionales.

Como ocurre con la mayoría de los algoritmos de valores propios para matrices hermíticas, el método de divide y vencerás comienza con una reducción a la forma tridiagonal . Para un${\displaystyle m\times m}$matriz, el método estándar para esto, a través de las reflexiones de Householder , toma${\displaystyle {\frac {4}{3}}m^{3}}$operaciones de punto flotante, o${\displaystyle {\frac {8}{3}}m^{3}}$Si también se necesitan los autovectores . Existen otros algoritmos, como la iteración de Arnoldi , que pueden funcionar mejor para ciertas clases de matrices; no los analizaremos aquí con más detalle.

En ciertos casos, es posible descomponer un problema de valores propios en problemas más pequeños. Consideremos una matriz diagonal por bloques.

${\displaystyle T={\begin{bmatrix}T_{1}&0\\0&T_{2}\end{bmatrix}}.}$

Los valores propios y los vectores propios de${\displaystyle T}$son simplemente los de${\displaystyle T_{1}}$y${\displaystyle T_{2}}$Y casi siempre será más rápido resolver estos dos problemas más pequeños que resolver el problema original de una sola vez. Esta técnica puede utilizarse para mejorar la eficiencia de muchos algoritmos de autovalores, pero tiene especial relevancia para la estrategia de divide y vencerás.

Para el resto de este artículo, asumiremos que la entrada al algoritmo de divide y vencerás es una${\displaystyle m\times m}$matriz tridiagonal simétrica real${\displaystyle T}$El algoritmo puede modificarse para matrices hermíticas.

La parte de división del algoritmo de divide y vencerás surge de la constatación de que una matriz tridiagonal es "casi" diagonal por bloques.

El tamaño de la submatriz${\displaystyle T_{1}}$llamaremos${\displaystyle n\times n}$, y luego${\displaystyle T_{2}}$es${\displaystyle (mn)\times (mn)}$. ${\displaystyle T}$es casi diagonal de bloques independientemente de cómo${\displaystyle n}$se elige. Para mayor eficiencia, normalmente elegimos${\displaystyle n\approx m/2}$.

Escribimos${\displaystyle T}$como una matriz diagonal por bloques, más una corrección de rango 1 :

La única diferencia entre${\displaystyle T_{1}}$y${\displaystyle {\hat {T}}_{1}}$es que la entrada inferior derecha${\displaystyle t_{nn}}$en${\displaystyle {\hat {T}}_{1}}$ha sido reemplazado por${\displaystyle t_{nn}-\beta }$y de manera similar, en${\displaystyle {\hat {T}}_{2}}$la entrada superior izquierda${\displaystyle t_{n+1,n+1}}$ha sido reemplazado por${\displaystyle t_{n+1,n+1}-\beta }$.

El resto del paso de división consiste en resolver para los valores propios (y si se desea, los vectores propios) de${\displaystyle {\hat {T}}_{1}}$y${\displaystyle {\hat {T}}_{2}}$, es decir, encontrar las diagonalizaciones${\displaystyle {\hat {T}}_{1}=Q_{1}D_{1}Q_{1}^{T}}$y${\displaystyle {\hat {T}}_{2}=Q_{2}D_{2}Q_{2}^{T}}$Esto se puede lograr con llamadas recursivas al algoritmo de divide y vencerás, aunque las implementaciones prácticas a menudo cambian al algoritmo QR desplazado implícitamente para submatrices suficientemente pequeñas. ^{[ 1 ]}

La parte de conquista del algoritmo es la menos intuitiva. Dadas las diagonalizaciones de las submatrices, calculadas anteriormente, ¿cómo hallamos la diagonalización de la matriz original?

Primero, defina${\displaystyle z^{T}=(q_{1}^{T},q_{2}^{T})}$, dónde${\displaystyle q_{1}^{T}}$es la última fila de${\displaystyle Q_{1}}$y${\displaystyle q_{2}^{T}}$es la primera fila de${\displaystyle Q_{2}}$Ahora es elemental demostrar que

${\displaystyle T={\begin{bmatrix}Q_{1}&\\&Q_{2}\end{bmatrix}}\left({\begin{bmatrix}D_{1}&\\&D_{2}\end{bmatrix}}+\beta zz^{T}\right){\begin{bmatrix}Q_{1}^{T}&\\&Q_{2}^{T}\end{bmatrix}}}$

La tarea restante se ha reducido a encontrar los valores propios de una matriz diagonal más una corrección de rango uno. Antes de mostrar cómo hacerlo, simplifiquemos la notación. Buscamos los valores propios de la matriz${\displaystyle D+ww^{T}}$, dónde${\displaystyle D}$es diagonal con entradas distintas y${\displaystyle w}$es cualquier vector con entradas distintas de cero. En este caso${\displaystyle w={\sqrt {|\beta |}}\cdot z}$.

El caso de una entrada cero es simple, ya que si w _i es cero, (${\displaystyle e_{i}}$,d _i ) es un par propio (${\displaystyle e_{i}}$está en la base estándar) de${\displaystyle D+ww^{T}}$desde ${\displaystyle (D+ww^{T})e_{i}=De_{i}=d_{i}e_{i}}$.

Si${\displaystyle \lambda }$es un valor propio, tenemos:

${\displaystyle (D+ww^{T})q=\lambda q}$

dónde${\displaystyle q}$es el vector propio correspondiente. Ahora

${\displaystyle (D-\lambda I)q+w(w^{T}q)=0}$

${\displaystyle q+(D-\lambda I)^{-1}w(w^{T}q)=0}$

${\displaystyle w^{T}q+w^{T}(D-\lambda I)^{-1}w(w^{T}q)=0}$

Ten en cuenta que${\displaystyle w^{T}q}$es un escalar distinto de cero.${\displaystyle w}$ni${\displaystyle q}$son cero. Si${\displaystyle w^{T}q}$si fueran cero,${\displaystyle q}$sería un vector propio de${\displaystyle D}$por${\displaystyle (D+ww^{T})q=\lambda q}$Si ese fuera el caso,${\displaystyle q}$contendría solo una posición distinta de cero ya que${\displaystyle D}$es diagonal distinta y por lo tanto el producto interno${\displaystyle w^{T}q}$Después de todo, no puede ser cero. Por lo tanto, tenemos:

${\displaystyle 1+w^{T}(D-\lambda I)^{-1}w=0}$

o escrita como una ecuación escalar,

${\displaystyle 1+\sum _{j=1}^{m}{\frac {w_{j}^{2}}{d_{j}-\lambda }}=0.}$

Esta ecuación se conoce como la ecuación secular . Por lo tanto, el problema se ha reducido a hallar las raíces de la función racional definida por el lado izquierdo de esta ecuación.

La resolución de la ecuación secular no lineal se puede realizar utilizando una técnica iterativa, como el método de Newton-Raphson . Sin embargo, cada raíz se puede encontrar en O (1) iteraciones, cada una de las cuales requiere${\displaystyle \Theta (m)}$fracasos (para un${\displaystyle m}$-función racional de grado), lo que hace que el costo de la parte iterativa de este algoritmo${\displaystyle \Theta (m^{2})}$. El método multipolar rápido también se ha empleado para resolver la ecuación secular en${\displaystyle \Theta (m\log(m))}$operaciones. ^{[ 2 ] [ 1 ]}

W utilizará el teorema maestro para recurrencias de divide y vencerás para analizar el tiempo de ejecución. Recuerda que arriba dijimos que elegimos${\displaystyle n\approx m/2}$Podemos escribir la relación de recurrencia :

${\displaystyle T(m)=2\times T\left({\frac {m}{2}}\right)+\Theta (m^{2})}$

En la notación del teorema maestro,${\displaystyle a=b=2}$y por lo tanto${\displaystyle \log _{b}a=1}$. Claramente,${\displaystyle \Theta (m^{2})=\Omega (m^{1})}$, así que tenemos

${\displaystyle T(m)=\Theta (m^{2})}$

Anteriormente, señalamos que reducir una matriz hermitiana a forma tridiagonal requiere${\displaystyle {\frac {4}{3}}m^{3}}$fallos. Esto empequeñece el tiempo de ejecución de la parte de divide y vencerás, y en este punto no está claro qué ventaja ofrece el algoritmo de divide y vencerás sobre el algoritmo QR (que también toma${\displaystyle \Theta (m^{2})}$flops para matrices tridiagonales).

La ventaja de dividir y conquistar se presenta cuando también se necesitan los autovectores. Si este es el caso, la reducción a la forma tridiagonal toma${\displaystyle {\frac {8}{3}}m^{3}}$, pero la segunda parte del algoritmo toma${\displaystyle \Theta (m^{3})}$También. Para el algoritmo QR con una precisión objetivo razonable, esto es${\displaystyle \approx 6m^{3}}$, mientras que para la estrategia de divide y vencerás es${\displaystyle \approx {\frac {4}{3}}m^{3}}$. La razón de esta mejora es que en divide y vencerás, el${\displaystyle \Theta (m^{3})}$parte del algoritmo (multiplicando${\displaystyle Q}$matrices) es independiente de la iteración, mientras que en QR, esto debe ocurrir en cada paso iterativo. Agregar la${\displaystyle {\frac {8}{3}}m^{3}}$fracasos para la reducción, la mejora total es de${\displaystyle \approx 9m^{3}}$a${\displaystyle \approx 4m^{3}}$fracasos.

El uso práctico del algoritmo de divide y vencerás ha demostrado que, en la mayoría de los problemas de valores propios realistas, el algoritmo en realidad funciona mejor que esto. La razón es que muy a menudo las matrices${\displaystyle Q}$y los vectores${\displaystyle z}$Suelen ser numéricamente dispersos , lo que significa que tienen muchas entradas con valores menores que la precisión de punto flotante , lo que permite la deflación numérica , es decir, dividir el problema en subproblemas desacoplados.

El algoritmo que se presenta aquí es la versión más sencilla. En muchas implementaciones prácticas, se utilizan correcciones de rango 1 más complejas para garantizar la estabilidad; algunas variantes incluso utilizan correcciones de rango 2.

Existen técnicas especializadas para encontrar raíces de funciones racionales que pueden superar al método de Newton-Raphson en rendimiento y estabilidad. Estas técnicas pueden utilizarse para mejorar la parte iterativa del algoritmo de divide y vencerás.

El algoritmo de divide y vencerás se puede paralelizar fácilmente , y los paquetes de cálculo de álgebra lineal , como LAPACK, contienen implementaciones paralelas de alta calidad.

• Demmel, James W. (1997), Álgebra lineal numérica aplicada , Filadelfia, PA: Society for Industrial and Applied Mathematics , ISBN 0-89871-389-7, MR 1463942 .
• Cuppen, JJM (1981). "Un método de divide y vencerás para el problema propio tridiagonal simétrico". Matemática numérica . 36 (2): 177– 195. doi : 10.1007/BF01396757 . S2CID 120504744 .