774 Тем для обсуждения

6,825 Открытых обсуждений

Достоверны ли вычисления?

Igor Vorobtsov (Intel) (3 пост(а)) 07.12.2011 17:28

В последнее время я достаточно много занимаюсь вопросами, связанными с точностью результатов, полученных при вычислениях, и пытаюсь найти ответ на вопрос - можно ли вообще получить точные результаты и как это сделать? Если отвечать на данный вопрос коротко и ясно – НЕТ, точный результат «в лоб» на машине получить практически невозможно при наличии сколь-нибудь сложной математической задачи, которую мы пытаемся решить.

Речь идёт не о погрешностях, которые возникают при использовании того или иного численного алгоритма и метода – речь о модели представления действительных чисел. Ввиду «ограниченности» машин, мы не можем точно представить все действительные числа – только лишь аппроксимировать их. В математическом анализе, для любого вещественного числа имеется бесконечно много чисел, которые больше или меньше его, а между любыми двумя вещественными числами также находится бесконечно много вещественных чисел. Система же машинных чисел конечна и дискретна, и образует подмножество системы вещественных чисел. Отсюда и возникает погрешность, которая будет накапливаться с количеством математических операций.

Многие скажут, что подобная точность и не нужна – ну подумаешь, в десятом знаке после запятой будет не тройка, а семёрка… а вот если нужна? Если мы решаем задачи, в которых эти значения могут быть весьма критичными (скажем, проблемы устойчивости атомных реакторов и подобные инженерные задачи), и мы должны точно знать, верно ли оно или нет? Кроме того, мы не гарантируем корректность проверки числовых соотношений. Например, если имеется код

if x < 0 then A else B

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

А может быть, всё-таки, есть способ вычислять точно? Да, такие способы есть, и их, на сегодня, целых 2 – но с понятием «точно» в данных случаях нужно быть очень аккуратным.
Первый подход – давайте заменять точное значение приближенным (что ещё нам остаётся делать), и производить оценку погрешности исходных данных и округлений. У данного подхода есть целый ряд серьёзных минусов, в частности, для нетривиальных алгоритмов получить оценку оказывается чрезвычайно сложной задачей. Кроме того, вычисления по формулам, связывающим погрешность исходных данных и погрешность результатов, сами неизбежно производятся с погрешностью.

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

Использование подобной арифметики приведёт к получению интервала, как результата вычислений, и в этом случае мы сможем гарантировать, что точное значение лежит в данном интервале. Кроме того, сравнивая нижнюю и верхнюю границы, мы сможем точно сказать, какое количество верных значащих цифр у нас есть. Например, при получение результата в виде [0.092312986, 0.092313129], мы можем точно сказать, что 0.09231 – значение, которое не зависит от машинных округлений.
Ввиду математической направленности и ряда других причин, в своей работе я использую Fortran. К большому сожалению, в Интеловской реализации Фортрана интервальной арифметики нет, хотя подобная реализация есть в ряде расширений для языков, например, XSC языков (Pascal-XSC), а так же в реализации Sun. Так что интервальную арифметику я реализовывал сам в виде модуля на языке Фортран.

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

И напоследок… для тех, кому данная тема показалась интересной, есть простая задачка, наводящая на мысли о правильности ветвления и сравнения действительных чисел (ну и о смысле «бытия» ).

Итак, пусть у нас есть два вещественных числа a и b (на Фортране – real, на С – float). Так вот, равны ли значения a = 1.1 – 1 и b = 0.1? И что меняется, если a=1.5-1, а b=0.5?

Категории: Intel Software Network, Разработка софта
Метки: точность вычислений

Пожалуйста, обратитесь к странице Уведомление об оптимизации для более подробной информации относительно производительности и оптимизации в программных продуктах компании Intel.

Комментарии (23)

Обратная ссылка (0)

Оставить комментарий  

Имя (обязательно)*

Электронная почта (обязательно; не будет отображено на этой странице)*

Ваш URL-адрес (необязательно)


Комментарий*