迭代法的收敛条件课件.ppt

1、1解线性方程组的迭代法解线性方程组的迭代法3.5 迭代法的收敛条件迭代法的收敛条件3.5.1 3.5.1 矩阵的谱半径矩阵的谱半径迭代法的收敛性与迭代矩阵的特征值有关。迭代法的收敛性与迭代矩阵的特征值有关。定义定义3.33.3 设设A为为n阶方阵阶方阵，),2,1(nii 为为A的特征值的特征值，称特征值模的最大值为矩阵称特征值模的最大值为矩阵A的的谱半径谱半径，记为记为1maxiin)223(12(,)n()A称为矩阵称为矩阵 A 的谱的谱.2解线性方程组的迭代法解线性方程组的迭代法由特征值的定义容易得出，矩阵由特征值的定义容易得出，矩阵 个kkAAAA12(,)(1,2,),kkknk()

2、()kkAA)233(矩阵的谱半径与范数有以下关系。矩阵的谱半径与范数有以下关系。的谱是的谱是因而因而3解线性方程组的迭代法解线性方程组的迭代法定理定理3.33.3 设设 A为任意为任意n阶方阵阶方阵，为任意由向量为任意由向量范数诱导出的矩阵范数，则范数诱导出的矩阵范数，则()AA证明证明 对对A的任一特征值的任一特征值i及相应的特征向量及相应的特征向量,iu都有都有iiuiiuiAu iA u因为因为iu为非零向量，于是有为非零向量，于是有Ai由由i的任意性即得的任意性即得AA)(4解线性方程组的迭代法解线性方程组的迭代法定理定理3.43.4设设A为为n阶方阵阶方阵，则对任意正数则对任意正数

3、,存在一存在一种矩阵范数种矩阵范数使得使得)(AA证明参看证明参看.对任意对任意n 阶方阵阶方阵 A,一般不存在矩阵范数一般不存在矩阵范数,使得使得().AA但若但若A为对称矩阵，则为对称矩阵，则2()AA下面的结论对建立迭代法的收敛性条件非常重要。下面的结论对建立迭代法的收敛性条件非常重要。5解线性方程组的迭代法解线性方程组的迭代法定理定理3.53.5 设设 A 为为n阶方阵阶方阵，则则0limkkA()1.A证明证明必要性必要性.若若lim0kkA 0limkkA而而)(0kAkkAA)(于是由极限存在准则，有于是由极限存在准则，有0)(limkkA由定义由定义3.23.2得得()1.A的

4、的充要条件充要条件为为所以所以6解线性方程组的迭代法解线性方程组的迭代法充分性充分性.若若()1,A取取,02)(1A由定理由定理3.43.4存在一种存在一种存在一种存在一种,使得使得)(AA12)(1A,kkAAkkAlimkkAlim0所以所以lim0kkA 而而于是于是7解线性方程组的迭代法解线性方程组的迭代法3.5.23.5.2迭代法的收敛条件迭代法的收敛条件定理定理.对任意初始向量对任意初始向量)0(x和右端项和右端项,g由迭代格式由迭代格式gMxxkk)()1(),2,1,0(k)243(产生的向量序列产生的向量序列)(kx收敛的收敛的充要条件充要条件是是()1M证明证明设存在设存

5、在n 维向量维向量*x使得使得()*limkkxx则则*x满足满足gMxxp98解线性方程组的迭代法解线性方程组的迭代法由迭代公式由迭代公式(3-24),有有xxk)(2(2)()kMxx(1)kMxg)()1(xxMk)()0(xxMk于是有于是有)(lim)0(xxMkk0)(lim)(xxkk因为因为)0(x为任意为任意n维向量维向量,因此上式成立必须因此上式成立必须0limkkM由定理由定理3.51)(MMxg9解线性方程组的迭代法解线性方程组的迭代法反之，若反之，若,1)(M则则1不是不是M 的的特征值特征值，因而有因而有0,IM于是对任意于是对任意n维向量维向量 g,方程组方程组(

6、)IM xg有唯一解，记为有唯一解，记为,x即即gMxx并且并且0limkkM又因为又因为xxk)()()1(xxMk)()0(xxMk所以，对任意初始向量所以，对任意初始向量,)0(x都有都有)(lim)(xxkk0)(lim)0(xxMkk即由迭代公式即由迭代公式(3-24)(3-24)产生的向量序列产生的向量序列 kx收敛收敛.p710解线性方程组的迭代法解线性方程组的迭代法由定理由定理3.43.4即得即得推论推论在定理在定理3.63.6的条件下的条件下,若若,1M则则 kx收敛收敛.推论推论松弛法收敛的松弛法收敛的必要条件必要条件是是02。证明证明设松弛法的迭代矩阵设松弛法的迭代矩阵M

7、有特征值有特征值12,.n因为因为det()M12n nM)(由定理由定理3.63.6，松弛法收敛必有，松弛法收敛必有1)det(Mp1911解线性方程组的迭代法解线性方程组的迭代法又因为又因为det()MUDLD)1()(11)(LDnnaaa22111UD)1(nnnaaa2211)1()det(M1)1(n于是有于是有所以所以021()(1)MDLDU12解线性方程组的迭代法解线性方程组的迭代法定理定理3.6表明，表明，迭代法收敛与否只决定于迭代迭代法收敛与否只决定于迭代矩阵的谱半径，矩阵的谱半径，与初始向量及方程组的右端项无关。与初始向量及方程组的右端项无关。对同一方程组，由于不同的迭

8、代法迭代矩阵不同，对同一方程组，由于不同的迭代法迭代矩阵不同，因此可能出现有的方法收敛，有的方法发散的情因此可能出现有的方法收敛，有的方法发散的情形形.13解线性方程组的迭代法解线性方程组的迭代法例例讨论用讨论用Jacobi迭代法与迭代法与Gauss-Seidel迭代法求解方程组迭代法求解方程组的收敛性的收敛性解解由定理由定理3.63.6，迭代法是否收敛等价于迭代，迭代法是否收敛等价于迭代矩阵的谱半径是否小于矩阵的谱半径是否小于，因为因为123223xxx1232xxx123221xxx故应先求迭代矩阵。故应先求迭代矩阵。14解线性方程组的迭代法解线性方程组的迭代法122111221A0220

9、01000LJacobi迭代法的迭代格式为迭代法的迭代格式为100010001D000100220U1kx()kBxg迭代矩阵为迭代矩阵为p161BID A15解线性方程组的迭代法解线性方程组的迭代法BID A1122111221I其特征方程为其特征方程为IB 221122 30因此有因此有,1230于是于是,10)(B所以所以Jacobi迭代法收敛迭代法收敛.02210122034442216解线性方程组的迭代法解线性方程组的迭代法如果用如果用Gauss-Seidel迭代迭代，100110221DL容易求出容易求出1200110011LD于是迭代矩阵为于是迭代矩阵为ULDM1)(1)(),k

