Algoritmo de Faddeev-LeVerrier

Urbain Le Verrier (1811–1877)
El descubridor de Neptuno .

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 , llamado así por 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 , se desvanece por el teorema de Cayley-Hamilton . Calcular el polinomio característico directamente a partir de la definición del determinante es computacionalmente engorroso en la medida en que introduce una nueva cantidad simbólica ; por el contrario, el algoritmo de Faddeev-Le Verrier trabaja directamente con coeficientes de la matriz . ${\displaystyle p_{A}(\lambda )=\det(\lambda I_{n}-A)}$ ${\displaystyle \lambda }$ ${\displaystyle A}$

El algoritmo ha sido redescubierto independientemente varias veces en diferentes formas. Fue publicado por primera vez en 1840 por Urbain Le Verrier , posteriormente fue desarrollado por P. Horst, Jean-Marie Souriau , en su forma actual por Faddeev y Sominsky, y luego por JS Frame y otros. ^{[1] [2] [3] [4] [5]} (Para puntos históricos, véase Householder. ^[6] Hou introdujo un atajo elegante para la prueba, que evita los polinomios de Newton . ^[7] La ​​mayor parte de la presentación aquí sigue a Gantmacher, p. 88. ^[8] )

El algoritmo

El objetivo es calcular los coeficientes c _k del polinomio característico de la matriz n × n A ,

${\displaystyle p_{A}(\lambda )\equiv \det(\lambda I_{n}-A)=\sum _{k=0}^{n}c_{k}\lambda ^{k}~,}$

donde, evidentemente, c _n = 1 y c ₀ = (−1) ⁿ det A .

Los coeficientes c _n-i se determinan por inducción sobre i , utilizando una secuencia auxiliar de matrices

${\displaystyle {\begin{aligned}M_{0}&\equiv 0&c_{n}&=1\qquad &(k=0)\\M_{k}&\equiv AM_{k-1}+c_{n-k+1}I\qquad \qquad &c_{n-k}&=-{\frac {1}{k}}\mathrm {tr} (AM_{k})\qquad &k=1,\ldots ,n~.\end{aligned}}}$

De este modo,

${\displaystyle M_{1}=I~,\quad c_{n-1}=-\mathrm {tr} A=-c_{n}\mathrm {tr} A;}$

${\displaystyle M_{2}=A-I\mathrm {tr} A,\quad c_{n-2}=-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2}{\Bigr )}=-{\frac {1}{2}}(c_{n}\mathrm {tr} A^{2}+c_{n-1}\mathrm {tr} A);}$

${\displaystyle M_{3}=A^{2}-A\mathrm {tr} A-{\frac {1}{2}}{\Bigl (}\mathrm {tr} A^{2}-(\mathrm {tr} A)^{2}{\Bigr )}I,}$

${\displaystyle c_{n-3}=-{\tfrac {1}{6}}{\Bigl (}(\operatorname {tr} A)^{3}-3\operatorname {tr} (A^{2})(\operatorname {tr} A)+2\operatorname {tr} (A^{3}){\Bigr )}=-{\frac {1}{3}}(c_{n}\mathrm {tr} A^{3}+c_{n-1}\mathrm {tr} A^{2}+c_{n-2}\mathrm {tr} A);}$

etc., ^{[9] [10]}   ...;

${\displaystyle M_{m}=\sum _{k=1}^{m}c_{n-m+k}A^{k-1}~,}$

${\displaystyle c_{n-m}=-{\frac {1}{m}}(c_{n}\mathrm {tr} A^{m}+c_{n-1}\mathrm {tr} A^{m-1}+...+c_{n-m+1}\mathrm {tr} A)=-{\frac {1}{m}}\sum _{k=1}^{m}c_{n-m+k}\mathrm {tr} A^{k}~;...}$

Observe A ⁻¹ = − M _n /c ₀ = (−1) ^{n −1} M _n /det A termina la recursión en λ . Esto podría usarse 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

${\displaystyle (\lambda I-A)B=I~p_{A}(\lambda )}$

y por tanto es proporcional a la solvencia

${\displaystyle B=(\lambda I-A)^{-1}I~p_{A}(\lambda )~.}$

Se trata evidentemente de un polinomio matricial en λ de grado n−1 . Por lo tanto,

${\displaystyle B\equiv \sum _{k=0}^{n-1}\lambda ^{k}~B_{k}=\sum _{k=0}^{n}\lambda ^{k}~M_{n-k},}$

donde se puede definir el inofensivo M ₀ ≡0.

Insertando las formas polinomiales explícitas en la ecuación definitoria para el adjunto, arriba,

${\displaystyle \sum _{k=0}^{n}\lambda ^{k+1}M_{n-k}-\lambda ^{k}(AM_{n-k}+c_{k}I)=0~.}$

