数值分析 第六章 解线性方程组的迭代法

数值分析

NumericalAnalysis第六章解线性代数方程组的迭代法郑州大学研究生课程（2014-2015学年第一学期）

ISCM2007,BeijingChina1第六章解线性代数方程组的迭代法

§6.1引言§6.2

范数与误差分析§6.3几种常用的迭代格式§6.4迭代法的收敛性及误差估计§6.5判别收敛的几个常用条件§6.6迭代法收敛判定的应用举例ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.1引言线性方程组的数值解法有：直接法和迭代法。直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.1引言当A为稀疏矩阵时，直接法将破坏矩阵A的稀疏性。系数矩阵的分类第一类：低阶稠密方程组，即系数矩阵的阶数不高，含零元素很少，在线性代数等课程学习中通常见到的，都属这类方程组；第二类：高阶稀疏方程组，系数矩阵的阶数很高，如几百阶、甚至成千上万阶，其中零元素成片分布，数量上绝对占优。ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis迭代法适用于解大型稀疏方程组(万阶以上的方程组,系数矩阵中零元素占很大比例,而非零元按某种模式分布)问题:(1)如何构造迭代格式？

(2)迭代格式是否收敛？

(3)如何进行误差估计？§6.1引言ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.1引言迭代法的基本思想迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值，按迭代格式，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis设非奇异，，则线性方程组

有惟一解，经过变换构造出一个等价同解方程组将上式改写成迭代式选定初始向量,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis如果向量序列存在极限则称迭代法是收敛的，否则就是发散的。收敛时，在迭代公式中当时，,则

故是方程组的解。对于给定的方程组可以构造各种迭代公式。并非全部收敛。ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2范数与误差分析为了研究线性方程组近似解的误差估计和迭代法的收敛性,有必要对向量及矩阵的“大小”引进某种度量----范数的概念。向量范数是用来度量向量长度的,它可以看成是二、三维解析几何中向量长度概念的推广。用Rn表示n维实向量空间。ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2范数与误差分析（一、向量范数）§6.2.1向量范数定义6.2.1设XRn，Ｘ

表示定义在Rn上的一个实值函数，称之为X的范数，它具有下列性质：（3）三角不等式：即对任意两个向量X、YRn，恒有

(1)正定性：即对一切XRn，X

0,Ｘ

>0(2)齐次性：即对任何实数aR，XRn，ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis注:向量范数是向量长度概念的推广.例如是向量

x的范数常见向量范数常用的范数:1-范数2-范数

-范数ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析例5.7.1证明||x||2

是Rn

上的一种范数证：先证柯西不等式:|xTy|≤||x||2·||y||2对任意实数λ,有(x-λy)T(x-λy)≥0xTx–2λxTy+λ2yTy≥0|xTy|2

–(xTx)(yTy)≤0|xTy|≤||x||2·||y||2判别式ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis(三角不等式成立)(正定性成立)(齐次性成立)ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis例5.7.2.范数意义下的单位向量:X=[x1,x2]T1-11||X||1=111-1-1||X||2=1-111-1-1||X||∞=1ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析当不需要指明使用哪一种向量范数时，就用记号||.||泛指任何一种向量范数。有了向量的范数就可以用它来衡量向量的大小和表示向量的误差。设x*为Ax=b的精确解，x为其近似解，则其绝对误差可表示成||x-x*||，其相对误差可表示成ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis例5.7.3

证明对任意同维向量x,y有

证：

即ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis例5.7.4

设x=(1,0,-1,2)T,计算

解:=1+0+|-1|+2=4ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析有限维空间的范数均等价ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理5.7.1

对于任意向量x,有证:∵

即

当p→∞，

∴ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis

定理5.7.2

（向量范数的等价性）设为上任意两种向量范数,则存在常数C1,,C2>0,使得对任意恒有有限维空间的范数等价定理ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定义5.7.2(向量序列的极限)设为中的一向量序列，,记。如果(i=1,2,…,n)，则称收敛于向量，记为ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理5.7.3

其中为向量中的任一种范数。

证由于

