数值分析（第2版）课件第4章 解线性方程组的迭代法

预备知识（一）武芳芳本节主要学习内容：2.向量范数的定义1.引言4.向量范数的等价性3.向量序列极限定义引言【回顾直接法】优点：缺点：不考虑舍入误差的条件下可以直接求出方程组的精确解破坏系数矩阵的稀疏性求解低阶稠密矩阵的方程组的有效方法在考虑舍入误差的情况下所求解仍是近似解计算量相对比较大迭代法【回顾非线性方程组的迭代法】

求解线性方程组的迭代法优点：不破坏原始矩阵，需要计算机存储空间少，易于编程，计算简单利用迭代公式逐步代入产生方程组近似解的方法称为迭代法定义：迭代技术很少用于解决小规模线性方程组，因为达到足够精度所需的时间超过了直接法所需的时间。然而，对于大型且0元素较多的方程组，迭代法在计算机存储和计算中是非常有效的，例如电路分析、边界值问题和偏微分方程的数值解。思考：（1）迭代过程中产生的方程组的近似解的形式？

误差如何度量？

（2）向量序列是如何收敛的？

1.向量范数的定义6

7

例用定义证明是向量范数的9

解

2.

向量序列极限定义10

11

证明

即

其中

设

证明

考虑函数

即3.

向量范数的等价性注意：由定理2可知，如果在一种范数意义下向量序列收敛，则在任何一种范数意义下该向量序列亦收敛.

证明:显然，

于是又有

常用范数的等价关系

或者

矩阵范数

1.矩阵范数相容性：

注意：为了保证矩阵范数和向量范数相容，最常用的矩阵范数是由相应向量范数导出的.

2.1-范数(列范数)：

它是从属于向量1-范数的矩阵范数.3.2-范数(谱范数)：

4.F-范数：

它是与向量2-范数相容的矩阵范数，但不是从属范数.

解

2.矩阵序列的极限

注意：由谱半径的定义，矩阵的2-范数可记为

此时,的2-范数与该矩阵的谱半径相等.3.谱半径

简单迭代法武芳芳SimpleIterationMethod本节主要学习内容：1.简单迭代法的构造2.简单迭代法的收敛性3.简单迭代法的误差估计

简单迭代法

考虑线性方程组1.基本思想

(3)研究使迭代过程收敛更快的方法.简单迭代法研究的主要内容：

迭代格式（收敛的）控制迭代过程（给定精度）简单迭代法的建立：2.基本构造

为构造迭代法，将方程组改写成等价形式为

迭代格式：

3.构造方法

？

可以看出：

由此递推得迭代法的收敛性考虑迭代格式【分析】

定理1

(迭代法基本定理)

证明：

解:

k0(0,0)T2510(6.513216,15.076516)T10.51823020(8.784233,21.410346)T3.78994730(9.576088,23.734455)T1.33465540(9.852191,24.557238)T0.46678250(9.948462,24.845458)T0.16290860(9.982030,24.946097)T0.05681970(9.993734,24.981203)T0.01981380(9.997815,24.993446)T0.00690890(9.999238,24.997715)T0.002408100(9.999734,24.999203)T0.000840

表1计算结果

迭代法的误差估计证明：

所以,把上式带入估计式（1）中，即得估计式（2）.定理证毕.先证估计式（1）再证估计式（2）

【说明】

【回顾例2】k0(0,0)T2510(6.513216,15.076516)T10.51823020(8.784233,21.410346)T3.78994730(9.576088,23.734455)T1.33465540(9.852191,24.557238)T0.46678250(9.948462,24.845458)T0.16290860(9.982030,24.946097)T0.05681970(9.993734,24.981203)T0.01981380(9.997815,24.993446)T0.00690890(9.999238,24.997715)T0.002408100(9.999734,24.999203)T0.000840

表1计算结果

1.简单迭代法的构造2.收敛性的判别方法

3.迭代法的误差估计

总结

雅可比迭代法与高斯赛德尔迭代法武芳芳JacobiIterationandGauss-SeidelIteration

考虑线性方程组

雅可比迭代法

雅可比（Jacobi）迭代格式构造相应的迭代格式

Jacobi迭代格式分量形式（用于计算）

矩阵形式（用于理论分析）

Jacobi迭代矩阵为：

分量形式（用于计算）

Jacobi迭代格式Jacobi迭代格式

Jacobi迭代矩阵

通过分裂矩阵得到Jacobi迭代格式

因而，构造的迭代格式为【另一种构造方法】Jacobi迭代格式（矩阵形式）

故

例

求解线性方程组

（1）写出Jacobi迭代格式的分量形式；（2）写出Jacobi迭代格式的矩阵形式；方程组等价于构造Jacobi迭代格式(分量形式)为

