Главная > Конкретная математика. Основание информатики
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

9.6 ЗАВЕРШАЮЩЕЕ СУММИРОВАНИЕ

Под конец этой книги настало время просуммировать все и подвести итоги. Мы рассмотрим несколько интересных и важных примеров и применим к ним формулу Эйлера.

Сумма 1: слишком простая

Сначала рассмотрим, хотя и интересный, но не важный пример, а именно сумму, которую мы уже умеем вычислять. Посмотрим, что скажет нам формула Эйлера, если применить ее к „телескопической" сумме

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

Для начала можно разложить функцию на простейшие дроби,

так как это упрощает интегрирование и дифференцирование. Имеем в общем случае

Далее,

Подставляя эти выражения в формулу суммирования (9.67), получаем

где

Например, для правая часть равна

Что-то тут не так; это определенно не похоже на правильный ответ Но все же пойдем дальше и посмотрим, что мы получили. Мы знаем, как расписать слагаемые правой части через

отрицательные степени до, скажем,

Следовательно, сумма членов в правой части аппроксимации дает

Коэффициенты при благополучно сократились, как им и положено.

Если с этим миром все в порядке, то мы должны бы суметь доказать, что асимптотически мало, может быть, и в результате мы получим аппроксимацию нашей суммы. Но доказать это, по всей видимости, невозможно, поскольку, как мы знаем, постоянное слагаемое равно 1, а не (что есть примерно 0.9978). Таким образом, в действительности равно — но формула суммирования Эйлера ничего не говорит нам об этом.

Иными словами, мы потерпели неудачу.

Попытаемся исправить положение. Заметим, что постоянное слагаемое в аппроксимации, по мере роста следует схеме:

Может быть, мы покажем, что этот ряд сходится к 1, когда число слагаемых становится бесконечным? Но нет; числа Бернулли возрастают очень быстро. Например, следовательно, будет гораздо больше, чем Мы окончательно зашли в тупик.

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

Интеграл будет существовать, если при и это несомненно так для Далее, имеем

Итак, мы доказали, с помощью формулы Эйлера, что

для некоторой константы С. Мы не знаем, что это за константа — для ее нахождения нужны другие методы, — однако формула суммирования Эйлера позволила нам установить, что константа существует.

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

и мы приходим к формуле

для каких-то констант Мы знаем, что в нашем случае все константы с оказываются нулевыми; тем не менее, докажем это, хотя бы для того, чтобы восстановить репутацию (если не свою, то формулы Эйлера). Член вносит в слагаемое вклад члена составляет а вклад члена равен Следовательно,

Совершенно ясно, что это нуль для Мы доказали, что

Формулы (9.82) недостаточно, чтобы доказать, что сумма точно равна она может равняться или чему-либо в этом роде. Но формула суммирования Эйлера все же дала нам точность для произвольно большого даже несмотря на то что мы не оценивали явно ни одного остаточного члена.

Снова сумма 1: выводы и обобщения

Прежде чем разделаться с нашим тренировочным примером, попробуем вновь взглянуть на сделанное в более широком аспекте. Мы начинали с суммы

и, воспользовавшись формулой суммирования Эйлера, получили

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

