?? 求根算法系列小結(jié).txt
字號(hào):
[數(shù)值算法]求根算法系列小結(jié)
1二分求根法:
二分求根法主要用的思想是不斷調(diào)整并縮小搜索區(qū)間的大小，當(dāng)搜索區(qū)間的大小已小于搜索精度要求時(shí)，則可說(shuō)明已找到滿足條件的近擬根.
當(dāng)然，在這之前，首先是要準(zhǔn)確的估計(jì)出根所處的區(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;
up=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,"down\t\tup\t\t\r\n");
/*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%-12f\r\n",down,up);
iteratorNum++;
}
/*get the answer*/
x=mid;
/*Output Answer*/
fprintf(outputFile,"total iterator time is:%d\r\n",iteratorNum);
fprintf(outputFile,"a root of equation is :%f\r\n",x);
return x;
}
測(cè)試1：用二分法求:
f(x)=x^3-x^2-2*x+1=0在(0,1)附近的根.
精度:0.001.
Output:
down up
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 time is:11
a root of equation is :0.444824
2迭代法：
迭代法首先要求方程能夠化到x=fi(x)的形式，并且還要保證這個(gè)式子在所給定的區(qū)間范圍內(nèi)滿足收斂要求.
主要的迭代過(guò)程是簡(jiǎn)單的，就是:
x_k+1=fi(xk)
當(dāng)xk+1-xk滿足精度要求時(shí)，則表示已找到方程的近擬根.
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 arguF is NULL");
assertF(outputFile!=NULL,"in iteratorMethod outputFile is NULL");
xk=downLimit;
fprintf(outputFile,"k\t\tXk\t\t\r\n");
fprintf(outputFile,"%-12d%-12f\r\n",iteratorNum,xk);
iteratorNum++;
while(fabs((*fiArguF)(xk)-xk)>(float)1/(float)2*precise)
{
/*in mathematic,reason:*/
/*
xk_1=(*fiArguF)(xk);
*/
xk=(*fiArguF)(xk);
fprintf(outputFile,"%-12d%-12f\r\n",iteratorNum,xk);
iteratorNum++;
}
fprintf(outputFile,"root finded at x=%f\r\n",xk);
return xk;
}
測(cè)試2：用迭代法求解方程
f(x)=1/(x+1)^2的近似根.
根的有效區(qū)間在(0.4,0.55).
精度為0.0001.
Output:
k Xk
0 0.400000
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也是基于迭代法的一種求根方案，所不同的是它在迭代式的選取上做了一些工作，使得迭代的速度變得更快.
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(outputFile,"k\t\tXk\t\t\r\n");
fprintf(outputFile,"%-12d%-12f\r\n",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%-12f\r\n",iteratorNum,xk);
iteratorNum++;
}
fprintf(outputFile,"root finded at x=%f\r\n",xk);
return xk;
}
測(cè)試3:Aitken迭代加速算法的應(yīng)用
計(jì)算的是方程
x=1/(x+1)^2在x=0.4附近的近似根.
精度:0.0001
Ouput:
k Xk
0 0.400000
1 0.466749
2 0.465570
root finded at x=0.465570
4牛頓求根法:
牛頓求根法通過(guò)對(duì)原方程切線方程的變換，保證了迭代結(jié)果的收斂性，唯一麻煩的地方是要提供原函數(shù)的導(dǎo)數(shù):
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 NULL\n");
assertF(fiArguFDao!=NULL,"in NewTownMethod,fiArguFDao is NULL\n");
assertF(outputFile!=NULL,"in NewTownMethod,fiArguFDao is NULL\n");
xk=startX;
fprintf(outputFile,"k\t\tXk\t\t\r\n");
fprintf(outputFile,"%-12d%-12f\r\n",iteratorNum,xk);
iteratorNum++;
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%-12f\r\n",iteratorNum,xk);
iteratorNum++;
}
fprintf(outputFile,"root finded at x=%f\r\n",xk);
return xk;
}
測(cè)試4：牛頓求根法的應(yīng)用:
被求方程為：f(x)=x(x+1)^2-1=0
其導(dǎo)數(shù)為：f'(x)=(x+1)(3x+1)
所求其在0.4附近的近似根.
精度為0.00001
Output:
k Xk
0 0.400000
1 0.470130
2 0.465591
3 0.465571
root finded at x=0.465571
5割線法（快速弦截法）:
是用差商來(lái)代替避免求f’(x)的一種方案,由這種迭代式產(chǎn)生的結(jié)果序列一定是收斂的.
Type geXianMethod(Type down,Type up,Type precise,Type (*fiArguF)(Type),FILE* outputFile)
{
Type xk,xk_1,tmpData;
int iteratorNum=0;
assertF(fiArguF!=NULL,"in geXian method,fiArguF is null\n");
assertF(outputFile!=NULL,"in geXian method,outputFile is null\n");
assertF(down<=up,"in geXian method,down>up\n");
xk_1=down;
xk=up;
fprintf(outputFile,"k\t\tXk_1\t\tXk\t\t\r\n");
fprintf(outputFile,"%-12d%-12f%-12f\r\n",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%-12f\r\n",iteratorNum,xk_1,xk);
iteratorNum++;
}
fprintf(outputFile,"root finded at x=%f\r\n",xk);
return xk;
}
測(cè)試5:割線法的應(yīng)用:
所求的方程為:
f(x)=x*(x+1)^2-1=0
尋根范圍:[0.4,0.6]
精度:0.00001
Output:L
k Xk_1 Xk
0 0.400000 0.600000
1 0.600000 0.457447
2 0.457447 0.464599
3 0.464599 0.465579
4 0.465579 0.465571
5 0.465571 0.465571
root finded at x=0.465571
我的演示程序的源碼下載:
http://free3.e-168.cn/as2forward/downloads/feature_FindRoot.rar
//如果上面這個(gè)鏈接無(wú)法響應(yīng)下載（有可能是被網(wǎng)站給屏蔽掉了），則可使用下載工具（如迅雷等）下載。
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=473718
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -