第四章 解线性方程组的迭代法

PAGEPAGE10第四章解线性方程组的迭代法4.1迭代法及其收敛性4.1.1向量序列及矩阵序列的极限定义1.1设中的向量序列，如果存在，使则称向量序列收敛于x,记作同样，矩阵序列，，若有，i,j=1,2,…，n,则称矩阵序列收敛于，记作.概据定义，显然有定理1.1的充分必要条件是(4.1.1)其中两个极限的右端分别指零矩阵与零向量.证明对任一种矩阵从属范数有由,故式(4.1.1)对成立.反之，若取x为第j个坐标向量，则表示第j列元素极限均为零；当j=1,2,…,n时则证明了.证毕.定理1.2的充分必要条件是，其中为谱半径.证明由于，而，当，故有，即，故.反之，当时，由上章定理4.6可知，对任给ε＞0，存在，使，于是从而.证毕.定理1.3设为任一种范数，则(4.1.2)讲解：及矩阵序列的极限是通过向量分量与矩阵元素极限定义的。共收敛充要条件是迭代法收敛性要使用的。为加深理解请看下例：例设，证明，但则不收敛。解根据定理1.2要证明只要证明，先求的特征值，由，可知，故，故对有得，故，由定理1.2知不收敛。4.1.2设非奇异，用迭代法解方程组(4.1.3)首先要构造迭代序列，通常可将方程改写为(4.1.4)并由此构造迭代法(4.1.5)其中称为迭代矩阵.对任意给定的初始向量，由(4.1.5)可求得向量序列.若，则就是方程(4.1.4)(或(4.1.3))的解.定义1.2若迭代法(4.1.5)生成的序列满足则称迭代法(4.1.5)是收敛的.构造的迭代法(4.1.5)是否收敛，取决于迭代矩阵的性质，先看例题.例4.1给定方程组它的精确解,可构造如下迭代法(4.1.6)若写成式(4.1.5)的形式，则迭代矩阵B及f可表示为：若取,按式(4.1.6)迭代10次可得，误差.它表明迭代序列(4.1.6)收敛.对于方程组(4.1.3)，构造迭代法的一般原则是将A分解为A=M-N(4.1.7)其中M非奇异且容易求,则由(4.1.3)可得(4.1.8)其中(4.1.9)这样就得到与(4.1.3)等价的(4.1.8)，从而可构造(4.1.5)的迭代法，将A按不同方式分解为(4.1.7)，就可得到不同的迭代矩阵B，从而得到不同的迭代法.通常为使容易计算，可取M为对角矩阵，三角矩阵或三对角矩阵等.在例4.1中，,.式(4.1.6)就是下节将要讨论的Jacobi迭代法.4.1.3迭代法的收敛性与收敛速度下面讨论迭代法(4.1.5)的收敛性.若则即,故即为方程(4.1.3)的解.令,由(4.1.5)减去等式,则得由此递推得(4.1.10)其中与k无关，所以等价于即.由定理1.2可知，于是有如下定理.定理1.4迭代法(4.1.5)对收敛的充分必要条件是(4.1.11)其中为矩阵B的谱半径.例4.2考察例4.1中迭代法(4.1.6)的收敛性.解由可得.用方程求根方法可解得，故迭代法(4.1.6)收敛.由于计算较困难，通常可利用判断迭代法的收敛性.在本例中由于，故迭代法(4.1.6)收敛.于是，迭代法(4.1.5)收敛的充分条件如下.定理1.5对迭代法(4.1.5)，如果迭代矩阵B的某种范数，则对及，迭代序列均收敛于，且有误差估计(4.1.12)证明由于，故由定理1.4得收敛于.又由(4.1.5)知于是即为(4.1.12)，证毕.注意，定理只给出迭代序列(4.1.5)收敛的充分条件，即使条件‖B‖＜1对任何范数都不成立，迭代序列仍可能收敛.例4.3设，其中，讨论迭代序列的收敛性.解显然表明B的范数均大于1，但由于，故由定理1.4知此迭代序列是收敛的.

下面考察迭代法(4.1.5)的收敛速度.由(4.1.10)得于是(4.1.13)根据算子范数定义可知所以是迭代k次后误差向量的范数与初始误差向量的范数之比的最大值.若要求迭代k次后

这里是一个小数，通常ε<<1，所以，由，两边取对数可得(4.1.14)它表明迭代步数k与成反比，即(4.1.15)愈大，迭代次数k愈少.于是可定义(4.1.15)式中的量为迭代法的平均收敛速度.它依赖于所取的范数，若利用定理1.3的(4.1.2)式则有定义1.3称为迭代法(4.1.5)的渐近收敛速度.显然，它与B取何种范数无关.由于迭代法(4.1.5)收敛，故，越小，越大，迭代法收敛越快，且当迭代次数k满足时，有.例4.4对例4.1中的迭代序列(4.1.6)要使相对误差，至少要迭代几次?解因(4.1.6)中迭代矩阵B的谱半径，，，因此取k=12,即为所求.讲解：求解可改为，从而有，为迭代收敛得充分必要条件。而为迭代法（4.1.5）收敛得充分条件，使用时只要有一种范数满足条件迭代法就收敛。当，则就是方程得组得解，且有误差估计（4.1.12）衡量迭代法收敛快慢可由（称为收敛速度）得大小决定。越大迭代序列收敛越快。4.2Jacobi迭代法与Gauss-Seidel迭代法4.2.1Jacobi迭代法将方程组(4.1.3)中系数矩阵分解为(4.2.1)其中为A的对角矩阵，假定(i=1,2,…，n)，则D非奇异.取M=D,N=L+U,则得(4.2.3)(4.2.4)(4.2.3)称为解方程组的Jacobi迭代法，简称J法.计算时可写成如下分量形式：(4.2.5)例4.1中的迭代(4.1.6)就是Jacobi迭代法.将定理1.4与定理1.5用于J法就有如下定理.定理2.1J法