Autovalor Dominante

Autovalor Dominante

Método de Potenciação

Devido a vasta aplicação de matrizes em vários campos da matemática, consideramos a importância do estudo dos métodos computacionais para determinar os autovalores e autovetores de matrizes. Em particular, exploraremos o método de potenciação, que é um procedimento iterativo para produzir uma sequência de escalares que converge para o autovalor da matriz.

1. AUTO VALOR E AUTO VETOR DE UMA MATRIZ

Os autovalores de uma matriz $A$ são precisamente as soluções $\lambda$ da equação:

$$det(A-\lambda I)$$

Quando desenvolvemos essa equação, obtemos um polinômio em $\lambda$, chamado polinômio característico, de $A$. Por exemplo, se $\begin{bmatrix}a & b \\ c & d \end{bmatrix}$, seu polinômio característico é:

$$det(A- \lambda I)=\begin{bmatrix} a-\lambda & b \\ c & d-\lambda \end{bmatrix}=$$

$$=(a-\lambda)(b-\lambda)-bc=$$

$$=\lambda^{2}-(a+d)\lambda+(ad-bc)$$

 

Dessa forma, se a matriz for $n\times n$, o seu polinômio característico será de grau $n$. E, pelo Teorema Fundamental da Álgebra, a matriz terá no máximo $n$ autovalores distintos.

Já o autovetor de uma matriz é um vetor $x$, não nulo, tal que $Ax=\lambda x$, ou seja, podemos encontrar o autovetor resolvendo o sistema $A-\lambda I=0$.

EXEMPLO: Vamos mostrar que $\lambda=5$ é um autovalor de $A=\begin{bmatrix}a&2\\4&3\end{bmatrix}$, e determinar todos os autovetores correspondentes a esse autovalor.

$$det(A-\lambda I)=\begin{vmatrix}1-\lambda & 2 \\ 4 & 3-\lambda\end{vmatrix}$$

Portanto, $\lambda=-1$ e $\lambda=5$ são todos os autovalores da matriz $A$. Podemos encontrar os autovetores resolvendo o sistema $(A-5I)x=0$ para o vetor $x\begin{bmatrix} x_{1}\\x_{2}\end{bmatrix}$, ou seja:

$$(A-5I)x=\begin{bmatrix}-4&2\\-4&-2\end{bmatrix}\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}=\begin{bmatrix}0\\0\end{bmatrix}$$

Resolvendo o sistema acima, temos que $x_{2}=2x_{1}$. E, portanto, temos que $x=\begin{bmatrix} x_{1}\\2x_{1}\end{bmatrix}$ é um autovetor correspondente ao autovalor $\lambda=5$. Ou seja, todos os seus autovetores são múltiplos não nulos de $\begin{bmatrix}1\\2\end{bmatrix}$.

AUTO VALOR DOMINANTE

Como foi visto, os autovalores de uma matriz são as raízes de seu polinômio característico. Assim, o autovalor dominante é como chamamos o autovalor com maior valor absoluto.

O processo de calcular os autovalores nem sempre é simples. Por exemplo, o cálculo de determinantes em matrizes de ordens muito grandes pode ser um processo muito demorado. Outra situação é que não existem fórmulas simples para calcular um polinômio característico de ordens maiores do que quatro. Portanto, uma boa alternativa é encontrar aproximações para o autovalor.

MÉTODO DE POTENCIAÇÃO

O Método de potenciação é uma boa ferramenta para calcular o autovalor dominante de uma matriz, pois este consiste em um método iterativo simples que gera uma sequência de escalares que converge para o autovalor da matriz.

A ideia é considerar uma matriz $A_{n\times n}$ com autovalor dominante $\lambda_{1}$. Lembrando ainda que $Av=\lambda v$. E sejam $v_{1}, v_{2},…, v_{n}$, os autovetores correspondentes aos autovalores da matriz $A_{n\times n}$. E, como $det(A-\lambda I)=0$, os autovetores devem ser linearmente independentes. Assim, podemos escrever um vetor $Z_{0}$ como combinação linear dos autovetores de $A$:

$$Z_{0}=a_{1}v_{1}+a_{2}v_{2}+…+a_{n}v_{n}$$

Definimos agora $Z_{k-1}=AZ_{k}$, para $k=1, 2, …$

Dessa forma temos:

$$Z_{1}=AZ_{0}=Aa_{1}v_{1}+Aa_{2}+...+Aa_{n}v_{n}$$

$$=a_{1}Av_{}1+a_{2}Av_{2}+…+a_{n}Av_{n}$$

$$=a_{1}\lambda_{1}v_{1}+a_{2}\lambda_{2}v_{2}+…+a_{n}\lambda_{n}v_{n}$$

Considerando que:

$$v_{1}=Av_{0}$$

$$v_{2}=Av_{1}=A(Av_{0})=A^{2}v_{0}$$

$$v_{3}=Av_{2}=A(A^{2}v_{0})=A^{3}v_{0}$$

$$…$$

$$v_{k}=A^{k}v_{0}$$

Então:

