第6章_解线性方程组的迭代法计算方法

1、结束结束第第6 6章章 解线性方程组的迭代法解线性方程组的迭代法 线性方程组的直接法，用于阶数不太高的线性方程组效线性方程组的直接法，用于阶数不太高的线性方程组效果较好果较好. .实际工作中有的线性方程组阶数很高，但其中的大实际工作中有的线性方程组阶数很高，但其中的大多数系数为多数系数为0 0，这一类的线性方程组的系数阵称为稀疏矩阵，这一类的线性方程组的系数阵称为稀疏矩阵. .稀疏矩阵的存贮和计算有一套技术处理，可以节约大量的存稀疏矩阵的存贮和计算有一套技术处理，可以节约大量的存贮空间和计算工作量贮空间和计算工作量. .用直接法计算时，因一次消元就可以用直接法计算时，因一次消元就可以使系数阵丧

2、失其稀疏性，不能有效利用其稀疏的特点使系数阵丧失其稀疏性，不能有效利用其稀疏的特点. .下文下文介绍的介绍的迭代法就有保持系数阵稀疏的优点，此外迭代法也常迭代法就有保持系数阵稀疏的优点，此外迭代法也常用来提高已知近似解的精度用来提高已知近似解的精度.6.1 6.1 迭代法的一般形式迭代法的一般形式线性方程组线性方程组 Ax=b (6.1) (6.1)其中其中A非奇异，非奇异，b00，因而它有唯一非零解，因而它有唯一非零解. . 1构造与构造与(6.1)(6.1)等价的方程组等价的方程组 x= =Bx+ +f (6.2) (6.2)即使得即使得(6.2)(6.2)与与(6.1)(6.1)同解，其

3、中同解，其中B是是nn矩阵，矩阵，f是是n维向量维向量.结束结束则有则有 x=Bx +f，即，即x是是(6.2)的解，当然的解，当然x也就是也就是Ax=b的解的解.任取一个向量任取一个向量x(0)作为作为x的近似解，用迭代公式的近似解，用迭代公式 x(k+1)=Bx(k)+f, (k=0,1,2,) (6.3)产生一个向量序列产生一个向量序列x(k)，若，若xxkk)(lim 从以上的讨论中，可以看出，迭代法的关键有：从以上的讨论中，可以看出，迭代法的关键有： 1 如何构造迭代公式如何构造迭代公式x(k+1)=Bx(k)+f ？这样的构造形式不止？这样的构造形式不止一种，它们各对应一种迭代法一

4、种，它们各对应一种迭代法. 2 迭代法产生的向量序列迭代法产生的向量序列x(k)的收敛条件是什么，收敛速的收敛条件是什么，收敛速度如何度如何.后面将进行讨论后面将进行讨论.6.2 几种常用的迭代法公式几种常用的迭代法公式6.2.1 简单迭代法简单迭代法 2结束结束按下式进行迭代按下式进行迭代 (k=0,1,2, )24 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 0)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkkkkkkxxxxxxxxx先看一个算例：先看一个算例：例例1 从以上三个方程中分别解出从以上三个方程中分别解出x1, x2, x3。

