函数方程求根讲稿.ppt

《函数方程求根讲稿.ppt》由会员分享，可在线阅读，更多相关《函数方程求根讲稿.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、函数方程求根第一页，讲稿共四十五页哦11,:,0)(RRbafxf例如例如:多项式方程 0)(0111axaxaxaxfnnnn和函数方程 0|sin|log)1cosh()(2xexxfx的求根。本章的主要任务，就是为这些不能套用现成的求根本章的主要任务，就是为这些不能套用现成的求根公式的函数方程，提供常用的，有效的，适合于快速公式的函数方程，提供常用的，有效的，适合于快速数字计算机的求根方法，并研究这些算法的可行性与数字计算机的求根方法，并研究这些算法的可行性与计算复杂性。计算复杂性。函数方程的求根函数方程的求根第二页，讲稿共四十五页哦所谓函数方程 11,:,0)(RRbafxf (2.1

2、)的求根,即求*x使成立 0*)(xf*x即为0)(xf的根,亦称解。*x是否存在?bx1(a,f(a)(b,f(b)ax2x3x1dcbx3ex2a隔离第一个判别定理是:定理 2.2 若函数 在区间ba,上连续，且0)()(bfaf,则函数方程0)(xf在区间ba,上必有根存在。)(xf第三页，讲稿共四十五页哦定理 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

3、(x0)0,f(x)单调增时y=(x-x0)/b+f(x0)x0+bf(x0)x0-bf(x0)首先注意到 0第四页，讲稿共四十五页哦111确定根存在区间的几种简易方法确定根存在区间的几种简易方法(ii)图解法0cos13)(xxxf*x3122xcos13 x(iii)近似方程替代法近似方程替代法 如级数展开如级数展开第五页，讲稿共四十五页哦确定根存在区间的几种简易方法确定根存在区间的几种简易方法 4 计 算)(21111kkkbacI2I3I4I1(i)二分法1 已知f在a,b上满足0)()(bfaf,令ba,=00,ba 2 取点)(21000bac计算)(0cf 3 若成立0)()(0

4、0cfaf，则有 1100,baca，否则，取 1100,babc由此，容易看到，通过 13的计算与判别，我们可获得新的方程根x*的存在区间a1,b1，且有 babax,*11这个过程可以继续下去，假定已经求得存在区间11,kkba，则一般形式是第六页，讲稿共四十五页哦确定根存在区间的几种简易方法确定根存在区间的几种简易方法6kkbababa,1,1abababkkkk2121115若成立0)()(11kkcfaf，则取11,kkkkbaba否则，取11,kkkkbcba，直到满足要求的精度为止。7若令)(21kkkkbacx，,1,0k 则)(21)(21*1ababxxkkkk，,1,0k

5、I2I3I4I1第七页，讲稿共四十五页哦)(211abk2log2log)log(abk定理 2.5 设函数f在区间ba,上连续，0bfaf,则由对分法所得的区间序列kkba,和中间序列 hx成立。I1ab设要求的精度为要分割几次？I2I3I4第八页，讲稿共四十五页哦（ii）弦位法x*ba(b,f(b)c(a,f(a)(c,f(c)用弦分割存在区间第九页，讲稿共四十五页哦（ii）弦位法1已知f在ba,上满足 0bfaf,令00,baba2计算0c=)()()()(000000afbfafbbfa和 0cf3若 成 立 000cfaf,则 取 1100,baca，否 则 取 1100,babc此

6、时新的根存在区间为 0,1111bfafba，故必有根11,*bax，继续这一过程,得算法的一般形式为a(b,f(b)c(a,f(a)(c,f)第十页，讲稿共四十五页哦（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)第

7、十一页，讲稿共四十五页哦定 理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第十二页，讲稿共四十五页哦01010111xxxxxfxfxfxl1010112xfxfxfxxxx割线法割线法abx*X1X0X2X1X0X2第十三页，讲稿共四十五页哦割 线 法 kkkkkkkxfxfxfxxxx111弦位法 kkkkkxfxfxfxxxx001 ,1,0k1x0 x4x3

8、x2xx4割线法与弦位法的区别第十四页，讲稿共四十五页哦今设序列 kx收敛于*x，若存在数1p和0c，使成立cxxxxpkkk*lim1收敛阶的概念收敛阶的概念:(:(重点重点)则称该序列 kx为p阶收敛。特别，当1,1cp时，称 kx为一阶收敛。当p满足21 p时，称 kx为超线性收敛。当2p时，序列 kx为2阶收敛。第十五页，讲稿共四十五页哦定理定理 2.7 设bax,*为方程0)(xf的根，函数f在*x的领域*,xxxS上二次连续可微，且满足条件割线法的收敛性定理割线法的收敛性定理1)*,0 xSxxf2)xfMxfmmMqxSxxSx*,2*,112min,min,12则对任何*,10

9、 xSxx,由割线法产生的序列kx收敛于*x，且有估计式 618.1251,2*151211kqMmxxk （2.3.3）第十六页，讲稿共四十五页哦证明证明 利用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，利 用 同 样 方

10、法，可 以得 到,3,2,*,kxSxk且有估计1121*21*kkkxxxxMMxx (2.3.5)第十七页，讲稿共四十五页哦由 条 件(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。第十八页，讲稿共四十五页哦NewtonNewton法

11、的几何意义法的几何意义Newton 法是求解函数方程 RRbafxf,:,0 （2.4.1）的经典而又重要的算法，它亦是以近似直线方程替代，不过它不象割线法那样用弦，而是用一个点上的切线替代曲线，如图示X2X3X1X0X4y=f(x)图 2.4.1(1)X*第十九页，讲稿共四十五页哦Newton法的几何意义法的几何意义X2X4X1X0X7X6X5X3Y=f(x)又如:图 2.4.1(2)第二十页，讲稿共四十五页哦2)对于,1,0k.计算kkkkxfxfxx11 (2.4.2)2.4 Newton法法的算法描述X2X3X1X0X4y=f(x)X*3)若kxf,则停止计算第二十一页，讲稿共四十五页

12、哦 00000 xxxfxfxl0001xfxfxx1 取 初 始bax,0和 精 度X2X3X1X0X4y=f(x)X*2对于,1,0K计算 kkkkxfxfxx113若kxf，则停止计算第二十二页，讲稿共四十五页哦不收敛例子初始值原因Y=f(x)X2X3X4X0X1第二十三页，讲稿共四十五页哦定定理理2.8 设bax,*满足0*)(xf，函数f在*x的某邻域|*|)*,(xxxxS上二次连续可微且满足条件Newton 法的收敛性问题法的收敛性问题（1）)*,(,0)(xSxxf（2）1212mMq，|)(|min)*,(1xfmxSx，|)(|max)*,(2xfMxSx 则对任何初始)*

13、,(0 xx，由算法产生的序列 kx收敛于*x，且有估计式 )10(,2|*|221qqMmxxkn (2.4.4)第二十四页，讲稿共四十五页哦证明证明 由 Taylor 展式200000)*)(!210)()(*)(xxfxxxfxfxf 及0*)(xf和0)()(0100 xxxfxf得20010)*)(21*)(xxfxxxf 于是有20001)*()()(21*xxxffxx 及20121|*|21|*|xxmMxx由 此 即 知)*,(1xSx。第二十五页，讲稿共四十五页哦利用同样的推导，又得,2,1),*,(kxSxk且有估计 2121|*|21|*|kkxxmMxx （2.4.5

14、）令|*|2112kkxxmM则由（2.4.5）即得估计式,1,0,21kkk因为q0，故有kqk220于是由(2.4.5)即得估计式kqMmxxk2212|*|。第二十六页，讲稿共四十五页哦定定理理 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)第二十七页，讲

15、稿共四十五页哦证证 明明 利 用 归 纳 法，对 于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)第二十八页，讲稿共四十五页哦由 于2h，故

16、当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

17、()2()2()2(|*|此即误差估计(2.4.6)。到此，定理完全证明完毕。第二十九页，讲稿共四十五页哦定理定理 2.9 亦可以认为解的存在性的解析证明。另外，从定理条件看到 Newton 法对于初始0 x的选择是非常苛刻的，要求它非常靠近*x，这就增加了使用 Newton 法的困难，所以有许多研究工作，致力于改变初始0 x的要求，但成效不甚明显。第三十页，讲稿共四十五页哦迭代算法的有效指数Newton法:E=?割线法:E=?第三十一页，讲稿共四十五页哦Y=f(x)bX*abY=f(x)X*aNewton法的走向第三十二页，讲稿共四十五页哦bY=f(x)X*aY=f(x)X*aNewton法

18、的走向第三十三页，讲稿共四十五页哦问 题 )(xx算 法 ,1,0),(1kxxkk1）变 换 如 何 构 成？2）由（2.5.4）产 生 的 序 列 是 否 收 敛 到 解？3）序 列kx收 敛 的 快 慢 程 度 如 何？第三十四页，讲稿共四十五页哦X1X2X0X*Y=(x)Y=xx2x0 x*x1x3y=xY=(x)1|)(|maxxSxY=(x)x0 x1x2x3x*y=xy=xx0 x2x*x3x1Y=(x)1|)(|maxqxSx第三十五页，讲稿共四十五页哦定定理理 2.12 设迭代函数 x在区间),(ba上连续可微，且满足1）baba,，即对任何bax,时，亦有 bax,2)1m

19、ax,qxbax则方程(2.5.3)在区间ba,上存在唯一解*x，对任意初始bax,0简单迭代法(2.5.4)所产生的序列 baxk,收敛于*x，且有估计011*xxqqxxkk （2.5.7）及 *lim1xxxxxkkk （2.5.8）第三十六页，讲稿共四十五页哦于 是 由 介 值 定 理 知 必 有 点bax,*使0*xx，即*x为（2.5.3）的解，唯一性亦是容易证明。假定另有一解 bax,满足 xx，则考虑证证明明:首先由定理假定可知，有 0aa，0bb由条件 2）即知必有*xx 其次，算法的收敛性证明与定理 2.5.1 的证明一样，从略。*xxqxxxxxx第三十七页，讲稿共四十五

20、页哦现在建立(2.5.7)，由于对一切k成立11kkkkxxxx 0111xxqxxqxxkkkkk因此要有010121111xxqqxxqqqxxxxxxkkpkpkkkpkpknpk第三十八页，讲稿共四十五页哦由于已经证明了*xxkk，故在上式中令p，即得011*xxqqxxkk此即(2.5.7)。至 于(2.5.8)的 证 明，就 更 容 易 了，只 需 注 意 到 x在ba,上 的 连 续 性 及 收 敛 性，即 得*lim*lim1xxxxxkkkk至 此 定 理 2.12 全 部 证 毕。第三十九页，讲稿共四十五页哦k值的一个估计式 qxxqklog1loglog01x*x2 x1

21、 x0图2.17第四十页，讲稿共四十五页哦定定理理 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)第四十一页，讲稿共四十五页哦证证明明 利用 Taylor 公式有 ppppxxpxxpxxxxxxxxxxx*!1*!1*!2*112 其中为x与*x所确定的区间中一点，由此，若令 ppxSxMx*,max则由定理条件及（2.5.11）得到 ppMpxxxx!1*(2.5.13)且当*xx时，有 *!1*xpx

