非线性方程求根(1)

1、整理ppt第七章 非线性方程求根1110 ()0 ()0 , 1: ()sin0nnnnxfxffxnfxxa xaxa xae求 解 非 线 性 方 程是 非 线 性 函 数 ， 例 ： 代 数 方 程。 例超 越 方 程 本章介绍一些求方程实根的近似值的有效方法，一般来说, 使用这些方法求非线性方程的实根可以分两步进行.第一步是确定某根的所在区间a,b，或给出根的近似值x0.第二步是对方程的根进一步精确化,得到满足精度要求的近似根.整理ppt ( ) , , ( )( )0 ( )0, ( )0f xa ba bf af bf af b设在上连续且有且仅有一个根又。则可用对分法：不妨设.

2、,2 2 02 , 2 02 ,11111aababbbbaabafbaxbaf反之，令，否则：若输出根若）,b ,a),ba2211 1 2）的计算，并产生区间重复对.2 02 ),3baxbafiiii则得到根，若1. 非线性方程实根的对分法(二分法)整理ppt二分法的收敛性 11 , ,nna ba ba b二分法产生一个有根区间：11, 11 ()()22nnnnnnnbaa bbaba区间长度：，足够大时，取近似值当2 baxnnnn1 2nnbaxx误 差 ：计 算 简 便 ， 容 易 估 计 误 差 ， 但 收 敛 较 慢 。a x* x0 b( )f x a1 b1整理ppt以

3、上公式可用于估计对分次数k.分析以上过程不难知道，对分法的收敛速度与公比为1/2的等比级数相同.由于210=1024，可知大约对分10次，近似根的精度可提高三位小数位.对分法的收敛速度较慢，它常用来试探实根的分布区间，或求根的近似值.例例1 1 求求x3-3x+1=0的实根分布情况，并求的实根分布情况，并求0,10,1中的实根近中的实根近似值，精确到三位小数似值，精确到三位小数. .整理ppt解解: : 从从-4,4-4,4区间以步长为区间以步长为1 1计算计算f f( (x x)=)=x x3 3-3-3x x+1+1的函数值，列的函数值，列如下表如下表x-4-4-3-3-2-2-1-10

4、01 12 23 34 4f(x) -51-51 -17-17-1-13 31 1-1-13 319195353表表7-17-1可见，在可见，在(-2,-1)(-2,-1)区间、区间、(0,1)(0,1)区间、区间、(1,2)(1,2)区间各有一实根，区间各有一实根，下面求下面求(0,1)(0,1)区间上的实根区间上的实根, ,按二分法按二分法. .可得可得 x 0.347167968, 0.3474121090.347167968, 0.347412109若取若取 =0.0005, =0.0005, 当当k =13=13时时, ,bk -ak=0.0002441410.0005, =0.00

5、02441410.0005, 此时过程结束此时过程结束, , 取取 xk=(0.347167968+0.347412109)/2=0.347290038=(0.347167968+0.347412109)/2=0.347290038 0.3470.347整理ppt可见，对分法的优点是对函数的要求低可见，对分法的优点是对函数的要求低(只要求只要求f(x)连续连续)，方法，方法简便、可靠，程序设计容易，事先估计计算次数容易，收敛速简便、可靠，程序设计容易，事先估计计算次数容易，收敛速度恒定；缺点是不能求出偶重根，收敛速度较慢度恒定；缺点是不能求出偶重根，收敛速度较慢.取适当的步长取适当的步长h =

6、(b-a)/m 逐一检验小区间逐一检验小区间a+kh,a+(k+1)h,(k=0,1,2,m-1) 的两端函数值是否异号，的两端函数值是否异号，若异号，则按以上二分法求出其中的根；若同号则不作求根而若异号，则按以上二分法求出其中的根；若同号则不作求根而转入检查下一个区间，只要转入检查下一个区间，只要h选得较小，则可求出本区间内的选得较小，则可求出本区间内的所有奇重实根所有奇重实根(包括单实根包括单实根).h选得过大，可能漏掉某些根；选得过大，可能漏掉某些根； h选得过小，则计算量增大选得过小，则计算量增大.对分法的思想方法还可用于搜索一个较大区间对分法的思想方法还可用于搜索一个较大区间a,b内

