第七章-线性方程组的解法11课件.ppt

1、 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-161 1 迭代法的一般形式及其收敛性迭代法的一般形式及其收敛性下面考虑bAx 事实上，令 ，则)(非奇异MNMA非零，非奇异，设nnnijRbRaA)(bAxgGxx?bMNxMx11bxNM)(NxbMxAxb求的解。*,)(xxk设),2,1(lim*lim)()(nixxxxikikkk(1)给定初值x(0)，可以构造序列构造序列),2,1,0()()1(kgxGxkk迭代格式(2)Numerical Analysis J.G.Li

2、u School of Math.&Phys.North China Elec.P.U.2022-12-162若*)(xxkbAx*并且，*)(*)()()1(xxGGxGxxxkkk*)()0(1xxGk(与初值与初值x(0)的选取无关的选取无关!)gxGx*所以，0kG序列收敛(3)(1)(0lim 不加证明由于GGkk定理定理1.1)(G迭代格式(2)nnRxRg)0(,收敛 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-163定义定义1 迭代法（2）的平均收敛速度平均收敛速度定义

3、为 。1()lnkkR GGk1lim()kkkAA由（3）式可得()(0)*(*)kkxxGxx引理引理 设ARnn，为任一矩阵范数，则注：注：平均收敛速度与范数和迭代次数有关，计算不便！定义定义2 迭代法（2）的渐近收敛速度渐近收敛速度定义为()lim()ln()kkR GR GG。Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-164定理定理2若 ，则 1G(1)方程组(1)的解x*存在并且唯一；(2)对迭代格式(2)有)()0()(,*limnnkkRgRxxx，并且)0()1()

4、(1*xxGGxxkk)1()()(1*kkkxxGGxx下面给出迭代格式(2)收敛的一个充分条件及误差估计，证明：证明：(1)1G非奇异GI Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-165GG)()1,G(2)下证误差估计式，)()1(kkxxxxxxkk)1()(xxGxxkk)()(xxGk)()1()()1(kkxxxx)1()()(1*kkkxxGGxx由迭代公式(3)得证！注：注：可作为迭代是否停止的判断条件迭代是否停止的判断条件！由知可由)1()(kkxx或)()1(

5、)(kkkxxx得证！#)0()1()1()()(11*xxGGxxGGxxkkkk即 迭代格式收敛。Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-166 2 线性代数方程组的常用迭代法线性代数方程组的常用迭代法迭代矩阵迭代矩阵G的构造原则：的构造原则：充分利用矩阵的稀疏性稀疏性，使运算量和存贮量尽量少，办法就是使迭代矩阵G与原矩阵A有相同的稀疏结构。000 ;000);,diag(1,-1,1,21,12,12211 nnnn-nnnnaaaUaaaLaaaD具体构造方法具体构造方法:

6、ULDA令其中 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-167,)0(nRxbxULDbAx)(由可以得到1、Jacobi 迭代算法)(;ULNDM令可得：bDxULDx11)(从而可得Jacobi 迭代算法：),2,1,0()()1(kgxGxkJk算法的分量形式为(具有并行性具有并行性)：),2,1()(11)(11)()1(nixaxabaxnijkjijijkjijiiiki若若D非奇异非奇异，)(1ULDGJ其中Jacobi迭代矩阵 Numerical Analysis

7、J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1682、Gauss-Seidel 迭代算法可得令,;UNLDMbLDUxLDx11)()(从而可得Gauss-Seidel迭代算法：),2,1,0()()1(kgxGxkSGk算法的分量形式为(只能逐个元素进行计算只能逐个元素进行计算)：),2,1()(11)(11)1()1(nixaxabaxnijkjijijkjijiiiki)()()1(1)1(kkkUxLxbDx也可写成如下形式：易于编程实现ULDGSG1)(其中G-S迭代矩阵 Numerical Analysis J

8、.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-169迭代算法的收敛性：迭代算法的收敛性：(1)Jacobi迭代算法收敛;1)(JG(2)若A按行（列）严格对角占优按行（列）严格对角占优，则Jacobi迭代和Gauss-Seidel迭代收敛；#Jacobi迭代收敛；1JG1 SGGGauss-Seidel迭代收敛；(3)(4)若A为正定矩阵正定矩阵，则Gauss-Seidel迭代收敛。#两种方法都存在收敛性问题，但两者的收敛性没有必然联系没有必然联系！有例子表明：Gauss-Seidel法收敛时，Jacobi法可能不收敛；而Ja

9、cobi法收敛时，Gauss-Seidel法也可能不收敛。G-S迭代算法收敛;1)(SGG Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1610算法描述算法描述:Jacobi迭代算法：迭代算法：给定迭代初始向量x(0)，置迭代次数k=0，精度要求 和最大迭代次数N；计算 ，k=k+1；bDxULDx1)0(1)1()(1)(2)若 ，则停止计算（x(1)作为方程的解）；)0()1(xx(3)若 k=N，则停止计算（输出某些信息），否则x(0)=x(1)，转(1)；注：注：将(1)中的迭

10、代公式换作)()0()1(1)1(UxLxbDx即为G-S迭代的算法描述！1）2）通常取向量的无穷范数！Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1611),2,1()1()(1)()1()1(1)(11)1()1(nixxxxaxabaxkikikinijkjijijkjijiiiki 3 超松弛超松弛(SOR)迭代算法迭代算法 设已得到,)(kx利用松弛技术松弛技术对由高斯-赛德尔迭代进行加速：(松弛因子)，超松弛迭代算法(SOR)注：注：=1 时，即为Gauss-Seidel迭

11、代算法。),2,1()()1(111)()1()()1(nixaxabaxxijnijkjijkjijiiikikiSOR算法的分量形式(只能逐个元素进行计算只能逐个元素进行计算)：Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1612注：注：)11(;1UDNLDM若令则可以得到矩阵表示形式：gxGxkSk)()1(bLDgUDLDGS11)1(;)11()1(其中 Numerical Analysis J.G.Liu School of Math.&Phys.North China

12、Elec.P.U.2022-12-1613SOR迭代算法的收敛性：迭代算法的收敛性：（5）若A为正定矩阵，则当02时，SOR迭代算法收敛；#（4）若A为严格对角占优阵，则当01时，SOR迭代算法收敛；#（2）SOR迭代收敛的必要条件必要条件02#注：注：松弛因子的选择通常靠经验经验或用试算试算的方法来确定！1)(SOR1SG迭代收敛）（迭代收敛）（SOR13SG Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1614 4 解线性代数方程组的共轭梯度法解线性代数方程组的共轭梯度法,21)(

13、xbAxxxfTT)(min)(*xfxfbAxx我们知道二次函数当A是对称正定矩阵时，有唯一的极小值点x*。0)()(*bAxxfxf由多元函数取得极值的必要条件，得 可以证明可以证明即解对称正定矩阵方程组对称正定矩阵方程组的问题等价于等价于求二次函数极小值二次函数极小值的问题。Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1615如何寻找 的极小点呢？)(xf从某点x(0)出发，逐步产生一串点：,)()2()1()0(kxxxx(0)(1)(2)().()()()()kstf xf

14、xf xf x以“最快”的速度，下降到 的极小值。)(xf基本思想就是下降法基本思想就是下降法：Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1616()()(1)()3 ()(.)kkkkf xie b-Axxx、直到或为止。下降法的算法描述：下降法的算法描述：假设已经求得x(k)，考虑如何确定x(k+1)，；下降的方向处确定一个使、在)()()(1kkpxfx);(min)(,)(2)()(01)()1()()(kktkkkktpxfxfxxftpxx即的极小值点上求、在射线根据下降

15、方向的选择不同，我们有不同的下降算法！下面主要介绍最速下降法最速下降法和共轭梯度法共轭梯度法。Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1617 4.1 最速下降法最速下降法我们知道，函数的负梯度方向负梯度方向是函数值下降最快的方向。),2,1,0()()()()(kAxbxfpkkk取的下降算法称为最速下降算法最速下降算法。)()()()()(2)()()()()()()()()()()(21)()()(21)()()(21)(kTkTkkTkkTkkkTkkTkkkkxbAxxt

16、bAxptApp tpxbtpxAtpxtpxf0)()()(kktpxfdtd)()()()()()(kTkkTkkAppppt )(min)()(0kkttpxf从而得到满足的点)()(1)(kkkkptxx Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1618算法描述如下：；，转，停止若，令)1(1)(;)()()2(;,)1(0,)()()1()()()()()()()()0(kkrtxxArrrrtrAxbrkRxkkkkkTkkTkkkkkn注：注：r(k+1)和r(k)正

17、交!这是因为()()(1)(1)()()()()()()()()()kTkkkkkkkkkTkrrrbAxbA xt rrArrAr ()(1)()0kTkrr从而 Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1619收敛定理：收敛定理：设A的特征值为,021n则由上述算法得到的序列满足,*)(*011AknnAkxxxx其中#;)(AxxxTA1 该算法简单易行，可充分利用A的稀疏性等特点，但当A的最大特征值远远大于最小特征值时收敛速度变得非常的最大特征值远远大于最小特征值时收敛速度

18、变得非常慢慢，以至于完全不适用。注：注：2 最速下降法并非最速！Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1620 4.2 共轭梯度共轭梯度(CG)算法算法有比负梯度方向负梯度方向更好的下降方向吗？设x(k)是沿下降方向p(k-1)求得的，且x(k)的最速下降方向为r(k)=b-Ax(k)。下面确定x(k)的下降方向p(k)，使之满足：；共轭关于与称)(0)()1()()1()(AppAppkkkTk)(min)()()(0)1(kktktpxfxf从而由极小值问题：可以确定x(k+

19、1)。注：A共轭向量是线性无关的!#Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1621)(min)()()(0)1(kktktpxfxf由;)()()()()()(kTkkTkkAppppt;)()()1(kkkkptxx0)()()(kktpxfdtd令,)1()()(kkksprp则 0)()1()(kTkApp)()()1()1()()1(kTkkTkkAppArps)1()()(kkkkpsrp具体做法如下：具体做法如下：共轭梯度方向共轭梯度方向 Numerical Anal

20、ysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1622);1(,1,)()(3);(2)()(1)0,)(1)1()1()()()1()(1)1()1()1()()()1()()()()()0()0()0()0()0(转，停止若；，；，令kkpsrpAppArpsrAxbrptxxApppptkrpAxbrRxkkkkkTkkTkkkkkkkkkkTkkTkkn算法如下：共轭梯度算法共轭梯度算法！确定下降方向计算极小值点 Numerical Analysis J.G.Liu School of Math.&Phys

21、.North China Elec.P.U.2022-12-1623共轭梯度算法的收敛性：共轭梯度算法的收敛性：对于共轭梯度算法，可以证明：是两两正交的；,)()1()0(krrr共轭的；是两两关于Apppk,)()1(0);1,1,0 ,0)()()(kirpkTi;0)(nr(1)(2)(3)(4)*x0)(nr说明，共轭梯度算法至多n步就能得到精确解注：注：1、实际计算中由于误差的影响，r(k)之间的正交性很快就会消失，以 至于有限步内不能得到精确解，所以CG算法实际是一种迭代算法迭代算法。2、cond(A)2 越小，CG算法收敛越快！Numerical Analysis J.G.Liu School of Math.&Phys.North China Elec.P.U.2022-12-1624实用的共轭梯度算法：实用的共轭梯度算法：)()()1()1()()()1()(1)()()1()1()()()()()()()()()()()()()()()()(kTkkTkkTkkTkkkkkkkkTkkTkkTkkTkkrrrrAppArpsAptrAxbrApprrAppppt；在CG算法中，令可见计算量减少了！本节可参考：运筹学教材编写组，运筹学，清华大学出版社，1990.(P158第六章)