Dfgfdg

Métodos numéricos para la determinación de autovalores
Pablo J. Santamaría

Introducción
Muchos problemas de interés conducen al cálculo, o por lo menos a la estimación, de los valores característicos o autovalores de una matriz asociada con un sistema lineal de ecuaciones. Algebraicamente el problema consiste en, dada una matriz real n × n A, encontrar los escalares (generalmente complejos)λ (los autovalores de A) y los vectores no nulos x (los autovectores de A asociados a λ) tales que Ax = λx, x = 0 Sabemos que tal matriz A tiene precisamente n autovalores, no necesariamente distintos, que son las raíces del polinomio característico de grado n p(λ) = det(A − λI) Así pues, formalmente, los autovalores de A se pueden obtener encontrando las n raíces de p(λ). En la práctica esto puedellevarse a cabo con matrices o bien de pequeño tamaño o bien de formas particulares. En el caso general el polinomio característico es difícil de obtener y, de cualquier modo, sabemos que la determinación de las raíces de un polinomio de grado n−ésimo es también un problema difícil, puesto que, excepto para valores pequeños de n, no es un problema cerrado (esto es, no hay fórmulas explícitas). Enconsecuencia es necesario considerar algoritmos que permitan determinar sistemáticamente todos los autovalores de una matriz dada en una forma eficiente, esto es, con el menor número de operaciones posibles, y además, dado que operar con grandes matrices involucra muchas sustracciones aritméticas, tales algoritmos deben ser estables de manera que los resultados numéricos no sean en realidadnúmeros aleatorios en lugar de los autovalores deseados. La estrategia práctica a considerar es dividir el problema en dos partes: en primer lugar se reduce la matriz original A a una matriz B = (bi,j ) de una estructura más simple (en el sentido de que posea la mayor cantidad de elementos nulos posibles) pero con los mismos autovalores; y luego se calculan los autovalores de esta nueva matriz.Típicamente, las matrices buscadas son ya sea una matriz tridiagonal bij = 0, o una matriz de Hessenberg (superior) bij = 0, para i ≤ j + 2 para |i − j| > 1

cuyas formas se ilustran en la fig. 0.1. Una matriz tridiagonal tiene elementos nulos fuera de las diagonales principal, superior e inferior. Una matriz de Hessenberg tiene elementos nulos debajo de la diagonal inferior. La utilidad de esta estrategiadual resulta clara si se considera la cantidad de cómputo realizada en la manipulación de una matriz grande (digamos n = 100 o 200), tal como la multiplicación por 1

2 × 6× 6 6 6 6 6 6 6 6 6 4

× × ×

× × ×

× × ×

× × ×

× × ×

× × ×

7 7 7 7 7 7 7 7 7 7 ×5 ×

3

2

× 6× 6 6 6 6 6 6 6 6 6 4

× × ×

× × × ×

× × × × ×

× × × × × ×

× × × × × × ×

× × × × × × ××

3 × ×7 7 ×7 7 ×7 7 ×7 7 ×7 7 ×5 ×

(a) Una matriz tridiagonal

(b) Una matriz de Hessenberg

Figura 0.1.

otra matriz. Para una matriz densa (esto es, con pocos elementos nulos) el número de operaciones requeridas es del orden de n3 , en tanto que para una matriz de Hessenberg tal cálculo requiere en realidad del orden de n2 operaciones y para una matriz tridiagonal el número requeridoes de orden n. Así para una matriz grande la diferencia entre n2 y n3 es apreciable (¡ sin mencionar n versus n3 !) y por lo tanto la búsqueda de los autovalores de una matriz simplificada resultará más eficiente. Dado que podemos reducir una matriz dada a la forma de Hessenberg (o a la forma tridiagonal en ciertos casos) mediante un número finito de pasos aritméticos, la estrategia diseñada resultade suma utilidad práctica. Como las dos etapas de nuestra estrategia son (casi) independientes vamos a discutirlas separadamente. Así trataremos en primer lugar la posibilidad de reducir una matriz dada a una forma más simple. Aquí es donde las cuestiones de la forma de proceder y estabilidad de los métodos resultan cruciales.

Reducción de matrices a una forma más simple
Los métodos...