Usuário(a):MGromov/Testes19

Em análise numérica, um dos problemas mais importantes é a concepção eficiente e estável de algoritmos para encontrar os autovalores de uma matriz, ou para um operador linear contínuo (por exemplo, os autovetores do Hamiltoniano de um determinado sistema quântico são diferentes de energia eigenstates de que o sistema e seus autovalores são os correspondentes níveis de energia). Estes algoritmos de autovalores também pode encontrar autovetores.

onde v é zero n × 1 vetor coluna, eu é o n × n a matriz identidade, k é um número inteiro positivo, e ambos λ e v podem ser complexos, mesmo quando Um é real. Quando k = 1, o vetor é chamado simplesmente de um eigenvector, e o par é chamado de eigenpair. Neste caso, a Umav = λv. Qualquer eigenvalue λ de Um tem ordinária autovetores associados a ele, para se k é o menor inteiro tal que (A - λI)^k v = 0 para uma generalizada eigenvector v, então (A - λI)^k-1 v é comum eigenvector. O valor de k pode sempre ser tomado como inferior ou igual a n. Em particular, (A - λI)ⁿ v = 0 para todos os generalizada autovetores v associado a λ.

Número de condicionamento

Qualquer problema numérico de cálculo pode ser visualizada como a avaliação de alguns função ƒ para alguns sinais de entrada x. A condição de número κ(ƒ, x) do problema é a razão entre o erro relativo na função de saída para o erro relativo na entrada, e varia de acordo com a função e a de entrada. A condição de número descreve como erro cresce durante o cálculo. Sua base 10 logaritmo diz quantos menos dígitos de precisão existir em resultado do que existia na entrada. A condição de número é um cenário de melhor caso. Ele reflete a instabilidade construído para o problema, independentemente de como ele é resolvido. Nenhum algoritmo pode nunca produzir resultados mais precisos do que o indicado pela condição de número, exceto por acaso. No entanto, um mal projetado algoritmo pode produzir significativamente piores resultados. Por exemplo, como mencionado abaixo, o problema de encontrar autovalores para o normal matrizes é sempre bem-condicionado. No entanto, o problema de encontrar as raízes de um polinômio pode ser muito mal-condicionado. Assim eigenvalue algoritmos que trabalham por encontrar as raízes do polinômio característico podem ser mal-condicionado, mesmo quando o problema não é.

Para o problema do autovalor, Bauer e Fike provaram que, se λ é um autovalor de uma matriz diagonalizável n × n  A com matriz autovetor Ve, em seguida, o erro absoluto no cálculo de λ é delimitado pelo produto de κ(V) e o erro absoluto em AUm. Como resultado, o número de condicionamento para encontrar λ é κ(λ, A) = κ(V) = ||V ||_op ||V ^-1||_op. Se AUm é 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 AUma correspondente a um autovalor λ tem sido mostrado ser inversamente proporcional à distância mínima entre λ e os outros distintos autovalores de AUma. 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 AUm com AUm - μI para alguma constante μ. O autovalor encontrado para AUm - μI deve ter μ adicionado de volta para obter um autovalor para AUm. 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. Por outro lado, 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. Desde A - λI é singular, o espaço de coluna é de menor dimensão. O valor próprio algoritmo pode, então, ser aplicada à matriz restrito. Este processo pode ser repetido até que todos os valores próprios são encontrados.

Hessenberg and Tri-diagonal matrices

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

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

Método	Aplica-se aos	Produz	De custo, sem semelhança matriz	Custo com semelhança matriz	Descrição
Pai de família, transformações	Geral	Hessenberg	2n3⁄3 + O(n2)	4n3⁄3 + O(n2)	Refletir cada coluna através de um subespaço a zero, devido a sua baixa entradas.
Rotações de Givens	Geral	Hessenberg	4n3⁄3 + O(n2)	Aplicar planar rotações de saída de zero entradas individuais. As rotações são ordenadas de forma que, mais tarde, não causa zero entradas para tornar-se diferente de zero novamente.
Arnoldi iteração	Geral	Hessenberg	Executar Gram–Schmidt orthogonalization no Krylov subspaces.
O algoritmo de Lanczos	Hermitiana	Tridiagonal	Arnoldi iteração para hermitiana matrizes, com atalhos.

