Matemática Numérica III

4 Autovalores e Autovetores 4 Autovalores e Autovetores 4.2 Iteração QR

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 $A\in\mathbb{C}^{n\times n}$ por

\sigma(A)=\{\lambda_{1},\lambda_{2},\dotsc,\lambda_{n}\},

(4.1)

sendo $\lambda_{i}\in\mathbb{C}$ o $i$ -ésimo autovalor de uma matriz diagonalizável⁶¹⁶¹endnote: ⁶¹Uma matriz $A\in\mathbb{C}^{n\times n}$ é diagonalizável, quando tem $n$ autovetores linearmente independentes. $A=[a_{i,j}]_{i,j=1}^{n,n}$ , i.e. existe um vetor $\boldsymbol{0}\neq\boldsymbol{v}_{i}\in\mathbb{C}^{n}$ tal que

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}A\boldsymbol{% v}_{i}=\lambda_{i}\boldsymbol{v}_{i},

(4.2)

sendo $\boldsymbol{v}_{i}$ chamado de autovetor associado a $\lambda_{i}$ . No desenvolvimento do método da potência, vamos assumir que os autovalores podem ser ordenados da seguinte forma

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}|\lambda_{1}|% >|\lambda_{2}|\geq\cdots\geq|\lambda_{n}|,

(4.3)

em que o $\lambda_{1}$ é chamado de autovalor dominante. Na sequência, vamos denotar por $\boldsymbol{A}^{H}$ a transposta conjugada de $A$ , i.e. $A^{H}=[\bar{a}_{j,i}]_{i,j=1}^{n,n}$ .

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

	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \boldsymbol{z}^{(k)}=A\boldsymbol{q}^{(k-1)},$		(4.4)
	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \boldsymbol{q}^{(k)}=\boldsymbol{z}^{(k)}/\left\\|\boldsymbol{z}^{(k)}\right\\|,$		(4.5)
	$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}% \nu^{(k)}=(\boldsymbol{q}^{(k)})^{H}A\boldsymbol{q}^{(k)},$		(4.6)

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

\nu^{(k)}=\frac{(\boldsymbol{q}^{(k)})^{H}A\boldsymbol{q}^{(k)}}{(\boldsymbol{% q}^{(k)})^{H}\boldsymbol{q}^{(k)}}\to\lambda_{1},

(4.7)

quando $k\to\infty$ .

Convergência

Para mostrar a convergência do método, basta mostrar que $\boldsymbol{q}^{(k)}$ converge para um autovetor associado a $\lambda_{1}$ . Primeiramente, notamos que⁶³⁶³endnote: ⁶³A afirmação segue por indução matemática.

\boldsymbol{q}^{(k)}=\frac{A^{k}\boldsymbol{q}^{(0)}}{\left\|A^{k}\boldsymbol{% q}^{(0)}\right\|},\leavevmode\nobreak\ k\geq 1.

(4.8)

Para $A$ matriz diagonalizável, temos que existe uma base $\left\{\boldsymbol{v}_{1},\boldsymbol{v}_{2},\dotsc,\boldsymbol{v}_{n}\right\}$ de $\mathbb{C}^{n\times n}$ formada apenas de autovetores de $A$ . Segue que

\boldsymbol{q}^{(0)}=\sum_{i=1}^{n}\alpha_{i}\boldsymbol{v}_{i},

(4.9)

onde $\alpha_{i}\in\mathbb{C}$ . Vamos assumir que $\alpha_{1}\neq 0$ . Ainda, $A\boldsymbol{v}_{i}=\lambda_{i}\boldsymbol{v}_{i}$ , donde

$\displaystyle A^{k}\boldsymbol{q}^{(0)}$	$\displaystyle=\sum_{i=1}^{n}\alpha_{i}A^{k}\boldsymbol{v}_{i}$	(4.10)
	$\displaystyle=\sum_{i=1}^{n}\alpha_{i}\lambda_{i}^{k}\boldsymbol{v}_{i}$	(4.11)
	$\displaystyle=\alpha_{1}\lambda_{1}^{k}\left[\boldsymbol{v}_{1}+\sum_{i=2}^{n}% \frac{\alpha_{i}}{\alpha_{1}}\left(\frac{\lambda_{k}}{\lambda_{1}}\right)^{k}% \boldsymbol{v}_{i}\right]$	(4.12)

Da hipótese (4.3), $|\lambda_{i}|/|\lambda_{1}|<1$ , $i=2,\dotsc,n$ , logo

\boldsymbol{y}^{(k)}=\sum_{i=2}^{n}\frac{\alpha_{i}}{\alpha_{1}}\left(\frac{% \lambda_{k}}{\lambda_{1}}\right)^{k}\boldsymbol{v}_{i}\to 0,

(4.13)

quando $k\to\infty$ . Logo, temos que

	$\displaystyle\boldsymbol{q}^{(k)}$	$\displaystyle=\frac{\alpha_{1}\lambda_{1}^{k}\left(\boldsymbol{v}_{1}+% \boldsymbol{y}^{(k)}\right)}{\left\\|\alpha_{1}\lambda_{1}^{k}\left(\boldsymbol% {v}_{1}+\boldsymbol{y}^{(k)}\right)\right\\|}$		(4.14)
		$\displaystyle=\frac{\alpha_{1}\lambda_{1}^{k}}{\|\alpha_{1}\lambda_{1}^{k}\|}% \frac{\left(\boldsymbol{v}_{1}+\boldsymbol{y}^{(k)}\right)}{\left\\|\boldsymbol% {v}_{1}+\boldsymbol{y}^{(k)}\right\\|}.$		(4.15)