22、xxxpp (2.5.14)今选，使1!11ppMp (2.5.15)由（2.5.13），对任何*,xSx有*xx第四十二页，讲稿共四十五页哦由此得kkkkkppppppppppkpppkpkxxpMxxpMxxpMxxpMxx*!*!*!*!*01101211212从 而 对 任 何*,0 xSx，由 迭 代 法（2.5.4）产 生 的 序 列*,xSxk。此 外，对kx利 用（2.5.13）可 得,1,0,!1*1kMpxxxxxxxxppkkpkk此即有 kpppkqpMxx11!*(2.5.16)其中 1*!011xxpMqpp至此定理证毕。第四十三页，讲稿共四十五页哦定定理理 2.17 设0d，则解向量是由(2.6.6)产生的序列 kz的吸引点，而*2t是它的收敛半径。,1,0,2,1,11knizzzpzzkjkinijjkinkiki(i)二阶方法(Durond-Kerner算法)第四十四页，讲稿共四十五页哦定定理理 2.20 设0d，则解向量是由算法(2.6.18)产生的序列 kZ的吸引点，而由(2.6.20)定义的*t是它的收敛半径。,2,1,0,2,111,11knizzzpzpzznijjkjkikinkinkiki三阶方法第四十五页，讲稿共四十五页哦