$$Z_{k}=A^{k}x_{0}$$

$$=a_{1}\lambda^{k}_{1}v_{1}+a_{2}\lambda^{k}_{2}v_{2}+…+a_{n}\lambda^{k}_{n}v_{n}$$

Evidenciando $\lambda_{1}{k}$ temos:

$$Z_{k}=\lambda_{1}(a_{1}v_{1}+a_{2}(\frac{\lambda_{2}}{\lambda_{1}})^{k}v_{2}+…+a_{n}(\frac{\lambda_{n}}{\lambda_{n}})^{k}v_{n})$$

Se considerarmos que $\lambda_{1}$ é o autovalor dominante, e que $\lambda \neq 0$, temos que: $\frac{\lambda_{i}}{\lambda_{1}}<1$, para $i=1, 2, 3, …$. Portanto:

$$(\frac{\lambda_{2}}{\lambda_{1}})^{k}, (\frac{\lambda_{3}}{\lambda_{1}})^{k}, … , (\frac{\lambda_{n}}{\lambda_{1}})^{k}$$

E essa é uma sequência que tende a zero quando $k\to\infty$. Logo, para $k \to infty$ temos que:

$$Z_{k}=A^{k}v_{0}\to \lambda_{1}^{k}a_{1}v_{1}$$

Onde $v_{1}$ é o auto vetor associado ao auto valor dominante $\lambda_{1}$, e $a_{1}$ é o coeficiente de $v$ na representação de $Z_{0}$ como combinação linear dos autovalores linearmente independentes de $A$.

Agora, nosso trabalho é explicitar $\lambda_{1}$. E, para simplificar a notação, chamaremos o autovalor dominante $\lambda_{1}$ apenas de $\lambda$, e o coeficiente $a_{1}$ apenas de $a$. Para este cálculo, utilizaremos os argumentos acima e ainda faremos uso de uma ferramenta chamada quociente de Rayleight, que é uma sequencia definida assim:

$$R^{(k)}=\frac{_{}^{t}\textrm{Z}_{k}AZ_{k}}{_{}^{t}\textrm{Z}_{k}Z_{k}}$$

Podemos verificar que $R^{(k)}\to \lambda$ quando $k \to \infty$. Deste modo, usando os fatos verificados anteriormente tem-se:

$$R^{(k)}=\frac{_{}^{t}\textrm{v}a\lambda^{k}A\lambda^{k}av}{_{}^{t}\textrm{v}a\lambda^{k}\lambda^{k}av}=\frac{_{}^{t}\textrm{v}a^{2}(\lambda^{k})^{2}A\lambda^{k}av}{_{}^{t}\textrm{v}a\lambda^{k}\lambda^{k}av}=\lambda$$

Desta maneira, temos que $\lambda=\frac{_{}^{t}\textrm{Z}_{k}AZ_{k}}{_{}^{t}\textrm{Z}_{k}Z_{k}}$. E, a seguir, temos que definir um vetor $Y_{k}$, para normalizar o vetor $Z_{k}$ da seguinte forma:

$$Y_{k}=\frac{Z_{k}}{||Z_{k}||^{2}}$$

para $k= 0, 1, 2, …$

Como $||Z_{k}||^{2}=1$ e $Z_{k}AZ_{k}=AZ_{k+1}$. Logo, usando o resultado anterior, temos que o quociente de Rayleigh pode ser reescrito assim:

$$\lambda_{k}=Y_{k}Z_{k+1}$$

Com isso, temos um método para calcular o autovalor dominante de uma matriz qualquer. Ou seja, devemos calcular os elementos da sequência $(\lambda_{k})$ até que $\frac{\lambda_{k+1}-\lambda_{k}}{\lambda_{k+1}}<\varepsilon$ , para todo $\varepsilon>0$.

O método se resume nos seguintes passos: 

	Dada uma Matriz real $A_{n\times n}$
1	Escolher um vetor coluna $n\times 1$ em $R^{n}$
2	Calcular $Z_{k+1}=AZ_{k}$, $k=0, 1, 2, …$
3	Calcular $Y_{k}=\frac{Z_{k}}{||Z_{k}||^{2}}$, $k=0, 1, 2, …$
4	Calcular a sequência $\lambda_{k}=_{}^{t}\textrm{Y}_{k}Z_{k+1}$, $k=0, 1, 2, …$
5	Terminar o processo quando $\frac{\lambda_{k+1}-\lambda_{k}}{\lambda_{k+1}}<\varepsilon$, $\forall \varepsilon>0$

EXEMPLO:

Seja $A=\begin{bmatrix}1&1\\2&0\end{bmatrix}$ e $\varepsilon=0,005$, encontre o auto valor dominante pelo método de potenciação.

Escolhendo $Z_{0}=\begin{bmatrix}1\\0\end{bmatrix}$ e normalizando temos $Y_{0}=\begin{bmatrix}1&0\end{bmatrix}$. Desta forma temos:

$$Z_{1}=AZ_{0}=\begin{bmatrix}1 & 0\\ 2& 0 \end{bmatrix}\begin{bmatrix}1\\0\end{bmatrix}$$

