2.2.4. Алгоритм Евклида и цепные дроби

Цепные дроби играют важную роль во многих областях математики. В гл. 7 этой книги мы увидим, как их можно использовать для построения очень эффективного алгоритма отделения и аппроксимации вещественных корней полиномов с целыми коэффициентами. В этом разделе мы введем цепные дроби, используя алгоритм Евклида (Olds, 1963; Richards, 1981).

Рассмотрим произвольную рациональную дробь записанную в несократимом виде, т.е. Применив к паре алгоритм Евклида, получим

Эти обозначения несколько отличаются от тех, которые мы использовали в разд. 2.2.2; а именно мы заменили на . Если мы запишем вместо для всех в пределах приведенные выше равенства примут вид

Если в заменить на , то получится Продолжая этот процесс, мы получим

Это — представление в виде цепной дроби. Целые числа называются неполными частными. Так как в общем случае может не быть положительным (мы предполагаем, что ), может быть положительным, отрицательным или нулевым. Однако, поскольку в алгоритме Евклида частное положительно и точно также положительны Мы будем использовать обозначение (со; ) для цепной дроби, приведенной выше.

Пример. Рассмотрим рациональную дробь 8/5. Нетрудно видеть, что Более того, можно проверить, что Оказывается, всякое рациональное число имеет только два представления в виде цепной дроби. В общем случае,

Замечание. Наше условие, что положительны, не является общепринятым. Если отказаться от него, то дробь —8/5 может также быть представлена в виде цепных дробей .

Цепные дроби могут быть конечными или бесконечными; например, цепная дробь, представляющая число 8/5, конечна. Следующие две теоремы устанавливают некоторые свойства конечных цепных дробей. Нам необходимо следующее определение.

Определение 2.2.11. Целой частью числа с называется

Теорема 2.2.12 (единственность). Если и если то для

Доказательство. Используем индукцию. Определим числа Очевидно, что

Заметим, что для для более того, для всех t в соответствующих пределах. По условию теоремы и, рассматривая целые части, имеем . По определению получаем откуда вытекает, что Предоставим читателю завершить шаг индукции: из того, что вытекает, что Кроме того, должно быть равным . Чтобы убедиться в этом, предположим без потери общности, что . Тогда из предыдущего рассуждения следует, что . Однако это противоречит тому, что

Теорема 2.2.13. Любая конечная цепная дробь представляет рациональное число, и, обратно, всякое рациональное число может быть представлено в виде конечной цепной дроби, причем ровно двумя способами.

Доказательство. Первая часть доказывается индукцией по числу членов в цепной дроби при помощи формулы () Вторая часть следует из возможности представления любого рационального числа в виде цепной дроби и теоремы

До сих пор мы имели дело только с рациональными числами и конечными цепными дробями, а что можно сказать об иррациональных числах и их разложениях? Некоторые очень важные свойства разложений иррациональных чисел в цепные дроби объединены в теореме 2.2.14, которую мы приводим без доказательства.

Теорема 2.2.14. Любое иррациональное число представимо единственным образом в виде бесконечной цепной дроби , где значения вычисляются с помощью следующего алгоритма:

Положим и определим по индукции

Обратно, всякая бесконечная цепная дробь, заданная числами для любого t, представляет иррациональное число . Более

того, если мы положим

то конечная цепная дробь будет иметь рациональное значение которое называется подходящей дробью иррационального числа . Знаменатели подходящих дробей образуют возрастающую последовательность положительных целых чисел для и выполняются следующие соотношения:

Наконец, всякая периодическая цепная дробь является квадратичным иррациональным числом, и обратно. (Квадратичным иррациональным числом называется число вида являющееся корнем квадратного полиномиального уравнения , где d — целое положительное число, не являющееся точным квадратом.)

Отметим, что алгоритм Евклида мажет быть использован только для разложения в цепную дробь рационального числа; из теоремы 2.2.14 видно, что имеется более общая процедура, которая может быть использована как для рационального, так и для иррационального числа. А именно пусть нам дано число (рациональное или иррациональное). Вычислим наибольшее целое

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

Теорема 2.2.15. Рассмотрим бесконечную цепную дробь и пусть — ее подходящая дробь. Справедливы следующие утверждения:

d. Лля четных значений последовательность подходящих дробей монотонно возрастает, и ее предел равен ; для нечетных значений соответствующая последовательность монотонно убывает, ее предел также равен ; кроме того, каждое меньше, чем и каждая подходящая дробь лежит между двумя предыдущими подходящими дробями.

