Algoritmo de autovalor

Em análise numérica, um dos problemas mais importantes é projetar algoritmos eficientes e estáveis para encontrar os autovalor de uma matriz, ou para um operador linear contínuo (por exemplo, os autovetores do hamiltoniano de um sistema quântico particular, são os diferentes autoestados de energia de que o sistema e os seus autovalores são os níveis de energia correspondentes). Esses algoritmos de autovalores também podem encontrar autovetores.

Autovalores e autovetores

Dada uma matriz quadrada $A$ $n \times n$ de números reais ou complexos, um autovalor $λ$ e o seu autovetor generalizado associado $v$ são um par obedecendo a relação ^[1]

\left(A-\lambda I\right)^{k}{\mathbf {v} }=0,

onde $v$ é um vetor coluna $n \times 1$ não nulo, $I$ é a matriz identidade $n \times n$ , $k$ é um inteiro positivo, e ambos $λ$ e $v$ podem ser complexos mesmo quando $A$ é real. Quando $k = 1$ , o vetor é chamado simplesmente de Autovetor, e o par é chamando de auto-par. Nesse caso, $A v = λ v$ . Qualquer autovalor $λ$ de $A$ tem autovalores comuns^{[note 1]} associados a ele, pois se $k$ é o menor inteiro tal que $(A - λ I) k v = 0$ para um autovetor generalizado $v$ , então $(A - λ I) k -1 v$ é um autovetor comum. O valor $k$ sempre pode ser tomado como menor que ou igual a $n$ . Em particular, $(A - λ I) n v = 0$ para todo autovetor $v$ associado com $λ.$

Para cada autovalor $λ$ de $A$ , o núcleo $ker(A - λ I)$ consiste de todos os autovetores associados com $λ$ (junto com $0$ ), chamado de autoespaço de $λ$ , enquanto o espaço vetorial $ker((A - λ I) n)$ consiste de todos os autovetores generalizados, e é chamado de autoespaço generalizado. A multiplicidade geométrica de $λ$ é a dimensão do autoespaço. A multiplicidade algébrica de $λ$ é a dimensão do autoespaço generalizado. Esta última terminologia é justificada pela equação

p_{A}\left(z\right)={\rm {det}}\left(zI-A\right)=\prod _{i=1}^{k}(z-\lambda _{i})^{\alpha _{i}},

onde $det$ é a função determinante, $λ i$ são todos os autovalores distintos de $A$ e $α i$ são as correspondentes multiplicidades algébricas. A função $p A (z)$ é o polinômio característico de $A$ . Então a multiplicidade algébrica é a multiplicidade do autovalor como um zero do polinômio característico. Como qualquer autovetor é também um autovetor generalizado, a multiplicidade geométrica é menor ou igual à multiplicidade algébrica. As multiplicidades algébricas somam até $n$ , o grau do polinômio característico. A equação $p A (z) = 0$ é chamada de equação característica, pois suas raízes são exatamente os autovalores de $A$ . Pelo teorema de Cayley-Hamilton, $A$ obedece à mesma equação: $p A (A) = 0.$ ^{[note 2]} Como consequência, as colunas da matriz $\textstyle \prod _{i\neq j}(A-\lambda _{i}I)^{\alpha _{i}}$ devem ser ou 0 ou autovetores generalizados para o autovalor $λ j$ , já que são aniquiladas por $\textstyle (A-\lambda _{j}I)^{\alpha _{j}}.$ De fato, o espaço da coluna é generalizado no autovalor de $λ j .$

Qualquer coleção de autovetores generalizados de distintos autovalores é linearmente independente, então uma base para todo $C n$ pode ser escolhida consitindo de autovetores generalizados. Mais particularmente, essa base ${v i} n i =1$

pode ser escolhida e organizada tal que

se $v i$ e $v j$ tem o mesmo autovalor, então $v k$ também tem, para cada $k$ entre $i$ e $j$ , e
se $v i$ não é um autovetor ordinário, e se $λ i$ é o seu autovalor, então $(A - λ i I) v i = v i -1$ (em particular, $v 1$ deve ser um autovetor ordinário).

Se esses vetores base são colocados como os vetores colunas de uma matriz $V = [v 1 v 2 ... v n]$ , então $V$ pode ser usado para se converter em $A$ para sua forma normal:

