我们知道，求解方程组的一般方法是高斯消元，时间复杂度为 O(n^3)。
如果求得解是实数的话，我们可以通过牺牲精度的方法来迭代求解。具体见2009年姜碧野的论文。
原理是这样的：
a11 * x1 + a12 * x2 + ... + a1n * xn = b1 可以变化成
x1 = 1/a11 * (b1 - a12 * x2 - a13 * x3 - .. a1n * xn);
如果x1 ... xn已经估计了一个值，那么通过上式进行进一步迭代就会得到更精确的解。
如果有解的话，最后一定是收敛的。
但是如果无解，或者有多个解，结果怎么样我就不知道了。。。。
这种方法叫做 jacobi 迭代法，复杂度O(k * n^2)。
缺点是后期收敛速度很慢。
有一种改进方法，叫做代数多重网格法（Algebraic Multi-Grid）。迭代过程中可以逐渐缩小大型矩阵的规模，使网格由细变粗。
具体细节有待钻研。
posted on 2013-05-23 23:03
西月弦 阅读(333)
评论(0) 编辑 收藏 引用