Непрерывная дробь

Непрерывная дробь

Цепная дробь (или непрерывная дробь) — это математическое выражение вида

[a_0; a_1, a_2, a_3,\cdots] = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\ldots}}}\;

где a0 есть целое число и все остальные an натуральные числа (положительные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.

Содержание

Разложение в цепную дробь

Любое вещественное число x может быть представлено (конечной или бесконечной, периодической или непериодической) цепной дробью [a_0; a_1, a_2, a_3,\cdots], где

a_0 = \lfloor x \rfloor, x_0 = x - a_0,
a_1 = \left\lfloor \frac{1}{x_0} \right\rfloor, x_1 = \frac{1}{x_0} - a_1,
\dots
a_n = \left\lfloor \frac{1}{x_{n-1}} \right\rfloor, x_n = \frac{1}{x_{n-1}} - a_n,
\dots

где \lfloor x \rfloor обозначает целую часть числа x.

Для рационального числа x это разложение оборвётся по достижении нулевого x_n для некоторого n. В этом случае x представляется конечной цепной дробью x = [a_0; a_1, \cdots, a_n].

Для иррационального x все величины x_n будут ненулевыми и процесс разложения можно продолжать бесконечно. В этом случае x представляется бесконечной цепной дробью x = [a_0; a_1, a_2, a_3,\cdots].

Для рациональных чисел может быть использован алгоритм Евклида для быстрого получения разложения в цепную дробь.

Подходящие дроби

n-ой подходящей дробью для цепной дроби x=[a_0; a_1, a_2, a_3,\cdots], называется конечная цепная дробь [a_0; a_1, \cdots, a_n], значение которой равно некоторому рациональному числу \frac{p_n}{q_n}. Подходящие дроби с чётными номерами образуют возрастающую последовательность, предел которой равен x. Аналогично, подходящие дроби с нечётными номерами образуют убывающую последовательность, предел которой также равен x.

Эйлер вывел рекуррентные формулы для вычисления числителей и знаменателей подходящих дробей:

p_{-1} = 1,\quad p_0 = a_0,\quad p_n = a_n p_{n-1} + p_{n-2};
q_{-1} = 0,\quad q_0 = 1,\quad q_n = a_n q_{n-1} + q_{n-2}.

Таким образом, величины p_n и q_n представляются значениями континуант:

p_n = K_{n+1}(a_0, a_1, \cdots, a_n)
q_n = K_n(a_1, a_2, \cdots, a_n)

Последовательности \left\{p_n\right\} и \left\{q_n\right\} являются возрастающими.

Числители и знаменатели соседних подходящих дробей связаны соотношением:

p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}, ((1))

которое можно переписать в виде

\frac{p_n}{q_n} - \frac{p_{n-1}}{q_{n-1}} = \frac{(-1)^{n-1}}{q_{n-1} q_n}.

Откуда следует, что

\left|x - \frac{p_{n-1}}{q_{n-1}}\right| < \frac{1}{q_{n-1}q_n} < \frac{1}{q_{n-1}^2}.

Приближение вещественных чисел рациональными

Цепные дроби позволяют эффективно находить хорошие рациональные приближения вещественных чисел. А именно, если вещественное число x разложить в цепную дробь, то её подходящие дроби будут удовлетворять неравенству

\left|x - \frac{p_n}{q_n}\right| < \frac{1}{q_n^2}.

Отсюда, в частности, следует:

  • подходящая дробь \frac{p_n}{q_n} является наилучшим приближением для x среди всех дробей, знаменатель которых не превосходит q_n;
  • мера иррациональности любого иррационального числа не меньше 2.

Примеры

  • Разложим число \pi=3,14159265… в непрерывную дробь и подсчитаем его подходящие дроби:
    3, 22/7, 333/106, 355/113, 103993/33102, …
Вторая подходящая дробь 22/7 — это известное архимедово приближение. Четвёртая подходящая дробь 355/113 была впервые получена в Древнем Китае.
  • В теории музыки требуется отыскать рациональное приближение для \textstyle\log_2 \frac {3}{2} \approx 0{,}585. Третья подходящая дробь 7/12 позволяет обосновать классическое деление октавы на 12 полутонов[1].

Свойства и примеры

  • Любое рациональное число может быть представлено в виде конечной цепной дроби двумя способами, например:
 9/4=[2; 3, 1] = [2; 4]\;
  • Теорема Лагранжа: Число представляется в виде бесконечной периодической цепной дроби тогда и только тогда, когда оно является иррациональным решением квадратного уравнения с целыми коэффициентами.
Например:
\sqrt{2} = [1; 2, 2, 2, 2, \dots]
золотое сечение \phi = [1;1,1,1,\dots]
  • Для алгебраических чисел степени большей 2 характер разложений в непрерывную дробь неизвестен. Например, даже для \sqrt[3]{2} неизвестно, конечно ли количество различных чисел в его разложении (последовательность A002945 в OEIS).
  • Для некоторых трансцендентных чисел можно найти простую закономерность. Например, для основания натурального логарифма:
e - 1 = [1; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, \ldots, 1, 1, 2n-2, 1, 1, 2n, \ldots]
для числа
\operatorname{tg}\,1 = [1; 1, 1, 3, 1, 5, 1, 7, \ldots, 1, 2n+1, 1, 2n+3, \ldots]
  • У числа пи простой закономерности не видно:[2]
\pi = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, \dots]
  • Теорема Гаусса — Кузьмина: Почти для всех (кроме множества меры нуль) вещественных чисел существует среднее геометрическое коэффициентов соответствующих им цепных дробей, и оно равно постоянной Хинчина.
  • Теорема Маршалла Холла. Если в разложении числа x в непрерывную дробь, начиная со второго элемента не встречаются числа большие n, то говорят, что число x относится к классу F(n). Любое вещественное число может быть представленно в виде суммы двух чисел из класса F(4) и в виде произведения двух чисел из класса F(4).[3] В дальнейшем было показано, что любое вещественное число может быть представленно в виде суммы 3 чисел из класса F(3) и в виде суммы 4 чисел из класса F(2). Количество требуемых слагаемых в этой теореме не может быть уменьшено — для представления некоторых чисел указанным образом меньшего количества слагаемых недостаточно.[4][5]

Приложения цепных дробей

Теория календаря

При разработке солнечного календаря необходимо найти рациональное приближение для числа дней в году, которое равно 365,2421988… Подсчитаем подходящие дроби для дробной части этого числа:

\frac{1}{4}; \frac{7}{29}; \frac{8}{33}; \frac{31}{128}; \frac{132}{545} \cdots

Первая дробь означает, что раз в 4 года надо добавлять лишний день; этот принцип лёг в основу юлианского календаря. При этом ошибка в 1 день накапливается за 128 лет. Второе значение (7/29) никогда не использовалось. Третья дробь (8/33), то есть 8 високосных лет за период в 33 года, была предложена Омаром Хайямом в XI веке и положила начало персидскому календарю, в котором ошибка в день накапливается за 4500 лет (в григорианском — за 3280 лет). Очень точный вариант с четвёртой дробью (31/128, ошибка в сутки накапливается только за 100000 лет) пропагандировал немецкий астроном Иоганн фон Медлер (1864), однако большого интереса он не вызвал.

Решение сравнений первой степени

Рассмотрим сравнение: ax \equiv b \pmod m, где a,\ b известны, причём можно считать, что a взаимно просто с m. Надо найти x.

Разложим \frac{m}{a} в непрерывную дробь. Она будет конечной, и последняя подходящая дробь \frac{p_n}{q_n}=\frac{m}{a}. Подставим в формулу (1):

m q_{n-1} - a p_{n-1} = (-1)^{n-1}

Отсюда вытекает:

a p_{n-1} \equiv (-1)^n \pmod m,  или:  \ a (-1)^n p_{n-1} \equiv 1 \pmod m

Вывод: класс вычетов x \equiv (-1)^n p_{n-1} b \pmod m  является решением исходного сравнения.

Другие приложения

Свойства золотого сечения

Интересный результат, который следует из того, что выражение непрерывной дроби для φ не использует целых чисел, больших 1, состоит в том, что φ является одним из самых «трудных» действительных чисел для приближения с помощью рациональных чисел. Теорема Гурвица[7] утверждает, что любое действительное число k может быть приближено дробью m/n так, что

\left| k - {m \over n}\right| < {1 \over n^2 \sqrt 5}.

Хотя практически все действительные числа k имеют бесконечно много приближений m/n, которые находятся на значительно меньшем расстоянии от k, чем эта верхняя граница, приближения для φ (то есть числа 5/3, 8/5, 13/8, 21/13 и т. д.) в пределе достигают этой границы, удерживая расстояние на почти точно {\scriptstyle{1 \over n^2 \sqrt 5}} от φ, тем самым никогда не создавая столь хорошие приближения как, к примеру, 355/113 для π. Может быть показано, что любое действительное число вида (a + bφ)/(c + dφ), где a, b, c и d являются целыми числами, причём ad − bc = ±1, обладают тем же свойством, как и золотое сечение φ; а также, что все остальные действительные числа могут быть приближены намного лучше.

Историческая справка

Античные математики умели представлять отношения несоизмеримых величин в виде цепочки последовательных подходящих отношений, получая эту цепочку с помощью алгоритма Евклида. По-видимому, именно таким путём Архимед получил приближение \sqrt{3} \approx \frac {1351}{780} — это 12-я подходящая дробь для \sqrt{3} или \frac {1}{3} от 4-й подходящей дроби для \sqrt{27}.

