线性方程组迭代法与数值解

type

status

date

slug

summary

迭代法的一般形式

对恰定线性方程组，构造与其同解的线性方程组

则，代入上述方程：

若：当充分大时收敛至某一点，则是方程组的解

证明：

不妨设，有，，则

又，矩阵的乘法运算是结合的，而加法运算是交换的，故可以应用等比数列求和公式：

上述分数线是方便表达的记法，指"分母的逆元左乘分子".

已知上式收敛，故

常用迭代法

Jacobi迭代法

将方程组展开：

移项：第个方程左边只留下：

上式可以转写为，其中

易知与同解.

将上述与重新表示：

定义

则

Gauss-Seidel迭代法

Jacobi迭代的运算过程可以描述如下：

为节省存储空间和加快迭代进度，在运算过程中我们可以使用前步求出的结果代入后步：

在实践过程中，只需要使用同一块存储单元，将求出的结果直接覆盖在旧的结果上即可.

数学上，我们将Jacobi迭代的矩阵一分为二：

其中：是下三角矩阵，是上三角矩阵

松弛迭代法

继续改进，将每一次迭代的Gauss-Seidel近似解与上一次迭代的作加权平均：

这样的方法称为松弛迭代

其中称为松弛系数，称为高松弛，称为低松弛，为Gauss-Seidel法

三种迭代方式的通式

观察得到，三种迭代方式的数学表达拥有共同的形式：

通过调整不同的即可得到不同的迭代方式

迭代法收敛的判断

谱半径

矩阵的谱指一个矩阵的特征值的集合，矩阵的谱半径是指模最大的特征值.

由特征值的性质容易导出，

关于谱半径有如下定理:

矩阵谱半径不大于矩阵的任意范数

存在某矩阵范数，对于任意小的正数，有：

若，则当且仅当

由上述定义及定理，立即推得：迭代式 收敛，当且仅当

有若干推论：

若的任意范数，则收敛

松弛法收敛的必要条件是

快速判断收敛的若干结论

对角占优矩阵

若一个方阵某一行的对角元之绝对值大于该行所有其余元素绝对值之和，则称这个方阵是弱对角占优的. 若所有行都满足上述条件，则称这个方阵是严格对角占优的.

例：下述方阵就是严格对角占优的：

有若干结论：

若方阵是严格对角占优阵或者不可约的弱对角占优阵，则Jacobi和G-S必收敛

若方阵是严格对角占优阵且，松弛法收敛

若方阵是正定二次型且，松弛法收敛

误差估计

设有迭代式收敛，则误差：

借此，若定义了误差容许范围，可以将其代入上式求出迭代次数的范围：

对于正定二次型的迭代方法

对于正定二次型有梯度下降法和共轭梯度法，本质上是非线性方程问题