[数值算法]求根算法系列小结

1、精选文档数值算法求根算法系列小结 1二分求根法:二分求根法主要用的思想是不断调整并缩小搜索区间的大小，当搜索区间的大小已小于搜索精度要求时，则可说明已找到满足条件的近拟根.当然，在这之前，首先是要准确的估计出根所处的区间，否则，是找不到根的。Type binaryPationMethod(Type x1,Type x2,Type e,Type (*arguF)(Type),FILE* outputFile) Type x;/*The return answer*/ Type mid; Type down,up; int iteratorNum=0;   down=x1; u

2、p=x2; assertF(x1<=x2,"in twoPation x1>=x2"); assertF(arguF!=NULL,"in twoPation arguF is NULL"); assertF(outputFile!=NULL,"in twoPation outputFile is NULL"); assertF(*arguF)(x1)*(*arguF)(x2)<=0,"in twoPation,f(x1)*f(x2)>0"); fprintf(outputFile,"

3、;downttupttrn"); /*two pation is a method that is surely to find root for a formula*/ while(fabs(up-down)>(float)1/(float)2*e) mid=(down+up)/2; if (*arguF)(mid)=0) break; else if(*arguF)(down)*(*arguF)(mid)>0) down=mid; else up=mid; fprintf(outputFile,"%-12f%-12frn",down,up); it

4、eratorNum+; /*get the answer*/ x=mid; /*Output Answer*/ fprintf(outputFile,"total iterator time is:%drn",iteratorNum); fprintf(outputFile,"a root of equation is :%frn",x); return x; 测试1：用二分法求: f(x)=x3-x2-2*x+1=0在(0,1)附近的根. 精度:0.001. Output: downup 0.000000 0.500000 0.250000 0.500

5、000 0.375000 0.500000 0.437500 0.500000 0.437500 0.468750 0.437500 0.453125 0.437500 0.445313 0.441406 0.445313 0.443359 0.445313 0.444336 0.445313 0.444824 0.445313 total iterator time is:11 a root of equation is :0.444824   2迭代法： 迭代法首先要求方程能够化到x=fi(x)的形式，并且还要保证这个式子在所给定的区间范围内满足收敛要求. 主要的迭代过

6、程是简单的，就是: x_k+1=fi(xk) 当xk+1-xk满足精度要求时，则表示已找到方程的近拟根. Type iteratorMethod(Type downLimit,Type upLimit,Type precise,Type (*fiArguF)(Type),FILE* outputFile) Type xk; int iteratorNum=0; assertF(downLimit<=upLimit,"in iteratorMethod x1>=x2"); assertF(fiArguF!=NULL,"in iteratorMethod

7、arguF is NULL"); assertF(outputFile!=NULL,"in iteratorMethod outputFile is NULL"); xk=downLimit; fprintf(outputFile,"kttXkttrn"); fprintf(outputFile,"%-12d%-12frn",iteratorNum,xk); iteratorNum+; while(fabs(*fiArguF)(xk)-xk)>(float)1/(float)2*precise) /*in mathem

8、atic,reason:*/ /* xk_1=(*fiArguF)(xk); */ xk=(*fiArguF)(xk); fprintf(outputFile,"%-12d%-12frn",iteratorNum,xk); iteratorNum+; fprintf(outputFile,"root finded at x=%frn",xk); return xk;   测试2：用迭代法求解方程 f(x)=1/(x+1)2的近似根. 根的有效区间在(0.4,0.55). 精度为0.0001. Output: kXk 0 0.40000

9、0 1 0.510204 2 0.438459 3 0.483287 4 0.454516 5 0.472675 6 0.461090 7 0.468431 8 0.463759 9 0.466724 10 0.464839 11 0.466037 12 0.465276 13 0.465759 14 0.465452 15 0.465647 16 0.465523 17 0.465602 18 0.465552 root finded at x=0.465552   3Aitken加速法 Aitken也是基于迭代法的一种求根方案，所不同的是它在迭代式的选取上做了一些工作，

10、使得迭代的速度变得更快. Type AitkenAccMethod(Type startX,Type precise,Type (*fiArguF)(Type),FILE* outputFile) Type xk; int iteratorNum=0; assertF(fiArguF!=NULL,"in AitkenAccMethod arguF is NULL"); assertF(outputFile!=NULL,"in AitkenAccMethod outputFile is NULL"); xk=startX; fprintf(outputFi

11、le,"kttXkttrn"); fprintf(outputFile,"%-12d%-12frn",iteratorNum,xk); iteratorNum+; while(fabs(*fiArguF)(xk)-xk)>(float)1/(float)2*precise) xk=(xk*(*fiArguF)(*fiArguF)(xk)-(*fiArguF)(xk)*(*fiArguF)(xk)/(*fiArguF)(*fiArguF)(xk)-2*(*fiArguF)(xk)+xk); fprintf(outputFile,"%-12d

12、%-12frn",iteratorNum,xk); iteratorNum+; fprintf(outputFile,"root finded at x=%frn",xk); return xk;   测试3:Aitken迭代加速算法的应用 计算的是方程 x=1/(x+1)2在x=0.4附近的近似根. 精度:0.0001 Ouput: kXk 0 0.400000 1 0.466749 2 0.465570 root finded at x=0.465570     4牛顿求根法: 牛顿求根法通过对原方程

13、切线方程的变换，保证了迭代结果的收敛性，唯一麻烦的地方是要提供原函数的导数: Type NewTownMethod(Type startX,Type precise,Type (*fiArguF)(Type),Type (*fiArguFDao)(Type),FILE* outputFile) Type xk; int iteratorNum=0; assertF(fiArguF!=NULL,"in NewTownMethod,arguF is NULLn"); assertF(fiArguFDao!=NULL,"in NewTownMethod,fiArguFD

14、ao is NULLn"); assertF(outputFile!=NULL,"in NewTownMethod,fiArguFDao is NULLn"); xk=startX; fprintf(outputFile,"kttXkttrn"); fprintf(outputFile,"%-12d%-12frn",iteratorNum,xk); iteratorNum+; while(fabs(*fiArguF)(xk)/(*fiArguFDao)(xk)>(float)1/(float)2*precise) /*

15、 Core Maths Reason Xk+1=Xk-f(Xk)/f'(Xk); */ xk=xk-(*fiArguF)(xk)/(*fiArguFDao)(xk); fprintf(outputFile,"%-12d%-12frn",iteratorNum,xk); iteratorNum+; fprintf(outputFile,"root finded at x=%frn",xk); return xk;   测试4：牛顿求根法的应用: 被求方程为：f(x)=x(x+1)2-1=0 其导数为：f'(x)=(x+1

16、)(3x+1) 所求其在0.4附近的近似根. 精度为0.00001 Output: kXk 0 0.400000 1 0.470130 2 0.465591 3 0.465571 root finded at x=0.465571   5割线法（快速弦截法）: 是用差商来代替避免求f(x)的一种方案,由这种迭代式产生的结果序列一定是收敛的. Type geXianMethod(Type down,Type up,Type precise,Type (*fiArguF)(Type),FILE* outputFile) Type xk,xk_1,tmpData; int ite

17、ratorNum=0; assertF(fiArguF!=NULL,"in geXian method,fiArguF is nulln"); assertF(outputFile!=NULL,"in geXian method,outputFile is nulln"); assertF(down<=up,"in geXian method,down>upn"); xk_1=down; xk=up; fprintf(outputFile,"kttXk_1ttXkttrn"); fprintf(outp

18、utFile,"%-12d%-12f%-12frn",iteratorNum,xk_1,xk); iteratorNum+; while(fabs(xk-xk_1)>(float)1/(float)2*precise) tmpData=xk; xk=xk-(*fiArguF)(xk)*(xk-xk_1)/(*fiArguF)(xk)-(*fiArguF)(xk_1); xk_1=tmpData; fprintf(outputFile,"%-12d%-12f%-12frn",iteratorNum,xk_1,xk); iteratorNum+; fprintf(outputFile,"root finded at x=%frn",xk); return xk; 测试5:割线法的应用: 所求的方程为: f(x)