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?
-
06-09-2019 - |
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.
La solution
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.