专栏文章

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

AARIS0_0
算法·理论参与者 9已保存评论 8

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
8 条
当前快照
1 份
快照标识符
@miqezhn5
此快照首次捕获于
2025/12/04 03:43
3 个月前
此快照最后确认于
2025/12/04 03:43
3 个月前
查看原文

起源

前两天为解三次方程时套了盛金公式，然而公式内部存在立方根的求解。
抛开大常数的 STL，我们还有什么方法来求开根的精确值呢？（当然三次以上的开根就没有 STL 了。）
牛顿迭代法横空出世。

前置数学知识

求偏导法求曲线在某点处的切线。
首先我们要了解导数的定义。
导数，又称“瞬时变化率”，是描述某个变量在极短时间内变化率的名词。
所以我们可以用导数描述曲线上一点在横坐标变化极小，可忽略不计时纵坐标的变化率，也即这一点的切线斜率。
根据定义，函数 f(x)f(x) 在点 (x0,f(x0))(x_0,f(x_0)) 处的导数为 f′(x0)=lim⁡Δx→0f(Δx+x0)−f(x0)Δxf'(x_0)=\lim\limits_{\Delta x\to0}\dfrac{f(\Delta x+x_0)-f(x_0)}{\Delta x}。
再套用直线的点斜式即可得出切线方程 y=f′(x0)(x−x0)+f(x0)y=f'(x_0)(x-x_0)+f(x_0)。
这里我们要用到的是多项式函数的导数。

前置算法知识

牛顿迭代法：通过对函数进行不断求导，从而不断逼近一个方程的精确解的算法。
具体操作如下：
首先我们估计一个方程的近似解 x0x_0。
然后我们计算函数在点 (x0,f(x0))(x_0,f(x_0)) 处的切线。
套用上面的公式即得切线方程为 y=f′(x0)(x−x0)+f(x0)y=f'(x_0)(x-x_0)+f(x_0)。
计算切线与 x 轴交点的横坐标。
将 yy 赋值为 00 有 f′(x0)(x−x0)+f(x0)=0f'(x_0)(x-x_0)+f(x_0)=0，解得 x=x0f′(x0)−f(x0)f′(x0)=x0−f(x0)f′(x0)x=\dfrac{x_0f'(x_0)-f(x_0)}{f'(x_0)}=x_0-\dfrac{f(x_0)}{f'(x_0)}，我们记为 x1x_1。
接下来不断重复 xi+1=xi−f(xi)f′(xi)x_{i+1}=x_i-\dfrac{f(x_i)}{f'(x_i)} 这一步骤，即可得到 f(x)=0f(x)=0 的精确解。

实现

我们构造函数 f(x)=xm−nf(x)=x^m-n，其中 nn 为待开方数，mm 为开根的次数，则此方程的解即为 nm\sqrt[m]{n}。
那么我们就需要对 f(x)f(x) 求导。
套定义有：
f′(x)=lim⁡Δx→0(x+Δx)m−n−(xm−n)Δxf'(x)=\lim\limits_{\Delta x\to0}\dfrac{(x+\Delta x)^m-n-(x^m-n)}{\Delta x} =lim⁡Δx→0(x+Δx)m−xmΔx=\lim\limits_{\Delta x\to0}\dfrac{(x+\Delta x)^m-x^m}{\Delta x} =lim⁡Δx→0xm+mxm−1Δx+⋯−xmΔx=\lim\limits_{\Delta x\to0}\dfrac{x^m+mx^{m-1}\Delta x+\dots-x^m}{\Delta x} =lim⁡Δx→0mxm−1Δx+⋯+(Δx)mΔx=\lim\limits_{\Delta x\to0}\dfrac{mx^{m-1}\Delta x+\dots+(\Delta x)^m}{\Delta x} =lim⁡Δ→0(mxm−1+⋯+(Δx)m−1)=mxm−1=\lim\limits_{\Delta \to0}(mx^{m-1}+\dots+(\Delta x)^{m-1})=mx^{m-1}
代入牛顿迭代法公式得 xi+1=xi−xim−nmxim−1x_{i+1}=x_i-\dfrac{x_i^m-n}{mx_i^{m-1}}，多次迭代即可。
此外，牛顿迭代法还有着精度高的优点。
牛顿迭代法的收敛率是平方级别的，这意味着每次迭代后近似解的精确数位会翻倍。 ——OI WiKi
因而我们在求解高精度开根时也可以用到它。

评论

共 8 条评论，欢迎与作者交流。

正在加载评论...