3

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

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

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

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

4

4 回答 4

3

计算A^-1。如果b_i是 的第 i 个分量b，则检查d/db_i A^-1 b（A^-1 相对于 的第 i 个分量的导数b）——它等于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 的该组件的变化。

于 2012-11-01T14:21:59.173 回答
1

您可以利用问题的线性：

x0 = A_(-1)*b0 
x = A_(-1)*b = x0 + A_(-1)*db

b其中 db 是和之间的差异矩阵b0，它应该用零填充：您可以将其压缩为稀疏矩阵。

Eigen lib有很多很酷的稀疏矩阵函数（乘法，逆，...）。

于 2012-11-01T14:36:40.553 回答
1

首先，不要执行矩阵求逆，而是使用求解器库。其次，将您的姓名首字母x作为第一个猜测传递给图书馆。

该库将执行某种分解，如 LU，并使用它来计算x. 如果您选择一个迭代求解器，那么它已经在完成您描述的解决方案中的大部分内容；它会从一个更糟糕的猜测开始并产生一个更好的猜测，任何好的例程都需要一个初步的猜测来加速这个过程。在许多情况下，无论如何您都对结果有一个很好的了解，因此利用它是有意义的。

如果新b的接近旧的b，那么新的x应该接近旧的x，这将作为一个很好的初步猜测。

于 2012-11-01T14:45:22.360 回答
0

首先，不要计算矩阵逆，而是使用 LU 分解或 QR 分解（比 LU 慢但更稳定）。这种分解在矩阵大小方面比反演性能更好，并且通常更稳定（尤其是 QR）。

如果 A 发生轻微变化（例如，通过一级矩阵），有一些方法可以更新 QR 分解，但是如果 B 发生变化，则必须用新的 b 再次求解——你无法逃避这一点，这是 O(n ^2)。

但是，如果右手边 B 只改变一个固定元素，即。B' = B + dB 预先知道 dB，您可以一劳永逸地解决 A dx = dB，现在 Ax' = B' 的解决方案 x' 是 x + dX。

如果预先不知道dB，但总是几个dB_i向量的线性组合，你可以解出A dx_i = dB_i，但是如果你有很多这样的dB_i，你最终会得到一个^2过程（这实际上相当于计算逆）...

于 2012-11-01T14:35:17.310 回答