解：
1、黄金分割法
思想：
黄金分割法是通过不断缩短搜索区间的长度来寻求一维函数的极小点，这种方法的基本原理是：在搜索区间[a,b]内按如下规则对称地取两点a1和a2
a1=a+0.382(b-a); a2=a+0.618(b-a);
黄金分割法的搜索过程是：
1） 给出初始搜索区间 [a , b] 及收敛精度 eps ，将 λ赋以0.618
2） 计算a1 和 a2，并计算起对应的函数值 f(a1),f(a2); ，
3） 根据期间消去法原理缩短搜索区间，为了能用原来的坐标点计算公式，需进行区间名城的代换，并在保留区间中计算一个新的试验点及其函数值。
4） 检查区间是否缩短到足够小和函数值收敛到足够近，如果条件不满足则返回到步骤2。
5） 如果条件满足，则取最后两试验点的平均值作为极小点的数值近似解。
黄金分割法的流程图
以f（x）= xx-5x+2 为例，
源程序如下：
#include<iostream>
using namespace std;
const float EPS=0.000001;//定义常量
float f(float);
//定义函数f
float f(float x){
return x*x-5*x+2;
}
int main()
{
float a,b,x1,x2,f1,f2,t,eps;
cout<<"a=";cin>>a;
cout<<"b=";cin>>b;
cout<<"eps=";cin>>eps;
x1=a+0.382*(b-a);
x2=a+0.618*(b-a);
f1=f(x1);
f2=f(x2);
while (b-a>eps)//搜索精度循环节
{
t=f1-f2;
if (t>EPS) {a=x1;x1=x2;f1=f2;x2=a+0.618*(b-a);f2=f(x2);}
else if (t>=-EPS && t<=EPS) {
a=x1;
b=x2;
x1=a+0.382*(b-a);
x2=a+0.618*(b-a);
f1=f(x1);
f2=f(x2);
}//函数值相等,两边区间均舍去
else {
b=x2;
x2=x1;
f2=f1;
x1=a+0.382*(b-a);
f1=f(x1);
}
}
cout<<"x*="<<(a+b)/2;
return (a+b)/2;
system ("pause");
}
运行截图如下：
2、平分法
思想：
平分法要求函数f（x）在区间[a ,b]上为下单峰函数且具有连续的一阶导数。每迭代一次可去掉区间的二分之一。
设f（x）在区间[a ,b]上一阶导数连续，且f ’(a)<0,f’(b)>0。则取c=1/2（a + b），计算f ’©。
若f ’©=0,则c是极小值点；
若f ’©<0,则在[c ,b]内有极小点，保留区间[c ,b]；
若f ’©>0,则在[a ,c]内有极小点，保留区间[a ,c]。
把保留下来的区间仍记为[a ,b]，重复前面的过程，知道区间[a ,b]的长度充分小，满足所要求的精度为止。
其算法过程如下 ：
已知 a ，b 且 a <b ,f’(a)<0 ,f’(b)>0及e>0。
- c=1/2(a + b)，转2。
- 若b-a≤e，则转4；否则转3。
- 计算f’©。若f’©=0,则转4；
若f’©<0,则令a=c，转1；
若f’©>0,则令b=c，转1。 - 令 x* =c。结束。
平分法的流程图
源程序如下：
#include<stdio.h>
#include<math.h>
//定义f(x)函数
double f(double x){
return x*x+2*x+1;
}
//定义f(x)的导函数g(x)
double g(double x){
double dx=0.001,dy,dd1,dd2;
dy=f(x+dx)-f(x);
dd1=dy/dx;
Lab:
dx=0.5*dx;//减小步长
dy=f(x+dx)-f(x);
dd2=dy/dx;//导数新值
if(fabs(dd1-dd2)<1e-06) return dd2;
else {dd1=dd2;goto Lab;};
}
int main() {
double x0,f0,a=-1,b=2,c,d=0.001;
int n;
c=(a+b)/2;
while(fabs(b-a)>d){
//判断求导
if(g(c)==0) n=0;
else if(g(c)>0) n=1;
else if(g(c)<0) n=2;
switch(n) {
case 0:
break;
case 1:
b=c;
c=(a+b)/2;
break;
case 2:
a=c;
c=(a+b)/2;
break;
}
}
x0=c;
f0=f(c);
printf("f(x)的最小值点在%f\n",x0);
printf("f(x)的最小值为%f\n",f0);
printf("%f",g(2));
return 0;
}
3.不精确一维搜索
程序基本思想：
源程序如下：
#include <iostream.h>
double f(double x1 , double x2)
{
double result;
result = 100 * (x2 - x1 * x1) * (x2 - x1 * x1) + (1 - x1) * (1 - x1);
return result;
}
double g1(double x1 , double x2)
{
double result;
result = (-1) * 400 * (x2 - x1 * x1) * x1 - 2 * (1 - x1);
return result;
}
double g2(double x1 , double x2)
{
double result;
result = 200 * (x2 - x1 * x1);
return result;
}
double linesearch()
{
double u, m, a, b, n, j ,best,min=0;
double x1 , x2 ;
u = 0.1 , m = 0.7;
a = 0 , b = 999999999 ;
n= 1 , j = 0 ;
int flag=1;
x1 = -1 , x2 = 1 ;
while( flag)
{
if( ( f(x1, x2) - f(n + x1, n + x2) + u*n*(g1(x1, x2) + g2(x1, x2)) ) < 0 && ( g1(x1 + n, x2 + n) + g2(x1 + n, x2 + n) - m*(g1(x1, x2) + g2(x1, x2))) >= 0 )
{
j = j + 1;
cout<<j<<" " ;
b = n;
n = 0.5 * (a + n);
flag=1;
cout<<n<<" "<<f(n + x1, n + x2)<<endl;
}
if( ( f(x1, x2) - f(n + x1, n + x2) + u*n*(g1(x1, x2) + g2(x1, x2)) ) >= 0 && ( g1((x1 + n), (x2 + n)) + g2((x1 + n), (x2 + n)) - m*(g1(x1, x2) + g2(x1, x2))) < 0 )
{
j = j + 1;
cout<<j<<" ";
a = n;
if( (2 * n - (a + b) * 0.5) > 0 )
{
n = (a + b) * 0.5;
}
else
{
n = 2 * n;
}
flag=1;
cout<<n<<" "<<f(n + x1, n + x2)<<endl;
}
else if(( f(x1, x2) - f(n + x1, n + x2) + u*n*(g1(x1, x2) + g2(x1, x2)) ) >= 0 && ( g1((x1 + n), (x2 + n)) + g2((x1 + n), (x2 + n)) - m*(g1(x1, x2) + g2(x1, x2))) >=0 )
{
best = n;
min=f(x1+best,x2+best);
flag=0;
cout<<"根据给定条件，不精确一维搜索的步长为:"<<best<<endl;
}
}
return min;
}
int main()
{
double bestresult;
cout<<" 函数为Y = 100(x2-x1*x1)*(x2-x1*x1)+(1-x1)*(1-x1)"<<endl;
bestresult=linesearch();
cout<<"根据给定条件，不精确一维搜索后的最小值为："<<bestresult<<endl;
}
程序运行情况如下：
结果为：步长=0.00390625，最小值为3.99809
