第二节单因素方法精选文档.ppt

第二节单因素方法本讲稿第一页，共十九页进一步取点逐步缩小包含x*的区间范围，利用有限次计算，使区间压缩。问题：计算n次函数值，能把区间缩小到什么程度？找寻一个标准。a a1 x*b1 byxa a1 x*b1 bxy本讲稿第二页，共十九页设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 0 1 2 3 4 5 6 7 8 9 10 11 12 1 1 2 3 5 8 13 21 34 55 89 144 233本讲稿第四页，共十九页第一次压缩的压缩率为：第二次压缩的压缩率为：第n次压缩的压缩率为：本讲稿第五页，共十九页利用压缩率欲将原区间a0,b0压缩为原长的倍，需计算几次函数值？本讲稿第六页，共十九页斐波那契法的步骤：（1）确定试点个数n，令Fn1/,查表确定试点个数n。（2）选取前两个试点的位置本讲稿第七页，共十九页它们在区间的位置是对称的。（3）计算函数值 和 ,并比较它们的大小。本讲稿第八页，共十九页（4）计算 或 ,如（3）步迭代。计算试点的一般公式为：本讲稿第九页，共十九页计算n次函数值，就可以达到预定的压缩率。本讲稿第十页，共十九页v0.618法利用斐波那契法压缩区间压缩率依次为：将数列分为 可证这两个数列收敛于同一极限。设k时，若 则=。又递推公式得本讲稿第十一页，共十九页又因为将（1）代入（2）中得：本讲稿第十二页，共十九页将斐波那契法中每次压缩的不同的压缩率都用0.618来代替，每次压缩的压缩率相同，简化了求试点的计算，这种方法称为0.618法。其递推公式为：若给定 ，令 求满足条件的最小的n。本讲稿第十三页，共十九页v牛顿法一 原理：构造函数逼近于已知函数，其最优解也逼近于所求函数的最优解。设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。解：任取 故 即是近似最优解。本讲稿第十六页，共十九页v抛物线法：一 原理：利用构造拟合（逼近）函数的方法，与牛顿法原理相同，但方法不同。设函数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）为新的三点继续迭代。每次的三点组中，中间点的函数值均不大于两端点的函数值。(3)当相距两次迭代的极小点的距离小于某一预先给定的距离时，或者逼近函数的值与原来函数值之差小于某一允许误差时就停止迭代。本讲稿第十九页，共十九页