Главная » Реферат » Непрерывные дроби реферат

Непрерывная дробь. Непрерывные дроби реферат


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

скачать

Реферат на тему:

План:

Введение

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

[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 натуральные числа (то есть неотрицательные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.

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

Любое вещественное число 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 это разложение оборвётся по достижении нулевого xn для некоторого n. В этом случае x представляется конечной цепной дробью x = [a_0; a_1, \cdots, a_n].

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

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

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

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}.

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

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\} являются возрастающими.

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

pnqn - 1 - qnpn - 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}.

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

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

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

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

3.1. Примеры

Вторая дробь (22/7) — это известное архимедово приближение. Четвёртая (355/113) была впервые получена в Древнем Китае.

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

9/4=[2; 3, 1] = [2; 4]\; Например: \sqrt{2} = [1; 2, 2, 2, 2, \dots] золотое сечение \phi = [1;1,1,1,\dots] e − 1 = [1;1;2;1;1;4;1;1;6;1;1;8;...;1;1;2n − 2;1;1;2n;...]

для числа

\operatorname{tg}\,1 = [1; 1; 1; 3; 1; 5; 1; 7; ...; 1; 2n+1; 1; 2n+3; ...] π = [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,…]

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

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

При разработке солнечного календаря необходимо найти рациональное приближение для числа дней в году, которое равно 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), однако большого интереса он не вызвал.

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

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

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

mqn − 1 − apn − 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  является решением исходного сравнения.

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

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

Интересный результат, которые следует из того факта, что выражение непрерывной дроби для φ не использует целых чисел больше чем 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 – имеют такое же свойство как и золотое сечение φ; а также, что все остальные действительные числа могут быть приближены намного лучше.

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

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

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

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

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

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

7. Мотивация

Непрерывные дроби являются самыми "математически естественными" представлениями вещественных чисел.

Большинство людей знакомы с десятичным представлением вещественных чисел, которое может быть определено как

r = \sum_{i=0}^\infty a_i 10^{-i},

где a0 может быть любым целым числом, а последующие ai являются одним из элементом {0,1,2,…,9}. В этом представление, число π, к примеру, может быть представлено как последовательность целых чисел (a_i) = (3,1,4,1,5,9,2,\ldots).

Это десятичное представление имеет несколько проблем. Одна из них, многие рациональные числа не имеет конечного представления в этой системе. Например, число 1/3 представимо бесконечной последовательностью (0,3,3,3,3,…). Другая проблема заключается в том, что константа 10 является по сути произвольным выбором, который оказывает предпочтение числам, которые как-либо относятся к целому числу 10. Например, 137/1600 имеет конечное десятичное представление, тогда как 1/3 не имеет, не потому, что 137/1600 проще чем 1/3, а всего лишь потому, что 1600 делит степень 10 (106 = 1600 × 625). Запись как цепная дробь является представлением вещественных чисел, которая не имеет этих проблем.

Давайте рассмотрим как мы можем описать число, такое как 415/93, которое примерно равняется 4,4624. Это примерно 4.Вообще-то это чуть больше чем 4, около 4 + 1/2. Но 2 в знаменателе не совсем точно; там должно быть число чуть больше чем 2, примерно 2 + 1/6. Таким образом, 415/93 примерно равняется 4 + 1/(2 + 1/6). Но 6 в знаменателе не верно; настоящее значение чуть больше 6, 6+1/7. Таким образом, 415/93 является 4+1/(2+1/(6+1/7). Это точное значение.

Опуская некоторые обязательные части в выражении 4 + 1 / (2 + 1 / (6 + 1 / 7)) мы получим краткую нотацию [4;2,6,7]. (Заметьте, что общепринято заменять только первую запятую точкой с запятой).

Представление как непрерывная дробь вещественного числа может быть определена таким образом. Она имеет несколько желательных свойств:

{a+b\sqrt{c} \over d}

для целых a, b, c, d; где b и d не ноль и c>1 и c не является точным квадратом.

К примеру, периодическая непрерывная дробь [1; 1, 1, 1, …] является золотым сечением, а периодическая непрерывная дробь [1; 2, 2, 2, …] является квадратным корнем из 2.

Последнее свойство чрезвычайно важно. У десятичного представления числа его нет. Усечение десятичного представления числа приводит к рациональному приближению числа, но обычно к не очень хорошему приближению. К примеру, усечение 1/7 = 0.142857… в разных местах приводит к приближениям таким как 142/1000, 14/100 и 1/10. Но очевидно лучшим рациональным приближением будет само число "1/7". Обрывая десятичное представление π мы получаем приближения такие как 31415/10000 и 314/100. Цепная дробь π начинается [3; 7, 15, 1, 292, …]. Усекая это представление мы получаем отличные рациональные приближение 3, 22/7, 333/106, 355/113, 103993/33102, …. Знаменатели 314/100 и 333/106 почти одинаковые, но ошибка в приближении 314/100 в девятнадцать раз больше ошибки, чем в приближении 333/106. Как приближении π, [3; 7, 15, 1] более чем в сто раз точнее приближения 3,1416.

wreferat.baza-referat.ru

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

скачать

Реферат на тему:

План:

Введение

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

[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 натуральные числа (то есть неотрицательные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.

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

Любое вещественное число 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 это разложение оборвётся по достижении нулевого xn для некоторого n. В этом случае x представляется конечной цепной дробью x = [a_0; a_1, \cdots, a_n].

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

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

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

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}.

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

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\} являются возрастающими.

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

pnqn - 1 - qnpn - 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}.

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

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

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

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