解矩阵形式为式中

Jacobi迭代格式(分量形式)表1Jacobi迭代法计算结果

Jacobi迭代法公式简单，每次迭代只需做一次矩阵和向量的乘积.

缺点:

在后继计算过程中没有使用已经计算出来的新值.优点:

【回顾Jacobi迭代过程】

Jacobi迭代格式高斯赛德尔迭代法

这样就得到了高斯赛德尔（Gauss-Seidel）迭代格式.高斯赛德尔迭代法

Gauss-Seidel迭代格式(分量形式):高斯赛德尔迭代法矩阵形式:Gauss-Seidel迭代矩阵为

留做作业，课下完成！4.3.2高斯-赛德尔迭代法例

分别利用Jacobi迭代法和Gauss-Seidel迭代法求解下列方程组（1）（3）（2）

解：Jacobi迭代格式为Gauss-Seidel迭代格式为取初始向量，

按上式进行迭代，计算结果见表2.（1）表2Jacobi迭代法与Gauss-Seidel迭代法的计算结果利用Gauss-Seidel迭代法求得的近似解为

4.3.2高斯-赛德尔迭代法（2）Jacobi迭代格式为Gauss-Seidel迭代格式为取初始向量，

按上式进行迭代，计算结果见表3.4.3.2高斯-赛德尔迭代法表3Jacobi迭代法与Gauss-Seidel迭代法的计算结果由表3可知，Jacobi迭代法发散.

4.3.2高斯-赛德尔迭代法（3）Jacobi迭代格式为Gauss-Seidel迭代格式为取初始向量，

按上式进行迭代，计算结果见表4.表4Jacobi迭代法与Gauss-Seidel迭代法的计算结果而Gauss-Seidel迭代法发散.

4.3.2高斯-赛德尔迭代法对于方程组(1)，Gauss-Seidel迭代法和Jacobi迭代法都收敛，且Gauss-Seidel迭代法比Jacobi迭代法收敛快.从算例可以看出：对于方程组(2)，Jacobi迭代法不收敛但Gauss-Seidel迭代法收敛.对于方程组(3)，Jacobi迭代法收敛但Gauss-Seidel迭代法发散.（1）对于不同的方程组，Jacobi迭代法和Gauss-Seidel迭代法的收敛性没有必然联系.【结论】（2）当Jacobi迭代法和Gauss-Seidel迭代法均收敛时，通常后者比前者收敛速度快.雅可比与高斯赛德尔迭代法

收敛性判别武芳芳【回顾简单迭代法的收敛性判别】所有适用于简单迭代法的收敛性条件同样适合Jacobi迭代法和Gauss-Seidel迭代法

收敛

Jacobi迭代法：

收敛

Gauss-Seidel迭代法：一般判别顺序：

充分条件充要条件例

考察用Jacobi迭代法求解方程组的收敛性

方法1解方程组的Jacobi迭代矩阵为其特征方程为

解

定理1例

讨论Jacobi迭代法和Gauss-Seidel迭代法解下列线性方程组的收敛性

解根据定理1求Jacobi迭代矩阵的特征值

求Gauss-Seidel迭代矩阵的特征值

【思考】

下列矩阵是否为严格对角占优矩阵？

解

例

证明：用反证法.

假设A为奇异矩阵

记

Jacobi迭代矩阵

Jacobi迭代法收敛【分析】

在例2中，方程组的系数矩阵是严格对角占优的，根据定理2

也可以判定出求解该方程组的Jacobi迭代法是收敛的.例2

考察用Jacobi迭代法解例1中方程组的收敛性.

定理3

定理4【总结】判断Jacobi迭代法和Gauss-Seidel迭代法收敛的常用方法充分条件

充要条件逐次超松弛迭代法—SOR法武芳芳SuccessiveOver-RelaxationMethod本节学习内容：1.逐次超松弛法迭代格式的构造2.逐次超松弛迭代法收敛的必要条件3.逐次超松弛迭代法收敛的充分条件逐次超松弛迭代法逐次超松弛迭代法（SuccessiveOver-RelaxationMethod），简称SOR方法，它是Gauss-Seidel迭代法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一.优点：

计算公式简单，程序设计容易，占用计算机内存小.1.基本思想在Gauss-Seidel迭代法的基础上引入了一个松弛因子（RelaxationFactor），以期望加快迭代的收敛速度。

Gauss-Seidel迭代格式:（分量形式）

2.SOR方法的构造可以看出：

因此得到：

Gauss-Seidel迭代格式：

即：称为SOR方法的迭代格式（分量形式）.

使迭代法收敛速度最快的松弛因子称为最佳松弛因子.

矩阵形式:式中，迭代矩阵为

SOR方法迭代格式（分量形式）