非线性方程组解法

1、非线性方程非线性方程 (组组) 解法的内容解法的内容 非线性方程的解法非线性方程的解法 非线性方程非线性方程组组的解法的解法 1. 解法解法牛顿法及牛顿型迭代法（拟牛顿法等牛顿法及牛顿型迭代法（拟牛顿法等) )；搜索法；搜索法；牛顿迭代法；牛顿迭代法； 弦截法；弦截法；多项式方程求根多项式方程求根延拓法；延拓法；最速下降法；最速下降法；2. 简单迭代法与牛顿迭代法的收敛性简单迭代法与牛顿迭代法的收敛性2.牛顿法、割线法、延拓法等的收敛性牛顿法、割线法、延拓法等的收敛性二分法；二分法； 简单迭代法；简单迭代法；（牛顿法、劈因子法）（牛顿法、劈因子法）1. 解法解法非线性最小二乘问题的计算方法非线

2、性最小二乘问题的计算方法1 基础知识基础知识1.1 非线性方程非线性方程(组组)及解的概念及解的概念2.常见的非线性方程常见的非线性方程高次方程高次方程, ,即多项式即多项式方程方程超越方程超越方程 例例1. 产生的背景产生的背景:科学理论与工程技术都可化为非线性方程科学理论与工程技术都可化为非线性方程(组组)第七章第七章 非线性方程（组）解法非线性方程（组）解法非线性最小二乘问题；非线性最小二乘问题；非线性积分、微分方程数值解非线性积分、微分方程数值解0)2sin( xex; 1cos xex 3.非线性方程的解：非线性方程的解：f (x)=0的根，或称为函数的根，或称为函数f (x)的零点

3、的零点.注：注：()方程的根可能是实数也可能是复数，相应地称为方程方程的根可能是实数也可能是复数，相应地称为方程的的实根实根或或复根复根。如果函数如果函数f (x)可因式分解为可因式分解为且且 )()()(xgxxxfm 0)( xg称称x*为为函数函数f (x)的的m重零点重零点，或称为，或称为方程方程f (x)=0的的m重根重根;当当m时，时，称称x*为为函数函数f (x)的的单重零点单重零点，又称作，又称作方程方程f (x)=0的的单根单根 ; 如果如果称称x*为方程为方程f (x)=0的的m重根重根.，1 m() 重根亦可利用导数来定义重根亦可利用导数来定义(略略)。若存在数若存在数

4、x*满足满足 f (x*)=0，则，则x*称为方程称为方程记为：记为： f (x)=0求解的特点：求解的特点： 无求解公式，无直接解法无求解公式，无直接解法，难求得精确解。难求得精确解。举例举例: :超越方程超越方程1.2 非线性方程非线性方程(组组)求解的特点求解的特点1cos xex 间接法间接法( (迭代法迭代法):):从一个初始近似值出发从一个初始近似值出发, ,重复某种计算过程重复某种计算过程没有一定的解法。没有一定的解法。间接法即迭代法。间接法即迭代法。来来不断改进近似解不断改进近似解，有限次改进后有限次改进后, ,计算出一个满足误差要求计算出一个满足误差要求的的近似解近似解，这种

5、求解方法称为这种求解方法称为迭代法迭代法。求解的方法：求解的方法：迭代法求解的要求：迭代法求解的要求： l 收敛收敛l 计算效率计算效率( (计算量计算量) )l 数值稳定性数值稳定性( (计算机的舍入误差计算机的舍入误差) ) 初始值好初始值好迭代公式合适迭代公式合适( (好的好的) ).,lim*)(*)( kxxxxkkk当当或或并并记记为为1.3 收敛性和收敛阶收敛性和收敛阶定义定义1成成立立及及点点列列对对于于点点 0*2*1*),(kknxxxxx, 0|lim*)( xxkk.*0)(xxkk收收敛敛于于点点则则称称点点列列 序列的收敛性序列的收敛性 序列的收敛阶序列的收敛阶称称

6、若若, 1 , 0,lim*)(*)( kxxxxkkk(1)(1)线性的线性的, ,若若收收敛敛于于 0kkx定义定义2是是点点*x);1 , 0(|lim*)(*)1( Cxxxxkkk(2)(2)超线性的超线性的, ,若若(3) p 阶收敛的阶收敛的, ,若若;0|lim*)(*)1( xxxxkkk. 1, 0|lim*)(*)1( pCxxxxpkkk注注 ：= =2时为二阶收敛时为二阶收敛, , 也称为也称为平方平方收敛收敛。2初始近似值的搜索、二分法和插值法初始近似值的搜索、二分法和插值法 2.1逐步搜索法逐步搜索法满足条件，满足条件，2. 解决问题依据解决问题依据 连续函数介值

7、定理连续函数介值定理, ,即若即若f( (x) )满足条件：满足条件：即即 a, ,b 内至少有方程内至少有方程(2.1)的一个根的一个根, ,0)()(,)( bfafbaCxf且且, 0)(* xf使使得得称称 a, ,b 为为f( (x) )的一个的一个含根区间含根区间。若非线性方程若非线性方程 f( (x)=0 )=0 (2.1) ba2ba *x1. 问题问题3. 逐步搜索法思想方法（基本思想）逐步搜索法思想方法（基本思想）根分布如何？如何确定求根区间？根分布如何？如何确定求根区间？ 如何求根？如何求根？把含根区间不断缩短，把含根区间不断缩短，求的近似解。求的近似解。，那么方程是否，

8、那么方程是否有根？有根？ 有根有根则则f( (x) )在在 a, ,b 存在某个存在某个x* *0)()(,)( bfafbaCxf且且且使含根区间之且使含根区间之间间含有一个满足误差要含有一个满足误差要设连续函数设连续函数f( (x) )的含根区间为的含根区间为 a, ,b ，不妨假定不妨假定 f( (a) )，从从出发出发，按预定步长按预定步长h （譬如取（譬如取 ax 0NNabh, 为正整数），一步为正整数），一步每跨一步进行一次根的每跨一步进行一次根的“搜索搜索”，即检查点，即检查点 khaxk 上的函数值上的函数值 )(kxf的符号，一旦发现的符号，一旦发现 处处的的函函数数值值异

9、异号号，即即处处与与axk, 0)( kxf一步地向右跨，一步地向右跨， 则可确定一个缩小了的含根区间则可确定一个缩小了的含根区间,1kkxx ，其长度等于预，其长度等于预 定的步长定的步长h。 特别地，可能有特别地，可能有, 0)( kxf这时这时xk即为所求的根。即为所求的根。 例例1 方程方程 f( (x)=)=x3- -x-1=0-1=0，利用逐步搜索法确定一个含根区间。利用逐步搜索法确定一个含根区间。 解解 )0(f在区间（在区间（0，2）内至少有一个实根。）内至少有一个实根。 设从设从x=0=0出发，取出发，取h=0.5为步长向右进行根的搜索，为步长向右进行根的搜索， 列表如下列表

10、如下 x 0 0.5 1.0 1.5 2f (x) - - - - - - + + + + 可以看出在可以看出在 1.0, 1.5内必有内必有唯一唯一根根).0)(5 . 1, 0 . 1( xfx时时，当当4. 具体过程（方法）具体过程（方法）)(, 0)2(, 0 xff 2.2 二分法二分法(对分法或分半法对分法或分半法)（满足条件（满足条件 ）2. 解决问题依据解决问题依据 连续函数介值定理连续函数介值定理, ,至少存在某个至少存在某个即即 a, ,b 内至少有方程内至少有方程(2.1)(2.1)的一个根的一个根, ,称称 a, ,b 为为f( (x) ) 0)()(,)( bfafb

11、aCxf且且),(*bax , 0)(* xf使使得得的一个的一个含根区间含根区间。2*bax 3. 思想方法（基本思想思想方法（基本思想）把含根区间不断缩短，使含根区间之把含根区间不断缩短，使含根区间之间间含有一个满足误差含有一个满足误差要求的近似解。要求的近似解。考虑非线性方程考虑非线性方程 f( (x)=0 )=0 (2.1)(2.1) ba2ba 并且有并且有 *x2ab 1. 问题问题);(21)1(000bax 找找中中点点：令令；即即中中点点的的函函数数值值计计算算：)()2(00 xff (3) 生成含根区间：生成含根区间：,0)(0*0 xxxf ，则则若若, 0)()(00

12、 afxf若若,0101bbxa 取取, 0)()(010100 xbaaafxf 取取若若4 4 具体过程（方法）具体过程（方法）,00abhbbaa 令令首首先先满足下式满足下式: :生成含根区间生成含根区间,11ba,)1(0011baba 2)2(11hab 11(3)()()0f af b .,220011bababa得得继继续续以以上上过过程程取取代代以以,11ba且且kibaii, 1 , 0, ，设设已已得得含含根根区区间间 , 2 , 1,)1(11kibabaiiii , 1 ,0,2)2(kihabiii (3)()() 0,0,1, .iif af bik 0,0,从而

13、函数从而函数f( (x) )在区间在区间1.0, 1.5上单调连续上单调连续， , 0875. 0) 5 . 1 (, 01) 1 ( ff所以函数所以函数f( (x) )在区间在区间1.0, 1.5上有唯一根。上有唯一根。 计算过程见表计算过程见表2-1表表 2-101234561.0001.25001.31251.32031.50001.37501.34381.32811.25001.37501.31251.34381.32811.32031.3242kkakbkx)(kxf则则x6 = =1.3242为方程根的近似值为方程根的近似值.例例3证明方程证明方程0sin1 xx在区间在区间0

14、, 1内有一个根内有一个根,使用二分使用二分法求误差不大于法求误差不大于 41021 的根的根, 需二分多少次需二分多少次证证,sin1)(xxxf 令令, 1 , 0时时则则当当 x, 0cos1)( xxf所以所以f( (x) )在在0 , 1上单调减少且连续。上单调减少且连续。, 01sin) 1 (, 01)0( ff又又所以所以f( (x) )在在0 , 1上有且只有一个根上有且只有一个根.使用二分法时，误差限使用二分法时，误差限)(211abxxnn ,10212141 n28.13214)01(1 ggn则则 所以需二分所以需二分14 次即可次即可.(ln102.3026,ln2

15、0.6931). 例例1 ,102 在在x012 x不能求出所有根不能求出所有根,(,(即有可能漏根即有可能漏根) )。例例如图如图该点可求出该点可求出, ,改进的方法：改进的方法：xab但漏掉了四个点但漏掉了四个点2.2.不能用于求偶重根、复根；不能推广到多元方程组求解不能用于求偶重根、复根；不能推广到多元方程组求解. .缺点缺点 的等比级数的收敛速度的等比级数的收敛速度相同，相同，1.1.收敛速度不快收敛速度不快, ,仅与公比为仅与公比为 21即是线性收敛；即是线性收敛；区间搜索法等区间搜索法等. . 1. .理解理解收敛性、收敛阶的概念；收敛性、收敛阶的概念； 3. .会用会用二分法求二

16、分法求非线性方程的近似解及执行次数非线性方程的近似解及执行次数k . . 2. .理解理解逐步搜索法搜索非线性方程解的思想方法逐步搜索法搜索非线性方程解的思想方法, ,理解理解掌握掌握二二作业作业1. 用搜索法求方程用搜索法求方程 065. 015. 08 . 123 xxx的有根区间的有根区间. 2. 用区间二分法求方程用区间二分法求方程 在在1,2的近似根（二分的近似根（二分3次）次）,013 xx并求若近似根准确到并求若近似根准确到10-3至少要二分多少次？至少要二分多少次？ 3. 用区间二分法求方程用区间二分法求方程在在3,4内的根，精确内的根，精确074223 xxx到到10-3。

17、分法分法解非线性方程的思想方法；解非线性方程的思想方法； 复习：复习： 3. 3. 正割法正割法解非线性方程的解非线性方程的思想方法思想方法、迭代公式迭代公式： 2.2. 二分法二分法解解非线性方程的非线性方程的条件条件、思想方法思想方法、执行次数、执行次数k：称称若若, 1 , 0,lim*)(*)( kXXXXkkk(1)(1)线性的线性的, ,若若收收敛敛于于 0kkX(2)(2)超线性的超线性的, ,若若;0lim*)(*)1( XXXXkkk);1 , 0(lim*)(*)1( CXXXXkkk. 1, 0lim*)(*)1( pCpkkXXXXk( (3)3)p p阶收敛的阶收敛的

18、, ,若若1. 序列的序列的收敛阶收敛阶：. 12lnln abN0 给定的误差界给定的误差界)()()(111kkkkkkkxfxfxfxxxx 是是点点*X为为含含根根区区间间,ba2.32.3 抛物线法抛物线法1 1 方法的推导（迭代公式）方法的推导（迭代公式）（二次插值）（二次插值） 设设f(x)=0f(x)=0的根为的根为,*x*x（即（即为方程为方程f(x)=0f(x)=0的精确解）的精确解）可由数据点可由数据点2 , 1 , 0),( ifxikik，构造抛物线，构造抛物线二阶差商二阶差商一阶差商一阶差商牛顿插值牛顿插值)(,)(1kkkkxxfxxfxp )(,112 kkkk

19、kxxxxfxxx)(a1 k次近似次近似,1 kx已已知知，若若kkkkkkfxffxffxf )(,)(,)(1122，k时时当当2 的的是是设设*,12xxxxkkk kkk, 1, 2 次近似，次近似，构造构造用用p(x)p(x)近似近似f(x),f(x),根。根。1 kxkx取取P(x)=0P(x)=0较靠近较靠近的根的根为为f(x)=0的改进近似的改进近似考虑考虑kkxx 1的最小值，的最小值， 变形变形( (a)a)式式( (插项插项),于是于是,kkxx 得得由由,0)( xp0)()(2 kkkkkxxcxxba则有则有0)()(,)(,12121 kkkkkkkkkkkxx

20、xxxxfxxxxxfxxfkakc)1 (kb)(,11 kkkkkxxcfxx得得由由,0)( xp)(,)(1kkkkxxfxxfxp )(,112 kkkkkxxxxfxxx)(akkxx ,0时时当当 kkaf*xxk kkkkkkacabbxx2412 kkkkkkcabbaxx422 ,*xxk 且有且有)1 (0)1()1(2 kkkkkcxxbxxa,4sgn221kkkkkkkkcabbbaxx 取取由此可得（由此可得（2.10）;1kkxx ,0时时当当 kkafkkkkkkcabbaxx422 )()(12kkkkkkxxxxcxxc 2 2 局部收敛定理局部收敛定理只

21、要只要,*210 xxxxx 抛物线法产生的迭代序列抛物线法产生的迭代序列kx收敛于收敛于,*x且有且有.)(6)(lim420. 0*840. 1*1*xfxfxxxxkkk 设设f(x)f(x)在在*x, 0)(* xf则存在则存在, 0 附近附近3 3次连续可导，次连续可导，)(,11 kkkkkkxxcfxxb)(kkxfa fxxxckkkk,21 ,4sgn221kkkkkkkkcabbbaxx )10. 2(继续以上过程，这种生成迭代序列的求根算法称为继续以上过程，这种生成迭代序列的求根算法称为抛物线法抛物线法。定理定理2 2, 3 , 2 k,210 xxx由由给给定定的的可由

22、可由(2.10) 式迭代求更接近式迭代求更接近的近似解的近似解 。*x3x)11. 2(注：注： 1 1 抛物线法可产生实根，也可产生复根。抛物线法可产生实根，也可产生复根。2 2 更高次的插值多项式很少选用更高次的插值多项式很少选用, ,一是高次插值多项式求根困一是高次插值多项式求根困难难, ,二是其收敛速度不会太快，即收敛阶总低于二是其收敛速度不会太快，即收敛阶总低于2 2。2.42.4* * 反插值法反插值法设设f(x)=0f(x)=0的根为的根为.*x由数据点由数据点, 1 , 0),(lixyikik 得得)(y 的的l次插值函数。次插值函数。差商差商取取)0(1qxk )()(yy

23、q 令令则则,) 1(,1121111 lkkklkklkkkkkkkkkkyyyyyyyyyyyyyxx )13. 2(该方法称为该方法称为反插值法反插值法。)(xfy 有反函数有反函数)(yx 且且).0(* x若若f(x)f(x)在在邻近严格单调邻近严格单调*x)()(,)(,)(,)(111211 lkkklkkkkkkkkkkkyyyyyyyyyyyyyyyyyyyxyq :11* kxkx次次近近似似的的是是若若lkkkxxx ,1个已知近似值，个已知近似值，构造构造1 l注：注： 1 1 当当1 l 时，反插值法完全重合于正割法。时，反插值法完全重合于正割法。2 2 反插值法是局

24、部收敛的反插值法是局部收敛的, ,且收敛阶低于且收敛阶低于2 2。思考：思考：总结：总结：上上讨论抛物线法，但平时很少用抛物线法，因为该方法计算量大，讨论抛物线法，但平时很少用抛物线法，因为该方法计算量大，且收敛阶不高。且收敛阶不高。几种插值法的条件不同几种插值法的条件不同。正割法是常用的方法，理论正割法是常用的方法，理论当当2 l 时，反插值法是否是抛物线法时，反插值法是否是抛物线法？解解x=x=g(xg(x) )的简单迭代法的简单迭代法3.1 3.1 简单迭代法公式简单迭代法公式问题问题: : f(xf(x) )实函数实函数. .求求f(xf(x)=0)=0的近似值的近似值。, 1 , 0

25、),(1 kxgxkk(1)(1)先将先将f(xf(x)=0)=0化为等价方程化为等价方程)(xgx )1.3(初始近似初始近似k+1次近似次近似( (迭代公式迭代公式) )2.3(*x若若kx)( xg收敛于收敛于且且连续连续, ,则则*x是是f(xf(x)=0)=0的根的根。说明说明: : 由由f(xf(x)=0)=0化成等价方程化成等价方程x=x=g(xg(x) )的化法有很多种。的化法有很多种。(1) (1) 如何选取如何选取迭代函数迭代函数g(xg(x) )？ (3.2) (3.2)式称为式称为简单迭代法简单迭代法或或单点迭代法单点迭代法或或单步迭代法单步迭代法。 g(x)称称为为迭

26、代函数。迭代函数。基本思想方法：基本思想方法：出发出发, ,作序列作序列:kx0 x(2) 从某从某讨论的问题讨论的问题: :(2) (2) g(xg(x) )满足什么条件，迭代序列收敛？收敛速度是多少？满足什么条件，迭代序列收敛？收敛速度是多少？(3) (3) 如何加速如何加速迭代序列的收敛速度迭代序列的收敛速度？(2)(2)(3)(3)问题问题: : 由由,)(1 kkxxg求求1 kxkx，然而，然而是否是是否是g(xg(x) )定义域上的值定义域上的值? ?定义定义4 4简单迭代法简单迭代法(3.2)(3.2)称为称为适定适定的；的；法法(3.2)称为称为收敛收敛的。的。当迭代当迭代(

27、3.2)(3.2)收敛时收敛时, ,极限点极限点又是又是g(xg(x) )的连续点的连续点, ,则则*x1*lim kkxx的解也称的解也称的不动点。的不动点。)(xg的不动点。的不动点。称为称为则则)(xg*x也可理解成：也可理解成：是映射，若是映射，若 满足满足)(xg*x),(*xgx 。g(x)把定义域的每个把定义域的每个x 映成了映成了g(x)，因此因此)2 .3(的的解解是是即即)2 .3(*xkx保持有界保持有界, ,若迭代序列若迭代序列且全在且全在g(xg(x) )定义域内定义域内, ,则则.lim*xxkk 若进一步有若进一步有则简单迭代则简单迭代)(limkkxg )()l

28、im(*xgxgkk , 1 , 0),(1 kxgxkk迭代公式迭代公式)2.3(注注: : 适定适定是是收敛收敛必要条件，即不必要条件，即不适定适定则一定不则一定不收敛收敛。1)(0*xg说明两点：说明两点：分别就下列四种情况说明几何意义：分别就下列四种情况说明几何意义：kxkx(1)(1)中中的产生。的产生。（2 2）kx何时收敛何时收敛, ,何时发散。何时发散。0)(1*xg1)(* xg1)(* xgy)(xgy xy x0 x1x2x0p1p2p00 x1x2x0p1p2pxy 0*xxy)(xgy几何意义几何意义 )( xgyxy求求x=x=g(xg(x) )的根的根求求的根的根

29、*x*x1p0 x1x2x0p2p)(xgy xy xy0*x*x0p2p0 x*x1x2x1p)(xgy xy 0 xy*x 迭代法收敛迭代法收敛*xxk迭代法不收敛迭代法不收敛从点从点)(,(000 xgxp的直线交的直线交y=xy=x于点于点出发出发, ,作平行于作平行于x x轴轴),(),(00 xgxg作平行于作平行于y y 轴的直线交轴的直线交y =y =g(xg(x) )于点于点过该点过该点),(),(001xggxgp即即).(,(111xgxp依次进行下去得到依次进行下去得到,kx且且).(1kkxgx 1. 1. 简单迭代法简单迭代法(2)(2)给定给定0kxx 满足满足。

30、, 1 , 0),(1 kxgxkk2. 2. 收敛定理收敛定理定理定理3 3；)(0)(xgxxf (1)方法步骤方法步骤: :( (压缩不动点定理或压缩映象定理压缩不动点定理或压缩映象定理) )若迭代函数若迭代函数g(xg(x) )满足满足) 3 . 3(,)()1(baxbaxg , 10)2( L使使,baxx 有有xxLxgxg )()() 4 . 3(则则；内内有有唯唯一一解解在在*0,)(1xbaxgx ；且且得得到到的的由由对对*10lim,)(,2xxbaxxgxbaxkkkkko ；有有误误差差估估计计011*0111:3xxLLxxLxxkkkk )5 . 3()(lim

31、,)(4*1*0 xgxxxxxgkkk 则则存存在在若若（收敛程度）（收敛程度）（收敛速度）（收敛速度）分析分析: : 结论结论(1)(1)中中)(xgx 有唯一根有唯一根, ,因此想到根的存在性定理因此想到根的存在性定理, ,.zLip连续条件。连续条件。(3.4)(3.4)实际是实际是证明：证明：且且得得由由作作,)(),1(,)()(10baCxhxxgxh 若等号成立若等号成立, ,则表示则表示a a是根或者是根或者b b是根是根, , a,ba,b 上已有根存在了上已有根存在了, ,对对于于一般情况一般情况,由根的存在定理，由根的存在定理，0)( xh在在,ba上至少存在一个根上至

32、少存在一个根,*x即即)(xgx 在在 a,ba,b 上至少存在一个根上至少存在一个根. 0)()(* xxgxh,*x即即, 0)()(, 0)()( bbgbhaagah定理定理3 3 ( (压缩不动点定理或压缩映象定理压缩不动点定理或压缩映象定理) )若迭代函数若迭代函数g(xg(x) )满足满足) 3 . 3(,)()1(baxbaxg , 10)2( L使使,baxx 有有xxLxgxg )()() 4 . 3(则则；内内有有唯唯一一解解在在*0,)(1xbaxgx 从而从而，*)()(xyLxgygxy 。*xy 下证唯一性，下证唯一性，为为)(xgx 在在 a,ba,b 上另一根

33、上另一根, ,则则),(),(*xgxygy 设设*y；且且得得到到的的由由对对*10lim,)(,2xxbaxxgxbaxkkkkko 02由条件由条件( (1)1)知知kx适定的，另外适定的，另外，, 1 , 0,)()(*1* kxxLxgxgxxkkk，00* kkkxxLxx。*limxxkk ，030 kkkkkxxxxxx 11*kkkxxxxL 1*)(*xg)(kxg 又又)()(11 kkkkxgxgxx.111*kkkxxLxx )4 . 3(1 kkxxL,01xxLk .101*xxLLxxkk 04).()()(limlim*1*xgxxxgxgxxxxkkkkkk

34、 （导数的定义）（导数的定义）) 4 . 3 (xxLxgxg )()(；有有误误差差估估计计011*0111:3xxLLxxLxxkkkk )5 . 3()(lim,)(4*1*0 xgxxxxxgkkk 则则存存在在若若证明：证明：注：注：(1)(1)从定理的结论从定理的结论3 3知，知，L L越小收敛越快，越小收敛越快，L L叫做叫做渐进收敛因子渐进收敛因子。(2)(2)定理定理3 3不是必要条件不是必要条件, ,如如 1123)(2102233，在在 xxgxxxx上不满足定理上不满足定理3 3的条件（的条件（2 2），实际上），实际上0 x是解，是解， 只要只要0 x取在取在0 0附

35、近，把（附近，把（1 1，1 1）缩小使）缩小使1)( Lxg可以满足。可以满足。( (3.43.4) )式的条件较难验证，常采用导数来代替。即有推论式的条件较难验证，常采用导数来代替。即有推论1 1 ：推论推论1 1 定理定理3 3 中（中（3.43.4）可用下式替代）可用下式替代1)(max, Lxgbax)4 . 3( 证明：证明：只证只证),4 . 3()4 . 3( 因因,baxx xxgxgxg )()()( xxxgbxa )(max.xxL 思考：思考：)4 . 3( 不成立时结论是否成立不成立时结论是否成立？不一定不一定因此该推论是充分条件但不是必要条件。因此该推论是充分条件

36、但不是必要条件。 若若)4 .3( 不成立时不成立时,则则需要判断需要判断(3.4)(3.4)。注：注：定理定理4 4 （局部收敛定理）（局部收敛定理）邻邻域域满满足足的的在在不不动动点点若若 *)(xxg,* xxx有有,)()(*xxLxgxg )7.3(, 10 L则则,*0 xxx由由)(1kkxgx 产生的序列产生的序列kx收敛于收敛于,*x且有误差估计：且有误差估计：., 1 , 0,0* kxxLxxkk)8 .3(证明：证明：1*1*)()(, 1 kkkxxLxgxgxxk， LxxLxx0*1*实际计算中往往只在根实际计算中往往只在根因此有局部收敛定理因此有局部收敛定理4

37、4：邻近讨论，邻近讨论，*x， 21*2*LxxLxx，,* xxxk，又又0*1*xxLxxLxxkkk .lim*xxkk kkLxx*说明：说明：定理中的条件是充分但非必要条件。见定理定理中的条件是充分但非必要条件。见定理3 3的注（的注（2 2）。）。推论推论2 2 若若)(xg在不动点在不动点*x处可微，而且处可微，而且, 1)(* xg则存在则存在, 0 )(*0 xx当当,*0 xxx时，由时，由)(1kkxgx 产生的序列产生的序列kx收敛于收敛于.*x且且).(lim*1*xgxxxxkkk )6 . 3(证明：证明：任取任取, 0)(),1),(* xgLxgL 由由*)(

38、)(lim)(*xxxgxgxgxx 知存在知存在0 ，成立，成立,)()()(* xxxxgxxxgxg即即.,* xxxxxL*) )()()(xxxgxgxg 由定理由定理4 4得证。得证。( (3.73.7) )式的条件较难验证式的条件较难验证, ,常采用导数来代替。即有推论常采用导数来代替。即有推论2 2 ：,* xxx,)()(*xxLxgxg )7.3(, 10 L 在一定条件下，迭代是高价收敛的。有定理在一定条件下，迭代是高价收敛的。有定理5 5：定理定理5 5（高阶收敛定理）（高阶收敛定理） 若若)(xg在不动点在不动点*x邻近有直至邻近有直至m阶的阶的连续导数，且满足连续导

39、数，且满足, 0)(, 0)()(*)(*)1(* xgxgxgmm则简单迭代法：则简单迭代法：.m是局部收敛的，且收敛阶为是局部收敛的，且收敛阶为)(1kkxgx 分析：分析：已知条件有各阶导数均为已知条件有各阶导数均为0 0, ,因此用泰勒展开公式。因此用泰勒展开公式。证明：证明： 由推论由推论2，简单迭代法是局部收敛的。，简单迭代法是局部收敛的。下证收敛阶为下证收敛阶为.m2*1)(! 21)()()(xxxgxxxgxgxgxkkkk mkkmmkmxxmgxxmxg)(!)()()!1()(*)(1*)1( .)(!)(*)(*mkkmxxmgx ,!)(!)()(*)()(*1mx

40、gmgxxxxmkkmmkk .!)(!)(lim)(lim*)()(*1mxgmgxxxxmkmkmkkk 即即)9 . 3(3 3 用简单迭代法求值用简单迭代法求值 （举例）：（举例）：例例用简单迭代法求用简单迭代法求2的近似值。的近似值。解：解： 设设, 12 x则则. 1)2( xx所以所以,求求2的近似值转化为求方程的近似值转化为求方程1) 2( xx 的正根，的正根，方程：方程：,21 xx以以21 xx为迭代函数，为迭代函数， 以以00 x为初始近似得到迭代序列：为初始近似得到迭代序列：,408169,16970,7029,2912,125,52,21, 0取取408169作为作

41、为12 的近似值，得：的近似值，得：.4142157. 140816912 下证序列下证序列,52,21,0收敛于收敛于. 12 只要证只要证21 x满足定理满足定理3 3，即证即证21)( xxg在某个区间上满足定理在某个区间上满足定理3的条件。的条件。取区间为取区间为,21,0列出等价列出等价,21,021)(,21,0 xxgx取区间为取区间为,21,0,21,021)(,21,0 xxgx,21, 0, vu又又.41)2)(2(2121)()(vuvuvuvuvgug )(xg在在21, 0上满足定理上满足定理3 3。则迭代法收敛。则迭代法收敛。 即即1.41421571.41421

42、57就是就是2近似值。近似值。4 4 迭代函数迭代函数g(xg(x) )的选取方法的选取方法)(0)(xgxxf 选取的选取的g(xg(x ) )必须满足必须满足: :(1) (1) 两方程同解；两方程同解；(2) (2) 迭代序列收敛于其根。迭代序列收敛于其根。两种选两种选g(xg(x) )的方法的方法: :上上假假设设在在）,1ba)(xf 存在，存在，,ba为含根区间为含根区间, ,11Mm使得使得.,)(01111MmMxfm 设设 为正常数为正常数, , 试用形如试用形如)()(xfxxg 作迭代函数作迭代函数. . 选取选取 使得使得, 1)(1)( qxfxg )(a对于某正实数

43、对于某正实数 成立成立. .且存在常数且存在常数, 0 , 11)(11011 qmxfM ,11m 取取式式成成立立。则则)(a)(1)(1xfmxxg 故可用故可用作为迭代函数作为迭代函数. .则简单迭代法收敛于则简单迭代法收敛于0)( xf的根的根.*x特别特别, ,时时，当当,)(baCxf ,ba 使得使得,)(1Mf .)()()( fxfxxg ( (5 5 牛顿迭代法的变形牛顿迭代法的变形) )2) 2) 假设已知假设已知)(xgx *,xba上上有有根根在在, 1)( kxg但但此时此时)(xg不能作为迭代函数不能作为迭代函数, ,若若)(xg的反函数的反函数)(xx 容易求

44、出容易求出, ,可用可用)( x 作为迭代函数作为迭代函数. .?因为因为)(xgx 与与)(xx 同根同根. .此时可用此时可用)(1kkxx 求解求解)(xgx 的根的根,*x且该迭代法收敛于且该迭代法收敛于.*x例例 求求01)(3 xxxf在在2 , 1 上的根上的根. .解解: :, 05) 1() 2() 1 ( ff)(xf在在2 , 1 上有根上有根. .方程方程1)(3 xxgx与与0)( xf等价等价. .但但,2 , 1 , 3)( xxg 故不能用故不能用1)(3 xxg作为迭代函数作为迭代函数. .然而然而)(xg的反函数的反函数31)1()( xx 的导数的导数32

45、)1(31)( xx 在在2 , 1 上满足上满足, 141431)(03 x 所以可用所以可用)(x 作迭代函数求作迭代函数求0)( xf的根的根. .5 5 迭代结束条件迭代结束条件1)1)根据实际问题需要定出解的误差界根据实际问题需要定出解的误差界, 由由 01*1xxLLxxkk定出迭代次数定出迭代次数.k2)2)用相邻两次近似值有多少位有效数字相同用相邻两次近似值有多少位有效数字相同, ,判断是否停机判断是否停机. .注注: : (1) (1) 编程序时编程序时, ,要注意结束条件要注意结束条件. .(2)(2)定出的定出的k不准确不准确, ,因为计算中有舍入误差，故使因为计算中有舍

