Colabore! Saiba mais screen_rotation

Ao navegar por este site , você concorda com a Política de Uso de Dados.

| | | | |

3 Autovalores e Autovetores 3 Autovalores e Autovetores 3.2 Iteração QR

3.1 Método da Potência

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

Em revisão

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.

3.1.1 Autovalor dominante

Em revisão

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

(3.1)

sendo $\lambda_{i}\in\mathbb{C}$ o $i$ -ésimo autovalor de uma matriz diagonalizável⁴⁹⁴⁹endnote: ⁴⁹Existe uma base de $\mathbb{C}^{n\times n}$ formada apenas de autovetores de $A$ . $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}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}A\boldsymbol{v% }_{i}=\lambda_{i}\boldsymbol{v}_{i},

(3.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}% \pgfsys@color@rgb@stroke{0}{0}{1}\pgfsys@color@rgb@fill{0}{0}{1}|\lambda_{1}|>% |\lambda_{2}|\geq\cdots\geq|\lambda_{n}|.

(3.3)

Assim sendo, 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\boldsymbol{z}^{(k)}=A\boldsymbol{q}^{(k-1)},$		(3.4)
	$\displaystyle\boldsymbol{q}^{(k)}=\boldsymbol{z}^{(k)}/\left\\|\boldsymbol{z}^{% (k)}\right\\|,$		(3.5)
	$\displaystyle\nu^{(k)}=(\boldsymbol{q}^{(k)})^{H}A\boldsymbol{q}^{(k)},$		(3.6)

com dada aproximação inicial $\boldsymbol{q}^{(0)}$ para um autovetor associado a $\lambda_{1}$ . Quando o método é bem sucedido, tem-se $\nu^{(k)}\to\lambda_{1}$ 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: ⁵⁰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.

(3.7)

Para $A$ 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},

(3.8)

onde $\alpha_{i}\in\mathbb{C}$ . Vamos assumir que $\alpha_{1}\neq 0$ ⁵¹⁵¹endnote: ⁵¹Condição necessária para a convergência.. 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}$	(3.9)
	$\displaystyle=\sum_{i=1}^{n}\alpha_{i}\lambda_{i}^{k}\boldsymbol{v}_{i}$	(3.10)
	$\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]$	(3.11)

Como $|\lambda_{i}|/|\lambda_{1}|<1$ , $i=2,\dotsc,n$ , temos que

\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,

(3.12)

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}\left(\boldsymbol{v}_% {1}+\boldsymbol{y}^{(k)}\right)\right\\|}$		(3.13)
		$\displaystyle=\frac{\lambda_{1}}{\|\lambda_{1}\|}\frac{\left(\boldsymbol{v}_{1}+% \boldsymbol{y}^{(k)}\right)}{\left\\|\boldsymbol{v}_{1}+\boldsymbol{y}^{(k)}% \right\\|}.$		(3.14)

Por fim, observamos que $\lambda_{1}/|\lambda_{1}|$ tem o mesmo sinal de $\lambda_{1}$ . Portanto, $\boldsymbol{q}^{(k)}$ tende a um múltiplo não nulo de $\boldsymbol{v}_{1}$ quando $k\to\infty$ .

Observação 3.1.1 (Aproximação Inicial).

A convergência do método da potência está condicionada a escolha de uma aproximação inicial tal que (3.8) 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.

Observação 3.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,

(3.15)

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}.

(3.16)

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

Código 6: 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

Exercícios

E. 3.1.1.

Use o método da potência para computar o autovalor dominante da matriz de coeficientes do problema discreto associado ao Exercício 1.1.3. Estude sua convergência para diferentes tamanhos da matriz.

E. 3.1.2.

Use o método da potência para computar o autovalor dominante da matriz de coeficientes do problema discreto associado ao Exemplo 1.1.2. Estude sua convergência para diferentes tamanhos da matriz.

3.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}.

(3.17)

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}$		(3.18)
	$\displaystyle M_{\mu}^{-1}(\lambda_{i}-\mu)\boldsymbol{v}_{i}=\boldsymbol{v}_{i}$		(3.19)
	$\displaystyle M_{\mu}^{-1}\boldsymbol{v}_{i}=(\lambda_{i}-\mu)^{-1}\boldsymbol% {v}_{i}.$		(3.20)

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.

(3.21)

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)},$		(3.22)
	$\displaystyle\boldsymbol{q}^{(k)}=\boldsymbol{z}^{(k)}/\\|\boldsymbol{z}^{(k)}\\|,$		(3.23)
	$\displaystyle\nu^{(k)}=(\boldsymbol{q}^{(k)})^{H}A\boldsymbol{q}^{(k)},$		(3.24)

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$ .

Exercícios

E. 3.1.3.

Use o método da potência para computar diferentes autovalores da matriz de coeficientes do problema discreto associado ao Exercício 1.1.3. Estude sua convergência para diferentes tamanhos da matriz.

E. 3.1.4.

Use o método da potência para computar diferentes autovalores da matriz de coeficientes do problema discreto associado ao Exemplo 1.1.2. Verifique se há vantagem em aplicar os métodos GMRES e GC na resolução de (3.22).

3.1.3 Métodos de Deflação

Em construção

Envie seu comentário

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. Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

| | | |