3.1. Примеры

Вторая дробь (22/7) — это известное архимедово приближение. Четвёртая (355/113) была впервые получена в Древнем Китае.

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

9/4=[2; 3, 1] = [2; 4]\; Например: \sqrt{2} = [1; 2, 2, 2, 2, \dots] золотое сечение \phi = [1;1,1,1,\dots] e − 1 = [1;1;2;1;1;4;1;1;6;1;1;8;...;1;1;2n − 2;1;1;2n;...]

для числа

\operatorname{tg}\,1 = [1; 1; 1; 3; 1; 5; 1; 7; ...; 1; 2n+1; 1; 2n+3; ...] π = [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,…]

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

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

При разработке солнечного календаря необходимо найти рациональное приближение для числа дней в году, которое равно 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), однако большого интереса он не вызвал.

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

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

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

mqn − 1 − apn − 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  является решением исходного сравнения.

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

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

Интересный результат, которые следует из того факта, что выражение непрерывной дроби для φ не использует целых чисел больше чем 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 – имеют такое же свойство как и золотое сечение φ; а также, что все остальные действительные числа могут быть приближены намного лучше.

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

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

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

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

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

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

7. Мотивация

Непрерывные дроби являются самыми "математически естественными" представлениями вещественных чисел.

Большинство людей знакомы с десятичным представлением вещественных чисел, которое может быть определено как

r = \sum_{i=0}^\infty a_i 10^{-i},

где a0 может быть любым целым числом, а последующие ai являются одним из элементом {0,1,2,…,9}. В этом представление, число π, к примеру, может быть представлено как последовательность целых чисел (a_i) = (3,1,4,1,5,9,2,\ldots).

Это десятичное представление имеет несколько проблем. Одна из них, многие рациональные числа не имеет конечного представления в этой системе. Например, число 1/3 представимо бесконечной последовательностью (0,3,3,3,3,…). Другая проблема заключается в том, что константа 10 является по сути произвольным выбором, который оказывает предпочтение числам, которые как-либо относятся к целому числу 10. Например, 137/1600 имеет конечное десятичное представление, тогда как 1/3 не имеет, не потому, что 137/1600 проще чем 1/3, а всего лишь потому, что 1600 делит степень 10 (106 = 1600 × 625). Запись как цепная дробь является представлением вещественных чисел, которая не имеет этих проблем.