46、入误差，故使迭代次数迭代次数比计算的比计算的 要大。要大。k 1.1.理解简单迭代法的理解简单迭代法的思想方法，几何意义，压缩不动点定理。思想方法，几何意义，压缩不动点定理。 2. 掌握简单迭代法的收敛掌握简单迭代法的收敛( (局部局部) )定理定理（定理证明，会判断简单（定理证明，会判断简单迭代法是否收敛）迭代法是否收敛）。, 1 , 0),(1 kxgxkk(1)(1) 将将f(xf(x)=0)=0化为等价方程化为等价方程；)(xgx *x若若kx)( xg收敛于收敛于且且连续连续, ,则则*x是是f(xf(x)=0)=0的根的根。1 1 简单迭代法的基本思想方法：简单迭代法的基本思想方法

47、：出发出发, ,作序列作序列:kx0 x(2) 从某从某解解x=x=g(xg(x) )的简单迭代法的简单迭代法 迭代公式迭代公式2. 2. 收敛性收敛性（定理（定理3及推论及推论1）)(lim*1*xgxxxxkkk 则则有有；,)()1(baxbaxg ,10)2( L使使,baxx 有有xxLxgxg )()(，1)(max, Lxgbax或或若若有有对对迭迭代代)(xgx 3 3、局部收敛性（定理、局部收敛性（定理4 4及推论及推论2 ）,* xxx有有,)()(*xxLxgxg , 10 L4 4、高阶收敛性（定理、高阶收敛性（定理5 5）)(lim*1*xgxxxxkkk 则则有有,

48、 1)(* xg或或, 0)(, 0)()(*)(*)1(* xgxgxgmm若若则收敛阶为则收敛阶为m。迭代法的加速法迭代法的加速法4.1 4.1 AitkenAitken( (埃特金埃特金) )加速方法加速方法假设简单迭代序列假设简单迭代序列kx,*x线性收敛于线性收敛于即即10,lim*1 ccxxxxkkk)1 .4( (加速收敛技巧加速收敛技巧) )设设,) 1*xxk ( (若等号成立若等号成立, ,则则,*xxk 是精确解是精确解) ), 1 , 0, k., 1 , 0, 02) 212 kxxxkkk( (若等号成立若等号成立, ,则则kx不收敛不收敛. .因为因为kkkxx

49、x 122则则 如图示如图示: : ,112kkkkxxxx kx不收敛于不收敛于 ) ) .*x*x12 kkxx21 kkxxkxx, 0)()(112 kkkkxxxx记序列记序列kx的埃特金加速序列为的埃特金加速序列为.0 kkx., 1 , 0,)(2)(221221 kxxxxxxxxxxkkkkkkkkkk)2 .4(埃特金加速序列埃特金加速序列 0kkx比原简单序列比原简单序列kx更快地收敛于更快地收敛于.*x二阶差分算子二阶差分算子定理定理6 6: : 若序列若序列 线性收敛于线性收敛于kx*x10,lim*1 ccxxxxkkk：.*x则则 的埃特金加速序列的埃特金加速序列

50、 比原简单序列比原简单序列 更快地收敛于更快地收敛于 0kkxkx 0kkx即即)3 . 4(. 0lim* xxxxkkk分析分析: : 该定理的证明用数学分析中证明极限的技巧该定理的证明用数学分析中证明极限的技巧. .证明证明: :,*xxekk 记记则有则有,lim1ceekkk .lim22ceekkk 由由)2.4(得得*1221*2)(xxxxxxxxxkkkkkkk .2)(1221kkkkkkeeeeee 12) 1(11221* kkkkkkkkeeeeeexxxx则则1122kkkkkkeeeeee ，即，即. 0lim* xxxxkkk# # kccc. 012) 1(1

51、22kkkkkkkxxxxxxx 12212)()2 . 4(*xx *2xxx 几何意义几何意义: :设初值设初值,0 x由迭代法由迭代法: :),(),(1201xgxxgx 由三角形相似由三角形相似, ,得得: :,10301213xxxxxxxx 0122120302xxxxxxxx .2)(0122010 xxxxxx xy xy0*x0 x2x1x),(211xxp),(100 xxp3x10 xx 30 xx 13xx 12xx 过两点过两点),(),(211100 xxpxxp作直线作直线 , ,说明说明:该表达式正是埃特金加速收敛的公式该表达式正是埃特金加速收敛的公式, ,0

52、3xx 比比2x更接近于更接近于.*x从图中可以看出从图中可以看出(1)(1)这里的这里的3x并不是简单收敛列并不是简单收敛列.3x0kkx中的中的(2)(2)对某些不收敛的情况对某些不收敛的情况, ,用埃特金方法用埃特金方法“加速加速”也有可能收敛也有可能收敛. .xy 的交点为的交点为),(33yx与与为为埃埃特特金金序序列列的的元元素素。则则03xx 4.2 4.2 SteffensonSteffenson迭代方法迭代方法 在埃特金加速法中在埃特金加速法中, , 只要有三个相邻点就可以进行加速只要有三个相邻点就可以进行加速, ,把把简单迭代与埃特金加速方法结合起来可建立简单迭代与埃特金加

53、速方法结合起来可建立SteffensoSteffenso迭代方法迭代方法. .设设g(x)g(x)为迭代函数为迭代函数, ,0, x为初始值为初始值, ,0kkx为迭代序列为迭代序列, ,则迭代则迭代过程如下过程如下: :)()(kkkkygzxgy , 1 , 0,)2()(21 kxyzxyxxkkkkkkk )4 .4(并有局部收敛定理。并有局部收敛定理。定理定理8 8 若若*x是是g(x)g(x)的不动点的不动点,g(x),g(x)一次连续可微一次连续可微, , 1 , 0)( xg存在存在, ,则存在则存在, 0只要只要,*0 xx由由SteffensoSteffenso方法产生的方

54、法产生的)(*xg kx收敛于收敛于,*x而且收敛阶至少为而且收敛阶至少为2 2。迭代序列迭代序列从例从例7 7、8 8可以看出收敛速度确实快。可以看出收敛速度确实快。优点：优点：收敛速度快。收敛速度快。缺点：缺点：计算量大，一步计算量大，一步SteffensoSteffenso方法迭代的计算量相当于两方法迭代的计算量相当于两步简单迭代。步简单迭代。理解简单迭代法的理解简单迭代法的加速收敛方法。加速收敛方法。5 5 解解f(x)=0f(x)=0的的NewtonNewton迭代法迭代法Newton-Newton-RaphsonRaphson法是广泛应用的高效计算方法。法是广泛应用的高效计算方法。

55、基本思想基本思想: : 非线性方程局部非线性方程局部线性化线性化 ( (化繁为简化繁为简) )特点特点: : 单根附近具有较高的收敛速度单根附近具有较高的收敛速度5.1 Newton5.1 Newton迭代公式迭代公式 (Newton(Newton法或切线法法或切线法) )1 1 公式公式: :设非线性方程设非线性方程0)( xf)1.5(,其精确解或真解为其精确解或真解为.*xf(xf(x) )二次连续可导二次连续可导, ,kx是是(5.1)(5.1)的第的第k k次近似解。次近似解。的泰勒展开式为的泰勒展开式为: :2)(! 2)()()()(kkkkxxfxxxfxfxf 其中其中 介于

56、介于x与与kx之间。之间。)()(kkkxxxfxfy 是是)( xf在点在点kx的线性展开的线性展开 ( (线性主部线性主部) )， 用其近似用其近似f(x),f(x),即有即有并设并设则则f(x)f(x)在点在点kx0)()()( kkkxxxfxfxf)()(kkkxfxfxx )0)( kxfNewtonNewton迭代公式迭代公式: :)()(1kkkkxfxfxx )3.5(说明说明: : 公式推导过程中是用公式推导过程中是用f(x)f(x)的泰勒展开式的的泰勒展开式的线性线性部分部分作作为为f(xf(x) )的近似值的近似值, ,因此说因此说NewtonNewton法是一个法是一

57、个逐次线性化逐次线性化方法。方法。把把)()(kkkxfxfxx 作为第作为第K+1K+1次近似解次近似解，即得即得0)()()( kkkxxxfxfxf)()(kkkxfxfxx )0)( kxf)0)( kxf2 2 几何意义几何意义设曲线设曲线y =f(x)y =f(x)的图象如图示的图象如图示, ,kx0)( xf是是的的k k次近似次近似, ,曲线曲线 y=y=f(xf(x) )上对上对应的点为应的点为),(,(kkxfx过该点作过该点作曲线曲线y=f(x)的切线的切线kL交交x x轴于点轴于点,1 kx:kL用用)2 . 5()()(kkkxxxfxfy 近似曲线近似曲线y=f(x

58、),y=f(x), 则则kL与与x x轴的交点轴的交点1 kx作为作为f(x)=0f(x)=0的第的第k+1k+1次近似解。次近似解。即由即由(5.2)(5.2)式令式令y=0y=0得得)()(1kkkkxfxfxx )0)( kxf该式就是该式就是NewtonNewton法的迭代公式法的迭代公式, ,因此因此NewtonNewton法也称为法也称为切线法切线法。xyo)( xfy kL*x)(,(kkxfxkx1 kx3 3 牛顿法与简单迭代法、正割法的关系牛顿法与简单迭代法、正割法的关系 若取若取,)()()(xfxfxxg 0)( xf)4 .5( 若若11)()()( kkkkkxxx

59、fxfxf(差商近似代替微商）差商近似代替微商）)()(1kkkkxfxfxx )(1kkxgx )0)( xf即即则则简单迭代法简单迭代法 (迭代函数为迭代函数为g(x)NewtonNewton法法则则正割法正割法NewtonNewton法法)()(1kkkkxfxfxx 即即)()()()(111 kkkkkkkxxxfxfxfxx因此正割法也称为离散的因此正割法也称为离散的NewtonNewton法，法， 或者称为或者称为NewtonNewton法的法的改进。改进。牛顿法也存在收敛问题，并不是对牛顿法也存在收敛问题，并不是对所有函数牛顿法都收敛所有函数牛顿法都收敛。因此有收敛因此有收敛定

60、理。定理。xyo*x)( xfy 1kxkx2kx5.2 Newton5.2 Newton法收敛定理法收敛定理1 1 收敛定理收敛定理定理定理9 9 （NewtonNewton法局部超线性收敛性）法局部超线性收敛性）如果如果f(x)f(x)在解在解*x邻近连续邻近连续 可导可导, ,且且, 0)(* xf则存在则存在,0 只要只要,*0 xxNewtonNewton序列序列超线性超线性收敛于收敛于,*x即即. 0lim*1 xxxxkkk)5.5(牛顿法迭代会越跑越远。牛顿法迭代会越跑越远。 如图示如图示: :分析：分析：NewtonNewton迭代公式为迭代公式为,)()(1kkkkxfxf