V^{-1}AV={\begin{bmatrix}\lambda _{1}&\beta _{1}&0&\ldots &0\\0&\lambda _{2}&\beta _{2}&\ldots &0\\0&0&\lambda _{3}&\ldots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\ldots &\lambda _{n}\end{bmatrix}},

onde $λ i$ são os autovalores, $β i = 1$ se $(A - λ i +1) v i +1 = v i$ e $β i = 0$ do contrário.

Mais genericamente, se $W$ é qualquer matriz invertível, e $λ$ é um autovalor de $A$ com autovetores generalizados $v$ , então $(W -1 AW - λ I) k W - k v = 0$ . Assim, $λ$ é um autovalor de $W -1 AW$ com autovetor generalizado $W - k v$ . Isto é, matrizes similares possuem os mesmos autovalores.

Matriz normal, adjunta e transposta conjugada

A adjunta $M *$ de uma matriz complexa $M$ é a transposta da conjugada de $M:M^{*}={\overline {M}}^{T}$ . Uma matriz quadrada é chamada normal se ela se relaciona com sua adjunta: $A * A = AA *$ . Ela é chamada de matriz transposta conjugada se for igual à sua adjunta: $A * = A$ . Todas as matrizes transpostas conjugadas são normais. Se $A$ só tem elementos reais, então a adjunta é apenas a transposta, e $A$ é conjugada tranposta se e somente se for simétrica. Quando aplicado para vetores coluna, a adjunta pode ser usada para definir o produto interno canônico em $C n$ : $w • v = w * v$ .^{[note 3]} Matrizes normal, adjunta e transposta possuem diversas propriedades utéis:

Cada autovetor generalizado de uma matriz normal é um vetor ordinário.
Qualquer matriz normal é similar à matriz diagonal, já que sua forma normal é diagonal.
Autovetores de autovalores distintos de uma matriz normal são ortogonais.
Para qualquer matriz normal $A$ , $C n$ tem uma base ortonormal consistindo de autovetores de $A$ . A matriz correspondente dos autovetores é unitária.
Os autovalroes de uma matriz tranposta adjunta são reais, já que $({\overline {\lambda }}-\lambda )\mathbf {v} =(A^{*}-A)\mathbf {v} =(A-A)\mathbf {v} =0$ para um autovetor não nulo de $v$ .
Se $A$ for real, existe uma base ortonormal para $R n$ consistindo de autovetores de $A$ se e somente se $A$ for simétrico.

É possível para uma matriz real ou complexa ter todos os autovalores reais sem ser tranposta conjugada. Por exemplo, uma matriz triangular real tem seus autovalores em sua diagonal, mas é, no geral, não simétrica.

Número de condicionamento

Qualquer problema de cálculo numérico pode ser visto como uma análise de uma função ƒ para um valor de entrada $x$ . O número de condicionamento $κ (ƒ, x)$ do problema é a razão do erro relativo no resultado da função e do erro relativo de entrada, e varia com ambas a função e a entrada. O número de condicionamento descreve como erros crescem durante o cálculo. Seu logaritmo de base 10 diz quantos digitos a menos de precisão existem no resultado que existe do que existia na entrada. O número condicional é um melhor cenário. Ele reflete a instabilidade construída no problema, independente de como ele se resolve. Nenhum algoritmo pode produzir resultados mais precisos do que o indicado pelo número de condicionamento, exceto por sorte. No entanto, um algoritmo mal preparado pode produzir resultados significativamente piores. Por exemplo, como mencionado abaixo, o problema de encontrar autovalores para matrizes normais é sempre bem condicionado. No entanto, o problema de encontrar as raízes de um polinômio pode ser bem mal condicionado. Assim, algoritmos de autovalor que trabalham para encontrar as raízes do polinômio característico pode ser mal condicionado mesmo quando o problema não é.