而对于上的任一种范数,由定理5.7.2知存在常数C1，C2，使于是可得向量序列依范数收敛与依坐标收敛是等价的。ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定义在Rn上的向量范数

是变量X分量的

连续函数。定理5.7.4ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（二、矩阵范数）§5.7.2矩阵范数ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析证明:(1)ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析证明:(2)矩阵范数和向量范数的相容性ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysisISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理5.7.6

设n

阶方阵A=(aij)nn，则（Ⅰ）与相容的矩阵范数是（Ⅱ）与相容的矩阵范数是其中1为矩阵ATA的最大特征值。（Ⅲ）与相容的矩阵范数是1-范数（列范数）2-范数（谱范数）-范数（行范数）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析与前述三种向量范数相容的三种矩阵范数：ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析

,X=[-35]T,求A、X的“1-范数”,“2-范数”和“无穷大范数”例5.7.5ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析1=26.1803,2=3.8197ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析矩阵的谱半径ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理5.7.8

对给定方阵G,若,则为非奇异矩阵,且

证:用反证法,若为奇异矩阵,则存在非零向量x,使,即有由相容性条件得

由于,两端消去,有,与已知条件矛盾,假设不成立,命题得证。又由于有

即

将G分别取成G和-G，再取范数

又已知，有

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定义5.7.6设有矩阵序列及,如果个数列极限存在且有则称收敛于，记为ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis例5.7.6且设，考查其极限.

解由于，当时，有设有矩阵序列所以ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理5.7.9设,则(零矩阵)的充分必要条件是矩阵的谱半径（证明参见：关治，陈景良.数值计算方法,清华大学出版社，P410~412）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）方程组的性态在建立方程组时，其系数往往含有误差（如观测误差或计算误差），就是说，所要求解的运算是有扰动的方程组，因此需要研究扰动对解的影响。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）矩阵的条件数ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）Ｑ：产生这种现象的原因何在呢？Ａ：方程组对右端项的扰动太敏感！ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）右端项b的扰动对解的影响ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）系数矩阵Ａ的扰动对解的影响ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）常用的条件数ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysisISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysisISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis“病态”方程的经验判断ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysisISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis误差分析§5.7范数与误差分析（三、误差分析）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§5.7范数与误差分析（三、误差分析）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式雅可比(Jacobi)迭代格式例6.2.1

建立迭代格式求解方程组

方程组的精确解x*=(3,2,1)T。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式建立迭代公式

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis取初始向量进行迭代,可以逐步得出一个近似解的序列：（k=1,2,…）直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明，此迭代过程收敛于方程组的精确解x*=(3,2,1)T。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis考察一般的n元线性方程组

写成ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis若,分离出变量ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式

（Jacobi迭代公式）(k=0,1,2,…)ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式

（Jacobi迭代公式）据此建立迭代公式上式称为解方程组的Jacobi迭代公式。也称为简单迭代法。ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis雅可比迭代法的矩阵表示

设方程组的系数矩阵A非奇异，且主对角元素，则可将A分裂成

记作A=L+D+UISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis则等价于因为

，则这样便得到一个迭代公式§6.2几种常用的迭代格式

（Jacobi迭代公式）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis其中

令则有（k=0,1,2…）称为雅可比迭代公式,B称为雅可比迭代矩阵§6.2几种常用的迭代格式

（Jacobi迭代公式）ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis

雅可比迭代法的算法实现

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式

（Jacobi迭代公式）functionX=jacobi(A,B,P,delta,max)%求解AX=B，A是非奇N阶方阵dleta是误差界，max是最大迭代次数N=length(B);fort=1:maxfork=1:N

