3.2 黄金分割法在线视频

今天我们来学习0.618法

也称为是黄金分割法

好

我们知道0.618我们称为是黄金分割数

那么在蒙娜丽莎的微笑的画像中有很多

0.618的数值

因此说她的微笑是最美的

包括对于欧洲的很多古老的建筑

它的窗户的长宽比例也是0.618

我们也称为是黄金分割

我们看看我们这里边的

优化方法里边的0.618法是什么呢

它的基本思想跟我们之前所学习的区间消去法

的思想是一样的

就是区间消去 逐步缩小单峰区间

这是它的基本思想

方法原理呢

我们是在已知求到的单峰区间ab内

如果它的长度L等于b减a那么也是

在ab内取两点对称的点

X1和X2

我们让aX2等于bX1等于λL

画一个图

我们来看一看

这是我们的单峰区间

区间的两端是a和b

在这里边对称的取两个点X1和X2

同学们注意

这里边是让aX2等于λL 让X1b等于λL

不是aX1 bX2注意这里边的λ取值

那么如果说我们计算既然有了X1和X2的话

带到我们的函数里边就能求出什么

Fx1和Fx2

我们让Fx1等于F1

Fx2等于F2

我们看就像我们PPT上讲的

如果说F1大于F2则我们的新区间为X1b

那么这样的话我们就把换这个形式

我们就换a等于X1

X1等于X2

F1等于F2

然后我们来计算X2

就像我们图上这里边的有了X1 X2

计算F1 计算F2然后进行比较

然后去掉谁呢

这里看看去掉谁呢

去掉了aX1这一段保留X1b这一段

那么这里计算X2等于a加上λb减a

F2等于Fx2

那么因此说我们把原来的ab这样

总长度为L的单峰区间就缩短为了

现在的新的ab

那么这个区间长度我们刚才知道

应该是等于λL

那么这时候我们把这个区间内原来计算过得

X2保留下来就变成了X1

他既然是X1的话

那么就算他的Fx1了

那么这里边我们再重新找一个X2

重新找一个X2计算Fx2

那么缩短长度呢

我们就是新区间

除以原区间的长度

就应该是等于λL除以L就是λ

那么再进行判断

如果说Fx1还是大于Fx2就是F1大于F2呢

则新区间又进一步缩短

缩短成什么

又变成新的X1和b

换名是a等于X

X1等于X2

F1等于F2

那么这样子我们可以再继续

我们看这里边新的区间

新的ab就是取X1b这一段

然后我们X2就变成新的X1

然后这是F1

然后再选取一个X2

再计算选取一个X2

然后这是F2

然后新的区间又是原来这个λL的一半

就是1减去λL

那么删除是aX1这一段

那么缩短距离呢

缩短的缩短率也是新区间长度

除以原n区间的长度就等于什么

1减λL比上λL等于1减λ比上λ

如果说我们让每一次的缩短的

缩短率都相等的时候呢

我们来看一看第一次我们刚才计算地

缩短率是λL比L等于λ

第二次是1减λL比上λ等于1减去λ比上λ

然后如果另两次相等

则有什么呢

λ等于1减λ比上λ

整理一下λ平方减λ减一等于0

很简单

这个题我们可以解一下这个方程

这个得出来什么呢

得出来λ就等于负1加减根号5除以2

等于0.618

刚好就是我们的黄金数0.618的黄金数

看我们这里边数学

我们为了让这个区间等比例缩短

我们最后计算出来刚好就是

我们的0.618这个数

就是我们的黄金数

因此说呢我们这个方法称为是0.618法

这是我们的黄金数

我们通过这个题我们可以看到

通过这个我们节点看到

为什么选取黄金数呢

它的好处是什么呢

我们看到在下一次计算的时候呢

我们有一个点已经算过的保留一个点

你看我们的第一次是选了两个点

X1X2带到函数里边算Fx1和Fx2

但是自此以后的每一次计算呢

每一次的原来的两个点中有一个点就被保留了

而仅需要计算一个新的点计算Fx

那我们想了如果说我们的FX非常复杂

这个函数非常复杂

你每次计算的工作量非常大

那我们用0.618法来计算时候呢

我们每一次只需要计算一个新的点

实际上计算量减少了一半

这就是它的好处

所以说0.618法我们看到它就是

因为用了黄金分割数

使你的计算量减少了一半

速度提升了

那我们也说了

对于一维优化搜索是多维优化搜索一个基础

每一步的多维搜索都要用到多次一维搜索

那你在一维搜索的计算量减少了一半

那么放在整个多维搜索里边

计算量减少就非常明显

你的速度就变得非常快

计算速度非常快

我们看一下黄金分割法的迭代步骤与框图

首先我们得输入ab λ 0.618和精度ε

那么我们以前也说了

精度ε就是你的工程计算中的精度

你是精度到0.01毫米

0.01厘米等等

这是你的精度

首先计算X1和X2

X1等于B减λb减a

