0618与二分法的学习.doc

0.618法的实例研究: 一、算法理论 黄金分割法是用于一元函数在确定的初始区间内搜索极小点的一种方法。它是优化计算中的经典算法，以算法简单、效果明显而著称，是许多优化算法的基础。但它只适用于某个区间上的凸函数。其基本思想是：依照“去坏留好”原则，对称原则，以及等比收缩原则来逐步缩小搜索范围。 0.618法适用于单峰区间函数，即所在区间上。具体的说，对于单峰函数，只需选择两个试探点，即在区间中取点，，且，就可以将包含极小点的区间缩短。事实上，必有：若，则；若，则。 根据单峰函数这个性质，就可以不断迭代缩小包含极小点的区间。若进行次迭代后，有，那么我们在区间取两个试探点，，且，计算的值。如果，令，那么计算，如果（为所给的精度），则；如果 ，令，；如果，令，，如此继续。这样每次可将搜索区间缩小0.328倍或者0.618倍，直至缩为一点。黄金分割原理如图1所示，其中，区间长度为。该算法为收敛速度很快的一种搜索方法。 图1. 二、算法框图 三、算法程序 用，区间为，取0.01为例 用C语言编程程序如下： #include stdio.h #include math.h #include stdlib.h #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); } 四、算法实现 方程为，区间是，精度是0.01。 解：运行程序 输入2 8 0.01 显示出运行结果 二分法求解单变量非线性方程及其应用与实现:　 　　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,ab 　　①如果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. 　　3. 计算f(c). 　　(1) 若f(c)=0,则c就是函数的零点; 　　(2) 若f(a)?f(c)0,则令b=c; 　　(3) 若f(c)?f(b)0,则令a=c. 　　4. 判断是否达到精确度ξ:即若┃a-b┃ξ,则得到零点近似值a(或b),否则重复2-4. 　　由于计算过程的具体运算复杂，但每一步的方式相同，所