5、1052151023210321321321xxxxxxxxx 324 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 0213312321xxxxxxxxx结束结束 任取一初始向量，例如任取一初始向量，例如x(0)=(0,0,0)T，得到迭代序列，得到迭代序列x(k) (k=0,1,2,)，列表如下表，列表如下表6-1。容易验证，原方程组的精确解为容易验证，原方程组的精确解为 x = (1,2,3) T，从上面的计，从上面的计算可看出，算可看出，x(k)收敛于精确解收敛于精确解.一般说来，对方程组：一般说来，对方程组： i=1,2,，n (6.4)并设并设aii0(

6、i=1,2,n)，从第，从第i个方程解出个方程解出xi，得等价的方程组，得等价的方程组：njijijbxa1k012345678x100.30000.80000.91800.97160.98040.99620.99850.9998x201.50001.76001.92601.97001.98971.99611.99861.9998x302.00002.66002.95402.95402.98232.99382.99772.9997 4迭代公式为：迭代公式为：结束结束 i=1,2,=1,2, ,n (6.5) (6.5)nijjjijiiiiiixaaabx11111)()()1(1ijnijk

7、jijkjijiiiiikixaxaaabx(6.6)(6.6) 这种迭代形式称为简单迭代法，也称雅可比这种迭代形式称为简单迭代法，也称雅可比(Jacobi)(Jacobi)迭迭代法代法. .,2, 1 ,0,2, 1kni雅可比迭代法雅可比迭代法的矩阵迭代形式的矩阵迭代形式: (推导推导)bDfULDBfxBxJJJkJk11)()1(),(其中， 5结束结束6.2.2 塞德尔塞德尔 (Seidel) 迭代法迭代法 在简单迭代法的迭代形式在简单迭代法的迭代形式(6.6)中，可以看出，在计算中，可以看出，在计算 时，要使用时，要使用 .但此时但此时 已计算出来已计算出来.看来此时可提前使看来此

8、时可提前使用用 代替代替 ，一般地，计算，一般地，计算 (ni2)时，使时，使用用 代替代替 (i p1)，这样可能收敛会快一些，这就，这样可能收敛会快一些，这就形成一种新的迭代法，称为塞德尔迭代法。形成一种新的迭代法，称为塞德尔迭代法。)(1kx) 1(2kx)1(1kx)(1kx)1(1kx)1( kix)1( kpx)(kpx例例2 用塞德尔迭代法计算例用塞德尔迭代法计算例1并作比较并作比较.解解 迭代公式为：迭代公式为：24 . 02 . 05 . 11 . 02 . 03 . 01 . 02 . 0)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kkkkkkkkkx

9、xxxxxxxx(k=0,1,2, ) 6结束结束用它计算得到的序列用它计算得到的序列x(k)列表如表列表如表6-2：可见它对这一方程组比简单迭代法收敛快一些。可见它对这一方程组比简单迭代法收敛快一些。塞德尔迭代法的公式如下：塞德尔迭代法的公式如下：111)()1()1(1ijnijkjijkjijiiiiikixaxaaabx, 2 , 1 , 0, 2 , 1kni(6.7)(6.7) Seidel 迭代法的矩阵迭代形式：迭代法的矩阵迭代形式： （推导推导）bLDfULDBfxBxsssksk11)()1()(,)(其中 7k0123456x100.30000.88040.98430.99

10、780.99971.0000 x201.50001.94481.99221.99891.99982.0000 x302.68402.95392.99382.99912.99993.0000结束结束6.2.3 逐次超松弛法逐次超松弛法(SOR方法方法)逐次超松弛法可看成塞德尔迭代法的加速，塞德尔迭代法逐次超松弛法可看成塞德尔迭代法的加速，塞德尔迭代法是逐次超松弛法的特例是逐次超松弛法的特例.将塞德尔迭代法的将塞德尔迭代法的(6.7)式式111)()1()1(1ijnijkjijkjijiiiiikixaxaaabx改写为改写为11111ijnijkjijkjijiiikikixaxabaxx)(

11、)()()(11111ijnijkjijkjijiiikikikixaxabaxxr)()()()()(记11111ijnijkjijkjijiiikikikikixaxabaxrxx)()()()()()(则 8结束结束称此公式为逐次超松弛法称此公式为逐次超松弛法(SOR法法).从从(6.9)式不难推出式不难推出SOR方法的矩阵迭代形式：方法的矩阵迭代形式：bLDfUDLDBfxBxkk11)()1()(, )1()(其中为加快收敛，在增量为加快收敛，在增量 前加一个因子前加一个因子 ，得，得)(kir) 20()8 . 6(11)()1()()1(ijnijkjijkjijiiikikix

12、axabaxx)9 . 6(1111)() 1()() 1(ijnijkjijkjijiiikikixaxabaxx）（或改写为下面定理下面定理6.8可以看到，必须取可以看到，必须取02，当，当=1时，就是时，就是Seidel迭代法迭代法.当当取得适当时，对塞德尔迭代法有加速效果取得适当时，对塞德尔迭代法有加速效果. 9结束结束例例3 用塞德尔迭代法和取用塞德尔迭代法和取=1.45的逐次超松弛法计算下列方的逐次超松弛法计算下列方程组的解，当程组的解，当 时退出迭代，初值取时退出迭代，初值取x(0)=(1,1,1)T 。7110|max)()(kikixx3322242024321321321x

13、xxxxxxxx由表由表6-和表和表6-可见，达到同样的精度可见，达到同样的精度Seidel迭代法要迭代法要72步，而取步，而取=1.45的逐次超松弛法只要的逐次超松弛法只要25步，可见当松弛因步，可见当松弛因子选择适当时，逐次超松弛法有明显加速收敛作用，它常子选择适当时，逐次超松弛法有明显加速收敛作用，它常用于求解大型线性方程组。用于求解大型线性方程组。 10结束结束6.3 迭代法的一般形式的收敛条件迭代法的一般形式的收敛条件6.3.1 一般迭代过程一般迭代过程 在什么条件下收敛在什么条件下收敛.定理定理6.1 对任意初始向量对任意初始向量x(0)和和f, 由上式产生的迭代序列由上式产生的迭

14、代序列x(k)收敛的充要条件是收敛的充要条件是(B)1.证证: 1)必要性：必要性：,*)(*)(xxfBxxxxkkk记有收敛于设fBxxkk)()(1 11.)(011*)(*)(*) 1(1kkkkkkkkBBBxxBfBxfBxxx有有.1)(0, 0lim, )(0也是任意的，,01*)0(0)0(BBkBxxxkkk章定理有由第必须有要有对任意的结束结束2)充分充分性：性：的特征值，不是则设BB1, 1)(定理定理6.1是迭代法收敛的基本定理，它不但能判别收敛，也能是迭代法收敛的基本定理，它不但能判别收敛，也能判别不收敛的情况判别不收敛的情况.但由于但由于(B)的计算往往比解方程组

15、本身更困的计算往往比解方程组本身更困难，所以本定理在理论上的意义大于在实用上的意义难，所以本定理在理论上的意义大于在实用上的意义.从上面的定理可以看到，迭代法的收敛与否与从上面的定理可以看到，迭代法的收敛与否与B的性态有关，的性态有关，与初始向量与初始向量x(0)和右端向量和右端向量 f 无关。无关。. 12成立，即有唯一解，记为于是有fBxxxfxBIBI*.)(, 0|.)(011*)(*)1(仍成立仍成立，则kkkkBxxBxx.lim,0lim.0lim0*)(成立即所以章定理有由第xxBkkkkkk结束结束定理定理6.2 若若|B|=q1，则由迭代格式，则由迭代格式x(k+1)=Bx

16、(k)+f 和任意初和任意初始向量始向量x(0)产生的迭代序列产生的迭代序列x(k)收敛于准确解收敛于准确解x*。本定理是迭代法收敛的充分条件，它只能判别收敛的情况本定理是迭代法收敛的充分条件，它只能判别收敛的情况，当，当|B|1时，不能断定迭代不收敛。但由于时，不能断定迭代不收敛。但由于|B|,特别是特别是|B|1和和|B|的计算比较容易，也不失为一种判别收敛的方法的计算比较容易，也不失为一种判别收敛的方法。同时当同时当|B|1时可以用来估计迭代的次数，或用来设置退出时可以用来估计迭代的次数，或用来设置退出计算的条件。计算的条件。 13 由于由于 (B)难于计算，而由第二章定理难于计算，而由

17、第二章定理4有有(B) |B| ，|B|1时，必有时，必有 (B) 1，于是得到：，于是得到： 14)10.6(|1|)1()0(*)(xxqqxxkk利用此定理可以在只计算出利用此定理可以在只计算出x(1)时，就估计迭代次数时，就估计迭代次数k，但估，但估计偏保守，次数偏大计偏保守，次数偏大.定理定理6.4 若若|B|=q1 ，则，则x(k)的第的第k次近似值的近似程度有如下次近似值的近似程度有如下估计式：估计式：)11.6(|1|)()1(*)1(kkkxxqqxx本定理可用于程序中设置退出条件，即只要相邻两次的迭代本定理可用于程序中设置退出条件，即只要相邻两次的迭代结果之差足够小时，迭代

18、向量对精确解的误差也足够小结果之差足够小时，迭代向量对精确解的误差也足够小.定理定理6.3 若若|B|=q1，则迭代格式，则迭代格式x(k+1) =Bx(k)+f产生的向量序产生的向量序列列 x(k)中中结束结束.,3212421245211102121021AA例例4 就例就例1中的系数阵中的系数阵A1和例和例3中的系数阵中的系数阵A2讨论简单迭代讨论简单迭代法和塞德尔迭代法的收敛性法和塞德尔迭代法的收敛性.因为因为|BJ|=0.61，由定理，由定理6.2知简单迭代法收敛。知简单迭代法收敛。.)(0402010020102001ULDBJ解：解：1）就）就A1讨论讨论.)(068005600

19、1200400102001ULDBS因为因为|BS|=0.31，由定理，由定理6.2知知Seidel迭代法收敛。迭代法收敛。 15结束结束用定理用定理6.2无法判断简单迭代法收敛性，现计算无法判断简单迭代法收敛性，现计算(BJ)。.)(0323121021412101ULDBJ2）就）就A2讨论讨论.|061323231212141213IBJ解之有三实根：解之有三实根：1=0.9207, 2 =-0.2846, 3 =-0.6361.所以所以(BJ)=0.92071，故简单迭代法收敛，故简单迭代法收敛. 16结束结束.)(21310854104121000020012032142411ULD

20、BS|BS|=0.875，故塞德尔迭代法收敛，故塞德尔迭代法收敛.6.3.2 从矩阵从矩阵A判断收敛的条件判断收敛的条件 能否直接由矩阵能否直接由矩阵 A 的性态，讨论的性态，讨论 Ax = b 使用迭代法使用迭代法是否收敛是否收敛. .讨论前必须先介绍几个概念：讨论前必须先介绍几个概念：1.1.对角优势对角优势 若若 A=(=(aij) )n nn n 满足满足且至少有一个且至少有一个i值，使值，使 成立，称成立，称A具有具有对角优对角优势势；niaanijjijii, 211nijjijiiaa1 17结束结束若若 称称A具有具有严格对角优势严格对角优势.niaanijjijii, 2 ,

21、 11定理定理6 6. .5 5 若若 A 具有严格对角优势，则具有严格对角优势，则A非奇异。非奇异。2. 2. 不可约不可约 如果矩阵如果矩阵 A 能通过行对换和相应的列对换，能通过行对换和相应的列对换，变成：变成： 的形式，的形式，其中其中 A11 和和 A22 为方阵，为方阵，则称则称 A 可约可约，反之称，反之称 A 不可约不可约.2212110AAA定理定理6 6. .6 6 A不可约，且具有对角优势，则不可约，且具有对角优势，则A非奇异非奇异. .以上两个定理的证明要使用较多的数学知识，本书从略以上两个定理的证明要使用较多的数学知识，本书从略.定理定理6 6. .7 7 A 具有严

22、格对角优势或具有严格对角优势或 A 不可约且具有对角优不可约且具有对角优势，则简单迭代法和塞德尔迭代法都收敛势，则简单迭代法和塞德尔迭代法都收敛. .证明：证明： 18定理定理6.8 逐次超松弛法收敛的必要条件是逐次超松弛法收敛的必要条件是02.例例5 5 用定理用定理6 6.5.5检验例检验例1 1中方程组的矩阵中方程组的矩阵A ，判断该方程组，判断该方程组用迭代法时是否收敛？用迭代法时是否收敛？ 解解 因为因为52111021210A 10 10 -2+-1-2+-1， 10 10 -2+-1 -2+-1， 5 5 -1+-2 -1+-2，所以，所以A A具有严格对角优势，具有严格对角优势，该方该方程组用程组用简单迭代法和塞德尔简单迭代法和塞德尔迭代法时收敛。迭代法时收敛。结束结束 定理定理6.9 如果如果A实实对称正定对称正定，且，且02，则逐次超松弛法收敛，则逐次超松弛法收敛.推论推论: 当当A实对称正定时，实对称正定时，Ax=b使用塞德尔迭代法收敛使用塞德尔迭代法收敛. 最后提一下关于最后提一下关于的选取，的选取，的选取影响的选取影响(B) 的大小，使的大小，使(B)最小的最小的值称为最佳松弛因子，记为值称为最佳松弛因子，记为 opt. opt