资源描述
Numerical Analysis,J.G.Liu,School of Math.&Phys.,North China Elec.P.U.,*,*,第二章,非线性方程(组)求根方法,若,n=,1,称为,非线性方程求根,问题；,n,1，称为非线性方程组求解问题。,理论问题：,（1）解的,存在性,。即有解还是无解，有多少解。,（2）解的,性态,。即孤立解的区域，解的重数，光滑性。,关于解的存在性及其性态，不是数值分析所讨论的问题。我们总认为：,我们的任务是用数值方法求满足一定精度要求的近似解！,通常求其精确解是困难的,11/17/2024,1,第二章 非线性方程(组)求根方法 若 n=1,称为非线性,二分法,内容:,一般迭代法,牛顿迭代法,迭代法的加速,非线性方程组的牛顿迭代法,*,11/17/2024,2,二分法内容:一般迭代法 牛顿迭代法 迭代法的加速,1、,二分法,设 在区间 上连续且有 ，则 在区间 内有解，,不妨设解唯一,！,算法构造原理:,有根区间,11/17/2024,3,1、二分法设 在区间 上连,x,1,a,a,b,x,2,b,什么时候停止？,或,x*,算法停止的条件,x,11/17/2024,4,x1aabx2b什么时候停止？或x*算法停止的条件x10/8,综合上述，得到如下算法，,(1),(2),(3),否则,(4),否则,，转(2)；,例1,可得,共计算21次！,注：,其中 为精度控制参数!,11/17/2024,5,综合上述，得到如下算法，(1)(2)(3)否则(4)否则，转,二分法只能求有根区间中的奇数重的实根;,关于二分法的讨论,(1),二分法线性收敛;,(2),二分法可用来细化有根区间，这是它的一大优点!,(3),故二分法可以用来确定迭代法的,迭代初值,!,返回主目录,11/17/2024,6,二分法只能求有根区间中的奇数重的实根;关于二,2、一般迭代法,(1),(2),(3),(一),构造方法,(1),11/17/2024,7,2、一般迭代法(1)(2)(3)(一)构造方法(1)10/,例2,11/17/2024,8,例210/8/20238,1.5000,-0.8750,6.7324,-69.7200,1.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次,*精度控制的表达式？,11/17/2024,9,1.5000 1.5000 1.5000,(二),大范围收敛定理,(1),(2),则,(1),(2),(3),下面看证明过程，,即 是自映射,；,11/17/2024,10,(二)大范围收敛定理(1)(2)则(1)(2)(3),(1),由条件(1)可得解的存在性；,由条件(2)可证解的唯一性！,(2),由条件(1)可知,(3),得证；,进而可证,!,11/17/2024,11,(1)由条件(1)可得解的存在性；由条件(2)可证解的唯一性,(三),局部收敛定理,设,在包含,x,*,某个开区间内连续，,若,由迭代(1)产生的序列 ,使得,则,证明:略!,注：,当定理条件成立时，,只要,x,0,充分,接近,x,*,，就能保证迭代序列,x,n,收敛于,x,*,！,且有与前一定理完全相同的不等式成立！,11/17/2024,12,(三)局部收敛定理设在包含x*某个开区间内连续，若由迭代(,分析例,2,四种迭代格式的收敛性，,一般迭代法只有理论上的意义，因为构造,保证收敛,的迭代函数比较困难。,注:,方法1的收敛性分析,方法2的收敛性分析,方法3的收敛性分析,方法4的收敛性分析,四种迭代格式的计算结果见本课件P9!,取定初值,x,0,=1.5,，,=1e-4,11/17/2024,13,分析例2四种迭代格式的收敛性，一般迭代法只有理论上的意义，因,（四）收敛阶（速度）的讨论,定义:,p,=1 线性收敛；,p,=2 平方收敛；,2,p,1 超线性收敛；,注：,1、,p,=1时，c0,时，收敛于 ；2）当,x,0,0,时，收敛于 ；,（,*,）,1)得证!,2）,事实上,，对（,*,）式进行配方可得,下面证明1），,11/17/2024,26,应用举例（1）对于给定的正数C，应用牛顿法解二次方程 x2-,（2）,对于给定的正数,C,，应用牛顿法求解方程,。,可得,可以证明上述迭代算法对任意初值 都收敛于 ！,事实上,，,从而,#,11/17/2024,27,（2）对于给定的正数C，应用牛顿法求解方程,牛顿迭代法的几点说明,牛顿迭代法算法简单，且局部收敛，但初值,x,0,的选择困难！,(1),(2),牛顿迭代每步都要计算导数 ，增加了计算量！,(3),定理表明牛顿迭代求单根有效且平方收敛（,能求重根吗？,）。,(一),一般来说采用试探法，可以结合,二分法,或通过做出,函数图形,来帮助选择初值！,关于初值,(二),导数的计算,(1),利用牛顿迭代法先计算几步，比如计算到了第,k,步，得到近似值,x,k,，接下来用 来代替导数，该算法通常是,线性收敛,的！,11/17/2024,28,牛顿迭代法的几点说明牛顿迭代法算法简单，且局部收敛，但初值x,(2),一个实用的方法是用差分代替微分，即,此迭代法称为,割线法,！它是,超线性收敛,的！,(三),关于重根的问题,11/17/2024,29,(2)一个实用的方法是用差分代替微分，即此迭代法称为割线法！,可见，当,x*,为重根时，牛顿迭代线性收敛，且随着,m,的增加，收敛性变差！,计算重根的改进算法,(1),至少平方收敛。(证明略!),设重数,m,已知，应用牛顿迭代法得,11/17/2024,30,可见，当x*为重根时，牛顿迭代线性收敛，且随着m的增加，收敛,返回主目录,(2),重数不知道时，一个实用的方法是，令,则,直接对 应用牛顿迭代法求解:,至少平方收敛！,(3),通过史蒂芬森（,Steffensen,）迭代算法进行加速！,11/17/2024,31,返回主目录(2)重数不知道时，一个实用的方法是，令则直接对,解非线性方程组的牛顿迭代法,11/17/2024,32,解非线性方程组的牛顿迭代法10/8/202332,Jacobi矩阵,11/17/2024,33,Jacobi矩阵10/8/202333,注意事项：,为了解决上述问题，提出拟牛顿法。,11/17/2024,34,注意事项：为了解决上述问题，提出拟牛顿法。10/8/2,11/17/2024,35,10/8/202335,11/17/2024,36,10/8/202336,Broyden秩1方法,11/17/2024,37,Broyden秩1方法10/8/202337,11/17/2024,38,10/8/202338,综合上述，得到Broyden秩1方法：,11/17/2024,39,综合上述，得到Broyden秩1方法：10/8/202339,11/17/2024,40,10/8/202340,返回主目录,11/17/2024,41,返回主目录10/8/202341,例2,返回,不满足局部收敛性定理!故可能发散。,可以验证，,11/17/2024,42,例2返回不满足局部收敛性定理!故可能发散。可以验证，10,例2,返回,在1,1.5内是自映射，并且,满足大范围收敛定理！收敛。,可以验证,，,11/17/2024,43,例2返回 在1,1.5内是自映射,例2,返回,因此方法3不满足局部收敛性定理！可能发散。,可以验证，,11/17/2024,44,例2返回因此方法3不满足局部收敛性定理！可能发散。可以验证，,例2,返回,即满足大范围收敛性定理！收敛。,可以验证,，,11/17/2024,45,例2返回即满足大范围收敛性定理！收敛。可以验证，10/8/2,
展开阅读全文