(А именно, у нас было Это означает, что для всех достаточно больших остаточные члены имеют маленький хвост,

Следовательно, мы можем заключить, что существует константа С, такая, что

(Заметьте, что С счастливым образом вобрала в себя неприятные члены

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

Предположим теперь, что для Мы доказали, что отсюда следует простая оценка (9.80) остаточного члена:

где лежит между 0 и 1. Но на самом деле нас не интересует оценка, содержащая мы, в конце концов, избавились от путем введения константы С. Что нам действительно нужно, так это оценка вида

при она позволила бы вывести из (9.85) соотношение

и здесь остаточный член будет действительно лежать между 0 и первым отброшенным членом.

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

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

Сумма 2: гармония гармонических чисел

Теперь, научившись столь многому на тривиальном (но надежном) примере, мы легко справимся с нетривиальным. Используем формулу суммирования Эйлера для вывода аппроксимации чисел уже объявленной ранее.

В этом случае Вычисляя сумму 1, мы уже изучили интеграл и производные как и ранее, при Поэтому можно сразу же использовать формулу (9.85):

для некоторой константы С. Сумма слева есть а не однако оказывается удобнее работать с и позднее добавить чем возиться с в правой части. Тогда перейдет в Обозначим константу буквой у вместо С, поскольку константа Эйлера у определяется ровно как

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

где некоторая дробь между 0 и 1. Первые члены этой общей формулы приведены в табл. 491. Например, для будем иметь

Это уравнение, оказывается, дает неплохое приближение к у уже при

где лежит между Если взять то можно вычислить значение у с 1271 верной десятичной цифрой, начинающееся так:

Однако константа Эйлера встречается и в других формулах, что позволяет вычислять ее еще эффективнее [290].

Сумма 3: аппроксимация Стирлинга

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

где а есть определенная константа, „константа Стирлинга", и . (В данном случае не положительна, а отрицательна; но мы можем по-прежнему утверждать, что остаточный член подчинен первому отброшенному, поскольку мы могли бы начать с функции вместо Добавление к обеим частям приводит при к соотношению

Аппроксимацию из табл. 491 можно теперь получить, взяв от обеих частей. (Значение ест оказывается равным но доказательство этого мы пока отложим. В действительности сам Стирлинг не знал точного значения константы еще несколько лет после того, как де Муавр [99] доказал ее существование.)

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

аппроксимации имеется некоторый порог точности, переступить который мешает что-то вроде принципа неопределенности.

В соотношении (5.83) из гл. 5 мы обобщили факториалы на произвольные вещественные числа а с помощью определения, предложенного Эйлером:

Пусть а — большое число; тогда

и для оценки этой суммы можно использовать формулу суммирования Эйлера с

(Здесь мы воспользовались (9.67) для затем добавили а к обеим частям.) Если вычесть эту аппроксимацию суммы из аппроксимации Стирлинга для добавить и перейти к пределу при то получим

ибо — оси остальные, не показанные здесь члены, стремятся к нулю. Таким образом, аппроксимация Стирлинга для обобщенных факториалов (и для гамма-функции выглядит точно так же, как и для обычных факториалов.

Сумма 4: колоколообразные слагаемые

Обратимся теперь к сумме совершенно иного характера:

Это бесконечная в обе стороны сумма, члены которой достигают максимального значения при Мы назвали сумму поскольку это степенной ряд, содержащий величину в степени где многочлен степени 2; такие степенные ряды традиционно называются „тета-функциями“. Если , то

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

При больших значениях график просто растянется по горизонтали в раз.

Чтобы оценить с помощью формулы суммирования Эйлера, можно взять (Если бесконечности страшат вас, то возьмите а затем перейдите к пределу при Интеграл от можно вычислить при помощи замены х на

Значение хорошо известно, но мы пока обозначим его буквой С с тем, чтобы вернуться к нему после того, как закончим разбирательство с формулой суммирования Эйлера.

Следующее, что нам нужно знать, — это последовательность производных для их нахождения удобно будет воспользоваться заменой

Тогда правило замены переменной из дифференциального исчисления говорит нам, что

а это означает просто

По индукции получаем

Так, вычислив получим

Чтобы было легче увидеть, что произойдет в дальнейшем, лучше работать с более простой функцией

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

Это доказывается по индукции.

Экспонента стремится к нулю при гораздо быстрее, чем стремится к бесконечности, поэтому мы делаем вывод, что

для всех к 0. Следовательно, все члены в

исчезают и остается лишь слагаемое с и остаточный член:

Выписанная О-оценка остаточного члена вытекает из того, что ограничено и интеграл существует, если Р — многочлен. (Константа в этом О зависит от .)

Мы доказали, что для сколь угодно большого М; разность между „экспоненциально мала“ Займемся теперь определением константы С, играющей столь важную роль в значении

Можно очень просто определить С, найдя нужный интеграл в таблице; но мы предпочтем самостоятельно получить это значение, чтобы в будущем суметь подсчитать также и те интегралы,

которых нет в таблицах. Для вычисления С достаточно элементарного анализа, если только мы догадаемся рассмотреть двойной интеграл

Переход к полярным координатам дает

Следовательно, Тот факт, что есть уравнение окружности длины в какой-то мере объясняет, откуда здесь берется

Можно вычислить С иначе, выполнив замену х на на

Этот интеграл равен поскольку, в соответствии с (5.84), Следовательно, мы показали, что

Итак, наша окончательная формула такова:

Константа в О зависит от М; именно поэтому мы говорим о „фиксированном" М.

Если, например, то бесконечная сумма равняется 2.506628288; это уже превосходное приближение к несмотря на малость Значение совпадает с до 427-й десятичной цифры! В упр. 59 при помощи более совершенных методов получается быстро сходящийся ряд для оказывается, что

Сумма 5: завершающий удар

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

главы (и из всей книги), так что это вполне уместный пример в завершение нашего исследования конкретной математики.

Последняя задача выглядит абсурдно простой: мы попытаемся найти асимптотическое значение суммы

с помощью формулы суммирования Эйлера.

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

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

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

Теперь мы собираемся применить трехшаговую процедуру, подразумеваемую приемом замены хвоста. Именно, мы хотим записать

с тем, чтобы получить оценку

Попробуем поэтому оценить в области малых Можно было бы использовать аппроксимацию Стирлинга, как она представлена в табл. 491, но проще работать с ее логарифмическим эквивалентом в виде (9.91):

Хотелось бы преобразовать это в простую и красивую О-оценку.

Метод замены хвоста позволяет использовать оценки, справедливые только для к, из „доминирующего множества Но как нам выбрать Мы должны взять достаточно малым, чтобы можно было получить хорошую оценку; так, например, не стоит допускать приближения к к в этом случае член в (9.95) „взрывается! С другой стороны, должно быть достаточно большим, чтобы остаточные члены (члены с к были пренебрежимо малы в сравнении со всей суммой. Обычно для определения подходящего множества требуется действовать методом проб и ошибок; в данной задаче вычисления, которые мы вскоре проделаем, покажут, что разумно определить множества следующим образом:

Здесь — небольшая положительная константа, значение которой мы выберем позже, после того как лучше изучим местность. (Наши О-оценки будут зависеть от е.) Уравнение (9.95) можно теперь сократить до

(Мы вынесли основную часть логарифмов, записав

в результате чего многие члены, содержащие сократились.)

Теперь нужно разложить члены асимптотически, так, чтобы погрешность стремилась к нулю при Мы умножаем на значит, требуется разложить логарифм до членов с учетом предположения

Умножение на дает

плюс другие члены, которые поглощаются слагаемым Таким образом, (9.97) превращается в

Взяв экспоненту, получим

Это и есть наша аппроксимация с

Заметьте, что к входит в очень простым образом. Это явная удача, ведь суммировать мы будем по k.

Трюк замены хвоста говорит нам, что приближенно равна если мы грамотно выполнили аппроксимацию. Вычислим поэтому

(И снова удача: можно использовать сумму из предыдущего примера.) Это радует, поскольку, как нам известно, исходная сумма равна в действительности

Похоже, таким образом, что ест как и было объявлено.

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

Хорошо; эта величина асимптотически меньше предыдущей суммы, если

Теперь следует проверить хвосты. Имеем

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

оценку, поскольку главная наша цель — найти значение константы а.) Точно так же другой хвост

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

Итак, мы успешно применили трюк замены хвоста и доказали оценку

если

Можем выбрать и сделать вывод, что

1
Оглавление
email@scask.ru