泰勒公式，雅可比矩阵，海塞矩阵，牛顿法
泰勒公式，雅可比矩阵，海塞矩阵，牛顿法
泰勒公式是一个在函数上取某点的近似值，如果函数足够平滑的话，在已知函数在某一点的各阶导数值的情况之下，泰勒公式可以用这些导数值做系数构建一个多项式来近似函数在这一点的近似值。泰勒公式还给出了这个多项式和实际的函数值之间的偏差
泰勒公式是将一个在x=x0处具有n阶导数的函数f(x)利用关于(x-x0)的n次多项式来逼近函数的方法。
若函数f(x)在包含x0的某个闭区间[a,b]上具有n阶导数，且在开区间(a,b)上具有(n+1)阶导数，则对闭区间[a,b]上任意一点x，成立下式：
其中，
表示f(x)的n阶导数，等号后的多项式称为函数f(x)在x0处的泰勒展开式，剩余的Rn(x)是泰勒公式的余项，是(x-x0)n的高阶无穷小
参考资料:
https://baike.baidu.com/item/%E6%B3%B0%E5%8B%92%E5%85%AC%E5%BC%8F/7681487?fr=aladdin
雅可比矩阵是一阶偏导数以一定方式排列成的矩阵，其行列式称为雅可比行列式。雅可比矩阵的重要性在于它体现了一个可微方程与给出点的最优线性逼近,例子：
由球坐标系到直角坐标系的转化由F函数给出︰
此坐标变换的雅可比矩阵是
的F函数:
其雅可比矩阵为:
此例子说明雅可比矩阵不一定为方阵。
如果m = n, 那么FF是从n维空间到n维空间的函数, 且它的雅可比矩阵是一个方块矩阵. 于是我们可以取它的行列式, 称为雅可比行列式.
如果连续可微函数FF在pp点的雅可比行列式不是零, 那么它在该点附近具有反函数. 这称为反函数定理；如果pp点的雅可比行列式是正数, 则FF在pp点的取向不变；如果是负数, 则FF的取向相反；雅可比行列式的绝对值, 就可以知道函数FF在pp点的缩放因子。
对于取向问题可以这么理解, 例如一个物体在平面上匀速运动, 如果施加一个正方向的力FF, 即取向相同, 则加速运动, 类比于速度的导数加速度为正；如果施加一个反方向的力FF, 即取向相反, 则减速运动, 类比于速度的导数加速度为负.
在数学中, 海森矩阵(Hessian matrix或Hessian)是一个自变量为向量的实值函数的二阶偏导数组成的方块矩阵
一般来说, 牛顿法主要应用在两个方面, 1, 求方程的根; 2, 最优化。
1，求方程的根
其原理便是使用泰勒展开，然后去线性部分，即：
     (1)
然后令上式等于0，则有：
                 (2)
经过不断迭代：
               (3)
当精度达到要求的时候停止迭代。
迭代示意图如上所示。
2，最优化
最优化一般是求极大或极小问题，这可以转变为求导数零点，然后转变为1的情形。
即f' = 0;
把f(x)用泰勒公式展开到二阶，即：
                                        (4)
等号左边和f(x)近似相等，抵消。然后对求导，得到：
                                                                            (5)
更进一步：
                                                                                (6)
然后得到迭代式子：
                                                             (7)
以上只针对单变量进行讨论，如果对多变量就要引入雅克比矩阵和海森矩阵
简单介绍一下二者，雅克比矩阵为函数对各自变量的一阶导数，海森矩阵为函数对自变量的二次微分。形式分别如下：
把两个矩阵代入(7)中
参考:
https://blog.csdn.net/ubunfans/article/details/41520047
泰勒公式，雅可比矩阵，海塞矩阵，牛顿法相关教程

泰勒公式

泰勒公式是一个在函数上取某点的近似值，如果函数足够平滑的话，在已知函数在某一点的各阶导数值的情况之下，泰勒公式可以用这些导数值做系数构建一个多项式来近似函数在这一点的近似值。泰勒公式还给出了这个多项式和实际的函数值之间的偏差

泰勒公式是将一个在x=x0处具有n阶导数的函数f（x）利用关于（x-x0）的n次多项式来逼近函数的方法。

若函数f（x）在包含x0的某个闭区间[a,b]上具有n阶导数，且在开区间（a,b）上具有（n+1）阶导数，则对闭区间[a,b]上任意一点x，成立下式：



其中，

