解线性方程组的迭代法精选课件.ppt

《解线性方程组的迭代法精选课件.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的迭代法精选课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于解线性方程组的迭代法第一页，本课件共有55页1 1 引言引言 我我们们知知道道，凡凡是是迭迭代代法法都都有有一一个个收收敛敛问问题题，有有时时某某种种方方法法对对一一类类方方程程组组迭迭代代收收敛敛，而而对对另另一一类类方方程程组组进进行行迭迭代代时时就就会会发发散散。一一个个收收敛敛的的迭迭代代法法不不仅仅具具有有程程序序设设计计简简单单，适适于于自自动动计计算算，而而且且较较直直接接法法更更少少的的计计算算量量就就可可获获得得满满意意的的解解。因因此此，迭迭代代法法亦亦是是求求解解线线性性方方程程组组，尤尤其其是是求求解解具具有有大大型型稀稀疏疏矩矩阵阵的线性方程组的重要方法之一。的线

2、性方程组的重要方法之一。6.1 迭代法的基本概念迭代法的基本概念第二页，本课件共有55页2 迭代法的基本思想迭代法的基本思想 迭代法的基本思想是将线性方程组转化为便于迭迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地对所得到的值进行修正，最终，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。获得满足精度要求的方程组的近似解。迭代法的基本思想迭代法的基本思想设设 非奇异，非奇异，则线性方程组，则线性方程组 有惟一解有惟一解 ，经过变换构造出一个等价同，经过变换构造出一个等价同解方

3、程组解方程组第三页，本课件共有55页将上式改写成迭代式将上式改写成迭代式选定初始向量选定初始向量 ,反复不断地使反复不断地使用迭代式逐步逼近方程组的精确解用迭代式逐步逼近方程组的精确解,直到满足精度要直到满足精度要求为止。这种方法称为迭代法求为止。这种方法称为迭代法如果如果 存在极限存在极限 则称迭代法是收敛的，否则就则称迭代法是收敛的，否则就是发散的。是发散的。迭代法的基本思想迭代法的基本思想第四页，本课件共有55页收敛时，在迭代公式收敛时，在迭代公式中当中当 时，时，,则则,故故 是方程组是方程组 的解。的解。对于给定的方程组可以构造各种迭代公式。对于给定的方程组可以构造各种迭代公式。并非

4、全部收敛并非全部收敛 迭代法的基本思想迭代法的基本思想第五页，本课件共有55页例例1 用迭代法求解线性方程组用迭代法求解线性方程组 解解 构造方程组的等价方程组构造方程组的等价方程组据此建立迭代公式据此建立迭代公式 取取 计算得计算得 例题例题第六页，本课件共有55页例题例题迭代解离精确解迭代解离精确解 越来越远迭代不收敛越来越远迭代不收敛 第七页，本课件共有55页1 1 雅可比（雅可比（JacobiJacobi）迭代法）迭代法 1.1.雅可比迭代法算法构造雅可比迭代法算法构造 6.2 雅可比迭代法与高斯雅可比迭代法与高斯-赛德尔迭代法赛德尔迭代法例例2 2 用雅可比迭代法求解方程组用雅可比迭

5、代法求解方程组 第八页，本课件共有55页例题例题解：从方程组的三个方程中分离出解：从方程组的三个方程中分离出 和和 第九页，本课件共有55页例题例题建立迭代公式建立迭代公式 取初始向量取初始向量进行迭代进行迭代,可以逐步得出一个近似解的序列：可以逐步得出一个近似解的序列：（k=1,2,）第十页，本课件共有55页直到求得的近似解能达到预先要求的精度，则迭代过直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。程终止，以最后得到的近似解作为线性方程组的解。当迭代到第当迭代到第10次有次有计算结果表明，此迭代过程收敛于方程组的精计算结果表明，此迭代过程收敛于方

