牛顿法如前面所提到的,最速下降法在最初几步迭代中函数值下降很快外,总的说来下降的并不快,且愈接近极值点下降的愈慢。因此,应寻找使目标函数下降更快的方法。牛顿法就是一种收敛很快的方法,其基本思路是利用二次曲线来逐点近似原目标函数,以二次曲线的极小值点来近似原目标函数的极小值点并逐渐逼近改点。一维目标函数f(x)在x(k)点逼近用的二次曲线(即泰勒二次多项式)为(x(k))f(x(k))f(x(k))(xx(k))1f(x(k))(xx(k))22此二次函数的极小点可由(x(k))0求得。对于n维问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
,n为目标函数f(X)在X(k)点逼近用的二次曲线为:(X(k))f(x(k))f(X(k)).[XX(k)]1[XX(k)]T.2f(X(k)).[XX(k)]2令式中的Hessian2f(X(k))H(X(k)),则上式可改写为:(X(k))f(x(k))f(X(k)).[XX(k)]-[XX(k)]T.H(X(k)).[XX(k)]2f(X)Hessian矩阵(X)0时可求得二次曲线(X)的极值点,且当且仅当改点处的为正定时有极小值点。由上式得:(X)f(X(k))H(X(k))[XX(k)](X)0,则f(x(k))H(X(k))[XX(k)]0H(X(k))为可逆矩阵,将上式等号两边左乘H(X(k))1,则得H(X(k))1f(X(k))In[XX(k)]0H(X(k))是一个X(k)]」变成精整理后得1XX(k)H(X(k))f(X(k))当目标函数f(X)是二次函数时,牛顿法变得极为简单、有效,这时常数矩阵,式(X(k))f(x(k))f(X(k)).[XX(k)]1[XX(k)]T.H(X(k)).[X2f(X)1确表达式,而利用式XX(k)H(X⑹)f(x(k))作一次迭代计算所得的X就是最优t*点X。在一般情况下f(X)不一定是二次函数,则不能一步就能求出极小值,即极小值点例:试用牛顿法求目标函数f(X)解:设取X(k)22T,则f(X(k))H(X(k))2f(X(k))则,X(k1)x(k)22f(X(k1))0例:试用牛顿法求目标函数f(X)22Xi25X2的极小值点fX12x!4f50x2100X22f2f2X1X1X2202f2f050X2X12X2XX(k)H(X(k))1f(X(k))150040100021000,故X(k1)0为极小点022为X2x1x210x14x260的极小点。1不在H(X(k))f(X(k))方向上,但由于在X(k)点附近函数(X)与f(X)是近似的,所以这个方向可以作为近似方向,可以用式XX(k)H(X(k))f(X(k))求出点X作为一个逼近点X(k1}。这时式XX(k)H(X(k))1f(X(k))可改成牛顿法的一般迭代
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
:X(k1)X(k)H(X(k))1f(X(k))式中H(X(k))1f(X(k))称为牛顿方向,通过这种迭代,逐次向极小值点X*逼近。解:取X(k)ooT,则f(X(k))xi2为2x2x210x-i410X2H(X(k))2f(X(k))2X12rXX22rX(k)X(k1)x(GH(X(k))f(X(k))108X(k1)6即为最小点X*,只迭代一次就达到了由上述可见,牛顿法无一维探索而直接代入公式计算,当初始点选得合适且当f(X)为当初始点选得好时,例如满足初二次函数时收敛很快。即使目标函数f(X)不是二次函数,始误差X(0)X*1时,也会很快收敛。但是这种方法对初始点的选择要求较高,如不满足IX(0)X*1就不能保证有比较好的收敛性。初始点的选择有时甚至会影响到是否收敛。如果选择不当使初始点离较大点近时,计算结果就可能收敛于极大点。初始点选择不当有时也会导致收敛到鞍点或不收敛,基于这种原因,对古典的牛顿法要做些修改,于是便出现了修正牛顿法。其修正方法是:X(k)求X(k-)时不是直接用原来的迭代公式,而且沿着X(k)点处的牛顿方向进行一维搜索,将该方向上的最优点最为X(k-)。这样就会避免收敛于极大点1或鞍点。于是式X(k1)X(k)H(X(k))f(X(k))改写成:X(k1)X(k)(k)H(X(k))1f(X(k))令1S(k)H(X(k))f(X(k))则X(k1)X(k)(k)s(k)式中的探索步长(k)为minf(X(k)S(k))f(X(k)(k)S(k))这种修正牛顿法虽然计算工作量多一些,但是具有收敛快的优点,并且,即使初始点选择不当,用这种探索方法也会成功。1.牛顿法算法原理牛顿法是基于多元函数的泰勒展开而来的,它将H(X(k))f(X(k))作为探索方向,因此它的迭代公式可直接写出来:x(k1)X(k)H(X(k))f(X(k))2.牛顿法算法步骤(1)给定初始点x(0),及精度0,令k0;若||f(X(k))|,停止,极小点为x(k),否则转步骤(3);11计算2f(X(k)),令s(k)H(X(k))f(X(k));令x(k1)x(k)s(k),kk1,转步骤2)。3.牛顿法算法的MATLAB程序调用
格式
pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载
:[x,minf]minNT(f,x0,var,eps)其中,f:目标函数x0:初始点var:自变量向量eps:精度x:目标函数取最小值时的自变量值minf:目标函数的最小值牛顿法的MATLAB程序代码如下:function[x,minf]=minNT(f,x0,var,eps)%目标函数:f;%初始点:x0;%自变量向量:var;%目标函数取最小值时的自变量值:x;%目标函数的最小值:minf;formatlong;ifnargin==3eps=1.0e-6;endtol=1;xO=transpose(xO);whiletol>epsgradf=jacobian(f,var);%梯度方向jacf=jacobian(gradf,var);%雅克比矩阵v=Funval(gradf,var,x0);tol=norm(v);pv=Funval(jacf,var,x0);p=-inv(pv)*transpose(v);x1=x0+p;x0=x1;endx=x1;minf=Funval(f,var,x);formatshort;4.法。5.修正牛顿法算法原理如果2f(X(k))不正定,则牛顿法有可能不收敛,为了解决这个问题,引进修正牛顿此方法与牛顿法不同的是在于引进了搜索步长,而搜索步长的大小通过一维搜索算法确修正牛顿法算法步骤给定初始点x(0),及精度0,令k0;若|f(X(k))|,停止,极小点为x(k),否则转步骤(3);11计算2f(X(k)),令s(k)H(X(k))f(X(k));用一维搜索法求,使得f(X⑹(k)S(k))minf(X(k)S(k)),令X(k1)X(k)(k)S(k),kk1,转步骤(2)。6.修正牛顿法算法的MATLAB程序调用格式:[x,minf]minMNT(f,x0,var,eps)其中,f:目标函数x0:初始点var:自变量向量eps:精度x:目标函数取最小值时的自变量值minf:目标函数的最小值修正牛顿法的MATLAB程序代码如下:function[x,minf]=minMNT(f,x0,var,eps)%目标函数:f;%初始点:x0;%自变量向量:var;%目标函数取最小值时的自变量值:x;%目标函数的最小值:minf;formatlong;ifnargin==3eps=1.0e-6;endtol=1;x0=transpose(x0);symsl;whiletol>epsgradf=jacobian(f,var);%梯度方向jacf=jacobian(gradf,var);%雅克比矩阵v=Funval(gradf,var,x0);tol=norm(v);pv=Funval(jacf,var,x0);p=-inv(pv)*transpose(v);y=x0+l*pyf=Funval(f,var,y);[a,b]=minJT(yf,0,0.1);xm=minHJ(yf,a,b);x1=x0+xm*p;x0=x1;endx=x1;minf=Funval(f,var,x);formatshort;