[数值算法]求根算法系列小结
[数值算法]求根算法系列小结
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<=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;
}
测试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)的形式，并且还要保证这个式子在所给定的区间范围内满足收敛要求.
主要的迭代过程是简单的，就是:
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 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;
}
测试2：用迭代法求解方程
f(x)=1/(x+1)^2的近似根.
根的有效区间在(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;
}
测试3:Aitken迭代加速算法的应用
计算的是方程
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牛顿求根法:
牛顿求根法通过对原方程切线方程的变换，保证了迭代结果的收敛性，唯一麻烦的地方是要提供原函数的导数:
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;
}
测试4：牛顿求根法的应用:
被求方程为：f(x)=x(x+1)^2-1=0
其导数为：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割线法（快速弦截法）:
是用差商来代替避免求f’(x)的一种方案,由这种迭代式产生的结果序列一定是收敛的.
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;
}
测试5:割线法的应用:
所求的方程为:
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
//如果上面这个链接无法响应下载（有可能是被网站给屏蔽掉了），则可使用下载工具（如迅雷等）下载。
