Determinação de valores e vectores próprios

Vamos agora abordar ligeiramente o problema da determinação de valores e vectores próprios de uma matriz, ou seja, estaremos interessados em encontrar os valores complexos l(valores próprios) para os quais existem v não nulos (vectores próprios) tais que

A v = l v.




É bem conhecido que isto corresponde a encontrar as soluções da equação polinomial

det (A - l I) = 0,
já que p(x)=det (A - lI) define um polinómio, denominado polinómio característico.

Se se tratar de uma matriz NxN então p é um polinómio de grau N e há N raízes complexas, ou seja N valores próprios, que iremos designar l1, ..., lN. (alguns valores podem ser iguais, correspondendo a raízes múltiplas). A cada valor próprio estão associados vectores próprios que constituem um subespaço linear, designado subespaço próprio. Pode acontecer que o subespaço próprio associado a um certo valor próprio tenha dimensão superior a 1. A dimensão desse subespaço é designada multiplicidade geométrica do valor próprio, e pode ocorrer que essa multiplicidade seja menor que a multiplicidade algébrica (a multiplicidade da raiz) do valor próprio.

Iremos apenas considerar o caso mais favorável, em que as multiplicidades são iguais, e em que os vectores próprios constituem uma base do espaço. Ou seja, iremos apenas considerar o caso de matrizes diagonalizáveis, que admitem a factorização de Jordan,

A = S-1 D S,
onde S é uma matriz invertível (mudança de base) e D é uma matriz diagonal.
 

Relembramos ainda que no caso em que as matrizes são simétricas (hermitianas, em C), os seus valores próprios são números reais.
Convém ainda relembrar que o determinante da matriz A é igual ao produto dos seus valores próprios, o que reflecte bem que a invertibilidade de uma matriz não ocorre se tiver um valor próprio nulo. Outras propriedade importantes podem ser retiradas imediatamente da definição, por exemplo, os valores próprios de A-1 são os inversos de A, e os vectores próprios são iguais, porque

A v = l v   <=>   l-1v = A-1v .
No entanto, há que ter em atenção que muitas propriedades desejáveis, tal como a linearidade, não são válidas, pelo que é aconselhável rever cuidadosamente esta matéria. Por exemplo, convém salientar que uma simples troca de linhas ou colunas pode alterar os valores próprios...



Localização de valores próprios

Começamos por recordar que, como vimos que o raio espectral era menor que qualquer norma induzida, esse resultado permite imediatamente obter um majorante para o valor absoluto dos valores próprios. Mas o teorema seguinte permite uma localização mais
eficaz, através de bolas no plano complexo.

Teorema (Gerschgorin):
(i) Os valores próprios de uma matriz A estão na reunião das bolas fechadas B(akk , rk), com k=1,...,N, em que

rk =     N
S
j = 1, j ¹ i
| akj |

Ou seja, associada a cada linha da matriz temos uma bola, o seu centro é definido pelo elemento da diagonal, e o raio é a soma do valor absoluto dos restantes elementos dessa linha.
(ii) Se m bolas definidas em (i) formarem uma componente conexa, então existem m valores próprios (contando com a multiplicidade) nessa componente.
Ou seja, se m bolas se intersectarem há m valores próprios na sua reunião.
(iii) A análise feita em (i) e (ii) para linhas pode ser efectuada para colunas.

demonstração:
Apenas iremos demonstrar (i). Consideremos A v = lv, e assim

[A v]i = ai1v1+ ...+ aiNvN = l v <= ai1v1+ ...+ aiNvN   - aiiv =  (l - aii) v .
Portanto, aplicando o módulo e a desigualdade triangular, temos
|l-aii| |vi| <    N
S
j = 1,j ¹ i
|aij| |vj|

Podemos agora escolher i=k em que k é o índice tal que |vk| = ||v||¥, o significa que o primeiro termo será
| l - aii | |vi| = | l - akk | ||v||¥ e como cada |vj| no somatório é majorado por ||v||¥, podemos obter imediatamente
 

|l-akk| ||v||¥ <    N
S
j = 1, j ¹ k
|akj| ||v||¥ = rk ||v||¥

e assim como v não é nulo, temos | l - akk | < rkou seja l está na bola B(akk , rk).



