下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 对牛顿迭代算法中的

对牛顿迭代算法中的.pdf

对牛顿迭代算法中的

15*******87@sina.cn
2013-10-06 0人阅读 举报 0 0 暂无简介

简介:本文档为《对牛顿迭代算法中的pdf》,可适用于人文社科领域

对牛顿迭代算法中的“不稳定拉格朗日点”的初步分析中国科大张嘉晖摘要:本文研究了牛顿迭代算法中的一种病态现象阐明了它和力学中的不稳定拉格朗日点的类似性。给出了找到这些点的方法并提出了一种避免这种“拉格朗日点”现象干扰牛顿迭代计算的方法。关键词:牛顿迭代法拉格朗日点引言力学上拉格朗日点指受两大物体引力作用下能使小物体稳定的点。可以证明对于某些拉格朗日点轻微的扰动会使小物体自发地偏离拉格朗日点而且该物体最终的归宿对扰动是极其敏感的这就是不稳定拉格朗日点。图地日拉格朗日点以L点为例在图中一个向左的扰动会使处于该点的小物体最终坠入太阳而一个向右的扰动会使物体最终坠落地球。在牛顿迭代法计算非线性方程的根时也有类似的现象:以初值xdx和xdx时各自得到不同的迭代结果。PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http:wwwnovapdfcom)极值点牛顿迭代公式:x(n)=x(n)-f(x(n))f'(x(n))在极值点处导数为零不能进行牛顿迭代。而极值点左右很小的范围内导函数的绝对值很小且取不同符号则易发现当x(n)从极值点一侧加上一个极小的增量到达极值点另一侧时x(n)将会有显著的变化。这便极有可能得到不同的迭代结果。举一个例子对于:f(x)=x^x,在x=处其导数为零运用牛顿迭代法分别输入初值和得到的结果分别为:和。迭代的结果从正根突越到负根说明对于方程f(x)=来说是一个拉格朗日点。相关程序:ROGRAMNTREAL*X,XK,XK,E,epsilonINTEGERK,J,MAXREAD*,XXK=Xepsilon=MAX=K=DOJ=,MAX,XK=XK(XK*XK*XKXK)(XK*XK)K=KE=XKXKIF(E<)THENE=EENDIFIF(E<epsilon)THENPRINT,X,XK,KFORMAT(F,EN,I)EXITENDIFXK=XKENDDOIF(J>=MAX)THENPRINT*,"附近无实根"ENDIFPAUSEEND程序一个直观上的判断:当极值点左右都存在方程的根时则该点是一个拉格朗日点。PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http:wwwnovapdfcom)图f(x)的图像非极值点的拉格朗日点一个有趣的现象是在寻找f(x)=x^x=的根时输入初值和得到的结果分别为:E、E说明这两点之间可能存在拉格朗日点于是用二分法的思想试图找到一个拉格朗日点相关程序为:PROGRAMNTreal*x,x,x,xintegerix=x=doi=,x=(xx)x=root(x)if(x<)THENx=xelsex=xendifenddoprint*,xpauseendfunctionroot(x)REAL*X,XK,XK,E,epsilonINTEGERK,J,MAXXK=Xepsilon=MAX=K=DOJ=,MAX,PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http:wwwnovapdfcom)XK=XK(XK*XK*XKXK)(XK*XK)K=KE=XKXKIF(E<)THENE=EENDIFIF(E<epsilon)THENEXITENDIFXK=XKENDDOIF(J>=MAX)THENPRINT*,"附近无实根"ENDIFroot=xkend程序算得结果为:拉格朗日点约是:。那么为什么会存在非极值点的拉格朗日点呢?为了解答这个问题我对程序增加了输出每次迭代结果的指令然后对初值进行迭代得到的前几个迭代结果为:······不难发现第次迭代的结果非常接近这个前面讨论过的极值拉格朗日点故一个合理的猜测是由于计算的误差并不是真正的拉格朗日点而是一个非常接近拉格朗日点的数值而真正的拉格朗日点应具有以下性质:经过有限次牛顿迭代后恰好达到一个极值点。寻找拉格朗日点根据上文的分析应首先寻找那些经过一次迭代后值为极值点的那些点这里不妨将之命名为一次拉格朗日点。不妨设x是一个f(x)的极值点则一次拉格朗日点x满足:X=xf(x)f’(x),这便相当于解一个非线性方程可以用迭代法求解。PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http:wwwnovapdfcom)不妨将这样一次求根的过程定义成一个函数:F(x)。则在给定迭代初值的情况下可得一系列的拉格朗日点:F(x)、F(F(x))、F(F(F(X)))······这些点便为一次拉格朗日点、二次拉格朗日点、三次拉格朗日点······。当然存在同次数拉格朗日点不唯一的情况这无疑会给寻找拉格朗日点带来极大的困难但对于低次数的拉格朗日点只需要逐一迭代即可。如存在x和x则在寻找x时要分别考虑到参数取x和x两种情况。对于f(x)=x^x来说选定一个极值点x=,相应的方程为:∗ݔଷ−∗ݔଶ=则可解得X是一个拉格朗日点这与程序的运行结果相吻合。再由其图像可知X是其唯一的以x=为基础的一次拉格日图∗ݔଷ−∗ݔଶ的图像点。同理可得X是该函数以x=为基础的唯一一次拉格朗日点。依此方法计算可得之后的一系列拉格朗日点(直到某一个求更高次的拉格朗日点的方程没有实根为止)。总结拉格朗日点的存在说明了一个事实即牛顿迭代法不仅在导函数为零的点无法进行而且在一系列拉格朗日点上均无法进行因为迭代最终会导致导函数为零的点出现。虽然作为一个个孤立的点实际计算时初值取到拉格朗日点的概率极小(由实数的绸密性可以认为概率为零)但我们可以发现当处值靠近拉格朗日点时迭代次数明显增加还以计算f(x)=x^x=的根为例运用程序初值取则迭代步数为初值取则迭代次数为增大倍。另外由迭代结果在拉格朗日点两侧小范围内的突变性知拉格朗日点附近的牛顿迭代时一个病态的算法。所以迭代算法中应当注意避免将拉格朗日点作为初值进行计算但是我们不可能事先将拉格朗日点全部计算出来然后当输入的处值接近他们时由某种方式进行调整。但我们可以注意到程序的运行结果中当越过这个非常接近的值后下一步的结果直接跳到了E于是直观上我们可以得到一个判断拉格朗日点的方法当迭代中相邻的两步的结果差超过一个预先设定的大值时就认为初值取在了拉格朗日点附近。这时一个明智的做法就是停止迭代调整初值重新进行迭代。PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http:wwwnovapdfcom)PrinttoPDFwithoutthismessagebypurchasingnovaPDF(http:wwwnovapdfcom)

用户评价(0)

关闭

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

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

提示

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

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/6

对牛顿迭代算法中的

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利