Política de uso de dados

Ao navegar por este site, você concorda com a política de uso de dados.

Política de uso de dados

Ao navegar por este site, você concorda com a política de uso de dados.

| | | |

Matemática Numérica III

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

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

3.1 Método da Potência

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}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}|\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.2.(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 [Quarteroni2007a, Seção 5.3.].

Código 12: 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 LABEL:exer:pvc1d. 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 LABEL:ex:poisson. 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 LABEL:exer:pvc1d. 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 LABEL:ex:poisson. 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

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.

Matemática Numérica III

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

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

3.1 Método da Potência

Em revisão

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)

\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{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}|\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

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

(3.7)

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

(3.8)

$\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)

Observação 3.1.2.(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 [Quarteroni2007a, Seção 5.3.].

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

E. 3.1.2.

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

	$\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)

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

E. 3.1.4.

3.1.3 Métodos de Deflação

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.

Pedro H A Konzen

| | | |