应用牛顿迭代法快速求精度较高的开根
RAY091016
·
·
算法·理论
起源
前两天为解三次方程时套了盛金公式,然而公式内部存在立方根的求解。
抛开大常数的 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
因而我们在求解高精度开根时也可以用到它。