Valores propios de pequeñas matrices

Estoy escribiendo una pequeña biblioteca numérica para matrices 2x2, 3x3 y 4x4 (real, asimétrica).

Una gran cantidad de textos de análisis numéricos recomiendan no calcular las raíces del polinomio característico y recomiendan usar el algoritmo QR de doble desplazamiento. Sin embargo, el tamaño de las matrices me hace cuestionar si simplemente calcular el polinomio característico y encontrar las raíces puede ser suficiente para esto. Encontré esta respuesta en StackExchange que admite esto, pero sé que los errores en los coeficientes polinómicos pueden producir ceros inexactos del polinomio (y, por lo tanto, valores propios diferentes). Por otro lado, la ecuación es solo cuártica en el mejor de los casos y tenemos fórmulas analíticas para las raíces polinómicas, por lo que no debemos alejarnos demasiado.

¿Cuáles son las ventajas y desventajas de utilizar el polinomio característico para obtener valores propios específicamente para este caso?

Lo primero que hay que tener en cuenta es que la correspondencia entre encontrar raíces de un polinomio ( cualquier polinomio) y encontrar los valores propios de una matriz arbitraria es realmente directa, y es un tema rico, ver Pseudozeros de polinomios y pseudospectra de matrices compañeras por Toh y Trefethen y las referencias allí.

Básicamente, el caso 2 × 2 es trivial y la fórmula estándar, es numéricamente estable y preciso, siempre que el determinante se evalúe con precisión; la fórmula directa será inexacta cuando , pero hay una fórmula precisa debido a Kahan que usa FMA ( https://hal.inria.fr/ensl-00649347v1/document ).

No existe tal equivalente directo incluso para polinomios cúbicos. ( Editar: vea el enlace al método de Kahan a continuación en el comentario de CADJunkie. Esto podría estar equivocado ) . La fórmula directa no siempre es numéricamente estable (al contrario de lo que supongo, creo), y no puede ser numéricamente estable de la misma manera. como la fórmula cuadrática insertando los signos correctos en alguna parte. Podría intentar evaluarlo con mayor precisión, por ejemplo, con aritmética doblemente nativa. Pero los enfoques que funcionan directamente en el polinomio son bastante complicados. Por ejemplo ( https://doi.org/10.1145/2699468 , que también funciona en polinomios cuárticos), podría usar el método de Newton con una buena primera aproximación calculada previamente, pero se vuelve realmente bastante complicado, y la aceleración ni siquiera es tan grande .

Las fórmulas explícitas para los polinomios de grado 4 tampoco son siempre numéricamente estables. Los polinomios que son los más difíciles tienden a tener raíces poco comunes (pequeñas o cercanas entre sí, que difieren mucho en magnitud), pero incluso probar su código en algunos miles de millones de polinomios puramente aleatorios generalmente puede revelar errores numéricos.

Una cosa curiosa relacionada con esto es que Jenkins-Traub, que es una buena forma común de encontrar raíces polinómicas, es en realidad un algoritmo de valor propio (iteración inversa) disfrazado.

Yo diría que lo explícito de las fórmulas es, en cierto modo, engañoso: te engaña para que pienses que debido a que la fórmula tiene una forma cerrada, eso significa que de alguna manera es más barato / más fácil. Realmente recomendaría que realmente pruebe / compare esto en algunos datos de prueba. No tiene por qué ser cierto: determinar las raíces de los polinomios de grado está dentro de un pequeño factor entero de dificultad del problema completo de determinar los valores propios de una matriz pequeña, y las rutinas de biblioteca estándar para valores propios son mucho más robustas Y bien probado. Entonces, al reducir el pequeño problema del valor propio a un problema de raíces polinómicas de bajo grado, no necesariamente lo está simplificando.$≥3$

¿Cuáles son las ventajas y desventajas de utilizar el polinomio característico para obtener valores propios específicamente para este caso?

Creo que la principal desventaja es que esta suposición que haces:

Por otro lado, la ecuación es solo cuártica en el mejor de los casos y tenemos fórmulas analíticas para las raíces polinómicas, por lo que no debemos alejarnos demasiado.

eso porque una fórmula está en forma cerrada y analítica, eso significa que es fácil / barata / precisa, no es necesariamente cierto. Podría ser cierto en los datos específicos que pueda tener, pero que yo sepa no es cierto en general.

PD: Toda la distinción entre forma cerrada y no cerrada se vuelve muy delicada con la aritmética de la computadora: se podría pensar que en una fórmula cúbica es una forma cerrada, pero en cuanto a la aritmética de la computadora está preocupado, esa es solo otra función racional aproximada, es quizás más rápida, pero no fundamentalmente diferente, de la función racional aproximada que define el resultado de un algoritmo de valor propio.$\cos (\cdots)$

Usar un algoritmo QR es la mejor manera. Creo que es mejor usar un algoritmo más adecuado para la tarea en cuestión.

De hecho, incluso si estaba tratando de calcular las raíces de un polinomio, sin tener la intención de usarlos como los valores propios de una matriz, a menudo se recomienda crear la matriz complementaria para ese polinomio y resolver los valores propios de esa matriz. (es decir, haga el proceso opuesto al que está considerando). El proceso es extremadamente robusto, pero no muy eficiente computacionalmente. Un algoritmo específico para la tarea de encontrar raíces polinómicas (por ejemplo, Jenkins-Traub, Método de Laguerre, etc.) sería más eficiente. E incluso si utiliza uno de estos métodos, aún puede haber algunos casos en los que formar la Matriz Companion y calcular sus valores propios todavía dé mejores resultados.

Además, como indicó Kirill, no hay forma de aprovechar las soluciones de forma cerrada para un polinomio de tercer o cuarto grado. Investigué esto hace algunos años antes de escribir una traducción del algoritmo Jenkins-Traub. Para obtener resultados numéricos, aún es mejor escribir un algoritmo desde cero como un solucionador discreto e ignorar las soluciones de forma cerrada.