购买

¥30.0

加入VIP
  • 专属下载券
  • 上传内容扩展
  • 资料优先审核
  • 免费资料无限下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 第六章 方程求根

第六章 方程求根.ppt

第六章 方程求根

中小学精品课件
2019-04-27 0人阅读 举报 0 0 0 暂无简介

简介:本文档为《第六章 方程求根ppt》,可适用于高等教育领域

第六章方程求根根的搜索在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程    f(x)=()的求根问题,其中f(x)为非线性函数如果f(x*)=,则x*称为方程f(x)=的根,亦称为函数f(x)的零点设函数f(x)在闭区间a,b上连续,且f(a)f(b)<,根据连续函数的性质可知,f(x)=在(a,b)内必有实根,称区间a,b为有根区间如果f(x)可以分解成其中m为正整数且则称x*是f(x)的m重零点,或方程f(x)=的m重根当m=时称x*为单根零点或根的重数当f(x)不是x的线性函数时,称对应的函数方程为非线性方程如果f(x)是多项式函数,则称为代数方程,若f(x)是三角函数、指数函数、对数函数等,称为超越方程一般称n次多项式构成的方程为n次代数方程,当n>时,方程显然是非线性的一般稍微复杂的次以上的代数方程或超越方程,很难甚至无法求得精确解记笔记本章将介绍常用的求解非线性方程的近似根的几种数值解法区间法迭代法通常方程求根的数值解法大致分为三个步骤进行① 判定根的存在性即方程有没有根?如果有根,有几个根?②确定根的分布范围即将每一个根用区间隔离开来,这个过程实际上是获得方程各根的初始近似值③根的精确化将根的初始近似值按某种方法逐步精确化,直到满足预先要求的精度为止本章介绍方程求根的数值解法,它既可以用来求解代数方程,也可以用来解超越方程,并且仅限于求方程的实根运用迭代解方程的根应解决以下两个问题:确定根的初值将进一步精确化到所需要的精度记笔记逐步搜索法为明确起见不妨假定f(a)<,f(b)>从有根区间a,b的左端的x=a出发按照某个预定的步长h一步一步地向右跨每跨一步进行一次根的“搜索”即检查节点xk=akh上的函数值f(xk)的符号一旦发现f(xk)与f(a)异号,则可以确定一个缩小了的有根区间xk,xk,其宽度等于预定的步长h例方程f(x)=xx=,确定其有根区间可以看出,在,内必有一根解:不难发现f()<,f()>,知f(x)在区间(,)内至有一个实根设从x=出发,取h=为步长向右进行根的搜索,列表如下用逐步搜索法的关键是选取步长h只要h取得足够小,利用此法可以得到具有任意精度的近似根相应的,所需要的搜索步数增多计算量增大二分法二分法又称二分区间法,是求解方程()的近似根的一种常用的简单方法二分法的基本思想:首先确定有根区间,将区间二等分,通过判断f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根①取有根区间a,b的中点将区间分为两个小区间,然后在a,x和x,b中确定新的有根区间记其为a,b求根过程yy=f(x)y=f(x)x*axx*xbaxxbabababab②对压缩了的有根区间施行同样的手法,即取中点,将区间再分为两半,然后再确定有根区间,其长度是的二分之一③如此反复下去,若不出现,即可得出一系列有根区间序列:上述每个区间都是前一个区间的一半,因此的长度当k→∞时趋于零,这些区间最终收敛于一点x*即为所求的根 每次二分后,取有根区间的中点作为根的近似值,得到一个近似根的序列该序列以根x*为极限 只要二分足够多次(即k足够大),便有这里ε为给定精度,由于,则()当给定精度ε>后,要想成立,只要取k满足即可,亦即当:时,计算得到的就是满足精度要求的近似根在程序中通常用相邻的与的差的绝对值或与的差的绝对值是否小于ε来决定二分区间的次数二分法算法实现yn开始输入a,b,ε(ab)(xf(a)f(x)<x(bx(a|ba|<ε输出x结束yn例求方程f(x)=xx=在区间,内的一个实根,使误差不超过×例证明方程在区间,内有一个根,使用二分法求误差不超过×的根要二分多少次?误差限为只要取k满足即可,亦即所以需二分次便可达到要求给定误差限=×,使用二分法时二分法的优点是不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单它的局限性是只能用于求函数的实根,不能用于求复根及重根,它的收敛速度与比值为的等比级数相同迭代法迭代法过程的收敛性为求解非线性方程f(x)=的根,先将其写成便于迭代的等价方程()其中为x的连续函数即任取一个初值代入式的右端,得到式()称为求解非线性方程的简单迭代法,称为迭代函数()依此类推,得到一个数列如果由迭代格式产生的序列收敛,即则称迭代法收敛此时x*就是方程f(x)=的根迭代法的几何意义通常将方程f(x)=化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于的性态,方程的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标(下图所示)(a)(b)y=xyy=y=xPxP�P*QQxxxx*xyxxxxx*y=�EMBEDEquation����EMBEDEquation���P*Punknownunknownunknowny=xyy=xy=(c)(d)xP*P*xxxx*xyxxxxx*y=�EMBEDEquation����EMBEDEquation���unknownunknownunknownunknownunknown例用迭代法求方程在x=附近的一个根解将方程改写成如下两种等价形式相应地可得到两个迭代公式如果取初始值=,用上述两个迭代公式分别迭代,计算结果收敛!发散!kxk迭代法收敛的条件对方程f(x)=可以构造不同的迭代公式,但迭代公式并非总是收敛那么,当迭代函数满足什么条件时,相应的迭代公式才收敛呢?即使迭代收敛时,我们也不可能迭代很多次,而是迭代有限次后就停止,这就需要估计迭代值的误差,以便适时终止迭代定理假定函数在a,b上具有连续的一阶导数,且满足下列两项条件:对任意的x∈a,b有∈a,b存在<L<,使所有的x∈a,b,有≤L<则方程在a,b上的解存在且唯一,且对任意的∈a,b,迭代过程均收敛于并有误差估计式()()定理’假定函数在a,b上连续且满足下列两项条件:对任意的x∈a,b有∈a,b存在<L<,使所有的∈a,b,有则方程在a,b上的解存在且唯一,且对任意的∈a,b,迭代过程均收敛于并有误差估计式()()实际计算中当然不可能无穷多步地做下去,由()迭代法的算法框图开始输入x,ε,N(k�k<Nk(kx(x输出近似根x|xx|<ε输出迭代失败标志结束ynnyunknown例对方程,构造收敛的迭代格式,求其一个正根,计算过程保留位小数解容易判断,是方程的有根区间,且在此区间内,所以此方程在区间,有且仅有一根将原方程改写成以下两种等价形式①,即不满足收敛条件②,即此时迭代公式满足迭代收敛条件局部收敛性在实际应用迭代法时通常在所求的根x*的邻近进行考察即研究其局部收敛性例求方程x=ex在x=附近的一个根,要求精度ε=解:对x=以h=为步长搜索一次,得(,)为有根区间对可知从而在根的附近有因此迭代公式对于初值x=是收敛的例设,要使迭代过程局部收敛到,求的取值范围解:由在根邻域具有局部收敛性时,收敛条件所以假定改变不大,近似地取某个近似值L,则由设是根的某个近似值,用迭代公式校正一次得迭代公式的加工得令()加权法校正:改进:或合并写成:例用加权法加速技术求解方程在附近的一个根解:由前面知在x=附近收敛又在x=附近加速公式的具体形式为但上述加速方案需要计算L实际使用不便对于用迭代公式再校正一次得同理可得又已知联立消去L得推得()Aitken加速方法校正:再校正:改进:Aitken加速方法校正:再校正:改进:Aitken加速方法例用Aitken方法求方程解取x=迭代格式是发散的用Aitken方法进行加速有Newton法用迭代法可逐步精确方程根的近似值,但必须要找到的等价方程,如果选得不合适,不仅影响收敛速度,而且有可能造成迭代格式发散能否找到一种迭代方法,既结构简单,收敛速度快,又不存在发散的问题?这就是本节要介绍的Newton法Newton公式牛顿迭代法一种重要和常用的迭代法,它的基本思想是将非线性函数f(x)逐步线性化,从而将非线性方程f(x)=近似地转化为线性方程求解将右端取为,即是比更接近于的近似值对于方程,设其近似根为,函数f(x)可在附近作泰勒展开忽略高次项,用其线性部分作为函数f(x)的近似,设的根,则有,即这就是著名的Newton公式()Newton法的几何解释方程f(x)=的根x*是曲线y=f(x)与x轴交点的横坐标,设xk是根x*的某个近似值,过曲线y=f(x)的横坐标为xk的点Pk=(xk,f(xk))引切线交x轴于xk,并将其作为x*新的近似值,重复上述过程,可见一次次用切线方程来求解方程f(x)=的根,所以亦称为Newton切线法`yy=f(x)PkPkPkx*xkxkxkx定义设迭代过程收敛于的根如果迭代误差当时成立下列渐进关系式:则称该迭代过程是p阶收敛的Newton法的局部收敛性一种迭代法具有实用价值首先要求它是收敛的其次还要求它收敛得比较快注:p=时称为线性收敛p=时称为平方收敛<p<时称为超线性收敛数p的大小反映了迭代法收敛的速度的快慢p愈大则收敛的速度愈快故迭代法的收敛阶是对迭代法收敛速度的一种度量定理对于迭代过程如果在所求根的邻近连续,并且则称该迭代过程在点邻近是p阶收敛的重根情形()()kxk()()()xxxxNewton法的算法实现开始输入x,ε,N(k�k<Nk(kx(x输出x输出迭代失败标志结束nnny输出奇异标志yyunknownunknownunknown例用Newton法解方程xex=解:因f(xk)=xex–,f`(x)=ex(x)建立迭代公式取x=,逐次计算得x=,x=,x=例已知迭代公式收敛于证明该迭代公式平方收敛Newton法应用举例()计算迭代对于任意初值x>都是收敛的()计算a迭代对于初值<x<a都是收敛的Newton下山法通常,Newton法的收敛性依赖于初始值的选取,如果偏离所求的根比较远,则Newton法可能发散为了防止迭代发散,我们对Newton法的迭代过程再附加一项要求,即具有单调性将Newton法与下山法结合起来使用,即在下山法保证函数值下降的前提下,用Newton法加快收敛速度把这一算法称为Newton下山法满足这项要求的算法称为下山法为此将Newton法的计算结果与前一步的近似值xk适当平均作为新的改进值即其中称为下山因子挑选下山因子时希望使单调性条件成立下山因子的选择是个逐步探索的过程,设从=开始反复将减半进行试算,即逐次取为从中挑选下山因子,直至找到其中某个使单调性条件成立,则称“下山成功”,否则“下山失败”,这时需另选初值重算现在设法利用迭代过程中的“老”信息来回避导数值的计算弦截法与抛物线法Newton法虽然具有收敛速度快的优点,但每迭代一次都要计算导数当比较复杂时,提供它的导数值往往是有困难的导出这类求根方法的基础是插值原理设是f(x)=的一组近似根,利用函数值构造插值多项式Pr(x),并适当选取Pr(x)=的一个根作为f(x)=的新的近似根xk,这就确定了一个新的迭代过程记迭代函数为则有弦截法()迭代公式相应的迭代法称为弦截法()几何意义()收敛速度定理假设f(x)在根的邻域内具有二阶连续导数且对于任意有又初值,那么当邻域充分小时弦截法将按收敛到根弦截法具有超线性收敛!弦截法算法实现x(x输入x,x,,ε,N(k�k<Nk(kx(xx(xf(x)(f(x)f(x)(f(x)输出xx(x输出迭代失败标志结束nnny输出奇异标志yynyy输出xnunknownunknownunknownunknownunknownunknownunknownunknownunknownunknown例用弦截法方程解:取令利用弦截迭代公式计算抛物线法()迭代公式()几何意义()收敛速度例用抛物线法方程解:取利用抛物线迭代公式计算非线性方程的解通常叫做方程的根,也叫做函数的零点,本章讨论了求解非线性方程近似根常用的一些数值方法先要确定有根区间,且对于收敛的迭代格式,这个区间要足够小针对各种求根的数值方法的特点,要考虑其收敛性、收敛速度和计算量二分法是逐步将含根区间分半,主要用来求实根迭代法是一种逐次逼近的方法,起着把根的精确值一步一步算出来的作用牛顿法具有较快的收敛速度,但对初值选取要求较高弦截法避开了导数的计算,具有超线性的收敛速度,每计算一步,要用到前面两步的信息抛物线法要用到前面三步的信息本章小结,,故k取()()

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

评分:

/85

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利