最优化方法的应用资料

1、最优化方法姓名张炯学号 201200144423一维搜索方法的分类为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。然而，对于插入点的位置，是可以用不同的方法来确定的。?黄金分割法? 一类称作解析法或函数逼近法：构造一个插值函数来逼近原来函数,用插 值函数的极小点作为区间的插入点-牛顿法、二次插值法等黄金分割法黄金分割法要求插入点、2的位置相对于原区间a,b的两端点具有对称性，即多a i = b - l (b - a) ”扌a2 二 a + l (b - a)其中I为待定系数1- II2-“ 5 = 0.618图黄金分割法黄金分割法的搜索过程出初始搜索区间a,b及收敛精度，将赋以0.6

2、18按前页中坐标点比例公式计算：-i和：-2，并计算其对应的函数值f（ ： 1）和f 2）。比较函数值，禾U用进退法缩短搜索区间检查区间是否缩短到足够小和函数值是否收敛到足够近，如果条件不满足则返回到步骤如果条件满足则取最后两试验点的平均值作为极小点的数值近似值黄金分割法程序框图黄金分割法程序框图牛顿法对于一维搜索函数，假定已给出极小点的一个较好的近似点aO,因为一个连续可微的函数在极小点附近与一个二次函数很接近，所以可以在aO点附近用一个二次函数来逼近函数，即在点 aO将f(a)进行泰勒展开，并保留到二次项，有f(x) ? f (a) f (ao) + f 见ao)( a - ao) + f

3、 彳ao)( a - ao)然后以二次函数的极小点作为极小点的一个新近似点，根据极值必要条件耳ao) + f ?a)( ai - ao) = 02 f (a1) = o 得 f_ f )ak+i = ak -f 叱ak)k=o,12丄_ f ao) ai ao -1 o f Ha。)牛顿法的计算步骤给定初始点ao，控制误差，令k=o计算f(x)在ak点的一阶和二阶导数利用牛顿法迭代公式求ak+i若|ak+i-ak| ，则求得近似解a*=ak+i，停止计算，否则作第步令k=k+i,然后转第步牛顿法的优缺点最大优点是收敛速度快缺点每一点处都要计算函数的导数和二阶导数，因而增加了每次迭代的工作量用数

4、值微分代替二阶导数时，舍入误差会影响牛顿法的收敛速度，当二阶导数很 小时问题更严重牛顿法要求初始点选得比较好，即不能离极小点太远，否则在可能使极小化序列 发散或收敛到非极小点二次插值法二次插值法又称抛物线法，它的基本思路是：在寻求函数f( a )极小点的搜索区间内，取三个点的函数值来构造一个二次插值多项式p( a ),用它的极小点(第四个点)近似地作为原目标函数的极小点。 若近似程度不满足精度要求时，可以 反复使用此法，从四个点中选取三个点，使函数值呈现“高 -低-高”变化的前提 下逐渐的缩短搜索区间，二次插值多项式的极小点就逼近原目标函数的极小点。二次插值法区间缩短的 4种情况16曲 殆(b

5、)二次插值法的流程图、牛顿迭代法详解牛顿迭代法(Newt ons method)又称为牛顿-拉夫逊(拉弗森)方法 (Newton-Raphson method),它是牛顿在17世纪提出的一种在实数域和复数域 上近似求解方程的方法。牛顿迭代法(Newt ons method)又称为牛顿-拉夫逊(拉弗森)方法 (Newton-Raphson method)，它是牛顿在17世纪提出的一种在实数域和复数域 上近似求解方程的方法。 多数方程不存在求根公式， 因此求精确根非常困难， 甚 至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数 f(x )的泰勒 级数的前面几项来寻找方程 f(x) = 0

6、 的根。牛顿迭代法是求方程根的重要方法 之一，其最大优点是在方程 f(x) = 0 的单根附近具有平方收敛，而且该法还可 以用来求方程的重根、 复根，此时线性收敛， 但是可通过一些方法变成超线性收 敛。另外该方法广泛用于计算机编程中。设 r 是 的根，选取 作为 r 的初始近似值，过点 做曲线 的切线 L ， L 的方 程为 ，求出 L 与 x 轴交点的横坐标 ，称 x1 为 r 的一次近似值。过点 做曲 线 的切线， 并求该切线与 x 轴交点的横坐标 ，称 为 r 的二次近似值。 重复 以上过程，得 r 的近似值序列，其中， 称为 r 的 次近似值，上式称为牛顿迭 代公式。用牛顿迭代法解非线

7、性方程， 是把非线性方程 线性化的一种近似方法。 把 在 点 的某邻域内展开成泰勒级数 ，取其线性部分(即泰勒展开的前两项) ，并 令其等于 0，即 ，以此作为非线性方程 的近似方程， 若 ，则其解为 ， 这 样，得到牛顿迭代法的一个迭代关系式： 。已经证明， 如果是连续的， 并且待求的零点是孤立的， 那么在零点周围存在一个 区域，只要初始值位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果不 为 0, 那么牛顿法将具有平方收敛的性能 . 粗略的说，这意味着每迭代一次，牛 顿法结果的有效数字将增加一倍。 1军人在进攻时常采用交替掩护进攻的方式，若在数轴上的点表示A, B两人的位置，规定在前面

8、的数大于后面的数，则是 AB BA交替出现。但现在假设军中 有一个胆小鬼， 同时大家又都很照顾他， 每次冲锋都是让他跟在后面， 每当前面 的人占据一个新的位置， 就把位置交给他， 然后其他人再往前占领新的位置。 也 就是A始终在B的前面，A向前迈进，B跟上，A把自己的位置交给B (即执行B =A)，然后A再前进占领新的位置，B再跟上，直到占领所有的阵地，前进结束。 像这种两个数一前一后逐步向某个位置逼近的方法称为迭代法。迭代法也称辗转法， 是一种不断用变量的旧值递推新值的过程， 跟迭代法相对应 的是直接法(或者称为一次解法) ，即一次性解决问题。迭代算法是用计算机解 决问题的一种基本方法。它利

9、用计算机运算速度快、适合做重复性操作的特点， 让计算机对一组指令(或一定步骤)重复执行，在每次执行这组指令(或这些步 骤)时，都从变量的原值推出它的一个新值。利用迭代算法解决问题，需要做好以下三个方面的工作：一、确定迭代变量在可以用迭代算法解决的问题中， 至少存在一个可直接或间接地不断由旧值递推 出新值的变量，这个变量就是迭代变量。二、建立迭代关系式 所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系) 。 迭代关系式的建立是解决迭代问题的关键， 通常可以使用递推或倒推的方法来完 成。三、对迭代过程进行控制 在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。 不能让迭代过

10、程 无休止地执行下去。 迭代过程的控制通常可分为两种情况： 一种是所需的迭代次 数是个确定的值， 可以计算出来； 另一种是所需的迭代次数无法确定。 对于前一 种情况，可以构建一个固定次数的循环来实现对迭代过程的控制； 对于后一种情 况，需要进一步分析得出可用来结束迭代过程的条件。关于牛顿迭代法有一个很典型的例子是斐波那契( Fibonacci )数列。斐波那契 数列为：0、 1、 1、2、3、 5、8、 13、21、，即 fib =0; fib =1;fib(n)=fib(n-1)+fib(n-2)(当 n2 时)。在n2时，fib(n)总可以由fib(n-1)和fib(n-2)得到，由旧值递

11、推出新值，这 是一个典型的迭代关系，所以我们可以考虑迭代算法。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;三、牛顿迭代法的程序实现

12、牛顿迭代法 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;%l代次数X=newton(f,x,x0,esp,N)% 求解 %真%值为 -1 0 -2%function x1=newton(f,x,x0,esp,N)%此函数用于解非线性方程，方法为牛顿下山法。R=jacobian(f,