浅谈牛顿迭代

前言

话说每次讲跟 $newton$ 有关的东西，都得先 $\%$ 一下这位大佬。

引入

我们很早就知道伽罗瓦证明了五次及以上方程不具有普遍的求根公式，但是高次方程却充斥着我们的生活，因此在不同的领域求解不同的高次方程变得尤为困难。

在高中我们就学过，对于在 $[l,r]$ 上单调的函数 $f(x)$，若 $f(l)$ 与 $f(r)$ 异号，即 $f(l)\cdot f(r)\le0$ ，则在此区间内定有且仅有一个该函数 $f(x)$ 的根。

结论很直观，这里就不赘述了。看到单调性，我们很容易想到可以通过二分的方法来快速找到函数在区间 $[l,r]$ 内的根，这也是课本里教的方法。二分的复杂度已经是 $\Theta(\log_2 n)$ 的了，可谓是极其优秀，但是随着时代的进步，这种 求近似根 的方法已经显得效率有点低了。

想必大家都知道 $C++$ 中自带的 $STL$ 函数 $sqrt(a)$，它的作用是求 $a$ 的算术平方根，我们也可以理解为求解一个 $x^2-a=0$ 的方程，或者说找到函数 $f(x)=x^2-a$ 的正零点，亦可想到可以用我们学过的二分实现。

但是已经有大佬尝试过了，无论如何优化这种求近似根的二分，都无法超越 $STL$ 中自带的 $sqrt$ 函数，甚至被远远甩开一大截！这是为什么？我曾经很不理解，知道我认识了它

$newton~method$，牛顿迭代。

---

牛顿迭代

牛顿迭代也是一种求解方程近似根的算法，但是它的效率远超我们熟知的二分算法！

在了解牛顿迭代之前，我们必须得明白什么是导数。

---

导数

我们通常听到的导数定义是一个函数的瞬时变化率（瞬时不存在变化，因此这个“瞬时”没那么严谨，是一个极限概念而已，感性理解），但是在这里，对于 $f(x)$ 的导数 $f’(x)$ 最好的理解是，$f’(n)$ 所表示的切线是函数 $f(n)$ 当自变量为 $n$ 时的线性近似

什么意思呢？就是说 $f’(x)$ 是一条在 $f(x)$ 图像上且过点 $(x,f(x))$ 的一条切线的斜率。

对，导数就是函数的切线的斜率函数。

考虑斜率的定义，函数上 $x$ 点附近的切线的斜率就是 $\dfrac{f(x+\Delta x)-f(x)}{\Delta x}$ ， $\Delta x$ 是自变量 $x$ 的增量，通常取它趋近于 $0$

举个例子最直观不过了，我们考虑对函数 $f(x)=x^2$ 求导：

$$\begin{aligned} f'(x)&=\dfrac{f(x+\Delta x)-f(x)}{\Delta x}\\ &=\dfrac{(x+\Delta x)^2-x^2}{\Delta x}\\ &=\dfrac{(\Delta x)^2+2(\Delta x) x}{\Delta}\\ &=\Delta x+2x \end{aligned}$$

再考虑导数的定义是极限的，因此我们对 $\Delta x$ 取极限

$$\begin{aligned} f'(x)&=\lim_{\Delta x\rightarrow 0}\Delta x+2x\\ &=2x \end{aligned}$$

因此， $2x$ 就是 $f(x)=x^2$ 的导数。同理，考虑导数的几何意义，$2t(x-t)+t^2$ 是一条切 $x^2$ 于 $(t,t^2)$ 点的切线。而切线则是在该点上函数的线性近似。（扣题）

---

知道了切线是函数的一种线性近似，自然会生出一种想法：我们可以通过找到切线的零点，然后转移到此处，再来作切线，再来得到零点……因为切线是原函数的近似，因此如此迭代往复，得到的点将平方逼近原函数的零点。

一不小心，你就发现了牛顿迭代的核心思想！

我们把过程量化，再来系统的讲一遍：

1. 随便找到一个初始迭代的点 $C$
2. 得到在位置 $C$ 处的函数切线，并找到这条切线的零点，作为下一个迭代点。
3. 重复迭代步骤 2

desmos直观理解牛顿迭代过程

大概就是这么个过程：

---

数学

牛顿迭代的整体思路真的很好理解，但是只有思想无法实现就没办法帮助我们写代码。因此，我们需要将牛顿迭代真正的公式化。

考虑此时我们的初始点为 $x_0$，那么在该位置上的函数切线方程即为 $y=f’(x_0)(x-x_0)+f(x_0)$，找到零点也就是等于求解一元一次方程 $f(x_0)(x-x_0)+f(x_0)=0$

我们设 $x_1$ 为这个方程的解，也就是说 $f’(x_0)(x_1-x_0)+f(x_0)=0$，化简可得 $x_1=x_0-\dfrac{f(x_0)}{f’(x_0)}$

此时，倘若我们继续以 $x_1$ 作为初始点如此迭代下去，得到的点将具有以下迭代关系：

$$\Large x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$$

显然，$x_{n+1}$ 会快速接近零点。

使用这条公式，我们就可以写出牛顿迭代的代码：

#define exp 1e-10
double f(double x)
{
  return /*函数表达式*/
}
double df(double x)
{
  int dx=x+exp;
  return 1.0*(f(dx)-f(x))/dx;   //使用两个接近的点来模拟求导 
}
double newton(double x0)
{
  while(abs(f(x0))>1e-10) x0-=1.0*f(x0)/df(x0);   //迭代公式，精度足够就退出 
  return x0;
}

应用

很多问题都可以转化为找函数零点，而这正是牛顿迭代所擅长的，这里举几个简单的例子：

• 求函数局部最优解
  在函数类似山峰的部分，都有着导数为 $0$ 的特性，因此找山峰实际上就是求导数的零点。
• 对函数求值
  例如引入中的求 $\sqrt a$，我们可以理解为解 $x^2-a=0$ 的方程，依然是个找零点的过程。
  更一般的，对于任意一个函数 $f(a)$ 求值，其实际上就是在解 $x=f(a)$ 的方程，化简得 $f^{-1}(x)-a=0$，也是一个求零点的问题。
  ……

综上所述，在实际上，我们很多问题都需要用到牛顿迭代，而它的本质实际上感性上还是不难理解的。

---

参考资料

隔壁的张栩嘉-浅谈牛顿迭代法

一个Sqrt函数引发的血案