一维搜索方法的分类如下：
这篇文章主要讲解
黄金分割法、二分法、牛顿法这三种一维搜索方法。黄金分割法只用到原函数，二分法用到函数的一阶导，牛顿法用到函数的二阶导。由于本文主要对研一上学期的课程中的部分算法进行程序实现，
理论部分大多参考上课的课件。
黄金分割法
基本概念：
算法思想：
算法流程图及优缺点如下：
二分法
基本思想：
牛顿法
基本思想：
算法流程图：
具体实现：
下面我们通过程序具体实现，
在程序中，我们设置原函数都是f(x)=sinx/x，搜索区间都是[0,1]，牛顿法中假设初始值设为1,具体程序如下所示：
#include<stdio.h>
#include<math.h>
/********************函数的定义、一阶导、二阶导的模块 BEGIN*************************/
/*****************************\
输入：x为自变量
输出：x自变量对应的函数值
\*****************************/
double Function(double x)
{
return (x-0.5)*(x-0.5);//这里填写函数式f(x),根据自己的函数修改
}
/*****************************\
输入：x为自变量
输出：x自变量对应的一阶导数值
\*****************************/
double Derivative(double x)//求函数的一阶导数
{
double eps=0.0000001;//精度控制
double dx=0.5;//设置初始的间隔，太大需要迭代多次，太小缺乏精度
double dy=Function(x+dx)-Function(x);//函数值的增量
double dd1=dy/dx;//导数
double dd2=0;//dx变化时的导数
dx=dx/2;//不断地减少x的增量
dy=Function(x)-Function(x+dx);
dd2=dy/dx;//计算新的导数值
while(abs(dd1-dd2)>eps)//当相邻两次的导数值小于精度时终止迭代，得到导数
{
dd1=dd2;
dx=dx/2.0;
dy=Function(x+dx)-Function(x);
dd2=dy/dx;
}
return dd2;
}
//求函数的2阶导数,与求一阶导数的原理一样，只需要把求函数值的函数Function换成求一阶导数的函数Derivative
/*****************************\
输入：x为自变量
输出：x自变量对应的二阶导数值
\*****************************/
double Derivative2(double x)
{
double eps=0.00000001;
double dx=0.5;
double dy=Derivative(x+dx)-Derivative(x);
double dd1=dy/dx;
double dd2=0;
dx=dx/2;
dy=Derivative(x)-Derivative(x+dx);
dd2=dy/dx;
while(abs(dd1-dd2)>eps)
{
dd1=dd2;
dx=dx/2.0;
dy=Derivative(x+dx)-Derivative(x);
dd2=dy/dx;
}
return dd2;
}
/********************函数的定义、一阶导、二阶导的模块 END*************************/
/******************************************\
输入：a，b为区间的上下限，n为最大的迭代次数
输出：打印函数最小值及对应的自变量x
\******************************************/
void GoldenSection(double a,double b,int n)//黄金分割法
{
double l=a+0.382*(b-a);
double h=a+0.618*(b-a);
double region=b-a;
double fl;
double fh;
int num=1;//迭代次数
while(region>0.0000000001&&num<n)
{
fl=Function(l);
fh=Function(h);
if(fl>fh)
{
a=l;
l=h;
h=a+0.618*(b-a);
}
else
{
b=h;
h=l;
l=a+0.382*(b-a);
}
num++;
region=abs(b-a);
}
if(num==n)
printf("找不到最小值");
else
{
printf("黄金分割法:x=%f时，最小值f(x)=%f",(a+b)/2,Function((a+b)/2));
}
}
/******************************************\
输入：a，b为区间的上下限
输出：打印函数最小值及对应的自变量x
\******************************************/
void Dichotomy(double a,double b)//二分法
{
double eps=0.0000001;
double x=(a+b)/2;
double region=b-a;
double fxDerivative= Derivative(x);
while(region>0.0000001&&abs(fxDerivative)>eps)
{
fxDerivative= Derivative(x);
if(fxDerivative>eps)
b=x;
if(fxDerivative<-eps)
a=x;
x=(a+b)/2;
region=abs(b-a);
}
printf("\n\n二分法：x=%f时，f(x)=%f\n",x,Function(x));
}
/******************************************\
输入：a，b为区间的上下限，x1是初始值
输出：打印函数最小值及对应的自变量x
\******************************************/
void Newton(double a,double b,double x1)
{
double eps=0.0000001;
double x=x1;
double d1=Derivative(x1);//一阶导
double d2;//二阶导
while(abs(d1)>eps)
{
d2=Derivative2(x);
if(d2<0)
printf("二阶导小于0，无法求解");
else
{
x=x-d1/d2;//x迭代公式
d1=Derivative(x);
}
}
printf("\n牛顿法：x=%f时，f(x)=%f\n\n",x,Function(x));
}
void main()
{
GoldenSection(0,1,100000);//黄金分割法
Dichotomy(0,1);//二分法
Newton(0,1,1);//牛顿法
}
运行结果如下图：
原文：http://blog.csdn.net/tengweitw/article/details/43488767
作者：nineheadedbird
