Jacobi eigenvalue algorithm
Método iterativo para calcular los autovalores y autovectores de una matriz simétrica real, mediante una serie de rotaciones que anulan sus elementos fuera de la diagonal.
- Año
- 1846
- Sección
- Matemáticas
Historia
El algoritmo de Jacobi sirve para diagonalizar una matriz simétrica real, es decir, para encontrar sus autovalores (valores característicos) y sus autovectores (direcciones que la matriz solo estira o encoge). Una matriz así aparece en problemas de física, estadística e ingeniería, y conocer sus autovalores permite analizar vibraciones, componentes principales de un conjunto de datos o la estabilidad de un sistema. Su idea central es sencilla: se aplica repetidamente una rotación de ejes que hace cero uno de los elementos situados fuera de la diagonal, de modo que la matriz se va pareciendo cada vez más a una diagonal, cuyos elementos son los autovalores buscados.
Antes de Jacobi existían métodos para problemas concretos, pero no un procedimiento general y fiable para matrices simétricas. El matemático alemán Carl Gustav Jacob Jacobi propuso este método en 1846, dentro de sus trabajos sobre sistemas de ecuaciones y formas cuadráticas. En aquella época el cálculo era manual y el procedimiento, aunque elegante, resultaba demasiado laborioso para matrices grandes, por lo que su uso práctico fue limitado durante más de un siglo.
El método comenzó a emplearse de forma generalizada en la década de 1950, cuando la llegada de los ordenadores hizo viable repetir miles de operaciones aritméticas en poco tiempo. Cada paso consiste en elegir el elemento fuera de la diagonal de mayor valor absoluto, llamado pivote, y aplicar una rotación de Givens, una transformación ortogonal que no altera la norma de la matriz. Con cada rotación la suma de los cuadrados de los elementos fuera de la diagonal disminuye, lo que garantiza la convergencia. Se pueden agrupar N rotaciones en un barrido, y se ha demostrado que la convergencia es al menos lineal, y cuadrática cerca de la solución cuando los autovalores están bien separados, según un resultado de Schönhage.
La principal limitación del método es su coste: buscar el pivote exige examinar casi todos los elementos fuera de la diagonal, lo que lleva la complejidad de un barrido clásico a orden n elevado a cuatro. Para reducir ese coste se han propuesto variantes que recorren los elementos en un orden fijo, o que guardan el máximo de cada fila para acelerar la búsqueda, hasta llegar a un orden de n al cubo por barrido. Además, al ser un método denso, no aprovecha bien las matrices dispersas, en las que la mayoría de los elementos son nulos.
Hoy el método de Jacobi tiene un papel más pequeño en el cálculo de grandes volúmenes de datos, donde suelen preferirse otros algoritmos, pero sigue siendo valorado por su precisión y porque sus rotaciones pueden repartirse fácilmente entre varios procesadores. Sus ideas forman parte de las herramientas numéricas que sustentan programas de análisis estadístico, simulación y cálculo científico.
Cronología
- 1846Jacobi propone el método para diagonalizar matrices simétricas reales.
- 1950El método empieza a usarse de forma generalizada al llegar los ordenadores al cálculo numérico.
- 1960Se estudian las propiedades de convergencia del método, con resultados de Schönhage sobre convergencia cuadrática.