应用牛顿迭代法快速求精度较高的开根

· · 算法·理论

起源

前两天为解三次方程时套了盛金公式，然而公式内部存在立方根的求解。

抛开大常数的 STL，我们还有什么方法来求开根的精确值呢？（当然三次以上的开根就没有 STL 了。）

牛顿迭代法横空出世。

前置数学知识

求偏导法求曲线在某点处的切线。

首先我们要了解导数的定义。

导数，又称“瞬时变化率”，是描述某个变量在极短时间内变化率的名词。

所以我们可以用导数描述曲线上一点在横坐标变化极小，可忽略不计时纵坐标的变化率，也即这一点的切线斜率。

根据定义，函数 f(x) 在点 (x_0,f(x_0)) 处的导数为 f'(x_0)=\lim\limits_{\Delta x\to0}\dfrac{f(\Delta x+x_0)-f(x_0)}{\Delta x}。

再套用直线的点斜式即可得出切线方程 y=f'(x_0)(x-x_0)+f(x_0)。

这里我们要用到的是多项式函数的导数。

前置算法知识

牛顿迭代法：通过对函数进行不断求导，从而不断逼近一个方程的精确解的算法。

具体操作如下：

首先我们估计一个方程的近似解 x_0。

然后我们计算函数在点 (x_0,f(x_0)) 处的切线。

套用上面的公式即得切线方程为 y=f'(x_0)(x-x_0)+f(x_0)。

计算切线与 x 轴交点的横坐标。

将 y 赋值为 0 有 f'(x_0)(x-x_0)+f(x_0)=0，解得 x=\dfrac{x_0f'(x_0)-f(x_0)}{f'(x_0)}=x_0-\dfrac{f(x_0)}{f'(x_0)}，我们记为 x_1。

接下来不断重复 x_{i+1}=x_i-\dfrac{f(x_i)}{f'(x_i)} 这一步骤，即可得到 f(x)=0 的精确解。

实现

我们构造函数 f(x)=x^m-n，其中 n 为待开方数，m 为开根的次数，则此方程的解即为 \sqrt[m]{n}。

那么我们就需要对 f(x) 求导。

套定义有：

f'(x)=\lim\limits_{\Delta x\to0}\dfrac{(x+\Delta x)^m-n-(x^m-n)}{\Delta x} =\lim\limits_{\Delta x\to0}\dfrac{(x+\Delta x)^m-x^m}{\Delta x} =\lim\limits_{\Delta x\to0}\dfrac{x^m+mx^{m-1}\Delta x+\dots-x^m}{\Delta x} =\lim\limits_{\Delta x\to0}\dfrac{mx^{m-1}\Delta x+\dots+(\Delta x)^m}{\Delta x} =\lim\limits_{\Delta \to0}(mx^{m-1}+\dots+(\Delta x)^{m-1})=mx^{m-1}

代入牛顿迭代法公式得 x_{i+1}=x_i-\dfrac{x_i^m-n}{mx_i^{m-1}}，多次迭代即可。

此外，牛顿迭代法还有着精度高的优点。

牛顿迭代法的收敛率是平方级别的，这意味着每次迭代后近似解的精确数位会翻倍。 ——OI WiKi

因而我们在求解高精度开根时也可以用到它。