Para o problema de resolver a equação linear $A v = b$ onde $A$ é invertível, o número de condicionamento $κ (A -1, b)$ é dado por $|| A || op || A -1 || op$ , onde || ||_op é a norma operacional subordinada a norma euclidiana normal em $C n$ . Como esse número é independente de $b$ e é o mesmo para $A$ e $A -1$ , é normalmente chamado de número de condicionamento $κ (A)$ da matriz $A$ . Esse valor $κ (A)$ também é o valor absoluto da razão do maior autovalor de $A$ e do menor. Se $A$ é unitária, então $|| A || op = || A -1 || op = 1$ , logo $κ (A) = 1$ . Para matrizes gerais, a norma operacional é difícil de se calcular. Por isso, outras normas matriciais são usadas normalmente para estimar o número de condicionamento.

Para o problema do autovalor, Bauer e Fike provaram que, se λ é um autovalor de uma matriz diagonalizável $n \times n$ $A$ com matriz autovetor $V$ , então, o erro absoluto no cálculo de $λ$ é delimitado pelo produto de $κ (V)$ e o erro absoluto em $A$ .^[2] Como resultado, o número de condicionamento para encontrar $λ$ é $κ (λ, A) = κ (V) = || V || op || V -1 || op$ . Se $A$ é uma matriz normal, então $V$ é unitária, e $κ (λ, A) = 1$ . Assim, o problema do autovalor para todas as matrizes normais é bem condicionado.

O número de condicionamento para o problema de encontrar o autoespaço de uma matriz normal $A$ correspondente a um autovalor $λ$ tem sido mostrado ser inversamente proporcional à distância mínima entre $λ$ e os outros distintos autovalores de $A$ .^[3] Em particular, o problema do autoespaço para matrizes normais é bem condicionado para autovalores isolados. Quando autovalores não são isolados, o melhor que se pode esperar é identificar a extensão de todos os autovetores de autovalores próximos.

Algoritmos

Qualquer polinômio mônico é o polinômio característico de sua matriz companheira. Portanto, um algoritmo geral para encontrar os autovalores também pode ser usado para encontrar as raízes de polinômios. O teorema de Abel-Ruffini mostra que qualquer algoritmo para dimensões maiores do que 4 deve ser ou infinito, ou envolver funções de maior complexidade do que operações aritméticas elementares e potências fraccionárias. Por este motivo, os algoritmos que calculam exatamente autovalores em um número finito de passos só existem para algumas classes especiais de matrizes. Para matrizes gerais, os algoritmos são iterativos, produzindo melhores soluções aproximadas com cada iteração.

Alguns algoritmos de produzir cada autovalor, outros vão produzir alguns, ou apenas um. No entanto, mesmo estas algoritmos podem ser utilizados para localizar todos os autovalores. Uma vez que um autovalor $λ$ de uma matriz $A$ foi identificado, ele pode ser usado para direcionar o algoritmo para uma solução diferente da próxima vez, ou para reduzir o problema a um que já não tem $λ$ como uma solução.

O redirecionamento é feito deslocando-se: a substituição de $A$ com $A - μ I$ para alguma constante $μ$ . O autovalor encontrado para $A - μ I$ deve ter $μ$ adicionado de volta para obter um autovalor para $A$ . Por exemplo, para o método das potências, $μ = λ$ . O método das potências encontra o maior autovalor em valor absoluto, de modo que, mesmo quando $λ$ é apenas aproximado do autovalor, é improvável que o método da potência encontre uma segunda vez. Inversamente, métodos com base em iteração inversa encontram o menor autovalor, então $μ$ é escolhido distante de $λ$ e, espera-se, mais perto de algum outro autovalor.

A redução pode ser realizada restringindo $A$ para o espaço de coluna da matriz $A - λ I$ , que $A$ transporta para si próprio. Como $A - λ I$ é singular, o espaço de coluna é de menor dimensão. O algoritmo de autovalor pode, então, ser aplicada à matriz restrita. Este processo pode ser repetido até que todos os autovalores são encontrados.

Se um algoritmo de autovalor não produz autovetores, uma prática comum é usar um algoritmo baseado em iteração inversa com μ definido para uma aproximação do autovalor. Isso irá rapidamente convergir para o autovetor dos autovalores mais próximos de $μ$ . Para pequenas matrizes, uma alternativa é olhar para o espaço de coluna do produto de $A - λ' I$ para cada um dos outros autovalores $λ'$ .

Matrizes de Hessenberg e tridiagonais