6、程组的精确解确解x*=(3,2,1)T。例题例题第十一页，本课件共有55页写成写成 例题例题考察一般的方程组，将考察一般的方程组，将n n元线性方程组元线性方程组 第十二页，本课件共有55页13若若 ,分离出变量分离出变量 例题例题据此建立迭代公式据此建立迭代公式 上式称为解方程组的上式称为解方程组的Jacobi迭代公式。迭代公式。第十三页，本课件共有55页2.雅可比迭代法的矩阵表示雅可比迭代法的矩阵表示 设方程组设方程组 的系数矩阵的系数矩阵A A非奇异，且主对非奇异，且主对角元素角元素 ，则可将，则可将A A分裂成分裂成 记作记作 A=L+D+U 雅可比（雅可比（Jacobi）迭代法）迭代

7、法第十四页，本课件共有55页则则 等价于等价于即即因为因为 ，则则这样便得到一个迭代公式这样便得到一个迭代公式雅可比（雅可比（Jacobi）迭代法）迭代法第十五页，本课件共有55页其中其中 雅可比（雅可比（Jacobi）迭代法）迭代法称为雅可比迭代公式称为雅可比迭代公式,B称为雅可比迭代矩阵称为雅可比迭代矩阵则有则有（k=0,1,2）令令第十六页，本课件共有55页雅可比迭代矩阵表示法，主要是用来讨论其收敛性，雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。实际计算中，要用雅可比迭代法公式的分量形式。即即 雅可比（雅可比（Jacobi）迭代法）迭代法在例

8、在例2中中,由迭代公式写出雅可比迭代矩阵为由迭代公式写出雅可比迭代矩阵为 第十七页，本课件共有55页雅可比（雅可比（Jacobi）迭代法）迭代法(k=0,1,2,)第十八页，本课件共有55页3 高斯高斯-塞德尔（塞德尔（Gauss-Seidel）迭代法迭代法 1.高斯高斯-塞德尔迭代法的基本思想塞德尔迭代法的基本思想 在在Jacobi迭迭代代法法中中，每每次次迭迭代代只只用用到到前前一一次次的的迭迭代代值值，若若每每次次迭迭代代充充分分利利用用当当前前最最新新的的迭迭代代值值，即即在在求求 时用新分量时用新分量代代替替旧旧分分量量 ,就就得得到到高高斯斯-赛赛德德尔尔迭迭代代法法。其迭代法格式

9、为：其迭代法格式为：高斯高斯-赛德尔迭代法赛德尔迭代法(i=1,2,=1,2,n k=0,1,2,=0,1,2,)第十九页，本课件共有55页例例3 用用GaussSeidel 迭代格式解方程组迭代格式解方程组 精确要求为精确要求为=0.005=0.005 解解 GaussSeidel 迭代格式为迭代格式为例题例题第二十页，本课件共有55页例题例题取初始迭代向量取初始迭代向量 ,迭代结果为：迭代结果为：x*第二十一页，本课件共有55页2.GaussSeidel 迭代法的矩阵表示迭代法的矩阵表示 将将A分裂成分裂成A=L+D+U，则则 等价于等价于 (L+D+U)x=b，于是，于是,则高斯则高斯塞

10、德尔迭代过程塞德尔迭代过程 因为因为 ,所以所以 则高斯则高斯-塞德尔迭代形式为：塞德尔迭代形式为：故故 令令 高斯高斯-赛德尔迭代法赛德尔迭代法第二十二页，本课件共有55页我们知道我们知道,对于给定的方程组可以构造成简单迭代公对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯式、雅可比迭代公式、高斯-塞德尔迭代公式，但并塞德尔迭代公式，但并非一定收敛。现在分析它们的收敛性。非一定收敛。现在分析它们的收敛性。对对于于方方程程组组 经经过过等等价价变变换换构构造造出出的的等等价价方方程组程组 在什么条件下迭代序列在什么条件下迭代序列 收敛？收敛？迭代法的收敛性迭代法的收敛性第二十三页，

