2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Анализ ошибок округления в арифметике с плавающей точкой
Сообщение02.04.2018, 01:41 


26/03/12
72
Здравствуйте. Задачка довольно простая, но разобраться не могу. Допустим вычисляется сумма
$$
S = \sum_{i=1}^{n} a_i/b_i,
$$
где все $a_i$ и $b_i$ - неотрицательные числа с плавающей точкой.

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

Везде дают оценки для округления "до ближайшего", и нигде нет оценок для направленных округлений. Например, в статье "Improved Error Bounds for Inner Products in Floating-Point Arithmetic" (http://www.ti3.tuhh.de/paper/rump/JeaRu13.pdf) приведена граница ошибки для скалярного произведения, вычисляемого с округлением "до ближайшего":
$$
|float(x^T y) - x^Ty| \le n\mathbf{u}|x|^T|y|,
$$
где $float(\cdot)$ обозначает вычисленное скалярное произведение, $x^Ty$ - точное скалярное произведение, $n$ - размер векторов и $\mathbf{u}$ - единица округления (unit roundoff). Для округления до ближайшего $\mathbf{u} = 2^{-p}$, где $p$ - точность (53 для double).

Корректно ли использовать приведенную выше оценку применительно к вычислению $S$? То есть, правильно ли следующее:
$$
|fldown(S) - S| \le n\mathbf{u}\sum_{i=1}^{n} |a_i/b_i|,
$$
где $fldown(S)$ - значение суммы, вычисленное с округлением "вниз", а единица округления $\mathbf{u} = 2^{1-p}$?

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение02.04.2018, 19:11 
Заслуженный участник


26/05/14
677
Думаю, что вы применяете слишком изощрённые методы. Проще оценить ошибки возникающие при делении, а затем - при сложении. Аккуратно сложить все такие ошибки.

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 05:28 
Заслуженный участник


18/01/15
980
По моему, тут и без суммирования неверно. Если $a$ порядка $10^{-200}$, а $b$ --- $10^{200}$, то $a/b\approx 10^{-400}$, машинный ноль! (применительно к обычному компьютеру).

Еще, посмотрел ту статью Румпа. Что-то странное. Я не специалист, но вроде весь анализ данного вопроса еще полвека назад был написан в книжке J.H.Wilkinson, Rounding Errors in Algebraic Processes (книжка хорошая, годная). Или я чего-то не понимаю.

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 10:17 
Заслуженный участник


26/05/14
677
vpb, при рассмотрении таких задач переполнение не рассматривается. Причина простая: при переполнении ошибка может стать произвольно велика.

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 11:06 


17/10/08
1097
В общем случае, такие задачи решаются аппаратом интервального анализа. Интервалы можно умножать, делить, складывать и т.д. - в результате будет интервал. При интервальном вычислении Вы получите интервал, в который гарантированно попадает результат.

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

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

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 11:55 
Заслуженный участник


28/04/09
1880
Интервальная арифметика (см. определение 4 основных арифметических операций над интервалами, работу с округлениями).

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 13:10 
Заслуженный участник


18/01/15
980
Понял я, кажется, в чем состоит научная новизна указанной статьи по сравнению с тем, что в Уилкинсоне написано. Да, не такая уж фиговая фигня простая вещь эти ваши округления.

Уважаемые специалисты, кто в курсе, не могли бы вы мне рекомендовать несколько книжек, где более-менее основательно рассматривается, как возникают вычислительные ошибки, как накапливаются, какие при этом неожиданные феномены возможны, и как с ними бороться?

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 13:45 
Заслуженный участник
Аватара пользователя


01/08/06
2509
Уфа
Вот тут пару хороших книжек рекомендуют (они особенно хороши, если дело пахнет системами линейных уравнений).

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 18:30 


26/03/12
72
Всем спасибо за ответы. Как закончу анализ ошибок при вычислении указанного выражения, помещу его сюда.


vpb в сообщении #1301401 писал(а):
Уважаемые специалисты, кто в курсе, не могли бы вы мне рекомендовать несколько книжек, где более-менее основательно рассматривается, как возникают вычислительные ошибки, как накапливаются, какие при этом неожиданные феномены возможны, и как с ними бороться?


1. Nicholas J. Higham. Accuracy and stability of numerical algorithms (2002),
2. J.-M. Muller et. al. Handbook of Floating-Point Arithmetic (2010),
3. D. Goldberg. What Every Computer Scientist Should Know About Floating-Point Arithmetic (1991)
4. W. Kahan. How Futile are Mindless Assessments of Roundoff in Floating-Point Computation? (2006)

-- 03.04.2018, 18:41 --

slavav в сообщении #1301211 писал(а):
Думаю, что вы применяете слишком изощрённые методы. Проще оценить ошибки возникающие при делении, а затем - при сложении. Аккуратно сложить все такие ошибки.

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

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 18:43 
Заслуженный участник


26/05/14
677
Вы правы про единицу округления. Чтобы определить её надо определить что такое деление с округлением вниз. Как только вы дадите точное определение, сразу станет ясна величина ошибки.

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение03.04.2018, 20:42 
Заслуженный участник


18/01/15
980
worm2, kisupov,
спасибо за указания на книжки!

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение04.04.2018, 11:03 


17/10/08
1097
slavav в сообщении #1301473 писал(а):
Чтобы определить её надо определить что такое деление с округлением вниз. Как только вы дадите точное определение, сразу станет ясна величина ошибки.

Чтобы не ошибиться, нужно обратиться к документации по сопроцессору. Наверняка это максимальное представимое число используемого для результата типа (типа double, например), не превышающее частное.

Поскольку $a_i$ и $b_i$ - это числа, а не интервалы, то для "теории" можно считать, что нижняя граница $(1-u) a_i/b_i$, а верхняя $(1+u)  a_i/b_i$. u - определяется разрядностью (вроде бы $2^{-53}$ для double).

 Профиль  
                  
 
 Re: Анализ ошибок округления в арифметике с плавающей точкой
Сообщение04.04.2018, 13:28 
Заслуженный участник


26/05/14
677
Вы правы. Ошибка при округлении вниз не превосходит $u\dfrac{a_i}{b_i}$. Это в два раза больше чем при округлении к ближайшему.
Осталось проанализировать суммирование.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, PAV, Toucan, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: alex55555


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group