最优化方法的应用资料

最优化方法姓名张炯学号 201200144423a a a a 图 黄金分割法一、一维搜索方法的分类为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。

然而，对于插入点的位置，是可以用不同的方法来确定的。

• 黄金分割法• 一类称作解析法或函数逼近法：构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的插入点– 牛顿法、二次插值法等黄金分割法黄金分割法要求插入点、的位置相对于原区间[a,b]的两端点具有对称性，即()()12b b a a b a a l l a l =--ìïïíï=+-ïî其中为待定系数21l l-=10.6182l -?==黄金分割法的搜索过程⑵出初始搜索区间[a,b]及收敛精度，将赋以0.618⑵按前页中坐标点比例公式计算α1和α2，并计算其对应的函数值f(α1)和f（α2)。

⑶比较函数值，利用进退法缩短搜索区间⑷检查区间是否缩短到足够小和函数值是否收敛到足够近，如果条件不满足则返回到步骤⑵⑸如果条件满足则取最后两试验点的平均值作为极小点的数值近似值黄金分割法程序框图牛顿法对于一维搜索函数，假定已给出极小点的一个较好的近似点a0，因为一个连续可微的函数在极小点附近与一个二次函数很接近，所以可以在a0点附近用一个二次函数来逼近函数，即在点a0将f(a)进行泰勒展开，并保留到二次项，有然后以二次函数的极小点作为极小点的一个新近似点，根据极值必要条件得得牛顿法的计算步骤⑴给定初始点a0，控制误差ε，令k=0⑵计算f(x)在a k 点的一阶和二阶导数 ⑶利用牛顿法迭代公式求a k+1⑷若|a k+1-a k |≤ε，则求得近似解a*=a k+1，停止计算，否则作第⑸步 ⑸令k=k+1，然后转第⑵步牛顿法的优缺点最大优点是收敛速度快 缺点每一点处都要计算函数的导数和二阶导数，因而增加了每次迭代的工作量 用数值微分代替二阶导数时，舍入误差会影响牛顿法的收敛速度，当二阶导数很小时问题更严重牛顿法要求初始点选得比较好，即不能离极小点太远，否则在可能使极小化序列发散或收敛到非极小点1()0a f ¢=()()()00100f a f a a a ⅱ?+-=()()0100f a a a f a ¢=-ⅱ二次插值法二次插值法又称抛物线法，它的基本思路是：在寻求函数f(α)极小点的搜索区间内，取三个点的函数值来构造一个二次插值多项式p(α),用它的极小点（第四个点）近似地作为原目标函数的极小点。

若近似程度不满足精度要求时，可以反复使用此法，从四个点中选取三个点，使函数值呈现“高-低-高”变化的前提下逐渐的缩短搜索区间，二次插值多项式的极小点就逼近原目标函数的极小点。

二次插值法区间缩短的4种情况二次插值法的流程图二、牛顿迭代法详解牛顿迭代法（Newton's method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

牛顿迭代法（Newton's method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。

