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

18

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

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]

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

Lagerbaer
источник
Это вопрос, который вы задали в математике. Несколько месяцев назад, нет? Является ли квадратной или прямоугольной формы? A
JM
Я вспоминаю, что кто-то в комментариях на math.SE предложил мне спросить об этом здесь, как только бета будет в сети :) В моем особом случае A - прямоугольная. Рекурсивные уравнения соответствуют иерархической системе уравнений, и число величин растет с N . В моем случае размерность A [n] равна nx (n-1)
Lagerbaer
Просто интересно, для какого приложения вы хотите использовать это?
Хюлле
1
Очень кратко, идентичность с помощью Дайсона для конкретного гамильтониана формирует функцию Грина , что можно пометить с определенным индексом . Сбор всех функций с одинаковым индексом в вектор V N позволяет мне записать V N = α N V N - 1 + β N V N + 1, используя тождество Дайсона и подходящее приближение. Использование отсечения, чтобы V N = 0 для всех n N, позволило мне найти матрицы A n, чтобы V nNVNVN=αNVN1+βNVN+1VN=0nNAn и эти матрицы задаются моим уравнением стиля с непрерывной дробью. Этот метод может, например, вычислять решеточные функции Грина для моделей с сильной связью. Vn=AnVn1
Лагербаер
1
Это не моя область, но я был некоторое время назад на семинаре, где было представлено что-то, имеющее отношение к этой проблеме. [Здесь] [1] - это единственный след, который я смог найти в Интернете. Я действительно не знаю, помогает ли это. [1]: mh2009.ulb.ac.be/ResActiv.pdf
user189035

Ответы:

9

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

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

р(Икс)знак равноб0+a1Иксб1+a2Иксб2++a2м-1Иксб2м-1+a2мИксб2м
Икс

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

п-1знак равноя,Q-1знак равно0,п0знак равноб0я,Q0знак равноя

для j = 1: 2 м

Pj=bjPj1+ajXPj2

Qj=bjQj1+ajXQj2

конец

rm=P2mQ2m1


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

Y2m=(a2m/b2m)X

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

Решить для Y j .(бJя+YJ+1)YJзнак равноaJИксYJ

конец

рмзнак равноб0я+Y1


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

б0+a1Икс1б1+a2Икс2б2++a2м-1Икс2м-1б2м-1+a2мИкс2мб2м

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

Y2мзнак равно(a2м/б2м)Икс2м

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

Решить для Y j .(бJя+YJ+1)YJзнак равноaJИксJYJ

конец

.рмзнак равноб0я+Y1

Дэвид Кетчесон
источник
Это выглядит очень интересно. Я посмотрю, смогу ли я применить его к своей конкретной задаче, но он ответит на вопрос, поскольку мой b [n] * A [n + 1] является квадратной матрицей
Lagerbaer
Икс
Хорошо, я обобщил это.
Дэвид Кетчон
6

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

{AN}{ВN}ВN{AN}{ВN}U'ВNUзнак равноΛNU'ANUзнак равноΩNU'ВNUзнак равноΔNUΛN{ΩN}{ΔN}

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

ВNзнак равно(я-ВNВN+1)-1ANзнак равно(я-UΔNU'UΛN+1U')-1UΩNU',

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

ВNзнак равноU(я-ΔNΛN+1)-1ΩNU'UΛNU',

ΛN{ВN}ΛNВN

ANαNяВNβNяВN

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