Интервальная арифметика

Интервальная арифметика — раздел вычислительной математики, который для вещественных интервалов определяет арифметические операции, аналогичные обычным. Эту область также называют интервальным анализом или интервальными вычислениями. Данная математическая модель удобна для исследования объектов, значения которых известны лишь приближённо (т. е. заданы конечным интервалом), искажены ошибками округления или носят случайный характер.

Объекты и операции интервальной арифметики можно рассматривать как обобщение обычных вещественных чисел; в литературе их часто называют интервальными числами. Практическая ценность модели в том, что результаты измерений и вычислений почти всегда содержат погрешность, которую необходимо учитывать и оценивать.

История вопроса Интервальная арифметика не является совершенно новым явлением; в прошлом она неоднократно появлялась под разными названиями. Например, Архимед в III веке . вычислил нижнюю и верхнюю границы для числа :

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

Новая история интервальных вычислений начинается в 1931 году с работы Розалинды Сесили ЯнгYoung, Rosalind Cicely (1931). The algebra of many-valued quantities. Mathematische Annalen, 104(1), 260—290. (Это её диссертация в Кембриджском университете)., в которой были приведены правила действий с интервалами и другими подмножествами вещественных чисел. В 1951 году вышла книга Пола С. Дуайера по линейной алгебре, где интервалы использовались для оценки ошибок округления в системах с плавающей запятойDwyer, Paul Sumner (1951). Linear computations. Oxford, England: Wiley. (University of Michigan). В 1958 году Теруо Сунага опубликовал обстоятельный доклад о применении интервальной алгебре в численном анализе.

Во второй половине XX века потребности компьютерных вычислений вызвали бурное развитие интервального анализа практически одновременно и независимо в СССР, США, Японии и Польше. В 1966 году появилась книга «Интервальный анализ». Достоинство этой работы заключалось в том, что, начиная с простого принципа, он предоставлял общий метод для автоматического анализа ошибок, причём не только ошибок, возникающих в результате округления.

В последующие два десятилетия важные исследования по интервальному анализу и его приложениям велись в Германии — Карлом Никелем и его учениками в Университете Фрайбурга, в группах и Гётца Алефельда в Университете Карлсруэ, и других.

В 1960-х годах Элдон Р. Хансен занимался расширением интервального подхода на системы линейных уравнений, а затем внес важный вклад в глобальную оптимизацию, включая то, что сейчас известно как метод Хансена — возможно, наиболее широко используемый интервальный алгоритм. Классические методы в этой задаче часто имеют проблему с определением наибольшего (или наименьшего) глобального значения (могут найти только локальный оптимум и не могут найти лучшие значения); Хельмут Рачек и Джон Джордж Рокне разработали вариацию метода ветвей и границ, который до этого применялся только к целочисленным значениям.

В 1988 году Рудольф Лонер разработал программное обеспечение на основе языка Фортран для доказательного решения задачи Коши для систем обыкновенных дифференциальных уравненийBounds for ordinary differential equations of Rudolf Lohner (in German).

С 1990-х годов началась публикация международного журнала «Интервальные вычисления» − «Interval Computations», который в 1995 году был переименован в «Reliable Computing» («Надёжные вычисления»). Основной тематикой журнала являются доказательные вычисления, методы интервального анализа и его приложения.

В России и СССР интервальной тематикой активно занимался с 1920-х годов В. М. Брадис. В 1962 году один из первых выпусков «Сибирского математического журнала» опубликовал статью Леонида Витальевича Канторовича, который, фактически, наметил основы интервального анализа в частично упорядоченных пространствах и приложения новой техники. В его статье эта тематика была обозначена как приоритетная для нашей вычислительной науки. В послевоенный период одной из первых стала книга Ю. И. Шокина «Интервальный анализ». В следующем году появилось учебное пособие Т.И. Назаренко и Л.В. Марченко «Введение в интервальные методы вычислительной математики»Т. И. Назаренко, Л. В. Марченко. Введение в интервальные методы вычислительной математики" Учеб. пособие. Иркутск : Изд-во Иркутского ун-та, 1982. — 108 с., а в 1986 году — монография С. А. Калмыкова, Ю. И. Шокина и З. Х. Юлдашева «Методы интервального анализа»С. А. Калмыков, Ю. И. Шокин, З. Х. Юлдашев Методы интервального анализа. — Новосибирск: Наука, 1986, 224 с..

Операции над интервалами Мы будем рассматривать всевозможные конечные вещественные интервалы . Операции над ними определяются следующим образом: Сложение: [a,b] + [c,d] = [a + c, b + d] Вычитание: [a,b] − [c,d] = [a − d, b − c] Умножение: [a,b] × [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)] Деление: [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]

Из определения видно, что интервал-сумма содержит всевозможные суммы чисел из интервалов-слагаемых и определяет границы множества таких сумм. Аналогично трактуются прочие действия. Отметим, что операция деления определена только в том случае, когда интервал-делитель не содержит нуля.

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

Свойства операций Сложение и умножение интервалов коммутативны и ассоциативны. Но вместо полноценной дистрибутивности умножения по сложению имеет место так называемая субдистрибутивность:

Варианты и расширения интервальной арифметики

Стандарт IEEE 1788 Стандарт компьютерной реализации интервальной арифметики IEEE 1788—2015 был принят в июне 2015 года. В процессе работы над стандартом и в последующие годы были подготовлены несколько свободно распространяемых референсных реализаций:Revol, Nathalie (2015). The (near-)future IEEE 1788 standard for interval arithmetic. 8th small workshop on interval methods. Slides (PDF) библиотека C++ libieeep1788 library for C++, библиотека JInterval для языка Java, а также пакет, реализующий интервальные вычисления для свободного математического ПО GNU Octave.

Минимальное подмножество стандарта, предназначенное для упрощения и ускорения его реализации — IEEE Std 1788.1-2017, было принято в декабре 2017 и опубликовано в феврале 2018.

Программное обеспечение Существует много реализаций интервальной арифметики в различных пакетах программного обеспечения Software for Interval Computations collected by Vladik Kreinovich, University of Texas at El Paso. Зачастую они оформляются как специализированные библиотеки. Ряд компиляторов Fortran и C++ включают в себя поддержку интервальных значений как специального типа данных.

См. также Приближённые вычисления IEEE 754

Примечания

Литература Алефельд Г., Херцбергер Ю.. Введение в интервальные вычисления. М.: Мир, 1987. 356 с. Добронец Б. С. Интервальная математика. Красноярск: Издательство КГУ, 2004.

Ссылки Интервальный анализ и его приложения. Исторические заметки. Интервальная арифметика на сайте Mathworld.

Категория:Арифметика Категория:Численные методы Категория:Стандарты IEEE