Точная оценка 1/1 + 1/2 + ... 1 / n ряд

Question

Мне нужно оценить сумму строки: 1/1 + 1/2 + 1/3 + ... + 1 / n. Учитывая, что в C ++ оценки не являются полностью точными, порядок суммирования играет важную роль. Выражение 1 / n + 1 / (n-1) + ... + 1/2 + 1/1 дает более точный результат. Поэтому мне нужно выяснить порядок суммирования, который обеспечивает максимальную точность. Я даже не знаю, с чего начать. Предпочтительный язык реализации - C ++. Извините за мой английский, если есть ошибки.

Answer 1

Для больших n лучше использовать асимптотические формулы, например, для http://en.wikipedia.org/wiki/Harmonic_number;

Другой способ - использовать преобразование exp-log. В основном:

H_n = 1 + 1/2 + 1/3 + ... + 1 / n = log (exp (1 + 1/2 + 1/3 + ... + 1 / n)) = log (exp (1) * exp (1/2) * exp (1/3) * ... * exp (1 / n)).

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

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

Answer 2

Я даже не знаю, с чего начать.

Здесь: Что каждый ученый должен знать об арифметике с плавающей точкой

Answer 3

Причиной отсутствия точности является точность типов float, double и long double. Они хранят только так много "десятичных" мест. Таким образом, добавление очень маленького значения к большому значению не имеет никакого эффекта, маленький термин «теряется» в большем.

Серия, которую вы суммируете, имеет "длинный хвост" в том смысле, что маленькие термины должны составлять большой вклад. Но если вы суммируете в порядке убывания, то через некоторое время каждый новый маленький член не будет иметь никакого эффекта (даже до этого большинство его десятичных разрядов будут отброшены). Как только вы дойдете до этой точки, вы можете добавить еще миллиард терминов, и если вы сделаете их по одному, это все равно не даст никакого эффекта.

Я думаю, что суммирование в порядке возрастания должно дать наилучшую точность для такого рода рядов, хотя возможно, что есть некоторые странные угловые случаи, когда ошибки из-за округления до степеней (1/2) могут привести к сближению Ответьте за некоторые дополнительные заказы, чем другие. Вы, вероятно, не можете предсказать это, хотя.

Answer 4

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

Посмотрите на проблему следующим образом: у вас есть N суммирования, независимо от порядка, и вы хотите иметь наименьшую общую ошибку. Таким образом, вы должны быть в состоянии получить наименьшую общую ошибку, минимизировав ошибку каждого суммирования - и вы минимизируете ошибку в суммировании, добавляя значения как можно ближе друг к другу, насколько это возможно. Я считаю, что следуя этой цепочке логики, вы получите двоичное дерево частичных сумм:

Sum[0,i] = value[i]

Sum[1,i/2] = Sum[0,i] + Sum[0,i+1]

Sum[j+1,i/2] = Sum[j,i] + Sum[j,i+1]

и так далее, пока не дойдете до одного ответа.

Конечно, когда N не является степенью двойки, на каждом этапе у вас останутся остатки, которые нужно перенести в суммирование на следующем этапе.

(Поля StackOverflow, конечно, слишком малы, чтобы включать в себя доказательство того, что это оптимально. Отчасти потому, что я не нашел времени, чтобы доказать это. Но он работает для любого N, даже большого, как все дополнения складывают значения почти одинаковой величины. Ну, все, кроме log (N) из них в худшем случае не степени 2, и это ничтожно мало по сравнению с N.)

Answer 5

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic Вы можете найти библиотеки с готовой к использованию реализацией для C / C ++.

Например http://www.apfloat.org/apfloat/

Answer 6

Если вы не используете какое-либо точное представление в закрытой форме, упорядоченное суммирование от малого к большому, вероятно, будет наиболее точным простым решением (мне не ясно, почему log-exp поможет - это ловкий трюк, но вы Насколько я могу судить, ничего здесь не выиграешь).

Вы можете еще больше повысить точность, осознав, что через некоторое время сумма будет «квантована»: эффективно, если у вас есть 2 цифры точности, добавление от 1,3 до 41 приводит к 42, а не к 42,3, но вы достигаете почти точности удваивая, поддерживая термин «ошибка». Это называется Суммирование Кахана . Вы бы вычислили термин ошибки (42-41-1.3 == -0.3) и исправили его в следующем добавлении, добавив 0,3 к следующему члену, прежде чем добавить его снова.

