Encontrando o

Dada uma matriz grande $A$ com valores próprios $\sigma_1\ge \sigma_2 \ge \dotsc$ , quero determinar apenas um subconjunto desses valores, digamos $\sigma_5,\sigma_8$ e $\sigma_{19}$ . Existe um algoritmo que pode fazer isso ou encontrar os 19 autovalores superiores é o melhor que pode ser feito?

eigenvalues svd dexter04
fonte

Sua matriz possui propriedades especiais? Você conhece aproximadamente os valores para

σ_{5}

$\sigma_5$

σ_{8}

$\sigma_8$

σ_{19}

$\sigma_{19}$

nicoguaro

Não. Mas fique à vontade para me informar se houver algum resultado assumindo propriedades especiais.

dexter04

Relacionado: stackoverflow.com/questions/12167654/… talvez você possa determinar o método nos bastidores lá.

Carlosvalderrama 20/03/19

Eu acho que algo na direção do subespaço de Krylov, Arnoldi ou Lanczos é necessário.

Carlosvalderrama 20/03/19

Se sua matriz é hermitiana, há garantia de que você tenha seu conjunto de valores próprios ordenados, pois todos eles são reais. Além disso, se você conhecer aproximadamente os valores, poderá tentar usar o método shift-invert. No final do dia, acho que pode ser mais fácil encontrar os primeiros

autovalores.

n

$n$

nicoguaro

Respostas:

Não, não há nada, até onde eu saiba, a menos que você saiba aproximadamente a localização desses autovalores. Quanto aos métodos que podem calcular um subconjunto do espectro de uma matriz, conheço apenas os métodos que podem produzir:

valores próprios dos "extremos do espectro", por exemplo, aqueles com o maior valor absoluto ou com a parte real / imaginária mais negativa. Por exemplo, iteração Arnoldi / subespaço (deslocada adequadamente).
autovalores mais próximos de um determinado ponto no plano complexo, por exemplo, os menores em módulo (mais próximos de zero). Por exemplo, Arnoldi de mudança e inversão (racional) ou a iteração inversa do poder.
autovalores em uma região específica do plano, por exemplo $[-1,1] \times [-1,1]$ . Acho que os métodos do tipo FEAST fazem isso, mas sei muito pouco sobre eles.

Pelo que entendi, com os métodos do tipo FEAST, você também pode obter uma contagem do número de autovalores em uma região especificada do plano complexo (por meio de uma integral de contorno); portanto, se você precisar de um autovalor especificado no meio do espectro , por exemplo, o 300, você pode executar uma espécie de pesquisa de bissecção: suponha (deslocamento e escala) que o espectro da sua matriz esteja em $[-1,1]$ (e isso é real, por simplicidade). Calcule os autovalores $\mu$ mais próximos de $\frac12$ . Calcule o número de valores próprios em $[\frac12,1]$ . Se for maior que 300, procure o valor próprio mais próximo do ponto médio de $[\mu,1]$ , caso contrário, o valor próprio mais próximo ao ponto médio de $[-1,\mu]$ . Repetir.

Acho que nada disso seria competitivo com a baunilha LAArnoldi se você substituir 300 por 19, como no seu exemplo. E talvez nem mesmo com 300.

Federico Poloni
fonte