Czy istnieje skuteczny algorytm dla ciągłych ułamków wycenianych w macierzy?

Załóżmy, że mam równanie macierzowe rekurencyjnie zdefiniowane jako

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

Następnie równanie dla A [1] wygląda podobnie do ułamka ciągłego, dla którego istnieje kilka wysoce wydajnych metod, które pozwalają uniknąć żmudnego ponownego obliczania (patrz „Przepisy numeryczne” dla niektórych przykładów).

Zastanawiam się jednak, czy istnieją analogiczne metody, które pozwalają, aby współczynniki b [n] i a n były macierzami, z jedynym ograniczeniem, że b [n] A [n + 1] jest macierzą kwadratową, tak że macierz

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

jest faktycznie odwracalny.

algorithms Lagerbaer
źródło

To pytanie zadałeś w matematyce kilka miesięcy wcześniej, nie? Czy kwadratowy czy prostokątny?

A

$A$

Pamiętam, że ktoś w komentarzach na mat.SE zasugerował, żebym zapytał tutaj, gdy beta będzie już dostępna online :) W moim szczególnym przypadku A jest prostokątne. Równania rekurencyjne odpowiadają hierarchicznemu zestawowi równań, a liczba wielkości rośnie wraz z . W moim przypadku wymiar A [n] wynosi nx (n-1)

n

$n$

Lagerbaer

Ciekawe, do jakiej aplikacji chcesz tego użyć?

Hjulle,

Bardzo krótko, tożsamość Korzystanie Dysona dla konkretnego Hamiltonianu generuje funkcje Greena, że mogę oznaczyć z określonym indeksem . Zebranie wszystkich funkcji z tym samym indeksem w wektorze pozwala mi napisać przy użyciu tożsamości Dysona i odpowiedniego przybliżenia. Użycie aby dla wszystkich pozwoliło mi znaleźć macierze tak że i te macierze są podane przez moje równanie stylu ułamka ciągłego. Ta technika może na przykład obliczyć funkcje sieci Greena dla ściśle powiązanych modeli.

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

To nie moja dziedzina, ale byłem pewien czas na seminarium, na którym przedstawiono coś związanego z tym problemem. [Tutaj] [1] to jedyny ślad, jaki mogłem znaleźć w Internecie. Naprawdę nie wiem, czy to pomaga. [1]: mh2009.ulb.ac.be/ResActiv.pdf

user189035

Odpowiedzi:

Poniższe dwie metody podano w Funkcjach macierzy: Teoria i obliczenia autorstwa Nicholasa Highama, na stronie 81. Te formuły oceniają

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}}}}}$ gdzie jest macierzą kwadratową.

X

$X$

Metoda zstępująca:

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

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

koniec

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

Metoda oddolna:

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

dla j = 2m − 1: −1: 1

Rozwiąż dla . $(b_jI+Y_{j+1})Y_j =a_jX$ $Y_j$

koniec

$r_m=b_0I+Y_1$

Pytanie wymaga oceny bardziej ogólnej formy

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

Można to ocenić przez proste uogólnienie powyższych wzorów; na przykład staje się metoda oddolna

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

dla j = 2m − 1: −1: 1

Rozwiąż dla . $(b_jI+Y_{j+1})Y_j =a_j X_j$ $Y_j$

koniec

$r_m=b_0I+Y_1$ .

David Ketcheson
źródło

To wygląda bardzo interesująco. Zobaczę, czy mogę zastosować go do mojego konkretnego problemu, ale odpowiada on na pytanie, ponieważ mój b [n] * A [n + 1] jest macierzą kwadratową

Lagerbaer

Ach, ale właśnie zauważyłem, że macierz jest wszędzie taka sama w twoim rozwiązaniu, ale moja niekoniecznie.

X

$X$

Lagerbaer,

Okej, uogólniłem to.

David Ketcheson

Wiem, że ta odpowiedź zawiera wiele założeń, ale przynajmniej uogólnia twój algorytm:

Załóżmy, że , i macierz , , tworzą rodzinę dojazdów do normalnych macierzy, gdzie rozkład wartości własnych i jest znany z góry , np , i , gdzie jest jednolity i , i są macierze diagonalne o złożonych wartościach. $\{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\}$

Kiedy już powiedzieliśmy rozkład, przez indukcję,

{V.}_{n} = (ja - b_{n} {V.}_{n + 1})^{- 1} {ZA}_{n} = (ja - 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',$

które można zmienić w formę

{V.}_{n} = U (ja - Δ_{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',$

gdzie jest oczywiście nadal przekątna, więc cała rodzina koniecznie będzie dojeżdżać do pracy z innymi operatorami, a my pokazaliśmy, że wartości przekątnych każdego są oddzielone, więc można zastosować szybką formułę rekurencji skalarnej niezależnie od wartości własnych i macierzy współczynników. $\Lambda_n$ $\{V_n\}$ $\Lambda_n$ $V_N$

Zauważ, że szczególnym przypadkiem jest sytuacja, gdy i , więc jedynym warunkiem jest, aby była normalną macierzą. $A_n \equiv \alpha_n I$ $B_n \equiv \beta_n I$ $V_N$

Jack Poulson
źródło