Gibt es einen effizienten Algorithmus für matrixwertige fortgesetzte Brüche?

18

Angenommen, ich habe eine rekursiv definierte Matrixgleichung als

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

Dann ähnelt die Gleichung für A [1] einer fortgesetzten Fraktion, für die es einige hocheffiziente Methoden gibt, die eine mühsame Neuberechnung vermeiden (siehe "Numerische Rezepte" für einige Beispiele).

Ich frage mich jedoch, ob es analoge Methoden gibt, die es erlauben, dass die Koeffizienten b [n] und a [n] Matrizen sind, mit der einzigen Einschränkung, dass b [n] A [n + 1] eine quadratische Matrix ist, so dass die Matrix

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

ist eigentlich umkehrbar.

Lagerbaer
quelle
Dies ist die Frage, die Sie in Mathe gestellt haben. SE ein paar Monate zuvor, nein? Ist Quadrat oder ein Rechteck? A
JM
Ich erinnere mich, dass jemand in den Kommentaren bei math.SE vorgeschlagen hat, dies hier zu erfragen, sobald die Beta online ist :) In meinem Spezialfall ist A rechteckig. Die rekursiven Gleichungen entsprechen einem hierarchischen Satz von Gleichungen, und die Anzahl von Größen wächst mit . In meinem Fall ist die Dimension von A [n] nx (n-1)n
Lagerbaer
Nur neugierig, wofür möchten Sie diese Anwendung verwenden?
Hjulle
1
Wenn ich Dysons Identität für einen bestimmten Hamilton-Operator verwende, werden in Kürze die Funktionen von Green generiert, die ich mit einem bestimmten Index . Das Sammeln aller Funktionen mit demselben Index in einem Vektor V N ermöglicht es mir, V N = α N V N - 1 + β N V N + 1 unter Verwendung der Identität von Dyson und einer geeigneten Approximation zu schreiben . Die Verwendung eines Cut-Offs, so dass V N = 0 für alle n N, ermöglicht es mir, Matrizen A n zu finden, so dass V nNVNVN=αNVN1+βNVN+1VN=0nNAn und diese Matrizen sind durch meine Gleichungen mit fortgesetzten Brüchen gegeben. Diese Technik kann zum Beispiel Gitter-Green-Funktionen für eng bindende Modelle berechnen. Vn=AnVn1
Lagerbaer
1
Es ist nicht mein Fachgebiet, aber ich war vor einiger Zeit auf einem Seminar, auf dem etwas zu diesem Problem vorgestellt wurde. [Hier] [1] ist die einzige Spur, die ich online finden konnte. Ich weiß wirklich nicht, ob es hilft. [1]: mh2009.ulb.ac.be/ResActiv.pdf
user189035

Antworten:

9

Die folgenden zwei Methoden werden in Funktionen von Matrizen angegeben: Theorie und Berechnung von Nicholas Higham, auf Seite 81. Diese Formeln werden ausgewertet

wobeiXeine quadratische Matrix ist.

r(X)=b0+a1Xb1+a2Xb2++a2m1Xb2m1+a2mXb2m
X

Top-down-Methode:

P1=I,Q1=0,P0=b0I,Q0=I

für j = 1: 2m

Pj=bjPj1+ajXPj2

Qj=bjQj1+ajXQj2

Ende

rm=P2mQ2m1


Bottom-up-Methode:

Y2m=(a2m/b2m)X

für j = 2m - 1: - 1: 1

Löse für Y j .(bjI+Yj+1)Yj=ajXYj

Ende

rm=b0I+Y1


Die Frage fragt nach einer Bewertung der allgemeineren Form

b0+a1X1b1+a2X2b2++a2m1X2m1b2m1+a2mX2mb2m

Dies kann durch eine einfache Verallgemeinerung der obigen Formeln bewertet werden; zum Beispiel wird die Bottom-up-Methode

Y2m=(a2m/b2m)X2m

für j = 2m - 1: - 1: 1

Löse für Y j .(bjI+Yj+1)Yj=ajXjYj

Ende

.rm=b0I+Y1

David Ketcheson
quelle
Das sieht sehr interessant aus. Ich werde sehen, ob ich es auf mein spezifisches Problem anwenden kann, aber es beantwortet die Frage, da mein b [n] * A [n + 1] eine quadratische Matrix ist
Lagerbaer
X
Okay, ich habe es verallgemeinert.
David Ketcheson
6

Ich weiß, dass diese Antwort viele Annahmen macht, aber sie verallgemeinert zumindest Ihren Algorithmus:

{An}{Bn}VN{An}{Bn}UVNU=ΛNUAnU=ΩnUBnU=ΔnUΛN{Ωn}{Δn}

Sobald wir Zersetzung gesagt haben, durch Induktion,

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

die in das Formular neu angeordnet werden kann

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

Λn{Vn}ΛnVN

AnαnIBnβnIVN

Jack Poulson
quelle