diagonalização da matriz - omitindo pequenos elementos da matriz

8

Fiquei me perguntando se existe algum teorema que me permita colocar um limite superior no erro introduzido pela omissão de pequenos elementos da matriz antes da diagonalização.

Vamos supor que temos uma matriz grande, cujos elementos da matriz variam de a . Se eu definisse todos os elementos da matriz menores que para antes de diagonalizar a matriz, qual seria o erro nos valores próprios e nos vetores próprios?10 - 15 10 - 10 01101510100

Essa implementação é dependente?

ftiaronsem
fonte
E se a matriz está dentro de epsilon de uma matriz que não é diagonalizável
k20

Respostas:

6

Existe um campo de estudo conhecido como análise de sensibilidade de valor próprio ou análise de perturbação de valor próprio que permite estimar o efeito de pequenas perturbações da matriz nos valores próprios e nos vetores próprios. A técnica básica usada para isso é diferenciar a equação da matriz de autovalores,

AX=XΛ.

Para situações em que os autovalores da matriz original são todos distintos, o documento a seguir possui uma derivação e resultados muito claros:

Mike Giles. "Uma coleção estendida de resultados de derivativos de matriz para diferenciação algorítmica de modo direto e reverso". https://people.maths.ox.ac.uk/gilesm/files/NA-08-01.pdf

Quando os autovalores não são distintos, é preciso ter mais cuidado. Veja a seguinte apresentação e artigo .

Para o caso especial de matrizes simétricas com valores próprios distintos, sujeitos a uma pequena perturbação A A + d A , os resultados são simples o suficiente para que eu os reproduza aqui. A derivada da matriz de autovalor é, d Λ = diag ( U T d A U ) , e a derivada da matriz de autovetor é, d U = U C ( d A ) , onde a matriz do coeficiente CA=UΛUTAA+dA

dΛ=diag(UTdAU),
dU=UC(dA),
Cé definido como,
C={uiTdAujλjλi,i=j0,i=j

O artigo a seguir de Overton e Womersley apresenta uma ótima análise de sensibilidade para o caso simétrico, incluindo segundas derivadas.

Overton, Michael L. e Robert S. Womersley. "Segundas derivadas para otimizar valores próprios de matrizes simétricas." Jornal SIAM sobre Análise e Aplicações de Matrizes 16.3 (1995): 697-718. http://ftp.cs.nyu.edu/cs/faculty/overton/papers/pdffiles/eighess.pdf

Nick Alger
fonte
10

Não depende da implementação, no sentido de que essa é uma operação matemática realizada em sua matriz. No entanto, é muito dependente da matriz .

A=XDX1EX

X1(A+E)X=D+X1EX.
DE κ ( X )
Eκ(X),
Eκ(X) é o número da condição da matriz de vetores próprios.

Se sua matriz é normal (ou seja, ), então é unitário e , então está tudo bem.A A t = A t A X κ ( X ) = 1AAAt=AtAXκ(X)=1

Se sua matriz não for normal, você precisará do conceito de seu pseudoespectro, definido como o conjunto Uma definição equivalente, mais fácil de calcular, é Existe um bom levantamento do pseudoespectra e suas propriedades no Pseudospectra de Matrizes de Trefethen (inclui uma bela galeria de matrizes cujos pseudoespecros são muito maiores que seus espectros: pode-se pensar que o pseudoespectro deve ser uma coleção de pequenosGanhe muitos £ ( A ) = { z | ( z I - A ) - 1£ - 1 } . £ k ( X )

Λϵ(A)={zz is an eigenvalue of A+E with Eϵ}.
Λϵ(A)={z(zIA)1ϵ1}.
ϵdiscos de tamanho único em torno dos valores próprios, mas isso realmente não está certo). Em geral, você não pode simplesmente assumir que o pseudoespectro é bem-comportado e que as perturbações são insignificantes. Você pode, no entanto, calcular e estimar o erro resultante; você também pode calcular o pseudoespectro diretamente.κ(X)

Em certo sentido, soltar pequenos elementos da matriz é bom: eles não importam e os novos resultados são tão precisos quanto o original ou importam, e os resultados originais são tão imprecisos quanto os novos resultados.

Kirill
fonte
muito obrigado pela sua resposta. a matriz em questão seria normal, o que é bom :). Você poderia elaborar um pouco mais sobre a afirmação "assumindo que a matriz X não mude muito"? Existe alguma maneira de garantir isso para matrizes normais?
ftiaronsem
@ftiaronsem Eu acho que você pode seguir os links na resposta de Nick Alger e determinar a mudança no calculando a derivada e estimando o tamanho dela. O ponto da minha resposta é realmente que, se a matriz não é conhecida como normal (sua pergunta não disse), então isso não é realmente tão simples quanto se pode imaginar. d XXdX
22414 Kirill