函数方程求根.ppt

函数方程求根现在学习的是第1页，共45页11,:,0)(RRbafxf例如例如: :多项式方程 0)(0111axaxaxaxfnnnn和函数方程 0|sin|log)1cosh()(2xexxfx的求根。 本章的主要任务，就是为这些不能套用现成的求根公式的本章的主要任务，就是为这些不能套用现成的求根公式的函数方程，提供常用的，有效的，适合于快速数字计算机的函数方程，提供常用的，有效的，适合于快速数字计算机的求根方法，并研究这些算法的可行性与计算复杂性。求根方法，并研究这些算法的可行性与计算复杂性。函数方程的求根函数方程的求根现在学习的是第2页，共45页所谓函数方程 11,:,0)(RRbafxf (2.1)的求根,即求*x使成立 0*)(xf*x即为0)(xf的根,亦称解。*x是否存在?bx1(a,f(a)(b,f(b)ax2x3x1dcbx3ex2a隔离第一个判别定理是:定理 2.2 若函数 在区间ba,上连续，且0)()(bfaf,则函数方程0)(xf在区间ba,上必有根存在。)(xf现在学习的是第3页，共45页定理 2.3 若函数f在区间ba,上连续，0)()(bfaf,且对任意bax,有)0)(0)(xfxf或, 则函数方程(2.1.1)在区间ba,上存在唯一解。图2.3CA(x0 , f(x0 )X0DB什么时候方程解是存在唯一的什么时候方程解是存在唯一的?y = - (x-x0) / b + f(x0)f(x0) 0, f(x)单调增时y=(x-x0)/b + f(x0)x0 + bf(x0)x0-bf(x0)首先注意到 0现在学习的是第4页，共45页111确定根存在区间的几种简易方法确定根存在区间的几种简易方法(ii) 图解法0cos13)(xxxf*x3122xcos13 x( iii ) 近似方程替代法近似方程替代法 如级数展开如级数展开现在学习的是第5页，共45页确定根存在区间的几种简易方法确定根存在区间的几种简易方法 4 计 算)(21111kkkbacI2I3I4I1( i ) 二分法1 已知f在a , b上满足0)()(bfaf,令ba,=00,ba 2 取点)(21000bac计算)(0cf 3 若成立0)()(00cfaf，则有 1100,baca，否则，取 1100,babc由此，容易看到，通过 13的计算与判别，我们可获得新的方程根x* 的存在区间a1,b1，且有 babax,*11这个过程可以继续下去，假定已经求得存在区间11,kkba，则一般形式是现在学习的是第6页，共45页确定根存在区间的几种简易方法确定根存在区间的几种简易方法6kkbababa,1, 1abababkkkk2121115若成立0)()(11kkcfaf，则取11,kkkkbaba否则，取11,kkkkbcba，直到满足要求的精度为止。7若令)(21kkkkbacx，, 1 , 0k 则)(21)(21*1ababxxkkkk，, 1 , 0kI2I3I4I1现在学习的是第7页，共45页)(211abk2log2log)log(abk定理 2.5 设函数f在区间ba,上连续， 0bfaf, 则由对分法所得的区间序列kkba ,和中间序列 hx成立。I1ab设要求的精度为要分割几次？I2I3I4现在学习的是第8页，共45页（ii）弦位法x* ba(b,f(b)c(a,f(a)(c,f(c)用弦分割存在区间现在学习的是第9页，共45页（ii）弦位法1已知f在ba,上满足 0bfaf,令00,baba2计算0c=)()()()(000000afbfafbbfa和0cf3若 成 立 000cfaf, 则 取 1100,baca， 否 则 取 1100,babc此时新的根存在区间为 0,1111bfafba，故必有根11,*bax ，继续这一过程,得算法的一般形式为a(b,f(b)c(a,f(a)(c,f)现在学习的是第10页，共45页（ii）弦位法4对于, 1 , 0k计算kc=)()()()(kkkkkkafbfafbbfa (2.2.4)和kcf5成 立0kkcfaf,则 取kkkkcaba,11否则取kkkkbcba,11，直到满足要求的精确度为止。6kkbax,*且对一切 k 成立*xbxbabkkk7令kkcx)()()()(kkkkkkafbfafbbfa则成立klim*xxk但未必成立0)(limkkkaba(b,f(b)c(a,f(a)(c,f)现在学习的是第11页，共45页定 理2 6 假 定 函 数f在 区 间ba,上 连 续 , 0bfaf,x*(c,f(c)(a,f(a)(b,1/2f(b)(b,f(b)dca弦位法的改进图2.1.6 则 由 弦 位 法 产 生 的 分 点 序 列 kx收敛于极限bax,*且成立0* xf(b, p*f(b)0=p=1现在学习的是第12页，共45页01010111xxxxxfxfxfxl1010112xfxfxfxxxx割线法割线法abx*X1X0X2X1X0X2现在学习的是第13页，共45页割 线 法 kkkkkkkxfxfxfxxxx111弦位法 kkkkkxfxfxfxxxx001 , 1 , 0k1x0 x4x3x2xx4割线法与弦位法的区别现在学习的是第14页，共45页今设序列 kx收敛于*x，若存在数1p和0c，使成立cxxxxpkkk*lim1收敛阶的概念收敛阶的概念: (: (重点重点) )则称该序列 kx为p阶收敛。特别，当1, 1cp时，称 kx为一阶收敛。 当p满足21 p时，称 kx为超线性收敛。 当2p时，序列 kx为2阶收敛。现在学习的是第15页，共45页定理定理 2.7 设bax,*为方程0)(xf的根，函数f在*x的领域*,xxxS上二次连续可微，且满足条件割线法的收敛性定理割线法的收敛性定理1) *, 0 xSxxf2) xfMxfmmMqxSxxSx *,2*,112min,min, 12则对任何*,10 xSxx,由割线法产生的序列kx收敛于*x，且有估计式 618. 1251,2*151211kqMmxxk （2.3.3）现在学习的是第16页，共45页证明证明 利用Newton插值公式，可得 100101011*21*xxxxfxxxxxfxfxfxf 由于0* xf和 01201211xxxxxfxfxf故有 10020101*21*xxxxfxxxxxfxf 再利用中值公式,上式可表示为 10102*21*xxxxffxx (2.3.4)其中1为包含10,xx的最小区间内某一点，(2.3.4)两端取绝对值，即得0121221xxxxMMxx由 条 件2)， 推 出*,2xSx ， 利 用 同 样 方法 ， 可 以得 到, 3 , 2,*,kxSxk且有估计1121*21*kkkxxxxMMxx (2.3.5)现在学习的是第17页，共45页由 条 件 (2)， 知q10， 因 此 由 (2.3.6)用 归 纳 法 得 到 , 1 ,0,kqkk (2.3.7)其中k满足关系式 , 2 , 1,11 (2.3.8)110今 用21,分 别 表 示 二 次 方 程12 tt的 二 个 根251,25121则 (2.3.8)的 解 可 表 示 为121151kkk由 此 易 得 kk151方 程 由 (3.6)得kqk151此 即 (2.3.3)式 ， 并 由 此 即 可 得 到*xxk。现在学习的是第18页，共45页NewtonNewton法的几何意义法的几何意义Newton 法是求解函数方程 RRbafxf,:, 0 （2.4.1）的经典而又重要的算法，它亦是以近似直线方程替代，不过它不象割线法那样用弦，而是用一个点上的切线替代曲线，如图示X2X3X1X0X4y=f(x)图 2.4.1 (1)X*现在学习的是第19页，共45页Newton法的几何意义法的几何意义X2X4X1X0X7X6X5X3Y=f(x)又如:图 2.4.1(2)现在学习的是第20页，共45页2)对于, 1 , 0k.计算kkkkxfxfxx11 (2.4.2)2.4 Newton法法的算法描述X2X3X1X0X4y=f(x)X*3)若kxf,则停止计算现在学习的是第21页，共45页 00000 xxxfxfxl0001xfxfxx1 取 初 始bax,0和 精 度X2X3X1X0X4y=f(x)X*2对于, 1 , 0K计算 kkkkxfxfxx113若kxf，则停止计算现在学习的是第22页，共45页不收敛例子初始值原因Y=f(x)X2X3X4X0X1现在学习的是第23页，共45页定定理理2.8 设bax,*满足0*)(xf，函数f在*x的某邻域| *|)*,(xxxxS上二次连续可微且满足条件Newton 法的收敛性问题法的收敛性问题（ 1）)*,(,0)(xSxxf（2）1212mMq，| )(|min)*,(1xfmxSx，| )(|max)*,(2xfMxSx 则对任何初始)*,(0 xx ，由算法产生的序列 kx收敛于*x，且有估计式 ) 10 ( ,2|*|221qqMmxxkn (2.4.4)现在学习的是第24页，共45页证明证明 由 Taylor 展式200000)*)(! 210)()(*)(xxfxxxfxfxf 及0*)(xf和0)()(0100 xxxfxf得20010)*)(21*)(xxfxxxf 于是有20001)*()()(21*xxxffxx 及20121|*|21|*|xxmMxx由 此 即 知)*,(1xSx。现在学习的是第25页，共45页利用同样的推导，又得, 2 , 1),*,(kxSxk且有估计 2121|*|21|*|kkxxmMxx （2.4.5）令|*|2112kkxxmM则由（2.4.5）即得估计式, 1 , 0,21kkk因为q0，故有kqk220于是由(2.4.5) 即得估计式kqMmxxk2212|*| 。现在学习的是第26页，共45页定定理理 2.9 设函数f于某初始点bax,0邻域baxxxxS,|),(00上连续可微且满足（1） | )(|0 xf（2）),(,|)(|01xSxxf（3）),(, 0|,| )()(|0 xSyxLyxLyfxf则当),(0*xSx 12002)2(, 2kkhLh时，函数方程0)(xf有唯一解，且算法（2.4.2）收敛于该解并有误差估计式kkhhxxk212)2(1)2(|*| (2.4.6)现在学习的是第27页，共45页证证 明明 利 用 归 纳 法 ， 对 于0k时 ， 有001|xx表 明),(01xSx 令 假 定mk 时 成 立（ 1）mnxSxk,2, 1 ,0),(0（ 2）2211|21|kkkkxxLxx验证1 mk时亦成立，首先可得)()()(|)(|11111mmmmmmmmxxxfxfxfxfxx 21|21mmxxL其次，由不等式01200101)2(|kmkkmkkmhLxxxx可得),(01xSxm，于是由 归纳 法 即知， 对一 切, 1 ,0k(1) (2)成立。 因此 ，对任何10pk和，亦有 1210)2(|kkpjkpkhxx (2.4.7)现在学习的是第28页，共45页由 于2h， 故 当p时 有0|kpkxx， 这 表 明kx为 一Caucky 序 列 ， 因 为),(0 xS为 闭 的 ， 故 必 有 一 个),(*0 xSx，使 得 下 式 成 立*limxxkk又由不等式| )()()(| )(|111kkkkkkxxxfxfxfxf21|21kkxxL及函数f的连续性,即得0*)(xf，表明*x是函数方程(2.41)的解。关于方程解的唯一性，可以利用反证法，如果在),(0 xS还有一个解*x使0*)*(xf，则利用中值公式及)(xf在),(0 xS上的非零性质，即知必有*xx。再在(2.4.7)式的两端，让p，则得kkkkjkhhhhhxxjjjk2122012120)2(1)2()2()2()2(|*|此即误差估计(2.4.6)。到此，定理完全证明完毕。现在学习的是第29页，共45页定定理理 2.9 亦可以认为解的存在性的解析证明。另外，从定理条件看到 Newton 法对于初始0 x的选择是非常苛刻的，要求它非常靠近*x，这就增加了使用 Newton 法的困难，所以有许多研究工作，致力于改变初始0 x的要求，但成效不甚明显。现在学习的是第30页，共45页迭代算法的有效指数Newton法: E=?割线法 : E=?现在学习的是第31页，共45页Y=f(x)bX*abY=f(x)X*aNewton法的走向现在学习的是第32页，共45页bY=f(x)X*aY=f(x)X*aNewton法的走向现在学习的是第33页，共45页问 题 )( xx算 法 ,1 ,0),(1kxxkk1） 变 换 如 何 构 成 ？2） 由 （ 2.5.4） 产 生 的 序 列 是 否 收 敛 到 解 ？3） 序 列kx收 敛 的 快 慢 程 度 如 何 ？现在学习的是第34页，共45页X1X2X0X*Y=(x)Y=xx2x0 x*x1x3y=xY=(x)1| )( |maxxSxY=(x)x0 x1x2x3x*y=xy=xx0 x2x*x3x1Y=(x)1| )( |maxqxSx现在学习的是第35页，共45页定定理理 2.12 设迭代函数 x在区间),(ba上连续可微，且满足1） baba,，即对任何bax,时，亦有 bax,2) 1max,qxbax则方程(2.5.3)在区间ba,上存在唯一解*x，对任意初始bax,0简单迭代法(2.5.4)所产生的序列 baxk,收敛于*x，且有估计011*xxqqxxkk （2.5.7）及 *lim1xxxxxkkk （2.5.8）现在学习的是第36页，共45页于 是 由 介 值 定 理 知 必 有 点bax,*使0*xx， 即*x为（2.5.3）的解，唯一性亦是容易证明。假定另有一解 bax,满足 xx，则考虑证证明明: 首先由定理假定可知，有 0aa， 0bb由条件 2）即知必有*xx 其次，算法的收敛性证明与定理 2.5.1 的证明一样，从略。 *xxqxxxxxx现在学习的是第37页，共45页现在建立(2.5.7)，由于对一切k成立11kkkkxxxx 0111xxqxxqxxkkkkk因此要有010121111xxqqxxqqqxxxxxxkkpkpkkkpkpknpk现在学习的是第38页，共45页由于已经证明了*xxkk，故在上式中令p，即得011*xxqqxxkk此即(2.5.7)。至 于 (2.5.8)的 证 明 ， 就 更 容 易 了 ， 只 需 注 意 到 x在ba,上 的 连 续 性 及 收 敛 性 ， 即 得 *lim*lim1xxxxxkkkk至 此 定 理 2.12 全 部 证 毕 。现在学习的是第39页，共45页k值的一个估计式 qxxqklog1loglog01x*x2 x1 x0图2.17现在学习的是第40页，共45页定定理理 2.13 设*x为方程（2.5.3）的解，在*x的领域*,xS内1p次连续可微，且 0*, 0*1 xxxxpp (2.5.11)则迭代法(2.5.4)在领域*,xS内为p阶收敛，且有 *!1*lim1xpxxxxppkkk (2.5.12)现在学习的是第41页，共45页证证明明 利用 Taylor 公式有 ppppxxpxxpxxxxxxxxxxx*!1*!1*! 2*112 其中为x与*x所确定的区间中一点，由此，若令 ppxSxMx *,max则由定理条件及（2.5.11）得到 ppMpxxxx!1* (2.5.13)且当*xx时，有 *!1*xpxxxxpp (2.5.14)今选，使1!11ppMp (2.5.15)由（2.5.13） ，对任何*,xSx有 *xx现在学习的是第42页，共45页由此得kkkkkppppppppppkpppkpkxxpMxxpMxxpMxxpMxx*!*!*!*!*01101211212从 而 对 任 何*,0 xSx， 由 迭 代 法 （ 2.5.4 ） 产 生 的 序 列*,xSxk。 此 外 ， 对kx利 用 （ 2.5.13） 可 得, 1 ,0,!1*1kMpxxxxxxxxppkkpkk此即有 kpppkqpMxx11!* (2.5.16)其中 1*!011xxpMqpp至此定理证毕。现在学习的是第43页，共45页定定理理 2.17 设0d，则解向量是由(2.6.6)产生的序列 kz的吸引点，而*2t是它的收敛半径。, 1 ,0,2, 1,11knizzzpzzkjkinijjkinkiki( i ) 二阶方法(Durond-Kerner算法)现在学习的是第44页，共45页定定理理 2.20 设0d，则解向量是由算法(2.6.18)产生的序列 kZ的吸引点，而由(2.6.20)定义的*t是它的收敛半径。,2, 1 ,0,2, 111,11knizzzpzpzznijjkjkikinkinkiki三阶方法现在学习的是第45页，共45页