主題
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 演算法

使用 探索

參考文獻

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.

在 中被引用

Gosper 演算法

請引用為

Weisstein, Eric W. "Gosper 演算法。" 來自 Web 資源。 https://mathworld.tw/GospersAlgorithm.html

主題分類