题目

Problem 235: An Arithmetic Geometric sequence

Given is the arithmetic-geometric sequence u(k) = (900-3k)rk-1.
Let s(n) = Σk=1...nu(k).

Find the value of r for which s(5000) = -600,000,000,000.

Give your answer rounded to 12 places behind the decimal point.

分析

根据题目,我们有:

F

当 r = 1 时,F ,不符合题目要求。

当 r ≠ 1 时,F

前一项使用了等比数列的求和公式,后一项请参见《具体数学:计算机科学基础(第2版)》第 28 页。

根据题目,我们有:

F

上式进行移项并乘以 F 就得到:

F

经整理后得到以下一元 5001 次方程:

F

经过简单的计算,得知这个方程的一个实根是 1,另一个实根比 1 稍大。我们的目的就是求出这个实根。

P

解答

根据以上分析,我们有以下 Haskell 程序:

import Text.Printf ( printf )

main = let eps = 1e-12 :: Double in printf "%.12f\n" $ fst $ until
  (\(a,b) -> b-a < eps/2) (\(a,b) -> let x = (a+b)/2 in if f x < 0
  then (x,b) else (a,x)) (1, 2) where
  f r = 4700*r**5001-4701*r**5000-2e11*r*r+(4e11+300)*r-2e11-299

简要说明:

  • 最后一行就是我们前面推导出来的 5001 次整系数多项式。
  • 然后简单地使用二分法在区间 (1,2) 内求根。

这个程序的运行时间是 0.002 秒。

进阶

根据代数基本定理,一元 n 次方程正好有 n 个复数根。而我们这道题目中涉及到的实系数一元 5001 次方程有多少个实数根?此外,这个 5001 次整系数多项式的函数图像整体上是怎样的呢?

注意,实系数多项式函数的定义域是全体实数,最高项的次数为奇数时,值域也是全体实数。而且多项式函数处处有导数,也就是说它的图像是光滑的,上图中两个看上去不光滑的点,局部放大后必然是光滑的。其中右边那个局部放大后如下图所示。

从上图可以看出,这个一元 5001 次方程有三个实数根,分别是:r1 = r2 = 1,r3 = 1.002322108... 。

参考资料

  1. 图灵社区:图书:具体数学:计算机科学基础(第2版)
  2. Wikipedia: Geometric progression
  3. Wikipedia: Arithmetico-geometric sequence
  4. Wikipedia: Fundamental theorem of algebra