[数值算法]求根算法系列小结[互联网+]

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; up=x2; assertF(x1

2、=x2); assertF(arguF!=NULL,in twoPation arguF is NULL); assertF(outputFile!=NULL,in twoPation outputFile is NULL); assertF(*arguF)(x1)*(*arguF)(x2)0); fprintf(outputFile,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=(do

3、wn+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); iteratorNum+; /*get the answer*/ x=mid; /*Output Answer*/ fprintf(outputFile,total iterator time is:%drn,iteratorNum); fprintf(outputFile,a root of equation is

4、:%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.500000 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 t

5、ime is:11 a root of equation is :0.444824 2迭代法： 迭代法首先要求方程能够化到x=fi(x)的形式，并且还要保证这个式子在所给定的区间范围内满足收敛要求. 主要的迭代过程是简单的，就是: 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(down

6、Limit=x2); assertF(fiArguF!=NULL,in iteratorMethod 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 m

7、athematic,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.400000 1 0.510204 2 0.438459 3 0.483

8、287 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也是基于迭代法的一种求根方案，所不同的是它在迭代式的选取上做了一些工作，使得迭代的速度变得更快. Type AitkenAccMethod(Type star

9、tX,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(outputFile,kttXkttrn); fprintf(outputFile,%-12d%-12frn,iteratorNum,xk); ite

10、ratorNum+; 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%-12frn,iteratorNum,xk); iteratorNum+; fprintf(outputFile,root finded at x=%frn,xk); return xk; 测试3:A

11、itken迭代加速算法的应用 计算的是方程 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牛顿求根法: 牛顿求根法通过对原方程切线方程的变换，保证了迭代结果的收敛性，唯一麻烦的地方是要提供原函数的导数: Type NewTownMethod(Type startX,Type precise,Type (*fiArguF)(Type),Type (*fiArguFDao)(Type),FILE* outputFile) Type xk

12、; int iteratorNum=0; assertF(fiArguF!=NULL,in NewTownMethod,arguF is NULLn); assertF(fiArguFDao!=NULL,in NewTownMethod,fiArguFDao is NULLn); assertF(outputFile!=NULL,in NewTownMethod,fiArguFDao is NULLn); xk=startX; fprintf(outputFile,kttXkttrn); fprintf(outputFile,%-12d%-12frn,iteratorNum,xk); iter

13、atorNum+; while(fabs(*fiArguF)(xk)/(*fiArguFDao)(xk)(float)1/(float)2*precise) /* 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：牛顿求根法的应用: 被求

14、方程为：f(x)=x(x+1)2-1=0 其导数为：f(x)=(x+1)(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 x

15、k,xk_1,tmpData; int iteratorNum=0; assertF(fiArguF!=NULL,in geXian method,fiArguF is nulln); assertF(outputFile!=NULL,in geXian method,outputFile is nulln); assertF(downupn); xk_1=down; xk=up; fprintf(outputFile,kttXk_1ttXkttrn); fprintf(outputFile,%-12d%-12f%-12frn,iteratorNum,xk_1,xk); iteratorNum

16、+; 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)=x*(x+1)2-1=0 寻根范围:0.4,0.6 精度:0.00001 O