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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,6,章 解线性方程组的迭代法,6.1,迭代法,的基本概念,6.2,雅可比迭代法与高斯,-,赛德尔迭代法,1,引言,我们知道，凡是迭代法都有一个收敛问题，有时某种方法对一类方程组迭代收敛，而对另一类方程组进行迭代时就会发散。一个收敛的迭代法不仅具有程序设计简单，适于自动计算，而且较直接法更少的计算量就可获得满意的解。因此，迭代法亦是求解线性方程组，尤其是求解具有大型稀疏矩阵的线性方程组的重要方法之一。,6.1,迭代法的基本概念,2,迭代法的基本思想,迭代法的基本思想是将线性方程组转化为便于迭代的等价方程组，对任选一组初始值,，按某种计算规则，不断地对所得到的值进行修正，最终获得满足精度要求的方程组的近似解。,迭代法的基本思想,设 非奇异，则线性方程组,有惟一解 ，经过变换构造出一个等价同解方程组,将上式改写成迭代式,选定初始向量 ,反复不断地使用迭代式逐步逼近方程组的精确解,直到满足精度要求为止。这种方法称为迭代法,如果 存在极限,则称迭代法是收敛的，否则就是发散的。,迭代法的基本思想,收敛时，在迭代公式,中当 时，,则,故 是方程组 的解。,对于给定的方程组可以构造各种迭代公式。,并非全部收敛,迭代法的基本思想,例,1,用迭代法求解线性方程组,解 构造方程组的等价方程组,据此建立迭代公式,取,计算得,例题,例题,迭代解离精确解 越来越远迭代不收敛,1,雅可比（,Jacobi,）迭代法,1.,雅可比迭代法算法构造,6.2,雅可比迭代法与高斯,-,赛德尔迭代法,例,2,用雅可比迭代法求解方程组,例题,解：从方程组的三个方程中分离出 和,例题,建立迭代公式,取初始向量,进行迭代,可以逐步得出一个近似解的序列：,（,k=1,2,）,直到求得的近似解能达到预先要求的精度，则迭代过程终止，以最后得到的近似解作为线性方程组的解。当迭代到第10次有,计算结果表明，此迭代过程收敛于方程组的精,确解,x,*,=(3,2,1),T,。,例题,写成,例题,考察一般的方程组，将,n,元线性方程组,若 ,分离出变量,例题,据此建立迭代公式,上式称为解方程组的,Jacobi,迭代公式。,2,.,雅可比迭代法的矩阵表示,设方程组 的系数矩阵,A,非奇异，且主对,角元素 ，则可将,A,分裂成,记作,A=L+D+U,雅可比（,Jacobi,）迭代法,则 等价于,即,因为,，,则,这样便得到一个迭代公式,雅可比（,Jacobi,）迭代法,其中,雅可比（,Jacobi,）迭代法,称为雅可比迭代公式,B,称为雅可比迭代矩阵,则有,（,k=0,1,2）,令,雅可比迭代矩阵表示法，主要是用来讨论其收敛性，实际计算中，要用雅可比迭代法公式的分量形式。即,雅可比（,Jacobi,）迭代法,在例,2,中,由迭代公式写出雅可比迭代矩阵为,雅可比（,Jacobi,）迭代法,(,k=0,1,2,),3,高斯-塞德尔（,Gauss-Seidel）,迭代法,1.,高斯-塞德尔迭代法的基本思想,在,Jacobi,迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用当前最新的迭代值，即在求 时用新分量,代替旧分量 ,就得到高斯-赛德尔迭代法。其迭代法格式为：,高斯,-,赛德尔迭代法,(,i,=1,2,n,k,=0,1,2,),例,3,用,Gauss,Seidel,迭代格式解方程组,精确要求为,=0.005,解,Gauss,Seidel,迭代格式为,例题,例题,取初始迭代向量 ,迭代结果为：,x,*,2.GaussSeidel,迭代法的矩阵表示,将,A,分裂成,A=L+D+U，,则 等价于,(,L+D+U)x=b,，于是,则高斯塞德尔迭代过程,因为 ,所以,则高斯-塞德尔迭代形式为：,故,令,高斯,-,赛德尔迭代法,我们知道,对于给定的方程组可以构造成简单迭代公式、雅可比迭代公式、高斯-塞德尔迭代公式，但并非一定收敛。现在分析它们的收敛性。,对于方程组 经过等价变换构造出的等价方程组,在什么条件下迭代序列 收敛？,迭代法的收敛性,定理,1,迭代公式 收敛的充分必要条件是迭代矩阵,G,的谱半径 。,迭代法的收敛性,由此定理可知，不论是雅可比迭代法、高斯,塞德尔迭代法还是简单迭代法，它们收敛的充要条件是其迭代矩阵的谱半径 。,事实上,在例,1,中,迭代矩阵,G=，,其特征多项式为,特征值为-2，-3，,所以迭代发散,迭代法的收敛性,定理,2,(,迭代法收敛的充分条件),若迭代矩阵,G,的一种范数 ,则迭代公式,收敛。,迭代法的收敛性,例,5,已知线性方程组,考察用,Jacobi,迭代和,G-S,迭代求解时的收敛性,解:雅可比迭代矩阵,例题,将系数矩阵分解,则高斯-塞德尔迭代矩阵,例题,故,Jacobi,迭代收敛,故高斯,塞德尔迭代收敛。,例题,定理,3,设,n,阶方阵 为对角占优阵,则非奇异。,（证明省略）,迭代法的收敛性,系数矩阵为对角占优阵的线性方程组称作对角占优方程组。,定理,4,对角占优线性方程组 的雅可比,迭代公式和高斯-赛德尔迭代公式均收敛。,迭代法的收敛性,定理,5,若方程组 的系数矩阵,A,是对称正定的，,则,GS,迭代法收敛。,迭代法的收敛性,例,6,设求解线性方程组 的雅可比迭代,求证当 1时,相应的高斯-塞德尔迭代收敛,例题,证:由于,B,是雅可比迭代的迭代矩阵,故有,例题,系数矩阵 为对角占优阵,故,G-S,迭代收敛,例题,则,又 1,故有,例,7,设 ,证明,求解方程组,的,Jacobi,迭代与,G-S,迭代同时收敛或发散,例题,证:雅可比迭代矩阵,例题,其谱半径,G-S,迭代矩阵,其谱半径,显然,和 同时小于、等于或大于1,因而,Jacobi,迭代法与,G-S,迭代法具有相同的收敛性,例题,例,9,考察用,雅可比迭代法和,高斯-塞德尔迭代,法解线性方程组,Ax=b,的收敛性，其中,例题,解：先计算迭代矩阵,例题,雅可比矩阵,求特征值,例题,(,B)=0 1,用高斯-塞德尔迭代,法求解时，迭代过程发散,求特征值,例,12,讨论用,雅可比迭代法和,高斯-塞德尔迭代,法解线性方程组,Ax=b,的收敛性。,例题,解：先计算迭代矩阵,例题,雅可比矩阵,求特征值,例题,1,=-1，,2,3,=1/2,(,B)=1,用,雅可比迭代法求解时，迭代过程不收敛,求特征值,高斯-塞德尔迭代矩阵,例题,例题,1,=0,(,G,1,)=0.3536 1,用高斯-塞德尔迭代,法求解时，迭代过程收敛,求解,AX=b,当,取何,值时迭代收敛？,例,13,给定线性方程组,AX=b,用迭代公式,X,(K+1),=,X,(K),+,(b,-A,X,(K),)(k=0,1,）,例题,解:所给迭代公式的迭代矩阵为,例题,即,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,迭代收敛,本章介绍了解线性方程组 迭代法的一些基本理论和具体方法。,本章小结,迭代法是一种逐次逼近的方法，即对任意给定的初始近似解向量，按照某种方法逐步生成近似解序列，使解序列的极限为方程组的解。注意到在使用迭代法,解方程组时，其迭代矩阵,B,和迭代向量,f,在计算过程中始终不变,迭代法具有循环的计算公式,方法简单，程序实现方便，它的优点是能充分利用系数的稀疏性,适宜解大型稀疏系数矩阵的方程组。迭代法不存在误差累积问题。使用迭代法的关键问题是其收敛性与与收敛速度，收敛性与迭代初值的选取无关，这是比一般非线性方程求根的优越之处。,本章小结,在实际计算中，判断一种迭代格式收敛性较麻烦，由于求迭代的谱半径时需要求特征值，当矩阵的阶数较大时，特征值不易求出，通常采用矩阵的任一种范数都小于1或对角占优来判断收敛性。,本章小结,本章结束,