Ниже — несколько практических подходов к вычислению суммы $S(n)=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$ (гармонического числа $H_n$) с кратким анализом сильных и слабых сторон в зависимости от требуемой точности.
1) Прямая сумма (последовательное суммирование)
- Формула: $H_n={\sum }_{k=1}^n\frac{1}{k}$.
- Плюсы: простая реализация, точна в математическом смысле (если выполняется в точной арифметике или в высокоточной вещественной).
- Минусы: затратно по времени для огромных $n$ (O(n)); при машинной арифметике на больших $n$ накапливаются ошибки округления. Можно уменьшить погрешность, суммируя в порядке от меньших к большим или используя попарное (pairwise) суммирование или Kahan: эти схемы снижают накопление погрешности.
2) Суммирование с коррекцией ошибок (Kahan, pairwise, divide-and-conquer)
- Идея: применять алгоритмы компенсирующего суммирования или разбивать сумму рекурсивно (pairwise).
- Плюсы: почти та же сложность O(n), но значительно лучше числовая стабильность при машинной арифметике; простой способ получить машинно-округлённую точность.
- Минусы: всё ещё O(n), не подходит если $n$ экстремально велико (например >10^12) и нужна асимптотика.
3) Асимптотическое разложение (Эйлер–Маклорен)
- Формула (несколько первых членов):
$$H_n=\ln n+\gamma +\frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\cdots ,$$ где $\gamma$ — константа Эйлера–Маскерони.
- Плюсы: для больших $n$ даёт отличную точность с несколькими членами; очень быстро (O(1) по времени за фиксированное число членов).
- Минусы: для малого и среднего $n$ разложение плохо сходится; для заданной точности надо знать, сколько членов брать (следующий невключённый член даёт порядок остатка, который оценивается через числа Бернулли). Кроме того, для очень высокой точности требуется вычисление больших чисел Бернулли или специальных коэффициентов.
4) Комбинация «частичная точная сумма + асимптотический хвост»
- Идея: посчитать точно (или с контролируемой точностью) первые $m$ членов, а остаток ${\sum }_{k=m+1}^{n}1/k$ аппроксимировать Эйлер–Маклореном или интегральной оценкой:
$$H_n=H_m+\sum _{k=m+1}^n\frac{1}{k}\approx H_m+\ln \frac{n}{m}+\frac{1}{2}\left(\frac{1}{n}-\frac{1}{m}\right)-\frac{1}{12}\left(\frac{1}{n^2}-\frac{1}{m^2}\right)+\dots$$ - Плюсы: гибко балансирует вычислительную сложность и точность; достаточно суммировать относительно небольшое $m$ и получить высокую точность для огромных $n$.
- Минусы: требуется выбирать $m$ в зависимости от требуемой точности; реализация чуть сложнее.
5) Специализированные функции (дигамма)
- Воспользоваться соотношением с дигамма-функцией:
$$H_n=\psi (n+1)+\gamma ,$$ где $\psi$ — дига́мма ($\psi ={\Gamma }^{\prime }/\Gamma$).
- Плюсы: современные математические библиотеки (MPFR, Boost, scipy, …) дают высокоточную и быструю реализацию; удобно для очень больших $n$ и для произвольной точности.
- Минусы: зависит от качества реализации специальной функции в библиотеке; для учебных/простых сред может отсутствовать.
6) Оценки через интегралы (низкая точность, грубые границы)
- Неравенства:
$$\ln (n+1)\le H_n\le 1+\ln n.$$ - Плюсы: очень простые, дают быстрые грубые оценки.
- Минусы: точность низкая (порядок 1), хуже для задач, требующих высокой точности.
7) Высокая точность с помощью деления и точной рациональной арифметики (binary splitting / exact rational)
- Идея: вычислить сумму в точной рациональной форме с последующим переводом в плавающую точку нужной точности.
- Плюсы: позволяет получить абсолютно точный результат (ограничивается только временем/памятью); хорошо масштабируется для многозначной точности с алгоритмами быстрого умножения.
- Минусы: дорого по памяти и времени для очень больших $n$; сложнее реализовать.
Рекомендации в зависимости от требуемой точности:
- Низкая точность (~1e-6 — 1e-9) и умеренные $n$: прямая сумма с Kahan или pairwise.
- Очень большие $n$ и средняя/высокая точность: суммировать первые $m$ членов и аппроксимировать хвост через Эйлер–Маклорен (или напрямую использовать формулу с несколькими членами); подобрать $m$ так, чтобы остаток оценивался меньше требуемой погрешности.
- Очень высокая точность (многозначная): использовать реализацию дигаммы в библиотеках произвольной точности или exact-rational + binary-splitting.
- Только грубая оценка: использовать интегральные неравенства.
Если нужен, могу дать конкретные пороги (например, сколько членов асимптотики нужно, чтобы получить ошибку <10^{-p} при заданном $n$) или код/алгоритм для выбранного подхода.