Анализ ошибок округления в арифметике с плавающей точкой

[kisupov]

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

$$ 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}$?

[slavav]

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

[vpb]

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

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

[slavav]

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

[mserg]

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

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

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

[EtCetera]

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

[vpb]

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

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

[worm2]

Вот тут пару хороших книжек рекомендуют (они особенно хороши, если дело пахнет системами линейных уравнений).

[kisupov]

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

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 писал(а):

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

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

[slavav]

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

[vpb]

worm2, kisupov,
спасибо за указания на книжки!

[mserg]

slavav в сообщении #1301473 писал(а):

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

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

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

[slavav]

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