X2等于a加上λb减a

带公式就行了

我们的框图就是为了让你编程的时候更容易

然后有了X1有了X2可以算什么

F1等于Fx1

F2等于Fx2

然后怎么办呢

就像我们这图上讲的

X1有了X2有了

Fx1 Fx2有了

下面很简单 比较

看Fx1或者F1是大于F2还是小于F2

如果F1大于F2

就像我们这图上画的

那怎么办

舍去aX1这个区间保留X1b这个区间

那就是什么

把X1变成a了

X2变成X1

b保留再重新求一个X2

那意思说就是我们这里的框图

a等于X1 X1等于X2

F1等于F2只需要求X2

X2怎么求

A加上λb减a

F2等于Fx2

然后我们再继续判断

判断看看新的区间b减a这个区间

是不是小于ε

如果小于ε的怎么办

我们认为这个区间已经足够小小到什么程度

小到你的极值点就在这个区间内的已经非常小

那我认为什么

我认为他们b减a这个区间的中点

0.5倍的b加a就是你的极值了

你就可以输出了

程序结束 end 整个程序就结束了

这是一布分支

那这是什么

是F1大于F2

那么这里边如果说b减a小于ε

它没有小于ε

我们的精度不够

怎么办呢

继续做

继续做在哪

回到了这个地方

我们又重新迭代继续迭代

让区间进一步缩小

一步一步的缩小

最终小到我的区间长度比你的精度要小

那我就认为什么

你这个区间的中点就是你的极值点

第二个分支如果F1小于F2

那么这时候我们知道要什么

去掉是X2b去掉这个区间

保留的是aX2这个区间

那么所以说X2就变成了b

X1就变成了X2

那么原来的F1就变成了F2

那我们现在仅需要

再求出一个新的X1就可以了

那么这里边b等于X2

X2等于X1

F2等于F1

X1等于b减去λb减a

F1等于Fx1

然后继续

那就是接到这边了

我们既然需要新的区间

ab新的区间生成了

已经缩短了λ倍的这样一个区间生成以后呢

我们再判断b减a是不是小于ε

如果是就输出

X星等于0.5倍的b减a就结束

如果不是再循环回去

那我们看整个这样一个过程呢

从框图中我们看出非常简单

易于编程

易于理解

那我们来看看0.618法的特点

那么它的特点包括第一个

每次区间的缩短率都相等

都是λ等于黄金数0.618

这是第一点

第二点每一次只需计算一个新点

我们说的X1或者X2的函数值

另一个点利用上一次的旧的迭代点的信息

这样就是我们刚才说的节省计算时间

能计算时间省一半

第三个刚才讲的通过框图我们能看出来

方法简单

对函数没有特殊的要求

什么意思

第一个框图非常简单

第二个

找到了X1 X2

只要有点我就能带到你的函数里头

我不需要知道你的函数是否可导

是否可微是否可积都无所谓

只要有点我能带进去

你包括函数分段是否连续

我都不用关心

你有点就带进去

带进去就有F值

我整个流程看出来是只需要比较F1F2大小

就可以了

所以说对函数没有特殊的要求

第四

那么既然是简单没有用到的函数的可导性

它的倒数的斜率的关系

那么意思说没有利用函数自身的性态

所以说在实际的计算中

它的收敛速度是比较慢的

那么下面我们来看一个例题

我们来通过例题来讲解一下0.618法

用0.618法

求函数Fx等于X平方减X加2的极小值

我们设定给你了初始区间

ab是等于什么

负1到3这个区间

因为我们说的我们不需要你做很多

我们只需要做一次迭代

我们来看一下这个他的实际计算方法

所以说我们要做一次迭代计算

确定第二次迭代的区间是多少

第一个求X1和X2两点 怎么求

带公式就可以 了

X2等于a加上λb减a

等于负1加上0.618乘以4

等于1.472

X1是等于b减去λb减a

算出来等于0.528

就像图这样子的X1 X2

有了X1X2 带到函数

Fx等于X平方减X加2里头就可以求出来

你这里边的F1和F2求一下

Fx1就是F1等于1.750784

Fx2等于2.694784

这个求得如果我们用编程来说

计算机很好求解

这个求得很快的

下一步怎么办

看我们的框图比较F1和F2

显然这里边的F1是小于F2的

F1小于F2的怎么办呢

是要取哪一段

去掉X2和b这一段的区间

则X2就等于b了

X1等于X2

然后我再找新得X1

那我们这道题注意审题

我们这道题讲的是做一次迭代计算

第二次迭代区间

那我既然确定了去掉X2b的话

那么这个新的区间就是什么呢

所以说第二次迭代的区间为

负1到1.472这个区间

所以由原来的负1到3变成了

负1到1.472这个区间

我们减少了一部分

那么这个题就是我们用0.618法

把区间缩短了

好

那么今天我们就讲到这里

这是我们讲的0.618法

也称为黄金分割法