《迭代法的收敛条件ppt课件.ppt》由会员分享，可在线阅读，更多相关《迭代法的收敛条件ppt课件.ppt（43页珍藏版）》请在三一办公上搜索。
1、1,3.5 迭代法的收敛条件,3.5.1 矩阵的谱半径,迭代法的收敛性与迭代矩阵的特征值有关。,定义3.3 设A为n阶方阵，,为,A的特征值，,称特征值模的最大值为矩阵A,的谱半径，,记为,称为矩阵 A 的谱.,2,由特征值的定义容易得出，矩阵,矩阵的谱半径与范数有以下关系。,的谱是,因而,3,定理3.3 设,A为任意n阶方阵，,为任意由向量,范数诱导出的矩阵范数，则,证明 对,的任一特征值,及相应的特征向量,都有,因为,为非零向量，于是有,由,的任意性即得,4,定理3.4,设A为n阶方阵，,则对任意正数,存在一,种矩阵范数,使得,证明参看 .,对任意n,阶方阵 A,一般不存在矩阵范数,使得,
2、但若,A为对称矩阵，则,下面的结论对建立迭代法的收敛性条件非常重要。,5,定理3.5 设 A,为n阶方阵，,则,证明必要性.,若,而,于是由极限存在准则，有,由定义3.2得,的充要条件为,所以,6,充分性.,若,取,由定理3.4存在一种存在一种,使得,所以,而,于是,7,3.5.2迭代法的收敛条件,定理.,对任意初始向量,和右端项,由迭代格式,产生的向量序列,收敛的充要条件是,证明,设存在n 维向量,使得,则,满足,p9,8,由迭代公式(3-24),有,于是有,因为,为任意n维向量,因此上式成立必须,由定理3.5,9,反之，若,则,不是M,的特征值，,因而有,于是对任意n维向量 g,方程组,有
3、唯一解，记为,即,并且,又因为,所以，对任意初始向量,都有,即由迭代公式(3-24)产生的向量序列,收敛.,p7,10,由定理3.4即得,推论在定理3.6的条件下,若,则,收敛.,推论松弛法收敛的必要条件是,证明设松弛法的迭代矩阵,有特征值,因为,由定理3.6，松弛法收敛必有,p19,11,又因为,于是有,所以,12,定理3.6表明，,迭代法收敛与否只决定于迭代,矩阵的谱半径，,与初始向量及方程组的右端项无关。,对同一方程组，由于不同的迭代法迭代矩阵不同，,因此可能出现有的方法收敛，有的方法发散的情,形.,13,例讨论用Jacobi迭代法与Gauss-Seidel,迭代法求解方程组,的收敛性,
4、解由定理3.6，迭代法是否收敛等价于迭代,矩阵的谱半径是否小于，,因为,故应先求迭代矩阵。,14,Jacobi迭代法的迭代格式为,迭代矩阵为,p16,15,其特征方程为,因此有,于是,所以Jacobi迭代法收敛.,16,如果用Gauss-Seidel迭代，,容易求出,于是迭代矩阵为,其中,又,p14,17,其特征方程为,特征值为,故,所以，,Gauss-Seidel迭代法发散.,18,例也说明了,确实只是松弛法,收敛的必要条件，而非充要条件，,因为Gauss-Seidel,迭代即为,的情形.,定理3.6虽然给出了判别迭代法收敛的充要条件，,但实际使用是很不方便 。因为求逆矩阵和特征值的,难度并
5、不亚于用直接方法求解线性方程组。,推论与,推论使用起来方便得多，,但它们分别给出收敛的,充分条件与必要条件，许多情形下，不能起作用.,19,如例中，两个方法均有,由推论无法判别收敛性。,特殊的系数矩阵给出几个常用的判敛条件。,下面对一些,定义3.4(1) (严格对角占优),设,如果A满足,则称A为严格对角占优阵.,20,且至少有一个i,值，使上式中不等号严格成立，则,称为A弱对角占优阵。,定义3.5如果矩阵不能通过行的互换和相应列的互,换成为形式,(2)若,n阶方阵,满足,其中,为方阵，则称A,为不可约.,21,如例的系数矩阵矩阵,是可约的.,为n阶方阵,若存在非空集,使得当,而,显然,若A是
6、可约的,则A所对应的线性方程组,可化为低阶方程组.,时有,则A是可约阵.,是不可约的. 而,一般地，设,22,几个常用的收敛条件.,设有线性方程组,下列结论成立：,1. 若,A为严格对角占优阵或不可约弱对角占优阵,则,Jacobi迭代法和Gauss-Seidel迭代法均收敛.,2. 若A为严格对角占优阵,则松弛法收敛.,3. 若A为对称正定阵,则松弛法收敛.,因此有: 若A为对称正定阵,则松弛法收敛的充分必要,条件是,4. 若A为对称正定阵,则Gauss-Seidel迭代法收敛.,23,例: 考虑,A为严格对角占优阵，故Jacobi迭代法与Gauss-Seidel,迭代均收敛.,又如例中，系数
7、矩阵,非严格对角占优,但,A为对称正定矩阵,故松弛法收敛。,上述结论的证明可参看1,7.,其中,例 对线性方程组,讨论Jacobi迭代法及Gauss-Seidel迭代法的收敛性.,解:,Jacobi迭代的迭代矩阵为,故Jacobi迭代法收敛.,Gauss-Seidel迭代矩阵,故Gauss-Seidel迭代法收敛.,26,讨论用三种迭代法求解的收敛性。,解:,例4,设有方程组,其中,27,故不能用条件1判别Jacobi迭代的收敛性.,因A为对称矩阵,且其各阶主子式皆大于零,故A为,对称正定矩阵,由判别条件3, Gauss-Seidel迭代法与,松弛法,均收敛.,A不是弱对角占优,Jacobi迭
8、代法的迭代矩阵为,故推论1不能用,28,其特征方程,29,值得指出的是，改变方程组中方程的次序，即将系,系数矩阵作行交换，会改变迭代法的收敛性。例如,方程组,的系数矩阵为,有根,因而,由定理3.6,Jacobi迭代法不收敛.,30,Jacobi迭代与Gauss-Seidel迭代的迭代矩阵分别为,它们的谱半径为,由定理3.6,这两种迭代均不收敛.,但若交换两个方程的次序,得原方程组的同解方程组,其中,31,显然,是严格对角占优阵,因而对方程组,用Jacobi迭代与Gauss-Seidel迭代,求解均收敛.,32,3.5.3误差估计,定理3.7设有迭代格式,若,收敛于,则有误差估计式,证明:,因为
9、,故,于是,存在,方程组,(即,有惟一解,),且,从而有,p35,33,取范数得,34,又因为,于是,取范数得,移项得,又,35,将(3-28)代入(3-27)得,有了误差估计(3-26),根据事先给定的精度,可以估算出迭代的次数k,p32,36,例如对迭代格式,其中,取,有,代入式(3-29)得,37,所以需要迭代13次才能保证各分量误差绝对值,不超过,实际计算时, 常常采用事后估计误差的方法,即利用相邻两次迭代值之差是否达到精度作为停,机准则.,因而下面的结论比定理3.7 更实用.,38,定理3.8在定理3.7的条件下,有,证明:,因为,所以,39,由定理3.8,为使,只要,即可.实际计算
10、时, 当,不太接近1时,可用,作为停机准则,即为满足精度,之近似解.,拉格朗日(Lagrange )插值,牛顿(Newton)插值,分段线性插值,第5章 插值法,样条插值,埃尔米特(Hermite)插值,快速傅里叶变换(FFT),应用实例,1,生产实践中常常出现这样的问题：,给出一批离散样点,要求作出一条通过这些点的光滑曲线，以便满足设计要求或进行加工.,反映在数学上，既已知函数在一些点上得,值，寻求它的分析表达式.,因为由函数的表格形式不能,直接得出表中未列点处的函数值，也不便于研究函数的,的性质.,此外，有些函数虽然有表达式，但因式子复杂，,不易计算其值和进行理论分析，也需要构造一个简单,
11、函数来近似它.,解决这种问题的方法有两种：,2,一类是给出函数,的一些点值，选定一个便于计算,的函数形式，如多项式，分式线性函数和三角多项式,等，要求它通过已知样点，由此确定函数,作为,的近似.这就是插值法。,另一类方法在选定近似函数形式后,不要求近似,函数过已知样点,只要求在某种意义下它在这些点上的,总偏差最小.,拟合法.,本章主要讨论构造插值多项式的几种常用方法及其误差.,这类方法称为曲线(数据),3,设函数,在区间,上有定义,它在该区间上,n+1个互异点,处的函数值为已知,记为,若存在一个简单函数,使得,成立, 就称,为,的插值函数,点,称为插值节点, 区间,称为插值区间,求插值函数,的方法称为插值法.,4,
