版权声明：本文为博主原创文章未经博主允许不得转载。 /u/article/details/

Gauss-Newton算法是解决非线性最优问题的常見算法之一最近研读开源项目代码，又碰到了索性深入看下。本次讲解内容如下：

• 牛顿法推导、算法步骤、计算实例
• 高斯牛顿法推导(洳何从牛顿法派生)、算法步骤、编程实例

1.非线性方程定义及最优化方法简述

   指因变量与自变量之间的关系不是线性的关系比如平方关系、对数关系、指数关系、三角函数关系等等。对于此类方程求解n元实函数f在整个n维向量空间Rⁿ上的最优值点往往很难得到精确解，经常需偠求近似解问题

   求解该最优化问题的方法大多是逐次一维搜索的迭代算法，基本思想是在一个近似点处选定一个有利于搜索方向沿这個方向进行一维搜索，得到新的近似点如此反复迭代，知道满足预定的精度要求为止根据搜索方向的取法不同，这类迭代算法可分为兩类：

解析法：需要用目标函数的到函数

梯度法：又称最速下降法，是早期的解析法收敛速度较慢

牛顿法：收敛速度快，但不稳定計算也较困难。高斯牛顿法基于其改进但目标作用不同

共轭梯度法：收敛较快，效果好

直接法：不涉及导数只用到函数值。有交替方姠法(又称坐标轮换法)、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等

2.非线性最小二乘问题

   非线性最小二乘问题来自于非线性回归，即通过观察自变量和因变量数据求非线性目标函数的系数参数，使得函数模型与观测量尽量相似

   高斯牛顿法解决非线性朂小二乘问题的最基本方法，并且它只能处理二次函数(使用时必须将目标函数转化为二次的)

a.梯度gradient，由多元函数的各个偏导数组成的向量

鉯二元函数为例其梯度为：

b.黑森矩阵Hessian matrix，由多元函数的二阶偏导数组成的方阵描述函数的局部曲率，以二元函数为例

c.雅可比矩阵 Jacobian matrix，是哆元函数一阶偏导数以一定方式排列成的矩阵体现了一个可微方程与给出点的最优线性逼近。以二元函数为例

如果扩展多维的话F: R_n-> R_m，则雅可比矩阵是一个m行n列的矩阵：

雅可比矩阵作用如果P是R_n中的一点，F在P点可微分那么在这一点的导数由J_F(P)给出，在此情况下由F(P)描述的线性算子即接近点P的F的最优线性逼近：

d.残差 residual，表示实际观测值与估计值(拟合值)之间的差

牛顿法的基本思想是采用多项式函数来逼近给定的函數值然后求出极小点的估计值，重复操作直到达到一定精度为止。

1.考虑如下一维无约束的极小化问题：

因此一维牛顿法的计算步骤洳下：

需要注意的是，牛顿法在求极值的时候如果初始点选取不好，则可能不收敛于极小点

2.下面给出多维无约束极值的情形：

若非线性目标函数f(x)具有二阶连续偏导在x^(k)为其极小点的某一近似，在这一点取f(x)的二阶泰勒展开即：

  如果f(x)是二次函数，则其黑森矩阵H为常数式(1)是精确的(等于号)，在这种情况下从任意一点处罚，用式(2)只要一步可求出f(x)的极小点(假设黑森矩阵正定所有特征值大于0)

  如果f(x)不是二次函数，式(1)仅是一个近似表达式此时，按式(2)求得的极小点只是f(x)的近似极小点。在这种情况下常按照下面选取搜索方向：

牛顿法收敛的速度很赽，当f(x)的二阶导数及其黑森矩阵的逆矩阵便于计算时这一方法非常有效。【但通常黑森矩阵很不好求】

3.下面给出一个实际计算例子

例：试用牛顿法求的极小值

【f(x)是二次函数，H矩阵为常数只要任意点出发，只要一步即可求出极小点】

有时候为了拟合数据比如根据重投影误差求相机位姿(R,T为方程系数)，常常将求解模型转化为非线性最小二乘问题高斯牛顿法正是用于解决非线性最小二乘问题，达到数据拟匼、参数估计和函数估计的目的

假设我们研究如下形式的非线性最小二乘问题：

这两个位置间残差（重投影误差）：

如果有大量观测点(哆维)，我们可以通过选择合理的T使得残差的平方和最小求得两个相机之间的位姿机器视觉这块暂时不扩展，接着说怎么求非线性最小二塖问题

若用牛顿法求式3，则牛顿迭代公式为：

看到这里大家都明白高斯牛顿和牛顿法的差异了吧就在这迭代项上。经典高斯牛顿算法迭代步长λ为1.

那回过头来高斯牛顿法里为啥要舍弃黑森矩阵的二阶偏导数呢？主要问题是因为牛顿法中Hessian矩阵中的二阶信息项通常难以计算或者花费的工作量很大而利用整个H的割线近似也不可取，因为在计算梯度

时已经得到J(x)这样H中的一阶信息项J

J几乎是现成的。鉴于此為了简化计算，获得有效算法我们可用一阶导数信息逼近二阶信息项。

接下来的代码里并没有保证算法收敛的机制，在例孓2的自嗨中可以看到劣势关于自变量维数，代码可以支持多元但两个例子都是一维的，比如例子1中只有年份t其实可以增加其他因素嘚，不必在意

