¿Cómo se aplica el algoritmo QR a una matriz real para devolver valores propios complejos?

8

Soy un novato en los algoritmos de valores propios, pero algo me llama la atención. El algoritmo QR funciona con matrices reales / complejas que producen valores propios reales / complejos. Sin embargo, no puede producir valores propios complejos a partir de una matriz real . Aquí un ejemplo simplista escrito en Julia y derivado de aquí y aquí :

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 la matriz A como compleja, con solo componentes reales, no hace ninguna diferencia.

Mis preguntas son:

  • ¿Cuál es mi malentendido conceptual sobre el tema?
  • ¿Qué paso estoy haciendo mal?
  • Y como arreglarlo ?

Gracias

Noel Araujo
fuente
2
Con respecto a la respuesta de Christian Clason, por ejemplo, puede verificar que el bloque más bajo tiene un rastro que también es aproximadamente dos veces la parte real del último par de valores propios . La misma relación debe mantenerse para los otros dos pares, pero la relación de orden no está tan garantizada como para el último, que siempre es el valor propio más pequeño en el algoritmo QR simple sin cambios u otras campanas y silbatos. 0.12201942568224483 + 3.0444575546321087 = 3.1664769803143535 2 1.5832384901571723 = 3.16647698031434472×20.12201942568224483+3.0444575546321087=3.166476980314353521.5832384901571723=3.1664769803143447
Lutz Lehmann el
3
La matriz real puede tener valores propios complejos. La matriz real y simétrica solo puede tener valores propios reales. math.stackexchange.com/questions/67304/…
R zu

Respuestas:

13

En pocas palabras, el algoritmo QR aplicarse a una matriz es un procedimiento iterativo que converge a la verdadera descomposición de Schur: una matriz unitaria y una matriz en bloque de forma superior triangular (ver abajo) tal que . De ello se deduce que las columnas de son los vectores propios (que son los principales objetos que se calculan!) Y que tiene los mismos valores propios como .AQRA = Q R Q T Q R AA=QRQTQRA

El punto clave es la forma triangular superior del bloque , lo que significa que donde son reales bloques de cualquiera

R=(R110Rmm),
Rii

  • tamaño , en cuyo caso es un valor propio (real) de , o1×1RiiA
  • tamaño , en cuyo caso tiene un par de autovalores conjugados complejos de (como y ).2×2RiiA2+i2i

Como puede calcular valores propios de matrices analíticamente (como raíces de un polinomio cuadrático), es un paso barato extraer los valores propios complejos de la calculada (aproximación de) al final, y esto es lo que hace.2×2Reigvals

Entonces, su malentendido conceptual es el siguiente: cada matriz real tiene valores propios, pero no tienen que ser reales (o distintos): mire el ejemplo ahora eliminado de Richard Zhang, , que tiene los valores propios . Solo si la matriz es simétrica, se garantiza que los valores propios sean reales (y que la matriz sea ​​diagonal), por lo que su código solo funciona para matrices simétricas. Si la matriz de entrada no es simétrica, también debe extraer los valores propios (complejos) identificando losn×nnA=(0110)±iR 2 × 2R2×2 bloques (por ejemplo, comprobando si un elemento subdiagonal es mayor que una tolerancia) y, de ser así, calculando los valores propios mediante una fórmula.

Esto es un poco tedioso, pero si está dispuesto a hacer trampa y usarlo eigenvaluespara los bloques , la siguiente modificación de su código lo hará:2×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
fuente
No creo que entienda tu punto. En mi ejemplo, la matriz M que contiene los valores propios. ¿Cómo se supone que obtengo los valores propios complejos de él? (si alguien pudiera proporcionar un código fuente sería mejor)
Noel Araujo
2
Aunque esta es la forma en que generalmente se hacen las cosas en la práctica, es un ejercicio interesante hacer una transformación de similitud compleja aleatoria a la matriz (manteniendo los valores propios constantes mientras se hace la matriz compleja) y luego hacer el algoritmo QR con números complejos. Terminarás con los valores propios complejos en la diagonal de y eliminarás los bloques de 2x2. R
Brian Borchers
2
Una ventaja de este enfoque es que cualquier forma razonable de encontrar los valores propios de los bloques 2x2 asegura que los valores propios complejos vengan en pares conjugados complejos como lo requiere la teoría.
Brian Borchers
3
@NoelAraujo Debe mirar la matriz completa M, no solo la diagonal diag(M)(ya Mque no es ni diagonal ni triangular). Luego verás los bloques de 2x2. Puede comprobar mi reclamo con, por ejemplo, eigvals(M[1:2,1:2]). (@BrianBorchers ¡Es un buen truco!)
Christian Clason el
2
@KutalmisB Si desea vectores propios complejos (en lugar de una base propia real), la forma más fácil es probablemente el enfoque de Brian para trabajar en aritmética compleja desde el principio. Se puede extraer vectores propios complejos de la factorización de Schur real, pero es más complicado; puedes ver cómo lo hace LAPACK .
Christian Clason
5

Olvídese del algoritmo QR y recuerde qué son los valores propios: son las raíces del polinomio característico de la matriz (consulte, por ejemplo, https://en.wikipedia.org/wiki/Characteristic_polynomial ). Para una matriz real de orden N, este es un polinomio de orden N con coeficientes reales. Pero los coeficientes reales no significan necesariamente raíces reales, es posible que tenga pares conjugados complejos. Por lo tanto, una matriz real general puede tener valores propios complejos.

Ian Bush
fuente
0

He usado esta ecuación muchas veces para probar la convergencia. El 11 en la primera fila debe ser -11. Ejecutar el algoritmo QR sin cambios, tal como lo hace la matriz, durante aproximadamente 60 iteraciones da como resultado una matriz con valores propios que se muestran casi exactamente en diagonal, incluso los complejos. Los 5 + -6i están en las dos primeras líneas, los 4 y 3 en las siguientes dos y finalmente el 1 + -21 en el bloque inferior derecho. No piense que los valores complejos generalmente aparecen claramente sin calcular los valores propios de la matriz 2x2.

Bill Nee
fuente