迭代法的收敛条件优秀PPT.ppt

《迭代法的收敛条件优秀PPT.ppt》由会员分享，可在线阅读，更多相关《迭代法的收敛条件优秀PPT.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、迭代法的收敛条件迭代法的收敛条件第一页，本课件共有43页2解线性方程组的迭代法解线性方程组的迭代法由特征值的定义容易得出，矩阵由特征值的定义容易得出，矩阵矩阵的谱半径与范数有以下关系。矩阵的谱半径与范数有以下关系。的谱是的谱是因而因而第二页，本课件共有43页3解线性方程组的迭代法解线性方程组的迭代法定理定理3.33.3 设设A为任意为任意n阶方阵阶方阵，为任意由向量为任意由向量范数诱导出的矩阵范数，则范数诱导出的矩阵范数，则证明证明 对对的任一特征值的任一特征值及相应的特征向量及相应的特征向量都有都有因为因为为非零向量，于是有为非零向量，于是有由由的任意性即得的任意性即得第三页，本课件共有43

2、页4解线性方程组的迭代法解线性方程组的迭代法定理定理3.43.4设设A为为n阶方阵阶方阵，则对任意正数则对任意正数存在一存在一种矩阵范数种矩阵范数使得使得证明参看证明参看.对任意对任意n 阶方阵阶方阵 A,一般不存在矩阵范数一般不存在矩阵范数使得使得但若但若A为对称矩阵，则为对称矩阵，则下面的结论对建立迭代法的收敛性条件非常重要。下面的结论对建立迭代法的收敛性条件非常重要。第四页，本课件共有43页5解线性方程组的迭代法解线性方程组的迭代法定理定理3.53.5 设设 A为为n阶方阵阶方阵，则则证明证明必要性必要性.若若而而于是由极限存在准则，有于是由极限存在准则，有由定义由定义3.23.2得得的

3、的充要条件充要条件为为所以所以第五页，本课件共有43页6解线性方程组的迭代法解线性方程组的迭代法充分性充分性.若若取取由定理由定理3.43.4存在一种存在一种存在一种存在一种使得使得所以所以而而于是于是第六页，本课件共有43页7解线性方程组的迭代法解线性方程组的迭代法3.5.23.5.2迭代法的收敛条件迭代法的收敛条件定理定理.对任意初始向量对任意初始向量和右端项和右端项由迭代格式由迭代格式产生的向量序列产生的向量序列收敛的收敛的充要条件充要条件是是证明证明设存在设存在n 维向量维向量使得使得则则满足满足p9第七页，本课件共有43页8解线性方程组的迭代法解线性方程组的迭代法由迭代公式由迭代公式

4、(3-24),有有于是有于是有因为因为为任意为任意n维向量维向量,因此上式成立必须因此上式成立必须由定理由定理3.5第八页，本课件共有43页9解线性方程组的迭代法解线性方程组的迭代法反之，若反之，若则则不是不是M的的特征值特征值，因而有因而有于是对任意于是对任意n维向量维向量 g,方程组方程组有唯一解，记为有唯一解，记为即即并且并且又因为又因为所以，对任意初始向量所以，对任意初始向量都有都有即由迭代公式即由迭代公式(3-24)(3-24)产生的向量序列产生的向量序列收敛收敛.p7第九页，本课件共有43页10解线性方程组的迭代法解线性方程组的迭代法由定理由定理3.43.4即得即得推论推论在定理在

5、定理3.63.6的条件下的条件下,若若则则收敛收敛.推论推论松弛法收敛的松弛法收敛的必要条件必要条件是是证明证明设松弛法的迭代矩阵设松弛法的迭代矩阵有特征值有特征值因为因为由定理由定理3.63.6，松弛法收敛必有，松弛法收敛必有p19第十页，本课件共有43页11解线性方程组的迭代法解线性方程组的迭代法又因为又因为于是有于是有所以所以第十一页，本课件共有43页12解线性方程组的迭代法解线性方程组的迭代法定理定理3.6表明，表明，迭代法收敛与否只决定于迭代迭代法收敛与否只决定于迭代矩阵的谱半径，矩阵的谱半径，与初始向量及方程组的右端项无关。与初始向量及方程组的右端项无关。对同一方程组，由于不同的迭

