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

《解线性方程组的迭代法课件.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的迭代法课件.ppt（55页珍藏版）》请在三一办公上搜索。

1、1,第6章 解线性方程组的迭代法,6.1 迭代法的基本概念6.2 雅可比迭代法与高斯-赛德尔迭代法,2,1 引言 我们知道，凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。因此，迭代法亦是求解线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。,6.1 迭代法的基本概念,3,2 迭代法的基本思想 迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值 ，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的

2、方程组的近似解。,迭代法的基本思想,设 非奇异， ，则线性方程组 有惟一解 ，经过变换构造出一个等价同解方程组,4,将上式改写成迭代式选定初始向量 ,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法如果 存在极限 则称迭代法是收敛的，否则就是发散的。,迭代法的基本思想,5,收敛时，在迭代公式中当 时， , 则, 故 是方程组 的解。对于给定的方程组可以构造各种迭代公式。并非全部收敛,迭代法的基本思想,6,例1 用迭代法求解线性方程组,解 构造方程组的等价方程组,据此建立迭代公式,取 计算得,例题,7,例题,迭代解离精确解 越来越远迭代不收敛,8,1 雅可比（

3、Jacobi）迭代法 1.雅可比迭代法算法构造,6.2 雅可比迭代法与高斯-赛德尔迭代法,例2 用雅可比迭代法求解方程组,9,例题,解：从方程组的三个方程中分离出 和,10,例题,建立迭代公式,取初始向量进行迭代, 可以逐步得出一个近似解的序列：,（k=1, 2, ）,11,直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有计算结果表明，此迭代过程收敛于方程组的精确解x*= (3, 2, 1)T。,例题,12,写成,例题,考察一般的方程组，将n元线性方程组,13,若 ,分离出变量,例题,据此建立迭代公式,上式称为解方程组的Jacobi

4、迭代公式。,14,2. 雅可比迭代法的矩阵表示 设方程组 的系数矩阵A非奇异，且主对角元素 ，则可将A分裂成,记作 A = L + D + U,雅可比（Jacobi）迭代法,15,则 等价于,即,因为 ，则,这样便得到一个迭代公式,雅可比（Jacobi）迭代法,16,其中,雅可比（Jacobi）迭代法,称为雅可比迭代公式, B称为雅可比迭代矩阵,则有,（k = 0,1,2）,令,17,雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即,雅可比（Jacobi）迭代法,在例2中,由迭代公式写出雅可比迭代矩阵为,18,雅可比（Jacobi）迭代法,(k=0,

5、1,2,),19,3 高斯-塞德尔（Gauss-Seidel）迭代法 1. 高斯-塞德尔迭代法的基本思想 在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求 时用新分量代替旧分量 , 就得到高斯-赛德尔迭代法。其迭代法格式为：,高斯-赛德尔迭代法,(i=1,2,n k=0,1,2,),20,例3 用GaussSeidel 迭代格式解方程组,精确要求为=0.005,解 GaussSeidel 迭代格式为,例题,21,例题,取初始迭代向量 ,迭代结果为：,x* ,22,2. GaussSeidel 迭代法的矩阵表示 将A分裂成A =L+D+U，则 等价

6、于 ( L+D+U )x = b ，于是,则高斯塞德尔迭代过程,因为 ,所以,则高斯-塞德尔迭代形式为：,故,令,高斯-赛德尔迭代法,23,我们知道, 对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式，但并非一定收敛。现在分析它们的收敛性。 对于方程组 经过等价变换构造出的等价方程组,在什么条件下迭代序列 收敛？,迭代法的收敛性,24,定理1 迭代公式 收敛的充分必要条件是迭代矩阵G的谱半径 。,迭代法的收敛性,25,由此定理可知，不论是雅可比迭代法、高斯塞德尔迭代法还是简单迭代法，它们收敛的充要条件是其迭代矩阵的谱半径 。,事实上, 在例1中, 迭代矩阵G= ，其

