计算方法第六章print课件.ppt

1、第六章第六章 解线性方程组的迭代法解线性方程组的迭代法6.1 引言6.2 基本迭代法6.3 迭代法的收敛性6.4 分块迭代法6.1 引言引言 本章介绍求解线性方程组 的迭代求解方法，其中 ，。假设 非奇异，则方程组有唯一解 。本章介绍迭代法的一些基本理论及Jacobi迭代法，Gauss-Seidel迭代法，超松弛迭代法等常用迭代法。n迭代法的例例：用迭代法求解线性方程组：记为：，其中：Axbn nAR,nx bRA*12(,)Tnxx xx123123123971081513xxxxxxxxxAxb12391171 101,811 1513xAxxbx 6.1 引言引言已知其精确解为：。现将方

2、程组改写成如下的等价形式：或写为 ，其中：*(1,1,1)Tx 1232133121179991181010101113151515xxxxxxxxx0 xB xf011709991180,10101011130151515Bf6.1 引言引言由此建立迭代格式（公式）：给定初始向量：，则可得：当 时，有：，得近似解：，由此可以看出由迭代法产生的向量序列 逐步逼近方程组的精确解 。(0)(0,0,0)Txk1234x10.7780.9630.9930.999x20.8000.9640.9930.999x30.8670.9720.9950.999(4)(3)(4)210 xxx4k(4)(0.99

3、9,0.999,0.999)Tx()kx(1)()()123(1)()()213(1)()()3121179991181010101113151515kkkkkkkkkxxxxxxxxx*x6.1 引言引言例2：考虑方程组：，取初值 ，则有：可见不收敛。因此，我们得到：对于任何一个方程组 ，由迭代法产生的向量序列 不一定收敛。为做进一步研究，我们假设方程组 有唯一解 ，则 ，又设 为任意初始向量，按下列公式构造向量序列：其中表示迭代次数，我们给出如下的定义：定义1：上述求解方法称为迭代法，如果 存在，则称迭代法收敛，否则称为迭代法发散。12212535xxxx(0)(0,0)Tx(1)(2)(

4、3)(4)(5,5),(15,20),(45,50),(105,140),TTTTxxxxxBxf()kxxBxf*xBxf*x(0)x(1)(),0,1,2,kkxBxfkk()limkkx6.1 引言引言为讨论收敛性，引进误差向量 ，从而可得：，递推得到：要研究 的收敛性，就要研究 在满足什么条件时有 ，实际就是(1)(1)*kkxx(1)()*()()(0,1,2,)kkkB xxBk()(1)(0)kkkBB()kxB()lim0kk()kBk 06.2 基本迭代法基本迭代法 设有方程组 ，其中 为非奇异矩阵下面研究如何建立解方程组 的各种迭代法。将 分裂为 ，其中 为可选择的非奇异矩

5、阵，且使 容易求解，一般选择为 的某种近似称 为分裂矩阵。于是，求解 转化为求解 ，即求解：这样，可构造迭代法：其中：称为迭代法的迭代矩阵，选取 阵，就得到解 的各种迭代法。Axb()n nijAaRAAxbAMNMMxdAMAxbMxNxb11xMNxM b(0)(1)()(0,1,)kkxxBxfk取为初始向量1111(),BMNMMAIMAfM b1BIMAMAxb6.2 基本迭代法基本迭代法 设 ，并将 写为三部分：nJacobi迭代法 由 ，选取 为 的对角元素部分，即选取 ，可得Jacobi迭代公式：其中 称 为解 的Jacobi迭代法的迭代矩阵。11121222121200000

6、0nnnnnnaaaaaaAaaa -0(1,2,)iiainADLU0(1,2,)iiainAMMDADN(0)(1)()(0,1,)kkxxBxfk取为初始向量111(),BID ADLUJfD bJAxb6.2 基本迭代法基本迭代法nJacobi迭代法的分量表示 记由Jacobi迭代公式可得：，写成分量形式即为：于是，解 的Jacobi迭代法的计算公式为：由此可知，Jacobi迭代法计算公式简单，每次迭代只需计算一次矩阵和向量的乘法且计算过程中 不变。()()()()1(,)kkkkTinxxxx(1)()()kkDxLU xb1(1)()()11(1,2,)inkkkiiiijjijj

