Точные решения для lib(ic)

Question

Точные решения для lib(ic)

Использование ECLiPSe Prolog's lib(ic) Я наткнулся на следующую проблему от Дэвида Х. Бейли: "Разрешение численных аномалий в научных вычислениях". который я упоминал в книге Унума. На самом деле, это только часть этого. Во-первых, позвольте мне сформулировать уравнение в терминах (is)/2, Кроме того, обратите внимание, что все эти десятичные числа имеют точное представление в числах с плавающей запятой 2 (которые включают IEEE):

ECLiPSe Constraint Logic Programming System [kernel]
...
Version 6.2development #21 (x86_64_linux), Wed May 27 20:58 2015
[eclipse 1]: lib(ic).
...
Yes (0.36s cpu)
[eclipse 2]: X= -1, Y = 2, Null is 0.80143857*X+1.65707065*Y-2.51270273.

X = -1
Y = 2
Null = 0.0
Yes (0.00s cpu)

Так что это ~~действительно~~ 0,0 (~~без округления вообще~~). Но теперь то же самое с $= на месте is:

[eclipse 3]: X= -1, Y = 2, Null $= 0.80143857*X+1.65707065*Y-2.51270273.

X = -1
Y = 2
Null = 2.2204460492503131e-16__2.2204460492503131e-16
Yes (0.00s cpu)

Этот интервал не содержит 0.0. Я знаю, что интервальная арифметика часто слишком приблизительна, как в:

[eclipse 4]: 1 $= sqrt(1).

Delayed goals:
    0 $= -1.1102230246251565e-16__2.2204460492503131e-16
Yes (0.00s cpu)

Но, по крайней мере, уравнение выполнено! Однако в первом случае ноль больше не включается. Видимо, я чего-то не поняла. Я пробовал также eval/1 но безрезультатно.

[eclipse 5]: X= -1, Y = 2, Null $= eval(0.80143857*X+1.65707065*Y-2.51270273).

X = -1
Y = 2
Null = 2.2204460492503131e-16__2.2204460492503131e-16
Yes (0.00s cpu)

В чем причина Null не включая 0.0?

(Изменить после удивительного ответа @jschimpf)

Вот цитата из страницы 187 книги, которую я интерпретировал как означающий, что числа представлены точно (теперь ~~обведены~~).

Используйте среду {3,5}, которая может моделировать одинарную точность IEEE. Входные значения точно представимы....
{-1, 2}
...
Это сделало свою работу, вычислив точный ответ с использованием менее половины битов, используемых...

В противном случае на странице заявления 184 содержится:

...
0,80143857 х + 1,65707065 у = 2,51270273
Уравнения, конечно, выглядят достаточно невинно. Предполагая точные десятичные входные данные, это
Система решается точно по x = -1 и y = 2.

Вот перепроверил с SICStus'ом library(clpq):

| ?- {X= -1,Y=2,
     A = 80143857/100000000,
     B = 165707065/100000000,
     C = 251270273/100000000,
     Null = A*X+B*Y-C}.
X =  -1,
Y = 2,
A = 80143857/100000000,
B = 33141413/20000000,
C = 251270273/100000000,
Null = 0 ? 
yes

Таким образом, -1, 2 являются точными решениями.

Точная формулировка

Вот переформулировка, которая не имеет проблем с округлением входных коэффициентов, но решение просто -∞...+∞. Таким образом, тривиально правильно, но не полезно.

[eclipse 2]: A = 25510582, B = 52746197, U = 79981812, 
C = 80143857, D = 165707065, V = 251270273,
A*X+B*Y$=U,C*X+D*Y$=V.

A = 25510582
B = 52746197
U = 79981812
C = 80143857
D = 165707065
V = 251270273
X = X{-1.0Inf .. 1.0Inf}
Y = Y{-1.0Inf .. 1.0Inf}


Delayed goals:
    52746197 * Y{-1.0Inf .. 1.0Inf} + 25510582 * X{-1.0Inf .. 1.0Inf} $= 79981812
    80143857 * X{-1.0Inf .. 1.0Inf} + 165707065 * Y{-1.0Inf .. 1.0Inf} $= 251270273
Yes (0.00s cpu)

3

prolog floating-accuracy eclipse-clp interval-arithmetic clpr

Источник

user772868 25 июн '15 в 19:16

1 ответ

Решение

Другие вопросы по тегам prolog floating-accuracy eclipse-clp interval-arithmetic clpr

