常用算法--几种数字积分法1.doc

(n大于等于5)(搜索法求一个根)对于n?5的代数方程,没有求根公式可寻,要求方程的根,通常是采用根搜索方法,求得方程的某一个根,然后将此根从原方程中劈去,使方程降一阶或二阶,继续求根。寻求方程在根平面上的某一个根,其搜索方法有很多种,但大部分方法对重根或密集根得方程搜索将会失败,下面介绍一种搜索较保险并能得到一定精度的搜索方法,即牛顿下山与撒网格结合的搜索法。此方法可求得任何形式代数方程的根,设代数方程0azazaza)z(fn1n1n1n0??????????并且不失一般性,1a0?设方程的一个试验根为000yjxz???当在此试验根附近存在方程的一个根,则有)dyy(j)dxx(zzyjxz00???????????代入方程得)z(vj)z(u)z(f???如果)z(v)z(us)z(f222???时,则yjxz???为方程得一个根。关键是怎样求得试验根的增量dx,dy值,使得z向方程的某一个根趋近。这就是利用牛顿下山法,其方法是将f(z)按泰劳级数:????????????200000)zz(!2)z(f)zz)(z(f)z(f)z(f展开后取一阶项得:dzz)z(f)z(fzz0000?????根据)z(f随z变化的下降性来判断下山迭代是否成功,如果)z(s<)z(s0则所选择的dz是成功的,将zz0?继续迭代,直到)z(s=0或)z(s<?。为加速迭代收敛速度,通常引入一个加速因子t,实际选取dz=dx+jdy为dztz)z(f)z(ftzz0000???????=)dyty(j)dxtx(00??????选取适当的t值可保证)z(s<)z(s0,使下山成功,一般选初值n41t??,寻找下山路线时使t减小,t=t/。直到)z(s>)z(s0或t<,即要作特殊处理了,转到撒网格寻求下山路线,注意每求得)z(s<)z(s0一次,将置t的初值。如果方程F(z)=0中有重根或密集根时,f(z)会出现鞍点,此时,有0s?而0)z(f??,而成dz溢出而使迭代失败,为避免这种情况,而使迭代能成功的搜索到方程的根,采用撒网格的方法,跳出鞍点继续迭代或使s=0或??s得到方程的一个根。其方法如图所示,取适当的一个模d和角度c,使得))csin(j)c(cos(ddz????,dzzz0??159如果dz选择使得)z(s<)z(s0,转到牛顿下山法迭代,如果)z(s>=)z(s0,就减小d,再找下山路线,当1d??时,还不能求得下山的路线时,说明有重根在z处,则可认为是求得的一个根。d的初值由牛顿下山时的dz计算,22)dy()dx(d??.c的初值可选为0。每次迭代入,????。在??2c时,?。在搜索根时,为使0)z(f?有一个根在单位圆内或上,使搜索在单位圆内的范围内,可选对f(z)作如下变换:0an?,令1Zp1Zaznn????nnap?变换后01Zaa1Z)1Z(fn1iinninin?????????niniiaac???(变换后的方程,其常数项为1,表明方程定有一个根在单位圆内,其模小于等于1。)其求得Z1在单位圆中的一个根,再来乘p得到原方程的一个根。Qbasic子程序SUBonwtons(a(),nasInteger,ps)为保证求根精度,子程序中所用迭代变量均采用双精度