10、kxMxd其中其中又又ULDM1100022110001021000 022023002p1417解线性方程组的迭代法解线性方程组的迭代法其特征方程为其特征方程为MI0)2(222023002特征值为特征值为,2,0321故故,12)(M所以所以，Gauss-Seidel迭代法发散迭代法发散.18解线性方程组的迭代法解线性方程组的迭代法例也说明了例也说明了20确实只是松弛法确实只是松弛法收敛的必要条件，而非充要条件，收敛的必要条件，而非充要条件，因为因为Gauss-Seidel迭代即为迭代即为1的情形的情形.定理定理3.63.6虽然给出了判别迭代法收敛的充要条件，虽然给出了判别迭代法收敛的充要

11、条件，但实际使用是很不方便但实际使用是很不方便 。因为求逆矩阵和特征值的。因为求逆矩阵和特征值的难度并不亚于用直接方法求解线性方程组。难度并不亚于用直接方法求解线性方程组。推论推论与与推论推论使用起来方便得多使用起来方便得多，但它们分别给出收敛的但它们分别给出收敛的充分条件与必要条件，许多情形下，不能起作用充分条件与必要条件，许多情形下，不能起作用.19解线性方程组的迭代法解线性方程组的迭代法如例中，两个方法均有如例中，两个方法均有,1B,1M由推论无法判别收敛性。由推论无法判别收敛性。特殊的系数矩阵给出几个常用的判敛条件。特殊的系数矩阵给出几个常用的判敛条件。下面对一些下面对一些定义定义3.

12、4(1)(严格对角占优严格对角占优)()ijn nAa设设如果如果A满足满足1niiijjj iaa),2,1(ni则则称称A为严格对角占优阵为严格对角占优阵.20解线性方程组的迭代法解线性方程组的迭代法nijjijiiaa1)253(),2,1(ni且至少有一个且至少有一个i 值值，使上式中不等号严格成立，则使上式中不等号严格成立，则称为称为A弱对角占优阵弱对角占优阵。定义定义3.53.5如果矩阵如果矩阵不能通过行的互换和相应列的互不能通过行的互换和相应列的互换成为形式换成为形式1112220AAAA(2)若若n阶方阵阶方阵)(ijaA满足满足其中其中2211,AA为方阵，则称为方阵，则称A

13、 为为不可约不可约.21解线性方程组的迭代法解线性方程组的迭代法如例如例的系数矩阵矩阵的系数矩阵矩阵214031012A是可约的是可约的.)(ijaA为为n阶方阵阶方阵2n 若存在非空集若存在非空集1,2,In使得当使得当,Ii 而而0,ija 显然显然,若若A是可约的是可约的,则则A所对应的线性方程组所对应的线性方程组Axb可化为低阶方程组可化为低阶方程组.jI时有时有则则A是可约阵是可约阵.122111221A是不可约的是不可约的.而而一般地，设一般地，设22解线性方程组的迭代法解线性方程组的迭代法几个常用的收敛条件几个常用的收敛条件.设有线性方程组设有线性方程组,bAx 下列结论成立下列

14、结论成立：1.若若A为严格对角占优阵或不可约弱对角占优阵为严格对角占优阵或不可约弱对角占优阵,则则Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.01,02,02.2.若若A为严格对角占优阵为严格对角占优阵,则松弛法收敛则松弛法收敛.3.若若A为对称正定阵为对称正定阵,则松弛法收敛则松弛法收敛.因此有因此有:若若A为对称正定阵为对称正定阵,则松弛法收敛的则松弛法收敛的充分必要充分必要条件条件是是4.若若A为对称正定阵为对称正定阵,则则Gauss-Seidel迭代法收敛迭代法收敛.23解线性方程组的迭代法解线性方程组的迭代法例例:考虑考虑51121012110AA为

15、严格对角占优阵，故为严格对角占优阵，故Jacobi迭代法与迭代法与Gauss-Seidel迭代均收敛迭代均收敛.210121012A又如例中，系数矩阵又如例中，系数矩阵非严格对角占优非严格对角占优,但但 A为对称正定矩阵为对称正定矩阵,4.1故松弛法收敛。故松弛法收敛。上述结论的证明可参看上述结论的证明可参看 1,7.,bAx 其中其中例例 对线性方程组对线性方程组123812xxx123202324xxx123231530 xxx讨论讨论Jacobi迭代法及迭代法及Gauss-Seidel迭代法的收敛性迭代法的收敛性.解解:Jacobi迭代的迭代矩阵为迭代的迭代矩阵为1301020110,8

16、82301515JB52 5max,20 8 15JB113故故Jacobi迭代法收敛迭代法收敛.(1)()()1232324202020kkkxxx(1)()()2131112888kkkxxx(1)()()3122330151515kkkxxx Gauss-Seidel迭代矩阵迭代矩阵1()GMDLU024036010302552400038316002400GM114故故Gauss-Seidel迭代法收敛迭代法收敛.2023181,23 15A2000080,00 15D00 01 0 0,2 3 0L 023001000U26解线性方程组的迭代法解线性方程组的迭代法,Axb111221

17、112211122A讨论用三种迭代法求解的收敛性。讨论用三种迭代法求解的收敛性。10,1112211810221611122解解:例例4 4 设有方程组设有方程组其中其中11320,141227解线性方程组的迭代法解线性方程组的迭代法02)（B 1102211022110221ID A故不能用条件故不能用条件1 1判别判别Jacobi迭代的收敛性迭代的收敛性.因因A为对称矩阵为对称矩阵,且其各阶主子式皆大于零且其各阶主子式皆大于零,故故A为为对称正定矩阵对称正定矩阵,由判别条件由判别条件3,Gauss-Seidel迭代法与迭代法与松弛法松弛法均收敛均收敛.A不是弱对角占优不是弱对角占优,Jac

