Numerical Summation of Series

题目大意

计算级数:

$$\phi(x) = \sum_{k=1}^\infty \frac{1}{k(k+x)}\tag{1}\label{1}$$

要求计算 $x = 0, 0.1, 0.2, \dots, 299.9, 300.0$ 时 $\phi(x)$ 的值。绝对误差小于 $10^{-10}$ 。时限50ms。

题目给了提示,由于原式是平方收敛(quadratic convergence),收敛到 $10^{-10}$ 的精度需要计算相当多项, 不仅会导致超时, 而且double类型变量的计算舍入误差也会累计到不能接受的水平。 因此需要减少需要计算的项数。我们发现

$$ \begin{align} \phi(1) &= \sum_{k=1}^\infty \frac{1}{k(k+1)} \\ &= \sum_{k=1}^\infty (\frac{1}{k} - \frac{1}{k+1}) \\ &= 1 - \frac{1}{2} + \frac{1}{2} - \frac{1}{3} + \dots \\ &= 1 \end{align} $$

因此我们可以构造

$$ \begin{align} \phi(x) - \phi(1) &= \sum_{k=1}^\infty (\frac{1}{k(k+x)} - \frac{1}{k(k+x)(k+1)}) \\ &= \sum_{k=1}^\infty \frac{1-x}{k(k+x)(k+1)} \tag{2}\label{2} \\ \end{align} $$

式 $\eqref{2}$ 是一个立方收敛(cubic convergence)的级数,它的收敛速度显著快于式 $\eqref{1}$ 。 下式可以用于计算收敛到指定精度所需要计算的项数。

$$ \begin{align} \sum_{k=n}^\infty \frac{1}{k^r} \lt \int_{n-1}^{\infty} \frac{1}{x^r}dx \text{ for $k \gt 1$ and $r \ge 0$}\tag{3}\label{3} \end{align} $$

解题思路

题目类似ZOJ1007,然而时限更小,因此仅仅用提示中的构造是不够的。我们需要构造一个收敛更快的级数。

事实上不止 $\phi(1)$ ,所有整数 $x$ 都可以通过类似方法计算出精确值, 于是我们可以仿造式 $\eqref{2}$ 构造更高阶收敛的级数。如下式。

$$ \begin{align} &\frac{\phi(x) - \phi(a)}{a-x} - \frac{\phi(b) - \phi(a)}{b-a} \\ =& \sum_{k=1}^\infty (\frac{1}{k(k+a)(k+x)} - \frac{1}{k(k+a)(k+b)}) \\ =& (b-x) * \sum_{k=1}^\infty \frac{1}{k(k+a)(k+b)(k+x)} = (b-x) * M\tag{4}\label{4} \end{align} $$

于是我们可以通过计算 $M$ 并控制它的误差来得到误差范围内的 $\phi(x)$ 值。注意在式 $\eqref{4}$ 中我们避免了在 $M$ 的分子中出现 $k$ 使得 $M$ 是一个四次方收敛(quartic convergence)的级数。

通过分析 $\phi(x)$ 的误差可知,

$$ \begin{align} error = [(b-x)e(M) + e(\frac{\phi(b) - \phi(a)}{b-a})] * (a-x) + e(\phi(a)) \end{align} $$

因此虽然理论上 $a$ 和 $b$ 可以取任意 $300$ 以内的整数,然而为了避免误差被放大, 我们应该保证 $b-x$ 和 $a-x$ 小于 $1$ ,也即取 $x$ 向上和向下取整的整数。对于小于 $1$ 的 $x$ ,我们则需要考虑到最坏情况,计算额外的项数以保证精度。

其他事项

  • 考虑到是一道课程作业,代码就不放了。而且古代代码很丑。
  • 我的数值分析学得很差,文章里对构造出的各个级数的收敛速度没有讨论,这是因为我不会讨论,所以是凭感觉瞎猜的(所以可能是错的)。不过至少可以通过直觉确定构造出的级数必然比原来的级数收敛更快,这对于编程来说就够了(为懒惰开脱)。