解线性方程组的各种方法

线性方程组分为稠密的和稀疏的

稠密矩阵

高斯消元法，复杂度O(n^3) 参考：高斯消元法-hihocoder 1166

稀疏矩阵

迭代法，基本原理描述如下，设线性方程组: \[Ax = b\] 将\(A\)分裂为：\(A = M - N\)，则公式可变成： \[Ax = b \Leftrightarrow Mx = Nx + b \Leftrightarrow x = M^{-1}N + M^{-1}b \]\[\Leftrightarrow x = (I - M^{-1}A)x + M^{-1}b\] 进而构造一个迭代法： \[ \begin{cases} &x^{(0)}(初始向量) \\ &x^{(k + 1)} = Bx^{(k)} + f \quad \quad (k = 0, 1, 2,... ) \end{cases} \] 其中 \(B = I - M^{-1}A, f = M^{-1}b\),选取\(M\)矩阵，就得到\(Ax = b\)的各种迭代法。 迭代法包括:

1. 雅克比迭代法
2. 高斯-赛德尔迭代法
3. 超松弛迭代法（广泛）

参考：http://wenku.baidu.com/link?url=9tIzyuwzApj6QMesnd8VCNqzJbi7TMpbvRzYfRed8MD4XspFQi7K5eteEy502M3uI9m6p0kyMnM4fshuyJOmN3zE2v35LKOaOzu9ruoIz9m