Porque os autovalores de uma matriz triangular são os seus elementos da diagonal, para matrizes gerais não há método finito como a eliminação gaussiana para converter uma matriz para a forma triangular preservando os autovalores. Mas é possível chegar a algo próximo triangular. Uma matriz de Hessenberg superior é uma matriz quadrada para o qual todas as entradas abaixo da subdiagonal são zero. Uma matriz de Hessenberg menor é aquela para o qual todas as entradas acima da superdiagonal são zero. Matrizes de Hessenberg que são ambas superiores e inferiores são tridiagonais. Matrizes de Hessenberg e tridiagonais são os pontos de partida para muitos algoritmos de autovalor porque as entradas zero reduzem a complexidade do problema. Vários métodos são comumente usados para converter uma matriz geral em uma matriz de Hessenberg com o mesmo autovalor. Se a matriz original foi simétrica ou hermitiana, então a matriz resultante será tridiagonal.

Quando apenas autovalores são necessários, não é necessário calcular a matriz de similaridade, pois a matriz transformada tem os mesmos autovalores. Se autovetores também são necessários, a matriz de similaridade pode ser necessária para transformar os autovetores da matriz de Hessenberg de volta para autovetores da matriz original.

Método	Aplica-se a	Produz	Custo, sem matriz de similaridade	Custo com matriz de similaridade	Descrição
Transformação de householder	Geral	Hessenberg	^2n³⁄₃ + O(n²)^[4]^(p474)	^4n³⁄₃ + O(n²)^[4]^(p474)	Reflete cada coluna através de um subespaço para zerar as suas entradas de baixo.
Rotações de Givens	Geral	Hessenberg	^4n³⁄₃ + O(n²)^[4]^(p470)		Aplica rotações planares para zerar entradas individuais. As rotações são ordenadas de forma que, mais tarde, não cause entradas zeradas se tornarem diferentes de zero novamente.
Iteração de Arnoldi	Geral	Hessenberg			Executa ortogonalização de Gram–Schmidt em subespaços de Krylov.
Algoritmo de Lanczos	Hermitiana	Tridiagonal			Iteração de Arnoldi para matrizes hermitianas, com atalhos.

Algoritmos iterativos

Algoritmos iterativos resolvem o problema do autovalor através da produção de sequências que convergem para os autovalores. Alguns algoritmos também produzem sequências de vetores que convergem para os autovetores. Mais comumente, as sequências de autovalores são expressas como sequências de matrizes de similaridade que convergem para uma forma triangular ou diagonal, permitindo que os autovalores sejam lidos facilmente. As sequências de autovetores são expressas como as correspondentes matrizes de similaridade.

Método	Aplica-se a	Produz	Custo por etapa	Convergência	Descrição
Método das potências	Geral	Autopar (λ,υ) associado ao maior autovalor λ	$O (n 2)$	Linear	Repetidamente aplica a matriz a um vetor inicial arbitrário e renormaliza.
Iteração inversa	Geral	Autopar (λ,υ) com o autovalor λ mais próximo de μ		Linear	Método das potências para $(A - μ I) -1$
Quociente de iteração de Rayleigh	Hermitiana	Autopar (λ,υ) com o autovalor λ mais próximo de μ		Cúbica	Método das potências para $(A - μ i I) -1,$ onde $μ i$ para cada iteração é o quociente de Rayleigh da iteração anterior.
Iteração inversa pré-condicionada^[5] ou algoritmo LOBPCG	Definida positiva Simétrica	Autopar com o valor mais próximo de μ			Iteração inversa usando um pré-condicionante (uma aproximação inversa de $A$ ).
Método da bisseção	Simétrica Tridiagonal	Qualquer autovalor		Linear	Usa o método da bisseção para encontrar as raízes do polinômio característico, apoiada pela sequência de Sturm.
Iteração de Laguerre	Simétrica Tridiagonal	Qualquer autovalor		Cúbica^[6]	Usa o método de Laguerre para encontrar as raízes do polinômio característico, apoiada pela sequência de Sturm.
Algoritmo QR	Geral	Todos os autovalores	$O (n 2)$	Cúbica	Fatora A = QR, onde Q é ortogonal e R é triangular, então aplica a próxima iteração a RQ.
Algoritmo QR	Geral	Todos os autopares	$6 n 3 + O (n 2)$	Cúbica
Algoritmo de autovalores de Jacobi	Simétrica	Todos os autovalores	$O (n 3)$	Quadrática	Usa rotações de Givens para tentar limpar todas as entradas não diagonais. Falha, mas fortalece a diagonal.
Divisão e conquista	Hermitiana Tridiagonal	Todos os autovalores	$O (n 2)$		Divide a matriz em submatrizes que são diagonalizadas e então recombinadas.
Divisão e conquista	Hermitiana Tridiagonal	Todos os autopares	$(.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}4⁄3)n3 + O(n2)$
Método da homotopia	Simétrica Tridiagonal	Todos os autopares	$O (n 2) [7]$		Constrói um caminho homotópico computacional a partir de um problema de autovalor diagonal.
Método do espectro dobrado	Simétrica	Autopar com o valor mais próximo de μ			Iteração inversa pré-condicionada aplicada a $(A - μ I) 2$
Algoritmo MRRR^[8]	Simétrica Tridiagonal	Alguns ou todos os autopares	$O (n 2)$		"Múltiplas representações relativamente robustas" - Realiza uma iteração inversa em uma decomposição LDL da matriz deslocada.