Давайте рассмотрим как мы можем описать число, такое как 415/93, которое примерно равняется 4,4624. Это примерно 4.Вообще-то это чуть больше чем 4, около 4 + 1/2. Но 2 в знаменателе не совсем точно; там должно быть число чуть больше чем 2, примерно 2 + 1/6. Таким образом, 415/93 примерно равняется 4 + 1/(2 + 1/6). Но 6 в знаменателе не верно; настоящее значение чуть больше 6, 6+1/7. Таким образом, 415/93 является 4+1/(2+1/(6+1/7). Это точное значение.

Опуская некоторые обязательные части в выражении 4 + 1 / (2 + 1 / (6 + 1 / 7)) мы получим краткую нотацию [4;2,6,7]. (Заметьте, что общепринято заменять только первую запятую точкой с запятой).

Представление как непрерывная дробь вещественного числа может быть определена таким образом. Она имеет несколько желательных свойств:

{a+b\sqrt{c} \over d}

для целых a, b, c, d; где b и d не ноль и c>1 и c не является точным квадратом.

К примеру, периодическая непрерывная дробь [1; 1, 1, 1, …] является золотым сечением, а периодическая непрерывная дробь [1; 2, 2, 2, …] является квадратным корнем из 2.

Последнее свойство чрезвычайно важно. У десятичного представления числа его нет. Усечение десятичного представления числа приводит к рациональному приближению числа, но обычно к не очень хорошему приближению. К примеру, усечение 1/7 = 0.142857… в разных местах приводит к приближениям таким как 142/1000, 14/100 и 1/10. Но очевидно лучшим рациональным приближением будет само число "1/7". Обрывая десятичное представление π мы получаем приближения такие как 31415/10000 и 314/100. Цепная дробь π начинается [3; 7, 15, 1, 292, …]. Усекая это представление мы получаем отличные рациональные приближение 3, 22/7, 333/106, 355/113, 103993/33102, …. Знаменатели 314/100 и 333/106 почти одинаковые, но ошибка в приближении 314/100 в девятнадцать раз больше ошибки, чем в приближении 333/106. Как приближении π, [3; 7, 15, 1] более чем в сто раз точнее приближения 3,1416.

www.wreferat.baza-referat.ru

Реферат Цепные дроби

скачать

Реферат на тему:

План:

Введение

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

[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 натуральные числа (то есть неотрицательные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.

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

Любое вещественное число 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 это разложение оборвётся по достижении нулевого xn для некоторого n. В этом случае x представляется конечной цепной дробью x = [a_0; a_1, \cdots, a_n].

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

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

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

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}.

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

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\} являются возрастающими.

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

pnqn - 1 - qnpn - 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}.

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

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

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

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

3.1. Примеры

Вторая дробь (22/7) — это известное архимедово приближение. Четвёртая (355/113) была впервые получена в Древнем Китае.

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

9/4=[2; 3, 1] = [2; 4]\; Например: \sqrt{2} = [1; 2, 2, 2, 2, \dots] золотое сечение \phi = [1;1,1,1,\dots] e − 1 = [1;1;2;1;1;4;1;1;6;1;1;8;...;1;1;2n − 2;1;1;2n;...]

для числа

\operatorname{tg}\,1 = [1; 1; 1; 3; 1; 5; 1; 7; ...; 1; 2n+1; 1; 2n+3; ...] π = [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,…]

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

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

При разработке солнечного календаря необходимо найти рациональное приближение для числа дней в году, которое равно 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), однако большого интереса он не вызвал.

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

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

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

mqn − 1 − apn − 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  является решением исходного сравнения.

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

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

Интересный результат, которые следует из того факта, что выражение непрерывной дроби для φ не использует целых чисел больше чем 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 – имеют такое же свойство как и золотое сечение φ; а также, что все остальные действительные числа могут быть приближены намного лучше.

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

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

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

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

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

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

7. Мотивация

Непрерывные дроби являются самыми "математически естественными" представлениями вещественных чисел.

Большинство людей знакомы с десятичным представлением вещественных чисел, которое может быть определено как

r = \sum_{i=0}^\infty a_i 10^{-i},

где a0 может быть любым целым числом, а последующие ai являются одним из элементом {0,1,2,…,9}. В этом представление, число π, к примеру, может быть представлено как последовательность целых чисел (a_i) = (3,1,4,1,5,9,2,\ldots).

Это десятичное представление имеет несколько проблем. Одна из них, многие рациональные числа не имеет конечного представления в этой системе. Например, число 1/3 представимо бесконечной последовательностью (0,3,3,3,3,…). Другая проблема заключается в том, что константа 10 является по сути произвольным выбором, который оказывает предпочтение числам, которые как-либо относятся к целому числу 10. Например, 137/1600 имеет конечное десятичное представление, тогда как 1/3 не имеет, не потому, что 137/1600 проще чем 1/3, а всего лишь потому, что 1600 делит степень 10 (106 = 1600 × 625). Запись как цепная дробь является представлением вещественных чисел, которая не имеет этих проблем.

