для приближения
α с точностью
ε достаточно соблюдения условия
1/q2n < ε => qn > 1/√ε
Остается получить оценку сверху для qn, причем требуется оценить qn величиной, связанной с Ic. Сделаем это.
Для знаменателей qn подходящих дробей справедливо рекуррентное соотношение (см. [1], стр. 11, формула (7))
qк = aкqк-1 + aкqк-2,
причем по определению полагается q-1 = 0, q0 = 1. Тогда q1 = а1, q2 = a2a1 + 1, q3 = a3a2a1 + a3 + a1 и т. д.
Лемма. Для знаменателей qn верна оценка qn <= 2n-1πn, где πn= Пn i=1= ai.
Доказательство (методом мат. индукции). Для n = 1 утверждение верно, ибо q1 = а1. Предположим, что оценка верна для всех k и n. Тогда
поскольку выражение в круглых скобках не превосходит единицы ибо аn >= 1, аn+1 >= 1. Лемма доказана.
Опираясь теперь на лемму, заключаем, что для аппроксимации числа α с точностью ε должно быть:
1/√ε < qn =< 2n-1Пni-1 ai
Следовательно, используя (2), находим:
Таким образом, учитывая (1), получаем соотношение:
Ic(ε) >= (1/2)∙I2(ε) - n + 3/2
Впрочем, данная оценка довольно груба. Ее можно немного усилить.
С другой стороны, очевидно, qn >= Пn i=1 ai (доказывается тоже индукцией), поэтому если
1/q2n < ε < 1/q2n-1
то
qn-1 < 1/√ε < qn
(5)
и, значит
Поэтому,
Ic(ε) <= 1/2∙I2(ε) + 1/2 + log2 an
Если принять, что 1/q2n < ε, то оценка упрощается:
Ic(ε) <= 1/2∙I2(ε) + 1/2
Таким образом видим, что теоретическая нижняя граница для Ic(ε) — объема данных, потребных для хранения вещественного числа а, оценена нами как сверху (формулы (6) и (6’)), так и снизу (формула (4)). Поэтому в случае больших объемов информации (Ic(ε) —> оо) представление числа в виде цепной дроби требует примерно вдвое меньшего количества бит, т. е. достигаемое сжатие — порядка 50 %.
3. Оценку (6) можно несколько улучшить. Для этого достаточно вместо (3) использовать более точную оценку приближения произвольного числа а подходящими дробями. Именно, ([1]. стр. 30) имеют место неравенства:
(7)
Поэтому если дробь pn/qn — первая из последовательности подходящих дробей, которая приближает число а с точностью ε, то, очевидно, имеют место неравенства:
и в тоже время
Из последнего неравенства вытекает
qn-1qn <= 1/ε (8)
Но
qn-1qn = qn-1(anqn-1 + qn-2) >= anq2n-1
Поэтому (8) превращается в неравенство
каковая оценка является просто уточнением первого из неравенств (5). Поэтому точно так же, как и раньше получаем уточненную оценку для Ic(ε):
Список литературы
[1] А. Я. Хинчин. Цепные дроби. Государственное изд-во физ. — мат. лит-ры. М., 1961.
Задача: Три рыбака ловили рыбу и после ловли заночевали на берегу. Двое рыбаков заснули, а третий решил уехать домой со своей частью улова. Он разделил рыбу на 3 равные части, но при этом одна рыбина оказалась лишней. Он швырнул ее в воду, забрал свою треть и ушел.
Среди ночи проснулся второй рыбак и тоже решил уехать. Не зная, что первый рыбак уже ушел, он тоже поделил всю рыбу на 3 равные части, одна рыбина снова оказалась лишней, он ее тоже выкинул и ушел.
То же произошло и с последним рыбаком: проснувшись, он тоже разделил оставшийся улов на 3 равные части, выкинул одну рыбину и ушел.
Вопрос: какое наименьшее количество рыб могло быть у рыбаков?
Решение П. А. М. Дирака: Рыб было (-2). После того, как первый рыбак выкинул одну рыбину в воду, их осталось (-2) — 1 = -3. Потом он ушел, унося (-1) рыбу. Рыб стало (-3) — (-1) = -2. Второй и третий рыбаки просто повторили поступок своего товарища.
Из книги "Физики продолжают шутить".
На самом деле решение Дирака, хоть и остроумно, но, строго говоря, неверно, и во всяком случае неполно. Приведем полное, "математическое" решение, т. е. найдем ВСЕ решения.
Решение.
Пусть в начале рыб было n0 (количество, после того, как уехало 0 рыбаков). Первый рыбак выбросил одну (лишнюю) рыбину (n0 — > n0 — 1), после чего количество рыбин стало делиться на 3, и взял 1/3 оставшегося улова, и после себя он оставил n1 = (2/3)∙(n0 — 1) рыбин. Аналогичным образом действовали и остальные рыбаки, так что после отъезда 2-го рыбака рыб осталось n2 = (2/3)∙(n1 — 1), а после отъезда 3-го — n3 = (2/3)∙(n2 — 1). Подставляя в последнее равенство выражения для n2 и n1, получаем:
В итоге получаем уравнение, требующее разрешения в целых числах:
8n0 — 27n3 = 38.
Для упрощения расчетов имеет смысл уменьшить входящие в уравнение числа перейдя к новым переменным n0 = n0 + k, n3 = n3. Если взять k = 5, то уравнение превратится в
27n3 — 8n0 = 2. (1)
Это уравнение имеет вид
ах — by = с (1')
т. е. является диофантовым уравнением, и нужно найти все решения данного уравнения. Как это сделать?
Взглянем на уравнение (1') с точки зрения теории сравнений. В самом деле, требуется найти такое число х, что ах отличается от заданного числа с на слагаемое, кратное Ь. Иными словами, разность ах — с делится на Ь, т. е. (ах — с) = ()(mod b) или
ах = c(mod Ь). (1")
То же самое можно выразить словами: "ах сравнимо с с по модулю b" или "ах принадлежит тому же классу вычетов по модулю Ь, что и с". Т. е. мы свели уравнение с двумя неизвестными (х и у) к уравнению с одним неизвестным, поскольку ясно,
