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.1 Método da Potência 4 Integração

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

3.2 Iteração QR

Em revisão

A iteração QR é um método para a computação aproximada de todos os autovalores de uma dada matriz $A$ . A ideia é explorar um método iterativo para a computação da decomposição de Schur⁵²⁵²endnote: ⁵²Issai Schur, 1875 - 1941, matemático russo-alemão. Fonte: Wikipédia. de A, i.e. encontrar uma matriz unitária⁵³⁵³endnote: ⁵³Uma matriz $U$ é dita unitária quando $U^{-1}=U^{H}$ . $U$ tal que

U^{H}AU=\begin{bmatrix}\lambda_{1}&t_{12}&\cdots&t_{1n}\\ 0&\lambda_{2}&&t_{2n}\\ \vdots&&\ddots&\vdots\\ 0&\vdots&0&\lambda_{n}\end{bmatrix}

(3.25)

Assumindo $A\in\mathbb{R}^{n\times n}$ , sejam $Q^{(0)}\in\mathbb{R}^{n\times n}$ uma matriz ortogonal⁵⁴⁵⁴endnote: ⁵⁴Uma matriz $Q$ é dita ortogonal quando $Q^{T}Q=I$ . e $T^{(0)}=(Q^{(0)})^{T}AQ^{(0)}$ . A iteração $Q R$ consiste em

	$\displaystyle\text{determinar }Q^{(k)},R^{(k)}\text{ tal que}$
	$\displaystyle Q^{(k)}R^{(k)}=T^{(k-1)}\leavevmode\nobreak\ \text{(fatora\c{c}% \~{a}o QR)}$		(3.26)
	$\displaystyle T^{(k)}=R^{(k)}Q^{(k)},$		(3.27)

para $k=1,2,\ldots$ .

Ou seja, a cada iteração $k$ , computa-se a fatoração da matriz $T^{(k-1)}$ como o produto de uma matriz ortogonal $Q^{(k)}$ com uma matriz triangular superior $R^{(k)}$ . Então, computa-se uma nova aproximação $T^{(k)}$ pela multiplicação de $R^{(k)}$ por $Q^{(k)}$ . Com isso, temos

	$\displaystyle T^{(k)}=R^{(k)}Q^{(k)}$		(3.28)
	$\displaystyle\text{}\quad=(Q^{(k)})^{T}(Q^{(k)}R^{(k)})Q^{(k)}$		(3.29)
	$\displaystyle\text{}\quad=(Q^{(k)})^{T}T^{(k-1)}Q^{(k)}$		(3.30)
	$\displaystyle\text{}\quad=(Q^{(k)})^{T}R^{(k-1)}Q^{(k-1)}Q^{(k)}$		(3.31)
	$\displaystyle\text{}\quad=(Q^{(k)})^{T}(Q^{(k-1)})^{T}Q^{(k-1)}R^{(k-1)}Q^{(k-% 1)}Q^{(k)}$		(3.32)
	$\displaystyle\text{}\quad=(Q^{(k-1)}Q^{(k)})^{T}T^{(k-2)}(Q^{(k-1)}Q^{(k)})$		(3.33)
	$\displaystyle\text{}\quad=(Q^{(0)}\cdots Q^{(k)})^{T}A(Q^{(0)}\cdots Q^{(k)}).$		(3.34)

Ou seja, $T^{(k)}$ é matriz semelhante a $A$ para todo $k$ . E, portanto, tem os mesmos autovalres.

Observação 3.2.1 (Convergência).

Se $A\in\mathbb{R}^{n\times n}$ for uma matriz com autovalores tais que

|\lambda_{1}|>|\lambda_{2}|>\cdots>|\lambda_{n}|,

(3.35)

então

\lim_{k\to\infty}T^{(k)}=\begin{bmatrix}\lambda_{1}&t_{12}&\cdots&t_{1n}\\ 0&\lambda_{2}&&t_{2n}\\ \vdots&&\ddots&\vdots\\ 0&\vdots&0&\lambda_{n}\end{bmatrix}.

(3.36)

Para a taxa de convergência, temos

|t^{(k)}_{i,i-1}|=\mathcal{O}\left(\left|\frac{\lambda_{i}}{\lambda_{i-1}}% \right|^{k}\right),\quad i=2,\dotsc,n,

(3.37)

quando $k\to\infty$ .

Ainda, se $A$ for uma matriz simétrica, então $T^{(k)}$ tende a uma matriz diagonal quando $k\to\infty$ .

Observação 3.2.2.

Variantes do método QR permitem sua aplicação para matrizes mais gerais. Consulte [5].

Uma forma eficiente do método QR é chamada de iteração Hessenberg⁵⁵⁵⁵endnote: ⁵⁵Karl Adolf Hessenberg, 1904 - 1959, engenheiro e matemático alemão. Fonte: Wikipédia.-QR. Consiste em inicializar $T^{(0)}$ como uma matriz de Hessenberg superior, i.e. $t^{(0)}_{i,j}=0$ para $i>j+1$ . A computação de $T^{(0)}$ é feita com transformadas de Householder e a fatoração $Q R$ de $T^{(k)}$ utiliza de matrizes de Givens⁵⁶⁵⁶endnote: ⁵⁶James Wallace Givens Jr., 1910 - 1993, matemático estadunidense. Fonte: Wikipédia..

Código 7: Algoritmo da Iteração QR

⬇

1import numpy as np

2import numpy.linalg as npla

4def qr_iter(A, Q=None, maxiter=10, tol=1e-5):

5 Q = np.eye(A.shape[0]) if Q==None else Q

6 T0 = Q.T @ A @ Q

7 info = -1

8 for k in range(maxiter):

9 Q, R = npla.qr(T0)

10 T = R @ Q

11 if (npla.norm(T-T0) < tol):

12 info = 0

13 break

14 T0 = T

15 return T, info

Observação 3.2.3 (Computação dos Autovetores).

Vamos denotar $\tilde{Q}^{(k)}=Q^{(0)}\cdots Q^{(k)}$ . Se $\boldsymbol{v}$ é autovetor associado ao autovalor simples $\lambda$ de $A$ , então

	$\displaystyle A\boldsymbol{v}=\lambda\boldsymbol{v}$		(3.38)
	$\displaystyle(\tilde{Q}^{(k)})^{T}A\tilde{Q}^{(k)}(\tilde{Q}^{(k)})^{T}% \boldsymbol{v}\approx\lambda(\tilde{Q}^{(k)})^{T}\boldsymbol{v}$		(3.39)

Denotando, $y=(\tilde{Q}^{(k)})^{T}\boldsymbol{v}$ , temos

T^{(k)}\boldsymbol{y}=\lambda\boldsymbol{y}.

(3.40)

Com isso, podemos computar $\boldsymbol{y}$ e, então, temos $\boldsymbol{v}\approx\tilde{Q}^{(k)}\boldsymbol{y}$ .

Exercícios

E. 3.2.1.

Use a iteração QR para computar os autovalores da matriz de coeficientes do problema discreto associado ao Exercício 1.1.3.

E. 3.2.2.

Use a iteração QR para computar os autovalores da matriz de coeficientes do problema discreto associado ao Exemplo 1.1.2. Use spla.hessenberg para computar $T^{(0)}$ .

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.