Давайте рассмотрим как мы можем описать число, такое как 415/93, которое примерно равняется 4,4624. Это примерно 4.Вообще-то это чуть больше чем 4, около 4 + 1/2. Но 2 в знаменателе не совсем точно; там должно быть число чуть больше чем 2, примерно 2 + 1/6. Таким образом, 415/93 примерно равняется 4 + 1/(2 + 1/6). Но 6 в знаменателе не верно; настоящее значение чуть больше 6, 6+1/7. Таким образом, 415/93 является 4+1/(2+1/(6+1/7). Это точное значение.

Опуская некоторые обязательные части в выражении 4 + 1 / (2 + 1 / (6 + 1 / 7)) мы получим краткую нотацию [4;2,6,7]. (Заметьте, что общепринято заменять только первую запятую точкой с запятой).

Представление как непрерывная дробь вещественного числа может быть определена таким образом. Она имеет несколько желательных свойств:

{a+b\sqrt{c} \over d}

для целых a, b, c, d; где b и d не ноль и c>1 и c не является точным квадратом.

К примеру, периодическая непрерывная дробь [1; 1, 1, 1, …] является золотым сечением, а периодическая непрерывная дробь [1; 2, 2, 2, …] является квадратным корнем из 2.

Последнее свойство чрезвычайно важно. У десятичного представления числа его нет. Усечение десятичного представления числа приводит к рациональному приближению числа, но обычно к не очень хорошему приближению. К примеру, усечение 1/7 = 0.142857… в разных местах приводит к приближениям таким как 142/1000, 14/100 и 1/10. Но очевидно лучшим рациональным приближением будет само число "1/7". Обрывая десятичное представление π мы получаем приближения такие как 31415/10000 и 314/100. Цепная дробь π начинается [3; 7, 15, 1, 292, …]. Усекая это представление мы получаем отличные рациональные приближение 3, 22/7, 333/106, 355/113, 103993/33102, …. Знаменатели 314/100 и 333/106 почти одинаковые, но ошибка в приближении 314/100 в девятнадцать раз больше ошибки, чем в приближении 333/106. Как приближении π, [3; 7, 15, 1] более чем в сто раз точнее приближения 3,1416.

wreferat.baza-referat.ru

Непрерывные дроби | Математика, которая мне нравится

Исторически непрерывные, или цепные дроби появились в связи с необходимости найти наилучшее приближение вещественного числа с помощью числа рационального. Так, при конструировании зубчатых передач для передачи вращения с одного колеса на другое требуется нарезать на одном из них q зубцов, а на другом — p, так чтобы отношение \frac{p}{q} как можно лучше приближало заранее заданное отношение угловых скоростей \omega. При этом ясно, что чем меньше зубцов нужно будет нарезать, тем это будет выгоднее. Интересно, что к такой же задаче сводится и установление длины года — ведь Земля совершает оборот вокруг Солнца за 365.24219878\ldots суток, а это число иррациональное. Давайте же посмотрим, что такое цепные дроби и как они связаны с алгоритмом Евклида нахождения наибольшего общего делителя двух чисел.

Определение. Непрерывной (или цепной) дробью называется выражение вида

\displaystyle q_1+\frac{1}{q_2+\frac{1}{q_3+}}

\ddots

+\frac{1}{q_n+}

\ddots

Непрерывная дробь может быть как конечной, так и бесконечной.

Числа q_1,q_2,\ldots, участвующие в разложении числа \alpha в непрерывную дробь, называются неполными частными.

Иногда непрерывную дробь обозначают следующим образом (с помощью неполных частных): [q_1,q_2,q_3,\ldots,q_s,\ldots].

Возьмем произвольное вещественное число \alpha. Пусть q_1 — целая часть числа \alpha (q_1=[\alpha] — наибольшее целое число, не превосходящее \alpha). Если число \alpha не целое, то получим \displaystyle \alpha=q_1+\frac{1}{\alpha_2},\ \alpha_2>1. Если \alpha_2 не является целым числом, то для него также можно найти целую часть и найти число \alpha_3 и т.д.:

    \[\begin{array}{ll} \displaystyle \alpha_2=q_2+\frac{1}{\alpha_3};&\alpha_3>1,\\[2mm] \ldots&\\ \displaystyle \alpha_{s-1}=q_{s-1}+\frac{1}{\alpha_{s}};&\alpha_{s}>1, \end{array}\]

откуда и получаем разложение \alpha в непрерывную дробь:

\displaystyle q_1+\frac{1}{q_2+\frac{1}{q_3+}}

\ddots

\displaystyle+\frac{1}{q_{s-1}+\frac{1}{\alpha_s}}.

Ясно, что если число \alpha иррационально, то непрерывная дробь будет бесконечной. Действительно, любая конечная цепная дробь является рациональным числом.

Пример 1. Разложим в непрерывную дробь число \sqrt{3}.

\left[\sqrt{3}\right]=1, поэтому

    \[\sqrt{3}=1+\frac{1}{q_2};\ q_2=\frac{1}{\sqrt{3}-1}=\frac{\sqrt{3}+1}{2} .\]

\displaystyle\left[\frac{\sqrt{3}+1}{2}\right]=1, следовательно,

    \[\frac{\sqrt{3}+1}{2}=1+\frac{1}{\sqrt{3}-1}=\sqrt{3}+1 ;\]

\left[\sqrt{3}+1\right]=2, поэтому

    \[\sqrt{3}+1=2+\frac{1}{q_4};\ q_4=\frac{1}{\sqrt{3}-1}=\frac{\sqrt{3}+1}{2} ,\]

т.е. q_2=q_4. Следовательно, неполные частные также будут повторяться. И разложение \sqrt{3} в непрерывную дробь имеет вид

    \[\sqrt{3}=[1;1,2,1,2,1,2,\ldots]\]

Если же число \alpha рационально, то оно представимо конечной непрерывной дробью. Разложить \alpha в непрерывную дробь в этом случае можно с помощью алгоритма Евклида.

    \[\begin{array}{ll} a=bq_1+r_1;&\displaystyle \frac{a}{b}=q_1+\frac{r_1}{b}=q_1+\frac{1}{\frac{b}{r_1}},\\[3mm] b=r_1q_2+r_2;&\displaystyle \frac{b}{r_1}=q_2+\frac{r_2}{r_1}=q_2+\frac{1}{\frac{r_1}{r_2}},\\[3mm] r_1=r_2q_3+r_3;&\displaystyle \frac{r_1}{r_2}=q_3+\frac{r_3}{r_2}=q_3+\frac{1}{\frac{r_2}{r_3}},\\[3mm] \ldots&\\ r_{n-2}=r_{n-1}q_n+r_n;&\displaystyle \frac{r_{n-2}}{r_{n-1}}=q_n+\frac{r_n}{r_{n-1}}=q_n+\frac{1}{\frac{r_{n-1}}{r_n}},\\[3mm] r_{n-1}=r_nq_{n+1};&\displaystyle \frac{r_{n-1}}{r_n}=q_{n+1}. \end{array}\]

Отсюда последовательной заменой каждой дроби

    \[\frac{b}{r_1},\frac{r_1}{r_2},\ldots,\frac{r_{n-2}}{r_{n-1}},\frac{r_{n-1}}{r_n}\]

на ее соответствующее выражение, получается представление

\displaystyle \frac{a}{b}=q_1+\frac{1}{q_2+\frac{1}{q_3+}}

\displaystyle \ddots +\frac{1}{q_n} .

Определение. Дроби

    \[\delta_1=\frac{P_1}{Q_1}=q_1,\delta_2=\frac{P_2}{Q_2}=q_1+\frac{1}{q_2},\delta_3=\frac{P_3}{Q_3}=q_1+\frac{1}{q_2+\frac{1}{q_3}},\ldots\]

называются подходящими дробями.

Теорема. Для подходящих дробей при s>1 справедливо соотношение

    \[\delta_s=\frac{P_s}{Q_s}=\frac{q_sP_{s-1}+P_{s-2}}{q_sQ_{s-1}+Q_{s-2}} .\]

Другими словами, числители и знаменатели подходящих дробей можно последовательно находить по формулам

    \[P_s= q_sP_{s-1}+P_{s-2},\ Q_s= q_sQ_{s-1}+Q_{s-2} .\]

Доказательство. Доказывать будем по индукции. Проверим базу индукции. Положим P_0=1, Q_0=0. Тогда поскольку \delta_s получается из \delta_{s-1} заменой в выражении для \delta_{s-1} числа q_{s-1} на \displaystyle q_{s-1}+\frac{1}{q_s}, имеем

    \[\frac{P_1}{Q_1}=\frac{q_1}{1},\]

    \[\frac{P_2}{Q_2}=q_1+\frac{1}{q_2}=\frac{q_1+\frac{1}{q_2}}{1}=\frac{q_1q_2+1}{q_2\cdot1+0}=\frac{q_2P_1+P_0}{q_2Q_1+Q_0} .\]

Предположим теперь, что справедливо равенство

    \[\frac{P_k}{Q_k}=\frac{q_kP_{k-1}+P_{k-2}}{q_kQ_{k-1}+Q_{k-2}} .\]

Тогда

    \[\frac{P_{k+1}}{Q_{k+1}}=\frac{\left( q_k+\frac{1}{q_{k+1}}\right) P_{k-1}+P_{k-2}}{\left( q_k+\frac{1}{q_{k+1}}\right) Q_{k-1}+Q_{k-2}}=\]

    \[=\frac{q_{k+1}(q_kP_{k-1}+P_{k-2})+P_{k-1}}{ q_{k+1}(q_kQ_{k-1}+Q_{k-2})+Q_{k-1}}=\frac{q_{k+1}P_k+P_{k-1}}{ q_{k+1}Q_k+Q_{k-1}} .\]

Тем самым, для \delta_{k+1} справедливо равенство того же вида. Теорема доказана.

Вычисления P_k и Q_k удобно производить с помощью следующей таблицы:

    \[\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline $q$&-&$q_1$&$q_2$&$\ldots$&$q_{k-2}$&$q_{k-1}$&$q_k$&$\ldots$&$q_n$&$q_{n+1}$\\ \hline $P$&$1$&$q_1$&$P_2$&$\ldots$&$P_{k-2}$&$P_{k-1}$&$P_k$&$\ldots$&$P_n$&$a$\\ \hline $Q$&$0$&$1$&$Q_2$&$\ldots$&$Q_{k-2}$&$Q_{k-1}$&$Q_k$&$\ldots$&$Q_n$&$b$\\ \hline \end{tabular}\]

Замечание. Последний столбец пишем только в том случае, когда \alpha — несократимая дробь с положительным знаменателем: \alpha=\displaystyle \frac{a}{b}.

Пример 2. Разложим в непрерывную дробь несократимую дробь \displaystyle \frac{125}{92}:

\begin{tabular}{c@{}r@{}|l} &125&92\\ \cline{1--1}\cline{3--3} &92&1\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &92&33\\ \cline{1--1}\cline{3--3} &66&2\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &33&26\\ \cline{1--1}\cline{3--3} &26&1\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &26&7\\ \cline{1--1}\cline{3--3} &21&3\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &7&5\\ \cline{1--1}\cline{3--3} &5&1\\ \cline{2--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &5&2\\ \cline{1--1}\cline{3--3} &4&2\\ \cline{1--2} \end{tabular}

\begin{tabular}{c@{}r@{}|l} &2&1\\ \cline{1--1}\cline{3--3} &2&2\\ \cline{1--2} &0& \end{tabular}

Получаем непрерывную дробь:

    \[\frac{125}{92}=1+\frac{1}{2+\frac{1}{1+\frac{1}{3+\frac{1}{1+\frac{1}{2+\frac{1}{2}}}}}} .\]

Таблица выглядит следующим образом:

    \[\begin{tabular}{|c|c|c|c|c|c|c|c|c|} \hline $q$&$-$&$1$&$2$&$1$&$3$&$1$&$2$&$2$\\ \hline $P$&$1$&$1$&$3$&$4$&$15$&$19$&$53$&$125$\\ \hline $Q$&$-$&$1$&$2$&$3$&$11$&$14$&$39$&$92$\\ \hline \end{tabular}\]

Таким образом, подходящие дроби будут следующие:

    \[\delta_1=1,\delta_2=\frac{3}{2},\delta_3=\frac{4}{3},\delta_4=\frac{15}{11},\delta_5=\frac{19}{14},\delta_5=\frac{53}{39} .\]

В случае же, когда числитель и знаменатель дроби не взаимно простые (НОД(a,b)=d\ne1) в последнем столбце таблицы будут стоять числитель и знаменатель несократимой дроби, равной данной дроби \displaystyle \frac{a}{b}.

Пример 3. Разложим в непрерывную дробь \displaystyle \frac{525}{231}:

Rendered by QuickLaTeX.com

    \[\frac{525}{231}=\frac{25\cdot21}{11\cdot21}=\frac{25}{11} .\]

Утверждение 1. 1) При s>0 имеем

    \[P_sQ_{s-1}-Q_sP_{s-1}=(-1)^s .\]

2) При s>0 имеем

    \[\delta_s-\delta_{s-1}=\frac{(-1)^s}{Q_sQ_{s-1}} .\]

