算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
我们知道,求解方程组的一般方法是高斯消元,时间复杂度为 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 西月弦 阅读(289) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理