e, portanto, $Z_{1}=\begin{bmatrix}1\\2\end{bmatrix}$, e:

$$\lambda_{0}=Z_{1}._{}^{t}\textrm{Y}_{0}=\begin{bmatrix}1\\0\end{bmatrix}\begin{bmatrix}1&0\end{bmatrix}=1$$

Continuando o algoritmo:

$$Z_{2}=AZ_{1}=\begin{bmatrix}1&1\\0&2\end{bmatrix}\begin{bmatrix}1\\2\end{bmatrix}$$

e, portanto, $Z_{2}=\begin{bmatrix}3\\4 \end{bmatrix}$.

Devemos normalizar $Z_{1}$ para encontrar $T_{1}$, ou seja: $Y_{1}=\begin{bmatrix}\frac{1}{5}\\ \frac{2}{5}\end{bmatrix}$, e:

$$\lambda_{1}=Z_{2}._{}^{t}\textrm{Y}_{1}=\begin{bmatrix}3\\4\end{bmatrix}\begin{bmatrix}\frac{1}{5} & \frac{2}{5} \end{bmatrix}=2,2$$

Fazendo o teste de convergência, temos $\frac{2,2-1}{2,2}=0,545>0,005=\varepsilon$. Continuando o algoritmo, temos que temos os dados na seguinte tabela:

$k$	$Z_{k}$	$_{}^{t}\textrm{Y}_{k}$	$\lambda_{k}$	$\frac{\lambda_{k+1}-\lambda_{k}}{\lambda_{k+1}}$
	$\begin{bmatrix}1\\0\end{bmatrix}$	$\begin{bmatrix}1\\0 \end{bmatrix}$	1
	$\begin{bmatrix}1\\2\end{bmatrix}$	$\frac{1}{5}\begin{bmatrix}1&2\end{bmatrix}$	2,2	0,545
	$\begin{bmatrix}3\\4\end{bmatrix}$	$\frac{1}{13}\begin{bmatrix}3&2\end{bmatrix}$	2,076	0,059
	$\begin{bmatrix}5\\6\end{bmatrix}$	$\frac{1}{61}\begin{bmatrix}5&6\end{bmatrix}$	1,885	0,101
	$\begin{bmatrix}11\\10\end{bmatrix}$	$\frac{1}{221}\begin{bmatrix}11&10\end{bmatrix}$	2,040	0,075
	$\begin{bmatrix}21\\22\end{bmatrix}$	$\frac{1}{925}\begin{bmatrix}21&22\end{bmatrix}$	1,975	0,032
	$\begin{bmatrix}85\\86\end{bmatrix}$	$\frac{1}{3613}\begin{bmatrix}43&42\end{bmatrix}$	2,011	0,017
	$\begin{bmatrix}85\\86\end{bmatrix}$	$\frac{1}{14621}\begin{bmatrix}85&86\end{bmatrix}$	1,994	0,008
	$\begin{bmatrix}171\\170\end{bmatrix}$	$\frac{1}{58141}\begin{bmatrix}171&170\end{bmatrix}$	1,997	0,001

 

Fazendo o teste de convergência para a ultima iteração temos $\frac{1,997-1,994}{1,997}=0,001<0,005=\varepsilon$. Assim, temos que o autovalor dominante se aproxima de $2$ a medida que $k\to \infty$. Ou que para um erro $\varepsilon$ temos que $\lambda=1,997$.

A figura abaixo, mostra o que está acontecendo geometricamente, alguns dos $Z_{k}$ do processo de iteração estão sendo mostrados juntamente com as direções que determinam. Aparentemente, os vetores $Z_{k}$ estão convergindo para a reta que representa o autovetor dominante.

CONCLUSÃO

Considerando o estudo de matrizes e seus autovalores, exploramos o método de potenciação, que é um procedimento iterativo para produzir uma sequência que converge para o autovalor dominante da matriz. Este método mostra-se bastante eficaz em situações em que é muito difícil calcular os autovalores analiticamente.

REFERÊNCIAS

• SHOKRANIAN, Salahoddin. Tópicos em Métodos Computacionais. Rio de Janeiro: Editora Ciência Moderna, 2009.

• POOLE, David. Álgebra linear. Rio de Janeiro: Pioneira Thomson Learning, 2004.

• Métodos Iterativos para o Cálculo de Autovalores. Disponível em: http://www.mat.puc-rio.br/cursos/MAT1202/files/teoria/MetPot.pdf. Acesso: Dezembro de 2016.

   

  QUER CITAR ESTE ARTIGO NO SEU TRABALHO? VOCÊ PODE USAR A SEGUINTE REFERÊNCIA:

  
  

  CASTRO, Mendelssohn Aguiar de Lima. Auto Valor Dominante: Método de Potenciação. Blog Matdriver: Matemática e Tecnologia. Brasília, mar. 2021. Disponível em: https://matdriver.blogspot.com/2021/04/autovalordominante-metodode-potenciacao.html. Acessado em________.