方法使用函数f(x）的泰勒级数的前面几项来寻找方程f(x) = 0的根。

牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。

另外该方法广泛用于计算机编程中。

设r是的根，选取作为r的初始近似值，过点做曲线的切线L，L的方程为，求出L与x轴交点的横坐标，称x1为r的一次近似值。

过点做曲线的切线，并求该切线与x轴交点的横坐标，称为r的二次近似值。

重复以上过程，得r的近似值序列，其中，称为r的次近似值，上式称为牛顿迭代公式。

用牛顿迭代法解非线性方程，是把非线性方程线性化的一种近似方法。

把在点的某邻域内展开成泰勒级数，取其线性部分（即泰勒展开的前两项），并令其等于0，即，以此作为非线性方程的近似方程，若，则其解为，这样，得到牛顿迭代法的一个迭代关系式：。

已经证明，如果是连续的，并且待求的零点是孤立的，那么在零点周围存在一个区域，只要初始值位于这个邻近区域内，那么牛顿法必定收敛。

并且，如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。

[1]军人在进攻时常采用交替掩护进攻的方式，若在数轴上的点表示A，B两人的位置，规定在前面的数大于后面的数，则是A>B，B>A交替出现。

但现在假设军中有一个胆小鬼，同时大家又都很照顾他，每次冲锋都是让他跟在后面，每当前面的人占据一个新的位置，就把位置交给他，然后其他人再往前占领新的位置。

也就是A始终在B的前面，A向前迈进，B跟上，A把自己的位置交给B（即执行B = A），然后A 再前进占领新的位置，B再跟上，直到占领所有的阵地，前进结束。

像这种两个数一前一后逐步向某个位置逼近的方法称为迭代法。

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。

迭代算法是用计算机解决问题的一种基本方法。

它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。

利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量在可以用迭代算法解决的问题中，至少存在一个可直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地执行下去。

迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析得出可用来结束迭代过程的条件。

关于牛顿迭代法有一个很典型的例子是斐波那契（Fibonacci）数列。

斐波那契数列为：0、1、1、2、3、5、8、13、21、…，即fib⑴=0; fib⑵=1;fib(n)=fib(n-1)+fib(n-2) （当n>2时）。

在n>2时，fib(n)总可以由fib(n-1)和fib(n-2)得到，由旧值递推出新值，这是一个典型的迭代关系，所以我们可以考虑迭代算法。

int Fib(int n) //斐波那契（Fibonacci）数列{if (n < 1）/*预防错误*/return 0;if (n == 1 || n == 2)/*特殊值，无需迭代*/return 1;int f1 = 1,f2 = 1,fn;/*迭代变量*/int i;for(i=3; i<=n; ++i)/*用i的值来限制迭代的次数*/{fn = f1 + f2; /*迭代关系式*/f1 = f2;//f1和f2迭代前进，其中f2在f1的前面f2 = fn;}return fn;}三、牛顿迭代法的程序实现牛顿迭代法Matlab程序（带下山因子）本文程序可用于求解线性和非线性方程组，在使用牛顿迭代法的同时，加入了下山因子，加入下山因子后，对于初值的选取更为宽泛。

使用方法：请将本文function所定义的函数存为m文件，将matlab路径改为存储newton 函数的路径，然后参照本文例子的格式定义变量、表达式、初值、收敛阈值、迭代次数后，输入X=newton(f,x,x0,esp,N)即可求解。

%%%%%%%%%%%%%%%%%%%%例子syms x1 x2 x3%定义变量名称f1=x1+x2+x3+3;f2=2*x1-x2-x3;f3=x1+2*x2-2*x3-3;%定义方程表达式（方程全都移到等号左边的表达式）f=[f1;f2;f3];x=[x1;x2;x3];x0=[0;0;0];%设定初值esp=[0.00001;0.00001;0.00001];%阈值N=1000;%迭代次数X=newton(f,x,x0,esp,N)%求解%%%%真值为-1 0 -2%%%%%%%%%%%%%%%%%%%%function x1=newton(f,x,x0,esp,N)%此函数用于解非线性方程，方法为牛顿下山法。

R=jacobian(f,x);ph=size(f,1);ty(1:ph,1)=1;coo=1;while abs(coo-1)<1e-6%这代表coo==1coo=0;R1=subs(R,x,x0);%%%f1=subs(f,x,x0);x1=x0-ty.*(R1\f1);f11=subs(f,x,x1);f12=double(f1);f112=double(f11);for i=1:size(f12,1);j=i;clcjif abs(f112(i))>abs(f12(i))ty(i)=ty(i)/2;coo=1;endendendfor i=1:NclciR1=subs(R,x,x0);%%%f1=subs(f,x,x0);x1=x0-ty.*(R1\f1);xx=abs(x1-x0);if xx<espbreakelsex0=x1;endend。