迭代法收敛条件课件

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