Algoritmo de Faddeev-LeVerrier

Em matemática (álgebra linear), o algoritmo de Faddeev–LeVerrier é um método recursivo para calcular os coeficientes do polinômio característico

( λ ) = det ( λ

− A )

{\displaystyle p_{A}(\lambda )=\det(\lambda I_{n}-A)}

de uma matriz quadrada A, com o nome de Dmitry Konstantinovich Faddeev e Urbain Le Verrier. O cálculo deste polinômio produz os autovalores de A como suas raízes; como um polinômio matricial na própria matriz A, 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

{\displaystyle \lambda }

; em contraste, o algoritmo de Faddeev–LeVerrier trabalha diretamente com coeficientes da matriz

{\displaystyle A}

. 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. (Para pontos históricos, veja Householder. Um atalho elegante para a prova, contornando polinômios de Newton, foi introduzido por Hou. A maior parte da apresentação aqui segue Gantmacher, p. 88.)

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

( λ ) ≡ det ( λ

− A ) =

∑

k = 0

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

onde, evidentemente, cn = 1 (polinômios característicos são polinômios mônicos) e c0 = (−1)n det A. Os coeficientes cn − i são determinados por indução em i, usando uma sequência auxiliar de matrizes

≡ 0

= 1

( k = 0 )

≡ A

k − 1

n − k + 1

n − k

= −

1 k

t r

( A

)

k = 1 , ... , n

{\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}}}

Assim,

= I

n − 1

= −

t r

A = −

t r

A ;

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

= A − I

t r

A ,

n − 2

= −

1 2

(

t r

− (

t r

)

= −

1 2

(

t r

n − 1

t r

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);}

− A

t r

A −

1 2

(

t r

− (

t r

)

I ,

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

n − 3

= −

1 6

(

( tr ⁡ A

)

− 3 tr ⁡ (

) ( tr ⁡ A ) + 2 tr ⁡ (

)

= −

1 3

(

t r

n − 1

t r

n − 2

t r

A ) ;

{\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., ...;

∑

k = 1

n − m + k

k − 1

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

n − m

= −

1 m

(

t r

n − 1

t r

m − 1

+ . . . +

n − m + 1

t r

A ) = −

1 m

∑

k = 1

n − m + k

t r

; . . .

{\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 que A−1 = − Mn /c0 = (−1)n−1Mn/detA termina a recursão em λ. Isso pode ser usado para obter a inversa ou o determinante de A.

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

( λ I − A ) B = I

( λ )

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

e é, portanto, proporcional à resolvente

B = ( λ I − A

)

− 1

( λ )

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

É evidentemente um polinômio matricial em λ de grau n−1. Portanto,

B ≡

∑

k = 0

n − 1

∑

k = 0

n − k

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

onde se pode definir o inofensivo M0≡0. Inserindo as formas polinomiais explícitas na equação de definição da adjunta, acima,

∑

k = 0

k + 1

n − k

−

( A

n − k

I ) = 0

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

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

A =

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

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

∑

k = 1

(

1 + n − k

− A

n − k

)

= 0

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

o que dita a recursão

∴

= A

m − 1

n − m + 1

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

para m=1,...,n. Observe que o índice ascendente equivale a descer nas potências de λ, mas os coeficientes polinomiais c ainda precisam ser determinados em termos dos Ms e A. Isso pode ser alcançado mais facilmente através da seguinte equação auxiliar (Hou, 1998),

∂

( λ )

∂ λ

− n p = tr ⁡ A B

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

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

∂

( λ )

∂ λ

( λ )

∑

m = 0

∞

− ( m + 1 )

tr ⁡

( λ )

tr ⁡

λ I − A

≡ tr ⁡ B

{\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~.}

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

∑

k = 1

(

− n

− tr ⁡ A

n − k

)

= 0

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

de modo que

∑

m = 1

n − 1

n − m

(

n − m

+ tr ⁡ A

)

= 0

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

e finalmente

∴

n − m

= −

1 m

tr ⁡ A

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

Isso completa a recursão da seção anterior, desdobrando-se em potências decrescentes de λ. Observe ainda no algoritmo que, mais diretamente,

= A

m − 1

−

m − 1

( tr ⁡ A

m − 1

) I

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

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

adj ⁡ ( A ) = ( − 1

)

n − 1

= ( − 1

)

n − 1

(

n − 1

n − 2

+ . . . +

A +

I ) = ( − 1

)

n − 1

∑

k = 1

k − 1

{\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}~.}

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

n − k

( − 1

)

n − k

k !

(

tr ⁡ A , − 1 !

tr ⁡

, 2 !

tr ⁡

, ... , ( − 1

)

k − 1

( k − 1 ) !

tr ⁡

)

{\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 )}.}

Exemplo

A =

[

]

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

[

]

[

]

[

]

= −

− 10

[

− 7

− 6

]

[

− 14

− 8

− 12

− 14

]

= −

( − 8 )

[

− 14

− 8

− 14

]

[

]

= −

120

− 40

{\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}}}}

Além disso,

= A

I = 0

{\displaystyle {\displaystyle M_{4}=A~M_{3}+c_{0}~I=0}}

, o que confirma os cálculos acima. O polinômio característico da matriz A é, portanto,

( λ ) =

− 10

+ 4 λ − 40

{\displaystyle {\displaystyle p_{A}(\lambda )=\lambda ^{3}-10\lambda ^{2}+4\lambda -40}}

; o determinante de A é

det ( A ) = ( − 1

)

= 40

{\displaystyle {\displaystyle \det(A)=(-1)^{3}c_{0}=40}}

; o traço é 10 = −c2; e a inversa de A é

− 1

= −

1 40

[

− 14

− 8

− 14

]

[

− 0

]

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

Uma expressão equivalente mas distinta Um determinante compacto de uma solução matricial m×m para a fórmula de Jacobi acima pode, alternativamente, determinar os coeficientes c,

n − m

( − 1

)

m !

tr ⁡ A

m − 1

⋯

tr ⁡

tr ⁡ A

m − 2

⋯

⋮

tr ⁡

m − 1

tr ⁡

m − 2

⋯

tr ⁡

m − 1

⋯

tr ⁡ A

{\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}}~.}

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

Algoritmo de Faddeev-LeVerrier

Mais conteúdos de Ciência

Alstroemeria julieae

Trichomycterus landinga