Lequel est plus rapide / plus stable: équations inversion de la matrice ou la résolution de trois systèmes linéaires avec de multiples côtés de la main droite?

Question

J'ai deux équations je résolution sur chaque tour récursive:

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

Je résous le problème de cette façon:

C = inv (B) Y bc = Y, résoudre C. D = C inv (B) <=> DB = C <=> B'D '= C', D résoudre '

E = inv (B) * A <=> BE = A, E résoudre.

Toutes les matrices changer au fil du temps, donc je dois le faire (ou inversion) à nouveau chaque récursion. N est habituellement d'environ 1-10, peut-être plus, mais le plus souvent quelque chose comme ça. B est définie positive que je puisse utiliser Cholesky sur factorisation, puis résoudre des équations de plusieurs côtés droit.

est-ce bien lent ou plus rapide qu'une simple inversion B et faire ensuite multiplications matrice avec cela? Un invertion vs résolution de trois systèmes d'équations linéaires (il y a qu'une autre équation trop) ainsi que certains transpositeur. Je pense que c'est au moins numériquement plus stable que l'inversion?

Merci.

Answer 1

Tout d'abord, supposons que toutes vos matrices sont d'ordre n x n. La factorisation de Cholesky de peut alors se faire en O (n ^ 3/6) les opérations (pour les grandes valeurs de n).

Résolution B * c (i) = y (i) ou L * L '* c (i) = y (i) (Cholesky) est égal à 2 * O (n ^ 2/2) ou O (n ^ 2 ), mais la résolution BC = Y est la résolution n de ces équations (parce que Y est nxn), donc au total, nous avons O (n ^ 3).

résolution D » est évidemment analogue à cela, alors un autre O (n ^ 3).

Transposition D » à D est peu prés O (n ^ 2), si aucun calcul, en échangeant simplement des données (à l'exception des éléments diagonaux qui bien sûr sont les mêmes).

Résolution E BE = A dans la seconde formule est en arrière substitution de factorisation de Cholesky une fois de plus, alors O (n ^ 3)

A » * E est n ^ 2 * (n mult et n-1 add) qui est O (2 * n ^ 3 - n ^ 2)

Ceci résume à: 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) (pour les grandes valeurs de n)

Notez que je ne l'ai pas calculé les additions de matrice / soustractions, mais ce n'est pas pertinent parce qu'ils seront les mêmes si nous décidons d'inverser B. J'ai aussi sautée A à A » pour les mêmes raisons.

Ok, alors comment est cher inversion d'une matrice? Eh bien, nous blême pour résoudre l'équation de la matrice:

B * inv (B) = I, qui est la même que la résolution B * x (i) = e (i) pour i = 1..n, où e (i) sont les vecteurs unitaires de base en I. Cela se fait habituellement à l'aide d'élimination de Gauss pour transformer le système en une forme triangulaire, ce qui prend environ O (n ^ 3/3). Lorsque la triangulation est faite, elle prend O (n ^ 2/2) pour les opérations de la résoudre (substitution en arrière). Mais cela doit être fait n fois, ce qui nous donne un total de O (n ^ 4/3) + O (n ^ 3/2) opérations, de sorte que vous pouvez voir que nous sommes déjà sur le bord.

Toutefois, calculé inv (B) lorsque la connaissance de la factorisation de Cholesky de B est O (n ^ 3) (car la résolution L * L '* inv (B) = I est la même que la résolution BE = A)

Nous avons alors: O (n ^ 3/6) (Cholesky de B) + O (n ^ 3) (calculé inv (B) avec Cholesky) + 4 * O (2n ^ 3-n ^ 2) (quatre multiplications de matrice) ~ O (9 * n ^ 3) qui est un peu mieux, mais pire encore.

Je suggère donc que vous restez avec votre approche actuelle. Mais vous devez garder à l'esprit que c'est pour les grandes valeurs de n. À moins que n est 100+ Je ne pense pas qu'il importe beaucoup de toute façon.