Fotools
zh-tw

有理逼近 / 連分數展開

輸入實數

快速範例：

計算結果

輸入數字後點擊開始計算

演算法說明：

1. 連分數（Continued Fraction）：
任何實數 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. 漸近分數（Convergents）：
截取連分數的前 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, ...] (週期連分數)
  • e：[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 直線演算法等