Leverrier Faddeev

Cálculo Diferencial e Integral: um KIT de sobrevivência -- www.dma.uem.
br/kit 1
Cálculo Diferencial e Integral: um KIT de sobrevivência

www.dma.uem.br/kit
O Algoritmo de Leverrier – Faddeev

Jorge Ferreira de Lacerda- DMA- UEM
Resumo: O Algoritmo de Leverrier-Faddeev fornece uma alternativa ao cálculo do polinômio

característico de uma matriz, sem a utilização de determinantes. Esta é uma alternativa
computacionalmente interessante, entre outras razões, devido à redução no número de cálculos
quando comparado aos métodos computacionais para o cálculo de determinantes.
1. Introdução
Um polinômio determina uma função do conjunto das
matrizes quadradas. Dada uma matriz quadrada de ordem , temos a matriz
.
O polinômio característico de uma matriz quadrada A de ordem n é dado por
(1.1)
O polinômio característico de uma matriz A é caracterizado como o único polinômio mônico (o

coeficiente de é 1) de grau tal que .
As raízes do polinômio característico são os auto-valores da matriz.
Exemplo 1: O polinômio característico da matriz é
Para determinar o polinômio característico basta determinar seus coeficientes. No exemplo acima os
coeficientes foram determinados calculando um determinante de ordem 3.
1
Cálculo Diferencial e Integral: um KIT de sobrevivência -- www.dma.uem.br/kit 2
O algoritmo de Leverrier determina os coeficientes do polinômio característico de uma matriz a

partir dos traços (soma dos elementos da diagonal principal) das potências desta matriz.
2. Algorítmo de Leverrier
Se
, (1.2)
então os coeficientes são dados por
(L)
onde
Exemplo 2: Apliquemos o algoritmo de Leverrier para a matriz do exemplo 1.
Das relações (L) obtemos,
Assim . Observe que, aqui, nenhum determinante foi calculado.
D. K. Fadeev introduziu a seguinte melhoria no método de Leverrier:
3. Algoritmo de Leverrier-Faddeev
Se
, (1.3)
então os coeficientes são dados por
2
(F)
Exemplo 3: Apliquemos o algoritmo de Leverrier-Faddeev para a matriz do exemplo 1.
Observe que .
Assim, .
Observações: Como e , temos que

. Logo, a matriz
é a inversa da matriz .
Além disso, no polinômio característico da matriz ,

, o termo constante é, a menos de um
sinal, igual ao determinante da matriz . Precisamente, .
Assim, a seqüência (F) inclui o determinante e a inversa da matriz fornecendo uma maneira
alternativa de calcular o determinante e a inversa de uma matriz.
4. Justificativa do algoritmo de Leverrier-Faddeev
i. As raízes do polinômio característico são os auto-valores da matriz
3
ii. Se é auto-valor de , então é auto-valor de .
iii. A soma dos autovalores de uma matriz é igual ao seu traço.
De (ii) temos
iv. Os coeficientes do polinômio característico são dados pelas funções simétricas elementares
de suas raízes .
Se , então
v. A partir das identidades de Newton que relacionam as funções simétricas elementares

obtemos as seguintes relações que determinam os coeficientes a partir dos traços de .
(L)
5. Demonstração de (F) a partir de (L)

A seqüência de matrizes dada por (F) é da forma
onde , .
Portanto .
Isto é, os coeficientes verificam as relações (L). Logo . Assim ,

.
Em particular,
6. Demonstração das relações (L) , para
De (iv) temos,
4
Assim,
Com uma pequena modificação o algoritmo (F) pode ser
Uma demonstração de (F) utilizando a transformada de Laplace pode ser encontrada em [2].
5
7. Alguns comentários
a) As operações do algoritmo de Leverrier-Faddeev são bastante simples: cálculo do traço e

divisão por um inteiro ( ) , modificação da diagonal (soma )e
multiplicação por uma matriz fixa, ( ).
b) A matriz calculada em uma etapa depende somente da matriz calculada na etapa anterior
. Portanto só precisamos guardar para a etapa seguinte a última
matriz calculada e os coeficientes .
c) Se a matriz tem entradas inteiras, sabemos que os coeficientes devem ser inteiros e
apenas números inteiros aparecem no algoritmo.
8. Procedimentos em Maple e MatLab