18、obi迭代法的迭代矩阵为迭代法的迭代矩阵为max 1,1,1B1故推论故推论1 1不能用不能用28解线性方程组的迭代法解线性方程组的迭代法IB0)1()21(211221122112211111(1)2211221111(1)0021002其特征方程其特征方程29解线性方程组的迭代法解线性方程组的迭代法1.B（）值得指出的是，改变方程组中方程的次序，即将系值得指出的是，改变方程组中方程的次序，即将系系数矩阵作行交换，会改变迭代法的收敛性。例如系数矩阵作行交换，会改变迭代法的收敛性。例如 方程组方程组bAx 的系数矩阵为的系数矩阵为49103A有根有根因而因而123112，由定理由定理3.63.

19、6Jacobi迭代法不收敛迭代法不收敛.30解线性方程组的迭代法解线性方程组的迭代法1003904B 21503100M,A xb3015(),().22BMJacobi迭代与迭代与Gauss-Seidel迭代的迭代矩阵分别为迭代的迭代矩阵分别为它们的谱半径为它们的谱半径为由定理由定理3.63.6这两种迭代均不收敛这两种迭代均不收敛.但若交换两个方程的次序但若交换两个方程的次序得原方程组的同解方程组得原方程组的同解方程组其中其中31解线性方程组的迭代法解线性方程组的迭代法10349AA xbA显然显然,是严格对角占优阵是严格对角占优阵,因而对方程组因而对方程组用用Jacobi迭代与迭代与Gau

20、ss-Seidel迭代迭代求解均收敛求解均收敛.32解线性方程组的迭代法解线性方程组的迭代法3.5.33.5.3误差估计误差估计定理定理3.73.7设有迭代格式设有迭代格式(1)(),kkxMxg,x1,M()kxx)263(1()IM,x1(),xIMg(1)(0)1kMxxM若若收敛于收敛于()kx则有误差估计式则有误差估计式证明证明:因为因为()1,MM故故0,IM于是于是存在存在,方程组方程组xMxg(即即有惟一解有惟一解()IM xg)且且从而有从而有p3533解线性方程组的迭代法解线性方程组的迭代法(0)()kMxx(0)1()kMxIMg1(0)()()kMIMIM xg1(0)

21、(1)()()kM IMxx()kxx)273(1)()kM xx()kxx1(0)(1)()kMIMxx取范数得取范数得34解线性方程组的迭代法解线性方程组的迭代法1)(IMIMI（），1()IM1()IM IM1()IMIM1()IM)283(1()IM1()IM IM11M()kxx1(0)(1)()kMIMxx又因为又因为于是于是取范数得取范数得移项得移项得又又35解线性方程组的迭代法解线性方程组的迭代法(1)(0)1kMxxM，(1)(0)(1)lnlnMxxM)293()kxxk 将将(3-28)代入代入(3-27)得得有了误差估计有了误差估计(3-26),根据事先给定的精度根据事

