| | | |

Matemática Numérica III

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

4.1 Método da Potência

O método da potência é uma técnica iterativa para computar o autovalor dominante de uma matriz e um autovetor associado. Modificações do método, tornam possível sua aplicação para a determinação de outros autovalores próximos a um número dado. Desta forma, pode ser utilizá-lo em conjunto com outra técnica de aproximação de autovalores e autovetores.

4.1.1 Aproximação do autovalor dominante

Vamos denotar o espectro de uma dada matriz An×n por

σ(A)={λ1,λ2,,λn}, (4.1)

sendo λi o i-ésimo autovalor de uma matriz diagonalizável6161endnote: 61Uma matriz An×n é diagonalizável, quando tem n autovetores linearmente independentes. A=[ai,j]i,j=1n,n, i.e. existe um vetor 𝟎𝒗in tal que

A𝒗i=λi𝒗i, (4.2)

sendo 𝒗i chamado de autovetor associado a λi. No desenvolvimento do método da potência, vamos assumir que os autovalores podem ser ordenados da seguinte forma

|λ1|>|λ2||λn|, (4.3)

em que o λ1 é chamado de autovalor dominante. Na sequência, vamos denotar por 𝑨H a transposta conjugada de A, i.e. AH=[a¯j,i]i,j=1n,n.

A iteração do método da potência consiste em

𝒛(k)=A𝒒(k1), (4.4)
𝒒(k)=𝒛(k)/𝒛(k), (4.5)
ν(k)=(𝒒(k))HA𝒒(k), (4.6)

com dada aproximação inicial 𝒒(0) para um autovetor associado a λ1. Quando o método é bem sucedido, tem-se que 𝒒(0) tende para um autovetor associado a λ1. Logo, neste caso, a sequência de quocientes de Rayleigh6262endnote: 62John William Strutt, 3º Barão Rayleigh, 1842 - 1919, físico e matemático britânico. Fonte: Wikipédia: John William Strutt.

ν(k)=(𝒒(k))HA𝒒(k)(𝒒(k))H𝒒(k)λ1, (4.7)

quando k.

Convergência

Para mostrar a convergência do método, basta mostrar que 𝒒(k) converge para um autovetor associado a λ1. Primeiramente, notamos que6363endnote: 63A afirmação segue por indução matemática.

𝒒(k)=Ak𝒒(0)Ak𝒒(0),k1. (4.8)

Para A matriz diagonalizável, temos que existe uma base {𝒗1,𝒗2,,𝒗n} de n×n formada apenas de autovetores de A. Segue que

𝒒(0)=i=1nαi𝒗i, (4.9)

onde αi. Vamos assumir que α10. Ainda, A𝒗i=λi𝒗i, donde

Ak𝒒(0) =i=1nαiAk𝒗i (4.10)
=i=1nαiλik𝒗i (4.11)
=α1λ1k[𝒗1+i=2nαiα1(λkλ1)k𝒗i] (4.12)

Da hipótese (4.3), |λi|/|λ1|<1, i=2,,n, logo

𝒚(k)=i=2nαiα1(λkλ1)k𝒗i0, (4.13)

quando k. Logo, temos que

𝒒(k) =α1λ1k(𝒗1+𝒚(k))α1λ1k(𝒗1+𝒚(k)) (4.14)
=α1λ1k|α1λ1k|(𝒗1+𝒚(k))𝒗1+𝒚(k). (4.15)

Por fim, observando que α1λ1k/|α1λ1k|0 para todo k, concluímos que 𝒒(k) tende para um vetor de mesma direção de 𝒗1 quando k.

Observação 4.1.1.(Taxa de convergência)

Pode-se mostrar a seguinte taxa de convergência para o método da potência

𝒒~(k)𝒗1C|λ2λ1|k,k1, (4.16)

onde

𝒒~(k)=𝒗1+i=2nαiα1(λiλ1)k𝒗i. (4.17)

Consulte [8, Seção 5.3.].

Código 15: Algoritmo do Método da Potência
1import numpy as np
2import numpy.linalg as npla
3
4def metPot(A, q0, maxiter=1000, tol=1e-14):
5 q = q0/npla.norm(q0)
6 nu0 = np.dot(q, A @ q)
7 print(f"{0}: {nu0}")
8
9 info = -1
10 for k in range(maxiter):
11 z = A @ q
12 q = z/npla.norm(z)
13 nu = np.dot(q, A @ q)
14
15 print(f"{k+1}: {nu}")
16 if (np.fabs(nu-nu0) < tol):
17 info = 0
18 break
19
20 nu0 = nu
21
22 return nu, q, info

Aspectos de implementação

A convergência do método da potência está condicionada a escolha de uma aproximação inicial tal que (4.9) seja tal que α10. Não há como saber a priori que o 𝒒(0) escolhido satisfaz essa condição e, caso não satisfaça as iterações não são convergentes. Por outro lado, em implementações computacionais, as computações sofrem de erros de arredondamento. Com isso, mesmo que α1=0 na expressão (4.9), o erro de arredondamento pode fazer com que a componente na direção de 𝒗1 não seja exatamente nula. Assim, na prática, o método da potência tende a convergir para qualquer escolha de 𝒒(0)𝟎.

Nos casos de dois autovalores dominantes, i.e.

|λ1|=|λ2||λ3||λn|, (4.18)

temos três possibilidades:

  • se λ1=λ2, então o método converge para qualquer autovetor no subespaço span{𝒗1, 𝒗2} (verifique);

  • se λ1=λ2, então o método não converge, mas quando aplicado à matriz A2 converge para λ12 (verifique);

  • se λ1=λ¯2, então o método não converge [8, Seção 5.3.].

4.1.2 Método da Potência Inversa

Em revisão

Esta variação do método da potência nos permite computar o autovalor mais próximo de um número μ dado, μσ(A). A ideia é aplicar o método para a matriz

Mμ1=(AμI)1. (4.19)

Neste contexto, μ é chamado de deslocamento (em inglês, shift).

Notamos que se (λi,𝒗i) é um autopar de A, então ξi=(λiμ)1 é autovalor de Mμ1 associado ao autovetor 𝒗i. De fato,

(λiμ)𝒗i=(AμI)𝒗i (4.20)
Mμ1(λiμ)𝒗i=𝒗i (4.21)
Mμ1𝒗i=(λiμ)1𝒗i. (4.22)

Isso também mostra que A e Mμ1 têm os mesmos autovetores.

Agora, se μ for suficientemente próximo de λm, autovalor simples de A, então

|λmμ|<|λiμ|,i=1,2,,n,im. (4.23)

Com isso, ξm=(λmμ)1 é o autovalor dominante de Mμ1 e, portanto, a iteração do método da potência aplicada a Mμ1 fornece este autovalor. Mais especificamente, como A e Mμ1 tem os mesmos autovetores, a iteração do método da potência inversa é dada como segue

(AμI)𝒛(k)=𝒒(k1), (4.24)
𝒒(k)=𝒛(k)/𝒛(k), (4.25)
ν(k)=(𝒒(k))HA𝒒(k), (4.26)

onde 𝒒(0) é uma aproximação inicial para o autovetor associado ao autovalor λm, ν(k)λm quando k.

4.1.3 Exercícios

Em construção


Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Opcional. Preencha seu nome para que eu possa lhe contatar.
Opcional. Preencha seu e-mail para que eu possa lhe contatar.
As informações preenchidas são enviadas por e-mail para o desenvolvedor do site e tratadas de forma privada. Consulte a política de uso de dados para mais informações.

Licença Creative Commons
Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Pedro H A Konzen
| | | |