220px|thumb|direita|Urbain Le Verrier (1811–1877) O descobridor de Netuno.

Em matemática (álgebra linear), o algoritmo de Faddeev–LeVerrier é um método recursivo para calcular os coeficientes do polinômio característico de uma matriz quadrada , com o nome de Dmitry Konstantinovich Faddeev e Urbain Le Verrier. O cálculo deste polinômio produz os autovalores de como suas raízes; como um polinômio matricial na própria matriz , ele se anula pelo teorema de Cayley–Hamilton. Calcular o polinômio característico diretamente a partir da definição do determinante é computacionalmente trabalhoso na medida em que introduz uma nova quantidade simbólica ; em contraste, o algoritmo de Faddeev–LeVerrier trabalha diretamente com coeficientes da matriz .

O algoritmo foi redescoberto independentemente várias vezes em diferentes formas. Foi publicado pela primeira vez em 1840 por Urbain Le Verrier, posteriormente redesenvolvido por P. Horst, Jean-Marie Souriau, na sua forma atual aqui por Faddeev e Sominsky, e ainda por J. S. Frame, e outros.Urbain Le Verrier: Sur les variations séculaires des éléments des orbites pour les sept planètes principales, J. de Math. (1) 5, 230 (1840), OnlinePaul Horst: A method of determining the coefficients of a characteristic equation. Ann. Math. Stat. 6 83-84 (1935), Jean-Marie Souriau, Une méthode pour la décomposition spectrale et l'inversion des matrices, Comptes Rend. 227, 1010-1011 (1948).D. K. Faddeev, and I. S. Sominsky, Sbornik zadatch po vyshej algebra (Problems in higher algebra , Mir publishers, 1972), Moscow-Leningrad (1949). Problem 979.J. S. Frame: A simple recursion formula for inverting a matrix (abstract), Bull. Am. Math. Soc. 55 1045 (1949), (Para pontos históricos, veja Householder. Um atalho elegante para a prova, contornando polinômios de Newton, foi introduzido por Hou.Hou, S. H. (1998). "Classroom Note: A Simple Proof of the Leverrier--Faddeev Characteristic Polynomial Algorithm" SIAM review 40(3) 706-709, . A maior parte da apresentação aqui segue Gantmacher, p. 88.)

O algoritmo O objetivo é calcular os coeficientes do polinômio característico da matriz ,

onde, evidentemente, = 1 (polinômios característicos são polinômios mônicos) e 0 = (−1)n det .

Os coeficientes são determinados por indução em , usando uma sequência auxiliar de matrizes

Assim,

etc.,Zadeh, Lotfi A. e Desoer, Charles A. (1963, 2008). Linear System Theory: The State Space Approach (Mc Graw-Hill; Dover Civil and Mechanical Engineering) , pp 303–305; Abdeljaoued, Jounaidi e Lombardi, Henri (2004). Méthodes matricielles - Introduction à la complexité algébrique, (Mathématiques et Applications, 42) Springer, .   ...;

Observe que termina a recursão em . Isso pode ser usado para obter a inversa ou o determinante de .

Derivação A prova baseia-se nos modos da matriz adjunta, , as matrizes auxiliares encontradas.   Esta matriz é definida por

e é, portanto, proporcional à resolvente

É evidentemente um polinômio matricial em de grau . Portanto,

onde se pode definir o inofensivo ≡0.

Inserindo as formas polinomiais explícitas na equação de definição da adjunta, acima,

Agora, na ordem mais alta, o primeiro termo se anula por =0; enquanto na ordem mais baixa (constante em , da equação de definição da adjunta, acima),

de modo que deslocando os índices fictícios do primeiro termo obtém-se

o que dita a recursão

para =1,...,. Observe que o índice ascendente equivale a descer nas potências de , mas os coeficientes polinomiais ainda precisam ser determinados em termos dos s e .

Isso pode ser alcançado mais facilmente através da seguinte equação auxiliar (Hou, 1998),

Esta é apenas o traço da equação de definição para em virtude da fórmula de Jacobi,

Inserindo as formas polinomiais dos modos nesta equação auxiliar obtém-se

de modo que

e finalmente

Isso completa a recursão da seção anterior, desdobrando-se em potências decrescentes de .

Observe ainda no algoritmo que, mais diretamente,

e, em conformidade com o teorema de Cayley–Hamilton,

A solução final pode ser mais convenientemente expressa em termos de polinômios de Bell exponenciais completos como

Exemplo

Além disso, , o que confirma os cálculos acima.

O polinômio característico da matriz é, portanto, ; o determinante de é ; o traço é 10 = −c2; e a inversa de é .

Uma expressão equivalente mas distinta Um determinante compacto de uma solução matricial × para a fórmula de Jacobi acima pode, alternativamente, determinar os coeficientes ,Brown, Lowell S. (1994). Quantum Field Theory, Cambridge University Press. , p. 54; Veja também Curtright, T. L., Fairlie, D. B. e Alshal, H. (2012). "A Galileon Primer", arXiv:1212.6972, seção 3.

Ver também

Polinômio característico Método de Horner Determinante de Fredholm

Referências

Bibliografia Barbaresco F. (2019) Souriau Exponential Map Algorithm for Machine Learning on Matrix Lie Groups. In: Nielsen F., Barbaresco F. (eds) Geometric Science of Information. GSI 2019. Lecture Notes in Computer Science, vol 11712. Springer, Cham. https://doi.org/10.1007/978-3-030-26980-7_10

Categoria:Polinómios Categoria:Teoria das matrizes Categoria:Álgebra linear Categoria:Física matemática Categoria:Determinantes Categoria:Polinômios homogêneos