 |
Пункт 10. Континуанты. Анализ алгоритма Евклида.
|
|
|
|
В этом пункте я расскажу о вещах совсем малоизвестных, хотя абсолютно доступных для понимания. Сначала напомню забывчивым читателям рекуррентные соотношения для числителей и знаменателей подходящих дробей:
P s = q s P s -1 + P s -2 - числители
Q s = q s Q s -1 + Q s -2 - знаменатели.
Начальные условия: P 1 = q 1 , P 0 = 1, Q 1 = 1, Q 0 = 0.
Теперь, когда эти соотношения стоят как живые у нас перед глазами в удобном месте, давайте рассмотрим не их, а трехдиагональный определитель:
| = (q 1 q 2 ... q n ) |
Определение. Определитель (а при устном рассказе, во избежание ненужной аллитерации "определение определителя", - детерминант), обозначенный несколькими строками выше через (q 1 q 2 ... q n ), называется континуантой n -ого порядка. Числа q 1 , q 2 ,..., q n в дальнейшем будут у нас неполными частными из алгоритма Евклида, поэтому подразумеваются целыми.
Разложим континуанту n -ого порядка по последнему столбцу (читатели наверняка натренировались делать это еще на первом курсе, когда вычисляли подобные определители из задачника Проскурякова по алгебре). Получим:
(q 1 q 2 ... q n ) = q n (q 1 q 2 ... q n -1 ) + (q 1 q 2 ... q n -2 ).
Получившееся соотношение очень напоминает рекуррентные соотношения для числителей и знаменателей подходящих дробей. Это не случайно и две следующие леммы только подтверждают нашу зародившуюся догадку о явной связи континуант и цепных дробей.
Лемма 1. Континуанта (q 1 q 2 ... q n ) равна сумме всевозможных произведений элементов q 1 , q 2 ,..., q n одно из которых содержит все эти элементы, а другие получаются из него выбрасыванием одной или нескольких пар сомножителей с соседними номерами (Если выбросили все сомножители, то считаем, что осталась 1).
Поясняющий пример.
|
|
|
(q 1 q 2 q 3 q 4 q 5 q 6 ) = q 1 q 2 q 3 q 4 q 5 q 6 + q 3 q 4 q 5 q 6 + q 1 q 4 q 5 q 6 + q 1 q 2 q 5 q 6 + q 1 q 2 q 3 q 6 + q 1 q 2 q 3 q 4 + q 5 q 6 + q 3 q 6 + q 1 q 6 + q 3 q 4 + q 1 q 4 + q 1 q 2 + 1.
Достучался ли я до вас этим примером, дорогие друзья? Понятно?
Доказательство. База индукции:
(q 1 ) = q 1 ,
| (q 1 q 2 ) = | 
| = q 1 q 2 + 1, |
и утверждение леммы справедливо для континуант первого и второго порядков.
Шаг индукции. Пусть утверждение леммы верно для континуант (n - 2)-го и (n - 1)-ого порядков. Тогда имеем:
(q 1 q 2 ... q n ) = q n (q 1 q 2 ... q n -1 ) + (q 1 q 2 ... q n -2 )
и просто внимательное разглядывание этого равенства в сочетании с мысленным прикидыванием, какие произведения получатся от умножения континуанты (q 1 q 2 ... q n -1 ) на q n , доказывает требуемое.
¨
Наблюдение. Количество слагаемых в континуанте n -ого порядка есть сумма числа слагаемых в континуантах (n - 1)-ого и (n - 2)-го порядков, т.е. континуанта (q 1 q 2 ... q n ) содержит F n +1 слагаемых, где F n +1 - (n +1)-ое число Фибоначчи.
Лемма 2.
Доказательство. База индукции:
| - верно. |
Шаг индукции. Пусть верно, что
Тогда:
¨
Утверждение леммы 2, устанавливающее прямую связь континуант с цепными дробями, впервые заметил Леонард Эйлер. Этот гениальный математик еще много что заметил, но, боюсь, полный рассказ о его математических достижениях не уместится в эту книжку даже самым мелким шрифтом. Мы отложим должное небольшое историческое отступление про Эйлера до пункта 18, где будет рассказана теорема, носящая его имя.
Приступим теперь к исполнению второй части названия этого пункта - анализу алгоритма Евклида. Нас будет интересовать наихудший случай - когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает
Теорема (Ламэ, 1845 г.). Пусть n Î N, и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = F n +2 , b = F n +1 , где F k - k- ое число Фибоначчи.
|
|
|
Доказательство. Разложим a / b в цепную дробь:
| a b | = | (q 1 q 2 ... q n ) (q 2 q 3 ... q n ) | , |
где q 1 , q 2 ,..., q n - неполные частные из алгоритма Евклида; по условию теоремы, их точно n штук. Согласно свойству 3 пункта 9, континуанты (q 1 q 2 ... q n ) и (q 2 q 3 ... q n ) взаимно просты, значит, если (a, b) = d - наибольший общий делитель, то
| (ª) |
Заметим, что по смыслу конечной цепной дроби, q n ³ 2, a q 1 , q 2 ,..., q n -1 , d ³ 1.
Поскольку континуанта суть многочлен с неотрицательными коэффициентами от всех этих переменных, минимальное значение достигается при q 1 = q 2 =...= q n -1 = d = 1, q n = 2. Подставляя эти значения в (ª), получим: а = F n +2 , b = F n +1 .
¨
Следствие. Если натуральные числа a и b не превосходят N Î N, то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает é log Ф (Ö 5 N) ù - 2, где é a ù - верхнее целое a, F = (1 + Ö 5)/2 - больший корень характеристического уравнения последовательности Фибоначчи (искусствоведы сказали бы: "золотое сечение").
Доказательство. Максимальное число шагов n достигается при а = F n +2 , b = F n +1 , где n - наибольший номер такой, что F n +2 < N. Рассматривая формулу для n -ого члена последовательности Фибоначчи (смотри, например, доказательство свойства 4 в пункте 9), легко понять, что F n +2 - ближайшее целое к (1/ Ö 5) F n +2 . Значит (1/ Ö 5) F n +2 < N, следовательно, n +2 < log Ф (Ö 5 N), откуда моментально даже n < é log Ф (Ö 5 N) ù - 3 (именно "минус три", ведь рассматривается верхнее целое, т.е., кажется, утверждение следствия можно усилить).
¨
Для еще не купивших калькулятор сообщу, что log Ф (Ö 5 N)» 4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за é 4,785 · 6 + 1,672 ù - 3 = 31 - 3 = 28 шагов.
Ну вот, используя теорему Ламэ, мы провели некоторый анализ быстродействия алгоритма Евклида и узнали наихудший случай для него - два последовательных числа Фибоначчи. Таким образом, давно висевшая перед нами народохозяйственная проблема об эффективности древнегреческого наследия решена полностью. На этом пункт и закончим.
|
|
|
Задачки 
| 1. Вычислите континуанты:
а) (1, 2, 3, 4, 5);
б) (1, 1, 1, 1, 1, 1);
в) (1, -1, 1, -1, 1)
301.(Из задачника Проскурякова). Методом рекуррентных соотношений вычислить определитель:
3. Потрудитесь и распишите на сумму произведений континуанту (q 1 q 2 q 3 q 4 q 5 q 6 q 7 ). Сколько получилось слагаемых?
4. Найдите все перестановки s множества {1, 2,..., n } такие, что (q 1 q 2 ... q n ) = (q s (1) q s (2) ... q s (n) ) для любых чисел q 1 , q 2 ,..., q n .
5. Помогите остаткам цивилизации заалтайских шоферов найти произведение матриц:
 .
6. Пусть a - иррациональное число и его разложение в цепную дробь суть:
Докажите, что тогда:
для соответствующих целых b 0 , b 1 ,..., b m . (Рассмотрите отдельно случаи a > 0 и a < 0.) Объясните, как выражаются все b 0 , b 1 ,..., b m через a 0 , a 1 , a 2 , a 3 , a 4 .
7. Каково наибольшее число шагов, необходимых алгоритму Евклида для обработки двух чисел, меньших миллиарда?
|
|
|
|
