线性方程组的迭代法

1、第四章线性方程组地迭代法第一节 迭代法及其收敛性一、迭代法地一般格式在前面我们已经介绍了解线性方程组【一1） 地一些直接方法，下面我们将简略介绍一下解方程组（1地另一类方法一一迭代 法,所谓迭代法是这样一种方法，对任意给定初始近似，按某种规则逐次生成序列 b5E2RGbCAP使极限（2为方程组（1地解,即设把矩阵A分解成矩阵N和P之差其中N为非奇异矩阵，于是,方程组（1便可以表示成即(3其中11，据此，我们便可以建立迭代公式（4我们称迭代公式（4中地矩阵B为迭代矩阵. 若序列收敛显然有即,极限便是所求方程组地解.定义11）对给定地方程组（3,用公式（4逐步代入求近似解 地方法称为 迭代法（2如

2、果二存在（记为 ,则称迭代法收敛,此时就是方程组地解 否则称此迭代法发散为了讨论迭代公式（4地收敛性，我们引进误差向量.因（5由（3和（4便得到误差向量所满足地方程 亠 （6递推下去,最后便得到（7、迭代法地收敛性若欲由（4所确定地迭代法对任意给定地初始向量-都收敛,则由（7确定地误差向量二应对任何初始误差一都收敛于0. plEanqFDPw定义2若(8则称矩阵序列丄 依范数收敛于由范数地等价性可以推出，在某种范数意义下矩阵序列收敛，则在任何一种范数意义下该矩阵序列都收敛因此，对矩阵序列收敛到矩阵，记为DXDiTa9E3d(9而不强调是在那种范数意义下收敛.从定义及矩阵地行（列范数可以直接推出

3、下面定理定理1设矩阵序列收敛于-地充分必要条件为及矩阵 1 x iJ因此，矩阵序列地收 敛可归结为元素序列地收敛此外,还可以推出下面定理.定理2迭代法(4对任何都收敛地充分必要条件为丨乂 | 1 (10定理3矩阵序列 收敛于0地充分必要条件为W (11证明：如果I ,则在任一范数意义下有而由第六节定理4有所以必有反之，若则存在足够小地正数,使1,则第六节定理5可知,存在范数 丄 使，亠 I .于是因为所以J 即丨定理4 :迭代法(4对任意都收敛地充分必要条件为一1三、迭代法地收敛速度考察误差向量r设B有n个线性无关地特征向量m ,相应地特征值为m ,由得可以看出,当一1愈小时,ri愈快,即亠|

4、愈快,故可用量来刻划迭代法地收敛快慢现在来确定迭代次数k,使(12取对数得定义3 称II*B1(13为迭代法(4地收敛速度.由此看出,1愈小，速度R(B就愈大,(12式成立所需地迭代次数也就愈少.=,则对任意初始向量由于谱半径地计算比较困难，因此，可用范数” B II来作为 地一种估计.定理5如果迭代矩阵地某一种范数迭代公式(4收敛,且有误差估计式(14证明利用定理4和不等式,可以立即证得收敛地充分条件，下面推导误差估计式.因为方程组地精确解，则,则由第六节定理7可知,1-B可逆,且由于两边取范数即得又由于所以有了定理5地误差估计式，在实际计算时，对于预先给定地精度，若有则就认为 I是方程组满

5、足精度地近似解此外,还可以用第二个估计式（15来事先确定需要迭代地次数以保证 u第二节雅可比迭代法与高斯一塞德尔迭代法、雅可比迭代法设线性方程组地系数矩阵A可逆且主对角元素均不为零,令并将A分解成(2从而（1可写成其中(3以为迭代矩阵地迭代法（公式(4称为雅可比Jacobi迭代法（公式,用向量地分量来表示,（4为(5其中为初始向量.由此看出，雅可比迭代法公式简单，每迭代一次只需计算一次矩阵和向量地乘法.在电算时需要两组存储单元,以存放一及匕. RTCrpUDGiT例1用雅可比迭代法求解下列方程组解：将方程组按雅可比方法写成取初始值按迭代公式进行迭代,其计算结果如表1所示表12101234567

6、凶00.720.9711.0571.08531.09511.0983凶00.831.0701.15711.18531.19511.1983凶00.841.1501.24821.28281.29411.2980二、高斯一塞德尔迭代法由雅可比迭代公式可知，在迭代地每一步计算过程中是用地全部分量来计算 地所有分量，显然在计算第i个分量 I时，已经计算出地最新分量没有被利用,从直观上看,最新计算出地分量可能比旧地分量要好些.因此,对这些最新计算出来地第三 次近似 I地分量 二 加以利用,就得到所谓解方程组地高斯一塞德vGauss-Seidel ）迭代法.5pczvd7Hxa把矩阵A分解成（6其中一三二

7、1, 分别为地主对角元除外地下三角和上三角部分,于是,方程组（1便可以写成jLBHrnAlLg即K 1其中以为迭代矩阵构成地迭代法（公式(8到称为高斯一塞德尔迭代法（公式 ,用量表示地形式为(9由此看出，高斯一塞德尔迭代法地一个明显地优点是，在电算时，只需一组存 储单元（计算出丄 后不再使用,所以用丄 冲掉 ,以便存放近似解.XHAQX74J0X例2用高斯一一塞德尔迭代法求解例1.解：取初始值,按迭代公式ri进行迭代,其计算结果如下表2表20123456700.721.043081.0931.099131.099891.099991.113凶00.901.167191.1951.199471.

8、199931.199991.2272凶01.161.282051.2971.299721.299961.31.34477从此例看出，高斯一塞德尔迭代法比雅可比迭代法收敛快（达到同样地精度所需 迭代次数少 ,但这个结论，在一定条件下才是对地，甚至有这样地方程组，雅可比 方法收敛,而高斯一塞德尔迭代法却是发散地.LDAYtRyKfE三、迭代收敛地充分条件定理1在下列任一条件下，雅可比迭代法（5收敛.I定理2设 分别为雅可比迭代矩阵与高斯一塞德尔迭代矩阵，则(10从而，当时,高斯一塞德尔迭代法（8收敛. 证明：由 1地定义,它们可表示成用表示维向量，则有不等式这里,记号表示其中矩阵地元素都取绝对值，

9、而不等式是对相应元素来考虑地,于是容易验证从而有可逆，且因此必有因为已知 二 所以二 即高斯一塞德尔迭代法收敛若矩阵 为对称,我们有定理3若矩阵 正定,则高斯一塞德尔迭代法收敛.证明：把实正定对称矩阵A分解为一口 ,则为正定地,迭代矩阵设是地任一特征值，为相应地特征向量，则以亠左乘上式两端,并由用向量地共轭转置左乘上式两端，得 (11求上式左右两端地共轭转置，得以一和田 分别乘以上二式然后相加,得一_1由，得二_I即(12因为A和D都是正定地,且x不是零向量,所以由(11式得 I ,而由(12式得，即,从而 1,因而高斯一塞德尔迭代法收敛.Zzz6ZB2Ltk定义1设上为n阶矩阵.如果(13即

10、A地每一行对角元素地绝对值都严格大于同行其他元素绝对值之和，则称A为严格对角优势矩阵.如果且至少有一个不等式严格成立，则称A为弱对角优势矩阵例如是严格对角优势矩阵是弱对角优势矩阵定义2 设二是n阶矩阵,如果经过行地互换及相应列地互换可化为即存在n阶排列矩阵P,使其中亠 为方阵,则称A是可约地,否则称A为不可约地.是可约矩阵，意味着|：-：|可经过若干次行列重排，化为两个低阶方程组事实上,亠可化为于是,求解化为求解可以证明，如果A为严格对角优势矩阵或为不可约弱对角优势矩阵，则A是 非奇异地.定理4如果A为严格对角优势矩阵或为不可约弱对角优势矩阵，则对任意 ,雅可比迭代法（4与高斯一塞德尔迭代法（

11、8均为收敛地.dvzfvkwMIl证明：下面我们以A为不可约弱对角优势矩阵为例，证明雅可比迭代法收敛 其他证明留给读者.要证明雅可比迭代法收敛,只要证 3, 是迭代矩阵.用反证法,设矩阵有某个特征值,使得 I ,则 ，由于A不可约,且具有弱对角优势,所以亠存在,且从而另一方面,矩阵与矩阵A地非零元素地位置是完全相同地，所以1也是不可约地，又由于 一1 ,且A弱对角优势,所以并且至少有一个i使不等号严格成立因此，矩阵弱对角优势,故I 为不可约弱对角优势矩阵.从而1 一 矛盾,故 地特征值不能大于等于1,定理得证.第三节超松驰迭代法逐次超松驰迭代法（Successive Over Relaxati

12、on Me thod, 简称 SOR方法 是高斯一塞德尔方法地一种加速方法，是解大型稀疏矩阵方程组地有效方法之一 它具有计算公式简单，程序设计容易，占用计算机内存较少等优点，但需要较好地 加速因子（即最佳松驰因子 .下面我们首先说说松驰一词地含意，再利用它来解 释雅可比迭代法与高斯一塞德尔迭代法，最后给出逐次超松驰迭代法地推算公式 和收敛性条件.rqyn14ZNXI设线性方程组亠 （1其中二1可逆，且对角元素均不为0,如果J 1是（1地近似解,一般说来1 （2不是0,这可理解为 不合格”把不合格地 更换为新地近似解X,希望新地残向 量r变小”想实现这一点地简单方法是每一次只把在（2中地一个式（

13、例如第i个中地一个分量进行更换，使新地残向量地第i个分量变成0.这样,我们就说第i个方程被松弛了 . 一般都把第i个式中第i个元 换掉，这相当于求 使EmxvxOtOco（3因此，雅可比迭代法将代换为I三 地过程,实际上是对 K i n把（4变为L (6(5地过程（松驰地过程.由 代换为 I还可看作是而修正量与修正公式可写成为(7倘若在修正量之前乘以一个因子，即以第i个分量（8为向量作新地近似向量（第k+1次迭代向量 代替原来地就得到所谓带松驰因子地迭代法.注意到,用（8中地 I代替（4中地 ,一般并不能使SixE2yXPq5(9为0,而为11在8）中取二就是（7中地1恰好使新地残量为0,这就

14、使第i个方程松驰了；如，则用 代换第i个方程中地将使残量由变成与有不同符号地新残量，于是我们就说第i个方程被松驰过头了 （超松驰 ,或说被修改过分了（超过了使残量正好为0地程度；如 山则用 代换第i个方程中地时，新残量 与 同号,并且当 时,它地绝对值小于之绝对值,于是我们不妨认为第i个方程还松驰得不够（低 松驰或称被修改得不够，不管是超松驰还是低松驰（ 或 ,我们一概都称为超松驰,即 时，我们称6ewMyirQFL为带松驰因子地同时迭代法（公式.带松驰因子地同时迭代法用处并不大，讲它地目地只是为了解释迭代，修改和松驰地含意，使我们能容易懂得什么是逐次超松驰法.下面介绍什么是逐次 超松驰法.k

15、avU42VRUs类似于高斯一塞德尔迭代法,在（11式中用新地 代替旧地可得其中为高斯一塞德尔迭代所得，所以逐个超松驰迭代法是高斯 一塞德尔迭代法地一种 加速方法,则上式为即丨其中(14(15(14为超松驰迭法(公式地矩阵形式称为其迭代矩陈例：用逐次超松驰迭代法求解方程组解：取,迭代公式取亠计算结果为表3表3012345a00.75961.082021.100881.099981.1 可00.9557881.200591.99891.200051.2凶01.248151.299181.300211.31.3对 取其他值,计算结果满足误差地迭代次数如下:表4pl0.10.20.30.40.50.60.70.80.911.11.21.31.41.51.61.71k16377493426201512966810131722315从此例看到，松驰因子选择得好，会使超松驰迭代法地收敛大大加速使收敛最快地松驰因子称为最佳松驰因子.本例地最佳松驰因子为亠 ,一般地,最佳松驰因子 应满足y6v3ALoS89最佳松驰因子理论是由Youn g(1950年针对一类椭圆型微分方程数值解得 到地代数方程组14，(具有所谓性质A和相容次序所建立地理论，他给出了 最佳松驰因子公式M2ub6vSTnP其