几种根号的近似计算方法：泰勒公式

序言

本文介绍了几种根号的近似估算方式。

在下文中，不妨假定我们早已得到了$\sqrtN$的一个恐怕值$S$.定义$d=N-S^2$,$f(x)=(S^2+x)^{1/2}$.则我们事实上就是在找寻$f(d)$的近似估算方式. #

接出来，我们将根据方式所根据的基本原理分类，依次介绍四种估算方式。 #

泰勒公式 #

由泰勒公式，$f(d)=f(0)+f'(0)d+f''(\xi)\dfrac{d^2}{2!}=S+\dfrac{d}{2S}-\dfrac{d^2}{8(S^2+\xi)^{3/2}}$,其中$\xi$在$0$与$d$之间。忽视余项，我们便有$\sqrt{N}\S+\dfrac{d}{2S}=\dfrac{N}{2S}+\dfrac{S}{2}$ #

这个多项式具有的意义是其实的。通过这个算式得到结果也是简单高效的。通过余项剖析，或则直接运用基本不方程，我们也容易得到，该方式获取的近似值总比确切值大。

因为对$f(x)$使用的是线性近似平方计算公式，我们得到的结果和（思路上愈加自然的）牛顿迭代法是一样的。出于对文章总体思想一致性的考虑，我并没有使用这些角度来剖析这些算法。但我会把这些角度的剖析置于末尾。 #

帕德近似

#

考虑将$f(x)$近似成两方程函数$P(x)$,$Q(x)$的商，即一有理函数$H(x)=\dfrac{P(x)}{Q(x)}$.

一种基于多项式线性递推数列的估算方式

#

令$S_{n+1}=\dfrac{S_n+N}{S_n+1}$.于是有$\lim_{n\to\infty}S_n=\sqrtN$.（原理见探讨多项式递推数列） #

一种基于连分数的估算方式 #

效率甚至低于牛顿迭代？

由平方差公式容易得到，$\sqrt{N}-S_0=\dfrac{d}{\sqrt{N}+S_0}$,于是有$\sqrt{N}=S_0+\dfrac{d}{S_0+\sqrt{N}}=S_0+\dfrac{d}{2S_0+\frac{d}{2S_0+\dots}}$当我们在一定层数截断这个连分数，并用$S_0$来近似$\sqrt{N}$,我们便有了不同精度的$\sqrt{N}$的近似。 #

前三层近似分别为$\sqrt{N}\S_0+\dfrac{d}{2S_0}=\dfrac{2S_0^2+d}{2S_0}$,$\sqrt{N}\S_0+\dfrac{d}{2S_0+\frac{d}{2S_0}}=\dfrac{4S_0^3+3S_0d}{4S_0^2+d}$,$\sqrt{N}\S_0+\dfrac{d}{2S_0+\frac{d}{2S_0+d/2S_0}}=\dfrac{8S_n^4+8S_n^2d+d^2}{8S_n^3+4Sd^2}$.经过观察，我们可以得到，记第$n$层近似所得到的最终结果的分子为$a_n$,分母为$b_n$,这么有$a_n={n-1}+da_{n-2}$,$b_n={n-1}+db_{n-2}$.于是我们又有$\begin{}a_{n+1}\\a_n\end{}=\begin{}2S_0&d\\1&0\end{}^{n}\begin{}a_1\\a_0\end{}$,$b_n$同理。

#

's #

因为是在wiki上见到的平方计算公式，也没有搜到英文资料，所以不晓得英文名叫哪些。具体来讲，我们定义$a_n=\dfrac{1}{2}(\dfrac{N}{S_n}-S_n)$,$S_{n+1}=S_n+a_n-\dfrac{a_n^2}{2(S_n+a_n)}$.因为欠缺资料，我不晓得古人是怎样得到这个多项式的。并且我们将$a_n$表示为$\dfrac{d}{2S_n}$并加以通分，会发觉这事实上即为$S_{n+1}=\dfrac{8S_n^4+8S_n^2d+d^2}{8S_n^3+4Sd^2}$,与我们连分数法中所得到的第三层近似一致。

#

各方式的比较

#

我们将假定三种应用场景，并分别对比各方式的效率。 #

第一种场景：高精度估算。我们选择估算$\sqrt{23}$到小数点后50位。由估算器得，其值约为4.. #

第二种场景：精度要求不高的多数据运算

第三种场景：精度要求不高的手算

附： #

$\sqrt{N}$即为函数$x^2-N$的零点。我们可以采用广为人知的牛顿迭代法，即切线近似法，由$S_{n+1}=S_n-\dfrac{f(S_n)}{f'(S_n)}$得到（一般是）更精确的零点值。通分以后，我们有$S_{n+1}=\dfrac{S_n+N/S_n}{2}$. #