【数学】以普通高中生的眼光深入牛顿迭代法

Newton's method for finding roots

前言&前置知识

• 前置知识：导数的定义与基本运算

如今 whk 确确实实讲了牛顿法，就是那个切线求导数近似解，效率是二分法的忘了多少倍。

（不觉得这很酷吗）

那么牛顿迭代到底有没有比课本更深刻一点的东西捏。

如有错误请指出。

基础

我们已经知道，\(f'(x_0)\) 可以看作函数 \(f(x)\) 在 \(x=x_0\) 的切线斜率 \(k\)，那么我们想要求一个方程的近似解时：

例如：求以下函数的根

我们设 \(f(x)=\frac{x^3}{15}-\frac{3x^2}{5}+2x-\frac{12}{5}\)，那么这个方程的近似解就是函数 \(f(x)\) 与 \(x\) 轴的交点的横坐标。

我们可以先随机 random 一个数 \(x_0\)（当然 \(x_0\) 越接近零点越好），在 \(x_0\) 上做一条切线，切线的斜率在某种意义上或许是可以代表函数增减趋势的，那么我们使得这条切线与 \(x\) 轴的交点设为 \(x_1\)，如此，\(x_1\) 在某种意义上就更加“接近”零点。

如图：

（个人认为，在原理上，这里的接近并非距离更加接近，而是更加接近函数图像在该点变化之前的点的横坐标，但是因为函数中 \(1\) 个 \(x\) 只对应 \(1\) 个 \(y\)，成映射关系，不存在山路十八弯的情况,所以似乎大多时候是更接近零点）

因此我们可以得到一个数列 \({x_n}\)，这个数列越来越接近零点，被称为“牛顿数列”。

如果 \(f(x)\) 在点 \((x_0,f(x_0))\) 处切线的斜率是 \(f'(x_0)\)，则切线方程为：

在 \(f'(x_0)\neq 0\) 时，存在：

即：

牛顿迭代法的收敛率是平方级别，每次迭代后精确的数位会翻倍，其收敛性的证明请参考citizendium - Newton method Convergence analysis，这里不深入讨论，因为我不会。

但是因为牛顿迭代法一般情况下只具有局部收敛性，所以当 \(x_0\) 在收敛区间内以平方速度收敛，距离平方根较远时则不能保证。

我们可以举一个例子，求解 \(x^3-x-1=0\) 在 \(x_0=1.5\) 附近的根。

计算过程如下：

那么如果我们将 \(x_0=0.5\) 呢？

我不想计算了，直接看函数图像如下：

应用：手动开方

众所周知，因为心胸狭隘的河北不让带计算器，所以我们必须学会手动开方（？）

以上为我瞎扯，事实上手动开根一般情况下没有什么用处，仅在某些估值时可能用上。大部分情况下，背诵常用的根号值是更加经济的选择。

手动开方的方式不止牛顿迭代法，但我认为牛顿迭代法是简单且效率的。

我们不难想到这就是解 \(x^2=n\) 这个方程。

所以直接套上面的公式，容易得到：

它的精度很高，不信你自己试试。

这个代码还是比较好写的。

double sqrt_newton(double n) {
  const double eps = 1E-15;
  double x = 1;
  while (true) {
    double nx = (x + n / x) / 2;
    if (abs(x - nx) < eps) break;
    x = nx;
  }
  return x;
}

优化：牛顿下山法

它的英文名字就叫 Newton down-hill method（

如上所言：

但是因为牛顿迭代法一般情况下只具有局部收敛性，所以当 \(x_0\) 在收敛区间内以平方速度收敛，距离平方根较远时则不能保证。

下山法的目的，就是保证迭代过程中 \(|f(x_{k+1})|<|f(x_k)|\) 恒成立。

在确保上式的情况下，我们如何让这个东西成立捏？

可以看看上面求解 \(x^3-x-1=0\) 在 \(x_0=1.5\) 附近的根时提到的图像。

我自己想的就是，稳定的单调时其 \(x_{k+1}\) 的图像越平稳。

只以普通高中生的眼光来看，我们现在是不太能证明的好像，只能姑且如下解释，毕竟我菜啊。

这是因为通过使 \(x_{k+1}\) 更接近 \(x_k\) ，我们可以更好地利用函数局部的线性性质来逼近函数的根。如果两个迭代点相距较远，可能会导致迭代过程发散或者收敛速度变慢。

因此我们令：

然后设一个下山因子 \(\lambda\)，对其进行加权平均，加权平均的目的是为了更好地平衡初始点和迭代点之间的差异，以便更快地逼近函数的根。

于是有：

选择下山因子时可以从 \(\lambda=1\) 开始，然后依次 \(\lambda=\dfrac{1}{2}、\dfrac{1}{4}、\dfrac{1}{8}\dots\) 试算。

具体来说，就是当不满足 \(|f(x_{k+1})|<|f(x_k)|\) 时，我们称其为不满足下山条件，试算下山因子，否则我们称其满足下山条件，直接计算。

这时候我们再来计算：

显然不满足下山条件，当 \(\lambda=\dfrac{1}{32}\) 时，\(x_1=1.140625\Rightarrow f(x_1)=-0.656643\)，\(x_0=0.6\Rightarrow f(x_0)=-1.384\)。
满足 \(|f(x_{k+1})|<|f(x_k)|\)。

后面的都满足 \(\lambda=1\) 时下山，还是比较好算的。

闲话

毕竟是以普通高中生自习的方式进行的学习，有些地方没有理解透理解错了还请指出。

另外牛顿迭代法还有另一种优化方法：梯度下降法。有兴趣的可以查资料学习。