Cálculo direto

Apesar de não existir um algoritmo simples para calcular diretamente autovalores para matrizes gerais, existem inúmeras classes especiais de matrizes nas quais os autovalores podem ser calculados diretamente. Estas incluem:

Matrizes triangulares

Como o determinante de uma matriz triangular é o produto de sua entradas diagonais, se T é triangular, então $\scriptstyle \mathrm {det} \left(\lambda I-T\right)={\prod }_{i}\left(\lambda -T_{ii}\right)$ . Assim, os autovalores de T são as suas entradas diagonais.

Equações polinomiais fatoráveis

Se $p$ é qualquer polinômio e $p (A) = 0,$ então os autovalores de $A$ também satisfazem a mesma equação. Se $p$ possui uma fatoração conhecida, então os autovalores de $A$ estão entre suas raízes.

Por exemplo, uma projeção é uma matriz quadrada $P$ satisfazendo $P 2 = P$ . As raízes da correspondente equação polinomial escalar, $λ 2 = λ$ , são 0 e 1. Assim, qualquer projeção tem 0 e 1 como seus autovalores. A multiplicidade de 0 como um autovalor é a nulidade de $P$ , enquanto a multiplicidade de 1 é a posição de $P$ .

Outro exemplo é o de uma matriz $A$ que satisfaça $A 2 = α 2 I$ para algum $α$ escalar. Os autovalores devem ser $\pmα$ . Os operadores de projeção

P_{+}={\frac {1}{2}}\left(I+{\frac {A}{\alpha }}\right)

P_{-}={\frac {1}{2}}\left(I-{\frac {A}{\alpha }}\right)

satisfazem

AP_{+}=\alpha P_{+}\quad AP_{-}=-\alpha P_{-}

e

P_{+}P_{+}=P_{+}\quad P_{-}P_{-}=P_{-}\quad P_{+}P_{-}=P_{-}P_{+}=0.

Os espaços coluna de $P +$ e $P -$ são os autoespaços de $A$ correspondentes a $+α$ e $-α$ , respectivamente.

Matrizes 2×2

Para dimensões de 2 a 4, fórmulas envolvendo radicais existem que podem ser usadas para encontrar os autovalores. Enquanto uma prática comum para matrizes 2×2 e 3×3, para matrizes 4×4 a complexidade crescente da raiz das fórmulas torna esta abordagem menos atraente.

Para a matriz 2×2

A={\begin{bmatrix}a&b\\c&d\end{bmatrix}},

o polinômio característico é

{\rm {det}}{\begin{bmatrix}\lambda -a&-b\\-c&\lambda -d\end{bmatrix}}=\lambda ^{2}\,-\,\left(a+d\right)\lambda \,+\,\left(ad-bc\right)=\lambda ^{2}\,-\,\lambda \,{\rm {tr}}(A)\,+\,{\rm {det}}(A).

Assim, os autovalores podem ser encontrados usando a fórmula quadrática:

\lambda ={\frac {{\rm {tr}}(A)\pm {\sqrt {{\rm {tr}}^{2}(A)-4{\rm {det}}(A)}}}{2}}.

Definindo $\textstyle {\rm {gap}}\left(A\right)={\sqrt {{\rm {tr}}^{2}(A)-4{\rm {det}}(A)}}$ como sendo a distância entre os dois autovalores, é simples calcular

{\frac {\partial \lambda }{\partial a}}={\frac {1}{2}}\left(1\pm {\frac {a-d}{{\rm {gap}}(A)}}\right),\qquad {\frac {\partial \lambda }{\partial b}}={\frac {\pm c}{{\rm {gap}}(A)}}

com fórmulas semelhantes para $c$ e $d$ . A partir disso, segue-se que o cálculo é bem condicionado se os autovalores são isolados.

Autovetores podem ser encontrados através da exploração teorema de Cayley-Hamilton. Se $λ 1, λ 2$ são os autovalores, então $(A - λ 1 I)(A - λ 2 I) = (A - λ 2 I)(A - λ 1 I) = 0$ , então as colunas de $(A - λ 2 I)$ são aniquiladas por $(A - λ 1 I)$ e vice-versa. Supondo que nenhuma matriz é zero, as colunas de cada uma devem incluir autovetores para o autovetor do outro. (Se qualquer matriz é igual a zero, então $A$ é um múltiplo da identidade e qualquer vetor não-nulo é um autovetor.)

Por exemplo, suponha que

A={\begin{bmatrix}4&3\\-2&-3\end{bmatrix}},

então $tr(A) = 4 - 3 = 1$ e $det(A) = 4(-3) - 3(-2) = -6$ , então a equação característica é

0=\lambda ^{2}-\lambda -6=(\lambda -3)(\lambda +2),

e os autovalores são 3 e -2. Agora,

A-3I={\begin{bmatrix}1&3\\-2&-6\end{bmatrix}},\qquad A+2I={\begin{bmatrix}6&3\\-2&-1\end{bmatrix}}.

Em ambas as matrizes, as colunas são múltiplas uma da outra, de modo que qualquer coluna pode ser usada. Assim, $(1, -2)$ pode ser tomado como um autovetor associado com o autovalor -2, e $(3, -1)$ omo um autovetor associado com o autovalor 3, como pode ser verificado multiplicando-os por $A$ .

Matrizes 3×3

Se $A$ é uma matriz 3×3, então a sua equação característica pode ser expressa como:

{\rm {det}}\left(\alpha I-A\right)=\alpha ^{3}-\alpha ^{2}{\rm {tr}}(A)-\alpha {\frac {1}{2}}\left({\rm {tr}}(A^{2})-{\rm {tr}}^{2}(A)\right)-{\rm {det}}(A)=0.

Um Se A = pB + qI, então Ae B têm o mesmo autovetores, e β é um eigenvalue de B se, e somente se, α = pß + q é um eigenvalue de Um. Deixar e , dá

Esta equação pode ser resolvida usando-se os métodos de Cardano ou de Lagrange, mas uma mudança afim para $A$ irá simplificar a expressão consideravelmente, e levam diretamente a uma solução trigonométrica. Se $A = pB + qI$ , então $A$ e $B$ têm o mesmo autovetores, e $β$ é um autovalor de $B$ se, e somente se, $α = pβ + q$ é um autovalor de $A$ . Sendo $\textstyle q={\rm {tr}}(A)/3$ and $\textstyle p={\rm {tr}}\left((A-qI)^{2}/6\right)^{1/2}$ , resulta que

{\rm {det}}\left(\beta I-B\right)=\beta ^{3}-3\beta -{\rm {det}}(B)=0.

A substituição $β = 2cos θ$ e alguma simplificação usando a identidade $cos 3 θ = 4cos 3 θ - 3cos θ$ reduzem a equação a $cos 3 θ = det(B) / 2$ . Assim,

\beta =2{\rm {cos}}\left({\frac {1}{3}}{\rm {arccos}}\left({\rm {det}}(B)/2\right)+{\frac {2k\pi }{3}}\right),\quad k=0,1,2.