Por fim, observando que $\alpha_{1}\lambda_{1}^{k}/|\alpha_{1}\lambda_{1}^{k}|\neq 0$ para todo $k$ , concluímos que $\boldsymbol{q}^{(k)}$ tende para um vetor de mesma direção de $\boldsymbol{v}_{1}$ quando $k\to\infty$ .

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

\left\|\tilde{\boldsymbol{q}}^{(k)}-\boldsymbol{v}_{1}\right\|\leq C\left|% \frac{\lambda_{2}}{\lambda_{1}}\right|^{k},\quad k\geq 1,

(4.16)

onde

\tilde{\boldsymbol{q}}^{(k)}=\boldsymbol{v}_{1}+\sum_{i=2}^{n}\frac{\alpha_{i}% }{\alpha_{1}}\left(\frac{\lambda_{i}}{\lambda_{1}}\right)^{k}\boldsymbol{v}_{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

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

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)

15 print(f"{k+1}: {nu}")

16 if (np.fabs(nu-nu0) < tol):

17 info = 0

18 break

20 nu0 = nu

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 $\alpha_{1}\neq 0$ . Não há como saber a priori que o $\boldsymbol{q}^{(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 $\alpha_{1}=0$ na expressão (4.9), o erro de arredondamento pode fazer com que a componente na direção de $\boldsymbol{v}_{1}$ não seja exatamente nula. Assim, na prática, o método da potência tende a convergir para qualquer escolha de $\boldsymbol{q}^{(0)}\neq\boldsymbol{0}$ .

Nos casos de dois autovalores dominantes, i.e.

|\lambda_{1}|=|\lambda_{2}|\geq|\lambda_{3}|\geq\cdots\geq|\lambda_{n}|,

(4.18)

temos três possibilidades:

•

se $\lambda_{1}=\lambda_{2}$ , então o método converge para qualquer autovetor no subespaço $\operatorname{span}\{\boldsymbol{v}_{1}$ , $\boldsymbol{v}_{2}\}$ (verifique);
•

se $\lambda_{1}=-\lambda_{2}$ , então o método não converge, mas quando aplicado à matriz $A^{2}$ converge para $\lambda_{1}^{2}$ (verifique);
•

se $\lambda_{1}=\bar{\lambda}_{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 $\mu\in\mathbb{C}$ dado, $\mu\not\in\sigma(A)$ . A ideia é aplicar o método para a matriz

M_{\mu}^{-1}=(A-\mu I)^{-1}.

(4.19)

Neste contexto, $\mu$ é chamado de deslocamento (em inglês, shift).

Notamos que se $\left(\lambda_{i},\boldsymbol{v}_{i}\right)$ é um autopar de $A$ , então $\xi_{i}=(\lambda_{i}-\mu)^{-1}$ é autovalor de $M_{\mu}^{-1}$ associado ao autovetor $\boldsymbol{v}_{i}$ . De fato,

	$\displaystyle(\lambda_{i}-\mu)\boldsymbol{v}_{i}=(A-\mu I)\boldsymbol{v}_{i}$		(4.20)
	$\displaystyle M_{\mu}^{-1}(\lambda_{i}-\mu)\boldsymbol{v}_{i}=\boldsymbol{v}_{i}$		(4.21)
	$\displaystyle M_{\mu}^{-1}\boldsymbol{v}_{i}=(\lambda_{i}-\mu)^{-1}\boldsymbol% {v}_{i}.$		(4.22)

Isso também mostra que $A$ e $M_{\mu}^{-1}$ têm os mesmos autovetores.

Agora, se $\mu$ for suficientemente próximo de $\lambda_{m}$ , autovalor simples de $A$ , então

|\lambda_{m}-\mu|<|\lambda_{i}-\mu|,\quad i=1,2,\dotsc,n,\leavevmode\nobreak\ % i\neq m.

(4.23)

Com isso, $\xi_{m}=(\lambda_{m}-\mu)^{-1}$ é o autovalor dominante de $M_{\mu}^{-1}$ e, portanto, a iteração do método da potência aplicada a $M_{\mu}^{-1}$ fornece este autovalor. Mais especificamente, como $A$ e $M_{\mu}^{-1}$ tem os mesmos autovetores, a iteração do método da potência inversa é dada como segue

	$\displaystyle(A-\mu I)\boldsymbol{z}^{(k)}=\boldsymbol{q}^{(k-1)},$		(4.24)
	$\displaystyle\boldsymbol{q}^{(k)}=\boldsymbol{z}^{(k)}/\\|\boldsymbol{z}^{(k)}\\|,$		(4.25)
	$\displaystyle\nu^{(k)}=(\boldsymbol{q}^{(k)})^{H}A\boldsymbol{q}^{(k)},$		(4.26)

onde $\boldsymbol{q}^{(0)}$ é uma aproximação inicial para o autovetor associado ao autovalor $\lambda_{m}$ , $\nu^{(k)}\to\lambda_{m}$ quando $k\to\infty$ .

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!

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.

Política de uso de dados