7、ijj ia xa xa xbin Axb(0)(0)(0)(0)121(1)()()11(,),(1,2,)(0,1,Tninkkkiiijjijjiijj ixxxxxba xa xaink 表示迭代次数）A6.2 基本迭代法基本迭代法nGauss-Seidel迭代法 我们再来分析前面的例子，其实在求 时，我们已经求得了 ，然而我们此时并没有用到 来计算 ，这使我们想到，应该尽可能利用已经计算出来得新的值，因此，可将上面的迭代公式改为：这就是所谓的Gauss-Seidel迭代法，用分裂矩阵的语言，这时选取的分裂矩阵 为 的下三角部分，即选取 ，于是由得到Gauss-Seidel迭代法：(1

8、)2kx(1)1kx(1)1kx(1)2kx(1)()()123(1)(1)()213(1)(1)(1)3121179991181010101113151515kkkkkkkkkxxxxxxxxxMAMDLAMN6.2 基本迭代法基本迭代法其中 称 为解方程组 的Gauss-Seidel迭代矩阵。至于Gauss-Seidel迭代法的分量表示，我们可由矩阵表示得到：即：写成分量形式得到：111()(),(),BIDLADLUGfDLb(0)(1)()(0,1,)kkxxBxfk取为初始向量GAxb(1)()(),kkDL xUxb(1)(1)(),kkkDxLxUxb(0)(0)(0)(0)12

9、1(1)(1)()11(,),(1,2,)(0,1,Tninkkkiiijjijjiijj ixxxxxba xa xaink 表示迭代次数）6.2 基本迭代法基本迭代法nJacobi迭代法和Gauss-Seidel迭代法的异同：Jacobi迭代法公式简单，每次只需做矩阵和向量的一次乘法，特别适合于并行计算；不足之处是需要存放 和 的两个存储空间。Gauss-Seidel方法只需要一个向量存储空间，一旦计算出 立即存入 的位置，可节约一套存储单元这是对Jacobi方法的改进，在某些情况下，它能起到加速收敛的作用。但它是一种典型的串行算法，每一步迭代中，必须依次计算解的各个分量。()kx(1)k

10、x(1)kjx()kjx6.2 基本迭代法基本迭代法n解大型稀疏线性方程组的逐次超松弛法 选取分裂矩阵 为带参数的下三角矩阵其中 为可选择的松弛因子，于是构造迭代法如下：其中：这就是解 的 逐次超松弛迭代法(SOR方法)。其分量形式为：M1()MDL011()()(1)LIDLADLDU(0)(1)()(0,1,)kkxxL xfk取为初始向量Axb(0)(0)(0)(0)121(1)()(1)()11(,),(1,2,)(0,1,Tninkkkkiiiijjijjiijj ixxxxxxba xa xaink 表示迭代次数）,为松弛因子6.2 基本迭代法基本迭代法n关于SOR方法的几点注释：

11、(1)显然，当 时，SOR方法就是Gauss-Seidel方法。(2)SOR方法每一次迭代的主要运算量是计算一次矩阵 与向量的乘法。(3)时称为超松弛方法，时称为低松弛方法。(4)计算机实现时可用 控制 迭代终止，或用 控制终止。(5)SOR方法可以看成是Gauss-Seidel方法的一种修正。111(1)()11maxmaxkkiiii ni nxxx ()()kkrbAx6.3 迭代法的收敛性迭代法的收敛性 例：分别用Jacobi迭代法和Gauss-Seidel迭代法计算下列方程组，均取同样的初值 ，观察其计算结果。解：对方程组1，其精确解 Jacobi迭代得：Gauss-Seidel迭代

12、得：对方程组2，其精确解 Jacobi迭代得：125次迭代可得精度为0.01的解；Gauss-Seidel迭代得：9次迭代可得精度为0.01的解；对方程组3，其精确解 Jacobi迭代得：Gauss-Seidel迭代得：(0)(1,1,1)Tx1231231239101(1)950874xxxxxxxxx 123123123531(2)24034154xxxxxxxxx 12312312310451(3)4107057104xxxxxxxxx*(0.4511,1.2383,1.0596)Tx (4)(7666,7023,3327)Tx(3)(10978,92687,736077)Tx*(0.0

13、984,1.1639,0.5547)Tx *(0.3658,0.5132,0.9421)Tx (299)101010(0.35 10,0.41 10,0.43 10)Tx(300)101010(0.38 10,0.45 10,0.47 10)Tx(6)(0.366,0.514,0.943)Tx(7)(0.366,0.514,0.942)Tx 6.3 迭代法的收敛性迭代法的收敛性 设 ，其中 为非奇异矩阵，记 为方程的精确解，的等价方程组为：，于是：设有解方程组 的一阶定常迭代法：我们希望研究的问题是：迭代矩阵满足什么条件时，迭代法产生的迭代序列 收敛到 。引进误差向量其递推公式为：由本章引言可

14、知：我们要研究的问题就是 满足什么条件时，有Axbn nARAxbxBxf*xBxfAxb(1)()kkxBxf()kx*x*x()()*(0,1,2,)kkxxk(1)()()(0),(0,1,2,)kkkkBBk()kBk 0B6.3 迭代法的收敛性迭代法的收敛性 定义2：设有矩阵序列 及 ，如果 个数列极限存在且有则称 收敛于 ，记为 。例：设有矩阵序列且设 ，考查其极限。解：显然，当 时，有 矩阵序列极限概念可以用矩阵算子范数来描述。定理1：，其中 为矩阵的任意一种算子范数。()()kn nkijAaR()n nijAaR2n()lim(,1,2,)kijijkaai jnkAAlim

15、kkAA1212,000kkkkkAAA1100limlim00kkkkAAlimlim0kkkkAAAA 6.3 迭代法的收敛性迭代法的收敛性 证明：显然有再利用矩阵范数的等价性，可证定理对其他算子范数亦对。定理2：对任何向量 都有 定理3：设 ，则 的充分必要条件是矩阵 的谱半径 。证明：由矩阵 的若当标准型，存在非奇异矩阵 使 其中若当块limlim0kkkkAAAAlimkkAAnxRlimkkA xAx()n nijBbRlim0kkBB()1BBP121,rJJP BPJJ11iiiiiinnJ6.3 迭代法的收敛性迭代法的收敛性且 ，显然有：，其中：于是 下面考查 的情况，引进记

16、号：显然有：，由于因此：1riinn11,kkBPJPBPJ P12kkkkrJJJJlim0lim0lim0(1,2,)kkkikkkBJJirkiJ,0()00t tt kiItkERtn,0,1,0(),()ktt ktt kEI EktEE,1iitJIE1,1,1,00()()kikkjkjjjkjiitkitkit jjjJIECECE6.3 迭代法的收敛性迭代法的收敛性利用极限 得到所以 的充要条件是 ，即定理4：（迭代法基本定理）设有方程组 ，对于任意的初始向量 ，一阶定常迭代法 收敛的充要条件是迭代矩阵 的谱半径 。11221(1)112(2)11kkktktikikikik

17、ktktikikikkikiCCCCCC lim0(01,0)rkkk ccrlim01jkjkkClim0kikJ1(1,2,)iir()1BxBxf(1)()kkxBxf(0)xB()1B6.3 迭代法的收敛性迭代法的收敛性证：的特征值 ，故 的特征值 从而有：，因此 有唯一解 。定义 为误差向量，则有：故对任意的 和 ，有：即：设对任意的 和 ，均有：且于是有 ，即 ，所以对任意的 有 故 ，从而由定理3，有 。定理4是一阶定常迭代法的基本理论。()1,BB1,(1,2,)iinIB10,(1,2,)iiin 1det()(1)0niiIBxBxf*x()()*kkxx()()*(1)*

18、(1)(0)()kkkkkxxB xxBB(0)xf()(0)limlim0kkkkB()*limkkxx(0)xf()*lim,kkxx()(0)kkeB e()*(0)*()kkxxBxx(0)x(0)*lim()0,kkBxxlim0kkB()1B*xBxf6.3 迭代法的收敛性迭代法的收敛性 推论：设 ，其中 为非奇异矩阵且 非奇异，则：(1)解方程组的Jacobi迭代法收敛的充要条件是其中 (2)解方程组的Gauss-Seidel迭代法收敛的充要条件是 ，其中 (3)解方程组的SOR迭代法收敛的充要条件是其中AxbADLUD()1J1()JDLU()1G1()GDLU()1L1()(

19、1)LDLDU6.3 迭代法的收敛性迭代法的收敛性 迭代法的基本定理在理论上有重要意义。在具体使用上，由于 ，因此，我们利用范数可以建立判别迭代法收敛的充分条件。定理5：（迭代法收敛的充分条件）设方程组 的一阶定常迭代法为如果有 的某种算子范数 ，则 (1)迭代法收敛，即对任取 有 且 (2)(3)(4)()BBxBxf(1)()kkxBxf1BqB(0)x()*limkkxx*xBxf*()*(0)kkxxqxx*()()(1)1kkkqxxxxq*()(1)(0)1kkqxxxxq6.3 迭代法的收敛性迭代法的收敛性证明：(1)由定理4，结论(1)是显然的；(2)由 及 得：(a)(b)反

20、复利用(b)即得(2)；(3)注意到即得：(4)反复利用(a)即得(4)。*(1)*()()kkxxB xx(1)()()(1)()kkkkxxB xx(1)()()(1)kkkkxxq xx*(1)*()kkxxq xx(1)()*()*(1)()kkkkxxxxxx*()*(1)*()(1)kkkxxxxqxx*()(1)()()(1)111kkkkkqxxxxxxqq6.3 迭代法的收敛性迭代法的收敛性n关于解某些特殊方程组迭代法的收敛性 定义3：(对角占优阵)设(1)如果 元素满足称 为严格对角占优阵(2)如果 元素满足且上式至少有一个不等式严格成立，称 为弱对角占优阵。()ijn n

21、AaA1(1,2,)niiijjj iaainAA1(1,2,)niiijjj iaainA 6.3 迭代法的收敛性迭代法的收敛性 定义4：(可约与不可约矩阵)设 ，如果存在置换阵 使其中 为 阶方阵，为 阶方阵 ，则称 为可约矩阵，否则，如果不存在这样的置换阵 使得上式成立，则称 为不可约矩阵。()(2)ijn nAanP1112220TAAP APA11Ar22Anr(1)rnAAP6.3 迭代法的收敛性迭代法的收敛性 定理6：(对角占优定理)如果 为严格对角占优矩阵或 为不可约弱对角占优矩阵，则 为非奇异矩阵。证明：我们只就严格对角占优证明定理。采用反证法。，则 有非零解，记为 则 ，由

22、齐次方程组第 个方程得到 ，即与对角占优的假设矛盾，故 。()ijn nAaAAdet()0A 0Ax 12(,)Tnxx xx1max0kii nxx k10nkjjja x111nnnkkkkjjkjjkkjjjjj ij kj ka xa xaxxa1nkkkjjj kaadet()0A 6.3 迭代法的收敛性迭代法的收敛性 定理7：设 ，如果：(1)为严格对角占优，则解 的Jacobi迭代法，Gauss-Seidel迭代法均收敛。(2)为弱对角占优，且 为不可约矩阵，则解 的Jacobi迭代法，Gauss-Seidel迭代法均收敛。证明：这里我们仅证(1)的Gauss-Seidel迭代

23、法。由假设可知：，Gauss-Seidel迭代矩阵为 ，因此由于 于是 的特征值为 的根，记AxbAAAAxbAxb0(1,2,)iiain1()GDLU1det()det()IGIDLU1det()det()DLDLU1det()0,DLGdet()0DLU111212122212()nnnnnnaaaaaaCDLUaaa6.3 迭代法的收敛性迭代法的收敛性下面证明：当 时，即 的特征值均满足 ，由基本定理，则有Gauss-Seidel迭代法收敛。事实上，当 时，由 A 为严格对角占优，有这说明，当 时，矩阵 为严格对角占优，再由对角占优定理有 。定理8：(SOR方法收敛的必要条件)设解方程

24、组的SOR迭代法收敛，则 。证明：由SOR迭代法收敛，则可得 ，设 的特征值为 ，则 从而1det()0C G11det()0C 1C1111111ininniiiiijijijijijjj ijj ijj icaaaaac (1,2,)in02()1LL12,n 12det(),()nnLL 1/det()()1nLL6.3 迭代法的收敛性迭代法的收敛性另一方面从而 ，即 。定理9：设 ，如果：(1)为对称正定矩阵，(2)则解 的SOR迭代法收敛。证明：我们只需在上述假设下，证明 即可。事实上，设 为对应于 的特征向量，即亦即：为了找到 的表达式，考虑数量积1det()det()det(1)

25、(1)nLDLDU1/det()11nL02AxbA02Axb1y12,(,)0TnL yyyy yy1()(1)DLDU yy(1)()DU yDL y(1),)(),)DU y yDL y y6.3 迭代法的收敛性迭代法的收敛性则显然记：由于 ，所以 ，故所以从而(,)(,)(,)(,)(,)Dy yDy yUy yDy yLy y21(,)0niiiiDy ya y(,)Ly yiTAATUL(,)(,)(,)Uy yy LyLy yi 0(,)(),)2Ay yDL U y y()()ii2222222()()6.3 迭代法的收敛性迭代法的收敛性 当 时，有即 的任一特征值满足 ，故S