Доказательство. Действительно, при s=1 получаем

    \[P_1Q_0-P_0Q_1=q_1\cdot0-1\cdot1=-1 .\]

Далее из равенств

    \[P_s= q_sP_{s-1}+P_{s-2},\ Q_s= q_sQ_{s-1}+Q_{s-2}\]

    \[P_sQ_{s-1}-Q_sP_{s-1}=P_{s-1}Q_{s-2}-Q_{s-1}P_{s-2} ,\]

откуда сразу же следует требуемое.

Вторая часть утверждения получается следующим образом:

    \[\delta_s-\delta_{s-1}=\frac{P_s}{Q_s}-\frac{P_{s-1}}{Q_{s-1}}=\frac{(-1)^s}{Q_sQ_{s-1}} .\]

Следствие. Линейное представление наибольшего общего делителя чисел a и b получается из равенства

    \[P_{n+1}Q_{n}-Q_{n+1}P_{n}=(-1)^{n+1}\]

домножением на НОД(a,b)=d, поскольку a=d\cdot P_{n+1},\ b=d\cdot Q_{n+1}.

Пример 4. Приведем линейное представление наибольшего общего делителя чисел 525 и 231 (см. пример 3):

    \[25\cdot4\cdot21-11\cdot9\cdot21=(-1)^4\cdot21\]

