最优化方法实验报告Numerical Linear Algebra And Its Applications学生所在学院：理学院学生所在班级：计算数学10-1学生姓名：甘纯指导教师：单锐教务处2013年5月实验一实验名称：熟悉matlab基本功能实验时间: 2013年05月10日星期三实验成绩：一、实验目的：在本次实验中，通过亲临使用MATLAB，对该软件做一全面了解并掌握重点内容。
二、实验内容：1. 全面了解MATLAB系统2. 实验常用工具的具体操作和功能实验二实验名称：一维搜索方法的MATLAB实现实验时间: 2013年05月10日星期三实验成绩：一、实验目的：通过上机利用Matlab数学软件进行一维搜索，并学会对具体问题进行分析。
并且熟悉Matlab软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。
二、实验背景：(一）0.618法（黄金分割法），它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。
1、算法原理黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。
2、算法步骤用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下： （1）选定初始区间11[,]a b 及精度0ε>，计算试探点：11110.382*()a b a λ=+-11110.618*()a b a μ=+-。
（2）若k k b a ε-<，则停止计算。
否则当()()k k f f λμ>时转步骤（3）。
当()()k k f f λμ≤转步骤（4）。
（3）置11111110.382*()k kk k k k k k k k a b b a b a λλμμ+++++++=⎧⎪=⎪⎨=⎪⎪=+-⎩转步骤（5）（4）置11111110.382*()k k k k k k k k k k a a b a b a μμλλ+++++++=⎧⎪=⎪⎨=⎪⎪=+-⎩转步骤（5）（5）令1k k =+，转步骤（2）。
(二）斐波那契法： 1、算法原理斐波那契法也是一种区间收缩算法，但是和黄金分割法不同的是，黄金分割法每次收缩只改变搜索区间的一个端点，而斐波那契法同时改变搜索区间的两个端点，是一种双向收缩法。
2、算法步骤(1)选取初始数据，确定单峰区间],[00b a ，给出搜索精度0>δ，由δ≤-nF ab 确定搜索次数n 。
(2) 00,,1b b a a k ===，计算最初两个搜索点，按（3）计算1t 和2t 。
(3) while 1-<n k)(),(2211t f f t f f == if 21f f <)()()1(;;1122a b k n F k n F a t t t t a ----+===else)()()1(;;2211b a k n F k n F b t t t t b ----+===end1+=k ken(4) 当进行至1-=n k 时，)(2121b a t t +==这就无法借比较函数值)(1t f 和)(2t f 的大小确定最终区间，为此，取⎪⎪⎩⎪⎪⎨⎧-++=+=))(21()(2112a b a t b a t ε其中ε为任意小的数。
在1t 和2t 这两点中，以函数值较小者为近似极小点，相应的函数值为近似极小值。
并得最终区间],[1t a 或],[2b t 。
由上述分析可知，斐波那契法使用对称搜索的方法，逐步缩短所考察的区间，它能以尽量少的函数求值次数，达到预定的某一缩短率。
(三）三点二次插值法：1、算法原理该算法在搜索区间中不断用低次（通常不超过三次）插值多项式来近似目标函数，并逐步用插值多项式的极小点来逼近）（x ϕ的极小点，当函数具有比较好的解析性质时，插值方法比直接方法（如0.618或Fibonacci 法）效果更好。
2、算法步骤(1)取初始点321ααα<<，计算3,2,1i i i ==），（αϕϕ并满足)()()(321αϕαϕαϕ<>，置精度要求ε（迭代终止条件）。
(2 ) 计算[]0A 2A 213132321=-+-+-=，）（）（）（ααϕααϕααϕ，则置22ϕαϕαα==）（， 停止计算(3)计算A 322212212312322ϕααϕααϕααα）（）（）（-+-+-=若1αα<或)),((33ααααα∉>则置22,ϕϕαα== 停止计算 (4)计算)(αϕϕ=，若εαα<-2停止计算（α作为极小点） (5)如果),(32ααα∈ 则若,2ϕϕ<则置：αϕααϕϕαα====222121,,,否则置ϕϕαα==33,；否则),(21ααα∈则若,2ϕϕ<则置：αϕααϕϕαα====222323,,,否则置ϕϕαα==11,。
(6)转（2）三、实验内容：1. 0.618法的MATLAB 实现2. Fibonacci 法的MATLAB 实现 3．二次插值法的MATLAB 实现 四、实验过程： 1．0.618法的函数：function [x,minf] = minHJ(f,a,b,eps) if nargin == 3 eps = 1.0e-6; endl = a + 0.382*(b-a); u = a + 0.618*(b-a); k=1; tol = b-a;while tol>eps && k<100000 fl = subs(f , findsym(f), l); fu = subs(f , findsym(f), u); if fl > fu a = l;l = u;u = a + 0.618*(b - a);elseb = u;u = l;l = a + 0.382*(b-a);endk = k+1;tol = abs(b - a);endif k == 100000disp('找不到最小值！');x = NaN;minf = NaN;return;endx = (a+b)/2;minf = subs(f, findsym(f),x);2．Fibonacci法的函数：function [x,minf] = minFBNQ(f,a,b,delta,eps) if nargin == 4eps = 1.0e-6;endF = ones(2,1);N = (b-a)/eps;c = F(2) - N;n = 2;while c<0n = n+1;F(n) = F(n-1) + F(n-2);c = F(n) - N;endl = a + F(n-2)*(b-a)/F(n);u = a + F(n-1)*(b-a)/F(n);k=1;while 1fl = subs(f , findsym(f), l);fu = subs(f , findsym(f), u);if fl > fua = l;l = u;u = a + F(n-k-1)*(b-a)/F(n-k);if (k == n - 3)break;elsek = k+1;endelseb = u;u = l;l = a + F(n-k-2)*(b-a)/F(n-k);if ( k == n-3 )break;elsek = k+1;endendendif k == 100000disp('找不到最小值！');x = NaN;minf = NaN;return;endu = l + delta;fl = subs(f , findsym(f), l);fu = subs(f , findsym(f), u);if fl > fua = l;elseb = l;endx = (a+b)/2;minf = subs(f , findsym(f), x);3．二次插值法函数：function [min,minf]=minTP(a1,a2,a3,f,eps)if nargin==4eps=10^(-2);endf1=subs(f,findsym(f),a1);f2=subs(f,findsym(f),a2);f3=subs(f,findsym(f),a3);if (f1<f2)||(f2>f3)disp('输入三点不符合三点二次插值的要求');endax=((a2^2-a3^2)*f1+(a3^2-a1^2)*f2+(a1^2-a2^2)*f3)/(2*((a2-a3)*f1+(a3-a1)*f2+(a1-a2)*f3)); fax=subs(f,findsym(f),ax);while(abs(fax-f2)>eps)if ax>a2if fax<=f2a1=a2;a2=ax;f1=f2;f2=fax;elsea3=ax;f3=fax;endelseif fax<=f2a3=a2;a2=ax;f3=f2;f2=fax;elsea1=ax;f1=fax;endendax=((a2^2-a3^2)*f1+(a3^2-a1^2)*f2+(a1^2-a2^2)*f3)/(2*((a2-a3)*f1+(a3-a1)*f2+(a1-a2)*f3)); fax=subs(f,findsym(f),ax);endmin=ax;minf=subs(f,findsym(f),ax);format short;五、实验结果(总结/方案)黄金分割法求解极值实例。
用黄金分割法求解下面函数的最小值：]10,10[,52)(24-∈+--==t t t t t f 其中在command window 中输入：>>syms t;f=t^4-t^2-2*t+5;[x,fx]=minHJ(f,-10,10)结果为：x= 1.0000fx= 3.00002．Fibonacci 法Fibonacci 法求解极值实例。
用Fibonacci 法求解下面函数的最小值：]10,10[,52)(24-∈+--==t t t t t f 其中在command window中输入：>>syms t;f=t^4-t^2-2*t+5;[x,fx]=minFBNQ(f,-10,10,0.05)结果为：x= 1.0000fx= 3.00003．二次插值法在command window中输入：>> syms t;f=t^3-3*t+2;a1=0;a2=2;a3=3;[min,minf]=minTP(a1,a2,a3,f,0.0001)结果为：min =0.9983minf =8.9463e-006。