Существует ли эффективный алгоритм для матричных непрерывных дробей?

Предположим, у меня есть матричное уравнение, рекурсивно определенное как

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

Тогда уравнение для A [1] выглядит аналогично непрерывной дроби, для которой есть несколько высокоэффективных методов, позволяющих избежать утомительного пересчета (см. «Числовые рецепты» для некоторых примеров).

Однако мне интересно, существуют ли аналогичные методы, которые позволяют коэффициентам b [n] и a [n] быть матрицами, с единственным ограничением, что b [n] A [n + 1] является квадратной матрицей, так что матрица

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

на самом деле обратим.

algorithms Lagerbaer
источник

Это вопрос, который вы задали в математике. Несколько месяцев назад, нет? Является ли квадратной или прямоугольной формы?

A

$A$

Я вспоминаю, что кто-то в комментариях на math.SE предложил мне спросить об этом здесь, как только бета будет в сети :) В моем особом случае A - прямоугольная. Рекурсивные уравнения соответствуют иерархической системе уравнений, и число величин растет с

n

$n$ . В моем случае размерность A [n] равна nx (n-1)

Lagerbaer

Просто интересно, для какого приложения вы хотите использовать это?

Хюлле

Очень кратко, идентичность с помощью Дайсона для конкретного гамильтониана формирует функцию Грина , что можно пометить с определенным индексом

. Сбор всех функций с одинаковым индексом в вектор

позволяет мне записать

используя тождество Дайсона и подходящее приближение. Использование отсечения, чтобы

для всех

позволило мне найти матрицы

чтобы

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

Лагербаер

Это не моя область, но я был некоторое время назад на семинаре, где было представлено что-то, имеющее отношение к этой проблеме. [Здесь] [1] - это единственный след, который я смог найти в Интернете. Я действительно не знаю, помогает ли это. [1]: mh2009.ulb.ac.be/ResActiv.pdf

user189035

Ответы:

Следующие два метода приведены в Функции матриц: теория и вычисления Николаса Хайама, на странице 81. Эти формулы оценивают

где- квадратная матрица.

р (Икс) знак равно б_{0} + \frac{a_{1} Икс}{б_{1} + \frac{a_{2} Икс}{б_{2} + \dots + \frac{a_{2 м - 1} Икс}{б_{2 м - 1} + \frac{a_{2 м} Икс}{б_{2 м}}}}}

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

Нисходящий метод:

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

для j = 1: 2 м

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

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

конец

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

Восходящий метод:

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

для j = 2m − 1: −1: 1

Решить для . $(b_jI+Y_{j+1})Y_j =a_jX$ $Y_j$

конец

$r_m=b_0I+Y_1$

Вопрос требует оценки в более общем виде

б_{0} + \frac{a_{1} {Икс}_{1}}{б_{1} + \frac{a_{2} {Икс}_{2}}{б_{2} + \dots + \frac{a_{2 м - 1} {Икс}_{2 м - 1}}{б_{2 м - 1} + \frac{a_{2 м} {Икс}_{2 м}}{б_{2 м}}}}}

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

Это можно оценить простым обобщением приведенных выше формул; например, восходящий метод становится

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

для j = 2m − 1: −1: 1

Решить для . $(b_jI+Y_{j+1})Y_j =a_j X_j$ $Y_j$

конец

. $r_m=b_0I+Y_1$

Дэвид Кетчесон
источник

Это выглядит очень интересно. Я посмотрю, смогу ли я применить его к своей конкретной задаче, но он ответит на вопрос, поскольку мой b [n] * A [n + 1] является квадратной матрицей

Lagerbaer

X

$X$

Хорошо, я обобщил это.

Дэвид Кетчон

Я знаю, что этот ответ делает много предположений, но он по крайней мере обобщает ваш алгоритм:

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

Как только мы сказали разложение, по индукции,

В_{N} знак равно (я - В_{N} В_{N + 1})^{- 1} A_{N} знак равно (я - 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',$

которые можно переставить в форму

В_{N} знак равно U (я - Δ_{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$

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

Джек Полсон
источник