《非线性方程组解法课件》由会员分享,可在线阅读,更多相关《非线性方程组解法课件(78页珍藏版)》请在金锄头文库上搜索。
1、非线性方程非线性方程 (组组) 解法解法的内容的内容非线性方程的解法非线性方程的解法非线性方程非线性方程组组的解法的解法 1. 牛顿法及牛顿型迭代法(拟牛顿法等牛顿法及牛顿型迭代法(拟牛顿法等) );搜索法;搜索法;牛顿迭代法;牛顿迭代法; 弦截法;弦截法;多项式方程求根多项式方程求根最速下降法;最速下降法;2. 简单迭代法与牛顿迭代法的收敛性简单迭代法与牛顿迭代法的收敛性2.牛顿法、割线法、延拓法等的收敛性牛顿法、割线法、延拓法等的收敛性二分法;二分法; 简单迭代法;简单迭代法;(牛顿法、劈因子法)(牛顿法、劈因子法)1. 非线性最小二乘问题的计算方法非线性最小二乘问题的计算方法非线性方程组
2、解法PPT课件1 基础知识基础知识1.1 非线性方程非线性方程(组组)及解的概念及解的概念2.常见的非线性方程常见的非线性方程高次方程高次方程, ,即多项式即多项式方程方程超越方程超越方程 例例1. 产生的背景产生的背景:科学理论与工程技术都可化为非线性方程科学理论与工程技术都可化为非线性方程(组组)第七章第七章 非线性方程(组)解法非线性方程(组)解法非线性最小二乘问题;非线性最小二乘问题;非线性积分、微分方程数值解非线性积分、微分方程数值解 3.非线性方程的解:非线性方程的解:f (x)=0的根,或称为函数的根,或称为函数f (x)的零点的零点.注:注:()方程的根可能是实数也可能是复数,
3、相应地称为方程方程的根可能是实数也可能是复数,相应地称为方程的的实根实根或或复根复根。如果函数如果函数f (x)可因式分解为可因式分解为且且 称称x*为为函数函数f (x)的的m重零点重零点,或称为方程,或称为方程f (x)=0的的m重根重根;当当m时,称时,称x*为函数为函数f (x)的的单重零点单重零点,又称作方程,又称作方程f (x)=0的的单根单根 ; 如果如果称称x*为方程为方程f (x)=0的的m重根重根.() 重根亦可利用导数来定义重根亦可利用导数来定义(略略)。若存在数若存在数 x*满足满足 f (x*)=0,则,则x*称为方程称为方程记为:记为: f (x)=0非线性方程组解
4、法PPT课件求解的特点:求解的特点:无求解公式,无直接解法无求解公式,无直接解法,难求得精确解。难求得精确解。举例举例: :超越方程超越方程1.2 非线性方程非线性方程(组组)求解的特点求解的特点 间接法间接法( (迭代法迭代法):):从一个初始近似值出发从一个初始近似值出发, ,重复某种计算过程重复某种计算过程没有一定的解法。没有一定的解法。间接法即迭代法。间接法即迭代法。来来不断改进近似解不断改进近似解,有限次改进后有限次改进后, ,计算出一个满足误差要求计算出一个满足误差要求的的近似解近似解,这种求解方法称为这种求解方法称为迭代法迭代法。求解的方法:求解的方法:迭代法求解的要求:迭代法求
5、解的要求: l 收敛收敛l 计算效率计算效率( (计算量计算量) )l 数值稳定性数值稳定性( (计算机的舍入误差计算机的舍入误差) )初始值好初始值好迭代公式合适迭代公式合适( (好的好的) )非线性方程组解法PPT课件1.3 收敛性和收敛阶收敛性和收敛阶定义定义1 序列的收敛性序列的收敛性 序列的收敛阶序列的收敛阶(1)(1)线性的线性的, ,若若定义定义2(2)(2)超线性的超线性的, ,若若(3) p 阶收敛的阶收敛的, ,若若注注 := =2时为二阶收敛时为二阶收敛, , 也称为也称为平方平方收敛收敛。非线性方程组解法PPT课件2初始近似值的搜索、二分法和插值法初始近似值的搜索、二分
6、法和插值法 2.1逐步搜索法逐步搜索法满足条件,满足条件,2. 解决问题依据解决问题依据 连续函数介值定理连续函数介值定理, ,即若即若f( (x) )满足条件:满足条件:即即 a, ,b 内至少有方程内至少有方程(2.1)的一个根的一个根, ,称称 a, ,b 为为f( (x) )的一个的一个含根区间含根区间。若非线性方程若非线性方程 f( (x)=0 )=0 (2.1) 1. 问题问题3. 逐步搜索法思想方法(基本思想)逐步搜索法思想方法(基本思想)根分布如何?如何确定求根区间?根分布如何?如何确定求根区间? 如何求根?如何求根?把含根区间不断缩短,把含根区间不断缩短,求的近似解。求的近似
7、解。,那么方程是否有根?,那么方程是否有根? 有根有根则则f( (x) )在在 a, ,b 存在某个存在某个x* *且使含根区间之且使含根区间之间间含有一个满足误差要含有一个满足误差要非线性方程组解法PPT课件设连续函数设连续函数f( (x) )的含根区间为的含根区间为 a, ,b ,不妨假定不妨假定 f( (a) ),从从出发出发,按预定步长按预定步长h (譬如取(譬如取 为正整数),一步为正整数),一步每跨一步进行一次根的每跨一步进行一次根的“搜索搜索”,即检查点,即检查点 上的函数值上的函数值 的符号,一旦发现的符号,一旦发现 一步地向右跨,一步地向右跨, 则可确定一个缩小了的含根区间则
8、可确定一个缩小了的含根区间,其长度等于预,其长度等于预 定的步长定的步长h。 特别地,可能有特别地,可能有这时这时xk即为所求的根。即为所求的根。 例例1 方程方程 f( (x)=)=x3- -x-1=0-1=0,利用逐步搜索法确定一个含根区间。利用逐步搜索法确定一个含根区间。 解解 在区间(在区间(0,2)内至少有一个实根。)内至少有一个实根。 设从设从x=0=0出发,取出发,取h=0.5为步长向右进行根的搜索,为步长向右进行根的搜索,列表如下列表如下 x 0 0.5 1.0 1.5 2f (x) - - - - - - + + + + 可以看出在可以看出在 1.0, 1.5内必有内必有唯一
9、唯一根根4. 具体过程(方法)具体过程(方法)非线性方程组解法PPT课件2.2 二分法二分法(对分法或分半法对分法或分半法)(满足条件(满足条件 )2. 解决问题依据解决问题依据 连续函数介值定理连续函数介值定理, ,至少存在某个至少存在某个即即 a, ,b 内至少有方程内至少有方程(2.1)(2.1)的一个根的一个根, ,称称 a, ,b 为为f( (x) ) 的一个的一个含根区间含根区间。3. 思想方法(基本思想思想方法(基本思想)把含根区间不断缩短,使含根区间之把含根区间不断缩短,使含根区间之间间含有一个满足误差含有一个满足误差要求的近似解。要求的近似解。考虑非线性方程考虑非线性方程 f
10、( (x)=0 )=0 (2.1(2.1) ) 并且有并且有 1. 问题问题非线性方程组解法PPT课件(3) 生成含根区间:生成含根区间:4 4 具体过程(方法)具体过程(方法)满足下式满足下式: :生成含根区间生成含根区间非线性方程组解法PPT课件, ,满足:满足:(3) 生成含根区间:生成含根区间:, ,满足(满足(2.22.2)式,)式,即即生成含根区间生成含根区间一般的一般的, ,非线性方程组解法PPT课件近似解序列近似解序列其极限为其极限为即序列即序列收敛于收敛于的一个根的一个根即即且且说明说明只要只要就有就有此时可计算或估计二分法执行的次数此时可计算或估计二分法执行的次数k.事实上
11、事实上, ,由由两边取对数得两边取对数得可取可取对于给定的误差界对于给定的误差界1.1.简单简单,对函数要求低对函数要求低 ( (只要连续只要连续, ,在两个端点异号在两个端点异号) );优点优点2.2.二分法是收敛的二分法是收敛的. .非线性方程组解法PPT课件例例2 用区间二分法求方程用区间二分法求方程 f( (x)=)=x3- -x- -1=0=0在区间在区间1.0, 1.5内的内的解解 一个实根一个实根. 考虑考虑f( (x)=)=x3- -x- -1在区间在区间1.0, 1.5上的导数,上的导数,f ( (x)=)=3x2- -10,0,从而函数从而函数f( (x) )在区间在区间1
12、.0, 1.5上单调连续上单调连续, 所以函数所以函数f( (x) )在区间在区间1.0, 1.5上有唯一根。上有唯一根。 计算过程见表计算过程见表2-1表表 2-101234561.0001.25001.31251.32031.50001.37501.34381.32811.25001.37501.31251.34381.32811.32031.3242则则x6 = =1.3242为方程根的近似值为方程根的近似值.非线性方程组解法PPT课件例例3证明方程证明方程在区间在区间0 , 1内有一个根内有一个根,使用二分使用二分法求误差不大于法求误差不大于 的根的根, 需二分多少次需二分多少次证证所
13、以所以f( (x) )在在0 , 1上单调减少且连续。上单调减少且连续。所以所以f( (x) )在在0 , 1上有且只有一个根上有且只有一个根.使用二分法时,误差限使用二分法时,误差限 所以需二分所以需二分14 次即可次即可.非线性方程组解法PPT课件例例不能求出所有根不能求出所有根,(,(即有可能漏根即有可能漏根) )。例例如图如图该点可求出该点可求出, ,改进的方法:改进的方法:但漏掉了四个点但漏掉了四个点2.2.不能用于求偶重根、复根;不能推广到多元方程组求解不能用于求偶重根、复根;不能推广到多元方程组求解. .缺点缺点 的等比级数的收敛速度的等比级数的收敛速度相同,相同,1.1.收敛速
14、度不快收敛速度不快, ,仅与公比为仅与公比为 即是线性收敛;即是线性收敛;区间搜索法等区间搜索法等. .非线性方程组解法PPT课件 1. .理解理解收敛性、收敛阶的概念;收敛性、收敛阶的概念; 3. .会用会用二分法求二分法求非线性方程的近似解及执行次数非线性方程的近似解及执行次数k . . 2. .理解理解逐步搜索法搜索非线性方程解的思想方法逐步搜索法搜索非线性方程解的思想方法, ,理解理解掌握掌握二二作业作业1. 用搜索法求方程用搜索法求方程 的有根区间的有根区间. 2. 用区间二分法求方程用区间二分法求方程 在在1,2的近似根(二分的近似根(二分3次)次),并求若近似根准确到并求若近似根
15、准确到10-3至少要二分多少次?至少要二分多少次? 3. 用区间二分法求方程用区间二分法求方程在在3,4内的根,精确内的根,精确到到10-3。 分法分法解非线性方程的思想方法;解非线性方程的思想方法;非线性方程组解法PPT课件 复习:复习: 3. 3. 正割法正割法解非线性方程的解非线性方程的思想方法思想方法、迭代公式迭代公式: 2.2. 二分法二分法解解非线性方程的非线性方程的条件条件、思想方法思想方法、执行次数、执行次数k:(1)(1)线性的线性的, ,若若(2)(2)超线性的超线性的, ,若若(3)p(3)p阶收敛的阶收敛的, ,若若1. 序列的序列的收敛阶收敛阶:给定的误差界给定的误差
16、界非线性方程组解法PPT课件2.32.3 抛物线法抛物线法1 1 方法的推导(迭代公式)方法的推导(迭代公式)(二次插值)(二次插值) 设设f(x)=0f(x)=0的根为的根为(即(即为方程为方程f(x)=0f(x)=0的精确解)的精确解)可由数据点可由数据点,构造抛物线,构造抛物线二阶差商二阶差商一阶差商一阶差商牛顿插值牛顿插值次近似次近似次近似,次近似,构造构造用用p(x)p(x)近似近似f(x),f(x),根。根。取取P(x)=0P(x)=0较靠近较靠近的根的根为为f(x)=0的改进近似的改进近似考虑考虑的最小值,的最小值, 变形变形( (a)a)式式( (插项插项),于是于是,非线性方
17、程组解法PPT课件则有则有且有且有由此可得(由此可得(2.10)非线性方程组解法PPT课件2 2 局部收敛定理局部收敛定理只要只要 抛物线法产生的迭代序列抛物线法产生的迭代序列收敛于收敛于且有且有设设f(x)f(x)在在则存在则存在附近附近3 3次连续可导,次连续可导,继续以上过程,这种生成迭代序列的求根算法称为继续以上过程,这种生成迭代序列的求根算法称为抛物线法抛物线法。定理定理2 2可由可由(2.10) 式迭代求更接近式迭代求更接近的近似解的近似解 。非线性方程组解法PPT课件注:注: 1 1 抛物线法可产生实根,也可产生复根。抛物线法可产生实根,也可产生复根。2 2 更高次的插值多项式很
18、少选用更高次的插值多项式很少选用, ,一是高次插值多项式求根困一是高次插值多项式求根困难难, ,二是其收敛速度不会太快,即收敛阶总低于二是其收敛速度不会太快,即收敛阶总低于2 2。2.4* 2.4* 反插值法反插值法设设f(x)=0f(x)=0的根为的根为由数据点由数据点得得的的次插值函数。次插值函数。差商差商取取令令则则该方法称为该方法称为反插值法反插值法。有反函数有反函数且且若若f(x)f(x)在在邻近严格单调邻近严格单调个已知近似值,个已知近似值,构造构造非线性方程组解法PPT课件注:注: 1 1 当当 时,反插值法完全重合于正割法。时,反插值法完全重合于正割法。2 2 反插值法是局部收
19、敛的反插值法是局部收敛的, ,且收敛阶低于且收敛阶低于2 2。思考:思考:总结:总结:上上讨论抛物线法,但平时很少用抛物线法,因为该方法计算量大,讨论抛物线法,但平时很少用抛物线法,因为该方法计算量大,且收敛阶不高。且收敛阶不高。几种插值法的条件不同几种插值法的条件不同。正割法是常用的方法,理论正割法是常用的方法,理论当当 时,反插值法是否是抛物线法时,反插值法是否是抛物线法?非线性方程组解法PPT课件3 解解x=g(x)x=g(x)的简单迭代法的简单迭代法3.1 3.1 简单迭代法公式简单迭代法公式问题问题: : f(x)f(x)实函数实函数. .求求f(x)=0f(x)=0的近似值的近似值
20、。(1)(1)先将先将f(x)=0f(x)=0化为等价方程化为等价方程初始近似初始近似k+1次次近似近似( (迭代公式迭代公式) )若若收敛于收敛于且且连续连续, ,则则是是f(x)=0f(x)=0的根的根。说明说明: : 由由f(x)=0f(x)=0化成等价方程化成等价方程x=g(x)x=g(x)的化法有很多种。的化法有很多种。(1) (1) 如何选取如何选取迭代函数迭代函数g(x)g(x)? (3.2) (3.2)式称为式称为简单迭代法简单迭代法或或单点迭代法单点迭代法或或单步迭代法单步迭代法。 g(x)称称为为迭代函数。迭代函数。基本思想方法:基本思想方法:出发出发, ,作序列作序列(2
21、) 从某从某讨论的问题讨论的问题: :(2) g(x)(2) g(x)满足什么条件,迭代序列收敛?收敛速度是多少?满足什么条件,迭代序列收敛?收敛速度是多少?(3) (3) 如何加速如何加速迭代序列的收敛速度迭代序列的收敛速度?(2)(2)(3)(3)非线性方程组解法PPT课件问题问题: : 由由求求,然而,然而是否是是否是g(x)g(x)定义域上的值定义域上的值? ?定义定义4 4简单迭代法简单迭代法(3.2)(3.2)称为称为适定适定的;的;法法(3.2)称为称为收敛收敛的。的。当迭代当迭代(3.2)(3.2)收敛时收敛时, ,极限点极限点又是又是g(x)g(x)的连续点的连续点, ,则则
22、的解也称的解也称的不动点。的不动点。的不动点。的不动点。称为称为则则也可理解成:也可理解成:是映射,若是映射,若 满足满足。g(x)把定义域的每个把定义域的每个x 映成了映成了g(x),因此因此保持有界保持有界, ,若迭代序列若迭代序列且全在且全在g(x)g(x)定义域内定义域内, ,则则若进一步有若进一步有则简单迭代则简单迭代迭代公式迭代公式注注: : 适定适定是是收敛收敛必要条件,即不必要条件,即不适定适定则一定不则一定不收敛收敛。非线性方程组解法PPT课件说明两点:说明两点:分别就下列四种情况说明几何意义:分别就下列四种情况说明几何意义:(1)(1)中中的产生。的产生。(2 2)何时何时
23、收敛收敛, ,何时发散。何时发散。几何意义几何意义求求x=g(x)x=g(x)的根的根求求的根的根 迭代法收敛迭代法收敛迭代法不收敛迭代法不收敛从点从点的直线交的直线交y=xy=x于点于点出发出发, ,作平行于作平行于x x轴轴作平行于作平行于y y 轴的直线交轴的直线交y =g(x)y =g(x)于点于点过该点过该点即即依次进行下去得到依次进行下去得到且且非线性方程组解法PPT课件1. 1. 简单迭代法简单迭代法(2)(2)给定给定满足满足2. 2. 收敛定理收敛定理定理定理3 3(1)方法步骤方法步骤: :( (压缩不动点定理或压缩映象定理压缩不动点定理或压缩映象定理) )若迭代函数若迭代
24、函数g(x)g(x)满足满足使使有有则则(收敛程度)(收敛程度)(收敛速度)(收敛速度)分析分析: : 结论结论(1)(1)中中有唯一根有唯一根, ,因此想到根的存在性定理因此想到根的存在性定理, ,连续条件。连续条件。(3.4)(3.4)实际是实际是非线性方程组解法PPT课件证明:证明:若等号成立若等号成立, ,则表示则表示a a是根或者是根或者b b是根是根, ,a,ba,b上已有根存在了上已有根存在了, ,对对于于一般情况一般情况,由根的存在定理,由根的存在定理,在在上至少存在一个根上至少存在一个根即即在在a,ba,b上至少存在一个根上至少存在一个根即即定理定理3 3 ( (压缩不动点定
25、理或压缩映象定理压缩不动点定理或压缩映象定理) )若迭代函数若迭代函数g(x)g(x)满足满足使使有有则则从而从而下证唯一性,下证唯一性,为为在在a,ba,b上另一根上另一根, ,则则设设由条件由条件( (1)1)知知适定的,另外适定的,另外非线性方程组解法PPT课件 又又(导数的定义)(导数的定义)证明:证明:注:注:(1)(1)从定理的结论从定理的结论3 3知,知,L L越小收敛越快,越小收敛越快,L L叫做叫做渐进收敛因子渐进收敛因子。非线性方程组解法PPT课件(2)(2)定理定理3 3不是必要条件不是必要条件, ,如如 上不满足定理上不满足定理3 3的条件(的条件(2 2),实际上),
26、实际上是解,是解, 只要只要取在取在0 0附近,把(附近,把(1 1,1 1)缩小使)缩小使可以满足。可以满足。( (3.43.4) )式的条件较难验证,常采用导数来代替。即有推论式的条件较难验证,常采用导数来代替。即有推论1 1 :推论推论1 1 定理定理3 3 中(中(3.43.4)可用下式替代)可用下式替代证明:证明:只证只证因因思考:思考:不成立时结论是否成立不成立时结论是否成立?不一定不一定因此该推论是充分条件但不是必要条件。因此该推论是充分条件但不是必要条件。 若若不成立时不成立时,则则需要判断需要判断(3.4)(3.4)。注:注:非线性方程组解法PPT课件定理定理4 4 (局部收
27、敛定理)(局部收敛定理)有有则则由由产生的序列产生的序列收敛于收敛于且有误差估计:且有误差估计:证明:证明:实际计算中往往只在根实际计算中往往只在根因此有局部收敛定理因此有局部收敛定理4 4:邻近讨论,邻近讨论,说明:说明:定理中的条件是充分但非必要条件。见定理定理中的条件是充分但非必要条件。见定理3 3的注(的注(2 2)。)。非线性方程组解法PPT课件推论推论2 2 若若在不动点在不动点处可微,而且处可微,而且则存在则存在当当时,由时,由产生的序列产生的序列收敛于收敛于且且证明:证明:任取任取由由知存在知存在,成立,成立即即由定理由定理4 4得证。得证。( (3.73.7) )式的条件较难
28、验证式的条件较难验证, ,常采用导数来代替。即有推论常采用导数来代替。即有推论2 2 :非线性方程组解法PPT课件在一定条件下,迭代是高价收敛的。有定理在一定条件下,迭代是高价收敛的。有定理5 5:定理定理5 5(高阶收敛定理)(高阶收敛定理) 若若在不动点在不动点邻近有直至邻近有直至阶的阶的连续导数,且满足连续导数,且满足则简单迭代法:则简单迭代法:是局部收敛的,且收敛阶为是局部收敛的,且收敛阶为分析:分析:已知条件有各阶导数均为已知条件有各阶导数均为0 0, ,因此用泰勒展开公式。因此用泰勒展开公式。证明:证明: 由推论由推论2,简单迭代法是局部收敛的。,简单迭代法是局部收敛的。下证收敛阶
29、为下证收敛阶为非线性方程组解法PPT课件3 3 用简单迭代法求值用简单迭代法求值 (举例):(举例):例例用简单迭代法求用简单迭代法求的近似值。的近似值。解:解: 设设则则所以所以,求求的近似值转化为求方程的近似值转化为求方程 的正根,的正根,方程:方程:以以为迭代函数,为迭代函数, 以以为初始近似得到迭代序列:为初始近似得到迭代序列:取取作为作为的近似值,得:的近似值,得:下证序列下证序列收敛于收敛于只要证只要证满足定理满足定理3 3,即证即证在某个区间上满足定理在某个区间上满足定理3的条件。的条件。取区间为取区间为列出等价列出等价非线性方程组解法PPT课件取区间为取区间为在在上满足定理上满
30、足定理3 3。则迭代法收敛。则迭代法收敛。 即即1.41421571.4142157就是就是近似值。近似值。非线性方程组解法PPT课件4 4 迭代函数迭代函数g(x)g(x)的选取方法的选取方法选取的选取的g(x )g(x )必须满足必须满足: :(1) (1) 两方程同解;两方程同解;(2) (2) 迭代序列收敛于其根。迭代序列收敛于其根。两种选两种选g(x)g(x)的方法的方法: :存在,存在,为含根区间为含根区间, ,使得使得设设为正常数为正常数, , 试用形如试用形如作迭代函数作迭代函数. . 选取选取 使得使得对于某正实数对于某正实数成立成立. .且存在常数且存在常数作为迭代函数作为
31、迭代函数. .则简单迭代法收敛于则简单迭代法收敛于的根的根特别特别, ,使得使得(5 (5 牛牛顿迭代法的迭代法的变形形) )非线性方程组解法PPT课件2) 2) 假设已知假设已知此时此时不能作为迭代函数不能作为迭代函数, ,若若的反函数的反函数容易求出容易求出, ,可用可用作为迭代函数作为迭代函数. .?因为因为与与同根同根. .此时可用此时可用求解求解的根的根且该迭代法收敛于且该迭代法收敛于例例 求求在在上的根上的根. .解解: :在在上有根上有根. .方程方程与与等价等价. .但但 故不能用故不能用作为迭代函数作为迭代函数. .然而然而的反函数的反函数的导数的导数在在上满足上满足所以可用
32、所以可用作迭代函数求作迭代函数求的根的根. .非线性方程组解法PPT课件5 5 迭代结束条件迭代结束条件1)1)根据实际问题需要定出解的误差界根据实际问题需要定出解的误差界由由定出迭代次数定出迭代次数2)2)用相邻两次近似值有多少位有效数字相同用相邻两次近似值有多少位有效数字相同, ,判断是否停机判断是否停机. .注注: : (1) (1) 编程序时编程序时, ,要注意结束条件要注意结束条件. .(2)(2)定出的定出的不准确不准确, ,因为计算中有舍入误差,故使因为计算中有舍入误差,故使迭代次数迭代次数比计算的比计算的 要大。要大。 1.1.理解简单迭代法的理解简单迭代法的思想方法,几何意义
33、,压缩不动点定理。思想方法,几何意义,压缩不动点定理。 2. 掌握简单迭代法的收敛掌握简单迭代法的收敛( (局部局部) )定理定理(定理证明,会判断简单(定理证明,会判断简单迭代法是否收敛)迭代法是否收敛)。非线性方程组解法PPT课件(1)(1) 将将f(x)=0f(x)=0化为等价方程化为等价方程若若收敛于收敛于且且连续连续, ,则则是是f(x)=0f(x)=0的根的根。1 1 简单迭代法的基本思想方法:简单迭代法的基本思想方法:出发出发, ,作序列作序列(2) 从某从某3 解解x=g(x)x=g(x)的简单迭代法的简单迭代法 迭代公式迭代公式2. 2. 收敛性收敛性(定理(定理3及推论及推
34、论1)使使有有或或3 3、局部收敛性(定理、局部收敛性(定理4 4及推论及推论2 )有有4 4、高阶收敛性(定理、高阶收敛性(定理5 5)则收敛阶为则收敛阶为m。非线性方程组解法PPT课件4 4 迭代法的加速法迭代法的加速法4.1 Aitken(4.1 Aitken(埃特金埃特金) )加速方法加速方法假设简单迭代序列假设简单迭代序列线性收敛于线性收敛于即即( (加速收敛技巧加速收敛技巧) )设设( (若等号成立若等号成立, ,则则是精确解是精确解) )( (若等号成立若等号成立, ,则则不收敛不收敛. .因为因为则则 如图示如图示: : 不收敛于不收敛于 ) ) 记序列记序列的埃特金加速序列为
35、的埃特金加速序列为埃特金加速序列埃特金加速序列比原简单序列比原简单序列更快地收敛于更快地收敛于二阶差分算子二阶差分算子非线性方程组解法PPT课件定理定理6:6: 若序列若序列 线性收敛于线性收敛于则则 的埃特金加速序列的埃特金加速序列 比原简单序列比原简单序列 更快地收敛于更快地收敛于即即分析分析: : 该定理的证明用数学分析中证明极限的技巧该定理的证明用数学分析中证明极限的技巧. .证明证明: :则有则有由由得得,即,即# #非线性方程组解法PPT课件几何意义几何意义: :设初值设初值由迭代法由迭代法: :由三角形相似由三角形相似, ,得得: :过两点过两点作直线作直线 , ,说明说明:该表
36、达式正是埃特金加速收敛的公式该表达式正是埃特金加速收敛的公式, ,比比更接近于更接近于从图中可以看出从图中可以看出(1)(1)这里的这里的并不是简单收敛列并不是简单收敛列中的中的(2)(2)对某些不收敛的情况对某些不收敛的情况, ,用埃特金方法用埃特金方法“加速加速”也有可能收敛也有可能收敛. .的交点为的交点为与与非线性方程组解法PPT课件4.2 Steffenson4.2 Steffenson迭代方法迭代方法 在埃特金加速法中在埃特金加速法中, , 只要有三个相邻点就可以进行加速只要有三个相邻点就可以进行加速, ,把把简单迭代与埃特金加速方法结合起来可建立简单迭代与埃特金加速方法结合起来可
37、建立SteffensoSteffenso迭代方法迭代方法. .设设g(x)g(x)为迭代函数为迭代函数, ,为初始值为初始值, ,为迭代序列为迭代序列, ,则迭代则迭代过程如下过程如下: :并有局部收敛定理。并有局部收敛定理。定理定理8 8 若若是是g(x)g(x)的不动点的不动点,g(x),g(x)一次连续可微一次连续可微, ,存在存在, ,则存在则存在只要只要由由SteffensoSteffenso方法产生的方法产生的收敛于收敛于而且收敛阶至少为而且收敛阶至少为2 2。迭代序列迭代序列从例从例7 7、8 8可以看出收敛速度确实快。可以看出收敛速度确实快。非线性方程组解法PPT课件优点:优点
38、:收敛速度快。收敛速度快。缺点:缺点:计算量大,一步计算量大,一步SteffensoSteffenso方法迭代的计算量相当于两方法迭代的计算量相当于两步简单迭代。步简单迭代。理解简单迭代法的理解简单迭代法的加速收敛方法。加速收敛方法。非线性方程组解法PPT课件5 5 解解f(x)=0f(x)=0的的NewtonNewton迭代法迭代法Newton-RaphsonNewton-Raphson法是广泛应用的高效计算方法。法是广泛应用的高效计算方法。基本思想基本思想: : 非线性方程局部非线性方程局部线性化线性化 ( (化繁为简化繁为简) )特点特点: : 单根附近具有较高的收敛速度单根附近具有较高
39、的收敛速度5.1 Newton5.1 Newton迭代公式迭代公式 (Newton(Newton法或切线法法或切线法) )1 1 公式公式: :设非线性方程设非线性方程,其精确解或真解为其精确解或真解为f(x)f(x)二次连续可导二次连续可导, ,是是(5.1)(5.1)的第的第k k次近似解。次近似解。的泰勒展开式为的泰勒展开式为: :其中其中介于介于与与之间。之间。是是在点在点的线性展开的线性展开 ( (线性主部线性主部) ), 用其近似用其近似f(x),f(x),即有即有并设并设则则f(x)f(x)在点在点非线性方程组解法PPT课件NewtonNewton迭代公式迭代公式: :说明说明:
40、 : 公式推导过程中是用公式推导过程中是用f(x)f(x)的泰勒展开式的的泰勒展开式的线性线性部分部分作作为为f(x)f(x)的近似值的近似值, ,因此说因此说NewtonNewton法是一个法是一个逐次线性化逐次线性化方法。方法。把把作为第作为第K+1K+1次近似解次近似解,即得即得非线性方程组解法PPT课件2 2 几何意义几何意义设曲线设曲线y =f(x)y =f(x)的图象如图示的图象如图示, ,的的k k次近似次近似, ,曲线曲线 y=f(x)y=f(x)上对上对应的点为应的点为过该点作过该点作曲线曲线y=f(x)的切线的切线交交x x轴于点轴于点近似曲线近似曲线y=f(x),y=f(
41、x), 则则与与x x轴的交点轴的交点作为作为f(x)=0f(x)=0的第的第k+1k+1次近似解。次近似解。即由即由(5.2)(5.2)式令式令y=0y=0得得该式就是该式就是NewtonNewton法的迭代公式法的迭代公式, , 因此因此NewtonNewton法也称为法也称为切线法切线法。非线性方程组解法PPT课件3 3 牛顿法与简单迭代法、正割法的关系牛顿法与简单迭代法、正割法的关系 若取若取 若若(差商近似代替微商)差商近似代替微商)即即则则简单迭代法简单迭代法 (迭代函数为迭代函数为g(x)NewtonNewton法法则则正割法正割法NewtonNewton法法即即因此正割法也称为
42、离散的因此正割法也称为离散的NewtonNewton法,法, 或者称为或者称为NewtonNewton法的法的改进。改进。非线性方程组解法PPT课件牛顿法也存在收敛问题,并不是对牛顿法也存在收敛问题,并不是对所有函数牛顿法都收敛所有函数牛顿法都收敛。因此有收敛因此有收敛定理。定理。5.2 Newton5.2 Newton法收敛定理法收敛定理1 1 收敛定理收敛定理定理定理9 9 (NewtonNewton法局部超线性收敛性)法局部超线性收敛性)如果如果f(x)f(x)在解在解邻近连续邻近连续 可导可导, ,且且则存在则存在只要只要NewtonNewton序列序列超线性超线性收敛于收敛于即即牛顿
43、法迭代会越跑越远。牛顿法迭代会越跑越远。 如图示如图示: :非线性方程组解法PPT课件分析:分析:NewtonNewton迭代公式为迭代公式为若证其收敛性,若证其收敛性,可看作可看作简单迭代,即简单迭代,即则迭代函数为则迭代函数为若若f(x)f(x)在解在解邻近连续可导,邻近连续可导, 则只要证则只要证g(x)g(x)在不动点在不动点处可微,且处可微,且则可由则可由363363页的推论页的推论2 2知迭代序列知迭代序列收敛于收敛于而且而且成立成立。因此该定理只要证因此该定理只要证即可。即可。 要证要证由导数的定义证,由导数的定义证, 即证即证可由可由来推导。来推导。非线性方程组解法PPT课件证
44、明:证明:中值定理中值定理其中其中介于介于与与之间。之间。即即若令若令则则再由再由的连续性知的连续性知则则即即所以由所以由363363页的推论页的推论2 2得得非线性方程组解法PPT课件牛顿法不仅收敛且在一般情况下收敛速度较快,是二阶收敛。牛顿法不仅收敛且在一般情况下收敛速度较快,是二阶收敛。分析:分析: 由定理由定理9 9知知NewtonNewton法超线性收敛,因此该定理只证法超线性收敛,因此该定理只证(5.6)(5.6)式式, ,因因(5.6)(5.6)式中有式中有f(x)f(x)的二阶导数及的二阶导数及因此试用含二阶导因此试用含二阶导数数项的泰勒展开式项的泰勒展开式。定理定理1010(
45、NewtonNewton法局部二阶收敛性)法局部二阶收敛性) 如果如果f(x)f(x)在解在解邻近邻近二次二次则存在则存在只要只要NewtonNewton序列二阶序列二阶即即连续可导连续可导, ,且且收敛于收敛于证明证明: : 首先首先将将在点在点进行泰勒展开进行泰勒展开: :代入上式代入上式, ,得得其中其中介于介于与与之间。之间。非线性方程组解法PPT课件说明说明: :当当时时, ,有有NewtonNewton法超二阶收敛法超二阶收敛. .定理定理9 9和定理和定理1010都要求满足都要求满足在实际应用中对初值在实际应用中对初值要求要求高高, ,初值选取较困难初值选取较困难. .可以放宽对
46、初值的要求可以放宽对初值的要求, ,即有以下的非即有以下的非局部收敛定理局部收敛定理: :# #当当时时, ,并由并由的连续性的连续性, ,则则其中其中介于介于与与之间。之间。非线性方程组解法PPT课件定理定理1111 (NewtonNewton法非局部收敛定理)法非局部收敛定理)且满足且满足: :在在上不变号;上不变号;在在上不取零上不取零则对则对满足满足NewtonNewton序列单调二阶收敛序列单调二阶收敛于于在在上的唯一解上的唯一解(2)(2)证证NewtonNewton序列是单调序列序列是单调序列, ,是有界序列是有界序列, ,因此有极限;因此有极限;(1)(1)证证f(x)=0f(
47、x)=0在在上有唯一解上有唯一解分析分析:分以下几步证明分以下几步证明: :需要证明需要证明为什么为什么NewtonNewton序列序列单调二阶收敛单调二阶收敛于于在在上的唯一解上的唯一解该定理中该定理中比较容易选取比较容易选取, 只要满足只要满足即可即可. .(3)(3)证明证明(2)(2)的极限值就是的极限值就是f(x)=0f(x)=0的唯一解的唯一解最后由定理最后由定理1010得得NewtonNewton序列二阶收敛于序列二阶收敛于非线性方程组解法PPT课件证明证明: : (1) (1) 先证先证f(x)=0f(x)=0有唯一解有唯一解. .(2) (2) 证证NewtonNewton序
48、列单调序列单调, ,有界有界, ,从而有极限从而有极限. .设设满足满足考虑由牛顿法得到的考虑由牛顿法得到的的特性的特性, ,因为因为f(x)f(x)连续连续, ,所以所以f(x)=0f(x)=0在在上至少有一个上至少有一个解解, ,设为设为又因为又因为连续连续, ,则则上恒正或恒负上恒正或恒负, , 从而从而f(x)f(x)在在上严格单调上升或下降上严格单调上升或下降, ,f(x)=0f(x)=0在在定理定理1111 (NewtonNewton法非局部收敛定理)法非局部收敛定理)且满足且满足: :在在上不变号;上不变号;在在上不取零上不取零则对则对满足满足NewtonNewton序列单调二阶
49、收敛序列单调二阶收敛于于在在上的唯一解上的唯一解上最多只有一个解上最多只有一个解. . 因此因此f(x)=0f(x)=0在在内有唯一解内有唯一解非线性方程组解法PPT课件其中其中介于介于与与之间之间. .另外另外, ,比较以上两式比较以上两式, ,并考虑到并考虑到与与同号同号, ,得得介于介于与与不变号不变号. .与与同号同号 ( (否则否则f(x)=0f(x)=0不是有唯一解不是有唯一解) ), 同时可得同时可得同理由同理由得由牛顿法得到的得由牛顿法得到的必介于必介于与与之间,且之间,且与与同号同号. .首先由首先由由此得到的牛顿序列由此得到的牛顿序列之间,之间, ( (若若则则若若则则)
50、)且且非线性方程组解法PPT课件则有则有满足满足介于介于与与之间之间, ,从而从而且且又单调、有界序列必有极限,又单调、有界序列必有极限,设极限为设极限为是单调序列并有界是单调序列并有界(3)(3)证证对对两边取两边取时的极限时的极限, ,得得由于由于从而从而又由又由在在上只有唯一解上只有唯一解得得即即最后最后, ,由定理由定理1010知知二阶收敛于二阶收敛于# #非线性方程组解法PPT课件NewtonNewton迭代公式迭代公式: :定理定理1111(NewtonNewton法非局部收敛定理)法非局部收敛定理)且满足且满足: :在在上不变号;上不变号;在在上不取零上不取零则对则对满足满足Ne
51、wtonNewton序列单调二阶收敛序列单调二阶收敛于于在在上的唯一解上的唯一解定理定理1010(NewtonNewton法局部二阶收敛性)法局部二阶收敛性) 如果如果f(x)f(x)在解在解邻近邻近二次二次则存在则存在只要只要NewtonNewton序列二阶序列二阶即即连续可导连续可导, ,且且收敛于收敛于本课内容:本课内容:非线性方程组解法PPT课件(1)掌握)掌握Newton迭代公式迭代公式:(2)掌握)掌握Newton法局部二阶收敛定理法局部二阶收敛定理并会并会证明证明。(3)理解)理解Newton法非局部收敛定理法非局部收敛定理及及证明证明。非线性方程组解法PPT课件NewtonNe
52、wton迭代公式迭代公式: :定理定理1111(NewtonNewton法非局部收敛定理)法非局部收敛定理)且满足且满足: :在在上不变号;上不变号;在在上不取零。上不取零。则对则对满足满足NewtonNewton序列单调二阶收敛序列单调二阶收敛于于在在上的唯一解上的唯一解定理定理1010(NewtonNewton法局部二阶收敛性)法局部二阶收敛性) 如果如果f( (x) )在解在解邻近邻近二次二次则存在则存在只要只要NewtonNewton序列二阶序列二阶即即连续可导连续可导, ,且且收敛于收敛于5.2 Newton5.2 Newton法收敛定理法收敛定理1 1 收敛定理收敛定理5 5 解解
53、f( (x)=0)=0的的NewtonNewton迭代法迭代法5.1 Newton5.1 Newton迭代公式迭代公式非线性方程组解法PPT课件例例9 9用用NewtonNewton法求解法求解解解: : 首先可以判断解在首先可以判断解在(0,1)(0,1)内内. .在在(0,1)(0,1)上上( (恒正恒正) )( (不变号不变号) )则则NewtonNewton迭代序列单调二阶收敛到迭代序列单调二阶收敛到在在(0,1)(0,1)内的唯一根内的唯一根NewtonNewton迭代取迭代取的计算结果如表的计算结果如表 . . 非线性方程组解法PPT课件2 Newton2 Newton法的推广与改
54、进法的推广与改进u 重根加速收敛法重根加速收敛法( (推广推广)u 正割法正割法( (或弦截法或弦截法)()(改进改进)定理定理9 9、1010、1111中,中,意味着意味着是是f( (x)=0)=0的单根的单根, , 假设假设是是f( (x)=0)=0的的m( (m1)1)重根重根, , NewtonNewton法能否用法能否用? ? 怎样用怎样用? ? 是否收敛是否收敛? ?(1) (1) 重根处重根处NewtonNewton法是收敛的法是收敛的事实上,事实上,设设是是f( (x)=0)=0的的m( (m1)1)重根重根, ,即即则则当当x接近接近时时, ,非线性方程组解法PPT课件重根处
55、重根处NewtonNewton法是局部线性收敛的法是局部线性收敛的. .重数重数越大越大,收敛越慢收敛越慢.结论结论: :m =1=1时即是牛顿法,此时时即是牛顿法,此时 是超线性收敛,即二阶收敛。是超线性收敛,即二阶收敛。(2)(2)加速法加速法l 以以NewtonNewton法为基本简单迭代法为基本简单迭代 , ,用用SteffensonSteffenson方法进行计算方法进行计算可可得二阶收敛迭代序列得二阶收敛迭代序列. .l 定义新函数定义新函数( (两种两种) )非线性方程组解法PPT课件l 定义新函数定义新函数则则若若是是f( (x) )的的m重根重根, ,必为必为h( (x) )
56、的单根的单根. . 因此因此, ,可用可用Newton法求法求h( (x)=0)=0的单根的单根. .即即h( (x)=0)=0的单根即为的单根即为f( (x)=0)=0的重根的重根. .且该迭代是二阶收敛的且该迭代是二阶收敛的. .( (定理定理10)10)事实上,事实上,非线性方程组解法PPT课件而在计算而在计算机机NewtonNewton法的每一步迭代中,都要计算一次导数值,法的每一步迭代中,都要计算一次导数值,上,计算一次导数的近似值比计算函数的近似值要麻烦的多,上,计算一次导数的近似值比计算函数的近似值要麻烦的多,为了为了避避免求导数免求导数, ,用差商近似代替微商用差商近似代替微商
57、, ,即得正割法。即得正割法。 详见牛顿迭代法详见牛顿迭代法与正割法的关系与正割法的关系. .5.3 Newton5.3 Newton下山法下山法( (修正的修正的NewtonNewton法法) )牛顿法收敛速度快,但对初值牛顿法收敛速度快,但对初值要求苛刻。要求苛刻。在实际应用中不在实际应用中不容易确定,有时往往由于初值选取不当而使迭代不收敛容易确定,有时往往由于初值选取不当而使迭代不收敛. Newton. Newton下山法是一种降低对初值要求的下山法是一种降低对初值要求的修正的牛顿法修正的牛顿法. .1 1 下山序列的定义下山序列的定义若视若视| |f( (x)|)|为为f( (x) )
58、在在x点的高度点的高度, ,则则是山谷最低点是山谷最低点. .定义定义: : 若序列若序列满足满足,称,称是是f(x)f(x)的的一个一个下山序列下山序列. .下山序列的极限点下山序列的极限点, , 不一定是不一定是f( (x) )0 0的解的解. .方程方程f( (x) )0 0的解的解 满足:满足:,称,称 是是| |f( (x)|)|的最小点。的最小点。注注: :u 正割法是正割法是Newton法的改进法的改进非线性方程组解法PPT课件2 2 收敛的牛顿序列除去有限点外一定是下山序列收敛的牛顿序列除去有限点外一定是下山序列因为因为中值定理中值定理非线性方程组解法PPT课件3 3 下山法下
59、山法引理引理1 1则一定存在则一定存在成立成立分析分析: : 该式子实际上是两个函数值的比较该式子实际上是两个函数值的比较, ,即是点即是点x与邻近点与邻近点的函数值的函数值, , 而点而点x与点与点只差只差且含有且含有f( (x) )的导数的导数因此考虑用导数的定义因此考虑用导数的定义, ,时用形如时用形如: :的导数定义的导数定义. .非线性方程组解法PPT课件证明证明: : 由导数的定义由导数的定义得得即即引理引理1 1则一定存在则一定存在成立成立于是由极限的概念于是由极限的概念, ,只要只要有有存在存在非线性方程组解法PPT课件于是由极限的概念于是由极限的概念, ,只要只要有有从而从而
60、则则# #即即存在存在非线性方程组解法PPT课件牛顿下山法的定义牛顿下山法的定义: :是是f( (x) )在在点的下山方向点的下山方向. .在牛顿在牛顿其中其中称为称为下山因子下山因子. .该方法称为该方法称为牛顿下山法牛顿下山法. .说明说明: : (1)(1)当当时时, ,牛顿下山法为标准的牛顿下山法为标准的牛顿法;牛顿法; 当当时时, ,此时此时不收敛不收敛于于因此为保证收敛性因此为保证收敛性, tk 不能太小不能太小. .(2)(2)下山因子下山因子tk的一种常用取法先取的一种常用取法先取若已满足若已满足则把则把作为第作为第k+1+1次近似值次近似值; 若不满足若不满足, ,则取则取再
61、判断是否再判断是否满满若满足若满足, ,把把作为作为k+1次近似值次近似值;否则取否则取法中法中, ,可以适当选择可以适当选择使使满足满足非线性方程组解法PPT课件举例举例: :求求 在在1.51.5附近的根附近的根. .解解: :若取初值若取初值1.5,1.5,满足收敛条件满足收敛条件. .但若取但若取计算得计算得与可能值的差距加大与可能值的差距加大, ,即使能收敛速度也会很慢即使能收敛速度也会很慢. . 此时用牛顿下山此时用牛顿下山法法, ,设下山因子为设下山因子为t , ,则计算结果如下表则计算结果如下表: :此时此时, ,计算方法计算方法: :非线性方程组解法PPT课件 如表所示如表所
62、示, ,用牛顿下山法用牛顿下山法, ,第第1 1次就落入了局部收敛的领域次就落入了局部收敛的领域, ,到到第第4次时近似值的精度已经相当高了次时近似值的精度已经相当高了. .本课重点本课重点: : 会会讨论讨论牛顿法求方程牛顿法求方程f(x)=0f(x)=0的的m m重根的近似值的加速收敛性。重根的近似值的加速收敛性。 理解牛顿法的修正:理解牛顿法的修正:牛顿下山法牛顿下山法。非线性方程组解法PPT课件6* 解方程组解方程组x= =G( (x) )的简单迭代法的简单迭代法6.1 6.1 简单迭代法简单迭代法问题问题: : F( (x) )实函数向量实函数向量. .求求F( (x)=0)=0的近
63、似解的近似解。(1)(1)先将先将F(x)=0 0化为等价方程化为等价方程基本思想方法:基本思想方法:假设假设每个每个gi有连续的二阶导数:有连续的二阶导数:G( (x) )在点在点x的的F-导数为:导数为:( (迭代公式迭代公式) )( (6.3)6.3)式称为式称为简单迭代简单迭代或或单点迭代单点迭代或或单步迭代法单步迭代法。映射映射G(x)称为称为迭代映射。迭代映射。非线性方程组解法PPT课件当迭代当迭代( (6.3)6.3)收敛时收敛时, ,极限点极限点又是又是G(x)的连续点的连续点, ,则则的解,则称的解,则称x*为为G(x)的不动点。的不动点。6.2 6.2 简单迭代的简单迭代的
64、收敛性收敛性定义定义4 4则映射则映射G(x)在区域在区域D上称为压缩的。上称为压缩的。常数常数L称称为压缩因子。压缩因子。定理定理1212 ( (压缩不动点定理压缩不动点定理) ) 设映射设映射G(x)在区域在区域D上上满足:满足:(2) G(x)在区域在区域D上是压缩映射,压缩因子为上是压缩映射,压缩因子为L;简单迭代简单迭代(6.3)产生的序列产生的序列收敛于收敛于G(x)在区域在区域且有误差估计:且有误差估计:D上的唯一不动点上的唯一不动点 ,非线性方程组解法PPT课件证明:证明: 由条件(由条件(1)知所有的)知所有的 全在全在D内,序列内,序列首先证明首先证明G(x)在区域在区域D
65、上有唯一不动点上有唯一不动点又因又因G(x)在区域在区域D上是压缩映射,上是压缩映射, 在在x*处连续,处连续,非线性方程组解法PPT课件从而从而其次证唯一性其次证唯一性,为为在在D上另一根上另一根, ,则则设设( (6.46.4) )式较难验证,常采用以下更强的条件代替,式较难验证,常采用以下更强的条件代替,定理定理1313(局部收敛定理)(局部收敛定理)上满足上满足且有误差估计:且有误差估计:产生的迭代序列产生的迭代序列收敛于收敛于由矩阵范数与谱半径的关系可得以下的定理:由矩阵范数与谱半径的关系可得以下的定理:非线性方程组解法PPT课件定理定理1414(局部收敛定理)(局部收敛定理)而且其
66、谱半径小于而且其谱半径小于1:产生的迭代序列产生的迭代序列收敛于收敛于7 7 解方程组解方程组F( (x)=)=0 0的的NewtonNewton法法基本思想基本思想: : 非线性方程局部非线性方程局部线性化线性化 ( (化繁为简化繁为简) )7.1 Newton7.1 Newton法迭代公式法迭代公式1 1 公式公式: :非线性方程组非线性方程组,其精确解或真解为其精确解或真解为F( (x) )在在x*邻近有连续的邻近有连续的F导数导数是是(7.1)(7.1)的第一个的第一个近似解。近似解。用用L(x)近似近似F( (x),),用用L(x)=0的解的解并设并设且且F( (x) )在点在点则仿
67、射映射则仿射映射是映射是映射( (函数函数) )y= =F( (x) )的局部近似。的局部近似。作为(作为(7.1)的改进解)的改进解,即即非线性方程组解法PPT课件NewtonNewton迭代公式迭代公式: :出发出发, ,利用上式不断改进得利用上式不断改进得从某从某2 2 牛顿法与简单迭代法的关系牛顿法与简单迭代法的关系即即则则简单迭代法简单迭代法 (迭代映射为迭代映射为G(x)NewtonNewton法法非线性方程组解法PPT课件7.2 7.2 收敛定理收敛定理局部超线性收敛定理局部超线性收敛定理定理定理1515 如果如果F( (x) )在解在解x*邻近有连续的邻近有连续的F导数导数,则
68、存在则存在只要只要即即超线性超线性收敛于收敛于NewtonNewton迭代生成的序列迭代生成的序列牛顿法不仅收敛且在一般情况下收敛速度较快,是二阶收敛。牛顿法不仅收敛且在一般情况下收敛速度较快,是二阶收敛。定理定理1616(NewtonNewton法局部二阶收敛性)法局部二阶收敛性) 如果如果F( (x) )的每个分量在解的每个分量在解邻近有邻近有二阶连续偏导数二阶连续偏导数,则存在则存在只要只要NewtonNewton序列至少二阶收敛于序列至少二阶收敛于即即非线性方程组解法PPT课件7.3 Newton7.3 Newton下山法下山法牛顿法收敛速度快,但对初值牛顿法收敛速度快,但对初值要求苛
69、刻。要求苛刻。在实际应用中不在实际应用中不容易确定,有时往往由于初值选取不当而使迭代不收敛容易确定,有时往往由于初值选取不当而使迭代不收敛. Newton. Newton下山法是一种降低对初值要求的下山法是一种降低对初值要求的修正的牛顿法修正的牛顿法. .引理引理2 2则一定存在则一定存在成立成立方向。在牛顿法中引进方向。在牛顿法中引进下山因子:下山因子:成立的最大值。成立的最大值。Newton法的法的修正修正方向方向是是F( (x) )在在x点的下山点的下山下山法:下山法:非线性方程组解法PPT课件缺点:缺点: Newton法的法的计算量比较大,因为每步要计算计算量比较大,因为每步要计算JacobiJacobi阵阵m步步 Newton法、割线法、拟法、割线法、拟 Newton法、法、改进方法:改进方法:Broyden方法、一般方法、一般quasi- Newton法。法。理解解方程组的理解解方程组的简单迭代法简单迭代法、Newton法法及及收敛定理。收敛定理。非线性方程组解法PPT课件