欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

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

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

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

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

    第第3 3章章 解线性方程组的迭代法解线性方程组的迭代法 迭代法的基本思想是,把n元线性方程组(3.1)或 Ax=b改写成等价的方程组 ,或x=Mx+g 迭代法是从某一取定的初始向量x x(0)出发,按照一个适当的迭代公式,逐次计算出向量x x(1),x x(2),使得向量序列x x(k)收敛于方程组的精确解.迭代法是一类逐次近似的方法.其优点是,算法简便,程序易于实现.由此建立方程组的迭代公式 x(k+1)=Mx(k)+g,k=0,1,2,(3.2)其中M称为迭代矩阵迭代矩阵。对任意取定的初始向量x x(0),由(3.2)式可逐次算出迭代向量x x(k),k=1,2,如果向量序列x(k)收敛于x*,由(3.2)式可得 x*=Mx*+g 从而x x*是方程组x=Mx+g的解,也就是方程组Ax=b的解.这种求解线性方程组的方法称为迭代法迭代法 ,若迭代序列x(k)收敛,则称迭代法收敛,否则称迭代法发散.1 Jacobi迭代法和迭代法和Gauss-Seidel迭代法迭代法 Jacobi方法是由方程组(3.1)中第k个方程解出x x(k),得到等价方程组:从而得迭代公式式(3.3)称为JacobiJacobi迭代法迭代法,简称为J J迭代法迭代法.,则J迭代法可写成 x x(k+1)=BxBx(k)+g g k=0,1,2,可见,J J迭代法的迭代矩阵为若记 J J法也记为G-SG-S迭代法也可记为式(3.4)称为Gauss-SeidelGauss-Seidel迭代法迭代法,简称为G-SG-S迭代法迭代法.若在J J迭代法中,充分利用新值,则可以得到如下的迭代公式方程组的精确解为x x*=(1,1,1)T.解解 J J迭代法计算公式为例例1 用J法和G-S法求解线性方程组取初始向量x x(0)=(0,0,0)T,迭代可得计算结果列表如下:可见,迭代序列逐次收敛于方程组的解,而切迭代7次得到精确到小数点后两位的近似解.kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636 G-SG-S迭代法的计算公式为:同样取初始向量x x(0)=(0,0,0)T,计算结果为 由计算结果可见,G-S迭代法收敛较快.取精确到小数点后两位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次.kx1(k)x2(k)x3(k)x(k)-x*012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956 为了进一步研究,从矩阵角度来讨论上述迭代法.对线性方程组AxAx=b b,记 D D=diag(a11,a22,ann)则有 A A=D D-L L-U U于是线性方程组 AxAx=b b 可写成 (D D-L L-U U)x x=b b等价于 DxDx=(L L+U U)x x+b b 或或 x x=D D-1(L L+U U)x x+D D-1b b 由此建立J J迭代法迭代公式 x x(k+1)=D D-1(L L+U U)x x(k)+D D-1b b k=0,1,2,或写成 x x(k+1)=BxBx(k)+g g k=0,1,2,其中G-SG-S迭代法迭代公式可写成 x x(k+1)=D D-1LxLx(k+1)+D D-1UxUx(k)+D D-1b b 讨论迭代法 x(k+1)=Mx(k)+g k=0,1,2,DxDx(k+1)=LxLx(k+1)+UxUx(k)+b b (D D-L L)x x(k+1)=UxUx(k)+b b x x(k+1)=(D D-L L)-1UxUx(k)+(D D-L L)-1b b 所以G-SG-S迭代法可以写成 x x(k+1)=GxGx(k)+g g k=0,1,2,其中 G G=(D D-L L)-1U U,g g=(D D-L L)-1b b 2 2 迭代法的收敛性迭代法的收敛性的收敛性.记误差向量e e(k)=x x(k)-x x*,则迭代法收敛就是e e(k)0 0.由于 x(k+1)=Mx(k)+g k=0,1,2,x*=Mx*+g k=0,1,2,所以 e(k+1)=Me(k),k=0,1,2,递推可得 e(k)=Mke(0),k=0,1,2,可见,当k时,e e(k)0 0 Mk O O.对任意初始向量x x(0),迭代法收敛(M)1.定理定理3.1 证证 若Mk0,则k(M)=(Mk)Mk0,所以(M)1.若(M)0,使得(M)+1.则MkMk(M)+)k 0.若若M1,则对任意x x(0),迭代法收敛,而且 定理定理3.2 证证 由于 x(k+1)=Mx(k)+g x(k)=Mx(k-1)+g x*=Mx*+g所以 x(k+1)-x(k)=M(x(k)-x(k-1),x(k+1)x*=M(x(k)x*)于是有 x(k+1)-x(k)Mx(k)-x(k-1)x(k+1)x*Mx(k)x*x(k+1)-x(k)=(x(k+1)x*)-(x(k)x*)x(k)x*-x(k+1)x*x(k+1)-x(k)=(x(k+1)x*)-(x(k)x*)x(k)x*-x(k+1)x*(1-M)x(k)x*所以 定理3.2只是收敛的充分条件,并不必要,如则M1=1.2,M=1.3,M2=1.09,MF=1.17但(M)=0.81,所以迭代法是收敛的.由(3.5)式可见,M越小收敛越快,且当x(k)-x(k-1)很小时,x(k)x*就很小,实际上用x(k)-x(k-1)作为迭代终止的条件.例如kx1(k)x2(k)x3(k)x(k)-x*0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636x(6)-x(5)=0.011339,x(7)x(6)=0.0056695 由(3.6)式可得:若使x(k)x*,只需可以事先估计达到某一精度需要迭代多少步.,即 用J J迭代法求例1中方程组的解,取x(0)=(0,0,0)T,若使误差x(k)-x*10-5,问需要迭代多少次?解解 由例1知,x x(1)=(1.4,0.5,1.4)T,于是有,x x(1)-x x(0)=1.4,B B=0.5.例例2 k应满足故取k=19,即需要迭代19次.3 3 J J迭代法和迭代法和G-SG-S迭代法的收敛性迭代法的收敛性 定理定理3.33.3 J J迭代法收敛(B)1;若B1J J迭代法收敛;G-SG-S迭代法收敛(G)1;若G1 G-SG-S迭代法收敛;定义定义3.13.1 若n阶矩阵A=(aij)满足:则称矩阵A是严格对角占优矩阵严格对角占优矩阵.引理引理 若A是严格对角占优矩阵,则det(A)0.证证 A=D-L-U=D(E-D-1(L+U)=D(E-B)因此,(B)B1,故=1不是B B的特征值,det(E E-B B)0.定理定理3.43.4 设A是严格对角占优矩阵,则解线性方程组Ax=b的J J迭代法和G-SG-S迭代法均收敛.因为A是严格对角占优矩阵,所以det(D)0,而且所以,det(A)0.证证 由于B1,所以J J迭代法收敛.设是G G的任一特征值,则满足特征方程 det(E-G)=det(E-(D-L)-1U)=det(D-L)-1)det(D-L)-U)=0所以有 det(D-L)-U)=0 若|1,则矩阵(D-L)-U 是严格对角占优矩阵,这与 det(D-L)-U)=0矛盾,所以|1,于是(G)1时称为超松弛迭代超松弛迭代,当当1时称为欠松弛迭代欠松弛迭代.其矩阵形式 x(k+1)=x(k)+D-1(b+Lx(k+1)+(U-D)x(k),k=0,1,2,于是有 Dx(k+1)=Dx(k)+(b+Lx(k+1)+(U-D)x(k)所以 x(k+1)=(D-L)-1(1-)D+Ux(k)+(D-L)-1b ,k=0,1,2,因此,SOR方法的迭代矩阵为 =(D-L)-1(1-)D+U SORSOR方法收敛()1;若 1,则SORSOR方法收敛.定理定理3.73.7 若SORSOR方法收敛,则02.定理定理3.6 证证 设SORSOR方法收敛,则()1,所以|det()|=|12 n|1而 det()=det(D-L)-1(1-)D+U)=det(E-D-1L)-1 det(1-)E+D-1U)=(1-)n于是|1-|1,或 02定理定理3.8 设A是严格对角占优矩阵,则解方程组Ax=b的SORSOR方法,当01时收敛.定理定理3.93.9 设A是对称正定矩阵,则解方程组Ax=b的SORSOR方法,当00 (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,因此()1,即S0R方法收敛.可得 =2/设是B的任一特征值,y是对应的特征向量,则 (L+U)y=Dy于是 (Ly,y)+(Uy,y)=(Dy,y)当A对称正定时,即2-0时,|0而 (2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2即,当A对称正定时,JacobiJacobi迭代法收敛2D-A正定.SORSOR方法收敛的快慢与松弛因子的选择有密切关系.但是如何选取最佳松弛因子,即选取=*,使()达到最小,是一个尚未很好解决的问题.实际上可采用试算的方法来确定较好的松弛因子.经验上可取1.41.6.用SORSOR方法解线性方程组 解解 SORSOR方法迭代公式为方程组的精确解是x x*=(2,1,-1)T.例例4取x x(0)=(0,0,0)T,=1.46,计算结果如下:kx1(k)x2(k)x3(k)01232003.652.321669102.56613991.999998700.88458820.42309390.69482611.00000130-0.2021098-0.22243214-0.4952594-1.0000034 从结果可见,迭代20次时已获得精确到小数点后五位的近似解.如果取=1.25,则需要迭代56次才能得到具有同样精度的近似解;如果取=1,则需迭代110次以上.练习题练习题第第75页页 习题习题33-2,3-3,3-4,3-7,3-8,3-9设线性方程组 (1)写出Jacobi法和SOR法的迭代格式(分量形式);(2)讨论这两种迭代法的收敛性.(3)取初值x(0)=(0,0,0)T,若用Jacobi迭代法计算时,预估误差x*-x(10)(取三位有效数字).课堂练习课堂练习 (2)因为A是严格对角占优矩阵,但不是正定矩阵,故Jacobi法收敛,SOR法当01时收敛.解解 (1)(1)Jacobi法和SOR法的迭代格式分别为 (3)由(1)可见B=3/4,且取x(0)=(0,0,0)T,经计算可得x(1)=(1/4,-2/5,1/2)T,于是x(1)-x(0)=1/2,所以有用SOR法求解方程组:分别取=0.65、1、1.2、1.45计算.要求精度为10-6;并指出迭代次数。上机实验题目上机实验题目(参考P66解线性方程组的SOR迭代算法)课课间间休休息息

    注意事项

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

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




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开