Welcher ist schneller/stabiler: Invertierung der Matrix oder Lösung von drei linearen Gleichungssystemen mit mehreren rechten Seiten?

Question

Ich habe zwei Gleichungen Ich bin auf jedem rekursiven runde Lösung:

X = A - INV (B) * Y * inv (B), X = X + A‘* inv (B) * A,

I lösen das Problem auf diese Weise:

C = inv (B) < Y => BC = Y, lösen C. D = C inv (B) < => DB = C = < > B'D '= C', löse D '

E = inv (B) * A < => BE = A, löse E.

Alle Matrizen ändern sich im Laufe der Zeit, also muss ich jede Rekursion wiederholen (oder invertieren). N ist normalerweise etwa 1-10, möglicherweise mehr, aber normalerweise so etwas. B ist positiv definit, so dass ich cholesky auf Faktorisierung verwenden kann, und dann Gleichungen von mehreren rechten Seiten lösen kann.

Ist das viel langsamer oder schneller als nur B zu invertieren und dann Matrixmultiplikationen zu machen? Eine Umkehrung gegen das Lösen von drei linearen Gleichungssystemen (es gibt auch eine andere Gleichung) plus etwas Transponieren. Ich würde denken, dass es zumindest numerisch stabiler ist als Invertieren?

Danke.

Answer 1

Als erstes nehmen wir an, dass alle Ihre Matrizen von der Ordnung n x n sind. Die Cholesky-Faktorisierung kann dann in O (n^3/6) -Operationen durchgeführt werden (für große Werte von n).

Lösung B * c (i) = y (i) oder L * L '* c (i) = y (i) (Cholesky) ist 2 * O (n^2/2) oder O (n^2), aber das Lösen von BC = Y löst n dieser Gleichungen (weil Y nxn ist), also haben wir insgesamt O (n^3).

Lösung D 'ist offensichtlich analog dazu, also ein anderes O (n^3).

Transponieren von D 'nach D ist grob O (n^2), keine Berechnungen, nur das Austauschen von Daten (abgesehen von den diagonalen Elementen, die natürlich gleich sind).

Solving E in BE = A in der zweiten Formel ist, rückwärts Substitution von Cholesky-Faktorisierung noch einmal, so O (n^3)

A‘* E n^2 * (n mult und n-1 add) das ist O (2 * n^3 - n^2)

Dies ergibt: O (n^3/6) + 3 * O (n^3) + O (n^2) + O (2 * n^3 - n^2) ~ 0 (31 * n^3/6) ~ O (5 * n^3) (für große Werte von n)

Beachten Sie, dass ich nicht berechnet habe die Matrix-Additionen/Subtraktionen, aber dies ist nicht relevant, weil sie dieselben sein werden, wenn wir uns entscheiden, B zu invertieren. Ich habe aus denselben Gründen auch A nach A 'übersprungen.

Ok, also wie teuer ist das Invertieren einer Matrix? Nun, wir wollen die Matrixgleichung lösen:

B * inv (B) = I, was das gleiche ist wie B * x (i) = e (i) für i = 1..n, wo e (i) sind die Basiseinheitsvektoren in I. Dies geschieht normalerweise durch Gauss-Eliminierung, um das System in eine Dreiecksform zu transformieren, die etwa O (n^3/3) -Operationen benötigt. Wenn die Triangulation gemacht wird, benötigt man O (n^2/2) -Operationen, um sie zu lösen (Rückwärtssubstitution). Aber das muss n-mal gemacht werden, was uns insgesamt O (n^4/3) + O (n^3/2) Operationen gibt, so wie Sie sehen können, sind wir schon über den Rand.

jedoch inv Berechnung (B), wenn die Cholesky-Faktorisierung von B zu kennen, ist O (n^3) (weil die Lösung L * L * = inv (B) = I ist die gleiche wie BE Lösung = A)

Also haben wir dann: O (n^3/6) (Cholesky von B) + O (n^3) (Berechnung inv (B) mit Cholesky) + 4 * O (2n^3-n^2) (vier Matrixmultiplikationen) ~ O (9 * n^3), was ein wenig besser ist, aber immer noch schlechter.

Also ich schlage vor, dass Sie mit Ihrem aktuellen Ansatz bleiben. Aber Sie müssen bedenken, dass dies für große Werte von n ist. Wenn n nicht 100+ ist, glaube ich nicht, dass es so wichtig ist.