线性方程

高斯消元法

高斯消元法求解线性方程是最为经典的方法，基本思想就是一次消去多个变量，直到留下一个，从而解出结果。用矩阵的语言描述，就是对线性方程

$$
Ax = b
$$

的矩阵A和b构成的增广矩阵[A b]做一系列的行变换$(P_i, i=1,...,k)$，将矩阵A变成只有对角线为1或0的单位阵

$$
P_k P_{k-1} ... P_1 A x = P_k P_{k-1} ... P_1 b \\
x = P b
$$

$(P = P_k P_{k-1} ... P_1)$是一系列的航变换，将A矩阵变为单位阵，实际上就是A矩阵的逆！
高斯消元法计算复杂度是$(O(n^3))$。

迭代解法

Jacobi 迭代：将系数矩阵A分解为$(A = D + B)$，其中D是对角阵，B是对角线上为0的矩阵。那么有

$$
x = - D^{-1} B x + D^{-1} b
$$

上式可以把x看做迭代方程的不动点，这就是Jacobi迭代法。收敛的充分条件是$(||D^{-1}B||<1)$，如果取无穷范数，则表示A矩阵是主对角元最大的矩阵，即$(|a_{ii}| > |a_{ij}|, \forall i,j)$。一般的方差，总可以通过简单的行初等变换变成主对角元最大的矩阵！

Gauss-Seidel迭代：将矩阵分解为$(A = L + U)$，其中L是有对角元素的下三角阵，U是没有对角元的上三角阵。迭代方程为

$$
L x_{k+1} = - U x_k + b
$$

每一次迭代是在解稀疏矩阵是下三角矩阵的线性方程，可以在$(O(n^2))$时间复杂度内求解！迭代速度高于Jacobi迭代。

非线性方程

不动点迭代

与线性方程的迭代方法类似，构造不动点方程，使得迭代是压缩映象，那么不断迭代该方程可以得到不动点，就是非线性方程的解！

$$
x = g(x)
$$

线性搜索

二分法、牛顿法等方法。实际上牛顿法求解方程可以看做梯度是f的原函数的最优化问题。