В V веке индийский математик Ариабхата применял аналогичный «метод измельчения» для решения неопределённых уравнений первой и второй степени. С помощью этой же техники было, вероятно, получено известное приближение для числа \pi (355/113). В XVI веке Рафаэль Бомбелли извлекал с помощью цепных дробей квадратные корни (см. его алгоритм).

Начало современной теории цепных дробей положил в 1613 году Пьетро Антонио Катальди. Он отметил основное их свойство (положение между подходящими дробями) и ввёл обозначение, напоминающее современное. Позднее его теорию расширил Джон Валлис, который и предложил термин «непрерывная дробь». Эквивалентный термин «цепная дробь» появился в конце XVIII века.

Применялись эти дроби в первую очередь для рационального приближения вещественных чисел; например, Христиан Гюйгенс использовал их для проектирования зубчатых колёс своего планетария. Гюйгенс уже знал, что подходящие дроби всегда несократимы и что они представляют наилучшее рациональное приближение.

В XVIII веке теорию цепных дробей в общих чертах завершили Леонард Эйлер и Жозеф Луи Лагранж.

См. также

Ссылки

Примечания

  1. ↑ Шилов Г. Е. Простая гамма. Устройство музыкальной шкалы. — Популярные лекции по математике. — М.: Физматгиз, 1963. — 20 с.
  2. ↑ последовательность A001203 в OEIS
  3. ↑ M. Hall, On the sum and product of continued fractions, Annals of Math. 48 (1947) 966—993.
  4. ↑ B. Diviš, On sums of continued fractions, Acta Arith. 22 (1973) 157—173.
  5. ↑ T. W. Cusick and R. A. Lee, Sums of sets of continued fractions, Proc. Amer. Math. Soc. 30 (1971) 241-46.
  6. ↑ Бугаенко В. О. Уравнения Пелля, М.:МЦНМО, 2001. ISBN 5-900916-96-0.
  7. ↑ Hardy G. H. Theorem 193 // An Introduction to the Theory of Numbers. — Fifth. — Oxford, 1979.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Полезное


Смотреть что такое "Непрерывная дробь" в других словарях:

  • НЕПРЕРЫВНАЯ ДРОБЬ — (цепная дробь) один из важнейших способов изображения чисел. К непрерывной дроби, изображающей некоторое (нецелое) число ?, приходят, записывая это число в виде: ,где a0 целое число и 0 ? 1/?1 1; далее, записывая ?1 в таком же виде: и продолжая… …   Большой Энциклопедический словарь

  • непрерывная дробь — (цепная дробь), один из важнейших способов изображения чисел. К непрерывной дроби, изображающей некоторое (нецелое) число α, приходят, записывая это число в виде: , где a0  целое число и ; далее, записывая α1 в таком же виде: и продолжая этот… …   Энциклопедический словарь

  • НЕПРЕРЫВНАЯ ДРОБЬ — (цепная дробь), один из важнейших способов изображения чисел. К Н.д., изображающей нек рое (нецелое) число а, приходят, записывая это число в виде: где а0 целое число и 0=< 1/а1<1 далее, записывая а1 в таком же виде: и продолжая этот… …   Естествознание. Энциклопедический словарь

  • Непрерывная дробь —         цепная дробь, один из важнейших способов представления чисел и функций. Н. д. есть выражение вида                  где a0 любое целое число, a1, a2,..., an,... натуральные числа, называемые неполными частными, или элементами, данной Н. д …   Большая советская энциклопедия

  • НЕПРЕРЫВНАЯ ДРОБЬ — то же, что цепная дробь, т. е. выражение вида конечные или бесконечные последовательности комплексных чисел. Для Н. д. употребляется обозначение Обычно предполагается, что последовательности и таковы, что для всех n, 0=<n=<w+1 (Qn… …   Математическая энциклопедия

  • Непрерывная дробь — см. Дроби …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • ДРОБЬ — ДРОБЬ, дроби, жен. 1. только ед., собир. Мелкие свинцовые шарики (употр. для стрельбы из охотничьего ружья). В утку попал весь заряд дроби. 2. Число, состоящее из частей единицы (мат.). Правильная дробь (меньше единицы). Неправильная дробь… …   Толковый словарь Ушакова

  • Дробь (в арифметике) — Дробь в арифметике, число, составленное из целого числа долей единицы. Д. изображается символом где m ‒ числитель Д. ‒ показывает число взятых долей единицы, разделённой на столько долей, сколько показывает (знаменует) знаменатель n. Д. можно… …   Большая советская энциклопедия

  • Дробь — I         в арифметике, число, составленное из целого числа долей единицы. Д. изображается символом                  где m числитель Д. показывает число взятых долей единицы, разделённой на столько долей, сколько показывает (знаменует)… …   Большая советская энциклопедия

  • Дробь — В Викисловаре есть статья «дробь» Наименование символа «⁄» (другое, распространённое по большей части в английском языке, название символа  солидус (англ.), или слэш), например, в номерах домов. Так номер дома «5/17» читается «пять… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»