กลับไปหน้าบทความ

อ่าน 3 นาที

อัลกอริทึมของกอสเปอร์

พีชคณิตคอมพิวเตอร์/ฟังก์ชันไฮเปอร์เรขาคณิต/ใช้วันที่ dmy ตั้งแต่เดือนมกราคม 2020

ในทางคณิตศาสตร์อัลกอริทึมของกอสเปอร์ซึ่งคิดค้นโดยบิล กอสเปอร์เป็นขั้นตอนสำหรับการค้นหาผลรวมของพจน์ไฮเปอร์ จีโอเมตริก ที่เป็นพจน์ไฮเปอร์จีโอเมตริกเช่นกัน กล่าวคือ สมมติว่าเรามีa...

อัลกอริทึมของกอสเปอร์

ในทางคณิตศาสตร์อัลกอริทึมของกอสเปอร์ซึ่งคิดค้นโดยบิล กอสเปอร์เป็นขั้นตอนสำหรับการค้นหาผลรวมของพจน์ไฮเปอร์ จีโอเมตริก ที่เป็นพจน์ไฮเปอร์จีโอเมตริกเช่นกัน กล่าวคือ สมมติว่าเรามีa (1)  +  ...  + a ( n ) = S ( n ) S (0) โดยที่S ( n ) เป็นพจน์ไฮเปอร์จีโอเมตริก (เช่นS ( n + 1)/ S ( n ) เป็นฟังก์ชันตรรกยะของn ) ดังนั้นa ( n ) จึงเป็นพจน์ไฮเปอร์จีโอเมตริกเช่นกัน และเมื่อกำหนดสูตรสำหรับa ( n ) อัลกอริทึมของกอสเปอร์จะพบว่าสำหรับS ( n )     

โครงร่างของอัลกอริทึม

ขั้นตอนที่ 1: หาพหุนามpที่ทำให้เมื่อเขียนb ( n ) = a ( n )/ p ( n ) แล้วอัตราส่วนb ( n )/ b ( n - 1) จะมีรูปแบบq ( n )/ r ( n ) โดยที่qและrเป็นพหุนาม และไม่มีq ( n ) ใดที่มีตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์กับr ( n + j ) สำหรับj = 0, 1, 2, ... (ซึ่งเป็นไปได้เสมอ ไม่ว่าอนุกรมจะสามารถหาผลรวมได้ในรูปแบบปิดหรือไม่ก็ตาม)        

ขั้นตอนที่ 2: หาพหุนามƒที่ทำให้S ( n ) = q ( n  +  1)/ p ( n ) ƒ ( n ) a ( n ) ถ้าอนุกรมสามารถหาผลรวมได้ในรูปแบบปิด แสดงว่าฟังก์ชันตรรกยะƒที่มีคุณสมบัตินี้มีอยู่จริง ในความเป็นจริงมันจะต้องเป็นพหุนามเสมอ และสามารถหาขอบเขตบนของดีกรีได้ การหาค่าƒ (หรือการหาว่าไม่มีƒ ดังกล่าว ) เป็นเรื่องของการแก้ระบบสมการเชิงเส้น[ 1 ]

ความสัมพันธ์กับคู่ Wilf Zeilberger

อัลกอริทึมของ Gosper สามารถใช้เพื่อค้นหาคู่ Wilf–Zeilbergerได้ หากมีอยู่จริง สมมติว่าF ( n  +  1, k ) F ( n , k ) = G ( n , k + 1) G ( n , k ) โดยที่Fเป็นที่รู้จัก แต่Gยังไม่เป็นที่รู้จัก จากนั้นป้อนa ( k ) := F ( n + 1, k ) F ( n , k ) เข้าไปในอัลกอริทึมของ Gosper (ให้ถือว่านี่เป็นฟังก์ชันของ k ที่สัมประสิทธิ์เป็นฟังก์ชันของ n แทนที่จะเป็นตัวเลข ทุกอย่างในอัลกอริทึมทำงานได้ในบริบทนี้) หากอัลกอริทึมค้นหาS ( k ) ได้สำเร็จ โดยที่S ( k ) S ( k 1) = a ( k ) แสดงว่าเสร็จสิ้นแล้ว นั่นคือG ที่ต้องการ หากไม่เป็นเช่นนั้น ก็ไม่มีG ดัง กล่าว                     

