版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、第三章 线性方程组的迭代解法,1 迭代法的一般形式 设线性方程组 Ax=b 的系数矩阵A非奇异,从而有一组唯一的解。构造等价的方程组,1,建立迭代公式。,任取一个初值x(0) ,由迭代公式产生x近似解的一个向量序列x(k) ,若,则有 即 x*是Ax=b的解。,注1迭代公式x(k+1)=Bx(k)+f 的构造形式不同,就可得到不同的迭代法。,2,定义3.1若对任意的初值x(0),迭代公式 x(k+1)=Bx(k)+f 产生的向量序列x(k)均收敛,则称迭代公式是收敛的,否则称迭代公式是发散的。称B为迭代矩阵。,注3由,迭代法产生的向量序列 的收敛终止条件常为,注2 迭代法不需存储系数矩阵的零元
2、素,特别适合求解零元素较多的稀疏矩阵。用直接解法求解时,一次消元就可能使系数阵丧失其稀疏性,不能充分利用其稀疏的特点。,3,例3.1 用迭代法求解方程组,4,2 几种常用的迭代公式,从三个方程中分别解出,取初值x(0)=(0,0,0)T,得到迭代序列x(k) 如下表,方程组的准确解为 x = (3,2,1)T,从上表的计算结果可看出,向量序列x(k)收敛于方程组的准确解。,5,构造迭代格式为,一般说来,对方程组,6,一、Jacobi方法(简单迭代法),并设,从第i个方程解出xi,得等价的方程组,构造迭代公式为,这种迭代格式称为Jacobi迭代法,也称为简单迭代法。记,7,得Jacobi迭代法的
3、矩阵形式为,其中,8,二、 Gauss-Seidel 迭代法,在例1的Jacobi 迭代法中,可以看出,在计算 时,要利用 ,但此时的 已经计算出来了。可以利用 代替 。一般地,计算 (ni2)时,可使用 代替 (i p1),这样收敛会快一些,由此形成一种新的迭代法,称为Gauss-Seidel迭代法。,例3.2 用Seidel迭代法计算例1,并与例1 的结果作比较。 解 迭代公式为,9,用它计算得到的序列x(k)列表如下表,可见Gauss-Seidel迭代法比Jacobi迭代法收敛要快一些。,Seidel迭代法的迭代公式如下,10,Seidel 迭代法的矩阵迭代形式为,Seidel 迭代法的
4、矩阵形式迭代公式,11,注1 Seidel 迭代法在用计算机计算时,只需一组内存单元。,注2 在一定的条件下,Seidel 迭代法比Jacobi迭代法收敛的速度快。,算法 (Gauss-Seidel迭代法),12,三、逐次超松弛法(SOR方法),13,逐次超松弛法(Successive Over Relaxation Method)可看成是Gauss-Seidel方法的加速,Seidel迭代法是SOR方法的特例。将Seidel方法的迭代公式,改写为,记,则,为加快收敛,在增量 前加一个因子 ,得,称此公式为逐次超松弛法(SOR法)。 当01时,称为超松弛法。,14,故SOR方法的矩阵形式迭代公
5、式为,15,SOR方法的矩阵形式为,例3.3 用Seidel 迭代法和取=1.45的SOR法求解方程组,解 取初值x(0)=(1,1,1)T ,精度,用Gauss-Seidel迭代法迭代有,16,达到同样的精度Gauss-Seidel迭代法需要迭代72步,而取=1.45的SOR法只需要迭代25步。由此可见选择适当的松弛因子,SOR方法收敛速度明显加快。所以SOR方法常用来求解大型的线性方程组。,准确值x=(1,1,2)T,取=1.45的SOR法迭代25步有,3 迭代法的收敛条件,设,,引进误差向量,有,17,定理3.1 对任意初始向量x(0)和f,由 产生的迭代序列x(k)收敛的充要条件是(B
6、)1. 证 1)必要性,18,基本定理 设迭代格式 收敛,则,由基本定理和结论(2)可证。,2)充分性,定理3.1是充分必要条件,既能判别迭代法收敛性,也可以判别迭代法不收敛的情况。但由于(B)的计算常常比解方程组本身更困难。基本定理和定理3.1可以看到,迭代法收敛与否与迭代矩阵B的性态有关,与初始向量x(0)和右端向量 f 无关。 由于 (B)难于计算,而由结论1又有(B) |B| ,所以当|B|1时,必有 (B) 1,于是得到,19,定理3.2 若|B|1,则由迭代格式x(k+1)=Bx(k)+f 和任意初始向量x(0)产生的迭代序列x(k) 收 敛于准确解x*。且有误差估计,20,定理3
7、.2是迭代法收敛的充分条件,它只能判别收敛的情况,当|B|1时,不能由此断定迭代不收敛。常用 |B|11 或 |B|1判别迭代法收敛。 常用定理3.2中的结论(1)来设置迭代终止的判别条件,即只要相邻两次的迭代结果之差达到误差精度时,迭代终止。 从定理3.2中的结论(2)可知,当|B|的值越小,收敛就越快。也可以用|B|的值来近似估计迭代的次数。在计算出x(1)时,就可估计出迭代次数k,不过估计偏保守,次数一般偏大。,例3.4 判别例3.1和例3.2中的Jacobi迭代法和Seidel迭代法的收敛性。如果取原点作为初始点,需要迭代多少次,能保证误差小于10-6。,解 (1),Jacobi迭代法
8、收敛。因为x0=(0,0,0),容易知道x1=(2.5,3,3). |x0-x1|=3.利用上述定理的第二个公式,可以得到,21,(2),Gauss-Seidel迭代法收敛。类似的可以估计迭代的次数。,22,由于 ,所以Gauss-Seidel方法一般比Jacobi方法收敛快。,例3.5 判别方程组的Jacobi迭代法的收敛性。,解,但,Jacobi迭代法收敛,23,定义3.2 若矩阵 A=(aij)nn 满足 且至少成立严格不等式,则称A是对角占优的。,24,定义3.3 若矩阵 A=(aij)nn 满足 则称A是严格对角占优的。,定义3.4 若矩阵 A 通过行交换和相应的列交换,能够变成 的
9、形式,其中 A11 和 A22 为方阵,则称 A是可约的,否则称 A 是不可约的。,25,所以解该方程组的Jacobi迭代法和Seidel迭代法均收敛。,例3.6,对例3.1的方程组,由于其系数矩阵 是严格对角占优的,故,定理3.5 SOR方法收敛的必要条件是02。,26,证明,定理3.6 如果A是实对称正定矩阵,且02,则SOR方法收敛,注 由定理6的结论,若A是实对称正定矩阵,则Gauss-Seidel 方法收敛,但Jacobi方法不一定收敛。,定理3.8 若A是对称正定矩阵,且是三对角阵,则最佳松弛因子为 其中BJ是Jacobi迭代法的迭代矩阵。 应用中常采取试算方法来确定最佳松弛因子。
10、加速收敛的效果也随问题而有所改变。对有的问题,可加速很多倍,对有的问题则加速不明显.,27,最后提一下关于松驰因子的选取,的选取将影响(B) 的大小,使(B)最小的值称为最佳松弛因子,记为 opt。 opt的选取是一个相当复杂和困难的问题,目前还没有无完善的方法,只有针对一些特殊矩阵有部分结果。,定理3.7 如果A严格对角占优矩阵,则当01时SOR方法收敛。,所以Seidel迭代法及SOR法(0 2)都收敛, 但A不是对角占优阵,就无法判断Jacobi迭代法收敛性,只有改求 (BJ)。,例3.7 若方程组的系数阵为,解,28,试判断它对各种迭代法的收敛性.,29,所以对Jacobi迭代法不收敛。,例3.8 设有方程组
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高中地理选择性必修2教学设计:长江流域协作开发与环境保护
- 初中物理九年级质量与密度二轮复习教学设计
- 高中一年级语文《时代担当与未来想象》教学设计
- 小学二年级美术教学设计《听听画画》核心素养导向下的跨感知表达实践
- 九年级数学《锐角三角函数》教学设计:基于相似模型的核心素养培育路径
- 小学五年级美术珍爱国宝古代陶瓷艺术教学设计
- 高中物理选择性必修一教学设计:电池电动势内阻测量与能源可持续发展
- 七年级语文整本书阅读分层提优教学设计
- 高中劳动技术教学设计:雪冬寻味·大米发糕传统工艺与现代创新
- 初中化学九年级化合价与化学式及物质分类复习教案教学设计
- 2026全球牙科诊疗椅人机工程学创新设计与用户体验提升分析报告
- 2025 重症脓毒症与感染性休克救治指南(中文版)完整原文 + 详细解读
- 洗衣机装配工岗前工艺控制考核试卷含答案
- 《数字人民币智能合约互联互通建设管理规范》编制说明
- 四川省政府采购评审专家考试真题库及答案(完整版)-四川评标评审专家
- ICU三管感染防控集束化管理
- 亚马逊店铺出租合同范本
- 【高盛】变革中的中国:聚焦产能周期-延迟的转折点
- 无创呼吸机气道湿化管理
- 专题01实数的混合运算(60题)专项训练数学北师大版2024八年级上学期
- 临床主动脉夹层患者护理个案汇报
评论
0/150
提交评论