Matemática Numérica III

4 Autovalores e Autovetores 4.1 Método da Potência 5 Integração

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

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

(4.27)

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ção QR)}$		(4.28)
	$\displaystyle T^{(k)}=R^{(k)}Q^{(k)},$		(4.29)

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)}$		(4.30)
	$\displaystyle\text{}\quad=(Q^{(k)})^{T}(Q^{(k)}R^{(k)})Q^{(k)}$		(4.31)
	$\displaystyle\text{}\quad=(Q^{(k)})^{T}T^{(k-1)}Q^{(k)}$		(4.32)
	$\displaystyle\text{}\quad=(Q^{(k)})^{T}R^{(k-1)}Q^{(k-1)}Q^{(k)}$		(4.33)
	$\displaystyle\text{}\quad=(Q^{(k)})^{T}(Q^{(k-1)})^{T}Q^{(k-1)}R^{(k-1)}Q^{(k-% 1)}Q^{(k)}$		(4.34)
	$\displaystyle\text{}\quad=(Q^{(k-1)}Q^{(k)})^{T}T^{(k-2)}(Q^{(k-1)}Q^{(k)})$		(4.35)
	$\displaystyle\text{}\quad=(Q^{(0)}\cdots Q^{(k)})^{T}A(Q^{(0)}\cdots Q^{(k)}).$		(4.36)

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

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

(4.37)

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

(4.38)

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,

(4.39)

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 4.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.. Para mais informações, consultemos [8].

Código 16: 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 4.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}$		(4.40)
	$\displaystyle(\tilde{Q}^{(k)})^{T}A\tilde{Q}^{(k)}(\tilde{Q}^{(k)})^{T}% \boldsymbol{v}\approx\lambda(\tilde{Q}^{(k)})^{T}\boldsymbol{v}$		(4.41)

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

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

(4.42)

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

4.2.1 Iteração QR com Deslocamento

Código 17: qr_iter_shift.py

⬇

1import numpy as np

2import numpy.linalg as npla

4def qr_iter_shift(A, Q=None, maxiter=100, 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 print(f"Iteração {k+1}: {npla.norm(np.diag(T)-np.diag(T0)):.4e}")

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

13 info = 0

14 break

15 T0 = T

16 return T, info

4.2.2 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