Доказательство.

a. Доказательство будем вести по индукции. Для пользуясь теоремой 2.2.14, получаем поэтому равенство справедливо; отметим, что . Допустим теперь, что равенство выполняется для , т. е. Мы покажем, что оно справедливо и для к Пользуясь опять теоремой 2.2.14, получим

b. Для доказательства этого пункта разделим обе части равенства на после чего получим Требуемое равенство теперь следует из того, что

c. Здесь в числителе соответствующими им выражениями

(из теоремы соответственно, получаем

Выведем этот пункт из предыдущих. Из пп. b и с следует, что потому что положительно для . Таким образом, Последовательность с четными индексами монотонно возрастает и ограничена сверху числом аналогично, последовательность с нечетными индексами монотонно убывает и ограничена снизу числом Эти два предела должны быть одинаковыми, поскольку разность стремится к нулю при , стремящемся к бесконечности, а целые числа возрастают с ростом .

Следует отметить, что утверждения теоремы 2.2.15 были бы иными, если бы в теореме 2.2.14 мы определили целые числа начав с не с . А именно если мы положим

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

а пп. b и с будут справедливы для соответственно. В гл. 7 книги мы будем использовать эту форму записи подходящих дробей.

Пример. Разложим рациональное число 144/89 в цепную дробь, используя алгоритм, описанный в теореме 2.2.14; обратим также внимание на то, как ведут себя подходящие дроби. В начале положим и, используя соотношения получим и — это первая четная подходящая дробь для числа 144/89, аппроксимирующая это число снизу. Затем вычислим и, используя те же соотношения, — первая нечетная подходящая дробь для числа 144/89, аппроксимирующая это число сверху. Далее имеем

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

Теорема 2.2.16. Пусть — иррациональное число, и пусть — его разложение в цепную дробь, где . Справедливы следующие утверждения:

a. Каждая подходящая дробь расположена ближе к , чем предыдущая.

c. Существует бесконечно много рациональных чисел вида таких, что .

Доказательство.

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

b. Из п. b теоремы 2.2.15 получаем ; кроме того, мы только что доказали, что расположено ближе к чем к и, следовательно, где потому что (См. также рис. 2.2.1.)

c. Этот пункт следует из того, что число иррационально, и существует бесконечно много подходящих дробей удовлетворяющих

Отметим, что неравенство выполняется также и для рациональных чисел.

Рис. 2.2.1. Геометрическое доказательство части b теоремы 2.2.16.

Пример. Вычислим несколько первых членов разложения числа в цепную дробь. Можно показать, что . Как уже было отмечено выше, для иррационального числа не всегда можно получить его полное разложение в цепную дробь, поскольку алгоритм Евклида не может быть применен; если, однако, известно десятичное приближение числа то можно вычислить соответствующую часть цепной дроби, представляющей . В нашем случае допустим, что нам достаточно приближения . Используя алгоритм, описанный в теореме 2.2.14, получим

Итак, мы получили Мы видим, что первые четыре неполные частные для числа совпадают с первыми четырьмя неполными частными для разложения в цепную дробь рационального числа 3.14159. Используя соотношения для подходящих дробей, получаем четыре первых приближения для . Проверим теперь справедливость неравенства Для имеем и после вычисления обеих частей получим

Отметим здесь открытие Эйлера: разложение числа в цепную дробь обладает в отличие от замечательной регулярностью: доказательство достаточно сложно и выходит за рамки этой книги.

Заметим, что неполные частные чисел не периодичны и 1 встречается чаще, чем любое другое число. Интересный результат Кузьмина (Lang, IYotter, 1972) утверждает, что для почти всех чисел вероятность того, что в разложении его в цепную дробь неполное частное равно положительному целому числу j, дается формулой

Это означает, что для почти всех чисел вероятность того, что примерно равна 0.41.

В конце этой главы рассмотрим бесконечные периодические цепные дроби, представляющие иррациональные числа (см. теорему 2.2.14); предположим, например, что Что из себя представляет 4? Заметим, что в нашем случае мы мажем записать согласно теореме 2.2.14; далее, поскольку имеем Отсюда следует, что или Итак, 4 удовлетворяет квадратному уравнению, и, отбросив отрицательный корень, мы получим — квадратичное иррациональное число.

Пример. Пусть вычислим его разложение в цепную дробь. Используя алгоритм из теоремы 2.2.14, мы получим

Таким образом, мы получили