Welches ist schneller / stabiles: Matrix invertieren oder drei Systeme von linearen Gleichungen mit mehreren rechten Seiten zu lösen?

Question

Ich habe zwei Gleichungen ich auf jeder rekursiven Runde bin Lösung:

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

Ich löse das Problem auf diese Weise:

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

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

Alle Matrices im Laufe der Zeit ändern, so habe ich diese (oder invertiert) zu tun, wieder jede Rekursion. N ist in der Regel etwa 1-10, möglicherweise mehr, aber in der Regel so ähnlich. B positiv definit, so kann ich cholesky auf Faktorisierung verwenden, und dann lösen Gleichungen mehrerer rechten Seiten.

Ist dies viel langsamer oder schneller als nur Umkehren B und dann tun Matrix-Multiplikationen mit dem? Eine Invertierung vs Lösung drei linearer Gleichungssysteme (es ist eine andere Gleichung zu) plus einige Transponieren. Ich würde denken, dass es zumindest numerisch stabiler als Umkehren?

Danke.

Answer 1

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

Solving B * c (i) = y (i) oder L * L * = c (i) = y (i) (Cholesky) 2 * O (n ^ 2/2) oder O (n ^ 2 ), aber die Lösung BC = Y n diese Gleichungen lösen (weil Y ist N × N), so dass bei insgesamt wir O haben (n ^ 3).

Lösen von D‘ist offensichtlich analog zu diesem, so ein weiterer O (n ^ 3).

Transponieren D‘bis D ist rougly O (n ^ 2), obwohl keine Berechnungen, nur von Daten Swapping (abgesehen von den diagonalen Elementen, die natürlich sind gleich).

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 ist n ^ 2 * (n mult und n-1 Add), die O (2 * n ^ 3 - n ^ 2)

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

Beachten Sie, dass ich nicht die Matrix Additionen / Subtraktionen berechnet haben, aber dies ist nicht relevant, da sie die gleiche sein wird, wenn wir B. umkehren entscheiden, ich habe auch übersprungen A bis A‘aus den gleichen Gründen.

Ok, so wie teuer ist Invertieren einer Matrix? Nun, wir wan die Matrix-Gleichung zu lösen:

B * inv (B) = I, die die gleiche ist wie die Lösung B * x (i) = e (i) für i = 1..n, wobei e (i) die Basiseinheitsvektoren in I. sind Dies wird üblicherweise unter Verwendung Gauß-Elimination erfolgt, das System zu einer dreieckigen Form zu transformieren, die etwa O nimmt (n ^ 3/3) Operationen. Wenn die Triangulation vorgenommen wird es dauert O (n ^ 2/2) Operationen, es zu lösen (Rückwärtssubstitution). Das hat aber getan wird n-mal, was gibt uns insgesamt O (n ^ 4/3) + O (n ^ 3/2) Operationen, so wie Sie sehen können wir bereits ü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 das gleiche wie die Lösung BE = A)

So gilt dann: O (n ^ 3/6) (Cholesky von B) + O (n ^ 3) (Berechnungs inv (B) mit Cholesky) + 4 * O (2n ^ 3-n ^ 2) (vier Matrix-Multiplikationen) ~ O (9 * n ^ 3), die ein bisschen besser, aber immer noch schlimmer.

Deshalb schlage ich vor, dass Sie mit Ihrem aktuellen Ansatz bleiben. Aber man muss sich vor Augen halten, dass dies für große Werte von n ist. Es sei denn, n 100+ Ich glaube nicht, dass es viel sowieso wichtig ist.