表示f（x）的n阶导数，等号后的多项式称为函数f（x）在x0处的泰勒展开式，剩余的Rn（x）是泰勒公式的余项，是（x-x0）n的高阶无穷小



参考资料:

https://baike.baidu.com/item/%E6%B3%B0%E5%8B%92%E5%85%AC%E5%BC%8F/7681487?fr=aladdin

 

雅可比矩阵

雅可比矩阵是一阶偏导数以一定方式排列成的矩阵，其行列式称为雅可比行列式。雅可比矩阵的重要性在于它体现了一个可微方程与给出点的最优线性逼近,例子：

由球坐标系到直角坐标系的转化由F函数给出︰









此坐标变换的雅可比矩阵是



 的F函数:









其雅可比矩阵为:



此例子说明雅可比矩阵不一定为方阵。

 

雅可比行列式

如果m = n, 那么FF是从n维空间到n维空间的函数, 且它的雅可比矩阵是一个方块矩阵. 于是我们可以取它的行列式, 称为雅可比行列式.

如果连续可微函数FF在pp点的雅可比行列式不是零, 那么它在该点附近具有反函数. 这称为反函数定理；如果pp点的雅可比行列式是正数, 则FF在pp点的取向不变；如果是负数, 则FF的取向相反；雅可比行列式的绝对值, 就可以知道函数FF在pp点的缩放因子。

对于取向问题可以这么理解, 例如一个物体在平面上匀速运动, 如果施加一个正方向的力FF, 即取向相同, 则加速运动, 类比于速度的导数加速度为正；如果施加一个反方向的力FF, 即取向相反, 则减速运动, 类比于速度的导数加速度为负.

海森Hessian矩阵

在数学中, 海森矩阵(Hessian matrix或Hessian)是一个自变量为向量的实值函数的二阶偏导数组成的方块矩阵



 

 

牛顿法

一般来说, 牛顿法主要应用在两个方面, 1, 求方程的根; 2, 最优化。

1，求方程的根

其原理便是使用泰勒展开，然后去线性部分，即：

      (1)

然后令上式等于0，则有：

                 (2)

经过不断迭代：

               (3)

当精度达到要求的时候停止迭代。

迭代示意图如上所示。



2，最优化

最优化一般是求极大或极小问题，这可以转变为求导数零点，然后转变为1的情形。

即f' = 0;

把f(x)用泰勒公式展开到二阶，即：

                                        (4)

等号左边和f(x)近似相等，抵消。然后对求导，得到：

                                                                            (5)

更进一步：

                                                                                (6)

然后得到迭代式子：

                                                              (7)

以上只针对单变量进行讨论，如果对多变量就要引入雅克比矩阵和海森矩阵

 

用牛顿法解无约束一维极值问题

原理：

1.给定初始点x0,及精度>0,令k=0;

2.若| f'(Xk) |<,停止，极小点为Xk;

3.

4.令k=k+1,转2

算法的matlab 实现：

function [x,minf]=minNewton(f,x0,eps)
%format long;
if nargin==2
    eps=1.0e-6;
end

df=diff(f);
d2f=diff(df);

k=0;
tol=1;

while tol>eps
    dfx=subs(df,findsym(df),x0);
    d2fx=subs(d2f,findsym(d2f),x0);
    x1=x0-dfx/d2fx;
    k=k+1;
    tol=abs(dfx);
    x0=x1;
end

x=x1;
minf=subs(f,findsym(f),x);
%format short;

用牛顿法解无约束多维极值问题

简单介绍一下二者，雅克比矩阵为函数对各自变量的一阶导数，海森矩阵为函数对自变量的二次微分。形式分别如下：





 

把两个矩阵代入(7)中



 

function [x,minf]=minNT(f,x0,var,eps)

format long;
if nargin==3
    eps=1.0e-6;
end

to1=1;
x0=transpose(x0);
while to1 > eps
    gradf = jacobian(f,var);
    jacf = jacobian(gradf, var);
    v = Funval(gradf, var,x0);
    to1=norm(v);
    pv=Funval(jacf,var,x0);
    p = -inv(pv)* transpose(v);
    x1=x0+p;
    x0=x1;
end
x=x1;
minf =Funval(f,var,x);
format short;

参考:

https://blog.csdn.net/ubunfans/article/details/41520047

 

http://blog.punkid.org/2008/02/28/compute-the-square-root-via-newtons-iteration/




求n的平方根，先假设一猜测值X0 =
 1，然后根据以下公式求出X1，再将X1代入公式右边，继续求出X2…通过有效次迭代后即可求出n的平方根，Xk+1