X(k)=(B(k)-A(k,[1:k-1,k+1:N])*P([1:k-1,k+1:N]))/A(k,k);enderr=abs(norm(X'-P));if(err<delta)break;endendX=X';ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式高斯-塞德尔（Gauss-Seidel）迭代法在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求时用新分量代替旧分量ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式Gauss-Seidel迭代法(i=1,2,…,n

k=0,1,2,…)高斯-赛德尔迭代法的迭代法格式为：ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式Gauss—Seidel迭代法的矩阵表示将A分裂成A=L+D+U，则等价于

(L+D+U)x=b

于是,则高斯—塞德尔迭代过程

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式Gauss—Seidel迭代法的矩阵表示因为,所以

故则高斯-塞德尔迭代形式为：令ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式高斯-塞德尔迭代法高斯—塞德尔迭代算法实现高斯-塞德尔迭代算法的计算步骤与流程图与雅可比迭代法大致相同，只是一旦求出变元的某个新值后,就改用新值替代老值进行这一步剩下的计算。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式functionX=gseid(A,B,P,delta,max)%求解AX=B，A是非奇N阶方阵dleta是误差界，max是最大迭代次数N=length(B);fort=1:max

fork=1:Nifk==1X(1)=(B(1)-A(1,2:N)*P(2:N))/A(1,1);elseifk==NX(N)=(B(N)-A(N,1:N-1)*(X(1:N-1))')/A(N,N);elseX(k)=(B(k)-A(k,1:k-1)*X(1:k-1)'-A(k,k+1:N)*P(k+1:N))/A(k,k);endend

err=abs(norm(X'-P));if(err<delta)break;endendX=X';高斯-塞德尔迭代法ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis例6.2.2，按高斯-塞德尔迭代公式迭代7次，得，

用高斯-塞德尔迭代法解下面线性方程组ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis由此例可知，用高斯-塞德尔迭代法，雅可比迭代法解线性方程组(且取)均收敛.而高斯-塞德尔迭代法比雅可比迭代法收敛较快(即取相同，达到同样精度所需迭代次数较少).但这结论只当满足一定条件时才是对的.且ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式超松弛迭代法（SOR方法）使用迭代法的困难在于难以估计其计算量。有时迭代过程虽然收敛，但由于收敛速度缓慢，使计算量变得很大而失去使用价值。因此，迭代过程的加速具有重要意义。

逐次超松弛迭代（SuccessiveOverrelaxaticMethod，简称SOR方法）法，可以看作是带参数的高斯—塞德尔迭代法，实质上是高斯-塞德尔迭代的一种加速方法。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式超松弛迭代法的基本思想

超松弛迭代法目的是为了提高迭代法的收敛速度，在高斯—塞德尔迭代公式的基础上作一些修改。这种方法是将前一步的结果与高斯-塞德尔迭代方法的迭代值适当加权平均，期望获得更好的近似值。是解大型稀疏矩阵方程组的有效方法之一，有着广泛的应用。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式SOR方法⑴用高斯—塞德尔迭代法定义辅助量。⑵把取为与的加权平均，即

合并表示为：

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式SOR方法式中系数ω称为松弛因子，为了保证迭代过程收敛，要求0<ω<2。

当ω=1时，便为高斯-塞德尔迭代法。当0<ω<1时，低松弛法；当1<ω<2时称为超松弛法。但通常统称为超松弛法(SOR)。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式故

令则超松弛迭代公式可写成SOR迭代法的矩阵表示ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式显然对任何一个ω值,(D+ωL)非奇异,(因为假设

)于是超松弛迭代公式为(k=0,1,2,…)ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis例6.2.3它的精确解为取，迭代公式为用SOR方法解方程组解ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.2几种常用的迭代格式取，取其他值，迭代次数如下表.第11次迭代结果为ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis从此例看到，松弛因子选择得好，会使SOR迭代法的收敛大大加速.本例中是最佳松弛因子.ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.3迭代法的收敛性及误差估计对于给定的方程组可以构造成雅可比迭代公式、高斯-塞德尔迭代公式和超松弛迭代公式，但并非一定收敛。现在分析它们的收敛性。对于方程组经过等价变换构造出的等价方程组

在什么条件下迭代序列收敛？ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理6.3.1

迭代公式收敛的充分必要条件是迭代矩阵G的谱半径证:必要性设迭代公式收敛,当k→∞时,则在迭代公式两端同时取极限得记,则收敛于0(零向量),且有

于是由于可以是任意向量,故收敛于0当且仅当收敛于零矩阵，即当时所以必ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis充分性:设,则必存在正数ε,使则存在某种范数

,使,,则,所以

,即。故收敛于0,

收敛于由此定理可知，不论是雅可比迭代法、高斯—塞德尔迭代法还是超松弛迭代法，它们收敛的充要条件是其迭代矩阵的谱半径。

§6.3迭代法的收敛性及误差估计ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理6.3.2

(迭代法收敛的充分条件)若迭代矩阵G的一种范数,则迭代公式收敛,且有误差估计式,且有误差估计式及§6.3迭代法的收敛性及误差估计ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.3迭代法的收敛性及误差估计证:矩阵的谱半径不超过矩阵的任一种范数,已知,因此,根据定理6.3.1可知迭代公式收敛又因为,则det(I-G)≠0,I-G为非奇异矩阵,故x＝Gx＋d有惟一解,即与迭代过程相比较,有ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis∴

两边取范数§6.3迭代法的收敛性及误差估计ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.3迭代法的收敛性及误差估计由迭代格式，有

两边取范数，代入上式，得证毕ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.3迭代法的收敛性及误差估计由定理知，当时，其值越小，迭代收敛越快，在程序设计中通常用相邻两次迭代

（ε为给定的精度要求）作为控制迭代结束的条件ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件迭代法收敛的判别条件：1.Jacobi迭代法（简单迭代法）的收敛判定。2.Gauss-Seidel迭代法的收敛判定。3.SOR迭代法的收敛判定。ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理6.4.1

设n阶方阵为对角占优阵,则它是非奇异的。证:因A为对角占优阵,其主对角元素的绝对值大于同行其它元素绝对值之和,且主对角元素全不为0,故对角阵为非奇异。作矩阵ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件利用对角占优知知非奇异,从而A非奇异,证毕

系数矩阵为对角占优阵的线性方程组称作对角占优方程组。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件定理6.4.2

对角占优线性方程组的雅可比迭代公式和高斯-赛德尔迭代公式均收敛。证:雅可比迭代公式的迭代矩阵为

由定理6.4.1知,这时,再由定理6.3.2知迭代收敛.再考察高斯-赛德尔迭代公式的迭代矩阵ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件令，则有即写出分量形式有设

而由上式得ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.4判别收敛的几个常用条件由此整理得利用对角占优条件知上式右端小于1,(如果右端大于1,则得出与对角占优条件矛盾的结果)故有据定理6.3.2知G-S法收敛ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理6.4.3

当系数矩阵A为正定矩阵，高斯-塞德尔迭代收敛。定理6.4.4

松弛迭代收敛的必要条件是0<ω<2§6.4判别收敛的几个常用条件ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis定理6.4.6

若A为对称正定矩阵时，则松弛迭代收敛的充要条件是.

定理6.4.5(松弛法收敛的充分条件)

如果系数矩阵A为严格对角占优，当松弛因子

时，松弛迭代法收敛。§6.4判别收敛的几个常用条件ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例例6.5.1

已知线性方程组考察用Jacobi迭代和G-S迭代求解时的收敛性解:⑴雅可比迭代矩阵ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例故Jacobi迭代收敛

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例故高斯—塞德尔迭代收敛。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例例6.5.2

设有迭代格式

X(k+1)=BX(k)+g(k=0,1,2……）

其中B=I-A,如果A和B的特征值全为正数，试证：该迭代格式收敛。分析:根据A，B和单位矩阵I之间的特征值的关系导出(B)<1,从而说明迭代格式收敛。

ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例证:因为B=I-A,故(B)=(I)-(A)=1-(A)(A)+(B)=1

由于已知(A)和(B)全为正数，故

0<(B)<1,从而(B)<1

所以该迭代格式收敛。ISCM2007,BeijingChina/68郑州大学研究生2014-2015学年课程数值分析

NumericalAnalysis§6.5迭代法收敛判定的应用举例例6.5.3

设方程组写出解方程组的Jacobi迭代公式和迭代矩阵并讨论迭代收敛的条件