Algoritmo Faddeev – LeVerrier - Faddeev–LeVerrier algorithm

Em matemática ( álgebra linear ), o algoritmo Faddeev – LeVerrier é um método recursivo para calcular os coeficientes do polinômio característico de uma matriz quadrada , A , em homenagem a Dmitry Konstantinovich Faddeev e Urbain Le Verrier . O cálculo desse polinômio produz os autovalores de A como suas raízes; como uma matriz polinomial na própria matriz A , ela desaparece pelo teorema fundamental de Cayley-Hamilton . O cálculo do determinante a partir da definição do polinômio característico, no entanto, é computacionalmente complicado, porque é uma nova quantidade simbólica, ao passo que esse algoritmo trabalha diretamente com coeficientes de matriz . ${\ displaystyle p_ {A} (\ lambda) = \ det (\ lambda I_ {n} -A)}$${\ displaystyle \ lambda}$${\ displaystyle A}$

O algoritmo foi redescoberto de forma independente várias vezes, de uma forma ou de outra. Foi publicado pela primeira vez em 1840 por Urbain Le Verrier , posteriormente redesenvolvido por P. Horst, Jean-Marie Souriau , em sua forma atual aqui por Faddeev e Sominsky, e posteriormente por JS Frame e outros. (Para pontos históricos, consulte Householder. Um atalho elegante para a prova, ignorando os polinômios de Newton , foi introduzido por Hou. A maior parte da apresentação aqui segue Gantmacher, p. 88.)

O Algoritmo

O objectivo consiste em calcular os coeficientes c _k do polinómio característico da N × n matriz A ,

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

em que, evidentemente, c _n = 1 e c ₀ = (-1) ⁿ det Uma .

Os coeficientes são determinados recursivamente de cima para baixo, por força da sequência de matrizes auxiliares M ,

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

Desse modo,

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

${\ displaystyle M_ {2} = AI \ 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, ...;

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

${\ displaystyle c_ {nm} = - {\ 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 a recursão em λ . Isto poderia ser usado para obter o inverso ou o determinante de Uma .

Derivação

A prova se baseia nos modos da matriz adjugada , B _k ≡ M _{n − k} , as matrizes auxiliares encontradas. Esta matriz é definida por

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

e é, portanto, proporcional ao resolvente

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

É evidentemente um polinômio de matriz em λ de grau n − 1 . Desse modo,

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

onde se pode definir o inofensivo M ₀ ≡0.

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

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

Agora, na ordem mais alta, o primeiro termo desaparece por M ₀ = 0; ao passo que na ordem inferior (constante em λ , a partir da equação de definição do adjunto, acima),

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

de modo que mudar os índices dummy do primeiro termo produz

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

que assim dita a recursão

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

para m = 1, ..., n . Note-se que índice ascendente corresponde a descer em potências de λ , mas os coeficientes polinomiais c estão ainda a ser determinado em termos de H S e A .

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

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

Este é apenas o traço da equação definidora de B por meio da 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 IA}} \ equiv \ operatorname { tr} B ~.}$

Inserir as formas de modo polinomial nesta equação auxiliar resulta

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

de modo a

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

e finalmente

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

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

Observe no algoritmo que, mais diretamente,

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

e, de acordo com o teorema de Cayley-Hamilton ,

${\ displaystyle \ operatorname {adj} (A) = (-) ^ {n-1} M_ {n} = (-) ^ {n-1} (A ^ {n-1} + c_ {n-1} A ^ {n-2} + ... + c_ {2} A + c_ {1} I) = (-) ^ {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

${\ displaystyle c_ {nk} = {\ frac {(-1) ^ {nk}} {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

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

${\ displaystyle {\ displaystyle {\ begin {alinhados} 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 {re d} 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 {alinhado}}}}$

Além disso ,, o que confirma os cálculos acima. ${\ displaystyle {\ displaystyle M_ {4} = A ~ M_ {3} + c_ {0} ~ I = 0}}$

O polinômio característico da matriz A é assim ; o determinante de A é ; o traço é 10 = - c ₂ ; e o inverso de A é ${\ 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 { matriz} {rrr} 6 e 26 e -14 \\ - 8 e -8 e 12 \\ 6 & -14 & 6 \ end {matriz}} \ direita] = \ esquerda [{\ begin {matriz} {rrr} 0 {.} 15 e 0 {.} 65 e -0 {.} 35 \\ - 0 {.} 20 e -0 {.} 20 e 0 {.} 30 \\ 0 {.} 15 e -0 {.} 35 e 0 {.} 15 \ end {array}} \ right] }}$.

Uma expressão equivalente, mas distinta

Um determinante compacto de um m × m solução -matrix para a fórmula acima de Jacobi pode alternativamente determinar os coeficientes c ,

${\ displaystyle c_ {nm} = {\ frac {(-1) ^ {m}} {m!}} {\ begin {vmatrix} \ operatorname {tr} A & m-1 & 0 & \ cdots \\\ operatorname {tr} A ^ {2} & \ operatorname {tr} A & m-2 & \ cdots \\\ 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}} ~.}$

Veja também

• Álgebra externa § Algoritmo de Leverrier
• Fórmula de Jacobi
• Fredholm determinante

Referências