《线性代数》课件D-3牛顿法与弦截法.ppt

1、2*0()0 a,b,()a,b()0.xf xf xfxx 设设是是方方程程 在在隔隔根根区区间间内内的的根根在在内内可可导导且且取取定定初初值值00000(,()()()()xf xyf xfxxx 以以过过点点的的切切线线方方程程 0100()(),0,.()f xyf xyxxfx 代代替替令令 得得以以x1作为根作为根x*的第一个近似值。又过曲线的第一个近似值。又过曲线 y=f(x)上的点上的点(x1,f(x1)作切线，得它与作切线，得它与x轴轴34n+1()(n=0,1,2,)(3.3.1)()nnnf xxxfx 的交点的横坐标的交点的横坐标x2为为1211().()f xxxf

2、x 它又它又可可作为根作为根x*的一个近似值。继续下去得的一个近似值。继续下去得-牛顿迭代法。也是简单迭代法牛顿迭代法。也是简单迭代法()(),()0().()f xxxf xxxfx 1(),nnxx 5*0*()()0,(1)()(2)()0,|,.1kxf xf xxxfxxSxxxxSxx 牛牛顿顿迭迭代代法法的的局局部部收收敛敛定定理理设设是是方方程程 的的根根 若若 函函数数在在 的的邻邻域域内内具具有有连连续续的的二二阶阶导导数数;在在 的的邻邻域域内内则则存存在在 的的一一个个邻邻域域对对任任意意初初值值,由由牛牛顿顿迭迭代代法法(3.3.1)(3.3.1)产产生生的的数数列列

3、收收敛敛于于方方程程的的根根定定理理6*000*()()0,(1),(),()(2),()()0.2nxf xa bxa bfxfxxa bf xfxxx 非非局局部部收收敛敛定定理理 设设是是方方程程 在在隔隔根根区区间间内内的的根根 若若 对对于于连连续续且且不不变变号号;选选取取初初始始值值使使,则则由由牛牛顿顿迭迭代代公公式式(3.3.1)(3.3.1)产产生生的的数数列列收收敛敛于于方方程程的的根根定定理理证证 定理的几何解释见图定理的几何解释见图3-6.满足定理条件满足定理条件（1）的情况有）的情况有4种。取初值种。取初值x0为为a或或b.下面先推导一个公式。下面先推导一个公式。7

4、公式公式 称为称为 的的 n 阶泰勒公式阶泰勒公式.)(xf公式公式 称为称为n 阶泰勒公式的阶泰勒公式的拉格朗日余项拉格朗日余项.泰勒中值定理泰勒中值定理 （高等数学（高等数学3.3节节）内具有的某开区间在包含若),()(0baxxf1n直到阶的阶的导数导数,),(bax时时,有有)(xf)(0 xf)(00 xxxf200)(!2)(xxxf nnxxnxf)(!)(00)()(xRn其中其中10)1()(!)1()()(nnnxxnfxR则当则当)0(之间与在xx81(),()()kkkkkf xnkxxf xxxfx 时时将将 在在用用泰泰勒勒公公式式展展开开到到一一阶阶，得得2()(

5、)()()()(),2!kkkkkff xf xfxxxxx *kkxxxx 其其中中在在 与与之之间间。令令得得*2()()()()()()0.2!kkkkkff xf xfxxxxx *2()()(),()2!()kkkkkkf xfxxxxfxfx 解解得得 9*21()()(3.3.2)2!()kkkkfxxxxfx 即即 下面以图下面以图3-6的情形进行证明的情形进行证明.1()0,()0;2fxfx设设条条件件（）：由由条条件件（）*00()0();()0.f xf xfxxx 从从而而由由知知*(i)(ii)nnxxx 用用数数学学归归纳纳法法证证；证证单单调调递递增增；(iii

6、),(3.3.1)nxx由由单单调调有有界界收收敛敛准准则则有有极极限限在在 *0,lim.nnfxxxx两两边边取取极极限限，得得1011 10 4.1xxe 用用牛牛顿顿法法求求方方程程 在在隔隔根根区区间间0,10,1内内的的根根,要要求求精精确确到到小小数数点点后后第第 位位例例 ()1,()(1)0,()(2)0.xxxf xxefxxefxxe设设 则则在在区区间间解解0,10,1内内000.8,()0.11270.xf x取取则则2由由定定理理，牛牛顿顿迭迭代代法法收收敛敛，迭迭代代公公式式：11,(1)ennxnnnxnx exxx 21+1 ,(1)ennxnnxnx exx

7、 即即4110,1,2,.|102nnnxx 当当 时时终终止止。12000010110101121111(1),(),();()(2),(),();()(3)|()|,(4)(4)()0,(xf xfxf xxxf xfxfxxxf xxfxxf x 准准备备:取取定定初初值值计计算算迭迭代代:计计算算控控制制:如如果果|或或则则终终止止迭迭代代,即即为为所所求求的的根根；否否则则转转；修修改改:如如果果迭迭代代次次数数超超过过预预 牛牛先先指指定定的的次次数数N N，或或者者 ，则则方方顿顿迭迭代代法法的的计计法法失失败败；否否则则以以算算步步骤骤1000),(),(),()(2).fxx

8、f xfx代代替替，转转继继续续迭迭代代134130 ()101 4.2f xxxx 用用牛牛顿顿法法求求方方程程 在在 附附近近的的实实根根,要要求求精精确确到到小小数数点点后后第第 位位例例 (30).C C 用用牛牛顿顿法法建建立立计计算算近近似似值值的的迭迭代代公公式式例例02000()0()()()(3.3.3)2fxfxf xfx 只只要要 ，也也可可以以选选取取满满足足如如下下条条件件的的初初值值：注注 14*1 ,1,|lim,|,.101,.2,1,1nnnnpnnnnnnxxexxpCeCexpCppxpxpx 设设数数列列收收敛敛于于令令误误差差如如果果存存在在某某个个实

9、实数数及及正正常常数数使使则则称称数数列列为为也也称称相相应应的的迭迭代代法法是是当当定定义义阶阶收收敛敛阶阶方方法法线线性性收收敛敛平平方方收收敛敛(或或二二阶阶且且时时 称称数数列列为为当当时时 称称数数列列为为当当时时收收敛敛称称数数).).列列为为超超线线性性.收收敛敛151*(1)*()*01 (58)()(0,1,2,),()(1)()1;(2)()()()0,()0;(,),(,),kkppkxxkxxxxxxxxU xxU xx 上上机机指指导导页页对对于于迭迭代代过过程程若若迭迭代代函函数数在在所所求求根根 的的附附近近有有连连续续的的p p阶阶导导数数,且且满满足足条条高高

10、阶阶收收件件 且且则则必必存存在在 的的某某个个邻邻域域使使对对任任意意初初始始值值迭迭代代过过程程敛敛定定理理()(0,1,2,).kxk 为为p p阶阶收收敛敛16*1*000*(1)(),()0()1,()(2)()0,(),(),()()0.3(3)(nnxxxxxSxSxxxf xa bxa bfxfxxa bf xfxxf 设设是是方方程程的的根根在在 的的某某一一邻邻域域 连连续续,且且 则则在在 内内的的迭迭代代法法线线性性收收敛敛.设设是是方方程程 在在隔隔根根区区间间内内的的根根 若若对对于于连连续续且且不不变变号号,且且初初值值使使,则则牛牛顿顿迭迭代代法法平平方方收收敛

11、敛 设设是是方方程程 定定理理)0 m(m2),.()x 的的重重根根则则牛牛顿顿迭迭代代法法仅仅为为线线性性收收敛敛上上机机指指导导7474页页17牛顿迭代法缺点是：需要计算分母上的牛顿迭代法缺点是：需要计算分母上的 f(x).设设a,b是一个隔根区间。连接曲线是一个隔根区间。连接曲线 y=f(x)上的两点上的两点A,B,令令 x0=a,x1=b,则弦则弦AB的方程的方程为为101010()()()().f xf xyf xxxxx 令令 y=0,得弦得弦AB与与x轴的交点的横坐标轴的交点的横坐标x2为为181211010()().()()f xxxxxf xf x 19以以x2作为根作为根

12、x*的一个近似值。又连接曲线的一个近似值。又连接曲线 y=f(x)上的两点上的两点(x1,f(x1),(x2,f(x2)作弦，作弦，得它与得它与x轴的交点的横坐标轴的交点的横坐标x3为为2322121()().()()f xxxxxf xf x 则则x3又可作为根又可作为根x*的一个近似值。继续下去得的一个近似值。继续下去得 20111()()(n=1,2,).()()nnnnnnnf xxxxxf xf x *01*()|()0,.(15)/21.1618.nf xxSxxxxSfxSSxxxxp 若若在在根根 的的某某个个邻邻域域 内内有有二二阶阶连连续续导导数数,且且对对任任意意,有有 则则当当 邻邻域域充充分分小小时时 对对 邻邻域域内内任任意意的的由由弦弦截截法法的的迭迭代代公公式式(3.4.1)(3.4.1)得得到到的的近近似似序序列列收收敛敛于于方方程程的的根根并并可可证证明明弦弦截截法法是是按按阶阶理理收收敛敛的的定定21