Observações:
Note-se que não é a priori possível por (i) saber em que bola está um determinado valor próprio, apenas usando (ii) podemos concluir alguns critérios importantes.
(a) Se a matriz A for real, o polinómio característico também tem coeficientes reais, e por isso as suas raízes ou são reais ou são complexas conjugadas. Assim, os valores próprios de uma matriz real ou são números reais ou há complexos conjugados.
Através de (ii), sabemos que se tivermos uma bola disjunta das restantes haverá apenas um valor próprio nessa bola, logo nessa bola não poderá existir um par conjugado de valores próprios e conclui-se que o valor próprio é real.
(b) Sabendo que os valores próprios da matriz são reais (o que acontece quando é simétrica) e que a sua diagonal é estritamente dominante (por linhas ou colunas) com elementos positivos, podemos concluir que a matriz é definida positiva. Com efeito, se os elementos da diagonal são positivos, os centros das bolas estão no semieixo positivo. Neste caso, como assumimos que os valores próprios são reais, podemos localizá-los em intervalos contidos em ]0,+¥[, pois a diagonal é estritamente dominante e nunca irá conter zero.
(c) Como referido em (iii) também podemos fazer uma análise através das colunas e assim intersectar com a informação obtida pela análise das linhas.



Exemplo:

Neste caso, uma análise por linhas permite obter as bolas colocadas na primeira figura, onde se conclui a existência de um único valor próprio em B(-4,2), porque a bola é disjunta das restantes e como a matriz real, pela observação (a) esse valor próprio será real. Pela análise feita por linhas apenas podemos concluir que em B(3,4) existem 2 valores próprios.

Colocamos os pontos correspondentes aos valores próprios para evidenciar que com efeito há dois valores próprios em B(3,4) e que não estão na bola B(1,1).

Uma análise por colunas permite verificar imediatamente que -4 é um valor próprio. Com efeito, pela regra de Laplace,
o determinante det (A - l I) será dado por (- 4 - l) det [(-1,1-l), (4,3-l)],
o que implica que l = - 4 seja valor próprio,
e que os restantes valores próprios sejam dados pela simples análise da matriz constituída pelas linhas (1,-1) e (4,3).

Na segunda figura, a azul, colocamos as bolas que se obtêm pela análise por colunas.



Método das potências

Até aqui apenas vimos um critério simples para uma localização pouco precisa dos valores próprios.
Iremos agora ver o método das potências que permite obter de forma simples uma aproximação do valor próprio dominante (ou seja, aquele que tem maior módulo), por um processo iterativo, desde que seja real.
Convém referir que assumimos que a matriz A é diagonalizável e que existe um único valor próprio dominante. Iremos assim determinar uma aproximação do vector próprio associado e a partir dessa aproximação do vector próprio podemos calcular uma aproximação do valor próprio.

O método consiste simplesmente em definir um vector inicial aleatório u(0), unitário numa norma ||.||.
Iremos considerar a norma do máximo.
A partir desse vector inicial definimos novos vectores unitários,

u(k+1) = s   Au(k) 

|| Au(k) ||
em que sk é o sinal da componente com maior módulo. Estando nas condições de convergência, a sucessão irá tender para um vector próprio unitário associado ao valor próprio dominante. Tendo a aproximação u(k)  para o vector próprio podemos definir a aproximação para o valor próprio definida por
l(k+1) = [Au(k+1)]j / [u(k+1)]j
considerando uma qualquer componente j não nula. Como usamos a norma do máximo, os vectores u(k)  têm a componente de maior módulo igual a 1, pelo que é aconselhável escolher j igual ao índice m dessa componente, e assim ficamos com
l(k+1) = [Au(k+1)]m .
Observação:
Dissémos que o vector inicial é aleatório, porque existe uma probabilidade (que podemos considerar nula) de que para certos vectores iniciais o método não convirja. Isso apenas acontece quando u(0) tem componente nula segundo o vector próprio dominante, o que é altamente improvável. De qualquer forma, e como convém que o método convirja mais rapidamente é habitualmente aconselhável começar com um vector inicial que seria vector próprio para o maior elemento (em módulo) da matriz formada apenas pela diagonal. Esta questão fica mais clara com a demonstração do resultado de convergência que faremos de seguida.
 

Teorema.
Sejam l1, ..., lN os valores próprios de A ordenados da seguinte forma

|l1| > |l2| > ... > |lN|,
em que l1 é real, e sejam v1, ..., vN os respectivos vectores próprios unitários
que constituem uma base (assumimos A diagonalizável).
Se u(0) = b1 v1 + ... + bN vN , com b1¹ 0, então o método das potências converge e verifica-se
||v1 - u(k) || < C ( |l2| / |l1| )k ,
||l1 - l(k) || < C ( |l2| / |l1| )k .
dem:
Reparamos que
Aku(0)  = Ak(b1v1 + ... + bN vN ) = b1Akv1 + ... + bN AkvN =
= b1 (l1)k v1 + ... + bN (lN)k vN
e dividindo por (l1)k obtemos
Aku(0)  / (l1)k = b1 v1 b2 (l2 / l1)k v2 +... + bN (lN / l1)k vN
logo, quando k tende para infinito, como |l1| > |l2| > ... > |lN| temos
Aku(0)  / (l1)k  ® b1 v1
e de forma semelhante aplicando a norma (que é contínua)
|| Aku(0) || / |l1|k ® |b1| ||v1|| = |b1|.
Assim,
Aku(0) / || Aku(0) ||  ® (+1) v1 / ||v1|| .
Por outro lado,
u(k) = sk-1 Au(k-1) / || Au(k-1) || = sk-1 sk-2 A2u(k-2) / || A2u(k-2) ||
= ... = sk-1 ... s0 Aku(0) / || Aku(0) ||
e concluímos, que a menos de verificação de sinal, u(k) converge para v1. O sinal é ajustado pelos valores sk-1 ... s0  de forma a que tenha a componente de maior módulo igual a 1.
A verificação de que o factor de convergência é  |l2| / |l1| resulta de
Aku(0)  / (l1)k  - b1 v1 = O( (l2 / l1)k ).


Observação:
Existem outros métodos mais eficazes para a aproximação de valores próprios, dos quais o mais utilizado é o denominado método QR com deslocamento (shift), e que se baseia numa decomposição de uma matriz na forma A = QR, em que Q é uma matriz unitária e R uma matriz triangular superior.