计算方法第六章迭代法

计算方法第六章迭代法第1页，共53页，2023年，2月20日，星期二第一节非线性方程求根（）1、二分法利用连续函数的性质进行对分。计算框图为：第2页，共53页，2023年，2月20日，星期二压缩映射：集合A上的映射，A上两个点之间的距离记为，如映射满足下面条件，称为压缩映射例：设函数满足：，则该函数为压缩映射定理：如果

为闭集合A上的压缩映射，则方程x=(x)

在集合A

上有唯一解。且解可以用下面迭代得到：第3页，共53页，2023年，2月20日，星期二2、简单迭代：对于形如的方程，可以通过迭代求解。定理：满足下面条件时，为压缩映射：（1）当时，（2）存在正数L<1，使得则方程在区间上有唯一解，且解可以用下面迭代得到第4页，共53页，2023年，2月20日，星期二第5页，共53页，2023年，2月20日，星期二第6页，共53页，2023年，2月20日，星期二例：在区间[1，）上求解方程可用迭代法求解，迭代序列第7页，共53页，2023年，2月20日，星期二误差估计：第k步迭代计算值与精确值误差为使用迭代法求解方程值得注意的事项：1、将要求解的方程化成的形式。2、该迭代法第一个条件不易验证。因此，实际使用时，总在根的附近区间内进行迭代计算，以保证每次迭代的值都在迭代区间内。3、L很小时迭代收敛非常快，但如果L与1很接近，则收敛相当慢。第8页，共53页，2023年，2月20日，星期二收敛阶：定义：设，如果存在实数p和非零常数c，使：则称序列p阶收敛，特别，p＝1时，称为线性收敛，p>1时，称为超线性收敛，p＝2时称为平方收敛。p越大，序列收敛越快。如果是线性收敛，则0<c<1第9页，共53页，2023年，2月20日，星期二加速收敛技术：1、松弛法选择适当的常数（松弛因子），令第10页，共53页，2023年，2月20日，星期二例子：求方程的根迭代格式：取＝1.15，第11页，共53页，2023年，2月20日，星期二计算结果要求准确到小数后8位数字2.1544347393126992.1036120826483502.0959274643276272.0947605999163422.0945833046495202.0945563634929972.0945522695502622.0945516474387052.0945515529032052.0945515385376762.0945515363547042.1025999584485222.0947499378817042.0945564465017492.0945516575136532.0945515389722662.094551536038016第12页，共53页，2023年，2月20日，星期二x=2.510y=x

x=(2*y+5)**(1.0/3.0)

if(abs(x-y).lt.0.00000001)then

goto15 endif goto1015x=2.520y=x

x=(2*y+5)**(1.0/3.0) x=1.15*x+(1.0-1.15)*y

if(abs(x-y).lt.0.00000001)then

goto30 endif goto2030end第13页，共53页，2023年，2月20日，星期二Aitken加速法（适用于线性收敛情况）第14页，共53页，2023年，2月20日，星期二3、插值加速法第15页，共53页，2023年，2月20日，星期二由线性插值公式：第16页，共53页，2023年，2月20日，星期二斯特芬森迭代（迭代两次后用Aitken加速）：迭代一次用插值加速，称为插值加速迭代：第17页，共53页，2023年，2月20日，星期二3.对于一般的函数方程f(x)=0

的求解，解决方案为：构造等价的方程x=(x)

，利用迭代法求解。这称为牛顿迭代，迭代序列收敛条件为：这在函数方程f(x)=0根a

的某邻域内显然成立。第18页，共53页，2023年，2月20日，星期二牛顿迭代法的几何意义：第19页，共53页，2023年，2月20日，星期二一个例子：第20页，共53页，2023年，2月20日，星期二牛顿迭代法是局部收敛。因此，只有初值选得靠近精确解时，才能保证迭代序列收敛。定理：设函数f(x)在区间[a,b]上二阶导数存在，且：则牛顿迭代序列收敛于f(x)＝0在区间[a,b]上的唯一根。第21页，共53页，2023年，2月20日，星期二利用泰勒展开容易证明，牛顿迭代法具有二阶收敛性，即平方收敛。收敛速度快这是牛顿迭代法的主要优点。计算步骤（框图）：例子：建立求某个正实数c

的平方根的迭代格式。第22页，共53页，2023年，2月20日，星期二设函数方程f(x)=0

的根为，将f()泰勒展开第23页，共53页，2023年，2月20日，星期二改进牛顿迭代或柯西迭代第24页，共53页，2023年，2月20日，星期二设函数y=f(x)的反函数为x=(y)，f(x)=0

的根为第25页，共53页，2023年，2月20日，星期二牛顿迭代法的收敛性：牛顿迭代法二阶收敛，两种改进牛顿迭代法三阶收敛第26页，共53页，2023年，2月20日，星期二简化牛顿法：目的：避免计算迭代格式中的导数方法：将牛顿迭代中导数取为某个定点的值，如，按如下格式迭代几何意义如图第27页，共53页，2023年，2月20日，星期二进一步，取任意常数c

代替迭代公式中的导数值，迭代公式为迭代函数为，为使迭代序列收敛，c

应满足这称为简化牛顿法，显然，当c

与导数同号且满足上面式子时，迭代收敛。第28页，共53页，2023年，2月20日，星期二本例中，c

与导数异号，迭代发散第29页，共53页，2023年，2月20日，星期二弦割法：用过两个点的直线的斜率代替函数在点处函数的导数，进行迭代。迭代公式：同样，此法具有局部收敛性。其收敛是超线性收敛，收敛阶为1.618第30页，共53页，2023年，2月20日，星期二单点弦割法：用固定点代替可以证明，单点法也是局部收敛的，且收敛阶为线性收敛，即1阶收敛。第31页，共53页，2023年，2月20日，星期二牛顿下山法：目的是解决初值的选取范围太小这以困难。构造迭代格式为：其中的参数满足：这个方法称为牛顿下山法。其中的参数称为下山因子，通常取，然后逐步减半。牛顿下山法当时，只有线性收敛速度，但对初值的选取却放的相当宽。第32页，共53页，2023年，2月20日，星期二第二节线性代数方程组迭代解法求解代数方程组方法：将方程组改造为一个等价的方程组构造迭代格式：设为事先给定的误差精度，则可以得到迭代次数：定理：对于上面的迭代格式，如果B的范数小于1，则对于任意的初始向量与常向量g，迭代格式收敛，迭代误差估计：第33页，共53页，2023年，2月20日，星期二2.1雅可比迭代与高斯－赛德尔迭代考虑n阶方程组，设系数阵非奇异，且对角元非零将方程组变形为：第34页，共53页，2023年，2月20日，星期二任意取一组初值，可以建立迭代格式：显然，如上面的迭代收敛，则收敛向量必然为方程组的唯一解。这个迭代法称为雅可比迭代。雅可比迭代也称为同时（或整体）代换第35页，共53页，2023年，2月20日，星期二显然，如果雅可比迭代法收敛，则将迭代格式中每一步迭代得到的迭代向量分量带入下一步迭代，则迭代效果应该更好，这种迭代称为高斯－赛德尔迭代，（逐个代换法）雅可比迭代与高斯－赛德尔迭代都称为简单迭代。第36页，共53页，2023年，2月20日，星期二逐个超松弛（SOR）迭代：第37页，共53页，2023年，2月20日，星期二基本迭代的收敛第38页，共53页，2023年，2月20日，星期二雅可比迭代的矩阵形式：高斯——赛德尔迭代的矩阵形式：超松弛（SOR）迭代矩阵形式：第39页，共53页，2023年，2月20日，星期二代数方程组简单迭代法收敛的条件定义：矩阵A的特征值中模最大者，称为矩阵的谱半径，矩阵A的谱半径记为(A)定理：简单迭代收敛的充分必要条件是或矩阵B

的谱半径(B)<1第40页，共53页，2023年，2月20日，星期二推论1：如果迭代矩阵的范数小于1，则简单迭代收敛。推论2：逐次超松弛迭代法收敛的一个条件是0<<2推论3：A严格对角占优时，雅可比迭代、0<1的SOR法都收敛。推论4：A对称正定时，雅可比迭代法收敛的充要条件是2D－A对称正定，SOR收敛的充要条件是0<<21、A严格对角占优，则雅可比、高斯－赛德尔迭代都收敛。2、如A

对称正定，则高斯－赛德尔迭代收敛。3、如果A

对称正定，D为A

的对角线上的元组成的矩阵，如2D－A也对称正定，则雅可比迭代收敛；如A对称正定而2D－A非正定，则雅可比迭代不收敛。第41页，共53页，2023年，2月20日，星期二第三节非线性方程组的迭代解法3.1一般迭代。设有非线性方程组

第42页，共53页，2023年，2月20日，星期二将方程组改写为下式，可得Jacobi型迭代格式第43页，共53页，2023年，2月20日，星期二记，称为关于x的Frechet导数。定理：若满足：1、存在凸闭区域，使得2、存在正常数，使得，则在在惟一的不动点x*，并且迭代序列收敛于x*，而且有上述关于方程式迭代一样的误差估计。注：上述矩阵的范数可取1范数、2范数、无穷范数等。存第44页，共53页，2023年，2月20日，星期二例子：第45页，共53页，2023年，2月20日，星期二2.249999996274710E-0010.000000000000000E+0002.186919316403400E-0015.466796866210643E-0022.325557956363573E-0015.317841537994177E-0022.317490821626177E-0015.644888021896249E-0022.325921363078080E-0015.625890688180394E-0022.325180586318136E-0015.645743714344483E-0022.325700280145271E-0015.643999442076879E-0022.325640279518354E-0015.645223144329810E-0022.325672764847015E-0015.645081864117191E-0022.325668208064959E-0015.645158355581563E-0022.325670264099253E-0015.645147625974770E-0022.325669930999687E-0015.645152467207023E-0022.325670062538411E-0015.645151682875589E-0022.325670038780621E-0015.645151992602669E-002第46页，共53页，2023年，2月20日，星期二

x=0.0 y=0.010x1=xy1=y

x=0.25*(1+y1-0.1*exp(x1)) y=0.25*(x1-0.125*x1*x1)write(10,*)x,y

if((abs(x-x1)+abs(y-y1)).lt.0.00000001)then

goto15 endif

goto1015end第47页，共53页，2023年，2月20日，星期二类似的可以得到高斯－赛德尔型迭代：第48页，共53页，2023年，2月20日，星期二2.249999996274710E-0015.466796866210643E-0022.323589238058666E-0015.640252253045976E-0022.325613187635559E-0015.645018072260635E-0022.325668492678739E-