1.算法简介

牛顿法作为求解非线性方程的一种经典的迭代方法，它的收敛速度快，有内在函数可以直接使用。可以结合MATLAB对其进行应用，求解方程。

牛顿迭代法（Newton's method）又称为牛顿–拉夫逊方法（Newton－Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解的方法，其基本思想是利用目标函数的二次泰勒展开，并将其极小化。牛顿法使用函数f（x）的泰勒级数的前面几项来寻找方程f（x）＝0的根。牛顿法是求方程根的重要方法之一，其最大优点是在方程f（x）＝0的单根附近具有平方收敛，并且该法还可以用来求方程的重根、复根，此时非线性收敛，但是可通过一些方法变成线性收敛。

牛顿法的几何解释：

方程f（x）＝0的根x∗可解释为曲线y＝f（x）与x轴的交点的横坐标。

牛顿算法的基本思想是利用二次函数近似目标函数，比最速下降法的一次函数更近了一步，将次二次函数的极小点作为新的迭代点。

设xk是根x∗的某个近似值，过曲线y＝f（x）上横坐标为xk的点Pk引切线，并将该切线与x轴的交点的横坐标xk＋1作为x∗的新的近似值。鉴于这种几何背景，牛顿法也称为切线法。

除了阶梯下降法，牛顿法也是机器学习中用到的比较多的一种优化算法。牛顿法的基本思想是利用迭代点xk处的一阶导数（梯度）和二阶导数（Hessen矩阵）对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值。牛顿法的速度相当快，并且能高度逼近最优值。牛顿法分为基本的牛顿法和全局牛顿法。

2.牛顿迭代公式

（1）最速下降法

以负阶梯方向作为极小化算法的下降方向，也称为梯度法。

设函数f（x）在xk附近连续可微，且gk＝∇f（xk）≠0。由泰勒展开式

f(x)＝f(xk)＋(x－xk)T∇f(xk)＋ο(｜｜x－xk｜｜)

可知，若记为x－xk＝αdk，则满足的方向dk是下降方向。当α取定后，的值越小，即的值越大，函数下降得越快。由Cauchy－Schwartz不等式，得

故当且仅当dk＝－gk时，最小，从而称－gk是最速下降方向。

最速下降法的迭代格式为

xk＋1＝xk－αkgk

（2）牛顿法

设f（x）是二次可微实函数，xk∈Rn，Hessen矩阵∇2f（xk）正定。在xk附近用二次泰勒展开近似f：

s＝x－xk，q（k）（s）为f（x）的二次近似。将上式右边极小化，便得

xk＋1＝xk－[∇2 f(xk)]－1∇f(xk)

在这个公式里，步长因子αk＝1。令Gk＝∇2 f（xk），gk＝∇f（xk），则上式也可写成

显然，牛顿法也可以看成在椭球范数｜｜·｜｜Gk下的最速下降法。

实际上，对于

sk是极小化问题的解。该极小化问题依赖于所取的范数，当采取l2范数时，sk＝－gk，所得方法为最速下降法。当采用椭球范数时，所得方法即为牛顿法。

对于正定二次函数，牛顿法一步即可得到最优解。而对于非二次函数，牛顿法并不能保证有限次迭代求得最优解，但由于目标函数在极小点附近近似于二次函数，故当初始点靠近极小点时，牛顿法的收敛速度一般是快的。

3.基本牛顿法的流程

①给定终止误差0≤ε<1，初始点x0＝Rn，令k＝0；

②计算gk＝∇f（x），若｜｜gk｜｜≤ε，则停止，输出x∗≈xk；

③计算Gk＝∇2f（xk），并求解线性方程组，得解dk：Gkd＝－gk；

④令xk＋1＝xk＋dk，k＝k＋1，并转②。

4.牛顿法收敛定理

设f＝C（2），xk充分靠近x∗，∇f（x∗）＝0，如果∇2 f（x∗）正定，且Hessen矩阵G（x）满足Lipschitz条件，即存在β>0，使得对所有i，j，有

｜Gij(x)－Gij(y)｜≤β｜｜x－y｜｜

其中，Gij（x）是Hessen矩阵G（x）的（i，j）元素，则对一切k，牛顿迭代公式有意义，且所得序列{xk}收敛到x∗，并且具有二阶收敛速度。

在实际求解中，当初始点远离最优解时，Hessen矩阵Gk不一定正定。牛顿方向不一定是下降方向，其收敛性不能保证。这说明恒取步长因子为1的牛顿法是不合适的，应该在牛顿法中采用某种一维搜索来确定步长因子。但是应该强调的是，仅当步长因子{xk}收敛到1时，牛顿法才是二阶收敛的。这时牛顿法的迭代公式为

其中，αk是一维搜索产生的步长因子。(www.daowen.com)

5.带步长因子的牛顿法

步骤1：准备。选定初始近似值x0，计算f0＝f（x0），f′0＝f′（x0）。

步骤2：迭代。按公式：

迭代一次，得新的近似值x1：

f1＝f(x1)，f′1＝f′(x1)

步骤3：控制。如果x1满足｜δ｜<ε1或｜f1｜<ε2，则终止迭代，以x1作为所求的根；否则转步骤4。此处，ε1，ε2是允许误差，而

其中，C是取绝对误差或相对误差的控制常数，一般可取C＝1。

步骤4：修改。如果迭代次数达到预先制订的次数N或者f′1＝0，则方法失败；否则，以（x1，f1，f′1）代替（x0，f0，f′0），转步骤2继续迭代。

6.实例应用

例5.6　函数，以x0＝[1，2]Τ为初始点，用牛顿法对其进行迭代。

解：根据题意编写MATLAB代码如下：

运行MATLAB后，得到结果如下：

即经过4次迭代，找到了该函数的最小值点。

例5.7　求f（x）＝2e－xsinx在区间[0，6]内的极小值点和极小值。

命令如下：

注：fminbnd为求一元函数y＝f（x）在（x1，x2）内的极小值的命令：

′fun′是函数f（x）的表达式，当然，也可以是关于f（x）的函数m文件名。返回值x是极小值点。

这是一元函数求极值，那么怎么求多元函数的极值呢？可以用下面最简形式的命令：

如果还必须满足更苛刻的要求，可以用下面的命令：

说明：

①返回值中，x是极小值点。如果需要相应的极小值，可以用fval＝fun（x）。

②这里′fun′必须是事先定义的函数m文件。

③x0是迭代初值。

④options是控制参数。

在使用options前，可以根据要求对options的某些分量进行赋值，否则，options会自动使用缺省值。

例5.8　已知，求f（x1，x2）在点（1，2）附近的极小值。

首先，建立m文件，文件名取函数名myfun.m。

然后调用命令如下：

例5.9　已知无约束优化问题的目标函数是，利用带步长因子的牛顿法，求在初始迭代点x0＝[1，1]Τ下，迭代次数不超过500次的目标函数最优值。

解：首先写出带步长因子牛顿法的MATLAB程序如下：

建立目标函数的MATLAB代码：

建立目标函数梯度的MATLAB代码：

建立目标函数Hessen矩阵的MATLAB代码：

调用上面的程序，在MATLAB命令窗口中输入：

运行后得到结果如下：

得到目标函数的最优值为4。