假设f(x)是关于X的函数:



求出f(x)的一阶导，即斜率:



简化等式得到:



然后利用得到的最终式进行迭代运算直至求到一个比较精确的满意值，为什么可以用迭代法呢?理由是中值定理(Intermediate Value Theorem):


如果f函数在闭区间[a,b]内连续，必存在一点x使得f(x)
 = c，c是函数f在闭区间[a,b]内的一点


我们先猜测一X初始值，例如1，当然地球人都知道除了1本身之外任何数的平方根都不会是1。然后代入初始值，通过迭代运算不断推进，逐步靠近精确值，直到得到我们主观认为比较满意的值为止。例如要求768的平方根，因为252 =
 625，而302 =
 900，我们可先代入一猜测值26，然后迭代运算，得到较精确值:27.7128。

回到我们最开始的那个”莫名其妙”的公式，我们要求的是N的平方根，令x2 =
 n，假设一关于X的函数f(x)为:

f(X) = X2 -
 n

求f(X)的一阶导为:

f'(X) = 2X

代入前面求到的最终式中:

Xk+1 =
 Xk - (Xk2 -
 n)/2Xk

化简即得到我们最初提到的那个求平方根的神奇公式了:

牛顿法和拟牛顿法是求解无约束最优化的常用方法，牛顿法是迭代算法，每一步需要求解目标函数的海赛矩阵的逆矩阵，计算比较复杂，拟牛顿法通过正定矩阵近似海赛矩阵的逆矩阵或海赛矩阵，简化了这一过程。



泰勒公式

在看牛顿法之前先看一下泰勒展开： 

泰勒公式一句话描述：就是用多项式函数去逼近光滑函数

泰勒公式是将一个在$x=x_0$处具有n阶导数的函数$f(x)$利用关于$(x-x_0)$的n次多项式来逼近函数的方法。 

若函数$f(x)$在包含$x_0$的某个闭区间[a,b]上具有n阶导数，且在开区间(a,b)上具有(n+1)阶导数，则对闭区间[a,b]上任意一点x，成立下式： 



其中，  表示$f(x)$的n阶导数，等号后的多项式称为函数f(x)在$x_0$处的泰勒展开式，剩余的$R_n(x)$是泰勒公式的余项，是$(x-x_0)^n$的高阶无穷小。 

如果 $a=0$的话，就是麦克劳伦公式：
 $$f(x)=\sum_{n=0}^N \frac{f^{(n)}{}(0)}{n!}x^n+R_n(x)$$  

其组成部分是由幂函数和相应的系数组成，其中的幂函数其实只有两种形态，一种是关于 Y 轴对称，一种是关于原点对称，并且指数越大，增长速度越大。 

那幂函数组成的多项式函数有什么特点呢？各幂函数加上相应的系数，通过改变系数，多项式可以像铁丝一样弯成任意的函数曲线。 

eg：用多项式对 $e^x$ 进行逼近


$e^x=1+x+\frac{1}{2!}x^2+\cdots+\frac{1}{n!}x^n+R_n(x)$ 



增加一个 \frac{1}{4!}x^4 看看 



增加一个 \frac{1}{5!}x^5 看看 



可以看出，$\frac{1}{n!}x^ n$ 不断的弯曲着那根多项式形成的铁丝去逼近 $e^ x$。并且 $n$ 越大，起作用的区域距离0越远。

但还有一个例子我觉得有必要说一下： 

用多项式对 $sin(x)$ 进行逼近:

$sin(x)=x-\frac{1}{3!}x^3+\cdots+\frac{(-1)^n}{(2n+1)!}x^{(2n+1)}+R_n(x)$



同样的，我们再增加一个 $\frac{1}{7!}x^7$ 试试



可以看到$\frac{1}{7!}x^7$ 在适当的位置，改变了 $4x-\frac{1}{3!}x^3+\frac{1}{5!}x^5$ 的弯曲方向，最终让$x-\frac{1}{3!}x^3+\frac{1}{5!}x^5-\frac{1}{7!}x^7$更好的逼近了$sin(x)$



参考：


  
http://www.matongxue.com/madocs/7.html#/madoc




牛顿法

五次及以上多项式方程没有根式解（就是没有像二次方程那样的万能公式），这个是被伽罗瓦用群论做出的最著名的结论，但牛顿法可以求出近似解。

要讲牛顿迭代法之前我们先说一个关键问题：切线是曲线的线性逼近。

