《无约束一维搜索》由会员分享,可在线阅读,更多相关《无约束一维搜索(142页珍藏版)》请在金锄头文库上搜索。
1、,一维搜索,一维搜索的方法,单谷函数的定义,单谷函数的性质,单谷函数的性质,单谷函数的性质,单谷函数的性质,单谷函数的性质,单谷函数的性质,单谷函数的性质,单谷函数的性质,Questions,单谷函数的性质有什么用?,寻找单谷函数的方法-加步探索法,寻找单谷函数的方法-加步探索法,加步探索法-具体步骤,加步探索法-具体步骤,加步探索法-具体步骤,加步探索法-具体步骤,加步探索法-具体步骤,加步探索法-具体步骤,加步探索法-具体步骤,加步探索法-具体步骤,加步探索法-具体步骤,加步探索法-具体步骤,0.618 法,利用单谷函数性质求极小值点的一种方法,0.618 法,Questions,两个点如
2、何选取?,0.618 法,0.618 法,0.61803398874989,0.618 法,Questions,为什么选黄金分割点和其对称点 作为缩小搜索区间的2个计算点?,0.618 法-选点的优点,0.618 法-选点的优点,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-缩短率,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.61
3、8 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,0.618 法-计算步骤,Questions,黄金分割点(黄金分割法)? 像金子一样珍贵?,由于公元前6世纪古希腊的毕达哥拉斯学派研究过正五边 形和正十边形的作图,因此现代数学家们推断当时毕达哥 拉斯学派已经触及甚至掌握了黄金分割。 公元前4世纪,古希腊数学家欧多克索斯第一个系统研究 了这一问题,并建立起比例理论。 公元前300年前后欧几里得撰写几何原本时吸收了 欧多克索斯的研究成果,进一步系统论述了黄金分割, 成为最早的有关黄金分割的论著。,历史,中世纪后,黄金分割被披上
4、神秘的外衣,意大利数家 帕乔利称黄金分割比为神圣比例,并专门为此著书立说。 德国天文学家开普勒称黄金分割为神圣分割。,历史,因为它在建筑、文艺、工农业生产和科学实验中 有着广泛 而重要的应用,所以人们才珍贵地称它 为“黄金分割“。,应用,因为它在建筑、文艺、工农业生产和科学实验中 有着广泛 而重要的应用,所以人们才珍贵地称它 为“黄金分割“。,应用,舞台上的报幕员并不是站在舞台的正中央,而是偏在台上 一侧,以站在舞台长度的黄金分割点的位置最美观。,应用,黄金矩形(Golden Rectangle)的长宽之比为黄金分割率, 换言之,矩形的长边为短边 1.618倍.黄金分割率和黄金矩 形能够给画面
5、带来美感,令人愉悦.在很多艺术品以及大自 然中都能找到它.希腊雅典的帕撒神农庙就是一个很好的 例子,达. 芬奇的符合黄金矩形. 的脸也符合黄金矩形,同样也应用了该比例 布局.,应用,应用,对人体解剖很有研究的意大利画家达芬奇发现,人的肚脐 位于身长的0.618处;咽喉位于肚脐与 头顶长度的0.618 处;肘关节位于肩关节与指头长度的0.618处,人体存在 着肚脐、咽喉、膝盖、肘关节四个黄金分割点,它们也是 人赖以生存的四处要 害。,最完美的人体:肚脐到脚底的距离/头顶到脚底的距离 =0.618 ; 最漂亮的脸庞:眉毛到脖子的距离/头顶到脖子的距离 =0.618 ;,应用,高雅的艺术殿堂里,自然
6、也留下了黄金数的足迹画家们 发现,按0.618:1来设计腿长与身高的比例,画出的人体身 材最优美,而现今的女性,腰身以下的长 度平均只占身高 的0.58,因此古希腊维纳斯女神塑像及太阳神阿波罗的形 象都通过故意延长双腿,使之与身高的比值为0.618,从 而创造艺术美难怪许多 姑娘都愿意穿上高跟鞋,,应用,医学与0.618有着千丝万缕的联系,它可解释人为什么在 环境22至24摄摄氏度时感觉最舒适。因为人的体温为 37C与0.618的乘积为22.8 C,而且这一温度中肌体 的新陈代谢、生理节奏和生理功能均处于最佳状态。现 代医学研究还表明,0.618与养生之道息息相关,动与静 是一个0.618的比
7、例关系,大致四分动六分静,才是最佳 的养生之道。医学分析还发现,饭吃六七 成饱的几乎 不生胃病。,0.618与战争,在进行战斗部署时,如果是进攻战斗,大炮阵地的配置 位置一般距离己方前沿为1/3倍最大射程处,如果是防御 战斗,则大炮阵地应配置距己方前沿 2/3倍最大射程处。,黄金分割法的例子,如在炼钢时需要加入某种化学元素来增加钢材的强度, 假设已知在每吨钢中需加某化学元素的量在1000 2000 克之间,为了求得最恰当的加入量,需要在1000克与 2000克这个区间中进行试验。0.618法只需要试验几次就 能达到理想的结果。,优选学中的黄金分割法或0.618法,是由美国数学家基弗于1953年
8、首先提出的,70年代在中国推广,代表人物是华罗庚。,0.618 法,Questions,要得到一个收缩的单谷区间,至少要计算2个点的函数值。给定初始单谷区间以及要达到的最终单谷区间,0.618法需要的试点个数最少吗?如果不是,哪种方法需要的试点个数最少? 或者换另外一种说法,如果令最终的搜索区间的区间长度为一个单位,那么经过N个试点函数值的计算,最大的原始区间长度是多少?,令Fn表示经过N个试点函数值的计算 能达到的最大区间长度。,Fibonacci 数,Fibonacci 法,Fibonacci 法n的计算,Fibonacci 法n的计算,Fibonacci 法n的计算,同样的缩短率,同样的
9、初始搜索区间,0.618法和Fibonacci法中哪种方法计算量最小? 同样的初始搜索区间,同样的计算量,哪种方法的缩短率最小?,Questions,Fibonacci 法n的计算,F10=89, F11=144, 1/F10=0.0112; 1/F11=0.00694, n=11.,0.6189 = 0.0131;0.61810 = 0.0081, n=11.,Delta=0.01,Fibonacci 法,0.618法,Fibonacci 法的计算步骤,Fibonacci 法的计算步骤,首先通过区间的缩短率计算Fn,Fibonacci 法,Fibonacci 法n的计算,Fibonacci
10、法,Fibonacci 法和0.618法的关系,Questions,相邻Fibonacci数的比值构成一个点列,这个点列的极限是多少?,1/2 = 0.5000 2/3 = 0.6667 3/5 = 0.6000 5/8 = 0.6250 8/13 = 0.6154 13/21 = 0.6190 21/34 = 0.6176 34/55 = 0.6182 55/89 = 0.6180 89/144 = 0.6181,Fibonacci 法和0.618法的关系,Fibonacci 法和0.618法的关系,Fibonacci 法和0.618法的关系,Fibonacci 法和0.618法的关系,二分
11、法,二分法,二分法,二分法,二分法,Example,二分法,二分法,二分法,二分法,二分法,牛顿法,Example,牛顿法,牛顿法,牛顿法的收敛性,牛顿法的收敛性-局部二阶收敛,牛顿法的收敛性-局部二阶收敛,Remark,牛顿法的计算步骤,牛顿法的计算步骤,牛顿法的计算步骤,牛顿法的计算步骤,牛顿法的计算步骤,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法的收敛,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,抛物线插值法,Home work P150 (6) (11),P150 (6),P150 (6),P150 (6),P150 (6),P150 (6),x= 2.0000 fval = -0.6667,P150 (11),P150 (11),P150 (11),x = 0.3517 fval = 0.8272,