1. เศษส่วนต่อ:
จำนวนจริง x ใดๆ สามารถแสดงเป็นเศษส่วนต่อเนื่องได้:
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
ย่อว่า: x = [a₀; a₁, a₂, a₃, ...]
- a₀ = ⌊x⌋ (ส่วนจำนวนเต็มของ x)
- ถ้า x ไม่ใช่จำนวนเต็ม ให้ x₁ = 1/(x - a₀) และต่อด้วย a₁ = ⌊x₁⌋
- ทำซ้ำขั้นตอนนี้เพื่อรับ a₂, a₃, ...
- การขยายเศษส่วนอย่างต่อเนื่องของจำนวนตรรกยะนั้นมีขอบเขตจำกัด
- การขยายเศษส่วนอย่างต่อเนื่องของจำนวนอตรรกยะนั้นไม่มีที่สิ้นสุด
2. คอนเวอร์เจนท์:
เศษส่วนที่ได้จากการสกัดกั้นเทอม n แรกของเศษส่วนต่อเนื่องเรียกว่าเศษส่วนเชิงเส้นกำกับลำดับที่ n ซึ่งบันทึกเป็น pn/qn:
- p-1 = 1, q-1 = 0
- p0 = a₀, q0 = 1
- สูตรการเรียกซ้ำ: pn = an·p(n-1) + p(n-2)
- สูตรการเรียกซ้ำ: qn = an·q(n-1) + q(n-2)
- เศษส่วนเชิงเส้นกำกับคือการประมาณเหตุผลที่ดีที่สุดของจำนวนเดิม
3. การประมาณเหตุผลที่ดีที่สุด:
- สำหรับจำนวนจริง x และขอบเขตบนของตัวส่วน Q ให้หาเศษส่วน p/q (q ≤ Q) โดยที่ |x - p/q| ย่อเล็กสุด
- เศษส่วนเชิงเส้นกำกับของเศษส่วนต่อเนื่องจะให้การประมาณเหตุผลที่ดีที่สุด
- ถ้า p/q เป็นเศษส่วนเชิงเส้นกำกับของ x ดังนั้นสำหรับทุก q' < q, |x - p/q| < |x - p'/q'|
4. เศษส่วนต่อของจำนวนพิเศษ:
- อัตราส่วนทองคำ φ:[1; 1, 1, 1, 1, ...] (ทั้งหมด 1 การบรรจบกันที่ช้าที่สุด)
- √2:[1; 2, 2, 2, 2, ...] (เศษส่วนต่อเนื่องเป็นระยะ)
- อี:[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ...] (เป็นประจำ)
- π:[3; 7, 15, 1, 292, 1, ...] (ไม่มีรูปแบบที่ชัดเจน)
ความซับซ้อนของอัลกอริทึม:
- ความซับซ้อนของเวลา:O(n)，โดยที่ n คือจำนวนเทอมที่จะขยาย
- ความซับซ้อนของพื้นที่:O(n)，ต้องเก็บค่าสัมประสิทธิ์และเศษส่วนเชิงเส้นกำกับทั้งหมด
- เสถียรภาพเชิงตัวเลข:ใช้ตัวเลขทศนิยมที่มีความแม่นยำสูงหรือจำนวนเต็มขนาดใหญ่เพื่อหลีกเลี่ยงการสูญเสียความแม่นยำ
สถานการณ์การใช้งาน:
- การคำนวณเชิงตัวเลข:ใช้เศษส่วนอย่างง่ายเพื่อประมาณจำนวนอตรรกยะเชิงซ้อน (เช่น π µ 22/7, 355/113)
- ทฤษฎีดนตรี:ความกลมกลืนของช่วงสัมพันธ์กับความเรียบง่ายของการขยายเศษส่วนอย่างต่อเนื่อง
- ดาราศาสตร์:การประมาณเหตุผลเพื่อคำนวณคาบการเคลื่อนที่ของดาวเคราะห์
- ทฤษฎีจำนวน:การประมาณไดโอแฟนไทน์ การแก้สมการเพลล์
- คอมพิวเตอร์กราฟิก:อัลกอริธึมเส้นตรงของ Bresenham ฯลฯ