En matemáticas ( álgebra lineal ), el algoritmo de Faddeev-LeVerrier es un método recursivo para calcular los coeficientes del polinomio característico de una matriz cuadrada , A , que lleva el nombre de Dmitry Konstantinovich Faddeev y Urbain Le Verrier . El cálculo de este polinomio produce los valores propios de A como sus raíces; como polinomio matricial en la propia matriz A , desaparece por el teorema fundamental de Cayley-Hamilton . Sin embargo, calcular el determinante a partir de la definición de polinomio característico es computacionalmente engorroso, porque es una nueva cantidad simbólica, mientras que este algoritmo trabaja directamente con coeficientes de matriz .
El algoritmo ha sido redescubierto de forma independiente varias veces, de una forma u otra. Fue publicado por primera vez en 1840 por Urbain Le Verrier , posteriormente remodelado por P. Horst, Jean-Marie Souriau , en su forma actual aquí por Faddeev y Sominsky, y más adelante por JS Frame, y otros. [1] [2] [3] [4] [5] (Para los puntos históricos, consulte Householder. [6] Hou introdujo un elegante atajo a la demostración, sin pasar por los polinomios de Newton . [7] La mayor parte de la presentación aquí sigue Gantmacher, p. 88. [8] )
El algoritmo
El objetivo es calcular los coeficientes c k del polinomio característico de la matriz A de n × n ,
donde, evidentemente, c n = 1 y c 0 = (-1) n det A .
Los coeficientes se determinan recursivamente de arriba hacia abajo, a fuerza de las matrices auxiliares M ,
Por lo tanto,
Observe A −1 = - M n / c 0 = (−1) n −1 M n / det A termina la recursión en λ . Esto podría ser utilizado para obtener la inversa o el determinante de A .
Derivación
La prueba se basa en los modos de la matriz adjunta , B k ≡ M n − k , las matrices auxiliares encontradas. Esta matriz está definida por
y, por tanto, es proporcional a la resolución
Evidentemente es un polinomio matricial en λ de grado n − 1 . Por lo tanto,
donde se puede definir el inofensivo M 0 ≡0.
Insertar las formas polinomiales explícitas en la ecuación definitoria para el adyuvante, arriba,
Ahora, en el orden más alto, el primer término desaparece en M 0 = 0; mientras que en el orden inferior (constante en λ , de la ecuación definitoria del adyuvante, arriba),
de modo que al cambiar los índices ficticios del primer término se obtiene
que así dicta la recursividad
para m = 1, ..., n . Nota que el índice ascendente asciende a descendente en potencias de λ , pero los coeficientes del polinomio c aún no se determinó en términos de la M s y A .
Esto se puede lograr más fácilmente mediante la siguiente ecuación auxiliar (Hou, 1998),
Esto es solo el rastro de la ecuación definitoria para B a fuerza de la fórmula de Jacobi ,
Al insertar las formas del modo polinomial en esta ecuación auxiliar se obtiene
así que eso
y finalmente
Esto completa la recursividad de la sección anterior, desarrollándose en potencias descendentes de λ .
Observe además en el algoritmo que, más directamente,
y, de acuerdo con el teorema de Cayley-Hamilton ,
La solución final podría expresarse más convenientemente en términos de polinomios de Bell exponenciales completos como
Ejemplo
Además, , lo que confirma los cálculos anteriores.
El polinomio característico de la matriz A es entonces; el determinante de A es; la traza es 10 = - c 2 ; y la inversa de A es
- .
Una expresión equivalente pero distinta
Un determinante compacto de una solución de matriz m × m para la fórmula de Jacobi anterior puede determinar alternativamente los coeficientes c , [11] [12]
Ver también
Referencias
- ^ Urbain Le Verrier : Sur les variaciones séculaires des éléments des orbites pour les sept planètes principales , J. de Math. (1) 5 , 230 (1840), en línea
- ^ Paul Horst: un método para determinar los coeficientes de una ecuación característica . Ana. Matemáticas. Stat. 6 83-84 (1935), doi : 10.1214 / aoms / 1177732612
- ↑ Jean-Marie Souriau , Une méthode pour la décomposition spectrale et l'inversion des matrices , Comptes Rend. 227 , 1010-1011 (1948).
- ^ DK Faddeev, e IS Sominsky, Sbornik zadatch po vyshej álgebra ( Problemas en álgebra superior , editores Mir, 1972), Moscú-Leningrado (1949). Problema 979 .
- ^ JS Frame: una fórmula de recursividad simple para invertir una matriz (resumen) , Bull. Soy. Matemáticas. Soc. 55 1045 (1949), doi : 10.1090 / S0002-9904-1949-09310-2
- ^ Jefe de familia, Alston S. (2006). La teoría de las matrices en el análisis numérico . Libros de Dover sobre matemáticas. ISBN 0486449726.
- ^ Hou, SH (1998). "Nota de clase: Una prueba simple del algoritmo polinomial característico de Leverrier - Faddeev" Revisión de SIAM 40 (3) 706-709, doi : 10.1137 / S003614459732076X .
- ^ Gantmacher, FR (1960). La teoría de las matrices . Nueva York: Chelsea Publishing. ISBN 0-8218-1376-5.
- ^ Zadeh, Lotfi A. y Desoer, Charles A. (1963, 2008). Teoría de sistemas lineales: el enfoque espacial estatal (Mc Graw-Hill; Dover Civil and Mechanical Engineering) ISBN 9780486466637 , págs. 303–305;
- ^ Abdeljaoued, Jounaidi y Lombardi, Henri (2004). Méthodes matricielles - Introduction à la complexité algébrique , (Mathématiques et Applications, 42) Springer, ISBN 3540202471 .
- ^ Brown, Lowell S. (1994). Teoría cuántica de campos , Cambridge University Press. ISBN 978-0-521-46946-3 , pág. 54; Ver también, Curtright, TL, Fairlie, DB y Alshal, H. (2012). "A Galileon Primer", arXiv: 1212.6972, sección 3.
- ^ Reed, M .; Simon, B. (1978). Métodos de la física matemática moderna . Vol. 4 Análisis de operadores. EE.UU .: ACADEMIC PRESS, INC. Págs. 323–333, 340, 343. ISBN 0-12-585004-2.
|volume=
tiene texto extra ( ayuda )