или

    \[4\cdot525-9\cdot231=21 .\]

Утверждение 2. Пусть s>1, а если \alpha — рациональная несократимая дробь \displaystyle \alpha=\frac{a}{b} с положительным знаменателем, то пусть также s<n+1. Тогда \alpha лежит между \delta_{s-1} и \delta_s, причем ближе к \delta_s, чем к \delta_{s-1}.

Доказательство. Заменим в равенстве

    \[\delta_s=\frac{P_s}{Q_s}=\frac{q_sP_{s-1}+P_{s-2}}{q_sQ_{s-1}+Q_{s-2}}\]

q_s на \displaystyle q_s+\frac{1}{\alpha_{s+1}}, получим

    \[\alpha=\frac{\alpha_{s+1}P_s+P_{s-1}}{\alpha_{s+1}Q_s+Q_{s-1}} ,\]

    \[\alpha\alpha_{s+1}Q_s+\alpha Q_{s-1}-\alpha_{s+1}P_s-P_{s-1}=0 ,\]

    \[\displaystyle \alpha_{s+1}Q_s\left(\alpha-\frac{P_s}{Q_s}\right)+Q_{s-1}\left(\alpha-\frac{P_{s-1}}{Q_{s-1}}\right)=0,\]

откуда ясно, что первая из разностей, стоящих в скобках, по знаку противоположна второй и численно меньше (так как Q_s>Q_{s-1}), что и доказывает наше утверждение.

