方程求解方法汇总

线性方程

高斯消元法

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

$$
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的原函数的最优化问题。