22、先给定的精度可以估算出迭代的次数可以估算出迭代的次数k()kxx1(0)(1)()kMIMxx1()IM11M)273()283(326)p3236解线性方程组的迭代法解线性方程组的迭代法00.10.20.100.20.20.20M，(0)00,0 x (1)7.28.38.4x0.4M，k 410(1 0.4)ln8.4ln0.412.932(1)(),kkxMxg例如对迭代格式例如对迭代格式其中其中7.28.3,8.4g取取410有有代入式代入式(3-29)(3-29)得得(1)(0)(1)lnlnMxxM(1)(0)8.4,xx37解线性方程组的迭代法解线性方程组的迭代法-410.所以需

23、要迭代所以需要迭代1313次才能保证各分量误差绝对值次才能保证各分量误差绝对值不超过不超过实际计算时实际计算时,常常采用事后估计误差的方法常常采用事后估计误差的方法,即利用相邻两次迭代值之差是否达到精度作为停即利用相邻两次迭代值之差是否达到精度作为停机准则机准则.因而下面的结论比定理因而下面的结论比定理3.7 3.7 更实用更实用.38解线性方程组的迭代法解线性方程组的迭代法()(1)1kkMxxM)303()(1)()kkxxM xx(1)1()kM xIMg1(1)(1)()kkM IMxMxg1(1)()()()kkM IMxx()kxx定理定理3.83.8在定理在定理3.73.7的条件