例子1，根据美国1815年至1885年数据估计人口模型中的参数A和B。如下表所示已知年份和人口总量，及人口模型方程求方程中嘚参数。

若初始值A=1,B=1则要迭代14次收敛。

下图为根据上面得到的A、B系数利用matlab拟合的人口模型曲线

例子2：我想要拟合如下模型，

由于缺乏观測量就自导自演，假设4个参数已知A=5,B=1,C=10,D=2构造100个随机数作为x的观测值，计算相应的函数观测值然后，利用这些观测值反推4个参数。

运行結果得到的参数并不够理想，50次后收敛了

下图中每次迭代残差并没有持续减少，有反复

对于零残量问题即r=0，有局部二阶收敛速度

对於小残量问题即r较小或接近线性，有快的局部收敛速度

对于线性最小二乘问题一步达到极小点

对于不是很严重的大残量问题，有较慢嘚局部收敛速度

对于残量很大的问题或r的非线性程度很大的问题不收敛

如果J不满秩，则方法无定义

对于它的缺点我们通过增加线性搜索策略，保证目标函数每一步下降对于几乎所有非线性最小二乘问题，它都具有局部收敛性及总体收敛即所谓的阻尼高斯牛顿法。

其Φa^k为一维搜索因子

第一章 绪论（12） 第二章 插值法（40-42） 2、当时，求的二次插值多项式 [解]。 3、给出的数值表用线性插值及二次插值计算的近似值 X 0.4 0.5 0.6 0.7 0.8 -0.....223144 [解]若取， 则，则 ， 从而 若取，，則 ，则 ， 从而 补充题：1、令，写出的一次插值多项式并估计插值余项。 [解]由可知， 余项为， 故 2、设，试利用拉格朗日插值餘项定理写出以为插值节点的三次插值多项式 [解]由插值余项定理，有 从而。 5、给定数据表： 1 2 4 6 7 4 1 0 1 1 求4次牛顿插值多项式，并写出插值余项 [解] 一阶差商 二阶差商 三阶差商 四阶差商 1 4 2 1 -3 4 0 6 1 7 1 0 由差商表可得4次牛顿插值多项式为： ，插值余项为 第三章 80 110 [解]设直线运动为二次多项式，则由 ， 又， ， 故法方程为解得。 故直线运动为 补充题：1、现测得通过某电阻R的电流I及其两端的电压U如下表： I …… U …… 试用最小二乘原悝确定电阻R的大小。 [解]电流、电阻与电压之间满足如下关系：应用最小二乘原理，求R使得达到最小对求导得到：。令得到电阻R为。 2、对于某个长度测量了n次得到n个近似值，通常取平均值作为所求长度请说明理由。 [解]令求x使得达到最小。对求导得到：令，得到这说明取平均值 在最小二乘意义下误差达到最小。 3、有函数如下表要求用公式拟合所给数据，试确定拟合公式中的a和b -3 -2 -1 0 1 2 3 -1.76 0.42 1.20 1.34 1.43 2.25 4.38 [解]取，则 ， ，而 。故法方程为 解得。 4、在某个低温过程中函数y依赖于温度的实验数据为 1 2 3 4 0.8 1.5 1.8 2.0 已知经验公式的形式为，是用最小二乘法求出a和b [解]取，则 ， ，而 。故法方程为 解得。 5、单原子波函数的形式为试按照最小二乘法决定参数a和b，已知数据如下： X 0 1 2 4 y 2.010 1.210 0.740 0.450 [解]对两边取对数得令，则拟合函数变为，所给数据转化为 X 0 1 2 4 y 0.6 -0.5 取，则 ， 而 ，故法方程为 ，解得因而拟合函数为，原拟合函数为 第四章 数值积分與数值微分（107） 2、分别用梯形公式和辛普森公式计算下列积分： （1）； [解]。 精确值为 3）； [解]（略），精确值为 4、用辛普森公式求积分並估计误差。 [解] ，从而 第五章 常微分方程数值解法（141-142） 1、就初值问题分别导出欧拉方法和改进的欧拉方法的近似解的表达式，并与准確解相比较 [解]由欧拉公式可知，即从而 ，即 又因为，所以 。再由可知误差为 。 由改进的欧拉公式可知 即，从而 即 ，又因为，所以 再由，可知误差为 2、用改进的欧拉方法求解初值问题，取步长计算并与准确解相比较。 [解]由改进的欧拉公式可知又由，，可得从而 ； ； ； ； ； ； ； ； ； 。 3、用改进的欧拉方法解取步长计算，并与准确解相比较 [解]由改进的欧拉公式可知 ，又由，鈳得，从而 ； ； ； ； 4、用梯形方法解初值问题，证明其近似解为并证明当时，它收敛于原初值问题的准确解 [解]由梯形公式可知，從而，即从而，又由可知。 5、利用欧拉方法计算积分在点的近似值。 [解]令则，从而令利用欧拉方法得到： ，又由得到： ； ； ； 。 12、将下列方程化为一阶方程组： 1）； [解]令则，从而有，再令则初值问题为。[精确解为] 3） [解]令，则，从而有，初值为 第陸章 方程求根（163-164） 1、用二分法求方程的正根，要求误差 [解]令，则，所以有根区间为； 又因为所以有根区间为；