Ilustramos o algoritmo de Leverrier-Faddeev com os seguintes procedimentos em Maple e
MatLab, disponíveis em [3]. Nesses procedimentos o sistema criará aleatoriamente uma matriz
quadrada, em seguida é calculado o polinômio característico dessa matriz aleatória utilizando o
algoritmo de Leverrier-Faddeeev. Esses procedimentos têm aplicação apenas didática. Veja [3]
para outros exemplos.
Procedimento em MatLab:
Crie um arquivo LF.m com os seguintes comandos e o execute. O procedimento solicita a dimensão
da matriz a ser criada e retornará os coeficientes do seu polinômio característico e suas raízes.
clear
n=input('Entre com o valor de n=');
A=randint(n,n),B=eye(n); for i=1:1:n
a(i)=-trace(A*B)/i, B=A*B+ a(i)*eye(n),
end, disp('O polinomio característo é'); p=[1,a],
disp('Suas raízes são'), roots(p),
Procedimento em Maple:
Crie um arquivo LF.mws com os seguintes comandos. O procedimento cria uma matriz quadrada de
dimensão entre 5 e 10 e retornará os coeficientes do seu polinômio característico.
> restart: with(linalg):

> num:=rand(5..10): n:=num():
> A:=randmatrix(n, n); 'n'=n:
> LF:=proc(A) local n,a,i,J,B:
n:=rowdim(A):J:=(i,j) ->matrix(n,n,(i,j)-
>piecewise(i<>j,0,i=j,1)):J:=J(n,n):B:=J:for i from 1 to n do
a[i]:=-(trace(A&*B))/i: B:=evalm(A&*B+(a[i])*J): od:print(`o
polinômio característico da matriz é`, x^n+sum('a[i]*x^(n-
i)','i'=1..n)): end:
> LF(A);
6
Referências
[1] D. K. Faddeev and V. N. Faddeeva, Computational Methods of Linear Algebra, Freeman, San
Francisco, 1963.
[2] Shui-Hung Hou, On The Leverrier-Faddeev algorithm, Dept of Applied Math. , Hong Kong
Polytechnic University.
[3] D. Andrade. Cálculo diferencial e Integral: um KIT de sobrevivência.

http://www.dma.uem.br/kit/LeverrierFaddeev1.html, 2007.

Leverrier Faddeev

Enviado por

Direitos autorais:

Formatos disponíveis

Leverrier Faddeev

Enviado por

Dados do documento

Descrição original:

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

Leverrier Faddeev

Enviado por

Direitos autorais:

Formatos disponíveis

Cálculo Diferencial e Integral: um KIT de sobrevivência -- www.dma.uem.

Cálculo Diferencial e Integral: um KIT de sobrevivência

O Algoritmo de Leverrier – Faddeev

Resumo: O Algoritmo de Leverrier-Faddeev fornece uma alternativa ao cálculo do polinômio

O polinômio característico de uma matriz A é caracterizado como o único polinômio mônico (o

Exemplo 1: O polinômio característico da matriz é

O algoritmo de Leverrier determina os coeficientes do polinômio característico de uma matriz a

Exemplo 2: Apliquemos o algoritmo de Leverrier para a matriz do exemplo 1.

Das relações (L) obtemos,

Assim . Observe que, aqui, nenhum determinante foi calculado.

D. K. Fadeev introduziu a seguinte melhoria no método de Leverrier:

Exemplo 3: Apliquemos o algoritmo de Leverrier-Faddeev para a matriz do exemplo 1.

Observações: Como e , temos que

Além disso, no polinômio característico da matriz ,

4. Justificativa do algoritmo de Leverrier-Faddeev

i. As raízes do polinômio característico são os auto-valores da matriz

ii. Se é auto-valor de , então é auto-valor de .

iii. A soma dos autovalores de uma matriz é igual ao seu traço.

v. A partir das identidades de Newton que relacionam as funções simétricas elementares

5. Demonstração de (F) a partir de (L)

Isto é, os coeficientes verificam as relações (L). Logo . Assim ,

6. Demonstração das relações (L) , para

Com uma pequena modificação o algoritmo (F) pode ser

a) As operações do algoritmo de Leverrier-Faddeev são bastante simples: cálculo do traço e

8. Procedimentos em Maple e MatLab

> restart: with(linalg):

[3] D. Andrade. Cálculo diferencial e Integral: um KIT de sobrevivência.

Você também pode gostar