Existe-t-il un algorithme efficace pour les fractions continues à valeurs matricielles?

18

Supposons que j'ai une équation matricielle définie récursivement comme

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

L'équation pour A [1] ressemble alors à une fraction continue, pour laquelle il existe des méthodes très efficaces qui évitent un recalcul fastidieux (voir «Recettes numériques» pour quelques exemples).

Cependant, je me demande s'il existe des méthodes analogues qui permettent aux coefficients b [n] et a [n] d'être des matrices, avec la seule contrainte que b [n] A [n + 1] soit une matrice carrée de sorte que la matrice

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

est en fait inversible.

Lagerbaer
la source
Telle est la question que vous avez posée en mathématiques.SE quelques mois auparavant, non? Est carré ou rectangulaire? A
JM
Je me souviens que quelqu'un dans les commentaires de math.SE a suggéré que je pose cette question ici une fois la version bêta en ligne :) Dans mon cas spécial, A est rectangulaire. Les équations récursives correspondent à un ensemble hiérarchique d'équations, et le nombre de quantités croît avec . Dans mon cas, la dimension de A [n] est nx (n-1)n
Lagerbaer
Juste curieux, pour quelle application voulez-vous l'utiliser?
Hjulle
1
Très brièvement, en utilisant l'identité de Dyson pour un hamiltonien particulier génère des fonctions de Green que je peux marquer avec un certain indice N . La collecte de toutes les fonctions avec le même indice dans un vecteur VN me permet d'écrire VN=αNVN1+βNVN+1 utilisant l'identité de Dyson et une approximation appropriée. Utiliser un seuil de coupure pour que VN=0 pour tout nN me permette de trouver des matrices An pour que et ces matrices sont données par mon équation de style à fraction continue. Cette technique peut, par exemple, calculer les fonctions du réseau de Green pour les modèles à liaison étroite. Vn=AnVn1
Lagerbaer
1
Ce n'est pas mon domaine, mais j'étais il y a quelque temps à un séminaire où quelque chose concernant ce problème a été présenté. [Ici] [1] est la seule trace que j'ai pu en trouver en ligne. Je ne sais vraiment pas si ça aide. [1]: mh2009.ulb.ac.be/ResActiv.pdf
user189035

Réponses:

9

Les deux méthodes suivantes sont données dans Fonctions des matrices: théorie et calcul par Nicholas Higham, à la page 81. Ces formules évaluent

Xest une matrice carrée.

r(X)=b0+une1Xb1+une2Xb2++une2m-1Xb2m-1+une2mXb2m
X

Méthode descendante:

P-1=je,Q-1=0,P0=b0je,Q0=je

pour j = 1: 2m

Pj=bjPj-1+unejXPj-2

Qj=bjQj-1+unejXQj-2

fin

rm=P2mQ2m-1


Méthode ascendante:

Oui2m=(une2m/b2m)X

pour j = 2m − 1: −1: 1

Résoudre pour Y j .(bjI+Yj+1)Yj=ajXYj

fin

rm=b0I+Y1


La question demande une évaluation de la forme plus générale

b0+a1X1b1+a2X2b2++a2m1X2m1b2m1+a2mX2mb2m

Cela peut être évalué par une simple généralisation des formules ci-dessus; par exemple, la méthode ascendante devient

Y2m=(a2m/b2m)X2m

pour j = 2m − 1: −1: 1

Résoudre pour Y j .(bjI+Yj+1)Yj=ajXjYj

fin

.rm=b0I+Y1

David Ketcheson
la source
Cela semble très intéressant. Je vais voir si je peux l'appliquer à mon problème spécifique mais cela répond à la question puisque mon b [n] * A [n + 1] est une matrice carrée
Lagerbaer
Ah, mais je viens de remarquer que la matrice est la même partout dans votre solution, mais pas la mienne. X
Lagerbaer
D'accord, je l'ai généralisé.
David Ketcheson
6

Je sais que cette réponse fait beaucoup d'hypothèses, mais elle généralise au moins votre algorithme:

Supposons que , { B n } et la matrice d'ensemencement, V N , forment tous une famille de navettage de matrices normales, où les décompositions de valeurs propres de { A n } et { B n } sont connues a priori, disons U V N U = Λ N , U A n U = Ω n et U B n U = Δ n{UNEn}{Bn}VN{UNEn}{Bn}UVNU=ΛNUUNEnU=ΩnUBnU=Δn, où est unitaire et Λ N , { Ω n } et { Δ n } sont des matrices diagonales à valeurs complexes.UΛN{Ωn}{Δn}

Une fois que nous avons dit la décomposition, par induction,

Vn=(IBnVn+1)1An=(IUΔnUUΛn+1U)1UΩnU,

qui peut être réorganisé sous la forme

Vn=U(IΔnΛn+1)1ΩnUUΛnU,

est bien sûr toujours diagonal, donc toute la famille { V n } va nécessairement commuter avec les autres opérateurs, et nous avons montré que les valeurs diagonales de chaque Λ n sont découplées, de sorte que votre formule de récursion scalaire rapide peut être appliquée indépendamment sur les valeurs propres de V N et les matrices de coefficients.Λn{Vn}ΛnVN

AnαnIBnβnIVN

Jack Poulson
la source