函数求值

                     

贡献者: 待更新

   函数求值归根结底,就是找到一个解析公式,用加减乘除表示一个函数。如果算法没有用到近似,有限精度和任意精度都是一样的,只是每个数占的内存不同罢了。任意精度的加减乘除和开根号参考 Numerical Recipes 最后一节。

   最常见的展开有三种,分别是泰勒展开,渐进展开,以及连续分数。这些展开在 functions.wolfram.com 都可以找到。

   接下来是如何计算级数或连续分数。求级数的方法一般是用

\begin{equation} f_N(x) = \sum_{n = 0}^N c_n x^n = (\dots ((c_n x + c_{n-1})x + c_{n-2} \dots )x + c_0~. \end{equation}
这么做误差和直接对多项式求和一样,但计算量却少了很多。将上式中的 $x$ 换成 $1/x$ 就是渐进展开的形式。注意我们可以在计算开始前估计误差,根据精度要求得到我们需要的项数。

   显然,$ \left\lvert x \right\rvert $ 越小时泰勒展开收敛得越快,而 $ \left\lvert x \right\rvert $ 越大时渐进展开收敛得越快。

   再来看连续分数

\begin{equation} f_N(x) = b_0 + \dfrac{a_1}{b_1 + \dfrac{a_2}{b_2 + \dots \dfrac{a_N}{b_N}}}~, \end{equation}
也可以表示为
\begin{equation} f_N(x) = b_0 + \frac{a_1}{b_1 +} \frac{a_2}{b_2 +} \frac{a_3}{b_3 +} \dots \frac{a_N}{b_N}~, \end{equation}
其中 $a_n$ 和 $b_n$ 都可以是 $x$ 的函数。

   乍看之下连续分数只能从右往左求,其实不然。由递归法可以证明

\begin{equation} f_n = \frac{A_n}{B_n}~. \end{equation}
其中
\begin{equation} A_n = b_n A_{n-1} + a_n A_{n-2} ~,\qquad B_n = b_n B_{n-1} + a_n B_{n-2}~. \end{equation}
\begin{equation} A_{-1} = 1 ~,\qquad B_{-1} = 0~, \qquad A_0 = b_0 ~,\qquad B_0 = 1~. \end{equation}
还有一种 Steed's 方法,详见 Numerical Recipes。正向求和的好处是可以判断什么时候开始收敛。 据说特定情况下连续分数收敛较快,但具体什么时候用还有待考察。

   另外两种不明觉厉的算法分别是切比雪夫多项式(Chebyshev Polynomial)算数几何平均(Agorithmic-Geometric Mean, AGM,后者也通常被用于计算高精度的 $\pi$,且有二次收敛。


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利