¿Existe un algoritmo eficiente para fracciones continuas con valores de matriz?

18

Supongamos que tengo una ecuación matricial definida recursivamente como

A[n] = inverse([1 - b[n]A[n+1]]) * a[n]

Entonces la ecuación para A [1] se parece a una fracción continua, para la cual existen algunos métodos altamente eficientes que evitan el tedioso recálculo (ver "Recetas numéricas" para algunos ejemplos).

Sin embargo, me pregunto si hay métodos análogos que permitan que los coeficientes b [n] y a [n] sean matrices, con la única restricción de que b [n] A [n + 1] sea una matriz cuadrada para que la matriz

1 - b[n]A[n+1]

En realidad es invertible.

Lagerbaer
fuente
Esta es la pregunta que hiciste en matemáticas. SE unos meses antes, ¿no? ¿Es cuadrado o rectangular? A
JM
Recuerdo que alguien en los comentarios de matemáticas sugirió que pregunte esto aquí una vez que la versión beta esté en línea :) En mi caso especial, A es rectangular. Las ecuaciones recursivas corresponden a un conjunto jerárquico de ecuaciones, y el número de cantidades crece con . En mi caso, la dimensión de A [n] es nx (n-1)n
Lagerbaer
Por curiosidad, ¿para qué aplicación quieres usar esto?
Hjulle
1
Muy brevemente, la identidad utilizando de Dyson para un hamiltoniano particular, genera funciones de Green que puedo etiqueta con un determinado índice . Recopilar todas las funciones con el mismo índice en un vector V N me permite escribir V N = α N V N - 1 + β N V N + 1 usando la identidad de Dyson y una aproximación adecuada. El uso de un punto de corte para que V N = 0 para todos los n N me permite encontrar matrices A n para que V nNVNVN=αNVN1+βNVN+1VN=0nNAn y estas matrices están dadas por mi ecuación de estilo de fracción continua. Esta técnica puede, por ejemplo, calcular las funciones de red de Green para modelos de enlace estrecho. Vn=AnVn1
Lagerbaer
1
No es mi campo, pero hace un tiempo estuve en un seminario donde se presentó algo relacionado con este problema. [Aquí] [1] es el único rastro que pude encontrar en línea. Realmente no sé si ayuda. [1]: mh2009.ulb.ac.be/ResActiv.pdf
usuario189035

Respuestas:

9

Los siguientes dos métodos se dan en Funciones de matrices: Teoría y Computación de Nicholas Higham, en la página 81. Estas fórmulas evalúan

dondeXes una matriz cuadrada.

r(X)=b0+a1Xb1+a2Xb2++a2m1Xb2m1+a2mXb2m
X

Método de arriba hacia abajo:

P1=I,Q1=0,P0=b0I,Q0=I

para j = 1: 2m

Pj=bjPj1+ajXPj2

Qj=bjQj1+ajXQj2

final

rm=P2mQ2m1


Método de abajo hacia arriba:

Y2m=(a2m/b2m)X

para j = 2m − 1: −1: 1

Resolver para(bjI+Yj+1)Yj=ajX .Yj

final

rm=b0I+Y1


La pregunta pide una evaluación de la forma más general.

b0+a1X1b1+a2X2b2++a2m1X2m1b2m1+a2mX2mb2m

Esto se puede evaluar mediante una simple generalización de las fórmulas anteriores; por ejemplo, el método ascendente se convierte

Y2m=(a2m/b2m)X2m

para j = 2m − 1: −1: 1

Resolver para Y j .(bjI+Yj+1)Yj=ajXjYj

final

.rm=b0I+Y1

David Ketcheson
fuente
Esto se ve muy interesante. Veré si puedo aplicarlo a mi problema específico, pero responde a la pregunta ya que mi b [n] * A [n + 1] es una matriz cuadrada
Lagerbaer
Ah, pero acabo de notar que la matriz es la misma en todas partes en su solución, pero la mía no es necesariamente. X
Lagerbaer
Bien, lo he generalizado.
David Ketcheson
6

Sé que esta respuesta hace muchas suposiciones, pero al menos generaliza su algoritmo:

Suponga que , { B n } , y la matriz de siembra, V N , forman una familia de conmutación de matrices normales, donde las descomposiciones de valores propios de { A n } y { B n } se conocen a priori, digamos U V N U = Λ N , U A n U = Ω n , y U B n U = Δ n{An}{Bn}VN{An}{Bn}UVNU=ΛNUAnU=ΩnUBnU=Δn, donde es unitario y Λ N , { Ω n } y { Δ n } son matrices diagonales de valores complejos.UΛN{Ωn}{Δn}

Una vez que hemos dicho descomposición, por inducción,

Vn=(IBnVn+1)1An=(IUΔnUUΛn+1U)1UΩnU,

que se puede reorganizar en la forma

Vn=U(IΔnΛn+1)1ΩnUUΛnU,

Λn{Vn}ΛnVnorte y las matrices de coeficientes.

Tenga en cuenta que un caso especial es cuando UNnorteαnorteyo y sinorteβnorteyo, de modo que el único requisito es que Vnorte Ser una matriz normal.

Jack Poulson
fuente