ผลรวมแบบจำกัดกับผลรวมแบบไม่จำกัด

อัลกอริทึมของ Gosper จะค้นหา (เท่าที่เป็นไปได้) รูปแบบปิดไฮเปอร์จีโอเมตริกสำหรับ ผลรวม ไม่จำกัดของพจน์ไฮเปอร์จีโอเมตริก อาจเกิดขึ้นได้ว่าไม่มีรูปแบบปิดดังกล่าว แต่ผลรวมเหนือn ทั้งหมด หรือชุดค่าn เฉพาะบางชุด อาจมีรูปแบบปิด คำถามนี้มีความหมายเฉพาะเมื่อสัมประสิทธิ์เป็นฟังก์ชันของตัวแปรอื่น ดังนั้น สมมติว่าa ( n , k ) เป็นพจน์ไฮเปอร์จีโอเมตริกทั้งในnและkนั่นคือa ( n , k )/ a ( n - 1, k ) และa ( n , k )/ a ( n , k - 1) เป็นฟังก์ชันตรรกยะของnและkจากนั้นอัลกอริทึมของ Zeilbergerและอัลกอริทึมของ Petkovšekสามารถใช้เพื่อค้นหารูปแบบปิดสำหรับผลรวมเหนือkของa ( n , k ) ได้        

ประวัติศาสตร์

บิลล์ กอสเปอร์ ค้นพบอั ลกอริทึมนี้ในช่วงทศวรรษ 1970 ขณะทำงานเกี่ยวกับ ระบบพีชคณิตคอมพิวเตอร์ Macsymaที่SAILและMIT

หมายเหตุ

  1. เพตคอฟเชค, มาร์โก ; วิลฟ์, เฮอร์เบิร์ต ; ไซล์เบอร์เกอร์, โดรอน (1996)  =  AK Peters Ltd. ISBN 1-56881-063-6เก็บถาวรจากต้นฉบับเมื่อ 2019-07-11 เรียกดูเมื่อ2020-01-10
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Gosper%27s_algorithm&oldid=1294592117 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ อัลกอริทึมของกอสเปอร์

ในทางคณิตศาสตร์อัลกอริทึมของกอสเปอร์ซึ่งคิดค้นโดยบิล กอสเปอร์เป็นขั้นตอนสำหรับการค้นหาผลรวมของพจน์ไฮเปอร์ จีโอเมตริก ที่เป็นพจน์ไฮเปอร์จีโอเมตริกเช่นกัน กล่าวคือ สมมติว่าเรามีa...

โครงร่างของอัลกอริทึม

ขั้นตอนที่ 1: หาพหุนาม p ที่ทำให้เมื่อเขียน b ( n ) = a ( n )/ p ( n ) แล้วอัตราส่วน b ( n )/ b ( n - 1) จะมีรูปแบบ q ( n )/ r ( n ) โดยที่ q และ r เป็นพหุนาม และไม่มี q ( n ) ใดที่มีตัวประกอบที่ไม่ใช่ตัวประกอบศูนย์กับ r ( n + j ) สำหรับ j = 0, 1, 2, ...

ความสัมพันธ์กับคู่ Wilf – Zeilberger

อัลกอริทึมของ Gosper สามารถใช้เพื่อค้นหา คู่ Wilf–Zeilberger ได้ หากมีอยู่จริง สมมติว่า F ( n + 1, k ) − F ( n , k ) = G ( n , k + 1) − G ( n , k ) โดยที่ F เป็นที่รู้จัก แต่ G ยังไม่เป็นที่รู้จัก จากนั้นป้อน a ( k ) := F ( n + 1, k ) − F ( n , k )...

ผลรวมแบบจำกัดกับผลรวมแบบไม่จำกัด

อัลกอริทึมของ Gosper จะค้นหา (เท่าที่เป็นไปได้) รูปแบบปิดไฮเปอร์จีโอเมตริกสำหรับ ผลรวม ไม่จำกัด ของพจน์ไฮเปอร์จีโอเมตริก อาจเกิดขึ้นได้ว่าไม่มีรูปแบบปิดดังกล่าว แต่ผลรวมเหนือ n ทั้งหมด หรือชุดค่า n เฉพาะบางชุด อาจมีรูปแบบปิด...