Ahora bien, en el orden más alto, el primer término se desvanece en M ₀ = 0; mientras que en el orden inferior (constante en λ , de la ecuación definitoria del adjunto, arriba),

${\displaystyle M_{n}A=B_{0}A=c_{0}~,}$

de modo que al desplazar los índices ficticios del primer término se obtiene

${\displaystyle \sum _{k=1}^{n}\lambda ^{k}{\Big (}M_{1+n-k}-AM_{n-k}+c_{k}I{\Big )}=0~,}$

Lo que dicta así la recursión.

${\displaystyle \therefore \qquad M_{m}=AM_{m-1}+c_{n-m+1}I~,}$

para m = 1,..., n . Nótese que el índice ascendente equivale a descendente en potencias de λ , pero los coeficientes polinomiales c aún deben determinarse en términos de M s y A .

Esto se puede lograr más fácilmente a través de la siguiente ecuación auxiliar (Hou, 1998):

${\displaystyle \lambda {\frac {\partial p_{A}(\lambda )}{\partial \lambda }}-np=\operatorname {tr} AB~.}$

Esto no es más que el rastro de la ecuación definitoria de B en virtud de la fórmula de Jacobi ,

${\displaystyle {\frac {\partial p_{A}(\lambda )}{\partial \lambda }}=p_{A}(\lambda )\sum _{m=0}^{\infty }\lambda ^{-(m+1)}\operatorname {tr} A^{m}=p_{A}(\lambda )~\operatorname {tr} {\frac {I}{\lambda I-A}}\equiv \operatorname {tr} B~.}$

Insertando las formas de modo polinomial en esta ecuación auxiliar se obtiene

${\displaystyle \sum _{k=1}^{n}\lambda ^{k}{\Big (}kc_{k}-nc_{k}-\operatorname {tr} AM_{n-k}{\Big )}=0~,}$

de modo que

${\displaystyle \sum _{m=1}^{n-1}\lambda ^{n-m}{\Big (}mc_{n-m}+\operatorname {tr} AM_{m}{\Big )}=0~,}$

Y finalmente

${\displaystyle \therefore \qquad c_{n-m}=-{\frac {1}{m}}\operatorname {tr} AM_{m}~.}$

Esto completa la recursión de la sección anterior, desarrollándose en potencias descendentes de λ .

Tenga en cuenta además en el algoritmo que, de forma más directa,

${\displaystyle M_{m}=AM_{m-1}-{\frac {1}{m-1}}(\operatorname {tr} AM_{m-1})I~,}$

y, en relación con el teorema de Cayley-Hamilton ,

${\displaystyle \operatorname {adj} (A)=(-1)^{n-1}M_{n}=(-1)^{n-1}(A^{n-1}+c_{n-1}A^{n-2}+...+c_{2}A+c_{1}I)=(-1)^{n-1}\sum _{k=1}^{n}c_{k}A^{k-1}~.}$

La solución final podría expresarse más convenientemente en términos de polinomios de Bell exponenciales completos como

${\displaystyle c_{n-k}={\frac {(-1)^{n-k}}{k!}}{\mathcal {B}}_{k}{\Bigl (}\operatorname {tr} A,-1!~\operatorname {tr} A^{2},2!~\operatorname {tr} A^{3},\ldots ,(-1)^{k-1}(k-1)!~\operatorname {tr} A^{k}{\Bigr )}.}$

Ejemplo

${\displaystyle {\displaystyle A=\left[{\begin{array}{rrr}3&1&5\\3&3&1\\4&6&4\end{array}}\right]}}$

${\displaystyle {\displaystyle {\begin{aligned}M_{0}&=\left[{\begin{array}{rrr}0&0&0\\0&0&0\\0&0&0\end{array}}\right]\quad &&&c_{3}&&&&&=&1\\M_{\mathbf {\color {blue}1} }&=\left[{\begin{array}{rrr}1&0&0\\0&1&0\\0&0&1\end{array}}\right]&A~M_{1}&=\left[{\begin{array}{rrr}\mathbf {\color {red}3} &1&5\\3&\mathbf {\color {red}3} &1\\4&6&\mathbf {\color {red}4} \end{array}}\right]&c_{2}&&&=-{\frac {1}{\mathbf {\color {blue}1} }}\mathbf {\color {red}10} &&=&-10\\M_{\mathbf {\color {blue}2} }&=\left[{\begin{array}{rrr}-7&1&5\\3&-7&1\\4&6&-6\end{array}}\right]\qquad &A~M_{2}&=\left[{\begin{array}{rrr}\mathbf {\color {red}2} &26&-14\\-8&\mathbf {\color {red}-12} &12\\6&-14&\mathbf {\color {red}2} \end{array}}\right]\qquad &c_{1}&&&=-{\frac {1}{\mathbf {\color {blue}2} }}\mathbf {\color {red}(-8)} &&=&4\\M_{\mathbf {\color {blue}3} }&=\left[{\begin{array}{rrr}6&26&-14\\-8&-8&12\\6&-14&6\end{array}}\right]\qquad &A~M_{3}&=\left[{\begin{array}{rrr}\mathbf {\color {red}40} &0&0\\0&\mathbf {\color {red}40} &0\\0&0&\mathbf {\color {red}40} \end{array}}\right]\qquad &c_{0}&&&=-{\frac {1}{\mathbf {\color {blue}3} }}\mathbf {\color {red}120} &&=&-40\end{aligned}}}}$

