Лучший алгоритм для предотвращения потери точности?

Question

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

К сожалению, указания для этого не были четко обозначены. Наблюдая за выполнением различных примеров, я знаю, что есть определенные способы сделать это: использовать ряды Тейлора, использовать конъюгаты, если задействованы квадратные корни, или найти общий знаменатель, когда вычитаются две дроби.

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

Мой вопрос заключается в том, какие еще общие ситуации мне следует искать, и какие методы «хороших» подходов к ним считаются?

Например, вот одна проблема:

f(x) = tan(x) − sin(x)  when x ~ 0

Каков наилучший и наихудший алгоритм для оценки этого из этих трех вариантов:

(a) (1/ cos(x) − 1) sin(x),
(b) (x^3)/2
(c) tan(x)*(sin(x)^2)/(cos(x) + 1).

Я понимаю, что когда x близко к нулю, tan (x) и sin (x) почти одинаковы. Я не понимаю, как или почему любой из этих алгоритмов лучше или хуже для решения проблемы.

Answer 1

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

Объяснить, почему это хорошо, довольно сложно. когда вы добавляете маленькие числа к большим числам, есть вероятность, что они будут полностью отброшены, потому что они меньше, чем самая низкая цифра в текущей мантиссе большого числа. Возьмем, к примеру, эту ситуацию:

a = 1,000,000;
do 100,000,000 time:
   a += 0.01;

если 0,01 меньше самой низкой цифры мантиссы, то цикл ничего не делает и конечный результат равен == 1 000 000 но если вы сделаете это так:

a = 0;
do 100,000,000 time:
   a += 0.01;
a += 1,000,000;

Чем низкое число медленно растет, и у вас больше шансов получить что-то близкое к == 2 000 000, что является правильным ответом.
Это, конечно, крайний пример, но я надеюсь, что вы поняли идею.

Answer 2

Когда я был студентом, мне нужно было вернуться к занятиям по цифровым методам, и это было очень больно. В любом случае, IEEE 754 - это стандарт с плавающей запятой, обычно используемый современными процессорами. Полезно понять основы этого, поскольку это дает вам большую интуицию о том, что не следует делать. Упрощенное объяснение этого состоит в том, что компьютеры хранят числа с плавающей запятой в чем-то вроде научной нотации base-2 с фиксированным числом цифр (битов) для показателя степени и для мантиссы. Это означает, что чем больше абсолютное значение числа, тем менее точно оно может быть представлено. Для 32-разрядных операций с плавающей запятой в IEEE 754 половина возможных битовых комбинаций представляет от -1 до 1, даже если числа до 10 ^ 38 представляются с помощью 32-разрядных операций с плавающей запятой. Для значений больше 2 ^ 24 (приблизительно 16,7 миллионов) 32-разрядное число с плавающей запятой не может точно представить все целые числа.

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

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

2. Сложение / вычитание небольших чисел из больших чисел. Например, если вы написали что-то вроде:

   для (индекс с плавающей запятой = 17000000; индекс <17000001; индекс ++) {} </p>

Этот цикл никогда не завершится, потому что 17 000 000 + 1 округляется до 17 000 000. Если у вас было что-то вроде:

float foo = 10000000 - 10000000.0001

Значение foo будет равно 0, а не -0,0001 из-за ошибки округления.

Answer 3

Мой вопрос: какие еще общие ситуации, которые я должен искать и то, что считается «хорошим» методы приближения к ним?

Существует несколько способов серьезной или даже катастрофической потери точности.

Наиболее важной причиной является то, что числа с плавающей запятой имеют ограниченное количество цифр, например, двойные имеют 53 бита. Это означает, что если у вас есть «бесполезные» цифры, которые не являются частью решения, но должны быть сохранены, вы теряете точность.

Например (Мы используем десятичные типы для демонстрации):

2.598765000000000000000000000100 -

2,598765000000000000000000000099

Интересная часть - ответ 100-99 = 1. Так как 2.598765 в обоих случаях равен не меняет результат, но тратит 8 цифр. Гораздо хуже, потому что компьютер не знаю, что цифры бесполезны, они вынуждены хранить их и забивают 21 ноль после них, тратить на все 29 цифр. К сожалению, нет способа обойти это из-за различий, но есть и другие случаи, например exp (x) -1 - функция, очень часто встречающаяся в физике.

Функция exp около 0 является почти линейной, но она вводит 1 как начальную цифру. Так с 12 значащие цифры exp (0.001) -1 = 1.00100050017 - 1 = 1.00050017e-3

Если вместо этого мы используем функцию expm1 (), используйте ряд Тейлора:

1 + х + х ^ 2/2 + х ^ 3/6 ... -1 =

x + x ^ 2/2 + x ^ 3/6 =: expm1 (x)

expm1 (0,001) = 1,00500166667e-3

Намного лучше.

Вторая проблема - это функции с очень крутым наклоном, например, тангенсом x около pi / 2. tan (11) имеет наклон 50000, что означает, что любое небольшое отклонение вызвано ошибками округления до того будет увеличен в 50000 раз! Или у вас есть особенности, если, например, результат приближается к 0/0, это означает, что он может иметь любое значение.

В обоих случаях вы создаете замещающую функцию, упрощая исходную функцию. Бесполезно выделять различные подходы к решению, потому что без обучения вы просто не увидите проблему в первую очередь.

Очень хорошая книга для изучения и обучения: Форман С. Актон: Реальные вычисления сделали реальностью

Answer 4

Еще одна вещь, которую следует избегать, это вычитать числа, которые почти равны, так как это также может привести к повышенной чувствительности к ошибке округления. Для значений, близких к 0, cos (x) будет близко к 1, поэтому 1 / cos (x) - 1 - это одно из тех вычитаний, которые вы хотели бы избежать, если это возможно, поэтому я бы сказал, что следует избегать (a) .