0.618与二分法的学习
- 格式:doc
- 大小:332.00 KB
- 文档页数:11
0.618法的实例研究:
一、算法理论
黄金分割法是用于一元函数)(x f 在确定的初始区间],[b a 内搜索极小点a '的一种方法。它是优化计算中的经典算法,以算法简单、效果明显而著称,是许多优化算法的基础。但它只适用于某个区间上的凸函数。其基本思想是:依照“去坏留好”原则,对
称原则,以及等比收缩原则来逐步缩小搜索范围。
0.618法适用于单峰区间函数,即所在区间],[b a 上。具体的说,对于单峰函数,只需选择两个试探点,即在区间],[b a 中取点)(382.01a b a x -+=,
)(618.02a b a x -+=,
且21x x <,就可以将包含极小点*
x 的区间缩短。事实上,必有:若)()(21x f x f >,则],[1*b x x ∈;若)()(21x f x f ≤,则],[2*
x a x ∈。
根据单峰函数这个性质,就可以不断迭代缩小包含极小点的区间。若进行k 次迭代
后,有],[*
k k b a x ∈,那么我们在区间],[k k b a 取两个试探点)(382.01a b a x -+=,
)(618.02a b a x -+=,且21x x <,计算)(),(21x f x f 的值。如果)()(21x f x f =,令
b x a x ==21,,那么计算||b a -,如果ξ≤-||b a (ξ为所给的精度)
,则*
2
x b a =+;
如果 )()(21x f x f >,令11x a k =+,k k b b =+1;如果)()(21x f x f <,令k k a a =+1,
21x b k =+,如此继续。这样每次可将搜索区间缩小0.328倍或者0.618倍,直至缩为一
点。黄金分割原理如图1所示,其中618.0=K ,区间长度为L 。该算法为收敛速度很
快的一种搜索方法。
图1.
二、算法框图
三、算法程序
用10
x
f,区间为]8,2[,e取0.01为例x
=x
-
)
(2+
7
用C语言编程程序如下:
#include
#include
#include
#define f(x) x*x-7*x+10
double hj(double *a,double *b,double e,int *n)
{
double x1,x2,s;
if(fabs(*b-*a)<=e)
s=f((*b+*a)/2);
else
{
x1=*a+0.382*(*b-*a);
x2=*a+0.618*(*b-*a);
if(f(x1)>f(x2))
*a=x1;
else
*b=x2;
*n=*n+1;
s=hj(a,b,e,n);
}
return s;
}
main()
{
double s,a,b,e;
int n=0;
printf("Please input left boundary right boundary precision:\n"); scanf("%lf%lf%lf",&a,&b,&e);//输入区间和精度的值
s=hj(&a,&b,e,&n);//调用hj函数,其中n代表迭代次数
printf("a=%lf,b=%lf,s=%lf,n=%d\n",a,b,s,n);
}
四、算法实现
方程为10
x
x
=x
f,区间是]8,2[,精度是0.01。
7
-
)
(2+
解:运行程序
(1)输入2 8 0.01
(2)显示出运行结果
二分法求解单变量非线性方程及其应用与实现:
1. 引言
在科学研究与工程技术中常会遇到求解非线性方程f(x)=0的问题。而方程f(x)是多项式或超越函数又分为代数方程或超越方程。对于不高于四次的代数方程已有求根公式,而高于四次的代数方程则无精确的求根公式,至于超越方程就更无法求其精确解了。因此,如何求得满足一定精度要求的方程的近似根也就成为了我们迫切需要解决的问题。近年来,随着数学科学研究的不断进展,又更新了许多方程求解的方法。我们知道,对于单变量非线性方程f(x)
=0,一般都可采用迭代法求根,由此产生了二分法。
2. 二分法
一般地,对于函数f(x),如果存在实数c,当x=c时f(c)=0,那么把x=c叫做函数f(x)的零点。
解方程即要求f(x)的所有零点。
先找到a、b,使f(a),f(b)异号,说明在区间(a,b)内一定有零点,然后求f[(a+b)/2], 现在假设f(a)<0,f(b)>0,a
①如果f[(a+b)/2]=0,该点就是零点,
如果f[(a+b)/2]<0,则在区间((a+b)/2,b)内有零点,(a+b)/2=>a,从①开始继续使用中点函数值判断。
如果f[(a+b)/2]>0,则在区间(a,(a+b)/2)内有零点,(a+b)/2=>b,从①开始继续使用中点函数值判断。
这样就可以不断接近零点。
通过每次把f(x)的零点所在小区间收缩一半的方法,使区间的两个端点逐步迫近函数的零点,以求得零点的近似值,这种方法叫做二分法。
给定精确度ξ,用二分法求函数f(x)零点近似值的步骤如下:
1. 确定区间[a,b],验证f(a)•f(b)<0,给定精确度ξ.
2. 求区间(a,b)的中点c.