26、OR方法收敛(注意当 时，可以证明 )定理10：设 ，如果：(1)为严格对角占优矩阵(或不可约弱对角占优矩阵)(2)则解 的SOR迭代法收敛。（证明略）0222()()(2)(2)0 L102222(2)0 A01AxbAxb6.3 迭代法的收敛性迭代法的收敛性n迭代法的收敛速度 我们已经知道，如果 且 越小时，迭代法收敛越快，现考虑方程组及一阶定常迭代法且设迭代法收敛，记 ，则 。由基本定理有 ，且误差向量 满足 ，故 现设 为对称矩阵，则有()1B()B,n nxBxfBR(1)(),(0,1,)kkxBxfk()*limkkxx*xBxf0()1B()()*kkxx()(0)kkB()(

27、0)kkBB()(0)(0)2222()kkkBB6.3 迭代法的收敛性迭代法的收敛性下面确定欲使初始误差缩小 所需的迭代次数，即使取对数，得到所需最少迭代次数为：故所需迭代次数与 成反比，越小，越大，从而所需迭代次数越少，收敛越快 定义5：称 为迭代法的渐进收敛速度，简称收敛速度。对于SOR迭代法来说，希望通过 的选择使得收敛速度较快，但具体计算时，并非都可实现。10s()10ksBln10ln()skBln()RB()1Bln()RB()ln()R BB 6.3 迭代法的收敛性迭代法的收敛性nSOR迭代法的算法 设 ，其中 为对称正定矩阵或为严格对角占优或为不可约弱对角占优，本算法用SOR

