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

3.2 Iteração QR

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

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 $U$ ⁵³⁵³endnote: ⁵³Uma matriz $U$ é dita unitária quando $U^{-1}=U^{H}$ . 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)}\qquad\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)}$	$\displaystyle=R^{(k)}Q^{(k)}$	(3.28)
	$\displaystyle=(Q^{(k)})^{T}(Q^{(k)}R^{(k)})Q^{(k)}$	(3.29)
	$\displaystyle=(Q^{(k)})^{T}T^{(k-1)}Q^{(k)}$	(3.30)
	$\displaystyle=(Q^{(k)})^{T}R^{(k-1)}Q^{(k-1)}Q^{(k)}$	(3.31)
	$\displaystyle=(Q^{(k)})^{T}(Q^{(k-1)})^{T}Q^{(k-1)}R^{(k-1)}Q^{(k-1)}Q^{(k)}$	(3.32)
	$\displaystyle=(Q^{(k-1)}Q^{(k)})^{T}T^{(k-2)}(Q^{(k-1)}Q^{(k)})$	(3.33)
	$\displaystyle=(Q^{(0)}\cdots Q^{(k)})^{T}A(Q^{(0)}\cdots Q^{(k)}).$	(3.34)

Observação 3.2.1 (Convergência do método QR).

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 de eficiente do método QR é chamada de iteração Hessenberg⁵⁵⁵⁵endnote: ⁵⁵Karl Adolf Hessenberg, 1904 - 1959, matemático e engenheiro 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)}$ é feito com matrizes de Householder⁵⁶⁵⁶endnote: ⁵⁶Alston Scott Householder, 1904 - 1993, matemático estadunidense. Fonte: Wikipédia. 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 autovalores).

Se $v$ é autovetor associado ao autovalor simples $\lambda$ de $A$ , então

	$\displaystyle Av$	$\displaystyle=\lambda v$		(3.38)
	$\displaystyle(Q^{(k)})^{T}AQ^{(k)}(Q^{(k)})^{T}v$	$\displaystyle\approx\lambda(Q^{(k)})^{T}v$		(3.39)

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

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

(3.40)

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

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

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!

| | | |