Gibt es eine -Methode, um lineare Systeme der Form zu lösen, wobei eine feste SPD-Matrix ist und positive Diagonalmatrizen sind?
Wenn beispielsweise jedes Skalar ist, genügt es , den SVD zu berechnen . Dies bricht jedoch für General aufgrund mangelnder Kommutativität zusammen.
Update : Die bisherigen Antworten lauten "nein". Hat jemand eine interessante Ahnung, warum? Eine Nein-Antwort bedeutet, dass es keine nicht einfache Möglichkeit gibt, die Informationen zwischen zwei nicht pendelnden Operatoren zu komprimieren. Es ist nicht sonderlich überraschend, aber es wäre toll, es besser zu verstehen.
linear-algebra
algorithms
performance
complexity
Geoffrey Irving
quelle
quelle
Antworten:
Die positivsten Antworten auf Ihre Frage, die ich finden konnte, sind für spärliche diagonale Störungen (siehe unten).
Trotzdem kenne ich keine Algorithmen für den allgemeinen Fall, obwohl es eine Verallgemeinerung der Technik gibt, die Sie für Skalarverschiebungen von SPD-Matrizen zu allen Quadratmatrizen erwähnt haben:
Für jede quadratische Matrix existiert eine Schur-Zerlegung A = U T U H , wobei U einheitlich und T oberes Dreieck ist und A + σ I = U ( T + σ I ) U H eine Schur-Zerlegung von A + liefert σ I . Somit erstreckt sich Ihre Vorberechnungsidee über den Algorithmus auf alle Quadratmatrizen:A A=UTUH U T A+σI=U(T+σI)UH A+σI
Diese Argumentation reduziert sich auf den Ansatz, den Sie erwähnt haben, wenn SPD ist, da sich die Schur-Zerlegung für normale Matrizen auf eine EVD reduziert und die EVD mit der SVD für positiv-definierte Hermitian-Matrizen übereinstimmt.A
Antwort auf die Aktualisierung: Bis ich einen Beweis habe, den ich nicht habe, lehne ich es ab, zu behaupten, die Antwort sei "nein". Ich kann jedoch einige Einblicke geben, warum es schwierig ist, sowie einen weiteren Teilfall, in dem die Antwort Ja lautet.
Die wesentliche Schwierigkeit besteht darin, dass das Update zwar diagonal ist, aber im Allgemeinen immer noch den vollen Rang hat. Daher scheint das primäre Tool zum Aktualisieren einer Inversen, die Sherman-Morrison-Woodbury-Formel , nicht zu helfen. Obwohl der Skalarverschiebungsfall auch den vollen Rang hat, ist er ein äußerst spezieller Fall, da er mit jeder Matrix pendelt, wie Sie erwähnt haben.
quelle
Antwort auf die Aktualisierung : @JackPaulson ist vom Standpunkt der numerischen linearen Algebra und der Algorithmen aus ein hervorragender Punkt. Ich werde mich stattdessen auf Argumente zur Komplexität von Berechnungen konzentrieren.
quelle
Wenn die Verschiebung im Vorkonditionierer viel größer ist als im Bediener, erzeugt diese Methode in der Regel eine Bedingungszahl, die etwa halb so groß ist wie die des verzögerten Bedieners (in den von mir durchgeführten Zufallstests könnte sie für eine bestimmte Klasse von Personen besser oder schlechter sein) Matrizen). Dieser Faktor von 2 in der Bedingungsnummer ergibt einen Faktor von in der Iterationszahl. Wenn die Iterationskosten von den Lösungen mit dominiert werden , ist dies kein ausreichender Faktor, um die Taylor-Expansion erster Ordnung zu rechtfertigen. Wenn die Matrixanwendung verhältnismäßig teuer ist (z. B. Sie haben nur einen kostengünstigen Vorkonditionierer für ), ist diese Methode erster Ordnung möglicherweise sinnvoll. A+DA+D2–√ A+D A+D
quelle