Популярно о науке

Previous Entry Share Next Entry
Решение менее типичной задачи
ahiin
Условие задачи здесь.

Первым задачу успешно решил уважаемый nabbla1, еще до того, как я опубликовал "точные" значения. Его объяснения я обильно цитирую ниже.

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

Под катом само решение (теория) и несколько вариантов реализации.


Цитируя nabbla1:
"Внутри суммы прибавим и отнимем 1/k2:


Первые два слагаемых приведём к общему знаменателю, получая:


Зная, что сумма по 1/k2 даёт π2/6 и вынося x за знак суммы, получим:



эта сумма сходится существенно лучше, поскольку "хвост" пропорционален 1/k2, т.е возьмём в 10 раз больше слагаемых - в 100 раз выше точность.

"Прикинуть" точность можно по x = 1, поскольку нетрудно показать, что результатом должна стать единица:


При суммировании сократятся все слагаемые, кроме самого первого (=1) и самого последнего, стремящегося к нулю. "

Процитированное решение практически дословно повторяет мое собственное, далекого 2002 года, когда мне эта задача попалась на всероссийской олимпиаде по прикладной математике.

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

Подобный фокус: выделить некую "главную часть", посчитать аналитически, а оклонения от нее уже считать численно — исключительно полезен и встречается повсеместно, особенно в приложениях. Например, таким способом прекрасно берутся численно некоторые интегралы и т.п.

Очевидно, что с рядом можно проделать тот же фокус (и так много раз).

Пока мне не надоело, я успел получить следующее выражение:



Здесь — дзета-функция Римана, которая определяется следующим образом:


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

Моя версия решения под спойлером.
[Код на C++]



На моей машине (Intel® Core™ i7-4720HQ) время счета составляет 8 микросекунд. До лимита в 10 секунд достаточно далеко, как видим.

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

Оно базируется на следующей идее: при достаточно большом k, члены рядов и становятся практически неразличимы.

Таким образом, если взять n достаточно большим, получим:


Идея вполне годная, авторская реализация под спойлером.
[Код на C++]



Для языкового разнообразия, привожу так же вариант уважаемого alexis_m.
[Код на Python]



  • 1
Может, в объяснение добавить первую строку и формулу: вычтем и прибавим 1/k²...

иначе не понятно, что за первые слагаемые.

Угу, это я копипастил невнимательно.

Здравствуйте! Ваша запись попала в топ-25 популярных записей LiveJournal северного региона. Подробнее о рейтинге читайте в Справке.

Если открыть, например, советскую книгу 1979-го года "Справочник по специальным функциям", там будут разложения в степенной ряд пси-функции (дигамма-функции), в том числе с использованием значений дзета-функции в точках.
В этой книге есть другие разложения да асимптотические формулы.
Безусловно и в интернете полно материалов.

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

Ну так тоже можно, не вопрос. Но, кмк, менее увлекательно)

  • 1
?

Log in

No account? Create an account