11、本课件共有55页定理定理1 1 迭代公式迭代公式 收敛的充收敛的充分必要条件是迭代矩阵分必要条件是迭代矩阵G的谱半径的谱半径 。迭代法的收敛性迭代法的收敛性第二十四页，本课件共有55页由此定理可知，不论是雅可比迭代法、高斯由此定理可知，不论是雅可比迭代法、高斯塞德尔塞德尔迭代法还是简单迭代法，它们收敛的充要条件是其迭迭代法还是简单迭代法，它们收敛的充要条件是其迭代矩阵的谱半径代矩阵的谱半径 。事实上事实上,在例在例1中中,迭代矩阵迭代矩阵G=，其特征多项式为其特征多项式为,特征值为特征值为-2，-3，,所以迭代发散所以迭代发散 迭代法的收敛性迭代法的收敛性第二十五页，本课件共有55页定理定理2

12、(2(迭代法收敛的充分条件迭代法收敛的充分条件)若迭代矩阵若迭代矩阵G G的一种范数的一种范数 ,则迭代公式则迭代公式收敛。收敛。迭代法的收敛性迭代法的收敛性第二十六页，本课件共有55页例例5 已知线性方程组已知线性方程组 考察用考察用Jacobi迭代和迭代和G-S迭代求解时的收敛性迭代求解时的收敛性解解:雅可比迭代矩阵雅可比迭代矩阵 例题例题第二十七页，本课件共有55页 将系数矩阵分解将系数矩阵分解 则高斯则高斯-塞德尔迭代矩阵塞德尔迭代矩阵 例题例题故故Jacobi迭代收敛迭代收敛 第二十八页，本课件共有55页故高斯故高斯塞德尔迭代收敛。塞德尔迭代收敛。例题例题第二十九页，本课件共有55页

13、 定理定理3 设设n阶方阵阶方阵 为对角占优阵为对角占优阵,则非奇异。则非奇异。（证明省略）（证明省略）迭代法的收敛性迭代法的收敛性系数矩阵为对角占优阵的线性方程组称作对角占优方程组。系数矩阵为对角占优阵的线性方程组称作对角占优方程组。第三十页，本课件共有55页定理定理4 对角占优线性方程组对角占优线性方程组 的雅可比的雅可比 迭代公式和高斯迭代公式和高斯-赛德尔迭代公式均收敛。赛德尔迭代公式均收敛。迭代法的收敛性迭代法的收敛性第三十一页，本课件共有55页定理定理5 若方程组若方程组 的系数矩阵的系数矩阵A是对称正定的，是对称正定的，则则GS迭代法收敛。迭代法收敛。迭代法的收敛性迭代法的收敛性

14、第三十二页，本课件共有55页例例6 设求解线性方程组设求解线性方程组 的雅可比迭代的雅可比迭代 求证当求证当 1 1时时,相应的高斯相应的高斯-塞德尔迭代收敛塞德尔迭代收敛 例题例题第三十三页，本课件共有55页34证证:由于由于B B是雅可比迭代的迭代矩阵是雅可比迭代的迭代矩阵,故有故有 例题例题第三十四页，本课件共有55页系数矩阵系数矩阵 为对角占优阵为对角占优阵,故故G-SG-S迭代收敛迭代收敛 例题例题则则 又又 1,1,故有故有 第三十五页，本课件共有55页例例7 设设 ,证明证明,求解方程组求解方程组 的的Jacobi迭代与迭代与G-S迭代同时收敛或发散迭代同时收敛或发散 例题例题第

15、三十六页，本课件共有55页37证证:雅可比迭代矩阵雅可比迭代矩阵 例题例题其谱半径其谱半径 第三十七页，本课件共有55页G-SG-S迭代矩阵迭代矩阵 其谱半径其谱半径 显然显然,和和 同时小于、等于或大于同时小于、等于或大于1,因而因而Jacobi迭代法与迭代法与G-S迭代法具有相同的收敛性迭代法具有相同的收敛性 例题例题第三十八页，本课件共有55页例例9 考察用考察用雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=b的收敛性，其中的收敛性，其中例题例题第三十九页，本课件共有55页40解：解：先计算迭代矩阵先计算迭代矩阵例题例题雅可比矩阵雅可比矩阵

16、第四十页，本课件共有55页求特征值求特征值例题例题 (B)=0 1)=21 用高斯用高斯-塞德尔迭代塞德尔迭代法求解时，迭代过程发散法求解时，迭代过程发散求特征值求特征值第四十三页，本课件共有55页例例12 讨论用讨论用雅可比迭代法和雅可比迭代法和高斯高斯-塞德尔迭代塞德尔迭代 法解线性方程组法解线性方程组Ax=bAx=b的收敛性。的收敛性。例题例题第四十四页，本课件共有55页45解：解：先计算迭代矩阵先计算迭代矩阵例题例题雅可比矩阵雅可比矩阵第四十五页，本课件共有55页求特征值求特征值例题例题 1=-1，2,3=1/2 (B)=1 用用雅可比迭代法求解时，迭代过程不收敛雅可比迭代法求解时，迭

