Teoriy_chisel_Lekcii-Sizuy

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

Свойство 1 . P s Q s -1 - Q s P s -1 = (- 1) s , s > 0.

Доказательство. Обозначим h s = P s Q s -1 - Q s P s -1 .

h 1 = P 1 Q 0 - Q 1 P 0 = q 1 · 0 - 1 · 1 = -1, h s = P s Q s -1 - Q s P s -1 =

=( q s P s -1 + P s -2 ) Q s -1 - ( q s Q s -1 + Q s -2 ) P s -1 =

=P s -2 Q s -1 - Q s -2 P s -1 = - h s -1 .

Значит, h s = (-1) s .

♦

Свойство 2.
	(-1) s
δ s - δ s -1 =				, s > 1.
	Q s Q s -1
Доказательство.
	P s		P s -1			h s		(-1) s
δ s - δ s -1 =		=			=		=		. ♦
	Q s		Q s -1			Q s Q s -1		Q s Q s -1

Свойство 3. Для любого s > 0, дробь P s / Q s - несократима.

Доказательство. Ну пусть наибольший общий делитель ( P s , Q s ) равен d и d > 1. Тогда d делит разность P s Q s -1 - Q s P s -1 , равную (-1) s , что невозможно.

♦

Свойство 4.

и равенство достигается только при q 1 = q 2 =...= q s = 1. Доказательство. Нам уже известно, что

Q 0 = 0, Q 1 = 1, q i N , Q s = q s Q s -1 + Q s -2 ≥ Q s -1 + Q s -2 .

Наиболее медленный рост знаменателей будет наблюдаться при Q s = Q s -1 + Q s -2 , т.е. при q 1 = q 2 = ... = q s = 1. Это рекуррентное соотношение вместе с начальными условиями Q 0 = 0, Q 1 = 1 задает последовательность Фибоначчи. Характеристическое уравнение для рекуррентного соотношения Фибоначчи:

			x 2 = x + 1;
		1± √ 5
	его корни: x 1,2 =		;
		2
	общее решение:

Подстановка начальных условий в общее решение дает

откуда C 1 = - C 2 = 1/ √ 5.

Впрочем, формула s -ого члена последовательности Фибоначчи достаточно общеизвестна, ее вывод можно посмотреть, например, в брошюрах А. И. Маркушевича "Возвратные последовательности" или Н. Н. Воробьева "Числа Фибоначчи" из серии "Популярные лекции по математике", регулярно выходившей для школьников в издательстве "Наука".

Итак, знаменатели подходящих дробей растут не медленнее последовательности Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,...

♦

Отступление про Фибоначчи.

Фибоначчи - "Сын Боначчо" или Леонардо Пизанский (1180 - 1240), - известный средневековый математик-кроликовод, философ, купец и т.д. Путешествовал и торговал в странах востока, но, в отличие от тупых современных челноков, озабоченных только марксовской разностью Д ′ - Д, где Д - деньги, Д ′ - деньги штрих, изучал науку востока. По возвращению в Европу он записал собранные сведения, добавил много собственных исследований и издал книги "Практика геометрии" и "Книга абака". Последовательность Фибоначчи возникает у самого Леонардо при решении следующей задачи: Сколько пар кроликов может произойти от одной пары в течении года, если а) каждая пара каждый месяц порождает новую пару, которая со второго месяца становится производителем, и б) кролики не дохнут. Поразительным образом, демонстрируя единство мироздания, последовательность Фибоначчи появляется не только при изучении цепных дробей, но и во многих других разделах математики, физики, биологии, искусствоведения. Кроме порождения на свет этой замечательной последовательности и другого прочего, "Книга абака" была одним из решающих источников проникновения в Западную Европу десятичной системы счисления и арабской записи цифр. Честь и хвала безумцам, которые, порой в ущерб своему благосостоянию, сохраняют и развивают культуру целых поколений, безумцам, чья система ценностей не замкнута на шмотках, деньгах и развлечениях!

Свойство 5. Для любой бесконечной цепной дроби, последовательность δ 1 , δ 2 , δ 3 ,...

сходится.

