¿Cuál es más rápido / más estable: la inversión de la matriz o de la solución de tres sistemas de ecuaciones lineales con múltiples lados derecho?

Question

Tengo dos ecuaciones que estoy resolviendo en cada ronda recursiva:

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

Me resolver el problema de esta manera:

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

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

Todas las matrices cambiar con el tiempo, así que tengo que hacer esto (o inversión) de nuevo cada recursividad. N es por lo general aproximadamente 1-10, posiblemente más, pero por lo general algo por el estilo. B es definida positiva por lo que se puede utilizar en la factorización de Cholesky, y luego resolver ecuaciones de múltiples lados derecho.

Es esto mucho más lento o más rápido que simplemente invirtiendo B y luego haciendo multiplicaciones de matrices con eso? Una Invertion contra la resolución de tres sistemas de ecuaciones lineales (no hay otra ecuación que también) además de algunos de transposición. Yo creo que es al menos numéricamente más estable que invertir?

Gracias.

Answer 1

En primer lugar, vamos a suponer que todas las matrices son de orden n x n. La factorización de Cholesky entonces puede hacerse en O (n ^ 3/6) Operaciones (para valores grandes de N).

Solución B * c (i) = y (i) o L L * '* c (i) = y (i) (Cholesky) es 2 * O (n ^ 2/2) o O (n ^ 2 ), pero la solución de BC = Y es la solución de n de estas ecuaciones (porque Y es nxn), por lo que en total tenemos O (n ^ 3).

Solución D' es, obviamente, análoga a esto, por lo que otro O (n ^ 3).

transposición D' a D es rougly O (n ^ 2), no hay cálculos sin embargo, sólo el intercambio de datos (aparte de los elementos de la diagonal que por supuesto son la misma).

Solución E en BE = A en la segunda fórmula es hacia atrás sustitución de factorización de Cholesky una vez más, por lo O (n ^ 3)

A' * E es n ^ 2 * (n mult y n-1 add), que es O (2 * n ^ 3 - n ^ 2)

Esto 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 valores grandes de n)

Tenga en cuenta que no he calculado las adiciones de matriz / restas, pero esto no es relevante, ya que será el mismo si decidimos invertir B. También he saltado de A a A' por las mismas razones.

Ok, así lo caro que es invertir una matriz? Así que WAN para resolver la ecuación matricial:

B * inv (B) = I, que es la misma que la solución de B * para i x (i) = e (i) = 1..n, donde e (i) son los vectores de la unidad base en I. esto se hace generalmente mediante el uso de la eliminación de Gauss para transformar el sistema a una forma triangular, que toma alrededor de O (n ^ 3/3) operaciones. Cuando se realiza la triangulación que se necesita O (n ^ 2/2) operaciones para resolver él (hacia atrás sustitución). Pero esto tiene que hacerse n veces, lo que nos da un total de O (n ^ 4/3) + O (n ^ 3/2) las operaciones, así como se puede ver que ya estamos por encima del borde.

Sin embargo, el cálculo de inv (B) al conocer la factorización de Cholesky de B es O (n ^ 3) (porque la solución de L * L '* inv (B) = I es la misma que la solución de BE = A)

Así tenemos entonces: O (n ^ 3/6) (Cholesky de B) + O (n ^ 3) (el cálculo de inv (B) con Cholesky) + 4 * O (2n ^ 3-n ^ 2) (cuatro multiplicaciones de matrices) ~ O (9 * n ^ 3) que es un poco mejor, pero todavía peor.

Así que sugiero que se quede con su enfoque actual. Pero hay que tener en cuenta que esto es para grandes valores de n. A menos que n es 100 + No creo que importe mucho de todos modos.