非线性方程(组)的迭代解法.ppt

《非线性方程(组)的迭代解法.ppt》由会员分享，可在线阅读，更多相关《非线性方程(组)的迭代解法.ppt（46页珍藏版）》请在三一办公上搜索。

1、2023/9/29,1,第二章 非线性方程(组)求根方法,若 n=1,称为非线性方程求根问题；n1，称为非线性方程组求解问题。,理论问题：（1）解的存在性。即有解还是无解，有多少解。（2）解的性态。即孤立解的区域，解的重数，光滑性。,关于解的存在性及其性态，不是数值分析所讨论的问题。我们总认为：,我们的任务是用数值方法求满足一定精度要求的近似解！,通常求其精确解是困难的,2023/9/29,2,二分法,内容:,一般迭代法,牛顿迭代法,迭代法的加速,非线性方程组的牛顿迭代法*,2023/9/29,3,1、二分法,设 在区间 上连续且有，则 在区间 内有解，不妨设解唯一！,算法构造原理:,有根区间

2、,2023/9/29,4,x1,a,x2,b,什么时候停止？,或,x*,算法停止的条件,x,2023/9/29,5,综合上述，得到如下算法，,(1),(2),(3),否则,(4),否则，转(2)；,例1,可得,共计算21次！,注：,其中 为精度控制参数!,2023/9/29,6,二分法只能求有根区间中的奇数重的实根;,关于二分法的讨论,(1),二分法线性收敛;,(2),二分法可用来细化有根区间，这是它的一大优点!,(3),故二分法可以用来确定迭代法的迭代初值!,返回主目录,2023/9/29,7,2、一般迭代法,(1),(2),(3),(一)构造方法,(1),2023/9/29,8,例2,20

3、23/9/29,9,1.5000-0.8750 6.7324-69.72001.0275e+8不收敛,1.5000 1.2870 1.4025 1.3455 1.3752 1.3601 1.3678 1.3639 1.3659 1.3649 1.3654 1.3651 1.3653 1.3652 1.3652,1.5000 0.8165 2.9969 0-2.9412i不收敛,1.5000 1.3484 1.3674 1.3650 1.3653 1.3652 1.3652,方法1,方法2,方法3,方法4,*收敛与否，以及收敛快慢，取决于迭代函数,15次,6次,*精度控制的表达式？,2023/9

4、/29,10,(二)大范围收敛定理,(1),(2),则,(1),(2),(3),下面看证明过程，,即 是自映射；,2023/9/29,11,(1),由条件(1)可得解的存在性；,由条件(2)可证解的唯一性！,(2),由条件(1)可知,(3),得证；,进而可证!,2023/9/29,12,(三)局部收敛定理,若,由迭代(1)产生的序列,证明:略!,注：,当定理条件成立时，,只要x0充分接近x*，就能保证迭代序列xn收敛于x*！,且有与前一定理完全相同的不等式成立！,2023/9/29,13,分析例2四种迭代格式的收敛性，,一般迭代法只有理论上的意义，因为构造保证收敛的迭代函数比较困难。,注:,方

5、法1的收敛性分析,方法2的收敛性分析,方法3的收敛性分析,方法4的收敛性分析,四种迭代格式的计算结果见本课件P9!,取定初值x0=1.5，=1e-4,2023/9/29,14,（四）收敛阶（速度）的讨论,定义:,p=1 线性收敛；,p=2 平方收敛；,2p1 超线性收敛；,注：,1、p=1时，c1;2、满足局部收敛定理的简单迭代算法至少具有一阶收敛速度。,2023/9/29,15,定理（简单迭代算法m阶收敛的充分条件）,设,在包含x*某个开区间内连续，,若,使得,则,注:1、给出了由迭代函数判断收敛速度的方法；2、给出了提高收敛速度的方法!,由迭代 产生的序列 xn 以m阶收敛速度收敛到x*。