Литература

1. Баврин И.И., Фрибус Е.А. Занимательные задачи по математике.2. Виноградов И.М. Основы теории чисел3. Нестеренко Ю.В., Никишин Е.М. Очерк о цепных дробях, Квант, 1983. – N5. – C- 16—20; N6. – С. 26-30

hijos.ru

Реферат Цепная дробь

скачать

Реферат на тему:

План:

Введение

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

[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 натуральные числа (то есть неотрицательные целые). Любое вещественное число можно представить в виде цепной дроби (конечной или бесконечной). Число представляется конечной цепной дробью тогда и только тогда, когда оно рационально. Число представляется периодической цепной дробью тогда и только тогда, когда оно является квадратичной иррациональностью.

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

Любое вещественное число 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 это разложение оборвётся по достижении нулевого xn для некоторого n. В этом случае x представляется конечной цепной дробью x = [a_0; a_1, \cdots, a_n].

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

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

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

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}.

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

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\} являются возрастающими.

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

pnqn - 1 - qnpn - 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}.

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

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

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

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

3.1. Примеры

Вторая дробь (22/7) — это известное архимедово приближение. Четвёртая (355/113) была впервые получена в Древнем Китае.

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

9/4=[2; 3, 1] = [2; 4]\; Например: \sqrt{2} = [1; 2, 2, 2, 2, \dots] золотое сечение \phi = [1;1,1,1,\dots] e − 1 = [1;1;2;1;1;4;1;1;6;1;1;8;...;1;1;2n − 2;1;1;2n;...]