6、代法迭代矩阵不同，对同一方程组，由于不同的迭代法迭代矩阵不同，因此可能出现有的方法收敛，有的方法发散的情因此可能出现有的方法收敛，有的方法发散的情形形.第十二页，本课件共有43页13解线性方程组的迭代法解线性方程组的迭代法例例讨论用讨论用Jacobi迭代法与迭代法与Gauss-Seidel迭代法求解方程组迭代法求解方程组的收敛性的收敛性解解由定理由定理3.63.6，迭代法是否收敛等价于迭代，迭代法是否收敛等价于迭代矩阵的谱半径是否小于矩阵的谱半径是否小于，因为因为故应先求迭代矩阵。故应先求迭代矩阵。第十三页，本课件共有43页14解线性方程组的迭代法解线性方程组的迭代法Jacobi迭代法的迭代格

7、式为迭代法的迭代格式为迭代矩阵为迭代矩阵为p16第十四页，本课件共有43页15解线性方程组的迭代法解线性方程组的迭代法其特征方程为其特征方程为因此有因此有于是于是所以所以Jacobi迭代法收敛迭代法收敛.第十五页，本课件共有43页16解线性方程组的迭代法解线性方程组的迭代法如果用如果用Gauss-Seidel迭代迭代，容易求出容易求出于是迭代矩阵为于是迭代矩阵为其中其中又又p14第十六页，本课件共有43页17解线性方程组的迭代法解线性方程组的迭代法其特征方程为其特征方程为特征值为特征值为故故所以所以，Gauss-Seidel迭代法发散迭代法发散.第十七页，本课件共有43页18解线性方程组的迭代

8、法解线性方程组的迭代法例也说明了例也说明了确实只是松弛法确实只是松弛法收敛的必要条件，而非充要条件，收敛的必要条件，而非充要条件，因为因为Gauss-Seidel迭代即为迭代即为的情形的情形.定理定理3.63.6虽然给出了判别迭代法收敛的充要条件，虽然给出了判别迭代法收敛的充要条件，但实际使用是很不方便但实际使用是很不方便 。因为求逆矩阵和特征值的。因为求逆矩阵和特征值的难度并不亚于用直接方法求解线性方程组。难度并不亚于用直接方法求解线性方程组。推论推论与与推论推论使用起来方便得多使用起来方便得多，但它们分别给出收敛的但它们分别给出收敛的充分条件与必要条件，许多情形下，不能起作用充分条件与必要

9、条件，许多情形下，不能起作用.第十八页，本课件共有43页19解线性方程组的迭代法解线性方程组的迭代法如例中，两个方法均有如例中，两个方法均有由推论无法判别收敛性。由推论无法判别收敛性。特殊的系数矩阵给出几个常用的判敛条件。特殊的系数矩阵给出几个常用的判敛条件。下面对一些下面对一些定义定义3.4(1)(严格对角占优严格对角占优)设设如果如果A满足满足则则称称A为严格对角占优阵为严格对角占优阵.第十九页，本课件共有43页20解线性方程组的迭代法解线性方程组的迭代法且至少有一个且至少有一个i值值，使上式中不等号严格成立，则使上式中不等号严格成立，则称为称为A弱对角占优阵弱对角占优阵。定义定义3.53

10、.5如果矩阵如果矩阵不能通过行的互换和相应列的互不能通过行的互换和相应列的互换成为形式换成为形式(2)若若n阶方阵阶方阵满足满足其中其中为方阵，则称为方阵，则称A为为不可约不可约.第二十页，本课件共有43页21解线性方程组的迭代法解线性方程组的迭代法如例如例的系数矩阵矩阵的系数矩阵矩阵是可约的是可约的.为为n阶方阵阶方阵若存在非空集若存在非空集使得当使得当而而显然显然,若若A是可约的是可约的,则则A所对应的线性方程组所对应的线性方程组可化为低阶方程组可化为低阶方程组.时有时有则则A是可约阵是可约阵.是不可约的是不可约的.而而一般地，设一般地，设第二十一页，本课件共有43页22解线性方程组的迭代

