我們知道，求解方程組的一般方法是高斯消元，時間復雜度為 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
西月弦 閱讀(360)
評論(0) 編輯 收藏 引用