Quale delle due è più veloce / più stabile: invertendo matrice o risolvere tre sistemi di equazioni lineari con più lati destro?

Question

Ho due equazioni che sto risolvendo in ogni giro ricorsiva:

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

I risolvere il problema in questo modo:

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

E = inv (B) * Un <=> BE = A, risolvere E.

Tutte le matrici cambiare nel tempo, quindi devo fare questo (o inversione) di nuovo ogni ricorsione. N è di solito circa 1-10, forse più, ma di solito qualcosa di simile. B è definita positiva modo da poter utilizzare Cholesky sulla fattorizzazione, e quindi risolvere equazioni su più lati mano destra.

E 'questa moltiplicazione di matrici molto più lento o più veloce di una semplice inversione B e poi facendo con questo? Un invertion vs risolvere tre sistemi di equazioni lineari (non c'è che un'altra equazione troppo) più alcuni trasposizione. Vorrei pensare che sia almeno numericamente più stabile di inversione?

Grazie.

Answer 1

Prima di tutto, diamo per scontato che tutte le vostre matrici sono di ordine n x n. La fattorizzazione di Cholesky può quindi essere fatto in O (n ^ 3/6) operazioni (per grandi valori di n).

Soluzione B * c (i) = y (i) o L L * '* c (i) = y (i) (Cholesky) è 2 * O (n ^ 2/2) o O (n ^ 2 ), ma risolvendo BC = Y sta risolvendo n di queste equazioni (perché Y è nxn), quindi in totale abbiamo O (n ^ 3).

Risoluzione D' è ovviamente analoga a questa, così un'altra O (n ^ 3).

traspositore D' a D è rougly O (n ^ 2), nessun calcolo però, solo scambio di dati (a parte gli elementi diagonali che ovviamente sono uguali).

Risoluzione E in BE = A nella seconda formula è all'indietro sostituzione della fattorizzazione di Cholesky ancora una volta, quindi O (n ^ 3)

A' * E è n ^ 2 * (n mult e n-1 add), che è O (2 * n ^ 3 - n ^ 2)

Questo riassume 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) (per grandi valori di n)

Si noti che non ho calcolato le aggiunte Matrix / sottrazioni, ma questo non è rilevante perché sarà la stessa se si decide di invertire B. Ho anche saltato A ad A' per le stesse ragioni.

Ok, così come costoso è invertente una matrice? Bene, noi WAN per risolvere l'equazione matriciale:

B * inv (B) = I, che è la stessa soluzione B * x (i) = e (i) per i = 1..n, dove e (i) sono i versori base nei I. questo è solitamente fatto utilizzando eliminazione di gauss per trasformare il sistema ad una forma triangolare, che richiede circa O (n ^ 3/3) operazioni. Quando la triangolazione è reso necessario O (n ^ 2/2) operazioni per risolverlo (all'indietro sostituzione). Ma questo deve essere fatto n volte, che ci dà un totale di O (n ^ 4/3) + O (n ^ 3/2) le operazioni, così come si può vedere, siamo già oltre il bordo.

Tuttavia, il calcolo inv (B) quando conoscendo la fattorizzazione di Cholesky di B è O (n ^ 3) (in quanto la risoluzione L * L '* inv (B) = I è lo stesso di risolvere BE = A)

Così abbiamo poi: O (n ^ 3/6) (Cholesky di B) + O (n ^ 3) (calcolo inv (B) con Cholesky) + 4 * O (2n ^ 3-n ^ 2) (quattro moltiplicazione di matrici) ~ O (9 * n ^ 3), che è un po 'meglio, ma ancora peggio.

Quindi suggerisco di stare con il vostro approccio attuale. Ma devi tenere a mente che questo è per grandi valori di n. A meno che n è 100 + non credo sia importante tanto comunque.