Как сравнить точность аналитического алгоритма и его программной реализации?

Question

[WTFAYD]

Здравствуйте!

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

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

Comments

[Roman]

Вы на голом си писали? или использовали хотя бы
https://ru.wikipedia.org/wiki/GNU_Multi-Precision_...
https://ru.wikipedia.org/wiki/GNU_Scientific_Library

[WTFAYD]

Роман, простой чистый Си и стандартная библиотека

Answer 1

[Mercury13]

Есть вычитание близких чисел? Какие-нибудь циклы вроде СЛАУ больших порядков и решения дифуров? Знакопеременные ряды? Если нет, можно писать, что вклад машинной арифметики в точность алгоритма незначителен.
А если есть, нужно исследовать, кто и как может многократно усилить ошибки округления.
Ради эксперимента можно также сравнить результаты во float и double.

Пример алгоритма, который аналитически устойчив, а вычислительно — нет: e^−x «в лоб» при достаточно больших x. Связан он с тем самым вычитанием близких чисел: промежуточные члены ряды могут быть достаточно большие, а в результате выходит 0,0…01.

UPD. Вот такую книжку нашёл: info.alnam.ru/book_clm.php?id=26

Comments

[res2001]

Зачетная книжка, спс.

[WTFAYD]

Mercury13, того что вы перечислили вроде бы нет, да и требуемая точность результата - 4-5 знаков после запятой.

Answer 2

[Griboks]

Быть может, вы хотите сравнить погрешности результатов работы алгоритма? Это целая тема. Во-первых, необходимо выяснить, какую погрешность вносит компьютер. Затем применить соответствующий метод коррекции систематической погрешности. Если убрать эту погрешность не удалось, её надо хотя бы как-то оценить. Вот стандартный пример:

> 0.1*0.2
< 0.020000000000000004

Видно, что погрешность равна 4e-19, т.е. 0.1*0.2=0.020000000000000000+-0.000000000000000004. Ну короч понятно, что есть какая-то погрешность.

Ну а если всё-таки вам нужна точность, то это количество знаков после запятой перед первой значащей цифрой погрешности. А может и нет. Нет понятия точности, насколько мне известно.

Answer 3

[Andy_U]

Инсталируйте пакет mpmath, повторите ваш расчет с его использованием (задав там много-много знаков) и без и сравните результаты. Если формулы простые, это будет быстро. А потом, если грабли найдутся, ищите конкретные причины.