Доказательство. Рассмотрим подпоследовательности:

P 0 P 2

P 2 n

,, ... , , ... - дроби с четными номерами и

Q 0		Q 2		Q 2 n
P 1		P 3		P 2 n +1
	,		, ... ,		, ... - дроби с нечетными номерами.
Q 1		Q 3		Q 2 n +1

Имеем:

P 2 n +2 - P 2 n = δ 2 n +2 - δ 2 n +1 + δ 2 n +1 - δ 2 n =

Q 2 n +2 Q 2 n
1			-1
=		+		< 0,
	Q 2 n +2 Q 2 n +1		Q 2 n +1 Q 2 n

т.к. Q 2 n +2 Q 2 n +1 > Q 2 n +1 Q 2 n . Значит, подпоследовательность дробей с четными номерами монотонно убывает. Аналогично, вторая подпоследовательность монотонно возрастает. Всякий член "четной" последовательности больше всякого члена "нечетной". Действительно, рассмотрим δ 2 n и δ 2 m +1 . Возьмем четное k такое, что k +1 > 2 n и k +1 > 2 m + 1. Тогда

	1
δ k - δ k -1 = +		> 0, т.е. δ k > δ k -1 .
	Q k Q k -1

Но ведь δ k < δ 2 n , в силу убывания последовательности "четных", а δ k -1 > δ 2 m +1 , в силу возрастания последовательности "нечетных". Значит, δ 2 n > δ k > δ k -1 > δ 2 m +1 , что и нужно. Получается, что обе последовательности монотонны и ограничены, следовательно, имеют пределы. Кроме того,

	1		1
| δ s - δ s -1 | =		<		—— → 0,
	Q s Q s -1			s →∞
			Φ s Φ s -1

где Φ s - s -ый член последовательности Фибоначчи, следовательно пределы обеих подпоследовательностей совпадают.

Итак, всякая бесконечная цепная дробь имеет некоторое значение.

♦

Свойство 6. Пусть α R раскладывается в цепную дробь, например, с помощью процесса взятия целых частей и "переворачивания" дробных (этот процесс предложен в пункте 7 после формулировки основной теоремы о цепных дробях), т.е.

- результат очередного этапа процесса разложения. Тогда α лежит между δ s -1 и δ s , причем

ближе к δ s , чем к δ s -1 .

Доказательство. На ( s +1)-ом шаге разложения мы заменяем q s на q s + 1/ α s +1 , поэтому имеем точное равенство:

α s +1 P s + P s -1

α =		, значит

α s +1 Q s + Q s -1

α α s +1 Q s + α Q s -1 - α s +1 P s - P s -1 = 0.

Преобразуем:

	P s			P s -1
α s +1 Q s α -		+ Q s -1 α -			= 0.
	Q s			Q s -1

Это равенство означает, что разности в скобках разных знаков. Кроме того, Q s > Q s -1 , α s +1 > 1, значит

	P s			P s -1
α -		< α -			. ♦
	Q s			Q s -1

Свойство 7. Для любого α R , разложение в цепную дробь единственно. Доказательство. Пусть есть два разложения одного и того же числа:

Если два числа совпадают, то у них совпадают целые части, т.е. р 1 = q 1 , и совпадают обратные величины к дробным частям:

Далее точно так же, по индукции.

♦

Наблюдательный читатель уже наверняка заметил, что основная теорема о цепных дробях (сформулированная в пункте 7), о необходимости доказательства которой так долго говорили большевики, к этому моменту оказалась доказанной. Более того, из вышеизложенного следует, что всякая цепная дробь (конечная или бесконечная) сходится именно к тому числу, которое было в нее разложено. И слава Богу! Аллилуйя!

Задачки	1		. Найдите формулу n -ого члена последовательности,
	задаваемой рекуррентно: a n = a n -1 + 2 a n -2 ; a 1 = 0, a 2 = 6.
	2		. Продвинутый десятиклассник Петя решает на школьной
	олимпиаде такую задачу:
		Доказать, что при любом n = 0, 1, 2,..., число

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

Помогите Пете, не используя бином Ньютона.

