主题
Search

Gosper 算法

一种用于寻找闭合形式超几何恒等式的算法。该算法处理项的比率为有理函数的和式。它不仅能最终确定是否存在超几何序列 z_n 使得

t_n=z_(n+1)-z_n,
(1)

而且如果存在，实际上会生成 z_n。如果不存在，则生成 sum_(k=0)^(n-1)t_k。算法概要如下（Petkovšek 等人，1996 年）

1. 对于比率 r(n)=t_(n+1)/t_n，它是 n 的有理函数。

2. 写作

r(n)=(a(n))/(b(n))(c(n+1))/(c(n)),
(2)

其中 a(n)、b(n) 和 c(n) 是满足以下条件的多项式

GCD(a(n),b(n+h))=1
(3)

对于所有非负整数 h。

3. 找到一个非零多项式解 x(n)，使得

a(n)x(n+1)-b(n-1)x(n)=c(n),
(4)

如果存在。

4. 返回 b(n-1)x(n)/c(n)t_n 并停止。

Petkovšek 等人（1996 年）将该算法描述为“闭合形式求和问题计算机化历史上的里程碑之一”。Gosper 算法对于 Zeilberger 算法和 Wilf-Zeilberger 对的机制的运行至关重要。

另请参阅

超几何恒等式, Sister Celine 方法, Wilf-Zeilberger 对, Zeilberger 算法

使用 Wolfram|Alpha 探索

参考文献

Gessel, I. and Stanton, D. "超几何级数的奇特求值。" SIAM J. Math. Anal. 13, 295-308, 1982.Gosper, R. W. "不定超几何求和的决策程序。" Proc. Nat. Acad. Sci. USA 75, 40-42, 1978.Graham, R. L.; Knuth, D. E.; and Patashnik, O. 具体数学：计算机科学基础，第二版。 Reading, MA: Addison-Wesley, 1994.Koepf, W. "m 重超几何求和算法。" J. Symb. Comput. 20, 399-417, 1995.Koepf, W. "Gosper 算法。" 《超几何求和：求和与特殊函数恒等式的算法方法》第 5 章，超几何求和：求和与特殊函数恒等式的算法方法。 Braunschweig, Germany: Vieweg, pp. 61-79, 1998.Lafron, J. C. "有限项求和。" 《计算机代数符号与代数计算》，第二版，计算机代数符号与代数计算，第二版。 (Ed. B. Buchberger, G. E. Collins, and R. Loos). New York: Springer-Verlag, 1983.Paule, P. and Schorn, M. "用于证明二项式系数恒等式的 Zeilberger 算法的 Mathematica 版本。" J. Symb. Comput. 20, 673-698, 1995.Petkovšek, M.; Wilf, H. S.; and Zeilberger, D. "Gosper 算法。" 《A=B》第 5 章，A=B。 Wellesley, MA: A K Peters, pp. 73-99, 1996. http://www.cis.upenn.edu/~wilf/AeqB.html.Pirastu, R. and Strehl, V. "有理求和与 Gosper-Petkovšek 表示。" J. Symb. Comput. 20, 617-635, 1995.Zeilberger, D. "创造性伸缩法。" J. Symb. Comput. 11, 195-204, 1991.

在 Wolfram|Alpha 中被引用

Gosper 算法

请引用为

Weisstein, Eric W. "Gosper 算法。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GospersAlgorithm.html

主题分类