24、下的条件下,有有证明证明:因为因为所以所以39解线性方程组的迭代法解线性方程组的迭代法()kxx()(1)1kkMxxM(),kxx()(1)kkxx1(1)()()kkMIMxx1MMM()kx由定理由定理3.8,3.8,为使为使只要只要即可即可.实际计算时实际计算时,当当不太接近不太接近1 1时时,可用可用作为停机准则作为停机准则,()(1)kkxx即为满足精度即为满足精度之近似解之近似解.拉格朗日拉格朗日(Lagrange)插值插值牛顿牛顿(Newton)插值插值分段线性插值分段线性插值第第5 5章章 插值法插值法 样条插值样条插值埃尔米特埃尔米特(Hermite)插值插值快速傅里叶变换

25、快速傅里叶变换(FFT)应用实例应用实例1生产实践中常常出现这样的问题：生产实践中常常出现这样的问题：给出一批离散样点给出一批离散样点,要求作出一条通过这些点的光滑曲线，以便满足设计要要求作出一条通过这些点的光滑曲线，以便满足设计要求或进行加工求或进行加工.反映在数学上，既已知函数在一些点上得反映在数学上，既已知函数在一些点上得值，寻求它的分析表达式值，寻求它的分析表达式.因为由函数的表格形式不能因为由函数的表格形式不能直接得出表中未列点处的函数值，也不便于研究函数的直接得出表中未列点处的函数值，也不便于研究函数的的性质的性质.此外，有些函数虽然有表达式，但因式子复杂，此外，有些函数虽然有表达

26、式，但因式子复杂，不易计算其值和进行理论分析，也需要构造一个简单不易计算其值和进行理论分析，也需要构造一个简单函数来近似它函数来近似它.解决这种问题的方法有两种解决这种问题的方法有两种：插值法插值法2一类是给出函数一类是给出函数 f x的一些点值，选定一个便于计算的一些点值，选定一个便于计算的函数形式，如多项式，分式线性函数和三角多项式的函数形式，如多项式，分式线性函数和三角多项式等，要求它通过已知样点，由此确定函数等，要求它通过已知样点，由此确定函数 x作为作为 f x的近似的近似.这就是这就是插值法插值法。另一类方法在选定近似函数另一类方法在选定近似函数形式后形式后,不要求近似不要求近似函

27、数过已知样点函数过已知样点,只要求在某种意义只要求在某种意义下它在这些点上的下它在这些点上的总偏差最小总偏差最小.拟合法拟合法.本章主要讨论构造插值多项式的几种常用方法及本章主要讨论构造插值多项式的几种常用方法及其误差其误差.这类方法称为这类方法称为曲线曲线(数据数据)插值法插值法3设函数设函数在区间在区间 yf x,a b上有定义上有定义,它在该区间上它在该区间上n+1个互异点个互异点nxxx,10处的函数值为已知处的函数值为已知,记为记为(),0,1,iiyf xin若存在一个简单函数若存在一个简单函数 P x使得使得,0,1,iiP xyin成立成立,就称就称 P x为为 f x的的插值函数插值函数,点点nxxx,10称为称为插值节点插值节点,区间区间,a b称为称为插值区间插值区间,求插值函数求插值函数 P x的方法称为的方法称为插值法插值法.4