28、迭代法求解 ，数组 存放 及 ，用 控制迭代终止，用 表示最大迭代次数。1.2.3.4.5.对于(1)(2)如果 ，则 (3)6.输出7.如果 ，则输出 停止；8.如果 ，则转3；9.输出 及有关信息。AxbAAxb()x n(0)x*x01maxii npxeps 0N0,k 0.0(1,2,),ixin1,kk1,2,in11*()iniiijjijjiijj ipxba xa xa 0pp0ppiixxp0p0peps,kx0kN0N00.0p 6.4 分块迭代法分块迭代法 前面讨论的迭代法，从 的计算过程，是逐个计算 的分量 ，因此这种方法又被称为点迭代法。现在介绍分块迭代法，就是一组

29、未知量同时被改进。设 ，其中 为大型稀疏矩阵且将 分块为三个部分 ，其中()(1)kkxx(1)(1,2,)kixin(1)kxAxbn nARAADLU1112111212222212,qqqqqqqqAAAAAAAAADAAAA121212120000,00qqqqAAAALUAA6.4 分块迭代法分块迭代法其中 为 非奇异矩阵，对 及 同样分块其中，在上述定义的基础上，我们来讨论分块迭代法。(1)块Jacobi迭代法(BJ)选取分裂矩阵 为 的对角块部分，即选取(1,2,)iiAiqiinn1qiinnxb1122,qqxbxbxbxb,iinniixRbRMA(MDAMN块对角阵）6.

30、4 分块迭代法分块迭代法于是，得到块Jacobi迭代法其中迭代矩阵 ，或由分块矩阵乘法，得到块Jacobi迭代法的具体形式：其中：这说明，块Jacobi迭代法每迭代一步需要求解 个低阶方程组(1)()kkxBxf111(),BID ADLUJ fD b(1)()()kkDxLU xb(1)()1()(1,2,)qkkiiiiijjijj iA xbA xgiq()1()2()()(),ikknkkikqxxxxRxq(1)(1,2,)kiiiiA xgiq6.4 分块迭代法分块迭代法(2)块SOR迭代法(BSOR)选取分裂矩阵 为带松弛因子的 块下三角部分，即：得到块SOR迭代法其中迭代矩阵 由分块矩阵乘法得到块SOR迭代法的具体形式：于是，可通过解一组低阶的方程组来代替原来的解。1()MDLAMNMA(1)()kkxL xf11()()(1)LIDLADLDU1()fDLb1(1)()(1)()1()(1,2,;0,1,)qikkkkiiiiiiiijjijjjj iA xA xbA xA xiq k6.4 分块迭代法分块迭代法 定理：设 ，其中(1)如果 为对称正定矩阵；(2)则解 的块SOR迭代法收敛。AxbADLUA02Axb