2014 dxdy logo

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

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




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


26/03/12
74
Здравствуйте. Задачка довольно простая, но разобраться не могу. Допустим вычисляется сумма
$$
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
727
Думаю, что вы применяете слишком изощрённые методы. Проще оценить ошибки возникающие при делении, а затем - при сложении. Аккуратно сложить все такие ошибки.

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


18/01/15
1273
По моему, тут и без суммирования неверно. Если $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
727
vpb, при рассмотрении таких задач переполнение не рассматривается. Причина простая: при переполнении ошибка может стать произвольно велика.

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


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

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

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

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


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

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


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

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

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


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

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


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


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
727
Вы правы про единицу округления. Чтобы определить её надо определить что такое деление с округлением вниз. Как только вы дадите точное определение, сразу станет ясна величина ошибки.

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


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

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


17/10/08
1117
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
727
Вы правы. Ошибка при округлении вниз не превосходит $u\dfrac{a_i}{b_i}$. Это в два раза больше чем при округлении к ближайшему.
Осталось проанализировать суммирование.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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