欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    第二章解线性方程组的迭代法.ppt

    • 资源ID:6110079       资源大小:719.05KB        全文页数:39页
    • 资源格式: PPT        下载积分:10金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要10金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    第二章解线性方程组的迭代法.ppt

    解线性方程组的迭代法,直接法得到的解是理论上准确的,但是它们的计算量都是n3数量级,存储量为n2量级,这在n比较小的时候还比较合适(n400),但是在很多实际问题中,我们要求解的方程组n很大,而系数矩阵中含有大量的0元素。对于这类的矩阵,在用直接法时就会耗费大量的时间和存储单元。因此我们有必要引入一类新的方法:迭代法。,迭代法是一种逐次逼近的方法,其基本思想是:使用某个固定的公式,对解的近似值进行反复校正,从而得到一个近似解序列,使之收敛于方程组的解。,迭代法具有算法简单、运算速度快的特点。但这种方法获得的是方程组解的近似值。,对方程组,做等价变换,从某一初值 x(0)出发,我们可以构造序列,若,同时:,所以,序列收敛,与初值的选取无关,如令A=D-L-U,于是 x=D-1(L+U)x+D-1b,定义5.1:设G为n阶方阵,若Gk0,则称G为收敛矩阵,定理:,即矩阵G为收敛矩阵,当且仅当G的谱半径1,迭代法的收敛性,定理:迭代法X(m+1)=GX(m)+g 收敛的充分必要条件是迭代矩阵G为收敛矩阵,即G的谱半径(G)1。,定理:迭代法X(m+1)=GX(m)+g 的迭代矩阵G的某种范数|G|q1,那么:1)对任意初值X(0)及g右端向量,迭代格式收敛于X*;2)|X(m)-X*|qm|X(1)X(0)|/(1-q);3)|X(m)-X*|q|X(m)X(m-1)|/(1-q).,Jacobi迭代,格式很简单:,1、输入系数矩阵A和向量b,和误差控制eps2、x1=0,0,.,0,x2=1,1,.,1/赋初值3、while(|A*x2-b|eps)x1=x2;for(i=0;i=n;i+)x2i=0;for(j=0;ji;j+)x2i+=Aij*x1j for(j=i+1;jn;j+)x2i+=Aij*x1j x2i=-(x2i-bi)/Aii 4、输出解x2,Jacobi迭代算法,迭代矩阵,记,Jacobi迭代法的收敛性,易知,Jacobi迭代有,练习,讨论用雅可比(Jacobi)迭代法求解下列线性方程组的收敛性。若收敛,求其解;若发散,作适当变换使其收敛并求解。,G的谱半径(G)=4.01971.Jacobi迭代不收敛。,迭代矩阵为,G的特征值为:1=4.02408,2=-2.01204 3.10115 i,1=4.02408;2,3=3.69668,将方程组变形,化为:,G的谱半径(G)=0.308507 1.Jacobi迭代收敛。,此时迭代矩阵为,G的特征值分别为:0.308507,-0.154254+0.18304 i,-0.154254-0.18304 i,收敛条件,迭代格式收敛的充要条件是G的谱半径1。对于Jacobi迭代,我们有一些保证收敛的充分条件,定理:若线性方程组AX=b的系数矩阵A满足下列条件之一,则Jacobi迭代收敛。,A为行对角占优阵,A为列对角占优阵,A满足,若A对称正定阵,且2D-A也为对称正定阵,则Jacobi迭代收敛。,证明:,A为列对角占优阵,则AT为行对角占优阵,有,证毕,在Jacobi迭代中,使用最新计算出的分量值,GaussSeidel迭代,1、输入系数矩阵A和向量b,和误差控制eps2、x2=1,1,.,1/赋初值3、while(|A*x2-b|eps)for(i=0;in;i+)for(j=0;ji;j+)x2i+=Aij*x2j for(j=i+1;jn;j+)x2i+=Aij*x2j x2i=-(x2i-bi)/Aii 4、输出解x2,Gauss-Siedel迭代算法,迭代矩阵,是否是原来的方程的解?,A=(D-L)-U,Gauss-Siedel迭代法的收敛性,收敛条件,迭代格式X=GX+g 对任意的初值X0和向量g,收敛的充要条件是G的谱半径(G)1。下面我们看一些充分条件:,定理:若线性方程组AX=b的系数矩阵A,,若A对称正定阵,则Gauss-Seidel迭代收敛;,若A对称正定阵,且2D-A也为对称正定阵,则Jacobi迭代收敛。,若A为行或列强对角占优阵,则Jacobi和Gauss-Seidel迭代都收敛;,证明:,设G的特征多项式为,,则,为对角占优阵,则,时,为对角占优阵,即,即,证毕,注:二种方法都存在收敛性问题。有例子表明:Gauss-Seidel法收敛时,Jacobi法可能不收敛;而Jacobi法收敛时,Gauss-Seidel法也可能不收敛。,练习:判定用Jacobi和Gauss-Seidel迭代解方程组:AX=b 时的收敛情况,其中,1、Jacobi迭代,特征值为,2、GaussSeidel迭代,G的谱半径(G)=1.1181.Jacobi迭代不收敛。,G的谱半径(G)=0.51.Gauss-Seidel迭代收敛。,分别用Jacobi,Gauss-Seidel迭代法解方程组AX=b,其中,例题,1、预处理,2、格式:Jacobi迭代:,Gauss-Seidel迭代:,取初值,矩阵A按行严格对角占优,都收敛,m=1 x1=0.777778 x2=0.875000 x3=0.888889 error=0.888889m=2 x1=0.973765 x2=0.972222 x3=0.975309 error=0.195988m=3 x1=0.994170 x2=0.996721 x3=0.997085 error=0.024498m=4 x1=0.999312 x2=0.999271 x3=0.999352 error=0.005142m=5 x1=0.999847 x2=0.999914 x3=0.999924 error=0.000643m=6 x1=0.999982 x2=0.999981 x3=0.999983 error=0.000135m=7 x1=0.999996 x2=0.999998 x3=0.999998 error=0.000017 m=8 x1=1.00000 x2=1.00000 x3=1.00000 error=0.000004,Jacobi迭代,3、结果,m=1 x1=0.777778 x2=0.972222 x3=0.975309 error=0.975309m=2 x1=0.994170 x2=0.999271 x3=0.999352 error=0.216392m=3 x1=0.999847 x2=0.999981 x3=0.999983 error=0.005677 m=4 x1=0.999996 x2=1.00000 x3=1.00000 error=0.000149m=5 x1=1.00000 x2=1.000000 x3=1.000000 error=0.000004,Gauss-Seidel迭代,练习,用雅可比(Jacobi)迭代法和高斯赛德尔(Gauss-Seidel)迭代法求解线性方程组:,可以看作在前一步上加一个修正量。若在修正量前乘以一个因子w,则有,对GaussSeidel迭代格式,松弛迭代,写成分量形式,有,松弛迭代算法,1、输入系数矩阵A、向量b和松弛因子omega,和误差控制eps2、x2=1,1,.,1/赋初值3、while(|A*x2-b|eps)for(i=0;in;i+)temp-0 for(j=0;ji;j+)temp+=Aij*x2j for(j=i+1;jn;j+)temp+=Aij*x2j temp=-(x2i-bi)/Aii x2i=(1-omega)*x2i+omega*temp 4、输出解x2,迭代矩阵,定理:,松弛迭代收敛,定理:,A对称正定,则松弛迭代收敛,是否是原来的方程的解?,SOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使(G)达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.,当松弛因子1时,称该算法为低松弛因子法;,当松弛因子1时,称该算法为超松弛因子法;,定理 若SOR方法收敛,则02.,证 设SOR方法收敛,则(G)1,所以|det(G)|=|12 n|1,而 det(G)=det(D-L)-1(1-)D+U),=det(E-D-1L)-1det(1-)E+D-1U),=(1-)n,于是|1-|1,或 02,定理 用SOR法解方程组Ax=b,,证 设是G的任一特征值,y是对应的特征向量,则,(1-)D+Uy=(D-L)y,于是(1-)(Dy,y)+(Uy,y)=(Dy,y)-(Ly,y),1)若A是对称正定矩阵,则当02时收敛;,2)若矩阵A按行(列)严格对角占优,则当01时收敛;,由于A=D-L-U是对称正定的,所以D是正定矩阵,且L=UT.若记(Ly,y)=+i,则有,(Dy,y)=0,(Uy,y)=(y,Ly)=(Ly,y),=-i,0(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2,所以,当02时,有,(-+)2-(-)2=(2-)(2-)=(2-)(2-)0,所以|21,因此(G)1,即S0R方法收敛.,可得=2/,设是B的任一特征值,y是对应的特征向量,则,(L+U)y=Dy,于是(Ly,y)+(Uy,y)=(Dy,y),当A对称正定时,即2-0,而(2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2,即,当A对称正定时,Jacobi迭代法收敛2D-A正定.,共轭梯度法,给定对称正定矩阵ARnn,求解方程组AX=b的共轭梯度法如下:,1.选定初值X(0)Rn,设r(0)=d(0)=b-AX(0);,2.r(k+1)=r(k)-(k)A d(k);其中,3.d(k+1)=r(k+1)+(k)d(k);其中,4.X(k+1)=X(k)+(k)d(k);,定理:设矩阵ARnn对称正定,X(k)为用共轭梯度法求解方程组AX=b所产生的迭代序列,并取条件数,那么:,1)用不超过n次迭代即可获得精确解;,2)对每次迭代结果的误差估计为:,其中范数|X|A=(AX,X),

    注意事项

    本文(第二章解线性方程组的迭代法.ppt)为本站会员(sccc)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开