从近似解开始快速求解线性方程组

Question

在我正在解决的一个问题中，需要求解 Ax=b，其中 A 是一个 n x n 方阵（通常 n = 几千），b 和 x 是大小为 n 的向量。诀窍是，有必要执行这么多（数十亿）次，其中 A 和 b 在连续计算之间仅发生很小的变化。

有没有办法重用之前计算中的 x（或者可能是 A 的倒数）的现有近似解，而不是从头开始求解方程？

我也对一种使 x 达到一定（定义的）精度的方法感兴趣（例如 x 的任何元素中的错误< 0.001), rather than an exact solution (again, reusing the previous calculations).

Answer 1

您可以使用 Sherman–Morrison 公式 逐步更新矩阵的逆矩阵

A

。

为了加速矩阵乘法，您可以使用合适的矩阵乘法算法或针对高性能计算而调整的库。经典的矩阵乘法具有复杂性

O(n³)

。 Strassen型算法具有

O(n^2.8)

甚至更好。

在这里提出了一个没有真正答案的类似问题。