Algoritmos iterativos

Algoritmos iterativos resolver o eigenvalue problema através da produção de sequências que convergem para os autovalores. Alguns algoritmos de também produzir sequências de vetores que converge para o autovetores. Mais comumente, o eigenvalue sequências são expressos como sequências de semelhante matrizes que convergem para um triangular ou em forma diagonal, permitindo que os autovalores para ser lido facilmente. O eigenvector sequências são expressas como as correspondentes matrizes de similaridade.

Method	Applies to	Produces	Cost per step	Convergence	Description
Power iteration	General	eigenpair with largest value	O(n2)	Linear	Repeatedly applies the matrix to an arbitrary starting vector and renormalizes.
Inverse iteration	General	eigenpair with value closest to μ	Linear	Power iteration for (A - μI )−1
Rayleigh quotient iteration	Hermitian	eigenpair with value closest to μ	Cubic	Power iteration for (A - μiI )−1, where μi for each iteration is the Rayleigh quotient of the previous iteration.
Preconditioned Inverse iteration or LOBPCG algorithm	Positive Definite Real Symmetric	eigenpair with value closest to μ	Inverse iteration using a preconditioner (an approximate inverse to A).
Bisection method	Real Symmetric Tridiagonal	any eigenvalue	linear	Uses the bisection method to find roots of the characteristic polynomial, supported by the Sturm sequence.
Laguerre iteration	Real Symmetric Tridiagonal	any eigenvalue	cubic	Uses Laguerre's method to find roots of the characteristic polynomial, supported by the Sturm sequence.
QR algorithm	General	all eigenvalues	O(n2)	cubic	Factors A = QR, where Q is orthogonal and R is triangular, then applies the next iteration to RQ.
		all eigenpairs	6n3 + O(n2)
Jacobi eigenvalue algorithm	Real Symmetric	all eigenvalues	O(n3)	quadratic	Uses Givens rotations to attempt clearing all off-diagonal entries. This fails, but strengthens the diagonal.
Divide-and-conquer	Hermitian Tridiagonal	all eigenvalues	O(n2)	Divides the matrix into submatrices that are diagonalized then recombined.
		all eigenpairs	(4⁄3)n3 + O(n2)
Homotopy method	Real Symmetric Tridiagonal	all eigenpairs	O(n2)	Constructs a computable homotopy path from a diagonal eigenvalue problem.
Folded spectrum method	Real Symmetric	eigenpair with value closest to μ	Preconditioned inverse iteration applied to (A - μI )2
MRRR algorithm	Real Symmetric Tridiagonal	some or all eigenpairs	O(n2)	"Multiple Relatively Robust Representations" - Performs inverse iteration on a LDLT decomposition of the shifted matrix.

Cálculo directo

Enquanto não existe um algoritmo simples para calcular diretamente autovalores para geral matrizes, existem inúmeras classes especiais de matrizes, onde autovalores pode ser calculado diretamente. Estes incluem:

Triangular matrizes

Desde o determinante de uma matriz triangular é o produto de sua diagonal entradas, se T é triangular, em seguida, $\scriptstyle \mathrm {det} \left(\lambda I-T\right)={\prod }_{i}\left(\lambda -T_{ii}\right)$. Assim, os autovalores de T são a sua diagonal entradas.

Factorable equações polinomiais

Se p é qualquer polinˆ omio e p(A) = 0, então os autovalores de Uma também satisfaz a mesma equação. Se p tem uma conhecida fatoração, então os autovalores de Uma mentira entre suas raízes.

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

Outro exemplo é o de uma matriz de Uma que satisfaz A² = α²I para algum escalar α. Os autovalores deve ser ±α. 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)$

satisfazer

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

e

${\displaystyle }$

A coluna espaços de P₊ e P_- são as eigenspaces de Um correspondente para +α e -α, respectivamente.