11、法解线性方程组的迭代法几个常用的收敛条件几个常用的收敛条件.设有线性方程组设有线性方程组下列结论成立下列结论成立：1.若若A为严格对角占优阵或不可约弱对角占优阵为严格对角占优阵或不可约弱对角占优阵,则则Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.2.若若A为严格对角占优阵为严格对角占优阵,则松弛法收敛则松弛法收敛.3.若若A为对称正定阵为对称正定阵,则松弛法收敛则松弛法收敛.因此有因此有:若若A为对称正定阵为对称正定阵,则松弛法收敛的则松弛法收敛的充分必要充分必要条件条件是是4.若若A为对称正定阵为对称正定阵,则则Gauss-Seidel迭代法收敛迭代法收敛.

12、第二十二页，本课件共有43页23解线性方程组的迭代法解线性方程组的迭代法例例:考虑考虑A为严格对角占优阵，故为严格对角占优阵，故Jacobi迭代法与迭代法与Gauss-Seidel迭代均收敛迭代均收敛.又如例中，系数矩阵又如例中，系数矩阵非严格对角占优非严格对角占优,但但A为对称正定矩阵为对称正定矩阵,故松弛法收敛。故松弛法收敛。上述结论的证明可参看上述结论的证明可参看 1,7.其中其中第二十三页，本课件共有43页例例 对线性方程组对线性方程组讨论讨论Jacobi迭代法及迭代法及Gauss-Seidel迭代法的收敛性迭代法的收敛性.解解:Jacobi迭代的迭代矩阵为迭代的迭代矩阵为故故Jaco

13、bi迭代法收敛迭代法收敛.第二十四页，本课件共有43页Gauss-Seidel迭代矩阵迭代矩阵故故Gauss-Seidel迭代法收敛迭代法收敛.第二十五页，本课件共有43页26解线性方程组的迭代法解线性方程组的迭代法讨论用三种迭代法求解的收敛性。讨论用三种迭代法求解的收敛性。解解:例例4 4 设有方程组设有方程组其中其中第二十六页，本课件共有43页27解线性方程组的迭代法解线性方程组的迭代法故不能用条件故不能用条件1 1判别判别Jacobi迭代的收敛性迭代的收敛性.因因A为对称矩阵为对称矩阵,且其各阶主子式皆大于零且其各阶主子式皆大于零,故故A为为对称正定矩阵对称正定矩阵,由判别条件由判别条件

14、3,Gauss-Seidel迭代法与迭代法与松弛法松弛法均收敛均收敛.A不是弱对角占优不是弱对角占优,Jacobi迭代法的迭代矩阵为迭代法的迭代矩阵为故推论故推论1 1不能用不能用第二十七页，本课件共有43页28解线性方程组的迭代法解线性方程组的迭代法其特征方程其特征方程第二十八页，本课件共有43页29解线性方程组的迭代法解线性方程组的迭代法值得指出的是，改变方程组中方程的次序，即将系值得指出的是，改变方程组中方程的次序，即将系系数矩阵作行交换，会改变迭代法的收敛性。例如系数矩阵作行交换，会改变迭代法的收敛性。例如 方程组方程组的系数矩阵为的系数矩阵为有根有根因而因而由定理由定理3.63.6J

15、acobi迭代法不收敛迭代法不收敛.第二十九页，本课件共有43页30解线性方程组的迭代法解线性方程组的迭代法Jacobi迭代与迭代与Gauss-Seidel迭代的迭代矩阵分别为迭代的迭代矩阵分别为它们的谱半径为它们的谱半径为由定理由定理3.63.6这两种迭代均不收敛这两种迭代均不收敛.但若交换两个方程的次序但若交换两个方程的次序得原方程组的同解方程组得原方程组的同解方程组其中其中第三十页，本课件共有43页31解线性方程组的迭代法解线性方程组的迭代法显然显然,是严格对角占优阵是严格对角占优阵,因而对方程组因而对方程组用用Jacobi迭代与迭代与Gauss-Seidel迭代迭代求解均收敛求解均收敛

16、.第三十一页，本课件共有43页32解线性方程组的迭代法解线性方程组的迭代法3.5.33.5.3误差估计误差估计定理定理3.73.7设有迭代格式设有迭代格式若若收敛于收敛于则有误差估计式则有误差估计式证明证明:因为因为故故于是于是存在存在,方程组方程组(即即有惟一解有惟一解)且且从而有从而有p35第三十二页，本课件共有43页33解线性方程组的迭代法解线性方程组的迭代法取范数得取范数得第三十三页，本课件共有43页34解线性方程组的迭代法解线性方程组的迭代法又因为又因为于是于是取范数得取范数得移项得移项得又又第三十四页，本课件共有43页35解线性方程组的迭代法解线性方程组的迭代法将将(3-28)代入