7、实根的分内实根的分布情况布情况(不包括偶重实根不包括偶重实根)，实际的作法是：，实际的作法是：整理ppt2. 迭代法及其收敛性 连续。且改写方程： )(0)( xxxfxxxnnn )( 1，得到序列建立迭代格式：1 (0 )(limlimlimnnnnnnnfxxxxx则 若收敛必收敛到）的根：* * ()()0limnnnxxxf xxx 若收敛，即，则：也称作不动点迭代法 P265整理ppt 迭代过程的几何表示 ) :)(xyxyxx交点即真根。( )yxy xO x* x2 x1 x0 xy0P1Q1P2P*P2Q整理ppt3*0331k ( )10 1.5. 1 1 1(0,1,2)

8、 k 0 1 2 7 8 x 1.51.35721 1.330861.324kkf xxxxxxxxxk 例：求方程 在附近的根解：（ ） 将方程改写为由此建立迭代公式331k721.32472 2 11.k 0 1 2 x1.52.37512.39 kkxxxx迭代收敛。（ ） 若将方程改写为建立迭代公式 迭代不收敛。P266表7-2整理ppt*1*. ( ) ,1 ,( );(2)01, , ( )()( ) , , ()(0,1,) nnxa bxa baxbLx ya bxyL xyxxa bxa bxxnx0定 理设 函 数在 区 间上 满 足 条 件（ ） 对 任 意， 都 有存

9、在 常 数使 得 对 一 切都 有则 方 程在内 有 唯 一 的 根且 对 任 何初 值 x迭 代 序 列均 收 敛 于， 并 有*10 x1nnLxxxL 不动点的存在性与迭代法的收敛性 （ P267 定理1，）连续，且满足整理ppt 2( ) , ( )( ),( ) , ( )( )0,( )( )0 , 0,( ) , xa bxxxxa baaabbba bxxa b 证：由条件（ ）知在上连续。令则在上连续，且故存在，使得 （ ）即（ ）,所以方程在内有根。*12*12121212 ( ) , ,2()()xxa bxxxxxxL xxxx假设方程在内有两个根由条件（ ），有导出矛

10、盾，唯一性得证。整理ppt0*11*0*0*1111 , ,()() 01, limx , , ()()nnnnnnnnkkkkkkkxa bxxxxL xxxxLxxLxxa bxxkxxxxL xxLx 对 任 意由 迭 代 公 式 有依 此 类 推 ， 得因 所 以即 对 任 意 初 值迭 代 序 列均 收敛 到 方 程 的 根。类 似 地 ， 对 任 意 正 整 数,有0 x整理ppt112112101010121010*10, ,(1)1 1, 1 npnnpnpnpnpnnnpnpnnpppnnnn pLpLxLxxxxxxxxxxxxxxLLLxxL LLLxxLxxx 于是，对

11、任意正整数有令得整理ppt*1*. ( ) , 1 , ( );(2)01, , , ( )( ) , , , , ()(0,1,) xnnxa bxa baxbLxa bxLxxa bxa bxxnx0定理 设函数在区间上满足条件（ ）对任意，都有存在常数使得对一切都有则方程在内有唯一的根且对任何初值x迭代序列均收敛于，并有101nnLxxxL改变定理条件（）可得以下结论整理ppt , , , ( )( )( )()( )( )( )()( )2x ya bx yxyxyxyxyL xyx 证：设为上任意两点，由微分中值定理，在之间至少存在一点 ，使得即满足上一定理的条件（ ），故结论成立。

12、整理ppt*10 x1( )( ) , nnLxxxLLxxa b误差估计式表明，常数 越小，简单迭代法收敛越快。因而构造迭代函数的原则是使在有根区间上有尽可能小的上界。11211211111111*, 1 npnnpnpnpnpnnppnnnnnnnnnpLpLxxxxxxxxLxxxxLxxxxxx 对任意正整数 有）令得可通过检查来判断迭代过程应否终止。（整理ppt21112 ( )10 (1.5)0.250, (2)10 1.5,2 11( ) 1.51.51( )212111( )3.162212 2.51(2) 1( ) f xxxffxxxxxxxxx 例：用简单迭代法求方程的根

13、。解：因为有根区间。（ ）因且2222011 1.51( )1221.5111 ( )1.52.25 1.5,2,xxxx 因且根据定理，任取由这两种等价方程所构造的简单迭代方法都收敛，且第一种所产生的迭代序列收敛较快。整理ppt 局部收敛性 (P269)*01* ()(,)()()1, () (0,1, 2,).nnxxO xxxxxxxxxxnx 定 理 ： 如 果 函 数在的 一 邻 域内 连 续 可 微 ，为 方 程的 根 ， 且则 存 在 正 数使 得 对 任 意迭 代 序 列收 敛 于设有不动点，如存在的某个领域对任意的迭代产生的序列且收敛到，则称迭代法是局部收敛的)(x*x*x*

14、:xxRRx 0)(1kkxx*xkx定义定理3局部收敛 *x整理ppt*1 ( )(,)( )1,1, ( )1(), ( )( )()( ),()nnxO xxLxxxxLxxxxxxL xxxxxxxx证 ： 因在内 连 续 ， 且故 存在 正 数使 得 对， 有另 一 方 面 ， 由又 有即。 由 上 面 定 理 知 ， 迭 代 序 列收 敛 于。 实际用迭代法计算时，先用对分区间法求较好的初值，然后再进行迭代。整理ppt1*1()( ) (0112kkkkkpkxxxxxexxkeCCepppp 定义：设迭代过程收敛于方程的根,如果迭代误差当时成立下列渐进关系式为常数）则称该迭代过程

15、是 阶收敛的。为线性收敛，为超线性收敛，为平方收敛。迭代法收敛速度定义(P271)整理ppt()1*(1)*()* (),( ) ()()()0;()0pkkppxxxxxxxxxp定理：对于迭代过程如果在所求根的邻近连续，并且则该迭代过程在点邻近是 阶收敛的。*1*()*()()*11()01,()()( ) ()()()!( )()()!kkkppkkpppkkkpkxxxxxxxxxpexxxxxpep证：由于故具有局部收敛性。将在根处展开，由条件有定理4:整理ppt 3.迭代收敛的加速方法*01021*1010*2121*1021*12 () () ()()()()()()()()(

16、),()()xxxxxxxxxxxxxxxxxxxLxxL xxxxL xxxxxx设是 根的 某 个 预 测 值 ， 通 过 两 次 迭 代 校 正有 由 微 分 中 值 定 理 ， 有假 定改 变 不 大 ， 近 似 地 取 某 个 近 似 值则 由*2*0212*1012()2xxxxxxxxxxx此 种 加 速 需 用 两 次 迭 代 值 进 行 加 工 。埃特金(Aitken)方法(P273)整理ppt1112111111 () ()() 2kkkkkkkkkkkxxxxxxxxxxx如 果 将 一 次 改 进 值 作 为 一 步 ，则 计 算 公 式 如 下 ：校 正再 校 正改

17、进可以证明0lim*1xxxxkkk表明kxkx即为斯蒂芬森(Steffensen)迭代法 (P273)的收敛速度比的收敛速度快, 且为2阶收敛的整理ppt020000( )0 02f x xTaylor()f(x)f() (x-)()!fxxfxxxx在真根附近点展开成级数：4. 牛顿(Newton)法 非线性问题的最简单解法是线性近似. 将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是Newton法的基本思想整理ppt)0( 000011)()()f(xxxfxfxxx：作为近似根解出 , 2 , 1 , 0 ),()( Newton 1nfxfxxxnnnn法：依次产生迭

18、代格式，称00 000 xx)(xf)f(x:f(x)取线性部分近似代替整理ppt Newton 法的几何解释 )x(f)x(fxxx)y01011 0( x：为第二个近似根轴交点与000000 ,() ( ) ()()()ff xyfxxxxfxxx当在取后（在真根附近），过作的切线，则切线方程：)(xfy 0 x1x2x*x故也称切线法整理ppt 12* ( ) , ( )0,() ()( ) ( ) ( )( )( ) ( ) ( )( )(kkkkxxa bxfxxxfxfxxxfxfx fxxfxxfxfx迭代过程的收敛速度依赖于迭代函数的选取。如果当时则该迭代过程只可能是线性收敛。

19、 对牛顿公式其迭代函数为由于假定是的一个单根，即*)0,()0,()0,fxxx则由上式知由上述定理知，牛顿法在根的邻近至少是平方收敛的。4整理ppt10 10. ( ) 1,( )(1)( ) ( )( )1 10.5kxxxxxkkkkxef xxefxexf xxexxxfxxxexxxx例：用牛顿法解方程解：牛顿法迭代函数为牛顿公式为可先用二分法或经验确定迭代初值，再按牛顿公式进行迭代。 Newton法具有收敛快，稳定性好，精度高等优点，是求解非 线性方程的有效方法之一。但它每次迭代均需计算函数值与 导数值，故计算量较大。而且当导数值提供有困难时， Newton法无法进行。(见P277

20、表7-5)整理ppt牛顿法应用举例21 01 ().2kkkCxCCCxxx对于给定正数，应用牛顿法解二次方程即导出求开方值的计算程序02211221010202000 11 () ()22. ,2.1 0,1. kkkkkkkkkkkkkkkkkxxCxCxCxCxxxCxCxCxCxCxCxCxCxCqqxCCxCqxqkxC 现证此迭代公式对于初值都是收敛的。由迭代公式得记对任意总有，故当时，整理ppt注 牛顿法每次计算)()(kkxfxf计算量较大1。简化牛顿法（平行弦法）0)(1CxCfxxkkk若1)(1)(xfCx即2)(0 xfC在根x*附近成立，则迭代为局部收敛。P2802。

21、牛顿下山法 即在牛顿迭代法的基础上附加一个条件)()(1kkxfxf计算公式：)()(1kkkkxfxfxxkkkxxx)1 (11)()(1kkkkxfxfxx即整理ppt5.弦截法与抛物线法11111 (),(),() ,( )0(),(),(),( ),( )0( )0 kkkkkkrkkkrrrkkf xf xfxxxxf xf xf xf xpxpxf xxx基本思想：利用一些函数值来回避导数值的计算。设是的一组近似根，利用函数值构造插值多项式并适当选取的一个根作为的新的近似根，这就确定了一个迭代过程，记迭代函数为 ：1(,). 12kkkrxxxrr当时为弦截法，当时为抛物线法。整

22、理ppt一、弦截法 （P283）111111111111 ,( )0(),()( )( )0( )0.()() ( )()()() ().()()()kkkkkkkkkkkkkkkkkkkkkxxf xf xf xpxpxf xxf xf xpxf xxxxxf xxxxxf xf xf xxxf设是的近似根，利用构造一次插值多项式，并用的根作为的新的近似根由此迭代公式可看作牛顿公式11()()()( )kkkkkxf xf xfxxx中的导数用差商取代的结果。整理ppt弦截法的几何表示x0Xx*x1 x2 x3Y f(x)0P0P2 P111011 ,.,kkkkkxxxxxxx弦截法在求时

23、要用到前面两步的结果需两个初值，而牛顿切线法在计算时，只用到前一步的值。整理ppt弦截法收敛性定理 （P285）*01111* ( ):( )0,() ().()()151.618.2kkkkkkkf xxxxxfxxxf xxxxxf xf xpx定理：假设在根 的邻域内具有二阶连续导数，且对任意有又初值那么当邻域 充分小时，弦截法将按阶收敛到根整理ppt11*11111*11111.11*1 ,()0( ),() ( )( )()()2()()()()()22 ( )0()kkkkkkkkkkkkxxxfxpxxxffxpxxxxxffpxxxxxe expxpx 证：用数学归纳法证明迭代

24、值全属于。首先证明当时必属于。设，是以为节点的插值多项式。由又由于是的根，故有*11111*11211()()( )()()()()().kkkkkkkkpxpxpxxfxfxxxfexx 整理ppt1112121112111101().2(),m ax(),. .2 m in(),1, . . ,kkkkkkkxxkkkkkkfee efxxxxfxMfxMxxeMeeMxxx 对 上 两 个 式 子 联 立由 于故 当时记选 取 邻 域充 分 小 以 保 证则 当与属 于时因由 数 学 归 纳 法 知kx一 切全 属 于整理ppt23224111223*111112* 1 ()0, ()

25、2()().2()1kkkkkkkkkkkkkkkkkeM eeMeeMeeeMMkekfee eeMeeffxMfxeM 由递推不等式故当时有收敛性得证。当 充分大时，由这里 令11.*,kzkkkdzzz则有差分方程整理ppt111 11 111121211221212111* 101.618,0.618; , ,111 () kkkkkkkkkkkkkzcckzzzzzccc ckzcedddMMM 方程是一差分方程，考虑的特解，其特征方程 为故差分方程的通解为（为任意常数） 由于当 充分大时故 而1 1111*11*1*111 1 1.618.kkzckkkkkeddMMeeMeMMe

26、，故有（）此说明弦截法收敛的阶整理ppt 迭代法加速（埃特金方法）*01021*1010*2121*1021*12 () () ()()()()()()()()( ),()()xxxxxxxxxxxxxxxxxxxLxxL xxxxL xxxxxx 设是根的某个预测值，通过两次迭代校正有 由微分中值定理，有假定改变不大，近似地取某个近似值则由*2*0212*1012()2xxxxxxxxxxx此种加速需用两次迭代值进行加工。整理ppt用弦截法给出埃特金算法的几何解释( ) xx用弦截法讨论形如得方程，给出埃特金算法的几何解释。 yx( )yx*P3P2P0P1P*x2x1x3x0 x33213

27、1301020213012*2013 ()2. ,.Pxxxxxxxxxx xxxxxxxxxxx点的坐标满足由此解出此即为加速埃特金公式从图上可知 尽管迭代值比和更远偏离了但按上式定出的却明显地扭转了这种发散的趋势整理ppt二、抛物线法 （P285）12221 ( )0,( ),( ),.kkkkf xxxxpxpxx设已知方程的三个近似根以这三点为节点构造二次插值多项式并适当选取的一个零点作为新的近似根 这样确定的迭代过程称抛物线法 也称密勒法( )f x2( )P x*x1kxkx1kx2kx整理ppt抛物线法计算公式2112112112122 ( )(),() + ,()().,+ ,

28、()()( )()kkkkkkkkkkkkkkkkkkkkkkkkkpxfxf xxxxf xxxxxxxaf xxxbf xxf xxxxxcfxpxaxx插 值 多 项 式令 22*2112()4224,.2sgn() 4kkkkkkkkkkkkkkkkkkkkkkkkkkkkkbxxcbba ccxxxabba cxxxxxxxxcbxxbba c在三 个 近 似 根 中 假 定更 接 近 根故 新 的 近似 根 应 在邻 近 即较 小 于 是 抛 物 线 计 算 公 式 为整理ppt*012* ,(), ()01.84 fxxxxxxxfxx可 以 证 明 如 果在 其 零 点邻 近

29、三 阶 连续 可 微 且 初 值充 分 接 近则 抛 物 线 法是 收 敛 的 。特 别 地 ， 若是 方 程的 单 根 ，收 敛 解 为。另 一 方 面 ， 在 收 敛 性 的 证 明 中 虽 然 要 求 初始 值 充 分 接 近 根， 但 实 际 计 算 表 明 ， 抛 物 线法 对 初 值 要 求 并 不 苛 刻 ， 在 初 值 不 太 好 的 情 况下 常 常 也 能 收 敛 。 缺 点 是 程 序 较 复 杂 ， 并 在 计算 实 根 的 过 程 中 ， 也 常 常 需 要 采 用 复 数 计 算 ，增 加()0fx了 工 作 量 。 因 此 ， 抛 物 线 法 适 用 于 当 初 值不 太 好 时 求 方 程的 复 根 的 情 况 。整理ppt三、代数方程的牛顿法0101100012012100 ( )( )0 () ( )(