Se $det(B)$ é complexo ou superior a 2, em valor absoluto, o arco cosseno deve ser tomado ao longo do mesmo ramo, para os três valores de $k$ . Este problema não surgem quando $A$ é real e simétrica, resultando em um algoritmo simples:^[9]

% Dada uma matriz 3x3 A real e simétrica, calcule os autovalores

p1 = A(1,2)^2 + A(1,3)^2 + A(2,3)^2
if (p1 == 0)
   % A é diagonal.
   eig1 = A(1,1)
   eig2 = A(2,2)
   eig3 = A(3,3)
else
   q = trace(A)/3
   p2 = (A(1,1) - q)^2 + (A(2,2) - q)^2 + (A(3,3) - q)^2 + 2 * p1
   p = sqrt(p2 / 6)
   B = (1 / p) * (A - q * I)       % I é a matriz identidade
   r = det(B) / 2

   % Em artimética exata para uma matriz simétrica  -1 <= r <= 1
   % mas um erro computacional pode deixar ligeiramente fora dessa faixa.
   if (r <= -1)
      phi = pi / 3
   elseif (r >= 1)
      phi = 0
   else
      phi = acos(r) / 3
   end

   % os autovalores satisfazem eig3 <= eig2 <= eig1
   eig1 = q + 2 * p * cos(phi)
   eig3 = q + 2 * p * cos(phi + (2*pi/3))
   eig2 = 3 * q - eig1 - eig3     % já que trace(A) = eig1 + eig2 + eig3
end

Mais uma vez, os autovetores de $A$ podem ser obtidos recorrendo-se ao teorema de Cayley-Hamilton. Se $α 1, α 2, α 3$ são autovalores distintos de $A$ , então $(A - α 1 I)(A - α 2 I)(A - α 3 I) = 0$ . Assim, as colunas do produto de quaisquer duas dessas matrizes irá conter um autovetor para o terceiro autovalor. No entanto, se $a 3 = a 1$ , então $(A - α 1 I) 2 (A - α 2 I) = 0$ e $(A - α 2 I)(A - α 1 I) 2 = 0$ . Assim, o autoespaço generalizado de $α 1$ é dividido pelas colunas de $A - α 2 I$ enquanto o autoespaço ordinário é dividido por colunas de $(A - α 1 I)(A - α 2 I)$ . O autoespaço ordinário de $α 2$ é dividido pelas colunas de $(A - α 1 I) 2$ .

Por exemplo, seja

A={\begin{bmatrix}3&2&6\\2&2&5\\-2&-1&-4\end{bmatrix}}.

A equação característica é

0=\lambda ^{3}-\lambda ^{2}-\lambda +1=(\lambda -1)^{2}(\lambda +1),

com autovalores 1 (de multiplicidade 2) e -1. Calculando,

A-I={\begin{bmatrix}2&2&6\\2&1&5\\-2&-1&-5\end{bmatrix}},\qquad A+I={\begin{bmatrix}4&2&6\\2&3&5\\-2&-1&-3\end{bmatrix}}

e

(A-I)^{2}={\begin{bmatrix}-4&0&-8\\-4&0&-8\\4&0&8\end{bmatrix}},\qquad (A-I)(A+I)={\begin{bmatrix}0&4&4\\0&2&2\\0&-2&-2\end{bmatrix}}

Assim, $(-4, -4, 4)$ é um autovetor para -1, e $(4, 2, -2)$ é um autovetor para 1. $(2, 3, -1)$ e $(6, 5, -3)$ são ambos autovetores generalizados associados a 1, qualquer um dos quais poderia ser combinada com $(-4, -4, 4)$ e $(4, 2, -2)$ para formar uma base de autovetores generalizados de $A$ . Em algumas rotinas, autovetores são normalizados para um, nesses casos, certifique-se de que você normalizou pela coluna.

Veja também

Notas

↑ O termo "comum" é usado aqui apenas para enfatizar a distinção entre "autovetor" e "autovetor generalizado".
↑ where the constant term is multiplied by the identity matrix $I$ .
↑ This ordering of the inner product (with the conjugate-linear position on the left), is preferred by physicists. Algebraists often place the conjugate-linear position on the right: $w • v = v * w$ .

Referências