Суммирование по Кахану в дополнение к заказу от малого к большому должно быть настолько точным, насколько вам когда-либо понадобится. Я серьезно сомневаюсь, что вам когда-нибудь понадобится что-то лучшее для гармонического ряда - в конце концов, даже после 2 ^ 45 итераций (безумно много) вы все равно будете иметь дело только с числами, которые по крайней мере 1/2 ^ 45 велики, и сумма порядка 45 (<2 ^ 6) для разности порядка 51 степеней двух, то есть даже представляемая в переменной двойной точности, если вы добавите в «неправильном» порядке. </p>

Если вы переходите от малого к большому и используете суммирование по Кахану, солнце, вероятно, погаснет, прежде чем сегодняшние процессоры достигнут процента ошибок - и вы столкнетесь с другими сложными проблемами точности только из-за отдельной ошибки в терминах эта шкала в любом случае сначала (если число порядка 2 ^ 53 или больше не может быть точно представлено как двойное число вообще).

Answer 7

Поскольку все ваши числа являются рациональными, самым простым (а также, возможно, самым быстрым, так как ему придется выполнять меньше операций с плавающей запятой), было бы сделать вычисления с рациональными числами (кортежами из 2 целых чисел p, q), а затем сделать только одно деление с плавающей запятой в конце.

обновление , чтобы эффективно использовать эту технику, вам нужно использовать bigints для p & q, так как они растут довольно быстро ...

Быстрый прототип на Лиспе со встроенными рациональными значениями показывает:

(defun sum_harmonic (n acc)
  (if (= n 0) acc (sum_harmonic (- n 1) (+ acc (/ 1 n)))))

(sum_harmonic 10 0)
7381/2520
[2.9289682]

(sum_harmonic 100 0)
14466636279520351160221518043104131447711/278881500918849908658135235741249214272
[5.1873775]

(sum_harmonic 1000 0)

53362913282294785045591045624042980409652472280384260097101349248456268889497101
75750609790198503569140908873155046809837844217211788500946430234432656602250210
02784256328520814055449412104425101426727702947747127089179639677796104532246924
26866468888281582071984897105110796873249319155529397017508931564519976085734473
01418328401172441228064907430770373668317005580029365923508858936023528585280816
0759574737836655413175508131522517/712886527466509305316638415571427292066835886
18858930404520019911543240875811114994764441519138715869117178170195752565129802
64067621009251465871004305131072686268143200196609974862745937188343705015434452
52373974529896314567498212823695623282379401106880926231770886197954079124775455
80493264757378299233527517967352480424636380511370343312147817468508784534856780
21888075373249921995672056932029099390891687487672697950931603520000
[7.485471]

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

Answer 8

Я не уверен, что порядок суммирования играет важную роль, я не слышал этого раньше. Я предполагаю, что вы хотите сделать это в арифметике с плавающей запятой, поэтому первое, что нужно, - это думать более линейно (1.0 / 1.0 + 1.0 / 2.0 + 1.0 / 3.0) - иначе компилятор выполнит целочисленное деление

для определения порядка вычисления, может быть, для цикла или скобок?

, например

float f = 0.0;
for (int i=n; i>0; --i) 
{
    f += 1.0/static_cast<float>(i);
}

о, забыл сказать, что компиляторы обычно имеют переключатели для определения режима оценки с плавающей запятой. это может быть связано с тем, что вы говорите по порядку суммирования - в Visual C + они находятся в настройках компиляции генерации кода, в g ++ есть опции -float, которые обрабатывают это

на самом деле, другой парень прав - сначала нужно выполнить суммирование в порядке наименьшего компонента; так 1 / n + 1 / (n-1) .. 1/1

это потому, что точность числа с плавающей запятой связана со шкалой, если вы начнете с 1, у вас будет 23 бита точности относительно 1,0. если вы начнете с меньшего числа, точность относительно меньшего числа, так что вы получите 23 бита точности относительно 1xe-200 или чего-либо еще. тогда, когда число станет больше, произойдет ошибка округления, но общая ошибка будет меньше, чем в другом направлении