在我正在解决的一个问题中,需要求解 Ax=b,其中 A 是一个 n x n 方阵(通常 n = 几千),b 和 x 是大小为 n 的向量。诀窍是,有必要执行这么多(数十亿)次,其中 A 和 b 在连续计算之间仅发生很小的变化。
有没有办法重用之前计算中的 x(或者可能是 A 的倒数)的现有近似解,而不是从头开始求解方程?
我也对一种使 x 达到一定(定义的)精度的方法感兴趣(例如 x 的任何元素中的错误< maxerr, or norm(error in x) < maxerr), rather than an exact solution (again, reusing the previous calculations).
您可以使用 Sherman–Morrison 公式 逐步更新矩阵的逆矩阵
A
。
为了加速矩阵乘法,您可以使用合适的矩阵乘法算法或针对高性能计算而调整的库。经典的矩阵乘法具有复杂性
O(n³)
。 Strassen型算法具有 O(n^2.8)
甚至更好。