Como o algoritmo QR aplicado a uma matriz real retorna autovalores complexos?

8

Sou um noob em algoritmos de autovalores, mas algo chama minha atenção. O algoritmo QR trabalha com matrizes reais / complexas que produzem valores próprios reais / complexos. No entanto, ele não pode produzir autovalores complexos a partir de uma matriz real . Aqui um exemplo simplista escrito em Julia e derivado daqui e aqui :

using LinearAlgebra
A = [7 3 4 11 -9 -2;
    -6 4 -5 7 1 12;
    -1 -9 2 2 9 1;
    -8 0 -1 5 0 8;
    -4 3 -5 7 2 10;
    6 1 4 -11 -7 -1]
M = copy(A)

for i=1:100
    global M
    Q,R = LinearAlgebra.qr(M);
    M=R*Q;
end

display(diag(M))
display(eigvals(A))

6-element Array{Float64,1}:
 -2.8415406888480472
  8.675063708533656
  3.658872985794657
  6.3411270142053695
  0.12201942568224483
  3.0444575546321087
6-element Array{Complex{Float64},1}:
  2.916761509842819 + 13.248032079355992im
  2.916761509842819 - 13.248032079355992im
  5.000000000000005 + 6.000000000000003im
  5.000000000000005 - 6.000000000000003im
 1.5832384901571723 + 1.4155521348117128im
 1.5832384901571723 - 1.4155521348117128im

Definir a matriz A como complexa, com apenas componentes reais, não faz diferença.

Minhas perguntas são:

  • qual é o meu mal-entendido conceitual sobre o assunto?
  • que passo estou dando errado?
  • e como consertar isso ?

Obrigado

Noel Araujo
fonte
2
2×20.12201942568224483+3.0444575546321087=3.166476980314353521.5832384901571723=3.1664769803143447
3
A matriz real pode ter autovalores complexos. Matrizes real e simétrica podem ter apenas autovalores reais. math.stackexchange.com/questions/67304/…
R zu

Respostas:

13

AQRA=QRQTQRA

R=(R110Rmm),
Rii

  • 1×1RiiA
  • 2×2RiiA2+i2i

2×2Reigvals

n×nnA=(0110)±iR2×2 blocos (por exemplo, verificando se um elemento subdiagonal é maior que uma tolerância) e, se for o caso, calculando os valores próprios por uma fórmula.

eigenvalues2×2

using LinearAlgebra
A = [7 3 4 11 -9 -2;
    -6 4 -5 7 1 12;
    -1 -9 2 2 9 1;
    -8 0 -1 5 0 8;
    -4 3 -5 7 2 10;
    6 1 4 -11 -7 -1]
M = copy(A)

for i=1:100
    global M
    Q,R = LinearAlgebra.qr(M);
    M=R*Q;
end

eig = Complex{Float64}[]
let
    i=1
    N=size(M,1)
    while i<N   
        if abs(M[i+1,i])<1e-10             
            append!(eig,M[i,i])         
            i+=1         
        else             
            append!(eig,eigvals(M[i:i+1,i:i+1]))         
            i+=2         
        end                 
    end
    if length(eig)<N
       append!(eig,M[N:N,N:N])
    end                 
end       
Christian Clason
fonte
Eu não acho que entendi o seu ponto. No meu exemplo, matriz M que contém os valores próprios. Como suponho obter os autovalores complexos a partir dele? (Se alguém poderia fornecer um código-fonte seria melhor)
Noel Araujo
2
R
2
Uma vantagem dessa abordagem é que qualquer maneira razoável de encontrar os autovalores dos blocos 2x2 garante que os autovalores complexos venham em pares conjugados complexos, conforme a teoria exige.
precisa
3
@NoelAraujo Você deve olhar para a matriz completa M, não apenas para a diagonal diag(M)(já que Mnão é diagonal nem triangular). Então você verá os blocos 2x2. Você pode verificar minha reivindicação com, por exemplo eigvals(M[1:2,1:2]),. (@BrianBorchers Isso é um truque!)
Christian Clason
2
@KutalmisB Se você deseja autovetores complexos (em vez de uma autovoltaica real), a maneira mais fácil é provavelmente a abordagem de Brian para trabalhar em aritmética complexa desde o início. A extração de autovetores complexos da fatoração de Schur real pode ser feita, mas é mais complicada; você pode ver como o LAPACK faz isso .
Christian Clason
5

Esqueça o algoritmo QR e lembre-se de quais são os autovalores - eles são as raízes do polinômio característico da matriz (consulte, por exemplo, https://en.wikipedia.org/wiki/Characteristic_polynomial ). Para uma matriz real de ordem N, este é um polinômio de ordem N com coeficientes reais. Mas coeficientes reais não significam raízes reais necessariamente; você pode ter pares conjugados complexos. Portanto, uma matriz real geral pode ter autovalores complexos.

Ian Bush
fonte
0

Eu usei essa equação muitas vezes para testar a convergência. Os 11 na primeira linha devem ser -11. A execução do algoritmo QR sem mudanças, assim como a matriz, por cerca de 60 iterações resulta em uma matriz com os valores próprios mostrando quase exatamente na diagonal, mesmo os complexos. Os 5 + -6i estão nas duas primeiras linhas, os 4 e 3 nas duas próximas e, finalmente, o 1 + -21 no bloco inferior direito. Não pense que os valores complexos geralmente aparecem claramente sem calcular os valores próprios da matriz 2x2.

Bill Nee
fonte