下面是 $f(x)=x^2$  的图像 



放大切点处，看看 



再放大切点处，看看 



可以看出放大之后切线和f(x)非常接近了。很明显，如果我们进一步放大图像，A点切线就越接近f(x)。

现在可以引入牛顿法了： 

随便找一个曲线上的A点（为什么随便找，根据切线是切点附近的曲线的近似，应该在根点附近找，但是很显然我们现在还不知道根点在哪里），做一个切线，切线的根（就是和x轴的交点）与曲线的根，还有一定的距离。此时从这个切线的根出发，做一根垂线，和曲线相交于B点，继续上面的步骤： 







经过多次迭代后，很明显越来越接近曲线的根了（但只会更接近根），此时称为迭代收敛了。

牛顿法的代数解法：当曲线方程为$f(x)$ ，我们在$x_n$点做切线，求$x_{n+1}$： 

此时容易得出，$x_n$点的切线方程为：$f(x_n)+f'(x_n)(x-x_n)$要求$x_{n+1}$，即相当于求$f(x_n)+f'(x_n)(x-x_n)=0$的解，即$f(x_n)+f'(x_n)(x_{n+1}-x_n)=0\implies$: $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$

但还有一些形式的函数是不收敛的，所以要注意以下问题：


函数在整个定义域内最好是二阶可导的
注意起始点的选择


牛顿法的基本思想是：在现有极小点估计值的附近对$f(x)$做二阶泰勒展开，进而找到极小点的下一个估计值。设$x_k$为当前的极小点估计值，则： 

 $$\varphi(x)=f(x_k)+f'(x_k)(x-x_k)+\frac{1}{2}f''(x_k)(x-x_k)^2$$ 表示$f(x)$在$x_k$附近的二阶泰勒展开式（略去了关于$x-x_k$的高阶项），由于求的是最值，由极值必要条件可知，$\varphi(x)$应满足 $$\varphi'(x)=0$$ 即 $$f'(x_k)+f''(x_k)(x-x_k)=0$$ 从而得到 $$x=x_k-\frac{f'(x_k)}{f''(x_k)}$$ 于是，若给定初始值$x_0$,则可以构造如下的迭代格式 $$x_{k+1}=x_k-\frac{f'(x_k)}{f''(x_k)}, k=0,1....$$ 可通过产生序列{$x_k$}来逼近$f(x)$的极小点.在一定条件下，{$x_k$}可以收敛到$f(x)$的极小点。 

对于N>1的情形，二阶泰勒展开式可以做推广，此时 $$\varphi(X)=f(X_k)+\bigtriangledown f(X_k)(X-X_k)+\frac{1}{2}(X-X_k)^T\bigtriangledown ^2f(X_k)(X-X_k)$$ 其中$\bigtriangledown f$为$f$的梯度向量，$\bigtriangledown ^2f$为$f$的海森矩阵，其定义如下：




注意，$\bigtriangledown f$和$\bigtriangledown ^2f$中的元素均为关于$X$的函数，以下简记为$g$和$H$.特别是若$f$的混合偏导数可交换次序，则海森矩阵为对称矩阵。而$\bigtriangledown f(X_k)$和$\bigtriangledown^2f(X_k)$则表示将$X$取为$x_k$后得到的实值向量和矩阵，以下分别将其简记为$g_k$和$H_k$ 

同样的，由于是求极小点，极值必要条件 要求它为$\varphi(X)$的驻点，即
 $$\bigtriangledown \varphi(X)=0$$ 通过在上式中两边作用一个梯度算子，得到： $$g_k+H_k(X-X_k)=0$$ 此时若矩阵$H_k$非奇异，可解得 $$X=X_k-H_k^{-1}g_k$$ 若给定初始值$X_0$,则可同样构造出迭代格式 $$X_{k+1}=X_k-H_k^{-1}g_k$$ 这就是牛顿迭代法，其迭代格式中的搜索方向为$-H_k^{-1}g_k$称为牛顿方向。


当目标函数是二次函数时，由于二次泰勒展开函数与原目标函数不是近似而是完全相同的二次式，海森矩阵退化为一个常数矩阵，从任一初始点出发，只需一步迭代即可达到极小点，因此牛顿法是一种具有二次收敛的算法。对于非二次函数，若函数的二次性态较强，或迭代点已进入极小点的邻域，则其收敛速度也是很快的。

参考：


  
http://blog.csdn.net/itplus/article/details/21896453


拟牛顿法