17、代过程不收敛第四十六页，本课件共有55页求特征值求特征值高斯高斯-塞德尔迭代矩阵塞德尔迭代矩阵例题例题第四十七页，本课件共有55页例题例题 1=0,(G1)=0.3536 1 用用高斯高斯-塞德尔迭代塞德尔迭代法求解时，迭代过程收敛法求解时，迭代过程收敛第四十八页，本课件共有55页求解求解AX=b,当当 取何取何值时迭代收敛？值时迭代收敛？例例13 给定线性方程组给定线性方程组 AX=b 用迭代公式用迭代公式 X(K+1)=X(K)+(b-AX(K)(k=0,1,）例题例题第四十九页，本课件共有55页50解解:所给迭代公式的迭代矩阵为所给迭代公式的迭代矩阵为例题例题第五十页，本课件共有55页即

18、即 2-(2-5 )+1-5 +4+4 2 2=0=0 2-(2-5 )+(1-)(1-4)=0)=0 -(1-)-(1-4)=0=0 1=1-2=1-4 例题例题(B)=max|1-|,|1-4|1取取0 1/21/2迭代收敛迭代收敛第五十一页，本课件共有55页 本章介绍了解线性方程组本章介绍了解线性方程组 迭代法的一些基迭代法的一些基本理论和具体方法。本理论和具体方法。本章小结本章小结迭代法是一种逐次逼近的方法，即对任意给定的初始近迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组

19、的解。注意到在使用迭代法列的极限为方程组的解。注意到在使用迭代法第五十二页，本课件共有55页 解方程组时，其迭代矩阵解方程组时，其迭代矩阵B和迭代向量和迭代向量f在计算过程中始在计算过程中始终不变终不变,迭代法具有循环的计算公式迭代法具有循环的计算公式,方法简单，程序方法简单，程序实现方便，它的优点是能充分利用系数的稀疏性实现方便，它的优点是能充分利用系数的稀疏性,适适宜解大型稀疏系数矩阵的方程组。迭代法不存在误差宜解大型稀疏系数矩阵的方程组。迭代法不存在误差累积问题。使用迭代法的关键问题是其收敛性与与收累积问题。使用迭代法的关键问题是其收敛性与与收敛速度，收敛性与迭代初值的选取无关，这是比一般敛速度，收敛性与迭代初值的选取无关，这是比一般非线性方程求根的优越之处。非线性方程求根的优越之处。本章小结本章小结第五十三页，本课件共有55页在在实实际际计计算算中中，判判断断一一种种迭迭代代格格式式收收敛敛性性较较麻麻烦烦，由由于于求求迭迭代代的的谱谱半半径径时时需需要要求求特特征征值值，当当矩矩阵阵的的阶阶数数较较大大时时，特特征征值值不不易易求求出出，通通常常采采用用矩矩阵阵的的任任一一种种范范数数都都小小于于1或或对角占优来判断收敛性。对角占优来判断收敛性。本章小结本章小结第五十四页，本课件共有55页感感谢谢大大家家观观看看第五十五页，本课件共有55页