c++ - 只有一个常数项发生变化时线性系统Ax= b的高效求解

Question

当只有少数常数项发生变化时，如何有效地求解大型线性方程组。例如:

我目前有系统 Ax= b。我计算 A 的逆一次，将其存储在矩阵中，每次 b 中的任何条目更新时执行矩阵 vector 乘法 A^-1(b) 以重新计算 x。

这是低效的，因为只有几个条目会在 b 中更新。当 A-1 保持不变但 b 的特定已知值发生变化时，是否有更有效的方法来求解该系统？

我使用 uBlas 和 Eigen，但不知道可以解决这个选择性重新计算问题的解决方案。感谢您的指导。

Answer 1

计算A^-1。如果 b_i 是 b 的第 i 个分量，则检查 d/db_i A^-1 b(A^-1 的导数关于b 的第 i 个组成部分)——它等于 A^-1 的列(特别是第 i 个列)。线性函数的导数在其域内是常数。因此，如果您有 b 和 b'，并且它们仅在第 i 个组件上不同，则 A^-1 b - A^-1 b' = [ d/db_i A^-1] * (b-b')_i.对于多个组件，只需将它们相加即可(因为 A^-1 是线性的)。

或者，简而言之，您可以计算 A^-1 (b'-b) 对零输入组件进行一些优化(如果只有一些组件发生变化，则大部分将是组件)。 A^-1 b' = A^-1 (b'-b) + A^-1 (b)。如果您知道只有某些组件会发生变化，您可以复制 A^-1 的相应列，然后将其乘以 b 的那个组件的变化。