[數值算法]求根算法系列小結

1、精選文檔數值算法求根算法系列小結 1二分求根法:二分求根法主要用的思想是不斷調整并縮小搜索區(qū)間的大小，當搜索區(qū)間的大小已小于搜索精度要求時，則可說明已找到滿足條件的近擬根.當然，在這之前，首先是要準確的估計出根所處的區(qū)間，否則，是找不到根的。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)的形式，并且還要保證這個式子在所給定的區(qū)間范圍內滿足收斂要求. 主要的迭代過

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的近似根. 根的有效區(qū)間在(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)