Fotools
EN

Раціональні наближення / Розклад у ланцюгові дроби

Введіть дійсне десяткове число

Швидкий приклад:

)

Похибка:

Опис алгоритму:

Кількість розгорнутих членів
членів
x = a₀ + 1/(a₁ + 1/(a₂ + 1/(a₃ + ...)))
Кількість ланцюгових дробів
  • Штук
  • Час обчислення
  • Тип розкладу
  • Скінченний
  • Скорочений
    • Обчислення завершено!
    Введіть число та натисніть "Почати обчислення"
    n/qnЗгорнути
    • p-1 = 1, q-1 = 0
    • p0 = a₀, q0 = 1
    • Рекурентна формула: pn = an·pn-1 + pn-2
    • Рекурентна формула: qn = an·qn-1 + qn-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, ...] (усі одиниці, найповільніша збіжність)
    • √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)
    • Теорія музики:Консонанс інтервалів пов'язаний із простотою розкладів ланцюговими дробами
    • Астрономія:Раціональні наближення для розрахунку орбітальних періодів планет
    • Теорія чисел:Діофантові наближення та розв'язки рівняння Пелля
    • Комп'ютерна графіка:Алгоритм Брезенхема та інші