第四章线性代数方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx
《第四章线性代数方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《第四章线性代数方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx(54页珍藏版)》请在咨信网上搜索。
1、 在第二章中我们知道,凡是迭代法都有在第二章中我们知道,凡是迭代法都有一个收敛问题,有时某种方法对一类方程组一个收敛问题,有时某种方法对一类方程组迭代收敛,而对另一类方程组进行迭代时就迭代收敛,而对另一类方程组进行迭代时就会发散。一个收敛迭代法不但含有程序设计会发散。一个收敛迭代法不但含有程序设计简单,适于自动计算,而且较直接法更少计简单,适于自动计算,而且较直接法更少计算量就可取得满意解。所以,迭代法亦是求算量就可取得满意解。所以,迭代法亦是求解线性方程组,尤其是求解含有大型稀疏矩解线性方程组,尤其是求解含有大型稀疏矩阵线性方程组主要方法之一。阵线性方程组主要方法之一。第四章第四章 解线性方
2、程组迭代法解线性方程组迭代法第1页4.2 4.2 迭代法基本思想迭代法基本思想 迭代法基本思想是将线性方程组转化为迭代法基本思想是将线性方程组转化为便于迭代等价方程组,对任选一组初始值便于迭代等价方程组,对任选一组初始值 ,按某种计算规则,不停地,按某种计算规则,不停地对所得到值进行修正,最终取得满足精度要对所得到值进行修正,最终取得满足精度要求方程组近似解求方程组近似解。第2页设设 非奇异,非奇异,则线性方程组,则线性方程组 有惟一解有惟一解 ,经过变换结构,经过变换结构出一个等价同解方程组出一个等价同解方程组将上式改写成迭代式将上式改写成迭代式选定初始向量选定初始向量 ,重复不停重复不停地
3、使用迭代式逐步迫近方程组准确解地使用迭代式逐步迫近方程组准确解,直到直到满足精度要求为止。这种方法称为迭代法满足精度要求为止。这种方法称为迭代法第3页 假如假如 存在极限存在极限则称迭代法是收敛,不然就是发散。则称迭代法是收敛,不然就是发散。收敛时,在迭代公式收敛时,在迭代公式中当中当 时,时,,则则,故故 是方程组是方程组 解。解。对于给定方程组能够结构各种迭代公式。对于给定方程组能够结构各种迭代公式。并非全部收敛并非全部收敛 第4页例例4.1 4.1 用迭代法求解线性方程组用迭代法求解线性方程组 解解 结构方程组等价方程组结构方程组等价方程组据此建立迭代公式据此建立迭代公式 取取 计算得计
4、算得 迭代解离准确解迭代解离准确解 越来越远迭代不收敛越来越远迭代不收敛 第5页4.3 雅可比(雅可比(Jacobi)迭代法迭代法4.3.14.3.1雅可比迭代法算法结构雅可比迭代法算法结构 例例4.2 4.2 用雅可比迭代法求解方程组用雅可比迭代法求解方程组 解:从方程组三个方程中分离出解:从方程组三个方程中分离出 和和 建立迭代公式建立迭代公式 第6页取初始向量取初始向量进行迭代进行迭代,能够逐步得出一个近似解序列:能够逐步得出一个近似解序列:(k=1,2,)直到求得近似解能到达预先要求精度,直到求得近似解能到达预先要求精度,则迭代过程终止,以最终得到近似解作为线则迭代过程终止,以最终得到
5、近似解作为线性方程组解。性方程组解。当迭代到第当迭代到第10次有次有计算结果表明,此迭代过程收敛于方程组精计算结果表明,此迭代过程收敛于方程组精确解确解x*=(3,2,1)T。第7页考查普通方程组,将考查普通方程组,将n n元线性方程组元线性方程组 写成写成 若若 ,分离出变量分离出变量 据此建立迭代公式据此建立迭代公式 上式称为解方程组上式称为解方程组JacobiJacobi迭代公式。迭代公式。第8页4.3.4.3.2 雅可比迭代法矩阵表示雅可比迭代法矩阵表示 设方程组设方程组 系数矩阵系数矩阵A A非奇异,且主对非奇异,且主对角元素角元素 ,则可将,则可将A A分裂成分裂成 记作记作 A=
6、L+D+U 第9页则则 等价于等价于即即因为因为 ,则则这么便得到一个迭代公式这么便得到一个迭代公式令令则有则有(k=0,1,2)称为雅可比迭代公式称为雅可比迭代公式,B称为雅可比迭代矩阵称为雅可比迭代矩阵第10页其中其中 在例在例4.24.2中中,由迭代公式写出雅可比迭代矩阵为由迭代公式写出雅可比迭代矩阵为 第11页雅可比迭代矩阵表示法,主要是用来讨论其收敛雅可比迭代矩阵表示法,主要是用来讨论其收敛性,实际计算中,要用雅可比迭代法公式分量形性,实际计算中,要用雅可比迭代法公式分量形式。即式。即(k=0,1,2,)第12页4.3.34.3.3 雅可比迭代法算法实现雅可比迭代法算法实现 第13页
7、4.4 高斯高斯-塞德尔(塞德尔(Gauss-Seidel)迭代法迭代法4.4.1 高斯高斯-塞德尔迭代法基本思想塞德尔迭代法基本思想 在在Jacobi迭迭代代法法中中,每每次次迭迭代代只只用用到到前前一一次次迭迭代代值值,若若每每次次迭迭代代充充分分利利用用当当前前最最新新迭迭代代值值,即即在在求求 时用新分量时用新分量代替旧分量代替旧分量 ,就得到高斯就得到高斯-赛德尔迭代法。其迭代法格式为:赛德尔迭代法。其迭代法格式为:(i=1,2,=1,2,n k=0,1,2,)=0,1,2,)第14页例例4.3 用用GaussSeidel 迭代格式解方程组迭代格式解方程组 准确要求为准确要求为=0.
8、005=0.005 解解 GaussGaussSeidel Seidel 迭代格式为迭代格式为取初始迭代向量取初始迭代向量 ,迭代结果为:迭代结果为:x*第15页4.4.2 GaussSeidel 迭代法矩阵表示迭代法矩阵表示 将将A分裂成分裂成A=L+D+U,则则 等价于等价于 (L+D+U)L+D+U)x=b=b 于是于是,则高斯则高斯塞德尔迭代过程塞德尔迭代过程 因为因为 ,所以所以 则高斯则高斯-塞德尔迭代形式为:塞德尔迭代形式为:故故 令令 第16页4.4.3 高斯高斯塞德尔迭代算法实现塞德尔迭代算法实现 高高斯斯-塞塞德德尔尔迭迭代代算算法法计计算算步步骤骤与与流流程程图图与与雅可
9、比迭代法大致相同,只是一旦求出变元雅可比迭代法大致相同,只是一旦求出变元某个新值某个新值 后后,就改用新值就改用新值 替换老值替换老值 进行这一步剩下计算。进行这一步剩下计算。高斯高斯-塞德尔迭代算法塞德尔迭代算法程序实现程序实现(见附录见附录A A-7 用高斯用高斯塞德尔迭代法求解线塞德尔迭代法求解线 性方程组性方程组)第17页4.5.5 超松弛迭代法(超松弛迭代法(SOR方法)方法)使用迭代法困难在于难以预计其计算使用迭代法困难在于难以预计其计算量。有时迭代过程即使收敛,但因为收敛速量。有时迭代过程即使收敛,但因为收敛速度迟缓,使计算量变得很大而失去使用价值度迟缓,使计算量变得很大而失去使
10、用价值。所以,迭代过程加速含有主要意义。逐。所以,迭代过程加速含有主要意义。逐次超松弛迭代(次超松弛迭代(Successive Over relaxatic Successive Over relaxatic MethodMethod,简称简称SORSOR方法)法,能够看作是带参方法)法,能够看作是带参数高斯数高斯塞德尔迭代法,实质上是高斯塞德尔迭代法,实质上是高斯-塞德塞德尔迭代一个加速方法。尔迭代一个加速方法。第18页4.5.1超松弛迭代法基本思想超松弛迭代法基本思想 超松弛迭代法目标是为了提升迭代法收敛速度,超松弛迭代法目标是为了提升迭代法收敛速度,在高斯在高斯塞德尔迭代公式基础上作一些
11、修改。这种塞德尔迭代公式基础上作一些修改。这种方法是将前一步结果方法是将前一步结果 与高斯与高斯-塞德尔迭代方法塞德尔迭代方法迭代值迭代值 适当加权平均,期望取得更加好近似值适当加权平均,期望取得更加好近似值 。是解大型稀疏矩阵方程组有效方法之一,有着广。是解大型稀疏矩阵方程组有效方法之一,有着广泛应用。泛应用。其详细计算公式以下:其详细计算公式以下:用高斯用高斯塞德尔迭代法定义辅助量。塞德尔迭代法定义辅助量。第19页把把 取为取为 与与 加权平均,即加权平均,即 合并表示为:合并表示为:式中系数式中系数称为称为松弛因子松弛因子,当,当=1时,便为高斯时,便为高斯-塞德尔迭代法。为了确保迭代过
12、程收敛,要求塞德尔迭代法。为了确保迭代过程收敛,要求0 2。当当0 1时,低松弛法;当时,低松弛法;当1 2时时称为超松弛法。但通常统称为超松弛法称为超松弛法。但通常统称为超松弛法(SOR)。第20页4.5.2 超松弛迭代法矩阵表示超松弛迭代法矩阵表示设线性方程组设线性方程组 系数矩阵系数矩阵A非奇异非奇异,且主对角且主对角元素元素 ,则将则将A A分裂成分裂成A=L+D+U,A=L+D+U,则超松弛迭代公式用矩阵表示为则超松弛迭代公式用矩阵表示为或或 故故 显然对任何一个显然对任何一个值值,(,(D+L)D+L)非奇异非奇异,(,(因为假设因为假设 )于是超松弛迭代公式为于是超松弛迭代公式为
13、 令令则超松弛迭代则超松弛迭代公式可写成公式可写成 第21页例例4.4 用用SOR法求解线性方程组法求解线性方程组 取取=1.46,要求要求 解:解:SOR迭代公式迭代公式 k=0,1,2,,初值初值 该方程组准确解该方程组准确解只需迭代只需迭代20次便可到达精度要求次便可到达精度要求 假如取假如取=1(即高斯即高斯塞德尔迭代法塞德尔迭代法)和同一初和同一初值值 ,要到达一样精度要到达一样精度,需要迭代需要迭代110次次第22页4.6 迭代法收敛性迭代法收敛性 我们知道我们知道,对于给定方程组能够结构成简对于给定方程组能够结构成简单迭代公式、雅可比迭代公式、高斯单迭代公式、雅可比迭代公式、高斯
14、-塞德尔塞德尔迭代公式和超松弛迭代公式,但并非一定收迭代公式和超松弛迭代公式,但并非一定收敛。现在分析它们收敛性。敛。现在分析它们收敛性。对于方程组对于方程组 经过等价变换结构出等价方程组经过等价变换结构出等价方程组 在什么条件下迭代序列在什么条件下迭代序列 收敛?先引入收敛?先引入以下定理以下定理 第23页定理定理4.1 对给定方阵对给定方阵G,若若 ,则则 为非奇异矩阵为非奇异矩阵,且且 证证:用反证法用反证法,若若 为奇异矩阵为奇异矩阵,则存在非零向则存在非零向 量量x,使使 ,即有即有 由相容性条件得由相容性条件得 因为因为 ,两端消去两端消去 ,有有 ,与已知条件与已知条件矛盾矛盾,
15、假设不成立假设不成立,命题得证。命题得证。又因为又因为 有有 即即 将将G分别取成分别取成G和和-G,再取范数再取范数 又已知又已知 ,有有 第24页定理定理4.2 4.2 迭代公式迭代公式 收敛收敛充分必要条件是迭代矩阵充分必要条件是迭代矩阵G谱半径谱半径证证:必要性必要性 设迭代公式收敛设迭代公式收敛,当当kk时时,则在迭代公式两端同时取极限得则在迭代公式两端同时取极限得记记 ,则则 收敛于收敛于0(0(零向量零向量),),且有且有 于是于是 因为因为 能够是任意向量能够是任意向量,故故 收敛于收敛于0 0当且仅当且仅当当 收敛于零矩阵,即当收敛于零矩阵,即当 时时 于是于是 所以必有所以
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第四 线性代数 方程组 解法 公共课 一等奖 全国 获奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,个别因单元格分列造成显示页码不一将协商解决,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。