Algoritmo eigenvalue divide y vencerás

Los algoritmos Divide y Vencerás eigenvalue son una clase de algoritmos eigenvalue para hermitanos o matrices reales simétricas que recientemente (cerca de 1990) se han hecho competitivos en plazo de estabilidad y eficiencia con los algoritmos más tradicionales como algoritmos QR.El concepto básico detrás de estos algoritmos es divide y vencerás llevado a las ciencias informáticas.Un problema eigenvalue se divide en dos problemas de aproximadamente la mitad del problema general; cada uno de estos problemas es resuelto recursivamente y los eigenvalue del problema original son computados a partir de los resultados de los problemas más pequeños.Aquí presentamos la versión más sencilla de un algoritmo de dividir y vencerás, similar al originalmente propuesto por Cuppen en 1981.Muchos detalles que quedan fuera del alcance de este artículo serán omitidos; aun así, sin considerar estos detalles, el algoritmo no es plenamente estable., y casi siempre es más rápido solucionar estos dos problemas más pequeños que solucionar todo el problema original inmediatamente.Esta técnica puede ser usada para mejorar la eficiencia de muchos algoritmos eigenvalue, pero tiene una especial importancia para dividir y vencerás.Además de que el algoritmo puede ser modificado para matrices Hermitianas, aquí no daremos los detalles.puede modificar el bloque diagonal dependiendo de la elección delHay muchas maneras de descomponer la matriz.como una matriz de bloque diagonal más una corrección Rank-1 La única diferencia entrey puede ser complementado con llamadas recursivas al algoritmo divide y vencerás, también implementaciones prácticas a menudo cambian al algoritmo QR para submatrices suficientemente pequeñas.La tarea pendiente ha sido reducida a encontrar el eigenvalue de una matriz diagonal más una corrección Rank-1.Antes de mostrar como hacer esto, vamos a simplificar la notación.no puede ser cero después de todo.Por tanto el problema ha sido reducido a encontrar las raíces de la función racional definida por la parte izquierda de esta ecuación.Generalmente el algoritmo Eigenvalue debe ser iterativo y el algoritmo divide y vencerá no es diferente.Resolver la ecuación secular no linear requiere una técnica iterativa, como el método Newton-Raphson.Como es común el algoritmo divide y vencerás, utilizaremos el Teorema Maestro para analizar el tiempo de ejecución.Recordar que señalamos reducir la matriz hermitiana a forma tridiagonal tomaEstos tiempos son pequeñps para el tiempo de ejecución de la parte dividen y vencerás, y en este punto no está claro que ventajas ofrece el algoritmo divide y vencerás frente al algoritmo QR (que también usaSi este es el caso, la reducción a forma tridiagonal seráconsiderando que para dividir y conquistar esto es.La razón de esta mejora en divide y vencerás es que el.El uso práctico del algoritmo divide y vencerás ha mostrado en los más realistas problemas eigenvalues, funciona mejor que lo estimado.tienden a ser numéricamente dispersos, esto significa que tienen muchas entradas con valores más pequeños que la precisión punto flotante, admitiendo deformaciones numérica, i.e.Estos pueden ser usados para mejorar la parte iterativa del algoritmo divide y vencerás.El algoritmo presentado aquí es la versión más sencilla.En muchas implementaciones prácticas más complicadas correcciones Rank-1 son usadas para garantizar estabilidad.Estos pueden ser usados para mejorar la parte iterativa del algoritmo divide y vencerás.El algoritmo divide y vencerás es fácilmente paralelizado y computarizado en paquetes de álgebra lineal así como LAPACK contiene implementaciones paralelas de una alta calidad