文章目录
牛顿法求解函数零点基本思想形象理解牛顿法求解函数极值点一维情况高维情况求极值点时与梯度下降法比较相同点不同点Reference牛顿法求解函数零点
基本思想
设有一个连续可导函数 y=f(x)y = f(x)y=f(x)，为了求解方程f(x)=0f(x)=0f(x)=0，可采用这样的方法来近似求解，因为f(x)f(x)f(x)在x=x0x = x_0x=x0处的泰勒展开式为：
f(x)=f(x0)+f′(x0)(x−x0)+f′′(x0)(x−x0)22!+...+f(n)(x0)(x−x0)nn!+o((x−x0)n)f(x) = f(x_0) +f^{\prime}(x_0)(x-x_0)+\frac{f^{\prime\prime}(x_0)(x-x_0)^2}{2!} +...+\frac{f^{(n)}(x_0)(x-x_0)^n}{n!}+o((x-x_0)^n)f(x)=f(x0)+f′(x0)(x−x0)+2!f′′(x0)(x−x0)2+...+n!f(n)(x0)(x−x0)n+o((x−x0)n)
考虑到一次方程容易解，而二次以及以上高次方程不一定有解，取泰勒展开式的线性部分来近似f(x)f(x)f(x)有：
f(x)=f(x0)+f′(x0)(x−x0)f(x)=f(x_0) +f^{\prime}(x_0)(x-x_0)f(x)=f(x0)+f′(x0)(x−x0)
若f′(x0)f^{\prime}(x_0)f′(x0)不等于0，将f(x)=0f(x)=0f(x)=0代入上式可得：
x1=x0−f(x0)f′(x0)x_1 = x_0 - \frac{f(x_0)}{f^{\prime}(x_0)}x1=x0−f′(x0)f(x0)
称x1x_1x1是方程f(x)=0f(x)=0f(x)=0的一次近似根，由此得到一个n次迭代式：
xn+1=xn−f(xn)f′(xn)(1)x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime}(x_n)} \tag{1}xn+1=xn−f′(xn)f(xn)(1)
利用(1)(1)(1)求解时，先对方程f(x)=0f(x)=0f(x)=0的根猜一个初始的估计值x0x_0x0,可以证明如果f(x)f(x)f(x)是连续的，并且待求的零点是孤立的，那么在零点周围存在一个区域，只要初始猜测值x0x_0x0位于这个邻近区域内，进行多次迭代后那么牛顿法必定收敛。
形象理解
如上图所示，过(x0,f(x0))(x_0, f(x_0))(x0,f(x0))做f(x)f(x)f(x)的切线，切线与 xxx 轴交点为 x1x_1x1, 过(x1,f(x1))(x_1, f(x_1))(x1,f(x1))继续做f(x)f(x)f(x)的切线，与 xxx 轴交点为 x2x_2x2 …不断迭代， xnx_nxn的值将趋近于方程f(x)=0f(x)=0f(x)=0的根。
牛顿法求解函数极值点
一维情况
对于f(x)f(x)f(x)的泰勒展开式，若取到二次项来近似，则：
f(x)=f(x0)+f′(x0)(x−x0)+f′′(x0)(x−x0)22!f(x) = f(x_0) +f^{\prime}(x_0)(x-x_0)+\frac{f^{\prime\prime}(x_0)(x-x_0)^2}{2!} f(x)=f(x0)+f′(x0)(x−x0)+2!f′′(x0)(x−x0)2
两边对xxx求导，有：
f′(x)=f′(x0)+f′′(x0)(x−x0)f^{\prime}(x) = f^{\prime}(x_0) + f^{\prime\prime}(x_0)(x-x_0)f′(x)=f′(x0)+f′′(x0)(x−x0)
函数f(x)f(x)f(x)的极值点满足f′(x)=0f^{\prime}(x) = 0f′(x)=0,代入上式中，有：
x1=x0−f′(x0)f′′(x0)x_1=x_0 - \frac{ f^{\prime}(x_0)}{f^{\prime\prime}(x_0)}x1=x0−f′′(x0)f′(x0)
由此可以得到一个求解方程f′(x)=0f^\prime(x)=0f′(x)=0的迭代式：
xn+1=xn−f′(xn)f′′(xn)(2)x_{n+1}=x_n - \frac{ f^{\prime}(x_n)}{f^{\prime\prime}(x_n)} \tag{2}xn+1=xn−f′′(xn)f′(xn)(2)
高维情况
上述描述的是自变量xxx是一维的情况，当xxx是一个多维向量时，同样有：
xn+1=xn−H−1(xn)∇f(xn)(3)x_{n+1} = x_{n} - H^{-1}(x_n)\nabla{f(x_n)} \tag{3}xn+1=xn−H−1(xn)∇f(xn)(3)
其中∇f(xn)\nabla{f(x_n)}∇f(xn)是f(x)f(x)f(x)在xnx_nxn处的梯度，H(xn)H(x_n)H(xn)是f(x)f(x)f(x)在xnx_nxn处的海森矩阵(高维函数的二阶导)。
当然，为了在迭代的时候使选取的xnx_nxn落在导数为0的点附近，记d=H−1(xn)∇f(xn)d=H^{-1}(x_n)\nabla{f(x_n)}d=H−1(xn)∇f(xn)
给ddd加一个类似于学习率的系数γ\gammaγ有：
xn+1=xn−γd(4)x_{n+1} = x_n-\gamma d \tag{4}xn+1=xn−γd(4)
每次迭代时需要选择合适的γ\gammaγ。
求极值点时与梯度下降法比较
相同点
和梯度下降法一样，牛顿法寻找的也是导数为0的点，这不一定是极值点，因此会面临局部极小值和鞍点问题。
不同点
与梯度下降法相比，牛顿法求解函数极值点时需要求解海森矩阵的逆矩阵，当xxx的维度较高时，这个计算过程会很费时，不如梯度下降法快。
Reference
牛顿法
理解牛顿法