user2353967 27 июн '15 в 00:18 2015-06-27 00:18 · Accepted Answer · 2015-06-27 00:18

Здесь возникает несколько проблем, чтобы создать путаницу:

кроме заявленных, три константы в примере не имеют точных представлений как двойные числа с плавающей запятой.
неверно, что первоначальный пример не предполагает округления.
казалось бы, правильный результат в первом примере на самом деле связан с удачной ошибкой округления. Другие порядки вычислений дают разные результаты.
точный результат, учитывая ближайшее представление констант с двойным плавающим числом, действительно не равен нулю, а равен 2.2204460492503131e-16.
интервальная арифметика может дать точные результаты только тогда, когда входные данные точны, что здесь не так. Константы должны быть расширены в интервалы, которые включают желаемую десятичную дробь.
реляционная арифметика, подобная той, что предлагается в lib(ic), по своей природе не гарантирует определенного порядка вычисления. По этой причине ошибки округления могут отличаться от ошибок, возникающих при функциональной оценке. Результаты, однако, будут точными в отношении данных констант.

Далее идет немного подробнее. Поскольку я продемонстрирую некоторые моменты, используя запросы ECLiPSe, коротко расскажу о синтаксисе:

два числа с плавающей точкой, разделенные двойным подчеркиванием, такие как 0.99__1.01 Обозначим интервальную константу с нижней и верхней границей, в этом случае число в окрестности 1.
два целых числа, разделенных одним подчеркиванием, например 3_4 Обозначим рациональную константу с помощью числителя и знаменателя, в данном случае три четверти.

Чтобы продемонстрировать точку (1), преобразуйте представление с плавающей точкой 0,80143857 в рациональное. Это дает точную дробь 3609358445212343/4503599627370496, которая близка, но не идентична, предполагаемой десятичной дроби 80143857/100000000. Следовательно, представление с плавающей точкой не является точным:

?- F is rational(0.80143857), F =\= 80143857_100000000.
F = 3609358445212343_4503599627370496
Yes (0.00s cpu)

Ниже показано, как результат зависит от порядка оценки (пункт 3 выше; обратите внимание, что я упростил исходный пример, избавившись от ненужных умножений):

?- Null is -0.80143857 + 3.3141413 - 2.51270273.
Null = 0.0
Yes (0.00s cpu)

?- Null is -2.51270273 + 3.3141413 - 0.80143857.
Null = 2.2204460492503131e-16
Yes (0.00s cpu)

Зависимость порядка доказывает, что возникают ошибки округления (точка 2). Для тех, кто знаком с операциями с плавающей запятой, на самом деле легко увидеть, что при добавлении -0.80143857 + 3.3141413, два бита точности от 0.80143857 теряться при настройке показателей операндов. Фактически, именно эта счастливая ошибка округления дает ОП, казалось бы, правильный результат!

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

?- Null is rational(-0.80143857) + rational(3.3141413) - rational(2.51270273).
Null = 1_4503599627370496
Yes (0.00s cpu)

?- Null is rational(-2.51270273) + rational(3.3141413) - rational(0.80143857).
Null = 1_4503599627370496
Yes (0.00s cpu)

Поскольку добавления выполняются с точными рациональными значениями, результат теперь не зависит от порядка, и потому 1_4503599627370496 =:= 2.2204460492503131e-16 это подтверждает ненулевой результат с плавающей запятой, полученный выше (точка 4).

Как здесь может помочь интервальная арифметика? Он работает путем вычисления с интервалами, которые содержат истинное значение, так что результаты всегда будут точными по отношению к входным данным. Поэтому крайне важно иметь входные интервалы (ограниченные вещественные числа в терминологии ECLiPSe), которые содержат желаемое истинное значение. Их можно получить, записав их явно, например: 0.80143856__0.80143858; путем преобразования из точного числа, например, рациональное использование breal(80143857_100000000); или инструктируя синтаксическому анализатору автоматически расширять все числа с плавающей запятой на ограниченные действительные интервалы, как показано ниже:

?- set_flag(syntax_option, read_floats_as_breals).
Yes (0.00s cpu)

?- Null is -0.80143857 + 3.3141413 - 2.51270273.
Null = -8.8817841970012523e-16__1.3322676295501878e-15
Yes (0.00s cpu)

?- Null is -2.51270273 + 3.3141413 - 0.80143857.
Null = -7.7715611723760958e-16__1.2212453270876722e-15
Yes (0.00s cpu)

Оба результата теперь содержат ноль, и становится очевидным, как точность результата зависит от порядка оценки.