3 . Вычислите α с точностью до десятого знака после запятой, если:

а) α = √ 2; б) α = √ 5.

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

4 . Вычислив последнюю и предпоследнюю подходящие дроби числа 215/157, решите диофантовы уравнения:

а) 215 x - 157 y = 1; б) 215 x - 157 y = 4.

§ 2. Цепные дроби

Пункт 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 ) содержит Φ n +1 слагаемых, где Φ n +1 - ( n +1)-ое число Фибоначчи.

Лемма 2.

Доказательство. База индукции:

- верно.

Шаг индукции. Пусть верно, что

Тогда:

♦

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

Приступим теперь к исполнению второй части названия этого пункта - анализу алгоритма Евклида. Нас будет интересовать наихудший случай - когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает

Теорема (Ламэ, 1845 г.). Пусть n N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = Φ n +2 , b = Φ n +1 , где Φ k - k- ое число Фибоначчи.

Доказательство. Разложим a / b в цепную дробь:

a = ( q 1 q 2 ... q n ) ,

b ( q 2 q 3 ... q n )

где q 1 , q 2 ,..., q n - неполные частные из алгоритма Евклида; по условию штук. Согласно свойству 3 пункта 9, континуанты ( q 1 q 2 ... q n ) и ( q просты, значит, если ( a , b ) = d - наибольший общий делитель, то

( ♠ )

теоремы, их точно n 2 q 3 ... q n ) взаимно

Заметим, что по смыслу конечной цепной дроби, 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.

Подставляя эти значения в ( ♠ ), получим: а = Φ n +2 , b = Φ n +1 .

♦

Следствие. Если натуральные числа a и b не превосходят N N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает log Ф ( √ 5 N ) - 2, где α - верхнее целое α , Φ = (1 + √ 5)/2 - больший корень характеристического уравнения последовательности Фибоначчи (искусствоведы сказали бы: "золотое сечение").

Доказательство. Максимальное число шагов n достигается при а = Φ n +2 , b = Φ n +1 , где n - наибольший номер такой, что Φ n +2 < N . Рассматривая формулу для n -ого члена последовательности Фибоначчи (смотри, например, доказательство свойства 4 в пункте 9), легко понять, что Φ n +2 - ближайшее целое к (1/ √ 5) Φ n +2 . Значит (1/ √ 5) Φ 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 . Найдите все перестановки σ множества {1, 2,..., n } такие, что ( q 1 q 2 ... q n ) = ( q σ (1) q σ (2) ... q σ ( n ) ) для любых чисел q 1 , q 2 , ... , q n .

5 . Помогите остаткам цивилизации заалтайских шоферов найти произведение матриц:

.

6 . Пусть α - иррациональное число и его разложение в цепную дробь суть:

Докажите, что тогда:

для соответствующих целых b 0 , b 1 , ..., b m . (Рассмотрите отдельно случаи α > 0 и α < 0.) Объясните, как выражаются все b 0 , b 1 , ..., b m

через a 0 , a 1 , a 2 , a 3 , a 4 .

7 . Каково наибольшее число шагов, необходимых алгоритму Евклида для обработки двух чисел, меньших миллиарда?

§ 2. Цепные дроби

Пункт 11. Еще кое-что о цепных дробях (приближение чисел, периодичность, теорема Эрмита).

Вэтом пункте я хочу рассказать кое-что еще о свойствах цепных дробей, что не уложилось

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

Теорема. Пусть α - произвольное число, s > 1, а если при этом

α = a / b - несократима, то s < n , где n таково, что Q n = b . Тогда неравенство

возможно только если у несократимой дроби c / d знаменатель больше Q s .

Доказательство. Мы знаем, что α всегда лежит между соседними подходящими дробями, поэтому всегда

Это неравенство проиллюстрировано рисунком 4, разглядывая который, нужно помнить, что

(тогда иллюстрируемое неравенство становится очевидным, даже если c / d < δ s +1 ).

Рис. 4 Из проиллюстрированного неравенства следует, что

и, если c / d ≠ δ s +1 , то

Следовательно,