17、代入(3-27)得得有了误差估计有了误差估计(3-26),根据事先给定的精度根据事先给定的精度可以估算出迭代的次数可以估算出迭代的次数kp32第三十五页，本课件共有43页36解线性方程组的迭代法解线性方程组的迭代法例如对迭代格式例如对迭代格式其中其中取取有有代入式代入式(3-29)(3-29)得得第三十六页，本课件共有43页37解线性方程组的迭代法解线性方程组的迭代法所以需要迭代所以需要迭代1313次才能保证各分量误差绝对值次才能保证各分量误差绝对值不超过不超过实际计算时实际计算时,常常采用事后估计误差的方法常常采用事后估计误差的方法,即利用相邻两次迭代值之差是否达到精度作为停即利用相邻两次迭

18、代值之差是否达到精度作为停机准则机准则.因而下面的结论比定理因而下面的结论比定理3.7 3.7 更实用更实用.第三十七页，本课件共有43页38解线性方程组的迭代法解线性方程组的迭代法定理定理3.83.8在定理在定理3.73.7的条件下的条件下,有有证明证明:因为因为所以所以第三十八页，本课件共有43页39解线性方程组的迭代法解线性方程组的迭代法由定理由定理3.8,3.8,为使为使只要只要即可即可.实际计算时实际计算时,当当不太接近不太接近1 1时时,可用可用作为停机准则作为停机准则,即为满足精度即为满足精度之近似解之近似解.第三十九页，本课件共有43页拉格朗日拉格朗日(Lagrange)插值插

19、值牛顿牛顿(Newton)插值插值分段线性插值分段线性插值第第5 5章章 插值法插值法 样条插值样条插值埃尔米特埃尔米特(Hermite)插值插值快速傅里叶变换快速傅里叶变换(FFT)应用实例应用实例1第四十页，本课件共有43页生产实践中常常出现这样的问题：生产实践中常常出现这样的问题：给出一批离散样点给出一批离散样点,要求作出一条通过这些点的光滑曲线，以便满足设计要求或进要求作出一条通过这些点的光滑曲线，以便满足设计要求或进行加工行加工.反映在数学上，既已知函数在一些点上得反映在数学上，既已知函数在一些点上得值，寻求它的分析表达式值，寻求它的分析表达式.因为由函数的表格形式不能因为由函数的表

20、格形式不能直接得出表中未列点处的函数值，也不便于研究函数的直接得出表中未列点处的函数值，也不便于研究函数的的性质的性质.此外，有些函数虽然有表达式，但因式子复杂，此外，有些函数虽然有表达式，但因式子复杂，不易计算其值和进行理论分析，也需要构造一个简单不易计算其值和进行理论分析，也需要构造一个简单函数来近似它函数来近似它.解决这种问题的方法有两种解决这种问题的方法有两种：插值法插值法2第四十一页，本课件共有43页一类是给出函数一类是给出函数的一些点值，选定一个便于计算的一些点值，选定一个便于计算的函数形式，如多项式，分式线性函数和三角多项式的函数形式，如多项式，分式线性函数和三角多项式等，要求它

21、通过已知样点，由此确定函数等，要求它通过已知样点，由此确定函数作为作为的近似的近似.这就是这就是插值法插值法。另一类方法在选定近似函数另一类方法在选定近似函数形式后形式后,不要求近似不要求近似函数过已知样点函数过已知样点,只要求在某种意义只要求在某种意义下它在这些点上的下它在这些点上的总偏差最小总偏差最小.拟合法拟合法.本章主要讨论构造插值多项式的几种常用方法及本章主要讨论构造插值多项式的几种常用方法及其误差其误差.这类方法称为这类方法称为曲线曲线(数据数据)插值法插值法3第四十二页，本课件共有43页设函数设函数在区间在区间上有定义上有定义,它在该区间上它在该区间上n+1个互异点个互异点处的函数值为已知处的函数值为已知,记为记为若存在一个简单函数若存在一个简单函数使得使得成立成立,就称就称为为的的插值函数插值函数,点点称为称为插值节点插值节点,区间区间称为称为插值区间插值区间,求插值函数求插值函数的方法称为的方法称为插值法插值法.4第四十三页，本课件共有43页