Existe um algoritmo eficiente para frações contínuas com valor de matriz?

Suponha que eu tenha uma equação de matriz definida recursivamente como

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

Então a equação para A [1] se parece com uma fração contínua, para a qual existem métodos altamente eficientes que evitam o recálculo tedioso (consulte "Receitas numéricas" para alguns exemplos).

No entanto, gostaria de saber se existem métodos análogos que permitem que os coeficientes b [n] e a [n] sejam matrizes, com a única restrição de que b [n] A [n + 1] seja uma matriz quadrada para que a matriz

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

é realmente invertível.

algorithms Lagerbaer
fonte

Esta é a pergunta que você fez em math.SE alguns meses antes, não? é quadrado ou retangular?

A

$A$

Lembro-me de que alguém nos comentários de math.SE sugeriu que eu perguntasse isso aqui quando o beta estiver online :) No meu caso especial, A é retangular. As equações recursivas correspondem a um conjunto hierárquico de equações e o número de quantidades cresce com . No meu caso, a dimensão de A [n] é nx (n-1)

n

$n$

Lagerbaer

Apenas curioso, qual é o aplicativo para o qual você deseja usar isso?

precisa saber é o seguinte

Muito resumidamente, a identidade usando de Dyson para um determinado Hamiltonian gera funções de Green que eu pode rotular com um certo índice . A coleta de todas as funções com o mesmo índice em um vetor me permite escrever usando a identidade de Dyson e uma aproximação adequada. Usando um ponto de corte para que para todos os permita-me encontrar as matrizes para que e essas matrizes sejam dadas pela minha equação de estilo de fração contínua. Essa técnica pode, por exemplo, computar as funções de Green da treliça para modelos de ligação rígida.

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$

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

$V_n = A_n V_{n-1}$

Lagerbaer

Não é minha área de atuação, mas estive um tempo atrás em um seminário em que algo referente a esse problema foi apresentado. [Aqui] [1] é o único vestígio que eu encontrei online. Realmente não sei se isso ajuda. [1]: mh2009.ulb.ac.be/ResActiv.pdf

user189035 4/12/12

Respostas:

Os dois métodos a seguir são apresentados em Funções de matrizes: Teoria e computação de Nicholas Higham, na página 81. Essas fórmulas avaliam

r (X) = b_{0 0} + \frac{{uma}_{1} X}{b_{1} + \frac{{uma}_{2} X}{b_{2} + \dots + \frac{{uma}_{2 m - 1} X}{b_{2 m - 1} + \frac{{uma}_{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}}}}}$ onde é uma matriz quadrada.

X

$X$

Método descendente:

$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}$

fim

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

Método de baixo para cima:

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

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

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

fim

$r_m=b_0I+Y_1$

A pergunta pede avaliação da forma mais geral

b_{0 0} + \frac{{uma}_{1} X_{1}}{b_{1} + \frac{{uma}_{2} X_{2}}{b_{2} + \dots + \frac{{uma}_{2 m - 1} X_{2 m - 1}}{b_{2 m - 1} + \frac{{uma}_{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}}}}}$

Isso pode ser avaliado por uma simples generalização das fórmulas acima; por exemplo, o método de baixo para cima se torna

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

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

Solução para . $(b_jI+Y_{j+1})Y_j =a_j X_j$ $Y_j$

fim

$r_m=b_0I+Y_1$ .

David Ketcheson
fonte

Isso parece muito interessante. Vou ver se eu posso aplicá-lo para o meu problema específico, mas que responde à pergunta desde a minha b [n] * A [n + 1] é uma matriz quadrada

Lagerbaer

X

$X$

Ok, eu generalizei.

David Ketcheson

Eu sei que essa resposta faz muitas suposições, mas pelo menos generaliza seu algoritmo:

$\{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$ $U$ $\Lambda_N$ $\{\Omega_n\}$ $\{\Delta_n\}$

Uma vez que dissemos decomposição, por indução,

V_{n} = (Eu - B_{n} V_{n + 1})^{- 1} {UMA}_{n} = (Eu - você Δ_{n} {você}^{'} você Λ_{n + 1} {você}^{'})^{- 1} você Ω_{n} {você}^{'},

$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 pode ser reorganizado no formato

V_{n} = você (Eu - Δ_{n} Λ_{n + 1})^{- 1} Ω_{n} {você}^{'} \equiv você Λ_{n} {você}^{'},

$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$

$A_n \equiv \alpha_n I$ $B_n \equiv \beta_n I$ $V_N$

Jack Poulson
fonte