Los algoritmos de valor propio de dividir y conquistar son una clase de algoritmos de valor propio para matrices simétricas reales o hermitianas que recientemente (alrededor de la década de 1990) se han vuelto competitivas 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 valor propio se divide en dos problemas de aproximadamente la mitad del tamaño, cada uno de ellos se resuelve de forma recursiva, y los valores propios del problema original se calculan a partir de los resultados de estos problemas más pequeños.
Aquí presentamos la versión más simple de un algoritmo de divide y vencerás, similar al propuesto originalmente por Cuppen en 1981. Se omitirán muchos detalles que quedan fuera del alcance de este artículo; sin embargo, sin considerar estos detalles, el algoritmo no es completamente estable.
Fondo
Al igual que con la mayoría de los algoritmos de valores propios para matrices hermitianas, divide y vencerás comienza con una reducción a la forma tridiagonal . Por unmatriz, el método estándar para esto, a través de las reflexiones de los jefes de hogar , toma fracasos , osi también se necesitan vectores propios . Hay otros algoritmos, como la iteración de Arnoldi , que pueden funcionar mejor para ciertas clases de matrices; no consideraremos esto más aquí.
En ciertos casos, es posible desinflar un problema de valor propio en problemas más pequeños. Considere una matriz diagonal de bloques
Los autovalores y autovectores de son simplemente los de y , y casi siempre será más rápido resolver estos dos problemas más pequeños que resolver el problema original de una vez. Esta técnica se puede utilizar para mejorar la eficiencia de muchos algoritmos de valores propios, pero tiene un significado especial para dividir y conquistar.
Para el resto de este artículo, asumiremos que la entrada al algoritmo divide y vencerás es una matriz tridiagonal simétrica real . Aunque el algoritmo se puede modificar para matrices hermitianas, no damos los detalles aquí.
Dividir
La brecha parte del algoritmo divide y vencerás proviene de la realización de que una matriz tridiagonal es "casi" diagonal por bloques.
El tamaño de la submatriz llamaremos , y entonces es . Tenga en cuenta que el comentario sobre ser casi diagonal en bloque es cierto independientemente de cómo se elige (es decir, hay muchas formas de descomponer la matriz). Sin embargo, tiene sentido, desde el punto de vista de la eficiencia, elegir.
Nosotros escribimos como una matriz diagonal de bloque, más una corrección de rango 1 :
La única diferencia entre y es que la entrada inferior derecha en ha sido reemplazado con y de manera similar, en la entrada superior izquierda ha sido reemplazado con .
El resto del paso de división es para resolver los valores propios (y si se desea los vectores propios) de y , es decir, encontrar las diagonalizaciones y . Esto se puede lograr con llamadas recursivas al algoritmo divide y vencerás, aunque las implementaciones prácticas a menudo cambian al algoritmo QR para submatrices lo suficientemente pequeñas.
Conquistar
La parte de conquista del algoritmo es la parte poco intuitiva. Dadas las diagonalizaciones de las submatrices, calculadas anteriormente, ¿cómo encontramos la diagonalización de la matriz original?
Primero, defina , dónde es la última fila de y es la primera fila de . Ahora es elemental mostrar que
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 hacer esto, simplifiquemos la notación. Buscamos los autovalores de la matriz., dónde es diagonal con distintas entradas y es cualquier vector con entradas distintas de cero.
Si w i es cero, (, d i ) es un par propio de desde .
Si es un valor propio, tenemos:
dónde es el vector propio correspondiente. Ahora
Manten eso en mente es un escalar distinto de cero. Ninguno de los dos ni son cero. Si fueran a ser cero, sería un vector propio de por . Si ese fuera el caso, contendría solo una posición distinta de cero ya que es una diagonal distinta y, por lo tanto, el producto interno no puede ser cero después de todo. Por tanto, tenemos:
o escrito como una ecuación escalar,
Esta ecuación se conoce como ecuación secular . Por tanto, el problema se ha reducido a encontrar las raíces de la función racional definida por el lado izquierdo de esta ecuación.
Todos los algoritmos generales de valores propios deben ser iterativos, y el algoritmo divide y vencerás no es diferente. Resolver la ecuación secular no lineal requiere 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 fracasos (por un -grado función racional), haciendo que el costo de la parte iterativa de este algoritmo .
Análisis
Como es común para los algoritmos de divide y vencerás, usaremos el teorema maestro para las recurrencias de divide y vencerás para analizar el tiempo de ejecución. Recuerda que arriba dijimos que elegimos. Podemos escribir la relación de recurrencia :
En la notación del teorema maestro, y por lo tanto . Claramente,, entonces tenemos
Recuerde que anteriormente señalamos que reducir una matriz hermitiana a forma tridiagonal requiere fracasos. 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 flops para matrices tridiagonales).
La ventaja de dividir y conquistar viene cuando también se necesitan vectores propios. Si este es el caso, la reducción a forma tridiagonal toma, pero la segunda parte del algoritmo toma también. Para el algoritmo QR con una precisión de destino razonable, esto es, mientras que para divide y vencerás . La razón de esta mejora es que en divide y vencerás, el parte del algoritmo (multiplicar matrices) está separada de la iteración, mientras que en QR, esto debe ocurrir en cada paso iterativo. Añadiendo el fracasos para la reducción, la mejora total es de a fracasos.
El uso práctico del algoritmo divide y vencerás ha demostrado que en la mayoría de los problemas de valores propios realistas, el algoritmo funciona mejor que esto. La razón es que muy a menudo las matrices y los vectores tienden a ser numéricamente escasos , lo que significa que tienen muchas entradas con valores más pequeños que la precisión del punto flotante , lo que permite una deflación numérica , es decir, dividir el problema en subproblemas desacoplados.
Variantes e implementación
El algoritmo que se presenta aquí es la versión más simple. En muchas implementaciones prácticas, se utilizan correcciones de rango 1 más complicadas para garantizar la estabilidad; algunas variantes incluso usan correcciones de rango 2. [ cita requerida ]
Existen técnicas especializadas de búsqueda de raíces para funciones racionales que pueden funcionar mejor que el método de Newton-Raphson en términos de rendimiento y estabilidad. Estos se pueden utilizar para mejorar la parte iterativa del algoritmo divide y vencerás.
El algoritmo divide y vencerás se paraleliza fácilmente , y los paquetes de cálculo de álgebra lineal como LAPACK contienen implementaciones paralelas de alta calidad.
Referencias
- Demmel, James W. (1997), Álgebra lineal numérica aplicada , Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas , 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". Numerische Mathematik . 36 : 177-195.