7、特征多项式为,特征值为 -2，-3， , 所以迭代发散,迭代法的收敛性,26,定理2 (迭代法收敛的充分条件)若迭代矩阵G的一种范数 ,则迭代公式收敛。,迭代法的收敛性,27,例5 已知线性方程组,考察用Jacobi迭代和G-S迭代求解时的收敛性解: 雅可比迭代矩阵,例题,28, 将系数矩阵分解,则高斯-塞德尔迭代矩阵,例题,故Jacobi迭代收敛,29,故高斯塞德尔迭代收敛。,例题,30,定理3 设n阶方阵 为对角占优阵, 则非奇异。（证明省略）,迭代法的收敛性,系数矩阵为对角占优阵的线性方程组称作对角占优方程组。,31,定理4 对角占优线性方程组 的雅可比 迭代公式和高斯-赛德尔迭代公式均

8、收敛。,迭代法的收敛性,32,定理5 若方程组 的系数矩阵A是对称正定的， 则GS迭代法收敛。,迭代法的收敛性,33,例6 设求解线性方程组 的雅可比迭代,求证当 1时,相应的高斯-塞德尔迭代收敛,例题,34,证:由于B是雅可比迭代的迭代矩阵,故有,例题,35,系数矩阵 为对角占优阵,故G-S迭代收敛,例题,则,又 1,故有,36,例7 设 ,证明, 求解方程组,的Jacobi迭代与G-S迭代同时收敛或发散,例题,37,证:雅可比迭代矩阵,例题,其谱半径,38,G-S迭代矩阵,其谱半径,显然, 和 同时小于、等于或大于1,因而Jacobi迭代法与G-S迭代法具有相同的收敛性,例题,39,例9

9、考察用雅可比迭代法和高斯-塞德尔迭代 法解线性方程组Ax=b的收敛性，其中,例题,40,解： 先计算迭代矩阵,例题,雅可比矩阵,41,求特征值,例题, ( B ) = 0 1 用雅可比迭代法求解时，迭代过程收敛,42,例题,高斯-塞德尔迭代矩阵,43,例题,1=0,2 =2,3 =2 (G1)=21 用高斯-塞德尔迭代法求解时，迭代过程发散,求特征值,44,例12 讨论用雅可比迭代法和高斯-塞德尔迭代 法解线性方程组Ax=b的收敛性。,例题,45,解： 先计算迭代矩阵,例题,雅可比矩阵,46,求特征值,例题,1 = - 1， 2,3 = 1/2, ( B ) = 1 用雅可比迭代法求解时，迭代

10、过程不收敛,47,求特征值,高斯-塞德尔迭代矩阵,例题,48,例题,1=0, (G1) = 0.3536 1 用高斯-塞德尔迭代法求解时，迭代过程收敛,49,求解AX=b,当取何值时迭代收敛？,例13 给定线性方程组 AX= b 用迭代公式 X(K+1)=X(K)+(b-AX(K) (k=0,1,）,例题,50,解:所给迭代公式的迭代矩阵为,例题,51,即 2-(2-5 )+1- 5 +4 2=0 2-(2-5 )+(1- )(1-4)=0 -(1-)- (1-4)=0 1=1- 2=1-4,例题,(B)=max|1- |, |1-4|1,取0 1/2迭代收敛,52,本章介绍了解线性方程组 迭

11、代法的一些基本理论和具体方法。,本章小结,迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。注意到在使用迭代法,53,解方程组时，其迭代矩阵B和迭代向量f在计算过程中始终不变,迭代法具有循环的计算公式,方法简单，程序实现方便，它的优点是能充分利用系数的稀疏性,适宜解大型稀疏系数矩阵的方程组。迭代法不存在误差累积问题。使用迭代法的关键问题是其收敛性与与收敛速度，收敛性与迭代初值的选取无关，这是比一般非线性方程求根的优越之处。,本章小结,54,在实际计算中，判断一种迭代格式收敛性较麻烦，由于求迭代的谱半径时需要求特征值，当矩阵的阶数较大时，特征值不易求出，通常采用矩阵的任一种范数都小于1或对角占优来判断收敛性。,本章小结,55,本章结束,