6、,证明：由泰勒公式和收敛阶定义可证！,2023/9/29,16,例3,解：,迭代函数为,2023/9/29,17,迭代函数为,解：,#,返回主目录,2023/9/29,18,3、简单迭代法加速,如何对其加速?,由微分中值定理得,事实上，设迭代算法 产生的序列，,其中 介于 和 之间。,2023/9/29,19,(一)埃特金(Aitken)加速方法,令,作为 的校正值！,2023/9/29,20,(二)steffensen加速算法,设迭代算法，,对其应用Aitken加速方法，得到如下Steffensen算法:,若 在 附近变化不大，,2023/9/29,21,Steffensen算法的收敛性,注

7、:,（1）可以用Steffensen算法对收敛缓慢的简单迭代算法加速！,可以证明：,（2）对于至少平方收敛的算法，用Steffensen算法进行加速，意义不大！,返回主目录,2023/9/29,22,4、牛顿迭代算法,将f(x)在初值x0处做Taylor展开,取其线性部分做为f(x)的近似，有：,若,则有,记为,同理，我们可以得到,2023/9/29,23,这样一直下去，我们可以得到迭代序列,Newton迭代的迭代函数,(2),牛顿迭代算法(切线法),其它构造方法,(1)待定函数法:,(2)数值积分法:,2023/9/29,24,收敛定理（单根的情形）,2023/9/29,25,证明：,由已知

8、可得，,所以至少平方收敛！,#,利用收敛阶的定义来证明！,注：也可以由收敛阶的判定定理来证！,2023/9/29,26,应用举例,（1）,对于给定的正数C，应用牛顿法解二次方程 x2-C=0。,可得,证明上述迭代算法 收敛，并求收敛阶！,1）当x00时，收敛于；2）当x00时，收敛于；,（*）,1)得证!,2）,事实上，对（*）式进行配方可得,下面证明1），,2023/9/29,27,（2）,对于给定的正数C，应用牛顿法求解方程。,可得,可以证明上述迭代算法对任意初值 都收敛于！,事实上，,从而,#,2023/9/29,28,牛顿迭代法的几点说明,牛顿迭代法算法简单，且局部收敛，但初值x0的选

9、择困难！,(1),(2),牛顿迭代每步都要计算导数，增加了计算量！,(3),定理表明牛顿迭代求单根有效且平方收敛（能求重根吗？）。,(一),一般来说采用试探法，可以结合二分法或通过做出函数图形来帮助选择初值！,关于初值,(二),导数的计算,(1),利用牛顿迭代法先计算几步，比如计算到了第k步，得到近似值xk，接下来用 来代替导数，该算法通常是线性收敛的！,2023/9/29,29,(2),一个实用的方法是用差分代替微分，即,此迭代法称为割线法！它是超线性收敛的！,(三),关于重根的问题,2023/9/29,30,可见，当x*为重根时，牛顿迭代线性收敛，且随着m的增加，收敛性变差！,计算重根的改

10、进算法,(1),至少平方收敛。(证明略!),设重数m已知，应用牛顿迭代法得,2023/9/29,31,返回主目录,(2),重数不知道时，一个实用的方法是，令,则,直接对 应用牛顿迭代法求解:,至少平方收敛！,2023/9/29,32,解非线性方程组的牛顿迭代法,2023/9/29,33,Jacobi矩阵,2023/9/29,34,注意事项：,为了解决上述问题，提出拟牛顿法。,2023/9/29,35,2023/9/29,36,2023/9/29,37,Broyden秩1方法,2023/9/29,38,2023/9/29,39,综合上述，得到Broyden秩1方法：,2023/9/29,40,2023/9/29,41,返回主目录,2023/9/29,42,1、数值分析.颜庆津.修订版.北京航空航天大学出版社，20002、李庆扬.非线性方程组的数值解法.科学出版社,1987,参考书目：,2023/9/29,43,例2,返回,不满足局部收敛性定理!故可能发散。,可以验证，,2023/9/29,44,例2,返回,在1,1.5内是自映射，并且,满足大范围收敛定理！收敛。,可以验证，,2023/9/29,45,例2,返回,因此方法3不满足局部收敛性定理！可能发散。,可以验证，,2023/9/29,46,例2,返回,即满足大范围收敛性定理！收敛。,可以验证，,