Топорное решение, но. Считать две суммы: для 1/k(k+x) и для 1/k*k. Хвост первой суммы - искомая погрешность, хвост второй суммы больше хвоста первой суммы и через него можно оценивать погрешность. В итоге как-то так:
У меня самым тупым способом приближённая сумма первых ста миллионов членов 1/k^2 занимает 30 секунд (Питон). Это не учитывает накопления погрешностей и того, что сумма "хвоста" довольно велика (порядка 1/n, если хвост начинается с n-ного члена, так что считать надо далеко за миллиардный член).
Так что если цель именно "ряд просуммировать", то задача не выглядит разрешимой, если не использовать необычные компьютеры (ну или хотя бы видеокарты): многопоточность мне только эти первые сто миллионов и позволит сложить в отведённое время (причём для более простой задачи с заведомо неучтёнными накопленными ошибками).
Использование опыта человечества в вычислении специально придуманной и изученной "дигаммы-функции и постоянной Эйлера-Маскерони" выглядит более разумным, а также экономия на совместном вычислении значений в разных точках, но это же получается уже не просто "суммированием ряда".
Разумеется, этот ряд нельзя просуммировать в лоб в заданном виде, иначе не было бы смысла в задаче. Использование дигамма-функции будет по факту означать, что вы переложили суммирование ряда на автора математической библиотеки, это неинтересно.
Задача состоит в том, чтобы поиграться с рядом и привести его к виду, который будет допускать суммирование.
1. Первое что приходит в голову -- разложить бесконечный ряд в конечный с остаточным членом и суммировать, пока оценка ост. члена не будет меньше погрешности. Но я уже забыл всё это (по условиям гугл не мучаем) поэтому зафиксируем, что решение есть и пойдём рассуждать.
2. Второе, что приходит в голову -- заключить ряд в две функции (оценка сверху-снизу) и сводить обе, пока точность нас не удовлетворит. Это по сути тот же остаточный член, только с переизобретением велосипеда.
Сравнение с остатком ряда эйлера.son_0f_morningMarch 27 2018, 12:25:10 UTC
Без гугла не получилось.
Обозначения: остаток нашего ряда через G(k=k0, x), Остаток ряда эйлера через E(k==k1).
1. Тогда: E(k) < G(k, x) < E(k+x) <= E(k + [x+1])
2. Решение просуммируем k0 первых членов ряда, пока E(k0+2) не станет меньше погрешности => G(k+1, x) тоже меньше погрешности.
3. Улучшение оценка остаточного члена как среднего от E(k) и E(k+[x+1]) Мы можем считать остаточные члены эйлеровского ряда: E(k) и E(k + [x+1]) и считать что наш остаток G(k, x) -- лежит между ними. Как-то пропорционально тому, к какому краю он ближе. Я бы предложил считать пропорционально квадрату, но могу ошибаться.
4. Код double calc_summ(double x, double delta) { double eiler_real = pi * pi /6; int extra_iterations = trunc(x + 1); double eiler_find = 0; double summ_find = 0;
for (i = 1; i <= extra_iterations; i++) eiler += 1/(i * i);
while((eiler - eiler_find) > delta) { summ_find += 1 / (i * (i + x)); eiler_find += 1 / ((i + extra_iterations) * (i + extra_iterations)) }
Re: Стартовые дефиниции ahiinMarch 27 2018, 15:08:18 UTC
Аналитические преобразования понадобятся, да.
А вот игнорировать погрешность как раз не надо, в этом суть задачи. В заданной форме этот ряд тупо не суммируется с требуемой точностью, вообще (даже на 80-разрядном флоате). Надо извернуться.
Я же советовал уже попробовать реально посуммировать и посмотреть, что получается.
Re: Стартовые дефиниции son_0f_morningMarch 27 2018, 15:15:56 UTC
Понятно. Ну есть решение в лоб -- с увеличивающими точность (квадрат точности ЕМНИП) преобразования при использовании двух float / double вместо одного. Но речь явно не про них, а про "подумать".
=\sum_{k=1}^{\infty}\frac{1}{k(k+x)})
Comments 33
const = pi*pi/6;
for(x = 0; x < 1.1; x+=0.1)
{
sum1 = 0;
sum2 = 0;
k = 1;
do
{
sum1 += 1/(k*(k+x));
sum2 += 1/(k*k);
k++;
} while(const-sum2 > 0.0000000001);
printf(" %f ",sum1);
}
Reply
Reply
Сейчас влом проверять, но в большинстве случаев этого достаточно
Reply
Так что если цель именно "ряд просуммировать", то задача не выглядит разрешимой, если не использовать необычные компьютеры (ну или хотя бы видеокарты): многопоточность мне только эти первые сто миллионов и позволит сложить в отведённое время (причём для более простой задачи с заведомо неучтёнными накопленными ошибками).
Использование опыта человечества в вычислении специально придуманной и изученной "дигаммы-функции и постоянной Эйлера-Маскерони" выглядит более разумным, а также экономия на совместном вычислении значений в разных точках, но это же получается уже не просто "суммированием ряда".
Чего я не понял про ограничения?
Reply
Использование дигамма-функции будет по факту означать, что вы переложили суммирование ряда на автора математической библиотеки, это неинтересно.
Задача состоит в том, чтобы поиграться с рядом и привести его к виду, который будет допускать суммирование.
Reply
Погрешностюь IEEE 754 (чисел двойной точности) пренебрежём.
1. Первое что приходит в голову -- разложить бесконечный ряд в конечный с остаточным членом и суммировать, пока оценка ост. члена не будет меньше погрешности. Но я уже забыл всё это (по условиям гугл не мучаем) поэтому зафиксируем, что решение есть и пойдём рассуждать.
2. Второе, что приходит в голову -- заключить ряд в две функции (оценка сверху-снизу) и сводить обе, пока точность нас не удовлетворит. Это по сути тот же остаточный член, только с переизобретением велосипеда.
Второй частью и займёмся, когда появятся идеи.
ПС
Спасибо за разминку мозгов.
Reply
Обозначения:
остаток нашего ряда через G(k=k0, x),
Остаток ряда эйлера через E(k==k1).
1.
Тогда:
E(k) < G(k, x) < E(k+x) <= E(k + [x+1])
2.
Решение
просуммируем k0 первых членов ряда, пока
E(k0+2) не станет меньше погрешности => G(k+1, x) тоже меньше погрешности.
3. Улучшение оценка остаточного члена как среднего от E(k) и E(k+[x+1])
Мы можем считать остаточные члены эйлеровского ряда:
E(k) и E(k + [x+1])
и считать что наш остаток G(k, x) -- лежит между ними. Как-то пропорционально тому, к какому краю он ближе.
Я бы предложил считать пропорционально квадрату, но могу ошибаться.
4. Код
double calc_summ(double x, double delta)
{
double eiler_real = pi * pi /6;
int extra_iterations = trunc(x + 1);
double eiler_find = 0;
double summ_find = 0;
for (i = 1; i <= extra_iterations; i++)
eiler += 1/(i * i);
while((eiler - eiler_find) > delta) {
summ_find += 1 / (i * (i + x));
eiler_find += 1 / ((i + extra_iterations) * (i + extra_iterations))
}
return summ_find;
}
Reply
А вот игнорировать погрешность как раз не надо, в этом суть задачи.
В заданной форме этот ряд тупо не суммируется с требуемой точностью, вообще (даже на 80-разрядном флоате). Надо извернуться.
Я же советовал уже попробовать реально посуммировать и посмотреть, что получается.
Reply
Ну есть решение в лоб -- с увеличивающими точность (квадрат точности ЕМНИП) преобразования при использовании двух float / double вместо одного.
Но речь явно не про них, а про "подумать".
Сейчас посчитаю "в лоб" и пойду думать хД
Reply
( ... )
Reply
Reply
Leave a comment