Además, , lo que confirma los cálculos anteriores. ${\displaystyle {\displaystyle M_{4}=A~M_{3}+c_{0}~I=0}}$

El polinomio característico de la matriz A es entonces ; el determinante de A es ; la traza es 10=− c ₂ ; y la inversa de A es ${\displaystyle {\displaystyle p_{A}(\lambda )=\lambda ^{3}-10\lambda ^{2}+4\lambda -40}}$ ${\displaystyle {\displaystyle \det(A)=(-1)^{3}c_{0}=40}}$

${\displaystyle {\displaystyle A^{-1}=-{\frac {1}{c_{0}}}~M_{3}={\frac {1}{40}}\left[{\begin{array}{rrr}6&26&-14\\-8&-8&12\\6&-14&6\end{array}}\right]=\left[{\begin{array}{rrr}0{.}15&0{.}65&-0{.}35\\-0{.}20&-0{.}20&0{.}30\\0{.}15&-0{.}35&0{.}15\end{array}}\right]}}$.

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]}

${\displaystyle c_{n-m}={\frac {(-1)^{m}}{m!}}{\begin{vmatrix}\operatorname {tr} A&m-1&0&\cdots &0\\\operatorname {tr} A^{2}&\operatorname {tr} A&m-2&\cdots &0\\\vdots &\vdots &&&\vdots \\\operatorname {tr} A^{m-1}&\operatorname {tr} A^{m-2}&\cdots &\cdots &1\\\operatorname {tr} A^{m}&\operatorname {tr} A^{m-1}&\cdots &\cdots &\operatorname {tr} A\end{vmatrix}}~.}$

Véase también

• Polinomio característico
• El método de Horner
• Determinante de Fredholm

Referencias

1. Urbain Le Verrier : Sur les variations séculaires des eléments des orbites pour les sept planètes principales , J. de Math. (1) 5 , 230 (1840), en línea
2. Paul Horst: Un método para determinar los coeficientes de una ecuación característica . Ann. Math. Stat. 6 83-84 (1935), doi :10.1214/aoms/1177732612
3. Jean-Marie Souriau , Une méthode pour la décomposition spectrale et l'inversion des matrices , Comptes Rend. 227 , 1010-1011 (1948).
4. DK Faddeev y IS Sominsky, Sbornik zadatch po vyshej algebra (Problemas en álgebra superior, Editorial Mir, 1972), Moscú-Leningrado (1949). Problema 979 .
5. JS Frame: Una fórmula de recursión simple para invertir una matriz (resumen) , Bull. Am. Math. Soc. 55 1045 (1949), doi :10.1090/S0002-9904-1949-09310-2
6. Householder, Alston S. (2006). La teoría de matrices en el análisis numérico . Dover Books on Mathematics. ISBN 0486449726.
7. Hou, SH (1998). "Nota para el aula: una prueba simple del algoritmo polinomial característico de Leverrier-Faddeev" SIAM review 40(3) 706-709, doi :10.1137/S003614459732076X .
8. Gantmacher, FR (1960). La teoría de matrices . Nueva York: Chelsea Publishing. ISBN 0-8218-1376-5.
9. Zadeh, Lotfi A. y Desoer, Charles A. (1963, 2008). Teoría de sistemas lineales: el enfoque del espacio de estados (Mc Graw-Hill; Dover Civil and Mechanical Engineering) ISBN 9780486466637 , pp 303–305; 
10. Abdeljaoued, Jounaidi y Lombardi, Henri (2004). Méthodes matricielles - Introducción a la complexité algébrique , (Mathématiques et Applications, 42) Springer, ISBN 3540202471 . 
11. Brown, Lowell S. (1994). Teoría cuántica de campos , Cambridge University Press. ISBN 978-0-521-46946-3 , pág. 54; Véase también Curtright, TL, Fairlie, DB y Alshal, H. (2012). "A Galileon Primer", arXiv:1212.6972, sección 3. 
12. Reed, M.; Simon, B. (1978). Métodos de 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.

Barbaresco F. (2019) Algoritmo de mapa exponencial de Souriau para aprendizaje automático en grupos de Lie de matrices. En: Nielsen F., Barbaresco F. (eds) Ciencia geométrica de la información. GSI 2019. Lecture Notes in Computer Science, vol 11712. Springer, Cham. https://doi.org/10.1007/978-3-030-26980-7_10