для числа

\operatorname{tg}\,1 = [1; 1; 1; 3; 1; 5; 1; 7; ...; 1; 2n+1; 1; 2n+3; ...] π = [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,…]

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

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

При разработке солнечного календаря необходимо найти рациональное приближение для числа дней в году, которое равно 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), однако большого интереса он не вызвал.

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

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

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

mqn − 1 − apn − 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  является решением исходного сравнения.

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

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

Интересный результат, которые следует из того факта, что выражение непрерывной дроби для φ не использует целых чисел больше чем 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 – имеют такое же свойство как и золотое сечение φ; а также, что все остальные действительные числа могут быть приближены намного лучше.

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

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

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

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

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

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

7. Мотивация

Непрерывные дроби являются самыми "математически естественными" представлениями вещественных чисел.

Большинство людей знакомы с десятичным представлением вещественных чисел, которое может быть определено как

r = \sum_{i=0}^\infty a_i 10^{-i},

где a0 может быть любым целым числом, а последующие ai являются одним из элементом {0,1,2,…,9}. В этом представление, число π, к примеру, может быть представлено как последовательность целых чисел (a_i) = (3,1,4,1,5,9,2,\ldots).

Это десятичное представление имеет несколько проблем. Одна из них, многие рациональные числа не имеет конечного представления в этой системе. Например, число 1/3 представимо бесконечной последовательностью (0,3,3,3,3,…). Другая проблема заключается в том, что константа 10 является по сути произвольным выбором, который оказывает предпочтение числам, которые как-либо относятся к целому числу 10. Например, 137/1600 имеет конечное десятичное представление, тогда как 1/3 не имеет, не потому, что 137/1600 проще чем 1/3, а всего лишь потому, что 1600 делит степень 10 (106 = 1600 × 625). Запись как цепная дробь является представлением вещественных чисел, которая не имеет этих проблем.

Давайте рассмотрим как мы можем описать число, такое как 415/93, которое примерно равняется 4,4624. Это примерно 4.Вообще-то это чуть больше чем 4, около 4 + 1/2. Но 2 в знаменателе не совсем точно; там должно быть число чуть больше чем 2, примерно 2 + 1/6. Таким образом, 415/93 примерно равняется 4 + 1/(2 + 1/6). Но 6 в знаменателе не верно; настоящее значение чуть больше 6, 6+1/7. Таким образом, 415/93 является 4+1/(2+1/(6+1/7). Это точное значение.

Опуская некоторые обязательные части в выражении 4 + 1 / (2 + 1 / (6 + 1 / 7)) мы получим краткую нотацию [4;2,6,7]. (Заметьте, что общепринято заменять только первую запятую точкой с запятой).

Представление как непрерывная дробь вещественного числа может быть определена таким образом. Она имеет несколько желательных свойств:

{a+b\sqrt{c} \over d}

для целых a, b, c, d; где b и d не ноль и c>1 и c не является точным квадратом.

К примеру, периодическая непрерывная дробь [1; 1, 1, 1, …] является золотым сечением, а периодическая непрерывная дробь [1; 2, 2, 2, …] является квадратным корнем из 2.

Последнее свойство чрезвычайно важно. У десятичного представления числа его нет. Усечение десятичного представления числа приводит к рациональному приближению числа, но обычно к не очень хорошему приближению. К примеру, усечение 1/7 = 0.142857… в разных местах приводит к приближениям таким как 142/1000, 14/100 и 1/10. Но очевидно лучшим рациональным приближением будет само число "1/7". Обрывая десятичное представление π мы получаем приближения такие как 31415/10000 и 314/100. Цепная дробь π начинается [3; 7, 15, 1, 292, …]. Усекая это представление мы получаем отличные рациональные приближение 3, 22/7, 333/106, 355/113, 103993/33102, …. Знаменатели 314/100 и 333/106 почти одинаковые, но ошибка в приближении 314/100 в девятнадцать раз больше ошибки, чем в приближении 333/106. Как приближении π, [3; 7, 15, 1] более чем в сто раз точнее приближения 3,1416.

wreferat.baza-referat.ru

Смотрите также