AOP_Tom2 (1021737), страница 110
Текст из файла (страница 110)
(24) (Аналогичное соотношение, 4.5.2 — (36), было получено при рассмотрении бинарных алгоритмов определения наибольшего общего делителя.) При любом основании Ь > 1 одна из функций, удовлетворяющих уравнению (24), имеет вид Ь"(х) !ойэ(1 + х) (см. упр. 19). Из дополнительного условия Е(1) = 1 следует, что Ь = 2. Таким образом, вполне обосновано предположение, что Р(х) = !8(1 + х) н что последовательность 5'„(х) сходится к этому пределу. Можно было бы предположить, например, что Е(1) = !8(з) ж 0.58496. Посмотрим, насколько близко Г„(1) к этому значению при малых и. Имссм Го(-') = 0.50000 и г!(2) = Н,(, = 2 — 2!п2»» 0.61371. »'э(2) = Нтуэ Нцз + Нз~4 — Нэ~э + Нэ7э — Нт~т + (см. табл.
3 приложения А). Обобщение на степенной ряд Н» Д2)т ДЗ)хг + Д4)хз Д5)хэ + .. (25) позволяет определить численное значение Е,(-.,') = 0.5765593276999140841882618721222705592452 — . (26) Получаем значение, близкое к 0.58496. Но совсем не очевидно, как получить хорошую оценку 5'„(-') при п = 3, т. е. при значении, меньшем, чем те значения, которые считаются действительно большими. Впервые распределения Г„(х) были исследованы К. Ф. Гауссом (С. Р.
Сапах), который начал решать эту проблему 5 февраля 1799 года. В его записях за 1800 год перечислены различные рекуррентные соотношения и приведена краткая таблица значений, включающая (неточные) приближения для Гт(-,') ж 0.5748. После завершения этих вычислений Гаусс записал: »Таш сошр!!сасш стас!ппг, и! пп11а эрез эпрегеээе тн!еасцг", т. е. "Они получаются такими сложными, что, кажется. нет никакой надежды".
Двенадцать лет спустя Гаусс написал письмо Лапласу, в Г„(х) =!8(1+у) +0(е д" е) для некоторой положительной константы А. Остаточный член 0(е "") был получен вскоре после этого Полем Леви (Рац! 1.4ту) (ВиГь Яос. МагЛ. с(е Л?апсе 57 (1929), 178-194) а. Но проблема, сформулированная Гауссом, которая заключается в поиске асимптотического поведения функции г'„(х) — !8(1+ х), фактически не была решена до 1974 года, пока Эдуард Вирсинг (Ейпагб %!гэ!п8) не опубликовал ее блестящий анализ (Асса Аг!сЛгпебса 24 (1974), 507 — 528]. Здесь мы исследуем самые простые аспекты приближения Вирсинга, поскольку его метод основан на использовании линейных операторов.
Если С вЂ” произвольная функция т, определенная на интервале 0 < х < 1, то определим функцию оС в виде (27) Таким образом, Я есть оператор, переводящий функцию нз одного состояния в другое. В частности, нз соотношения (23) получаем Г„е, (х) = Яг„(х); тогда (28) .Р'е = В" Ео. (В данном случае Р„означает функцию распределения, а мс числа Фибоначчн.) Заметим,. что Я- "линейный оператор", т. е. Я(сС) = с(ЯС) для всех постоянных с, и Б(Сз + Сз) = ЯСг + ВСг. Теперь, если для С существуют ограниченные первые производные, выражение (27) можно почленно проднфференцировать н показать, что ~ (Л+ )'С '1 + )' а>1 (29) так что функция ВС также имеет ограниченную первую производную.
(Почленное дифференцирование сходящегося ряда оправдано в том случае, когда равномерно сходится ряд, составленный из производных; см., например, К. Кпорр, ТЛеогу апс! Арр!!сабоп оГ 1пбпйе Бег!еэ (С!азйовс В!ас)ое, 1951), 147.) Изложение интересного доказательства Леви приведено в первом издании этОй книги. котором сформулировал эту проблему как таковую, дпя которой он не смог найти удовлетворяющего его решения. Он писал: еВ результате простых рассуждений я обнаружил, что г'„(х) = 1ой(1+ х)7'!о82 для бесконечного и. Но все дальнейшие попытки, предпринятые мною для оценки Г„(х) — 1об(1+х)/1о82 для очень больших, но конечных значений п, были безуспешны".
Гаусс так никогда и не опубликовал свои "очень простые рассуждения", поэтому не совсем ясно, нашел ли он строгое доказательство. (См. Сацзз'э )4ег)се, то!. 10', 552-556.! Прошло более ста лет, прежде чем такое доказательство было, наконец, опубликовано Р. О. Кузьминым в Агг! с)е! Сопйгевэо 1пгегпав!опа)е с!е! Масетабс! 6 (Во!обпа, 1928), 83-89, который показал, что Тогда Ео(х) = х, Уо(х) = 1+х и Д(х) есть постоянная функция, равная 1.
Покажем, что оператор П" переводит постоянную функцию в функцию, принимающую очень малые значения, поэтому при 0 < х < 1 значение (В'„'(х)~ должно быть очень малым. Покажем также, что функция Л„(х) сама по себе мала. Так как выполняется соотношение В„(0) = Л„(1) = О, согласно знакомой интерполяционной формуле (см. Упр. 4.6.4 — 15 для случая, когда хе — — О, х~ = х, хэ = 1) для произвольной функции с„(х), где 0 < ~„(х) < 1 при 0 < х < 1, функция /1„(х) имеет вид Л„(*) = — х(' ') я'„'(~„( )). (36) Таким образом, все сводится к попытке доказать, что У" порождает функции с малыми значениями, где à — линейный оператор, определяемый уравнением (31).
Заметим, что П вЂ” полохсительнмп оператор в том смысле, что если для всех х р(х) > О, то и Уфх) > О. Отсюда следует, что оператор (/ сохраняет порядок: если р~(х) < рз(х) для всех х, то (/сь(х) < (/срз(х) для всех х. Один из способов использования этого свойства заключается в поиске функции 1т, лля которой можно вычислить точное значение (/у и использовать константу, кратную этому значению функции, для определения верхней границы интересующей нас функции. Сначала рассмотрим такую функцию д, чтобы можно было легко вычислить значение Тд.
Если рассмотреть функции, определенные для всех х > О, а не только на отрезке [О .. 1], то можно исключить в (27) суммирование, заметив, что для непрерывной функции С выполняется соотношение ЯС(х+ 1) — ЯС(х) = С( — ) — 1пп С( — ) = С~ — ) — С(0). (37) Из того, что Т((1+ х) С') = (1+ х)(ЯС)', следует (см. Упр. 20) Если положить, что Тд(х) = 1/(1+ х), то находим, что соответствующее значение функции д(х) равно 1 + х — 1/(1+ х).
Положим 1с(х) = д'(х) = 1 + 1/(1 + х)~, так что (/~р(х) = -(Тд)'(х) = 1/(1+ х)э. Функция ~р и является искомой функцией, При таком выборе функции у получаем 2 < ~о(х)/Гр(х) = (1 + х)э + 1 < 5 при 0 < х < 1. Следовательно, ,-'д < ид <,-'д. Так как функции 1/ и 1с положительны, можно снова применить оператор П к этому неравенству и получить фу < 1ьП1Р < (/~у < ~1Сх < 1~у. После (и — 1)-го воздействия оператора 17 на неравенство получаем для конкретного значения ~о следующее выражение: 5 "1г < (/"у < 2 "~р. (39) Пусть Х(х) = /о(х) = 1 — постоаниаЯ фУнкциЯ.
Тогда длЯ 0 < х < 1 имеем ~1Х < Р < 2Х, откуда 15 "Х < 15 "у < 1П"р < П"Х < 1(7"д < 42 "х < э2 "Х. Из равенства (35) следует, что т(1п 2) 5 " < ( — 1)"В'„'(х) < — '(1п 2) 2 " для 0 < х < 1. Таким образом, нз (32) и (36) следует, что доказана следующая теорема.
Теорема ЪЧ. Прп и -+ оо распределение Р„(х) равно 18(1+ х) + 0(2 "). В действительности Р„(х) — !8(1+ х) лежит между,~ (-1)"+~5 "(!п(1+ х)) (!и 2/(1+ х)) и е(-1)в+'2 "(1п(1+ х)) (!и 2/(1+ х)) для 0 < х < 1. $ Если несколько изменить функцию !э, можно получить более сжатые границы (см. упр. 21). На самом деле Вирсинг пошел гораздо дальше, доказав в своей работе, что Р„(х) = 18(1+ х) + ( — Л)" Ф(х) + 0(х(1 — х)(Л вЂ” 0.031)"), (40) где Л = 0.30366 30028 98732 65859 74481 21901 55623 31109— = //3, 3, 2, 2, 3, 13, 1, 174, 1, 1, 1, 2, 2, 2, 1, 1, 1„2, 2, 1,...
//, (41) Это фундаментальная постоянная (к счастью, никак не связанная с более известными постоянными), где Ф вЂ” интересная функция, аналитическая в комплексной плоскости за исключением отрицательной вещественной оси от — 1 до — оо. Функция Вирсинга удовлетворяет соотношениям Ф(0) = Ф(1) = О, Ф'(0) < 0 н ЯФ = — ЛФ. Таким образом, с учетом (37) эта функция удовлетворяет тождеству Ф(2) — Ф(х + 1) = — Ф ( — ) . 1 1 (42) Далее Вирсннг показал, что и 11 Ф(--+ —,! = сЛ "!ойдо+ 0(1) при Дг-г оо, р!! где с — константа, а гь = Т(и, н) — число итераций алгоритма Евклида прн выполне- нии операций над целыми числами и > о > О. Полное решение проблемы Гаусса было найдено несколькими годами позже К.
И. Бабенко ]ДАН СССР 238 (1978), 1021-1024], который использовал мощный аппарат функционального анализа для доказательства следующей формулы: Р„(х) = !8(1+ х) + ~~~ Л" Фу(х) (44) э>2 для всех 0 < х < 1, п > 1. В этой формуле ]Лз] > ]Лэ] > ]Л4] > каждая из функций Ф„(х) — аналитическая функция на комплексной плоскости за исключени- ем ( — со.. — Ц.
Функция Фз — зто функция Вирсинга Ф, а Лэ = — Л, в то время как Лз 0.10088, Л4 - — 0.03550, Ль - 0.01284, Ле — 0.00472, Лг — 0.00175. Бабенко установил также дополнительные свойства собственных значений Л, до- казав, в частности, что они являются экспоненцивльно убывающими при / -э оа н что их сумма в (44) прн / > !г ограничена величиной (яз/6)]Ля]" гпйп(х, 1 — х). (Дополнительная информация содержится в работах Бабенко и Юрьева, опублико- ванных в ДАН СССР 240 (1978), 1273-1276, в работах Майера (Мауег) и Роепсторфа (Ноервгог!1), 7.
$сабэска! РЬугбсэ 47 (1987), 149 — 171; 50 (1988), 331 — 344; Д. Хеисли (П. Непэ!еу), Х ХнтЬег ТЬеогу 49 (1994), 142-182; а также в работах Доде (Ванде), Флажоле (Р!а)о!ет) и Валле (Уа!1ее), СотЬ!паголсе, РгобаЬ11!Гу впд Сотрпгтй 6 (1997), 397-433; Р)а)о1ец На!!4е, ТЬеогебса! Сотр. Ясб 194 (1998), 1 — 34.] Джон Хершбергер (ЗоЬп НегэЬЬегйег) вычислил 40-значное значение Л в (41). От непрерывного к дискретному. Выше были получены результаты, относящиеся к распределению вероятностей для цепных дробей в случае, когда Х— вещественное число, равномерно распределенное в интервале [О ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
