Apakah ada algoritma yang efisien untuk fraksi lanjutan bernilai matriks?

Misalkan saya memiliki persamaan matriks yang didefinisikan secara rekursif sebagai

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

Kemudian persamaan untuk A [1] terlihat mirip dengan fraksi lanjutan, di mana ada beberapa metode yang sangat efisien yang menghindari perhitungan ulang yang membosankan (Lihat "Resep Numerik" untuk beberapa contoh).

Namun, saya bertanya-tanya apakah ada metode analog yang memungkinkan koefisien b [n] dan [n] menjadi matriks, dengan satu-satunya kendala bahwa b [n] A [n + 1] menjadi matriks persegi sehingga matriks

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

sebenarnya tidak bisa dibalik.

algorithms Lagerbaer
sumber

Ini adalah pertanyaan yang Anda ajukan dalam matematika. SEBELUM beberapa bulan sebelumnya, bukan? Apakah

A

$A$ persegi atau persegi panjang?

Saya ingat bahwa seseorang dalam komentar di math.SE menyarankan agar saya bertanya di sini setelah beta online :) Dalam kasus khusus saya, A adalah persegi panjang. Persamaan rekursif sesuai dengan seperangkat persamaan hirarkis, dan jumlah kuantitas tumbuh dengan

n

$n$ . Dalam kasus saya, dimensi A [n] adalah nx (n-1)

Lagerbaer

Hanya ingin tahu, untuk apa aplikasi yang ingin Anda gunakan ini?

Hjulle

Secara singkat, menggunakan identitas Dyson untuk Hamiltonian tertentu menghasilkan fungsi Green yang dapat saya label dengan indeks

tertentu

N

$N$ . Mengumpulkan semua fungsi dengan indeks yang sama ke dalam vektor

V_{N}

$V_N$ memungkinkan saya untuk menulis

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

$V_N = \alpha_N V_{N-1} + \beta_N V_{N+1}$ menggunakan identitas Dyson dan perkiraan yang sesuai. Menggunakan cut-off sehingga

V_{N} = 0

$V_N = 0$ untuk semua

n \geq N

$n \ge N$ memungkinkan saya untuk menemukan matriks

A_{n}

$A_n$ sehingga

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

$V_n = A_n V_{n-1}$ dan matriks ini diberikan oleh persamaan gaya lanjutan fraksi saya. Teknik ini dapat, misalnya, menghitung fungsi lattice Green untuk model yang terikat erat.

Lagerbaer

Itu bukan bidang saya, tetapi saya beberapa waktu lalu di sebuah seminar di mana sesuatu yang berkaitan dengan masalah ini disajikan. [Sini] [1] adalah satu-satunya jejak yang dapat saya temukan secara online. Saya benar-benar tidak tahu apakah itu membantu. [1]: mh2009.ulb.ac.be/ResActiv.pdf

user189035

Jawaban:

Dua metode berikut diberikan dalam Fungsi Matriks: Teori dan Perhitungan oleh Nicholas Higham, di halaman 81. Rumus-rumus ini mengevaluasi

di manaadalah matriks persegi.

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$

Metode top-down:

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

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

akhir

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

Metode bottom-up:

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

untuk j = 2m − 1: −1: 1

Memecahkan untuk . $(b_jI+Y_{j+1})Y_j =a_jX$ $Y_j$

akhir

$r_m=b_0I+Y_1$

Pertanyaannya meminta evaluasi bentuk yang lebih umum

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

Ini dapat dievaluasi dengan generalisasi sederhana dari rumus di atas; misalnya metode bottom-up menjadi

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

untuk j = 2m − 1: −1: 1

Memecahkan untuk . $(b_jI+Y_{j+1})Y_j =a_j X_j$ $Y_j$

akhir

. $r_m=b_0I+Y_1$

David Ketcheson
sumber

Ini terlihat sangat menarik. Saya akan melihat apakah saya dapat menerapkannya pada masalah spesifik saya tetapi menjawab pertanyaan karena b [n] * A [n + 1] saya adalah matriks persegi

Lagerbaer

Ah, tapi saya baru saja memperhatikan bahwa matriks

adalah sama di mana-mana dalam solusi Anda, tetapi saya belum tentu.

X

$X$

Lagerbaer

Oke, saya sudah menggeneralisirnya.

David Ketcheson

Saya tahu bahwa jawaban ini menghasilkan banyak asumsi, tetapi setidaknya menggeneralisasikan algoritme Anda:

Misalkan , , dan matriks pembenihan, , semua membentuk keluarga komuter dari matriks normal, di mana nilai eigen dekomposisi dari $\{A_n\}$ $\{B_n\}$ $V_N$ dan dikenal sebagai apriori, katakanlah , , dan $\{A_n\}$ $\{B_n\}$ $U' V_N U = \Lambda_N$ $U' A_n U = \Omega_n$ $U' B_n U = \Delta_n$ , di mana adalah kesatuan dan , , dan adalah matriks diagonal bernilai kompleks. $U$ $\Lambda_N$ $\{\Omega_n\}$ $\{\Delta_n\}$

Setelah kita mengatakan dekomposisi, dengan induksi,

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

yang dapat diatur ulang ke dalam formulir

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$

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

Jack Poulson
sumber