《因素方法》PPT课件.ppt

第二节 单因素方法,一 斐波那契法 （一）原理：设 为定义在a,b上的下单峰函数，存在x*使,对任意a1b1, 若 , x*属于a,b1; 若 , x*属于a1,b.,进一步取点逐步缩小包含x*的区间范围，利用有限次计算，使区间压缩。问题： 计算n次函数值，能把区间缩小到什么程度？ 找寻一个标准。,a a1 x* b1 b,y,x,a a1 x* b1 b,x,y,设Fn为计算n次函数值能把区间缩小为单位区间的 最大原区间的长度。称为斐波那契数。,F0=F1=1 ， F2=2，F3=3 有递推公式为：Fn=Fn-1+Fn-2。,由此可得 ：计算n次函数值，压缩区间的总压缩率为：,斐波那契数 1202年伦纳德斐波那契提出了这样一个问题：假定一对兔子每个月都生一对新的兔子，新生的兔子隔一个月后就开始生育，其次，假定兔子都没有死亡。这样第一个月是F1=1，第二个月没有生，F2=1；第三个月生了一对兔子，F3=2（老兔及第一对兔子）；第四个月，F4=3（老兔、第一、二对兔子）；第五个月，F5=5（老兔、第一、二、三对兔子及第一对兔子生的兔孙）；这样形成的数列称为斐波那契数列。,第一次压缩的压缩率为： 第二次压缩的压缩率为： 第n次压缩的压缩率为：,利用压缩率欲将原区间a0,b0压缩为原长的倍，需计算几次函数值？,斐波那契法的步骤： （1）确定试点个数n，令Fn1/,查表确定试点个数n。 （2）选取前两个试点的位置,它们在区间的位置是对称的。 （3）计算函数值 和 ,并比较它们的大小。,（4）计算 或 ,如（3）步迭代。计算试点的一般公式为：,计算n次函数值，就可以达到预定的压缩率。,0 .618法 利用斐波那契法压缩区间压缩率依次为：,将数列分为 可证这两个数 列收敛于同一极限。,设k时，若 则=。 又递推公式得,又因为,将（1）代入（2）中得：,将斐波那契法中每次压缩的不同的压缩率都用0.618来代替，每次压缩的压缩率相同，简化了求试点的计算，这种方法称为0.618法。其递推公式为：,若给定 ，令 求满足条件的最小的n。,牛顿法 一 原理：构造函数逼近于已知函数，其最优解也逼近于所求函数的最优解。设y=f(x)在a,b区间是下单峰函数 ，在点 处 存在。构造函数,该函数是二次抛物线函数，且与f(x)共有一点 可逼近于f(x)，以 的极小点 作为f(x)的极小点的近似 值。现求 的极小点 ，有,如果这个近似值不到预先给定的精确度，就在 点构造函数 并求极小点，这样继续下去，逐步逼近f（x）的极小点，直到到达给定精确度为止。 二 牛顿法运算步骤： （1） 已知给定精确度0。任取 若 则 为 的近似解即是f(x)的最优解。 （2） 若 则算出 若 则停止， 为 的近似解即是f(x)的最优解。,（3）一般地，若迭代至 点，已知 时 为近似解，若 令 迭代直到满足精确度为止。,例1 求函数 在区间3，4上的最小值,精度 = 0.05。 解： 任取 故 即是近似最优解。,抛物线法： 一 原理：利用构造拟合（逼近）函数的方法，与牛顿法原理相同，但方法不同。 设函数f(x)的三点x1 x2 x3，函数值(或试验结果)分别为y1,y2, y3。利用(x1,y1)、(x2,y2) 、(x3,y3)拟合一条抛物线,使得： 满足条件的函数为： (x)=,(x)与f(x)拟合（共用三点）求(x)的最小值点，得：,二 抛物线法的计算步骤： （1）选三个点x1x2x3 ,使其函数值之间关系为： 构造(x),并求其最小值 。验证 是否是f(x)的最优解。 （2）若,(1) f(x4)f(x2)，则以（x2，x4，x3）为新的三点继续迭代。 (2) f(x2)f(x4) f(x3),则以（x1，x2，x4）为新的三点继续迭代。每次的三点组中