ch4一维搜索方法

《ch4一维搜索方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章一维搜索方法14.1一维搜索方法对n元函数,给定点x(k),向量pk,则f(x)从x(k),出发沿方向pk的直线上函数值的变化可以表示为一元函数:该函数只有一个变量,且每一个λ值都对应着直线上一个点。求函数f(x)的解,就转化为沿直线求一元函数的极小值点,因此本节先介绍一元函数f(x)的极小问题。2§4.2二分法当f(x)连续可导时,在极小点x*处有,因此求一元函数f(x)的极小值点问题就转化为求解方程的根的问题。称的点为函数f(x)的驻点。设根,且,则有算法3算法4.1(二分法)1．输入a,b及

2、精度ε>0。2.3．若或,输出x*=x。否则转4。4．求,若,则,否则5．输出超过最大迭代次数的信息,停机。4§4.3Newton法假设f(x)二阶连续可导,对在xk处展开为Taylor公式由此有迭代公式：算法4.2(Newton法求的根)1．对;做到第6步。2．3．若d=0停止计算。4．计算5．若或,输出x,停机。6．7．若迭代N0次后仍达不到精度要求,停机。5定义4.4.1设f(x):[a,b]→R若存在点x*∈(a,b)使f(x)在[a,x*]上是单调减小,在[x*,b]上是单调增加,则称[a,b

3、]是f(x)的单峰区间。f(x)是[a,b]上的单峰函数如图所示。其中图(a),图(c)是单峰函数,图(b)不是单峰函数。(a)(b)(c)6§4.40.618法(黄金分割法)假设f(x)是单峰函数,但不知道极小点x*的位置。任取x1,x2∈[a,b],且x1f(x2)此时x*>x1,即x*∈[x

4、1,b]见图(c)。为计算方便可将情况(1)归结到情况(2)或情况(3)。为了寻找x*,在初始区间[a1,b1]内任取两点;且,通过比较函数值,从而确定极小点x*是在或者[x1,b1]内。取小区间代替[a1,b1]得新的x*的存在区间,记为[a2,b2],又任取且,通过比较函数值得新的小区间[a3,b3]·······x*的存在区间不断缩小,最后便可确定出近似的极小点,为了节省计算函数值的工作量,永远保证新区间的一个端点和原区间的一个端点重合。8设每次迭代的区间长度按比例α缩小(0<α<1),设第k次迭

5、代后的区间为[ak,bk],则第k+1次的区间为或取不妨设,经迭代后包含极小点的区间为为了进一步缩短此区间,取xk+1和且,9取同理,若可得相同的结论,故有定义4.4.2若实数满足则称为黄金分割数,黄金分割数在单位长度区间中对应的点称为黄金分割点。10算法4.3(0.618法)给定初值,误差1．计算2．若,得最优解,否则转3。3．若则,转4;若则,转5;若则,转1。4．计算,转2。5．计算,转2。1112§4.5Fibonacci法(分数法)该方法也适用于单峰函数,与0.618法的区别是每次迭代区间长度

6、的缩短。不是按常数比率进行而是由Fibonacci数确定的,而且可以预先确定迭代次数。定义4.5.1设数列{Fn}满足称数列{Fn}为Fibonacci数列,Fn为第n个Fibonacci数,相邻两个Fibonacci数之比Fn-1/Fn称为Fibonacci分数。如下表：n01234567Fn1123581321Fn-1/Fn11/22/33/55/88/1513/2113用数学归纳法可以证明且设第k次迭代时的区间为[ak,bk],取14容易验证且当时,令。有当时,令。有特别当k=n-1时有15由此可

7、知,只要给定了初始区间b1-a1的长度和精度要求ε,就可计算出迭代的次数此时为了能在第n-1次迭代中使区间缩短,可在第n-2次迭代后在的右边或左边取一点,令且16算法4.4(Fibonacci方法)(1)给定初始区间[a,b]和误差要求ε>0,(2)(3)若,转(4);否则转(2)。(4)17(5)若转(6);若转(7)。(6)若k=n-2则转(9);否则计算f(x)转(8)。(7)若k=n-2则转(9);否则计算f(x)转(8)。(8),转(5)。(9),若,则;否则(10)输出例4.1分别用二分法、

8、Newton法、0.618法求解解:取精度,初值Newton法的迭代公式为：计算结果如下表18迭代次数二分法Newton法02.252.2511.8752.071428622.06252.008403431.968752.000137842.01562551.992187562.003906271.998361882.00113991.99975040.618法的计算结果如下表20迭代次数[ak,bk]xkf(xk)0[0,3]1.1458