2×2 matrizes

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 2×2 e 3×3 matrizes 4×4 matrizes a crescente complexidade da raiz fórmulas torna esta abordagem menos atraente.

Para o 2×2 matriz

${\displaystyle }$

o polinômio característico é

${\displaystyle }$

Assim, os autovalores pode ser encontrado usando a fórmula quadrática:

${\displaystyle }$

Definição ${\displaystyle }$ para ser a distância entre os dois autovalores, é simples calcular

${\displaystyle }$

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 Cayley-Hamilton teorema. Se λ₁, λ₂ são os autovalores e, em seguida, (A - λ₁I )(A - λ₂I ) = (A - λ₂I )(A - λ₁I ) = 0, então as colunas de (A - λ₂I ) são aniquilados por (A - λ₁I ) e vice-versa. Supondo que nem a matriz é zero, as colunas de cada um deve incluir autovetores para o outro eigenvalue. (Se uma matriz é igual a zero, então A é um múltiplo de a identidade e o não-zero, o vetor é um eigenvector.)

Por exemplo, suponha que

${\displaystyle }$

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

${\displaystyle }$

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

${\displaystyle }$

Em ambas as matrizes, as colunas são múltiplos um do outro, de modo que cada coluna pode ser usado. Assim, (1, -2) pode ser tomado como um eigenvector associado com o eigenvalue -2 e (3, -1) como um eigenvector associado com o eigenvalue 3, como pode ser verificado multiplicando-os por Um.

3×3 matrizes

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

${\displaystyle }$

Esta equação pode ser resolvida usando-se os métodos de Cardano ou de Lagrange, mas um afim de alterar para Um irá simplificar a expressão consideravelmente, e levam directamente a uma trigonométricas solução. Se A = pB + qI, então A e B têm o mesmo autovetores, e β é um eigenvalue de B se, e somente se, α = pß + q é um eigenvalue de Um. Deixar ${\displaystyle }$ e ${\displaystyle }$, dá

${\displaystyle }$

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

${\displaystyle }$

Se det(B) é complexo ou superior a 2, em valor absoluto, o arco-co-seno deve ser tomado ao longo do mesmo ramo, para os três valores de k. Este problema não se levantam quando Uma é real e simétrica, resultando em um algoritmo simples:

Mais uma vez, os autovetores de A pode ser obtido por recurso ao Cayley-Hamilton teorema. Se α₁, α₂, α₃ são distintos autovalores de A, então (A - α₁I)(A - α₂I)(A - α₃I) = 0. Assim, as colunas do produto de quaisquer duas dessas matrizes irá conter uma eigenvector para o terceiro eigenvalue. No entanto, se a₃ = a₁, então (A - α₁I)²(A - α₂I) = 0 e (A - α₂I)(A - α₁I)² = 0. Assim, a generalizada eigenspace de α₁ é dividido pelas colunas de A - α₂I , enquanto a ordinária eigenspace é dividido por colunas de (A - α₁I)(A - α₂I). O processo eigenspace de α₂ é dividido por colunas de (A - α₁I)².

Por exemplo, vamos

${\displaystyle }$

A equação característica é

${\displaystyle }$

com autovalor 1 (multiplicidade 2) e -1. O cálculo,

${\displaystyle }$

${\displaystyle }$

Assim, (-4, -4, 4) é um eigenvector para -1, e (4, 2, -2) é um eigenvector 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 a (-4, -4, 4) e (4, 2, -2) , para formar uma base de autovetores generalizados de Um.Em alguns rotina de autovetores são normalizados para um, em tal caso, certifique-se de que você normalizadas pela coluna.

Veja também

• Lista de eigenvalue algoritmos

Ler mais

• Bojanczyk, Adam W.; Adam Lutoborski (Janeiro De 1991). "Cálculo dos ângulos de Euler de uma simétrico matriz 3X3". SIAM Journal on Matriz de Análise e Aplicações. 12 (1): 41-48. doi:10.1137/0612005.

[[Categoria:Álgebra linear numérica]]