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. Esses algoritmos de autovalores também podem encontrar autovetores.
Dada uma matriz quadrada A n × n de números reais ou complexos, um autovalor λ e o seu autovetor generalizado associado v são um par obedecendo a relação onde v é um vetor coluna n × 1 não nulo, I é a matriz identidade n × 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, Av = λ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
Matriz normal, adjunta e transposta conjugada
A adjunta M* de uma matriz complexa M é a transposta da conjugada de M : M ∗ = M ¯ T {\displaystyle 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:
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 é.
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.
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.
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.
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 d e t ( λ I − T ) = ∏ i ( λ − T i i ) {\displaystyle \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 P2 = 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 A2 = α2I para algum α escalar. Os autovalores devem ser ±α. Os operadores de projeção 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. Assim, os autovalores podem ser encontrados usando a fórmula quadrática: Definindo g a p ( A ) = t r 2 ( A ) − 4 d e t ( A ) {\displaystyle \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 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.
Matrizes 3×3
Se A é uma matriz 3×3, então a sua equação característica pode ser expressa como: 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 q = t r ( A ) / 3 {\displaystyle \textstyle q={\rm {tr}}(A)/3} and p = t r ( ( A − q I ) 2 / 6 ) 1 / 2 {\displaystyle \textstyle p={\rm {tr}}\left((A-qI)^{2}/6\right)^{1/2}} , resulta que
