В чём ошибка вычисления бесконечно убывающей прогрессии с точностью до эпсилон?

Question

[Lexluter20]

#include <stdio.h>
#include <stdlib.h>

int main()
{
    double analit = 1.0, eps = 0.00000001, prog = 0.0;
    for(int i = 1; ; i++){
        prog += (double)1/(i*(i+1));
        if((analit - prog) <= eps){
            printf("%.10f\n%.10f\n%.10f\n%d\n", analit, prog, eps, i);
            return 0;
        }
    }

}

Нужно найти сумму бесконечно убывающей прогрессии с точностью до eps, не пойму в чём ошибка и почему prog > 1 и prog > analit - eps?
код выводит:
1.0000000000
1.0796516589
0.0000000100
6697830
А должен по идеи
1.0000000000
0.9999999999
0.0000000100
какое-то количество итераций

Comments

[Dmitrii]

Думаю вот эта ссылка наведет вас на мысли почему такое может произойти.
https://godbolt.org/z/d1z3bdsGe
Также для дебага выведите значение каждой итерации и сравните с ожидаемым значнием.

[Lexluter20]

вроде всё правильно решает, если поменять int на long long, но тогда в задаче ошибка cpu time, что можно сделать?

Answer 1

[Wataru]

Целочисленное переполнение при умножении i на i+1. Замените на, скажем prog += 1/((double)i*(i+1));, должно сработать.

При i порядка 50000 результат перемножения не влезает в int. А у вас там 6697830 операций. В результате используются отрицательные или слишком маленькие неправильные значения i для вычисления слагаемых после 50000, и результат вообще не правильный.

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

Comments

[Mercury13]

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

[Lexluter20]

Составить программу, которая вычисляет значение суммы ряда, стоящего в левой
части данного уравнения. Вычисляемое значение должно приближаться к
аналитическому решению, стоящему в правой части уравнения.
Определить наименьшее, при котором значение суммы ряда вычисляется с
абсолютной погрешностью не более 1×10^–8
такое вот условие задачи

[Lexluter20]

вроде всё правильно решает, если поменять int на long long, но тогда в задаче ошибка cpu time, что можно сделать?

[Rsa97]

Lexluter20, А какое ограничение по времени установлено? Ваша задача на PHP у меня на компьютере укладывается в 5 секунд. На C/C++ должно быть гораздо быстрее.

[Wataru]

Lexluter20, 6 миллионов итераций - это не так много. на с++ это 10-50мс на современном железе.

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

Answer 2

[Rsa97]

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

Comments

[Lexluter20]

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

[Rsa97]

Lexluter20, А смысл считать итерации, если уже есть аналитическое решение? Вычислительные методы используют, когда аналитические не справляются.

[Rsa97]

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

[wisgest]

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

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

Answer 3

[Mercury13]

У вас две ошибки.
1. Целочисленное переполнение в знаменателе в prog += (double)1/(i*(i+1));. Вычисляйте знаменатель в double, его длины более чем хватит.
2. Нельзя брать в счёт аналитический результат, надо высчитывать погрешность по имеющимся данным. Поскольку ещё и ряд сходится ХУдожественно — придётся помучиться, 1/(i(i+1)) < k·eps не катит (катит, если элемент ряда убывает экспоненциально, а у нас всего лишь квадратично).