Qual deles é mais rápido / mais estável: matriz invertendo ou resolver três sistemas de equações lineares com vários lados mão direita?

Question

Eu tenho duas equações Estou resolvendo em cada ronda recursiva:

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

Eu resolver o problema desta forma:

C = inv (B) Y <=> BC = Y, resolver C. D = C inv (B) <=> DB = C <=> B'D '= C', resolver D '

E = inv (B) * Um <=> BE = A, resolver E.

Todas as matrizes mudança ao longo do tempo, por isso tenho de fazer isso (ou inverter) novamente a cada recursão. N é geralmente cerca de 1-10, possivelmente mais, mas normalmente algo parecido. B é definida positiva para que eu possa usar cholesky na fatoração, e depois resolver equações de vários lados mão direita.

É este muito mais lento ou mais rápido do que apenas invertendo B e, em seguida, fazer produto de matrizes com isso? Uma inversão vs resolver três sistemas de equações lineares (há que outra equação muito) mais alguns transposição. Eu acho que é, pelo menos numericamente mais estável do que invertendo?

Graças.

Answer 1

Em primeiro lugar, vamos supor que todas as suas matrizes são de ordem n x n. Fatorização cholesky pode, então, ser feito em O (n ^ 3/6) operações (para grandes valores de n).

Solução B * c (i) = y (i) ou L * L '* c (i) = y (i) (de Cholesky) é 2 * O (n ^ 2/2) ou O (n ^ 2 ), mas a solução BC = Y é resolver n destas equações (porque Y é nxn), de modo que no total, temos O (n ^ 3).

Solução D' é, obviamente, análoga a esta, de modo que um outro O (n ^ 3).

Transpondo D' para D é rougly O (n ^ 2), não há cálculos no entanto, apenas a troca de dados (para além dos elementos da diagonal que obviamente são o mesmo).

Solução de E em BE = A na segunda fórmula é para trás substituição de fatoração cholesky mais uma vez, de modo que o (n ^ 3)

A' * E é n ^ 2 * (n mult e n-1 suplemento), que é O (2 * n ^ 3 - n ^ 2)

Este resume a: 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) (para grandes valores de n)

Note que eu não ter calculado as adições de matriz / subtrações, mas isso não é relevante, porque eles vão ser o mesmo se decidirmos invertido B. Eu também ter pulado A para A', pelas mesmas razões.

Ok, então o quão caro é inverter uma matriz? Bem, nós wan para resolver a equação de matriz:

B * inv (B) = I, que é o mesmo que a solução B * x (i) = E (i) para i = 1..n, em que e (i) são os vectores de unidade de base em I. Isto é geralmente feito por meio de eliminação de Gauss para transformar o sistema de uma forma triangular, que leva cerca de o (n ^ 3/3) operações. Quando a triangulação é feito leva O (n ^ 2/2) para operações de resolvê-lo (para trás substituição). Mas isso tem que ser feito n vezes, o que nos dá um total de O (n ^ 3/4) + O (n ^ 3/2) operações, assim como você pode ver que já estão sobre a borda.

No entanto, o cálculo inv (B) quando sabendo Fatorização cholesky de B é O (n ^ 3) (porque resolver L * L '* inv (B) = I é o mesmo que resolver BE = A)

Então temos então: O (n ^ 3/6) (cholesky de B) + O (n ^ 3) (cálculo inv (B) com cholesky) + 4 * O (2n ^ 3-N ^ 2) (quatro multiplicações de matriz) ~ O (9 * n ^ 3), que é um pouco melhor, mas ainda pior.

Por isso, sugiro que você ficar com a sua abordagem atual. Mas você tem que manter em mente que este é para grandes valores de n. A menos que n é 100+ Eu não acho que isso importe tanto assim de qualquer maneira.