黄金分割法

黄金分割法也叫0.618法，它是一种基于区间收缩的极小值点搜索算法，当用进退法确定搜索区间后，我们只知道极小值点包含于搜索区间内，但是具体是哪个点，无法得知。

1. 算法原理

黄金分割法的思想很直接，既然极小值点包含于搜索区间内，那么可以不断地缩小搜索区间，就可以使搜索区间的端点逼近到极小值点。

?a,b?为搜索区间，黄金分割法首先根据黄金比例产生两个内点x1,x2。

x1?a?0.382*(b?a)x2?a?0.618*(b?a)

然后根据f?x1?，f?x2?的大小关系来重新选择搜索区间。 （1） 若f?x1??f?x2?，则搜索区间变为[x1,b]； （2） 若f?x1??f?x2?，则搜索区间变为[a,x2]。

2. 算法步骤

用黄金分割法求无约束问题minf(x),x?R的基本步骤如下： （1） 选定初始区间[a1,b1]及精度??0，计算试探点：

?1?a1?0.382*(b1?a1)

?1?a1?0.618*(b1?a1)。

（2） 若bk?ak??，则停止计算。否则当f。 f??k??f??k?转步骤（4）

（3） 置

??k??f??k?时转步骤（3）。当

?ak?1??k?b?b?k?1k转步骤（5） ???k?1??k???k?1?ak?1?0.382*(bk?1?ak?1)（4） 置

?ak?1?ak?b???k?1k转步骤（5） ???k?1??k???k?1?ak?1?0.382*(bk?1?ak?1)（5） 令k?k?1，转步骤（2）。

3. 算法的MATLAB实现

在MATLAB中编程实现黄金分割法的函数为：minHJ。

功能：用黄金分割法求解一维函数的极值。 调用格式：[x,minf]?minHJ(f,a,b,eps) 其中，f：为目标函数； a：极值区间的左端点； b：极值区间的右端点； eps：精度；

x：目标函数取最小值时的自变量值；

minf：目标函数的最小值。 黄金分割法的MATLAB程序代码如下： function [x,minf]=minHJ(f,a,b,eps) %目标函数;f；

%极值区间的左端点:a； %极值区间的右端点:b； %精度:eps；

%目标函数取最小值时的自变量值:x； %目标函数的最小值:minf; format long; if nargin==3 eps=1.0e-6; end

l=a+0.382*(b-a); %试探点 u=a+0.618*(b-a); %试探点 k=1; tol=b-a;

while tol>eps && k<100000

fl=subs(f,findsym(f),l); %试探点函数值 fu=subs(f,findsym(f),u); %试探点函数值 if fl>fu

a=l; %改变区间左端点 l=u;

u=a+0.618*(b-a); %缩短搜索区间 else

b=u; %改变区间右端点 u=l;

l=a+0.382*(b-a); %缩短搜索区间 end k=k+1;

tol=abs(b-a); end

if k==100000

disp('找不到最小值!'); x=NaN; minf=NaN; end

x=(a+b)/2;

minf=subs(f,findsym(f),x); format short; 例：

f(t)?(t2?1)2?(t?1)2?3?t4?t2?2t?5,其中t?[?10,10]。

解：在MATLAB命令窗口中输入命令： syms t;

f=t^4-t^2-2*t+5; [x,fx]=minHJ(f,-10,10)

所得结果为： x =

1.0000 fx =

3.0000