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

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.

algorithms Lagerbaer
fuente

Esta es la pregunta que hiciste en matemáticas. SE unos meses antes, ¿no? ¿Es

cuadrado o rectangular?

A

$A$

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

$n$

Lagerbaer

Por curiosidad, ¿para qué aplicación quieres usar esto?

Hjulle

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

me permite escribir

usando la identidad de Dyson y una aproximación adecuada. El uso de un punto de corte para que

para todos los

me permite encontrar matrices

para que

N

$N$

V_{N}

$V_N$

V_{N} = α_{N} V_{N - 1} + β_{N} V_{N + 1}

$V_N = \alpha_N V_{N-1} + \beta_N V_{N+1}$

V_{N} = 0

$V_N = 0$

n \geq N

$n \ge N$

A_{n}

$A_n$

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.

V_{n} = A_{n} V_{n - 1}

$V_n = A_n V_{n-1}$

Lagerbaer

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:

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

dondees una matriz cuadrada.

r (X) = b_{0} + \frac{a_{1} X}{b_{1} + \frac{a_{2} X}{b_{2} + \dots + \frac{a_{2 m - 1} X}{b_{2 m - 1} + \frac{a_{2 m} X}{b_{2 m}}}}}

$r(X) = b_0 + \frac{a_1 X}{b_1+\frac{a_2 X}{b_2+\cdots + \frac{a_{2m-1} X}{b_{2m-1} + \frac{a_{2m}X}{b_{2m}}}}}$

X

$X$

Método de arriba hacia abajo:

$P_{−1}=I, Q_{−1}=0,P_0 =b_0 I,Q_0 =I$

para j = 1: 2m

$P_j =b_j P_{j−1}+a_jXP_{j−2}$

$Q_j =b_j Q_{j−1}+a_j X Q_{j−2}$

final

$r_m =P_{2m} Q_{2m}^{-1}$

Método de abajo hacia arriba:

$Y_{2m} = (a_{2m}/b_{2m})X$

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

Resolver para $(b_jI+Y_{j+1})Y_j =a_jX$ . $Y_j$

final

$r_m=b_0I+Y_1$

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

b_{0} + \frac{a_{1} X_{1}}{b_{1} + \frac{a_{2} X_{2}}{b_{2} + \dots + \frac{a_{2 m - 1} X_{2 m - 1}}{b_{2 m - 1} + \frac{a_{2 m} X_{2 m}}{b_{2 m}}}}}

$b_0 + \frac{a_1 X_1}{b_1+\frac{a_2 X_2}{b_2+\cdots + \frac{a_{2m-1} X_{2m-1}}{b_{2m-1} + \frac{a_{2m}X_{2m}}{b_{2m}}}}}$

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

$Y_{2m} = (a_{2m}/b_{2m})X_{2m}$

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

Resolver para . $(b_jI+Y_{j+1})Y_j =a_j X_j$ $Y_j$

final

. $r_m=b_0I+Y_1$

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

$X$

Lagerbaer

Bien, lo he generalizado.

David Ketcheson

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

Suponga que , , y la matriz de siembra, , forman una familia de conmutación de matrices normales, donde las descomposiciones de valores propios de y se conocen a priori, digamos , , y $\{A_n\}$ $\{B_n\}$ $V_N$ $\{A_n\}$ $\{B_n\}$ $U' V_N U = \Lambda_N$ $U' A_n U = \Omega_n$ $U' B_n U = \Delta_n$ , donde es unitario y , y son matrices diagonales de valores complejos. $U$ $\Lambda_N$ $\{\Omega_n\}$ $\{\Delta_n\}$

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

V_{n} = (I - B_{n} V_{n + 1})^{- 1} A_{n} = (I - U Δ_{n} U^{'} U Λ_{n + 1} U^{'})^{- 1} U Ω_{n} U^{'},

$V_n = (I - B_n V_{n+1})^{-1} A_n = (I - U \Delta_n U' U\Lambda_{n+1} U')^{-1} U \Omega_n U',$

que se puede reorganizar en la forma

V_{n} = U (I - Δ_{n} Λ_{n + 1})^{- 1} Ω_{n} U^{'} \equiv U Λ_{n} U^{'},

$V_n = U (I - \Delta_n \Lambda_{n+1})^{-1} \Omega_n U' \equiv U \Lambda_n U',$

$\Lambda_n$ $\{V_n\}$ $\Lambda_n$ $V_N$ y las matrices de coeficientes.

Tenga en cuenta que un caso especial es cuando $A_n \equiv \alpha_n I$ y $B_n \equiv \beta_n I$ , de modo que el único requisito es que $V_N$ Ser una matriz normal.

Jack Poulson
fuente