哪一个更快/更稳定：求逆矩阵或求解具有多个右侧的三个线性方程组？
我在每个递归轮中求解两个方程：
X = A - inv(B) * Y * inv(B)， X = X + A' * inv(B) * A，
我这样解决问题：
C = inv(B)Y <=> BC=Y，解C。 D = Cinv(B) <=> DB=C<=> B'D' = C'，求解 D'
E = inv(B)*A <=> BE = A，求解 E。
所有矩阵都会随着时间而变化，因此每次递归我都必须再次执行此操作（或求逆）。 N 通常约为 1-10，也可能更多，但通常是这样的值。 B 是正定的，所以我可以使用 cholesky 进行因式分解，然后求解多个右侧方程。
这比仅仅反转 B 然后用它进行矩阵乘法慢还是快得多？ 一次反演与求解三个线性方程组（还有另一个方程）加上一些转置。 我认为它至少在数值上比反转更稳定？
谢谢。
I have two equations I'm solving on each recursive round:
X = A - inv(B) * Y * inv(B),
X = X + A' * inv(B) * A,
I solve the problem this way:
C = inv(B)Y <=> BC = Y, solve C.
D = Cinv(B) <=> DB = C <=> B'D' = C', solve D'
E = inv(B)*A <=> BE = A, solve E.
All matrices change over time, so I have to do this (or inverting) again every recursion. N is usually about 1-10, possibly more, but usually something like that. B is positive definite so I can use cholesky on factorisation, and then solve equations of multiple right hand sides.
Is this much slower or faster than just inverting B and then doing matrix multiplications with that? One invertion vs solving three systems of linear equations (there's that another equation too) plus some transposing. I would think it's at least numerically more stable than inverting?
Thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
首先，我们假设所有矩阵的阶数都是 nx n。 然后，可以在 O(n^3/6) 运算中完成乔列斯基分解（对于较大的 n 值）。
求解 B*c(i) = y(i) 或 L*L'*c(i) = y(i) (Cholesky) 是 2*O(n^2/2) 或 O(n^2)，但是求解 BC=Y 就是求解这些方程中的 n 个（因为 Y 是 nxn），所以总共有 O(n^3)。
求解 D' 显然与此类似，所以又是一个 O(n^3)。
将 D' 转置为 D 的时间复杂度约为 O(n^2)，但无需计算，只需交换数据（除了对角线元素当然是相同的）。
在第二个公式中求解 BE = A 中的 E 是再次向后代入乔列斯基分解，因此 O(n^3)
A' * E 为 n^2 *（n 乘和 n-1 加），即 O(2* n^3 - n^2)
总计为： 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) （对于较大的 n 值）
请注意，我还没有计算矩阵加法/减法，但这并不相关，因为它们将如果我们决定反转 B，情况也是如此。出于同样的原因，我也跳过了 A 到 A'。
好吧，那么矩阵求逆的成本有多高呢？ 我们想要求解矩阵方程：
B * inv(B) = I，这与求解 B * x(i) = e(i) for i=1..n 相同，其中 e(i) 是I 中的基本单位向量。这通常是通过使用高斯消去法将系统转换为三角形形式来完成的，这需要大约 O(n^3/3) 运算。 当进行三角剖分时，需要 O(n^2/2) 运算来解决它（向后替换）。 但这必须完成 n 次，这使得我们总共需要 O(n^4/3) + O(n^3/2) 次操作，所以如您所见，我们已经超出了极限。
然而，当知道 B 的乔列斯基分解时，计算 inv(B) 为 O(n^3)（因为求解 L*L'*inv(B) = I 与求解 BE=A 相同），
因此我们有： O (n^3/6)（B 的 cholesky）+ O(n^3)（用 cholesky 计算 inv(B)）+ 4*O(2n^3-n^2)（四次矩阵乘法）~ O(9 *n^3) 稍微好一点，但仍然更糟。
所以我建议您保持当前的方法。 但您必须记住，这是针对较大的 n 值。 除非 n 是 100+，否则我认为这并不那么重要。
First of all, let's assume that all your matrixes are of order n x n. The cholesky factorization can then be done in O(n^3/6) operations (for large values of n).
Solving B*c(i) = y(i) or L*L'*c(i) = y(i) (Cholesky) is 2*O(n^2/2) or O(n^2), but solving BC=Y is solving n of these equations (because Y is n x n), so at total we have O(n^3).
Solving D' is obviously analogous to this, so another O(n^3).
Transposing D' to D is rougly O(n^2), no calculations though, just swapping of data (apart from the diagonal elements which of course are the same).
Solving E in BE = A in the second formula is backwards substitution of cholesky factorization once more, so O(n^3)
A' * E is n^2 * (n mult and n-1 add) which is O(2*n^3 - n^2)
This sums up to: 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) (for large values of n)
Note that I haven't calculated the matrix additions/subtractions, but this isn't relevant because they will be the same if we decide to invert B. I have also skipped A to A' for the same reasons.
Ok, so how expensive is inverting a matrix? Well we wan to solve the matrix equation:
B * inv(B) = I, which is the same as solving B * x(i) = e(i) for i=1..n, where e(i) are the base unit vectors in I. This is usually done by using gauss elimination to transform the system to a triangular form, which takes about O(n^3/3) operations. When the triangulation is made it takes O(n^2/2) operations to solve it (backwards substitution). But this has to be done n times, which gives us a total of O(n^4/3) + O(n^3/2) operations, so as you can see we are already over the edge.
However, calculating inv(B) when knowing the cholesky factorization of B is O(n^3) (because solving L*L'*inv(B) = I is the same as solving BE=A)
So we then have: O(n^3/6) (cholesky of B) + O(n^3) (calculating inv(B) with cholesky) + 4*O(2n^3-n^2) (four matrix multiplications) ~ O(9*n^3) which is a little bit better, but still worse.
So I suggest that you stay with your current approach. But you have to keep in mind that this is for large values of n. Unless n is 100+ I don't think it matters that much anyway.