↑ Axler, Sheldon (1995), «Down with Determinants!» (PDF), American Mathematical Monthly, 102: 139–154, doi:10.2307/2975348
↑ F. L. Bauer; C. T. Fike (1960), «Norms and exclusion theorems», Numer. Math., 2: 137–141, doi:10.1007/bf01386217
↑ S.C. Eisenstat; I.C.F. Ipsen (1998), «Relative Perturbation Results for Eigenvalues and Eigenvectors of Diagonalisable Matrices», BIT, 38 (3): 502–9, doi:10.1007/bf02510256
↑ ^a ^b ^c Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1992). Numerical Recipes in C 2nd ed. [S.l.]: Cambridge University Press. ISBN 0-521-43108-5
↑ Neymeyr, K. (2006), «A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases.», Linear Algebra Appl., 415 (1): 114–139, doi:10.1016/j.laa.2005.06.022
↑ Li, T. Y.; Zeng, Zhonggang (1992), «Laguerre's Iteration In Solving The Symmetric Tridiagonal Eigenproblem - Revisited», SIAM Journal on Scientific Computing
↑ Chu, Moody T. (1988), «A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems», Linear Algebra Appl., 105: 225–236, doi:10.1016/0024-3795(88)90015-8
↑ Dhillon, Inderjit S.; Parlett, Beresford N.; Vömel, Christof (2006), «The Design and Implementation of the MRRR Algorithm», ACM Transactions on Mathematical Software, 32 (4): 533–560, doi:10.1145/1186785.1186788
↑ Smith, Oliver K. (abril de 1961), «Eigenvalues of a symmetric 3 × 3 matrix.», Communications of the ACM, 4 (4): 168, doi:10.1145/355578.366316

Leitura adicional

Bojanczyk, Adam W.; Adam Lutoborski (janeiro de 1991). «Computation of the Euler angles of a symmetric 3X3 matrix». SIAM Journal on Matrix Analysis and Applications. 12 (1): 41–48. doi:10.1137/0612005

[2] O termo "comum" é usado aqui apenas para enfatizar a distinção entre "autovetor" e "autovetor generalizado".

[3] where the constant term is multiplied by the identity matrix $I$ .

[4] This ordering of the inner product (with the conjugate-linear position on the left), is preferred by physicists. Algebraists often place the conjugate-linear position on the right: $w • v = v * w$ .

[Axler-1] Axler, Sheldon (1995), «Down with Determinants!» (PDF), American Mathematical Monthly, 102: 139–154, doi:10.2307/2975348

[5] F. L. Bauer; C. T. Fike (1960), «Norms and exclusion theorems», Numer. Math., 2: 137–141, doi:10.1007/bf01386217

[6] S.C. Eisenstat; I.C.F. Ipsen (1998), «Relative Perturbation Results for Eigenvalues and Eigenvectors of Diagonalisable Matrices», BIT, 38 (3): 502–9, doi:10.1007/bf02510256

[NumericalRecipes-7] Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (1992). Numerical Recipes in C 2nd ed. [S.l.]: Cambridge University Press. ISBN 0-521-43108-5

[8] Neymeyr, K. (2006), «A geometric theory for preconditioned inverse iteration IV: On the fastest convergence cases.», Linear Algebra Appl., 415 (1): 114–139, doi:10.1016/j.laa.2005.06.022

[9] Li, T. Y.; Zeng, Zhonggang (1992), «Laguerre's Iteration In Solving The Symmetric Tridiagonal Eigenproblem - Revisited», SIAM Journal on Scientific Computing

[10] Chu, Moody T. (1988), «A Note on the Homotopy Method for Linear Algebraic Eigenvalue Problems», Linear Algebra Appl., 105: 225–236, doi:10.1016/0024-3795(88)90015-8

[11] Dhillon, Inderjit S.; Parlett, Beresford N.; Vömel, Christof (2006), «The Design and Implementation of the MRRR Algorithm», ACM Transactions on Mathematical Software, 32 (4): 533–560, doi:10.1145/1186785.1186788

[Smith-12] Smith, Oliver K. (abril de 1961), «Eigenvalues of a symmetric 3 × 3 matrix.», Communications of the ACM, 4 (4): 168, doi:10.1145/355578.366316

[1]

[note 1]

[note 2]

[note 3]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]