Оценка суммы сверху интегралом

Если умеешь оценить Σ f(k) через ∫ f(x)dx и понимаешь, почему площадь ограничивает лесенку, - листай до «Теперь сам».

Как думаешь, какого порядка эта сумма

1² + 2² + 3² + ... + n²

Приёма «сложить задом наперёд», как у 1 + 2 + ... + n, тут нет: квадраты так не парятся. Точная формула существует (n(n+1)(2n+1)/6), но её надо помнить. А порядок роста можно получить в одну строку, не вспоминая формулу, - если догадаться, что сумма квадратов близка к площади под кривой x².

На что это похоже

Нарисуй сумму как гистограмму: над отрезком [k, k+1] стоит столбик высотой f(k) и шириной 1, его площадь равна как раз f(k). Вся сумма - это суммарная площадь столбиков, то есть лесенка. Рядом проведи гладкую кривую f(x). Лесенка идёт вплотную к кривой - то чуть выше, то чуть ниже, - поэтому площадь под кривой (это и есть интеграл) зажимает сумму сверху и снизу.

Механизм: почему площадь ограничивает сумму

Интеграл ∫ₐᵇ f(x)dx - это площадь под кривой f от a до b; для степеней её берут по правилу «степень поднять на единицу и поделить на новую степень»: площадь под xᵏ от 0 до n равна n^(k+1)/(k+1). Правило годится для любой степени, кроме k = -1: там формула упёрлась бы в деление на ноль, а у 1/x площадь особая - это ln n (из прошлого урока).

Пусть f растёт. Столбик высотой f(k) над [k, k+1] не выше, чем площадь под растущей кривой на этом же отрезке (кривая там ещё выше f(k)). Сложив столбики, получаем оценку сверху:

Σₖ₌ₘⁿ f(k) ≤ ∫ₘ^(n+1) f(x) dx

Снизу столбик не ниже площади на предыдущем отрезке, откуда парная нижняя оценка ∫_(m-1)^n f(x)dx ≤ Σ. Для убывающей f картинка та же, но неравенства меняются местами. Итог один: сумма и интеграл одного порядка, а интеграл считается по готовому правилу.

Правило

Для монотонной f сумма Σₖ₌ₘⁿ f(k) того же порядка, что интеграл ∫ f(x)dx. Верхняя оценка растущей f: Σ ≤ ∫ₘ^(n+1) f(x)dx. Площадь под xᵏ до n - это n^(k+1)/(k+1), поэтому порядок суммы степеней виден сразу.

Разбор: метод воспроизводит уже известное

Проверим метод на суммах, ответ которых мы знаем.

• Σ k (степень 1): интеграл ∫x dx до n это n²/2. Порядок Θ(n²) - ровно как даёт формула n(n+1)/2.
• Σ 1/k (гармонический): правило степеней тут даёт осечку (1/x = x^(-1), k = -1), но площадь под 1/x мы уже знаем - это ln n. Порядок Θ(log n) - ровно как в прошлом уроке.
• Σ k²: интеграл ∫x² dx до n это n³/3. Значит 1² + ... + n² = Θ(n³).

Три известных ответа метод даёт одинаково, не требуя ни парного приёма, ни запоминания формул. За это его и любят: одна кривая - один порядок.

Работает он и там, где парного приёма нет вовсе. Сумму логарифмов log 1 + log 2 + ... + log n руками не свернёшь, но логарифм превращает произведение в сумму (log(a·b) = log a + log b), поэтому она равна log(1·2·...·n) = log(n!). Площадь под кривой log x до n растёт как n·log n, значит Σ log k = Θ(n·log n) - то есть log(n!) = Θ(n·log n), хотя сам n! (факториал из главы про асимптотику) растёт быстрее любой экспоненты. Кривая нашлась - порядок получен.

Разбор: интеграл даёт порядок, а не точное значение

∫x² dx до n дало n³/3, а точная сумма квадратов - n(n+1)(2n+1)/6. Раскрой скобки: старший член там 2n³/6 = n³/3 - тот же самый. Различаются они младшими слагаемыми и на конечных n немного расходятся: при n = 10 точная сумма 385, а n³/3 ≈ 333. Для Θ этого достаточно - порядок n³ один и тот же; но подставлять n³/3 вместо точного числа нельзя, интеграл оценивает класс, а не считает сумму.

Что ломается без этого

Метод работает только для МОНОТОННОЙ f - растущей или убывающей на всём отрезке. Для функции, которая то растёт, то падает, столбики не жмутся к кривой с одной стороны, и оценка ломается. Вторая ошибка - перепутать направление неравенства у убывающей f: у неё верхнюю оценку даёт интеграл от m-1, а не от m. И третья - принять n³/3 за точную сумму: это оценка порядка, у точной формулы другой хвост.

Зачем это в работе

Интеграл - универсальная отмычка к суммам в анализе цикла: не нужно помнить формулу для суммы квадратов, логарифмов или k·log k - достаточно взять площадь под соответствующей кривой. Встретив в оценке цикла сумму, которую не свернуть парным приёмом, ты берёшь интеграл и получаешь порядок за одну строку. Это и есть цель главы: свернуть ряд из анализа и оценить его сверху.

Теперь сам

Оцени интегралом порядок суммы 1³ + 2³ + ... + n³.