Просмотр кода страницы Русская Википедия:Интервальная арифметика

{{Русская Википедия/Панель перехода}}
'''Интервальная арифметика''' — [[математическая структура]], которая для [[Вещественное число|вещественных]] [[Промежуток (математика)|интервалов]] определяет [[Операция (математика)|операции]], аналогичные обычным арифметическим. Эту область математики называют также '''интервальным анализом''' или '''интервальными вычислениями'''. Данная [[математическая модель]] удобна для исследования различных прикладных объектов{{sfn |Шарый|2019|с=18}}:
* Величины, значения которых известны только [[Приближённые вычисления|приближённо]], то есть определён конечный интервал, в котором эти значения содержатся.
* Величины, значения которых в ходе вычислений искажены ошибками [[Округление|округления]].
* [[Случайные величины]].
Объекты и операции интервальной арифметики можно рассматривать как обобщение модели вещественных чисел, поэтому интервалы в ряде источников называются '''интервальными числами'''. Практическая важность этой модели связана с тем, что результаты измерений и вычислений почти всегда имеют некоторую погрешность, которую необходимо учесть и оценить.

== История вопроса ==
Интервальная арифметика не является совершенно новым явлением в математике; в истории она несколько раз появлялась под разными именами. Например, [[Архимед]] в III веке {{донэ}}. рассчитал нижнюю и верхнюю границы для числа <math>\pi</math>:
: <math>\frac{223}{71} < \pi < \frac{22}{7}</math>
Хотя вычисления с интервалами не были столь же популярны, как другие численные методы, но они не были полностью забыты.

Новая история интервальных вычислений начинается в 1931 году с работы Розалинды Сесили Янг<ref name="Young_1931">''Young, Rosalind Cicely'' (1931). The algebra of many-valued quantities. Mathematische Annalen, 104(1), 260—290. (Это её диссертация в [[Кембриджский университет|Кембриджском университете]]).</ref>, где были приведены правила вычисления с интервалами и другими подмножествами вещественных чисел. В 1951 году появился учебник Пола С. Дуайера по [[Линейная алгебра|линейной алгебре]], в нём эта тема рассматривалась с точки зрения повышения надёжности цифровых систем — интервалы использовались для оценки [[Округление|ошибок округления]], связанных с [[Число с плавающей запятой|числами с плавающей запятой]]<ref>''Dwyer, Paul Sumner'' (1951). Linear computations. Oxford, England: Wiley. (University of Michigan)</ref>. В 1958 году Теруо Сунага опубликовал подробный доклад о применении интервальной алгебре в [[Вычислительная математика|численном анализе]]<ref>{{статья |author-first=Teruo |author-last=Sunaga |заглавие=Theory of interval algebra and its application to numerical analysis |издание=RAAG Memoirs |номер=2 |страницы=29—46 |язык=en |тип=journal |год=1958}}</ref>.

Во второй половине XX века потребности компьютерных вычислений вызвали бурное развитие интервального анализа практически одновременно и независимо в Советском Союзе, США, Японии и Польше. В 1966 году появилась книга американского математика {{нп5|Рамон Мур|Рамона Мура||Ramon E. Moore}} «Интервальный анализ» (''Interval Analysis'')<ref name="Moore_1966">{{книга |author-last=Moore |author-first=Ramon Edgar |заглавие=Interval Analysis |издательство=[[Prentice Hall]] |место=Englewood Cliff, New Jersey, USA |isbn=0-13-476853-1 |язык=en |год=1966}}</ref>. Достоинство этой работы заключалось в том, что, начиная с простого принципа, он предоставлял общий метод для автоматического анализа ошибок, причём не только ошибок, возникающих в результате округления.

В последующие два десятилетия важные исследования по интервальному анализу и его приложениям велись в Германии — Карлом Никелем и его учениками в Университете Фрайбурга, в группах {{нп5|Кулиш, Ульрих|Ульриха Кулиша||Ulrich Kulisch}} и Гётца Алефельда в [[Технологический институт Карлсруэ|Университете Карлсруэ]]<ref name="Kulisch_1969">{{книга |часть=Grundzüge der Intervallrechnung |язык=de |author-first=Ulrich W. |author-last=Kulisch |заглавие=Jahrbuch Überblicke Mathematik |том=2 |издательство=[[Библиографический институт|Bibliographisches Institut]] |место=Mannheim, Germany |страницы=51—98 |ответственный=Laugwitz, Detlef |год=1969}}</ref><ref name="Kulisch_1989">{{книга |author-last=Kulisch |author-first=Ulrich W. |заглавие=Wissenschaftliches Rechnen mit Ergebnisverifikation. Eine Einführung |издательство={{Нп5|Springer Vieweg Verlag}} |место=Wiesbaden |язык=de |isbn=3-528-08943-1 |год=1989}}</ref>, и других.

В 1960-х годах Элдон Р. Хансен занимался расширением интервального подхода на [[Система линейных алгебраических уравнений|системы линейных уравнений]], а затем внес важный вклад в [[Оптимизация (математика)|глобальную оптимизацию]], включая то, что сейчас известно как метод Хансена — возможно, наиболее широко используемый интервальный алгоритм<ref>{{книга |author-last1=Walster |author-first1=G. William |author-last2=Hansen |author-first2=Eldon Robert |заглавие=Global Optimization using Interval Analysis |издание=2nd |издательство={{Нп5|Marcel Dekker}} |место=New York, USA |isbn=0-8247-4059-9 |язык=en |год=2004}}</ref>. Классические методы в этой задаче часто имеют проблему с определением наибольшего (или наименьшего) глобального значения (могут найти только локальный оптимум и не могут найти лучшие значения); Хельмут Рачек и Джон Джордж Рокне разработали вариацию [[метод ветвей и границ|метода ветвей и границ]], который до этого применялся только к целочисленным значениям.

В 1988 году Рудольф Лонер разработал программное обеспечение на основе языка [[Фортран]] для доказательного решения задачи Коши для систем [[Обыкновенное дифференциальное уравнение|обыкновенных дифференциальных уравнений]]<ref>[http://fam-pape.de/raw/ralph/studium/dgl/dglsem.html Bounds for ordinary differential equations of Rudolf Lohner] {{Webarchive|url=https://web.archive.org/web/20180511153904/http://fam-pape.de/raw/ralph/studium/dgl/dglsem.html |date=11 May 2018 }} (in German)</ref>.

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

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

== Операции над интервалами ==
Мы будем рассматривать всевозможные конечные вещественные [[Промежуток (математика)|интервалы]] <math>[a,b]\ (a \leqslant b)</math>. Операции над ними определяются следующим образом:
* Сложение: [''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'')]

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

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

== Свойства операций ==
Сложение и умножение интервалов [[Коммутативность|коммутативны]] и [[Ассоциативность (математика)|ассоциативны]]. Но вместо полноценной [[Дистрибутивность|дистрибутивности]] умножения по сложению имеет место так называемая субдистрибутивность:

: <math>X ( Y + Z ) \subset XY + XZ</math>

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

== Стандарт IEEE 1788 ==
Стандарт компьютерной реализации интервальной арифметики IEEE 1788—2015 был принят в июне 2015 года.<ref>{{Cite web |url=https://standards.ieee.org/ieee/1788/4431 |title=IEEE Standard for Interval Arithmetic |access-date=2022-02-07 |archive-date=2022-02-07 |archive-url=https://web.archive.org/web/20220207220021/https://standards.ieee.org/ieee/1788/4431/ |deadlink=no }}</ref> В процессе работы над стандартом и в последующие годы были подготовлены несколько свободно распространяемых референсных реализаций:<ref>Revol, Nathalie (2015). The (near-)future IEEE 1788 standard for interval arithmetic. 8th small workshop on interval methods. [http://kam.mff.cuni.cz/conferences/swim2015/slides/revol.pdf Slides (PDF)] {{Wayback|url=http://kam.mff.cuni.cz/conferences/swim2015/slides/revol.pdf |date=20160602221649 }}</ref> библиотека [[C++]] libieeep1788<ref>{{Cite web |url=https://github.com/nehmeier/libieeep1788 |title=C++ implementation of the preliminary IEEE P1788 standard for interval arithmetic |access-date=2018-07-31 |archive-date=2018-06-10 |archive-url=https://web.archive.org/web/20180610233759/https://github.com/nehmeier/libieeep1788 |deadlink=no }}</ref> library for C++, библиотека JInterval для языка Java, а также пакет, реализующий интервальные вычисления для свободного математического ПО [[GNU Octave]]<ref>{{Cite web |url=http://octave.sourceforge.net/interval/ |title=GNU Octave interval package |access-date=2018-07-31 |archive-date=2016-11-09 |archive-url=https://web.archive.org/web/20161109225114/http://octave.sourceforge.net/interval/ |deadlink=no }}</ref>.

Минимальное подмножество стандарта, предназначенное для упрощения и ускорения его реализации — IEEE Std 1788.1-2017, было принято в декабре 2017 и опубликовано в феврале 2018.<ref>{{cite web
  |url=https://standards.ieee.org/ieee/1788.1/6074
  |title=IEEE Std 1788.1-2017 - IEEE Standard for Interval Arithmetic (Simplified)
  |author=<!--Staff writer(s); no by-line.-->
  |date=
  |website=IEEE SA
  |publisher=IEEE Standards Association
  |accessdate=2018-02-06
  |archive-date=2022-02-07
  |archive-url=https://web.archive.org/web/20220207221608/https://standards.ieee.org/ieee/1788.1/6074/
  |deadlink=no
  }}</ref>

== Программное обеспечение ==
Существует много реализаций интервальной арифметики в различных пакетах программного обеспечения<ref>[http://www.cs.utep.edu/interval-comp/main.html  Software for Interval Computations] {{Wayback|url=http://www.cs.utep.edu/interval-comp/main.html |date=20060302095039 }} collected by [[:en:Vladik Kreinovich|Vladik Kreinovich]], [[University of Texas at El Paso]]</ref>. Зачастую они оформляются как специализированные библиотеки. Ряд компиляторов [[Fortran]] и [[C++]] включают в себя поддержку интервальных значений как специального типа данных.

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

== Примечания ==
{{примечания}}

== Литература ==
* ''Алефельд Г., Херцбергер Ю.''. [http://www.nsc.ru/interval/Library/InteBooks/AlefeHerz.pdf Введение в интервальные вычисления]. М.: Мир, 1987. 356 с.
* ''Добронец Б. С.'' [http://www.nsc.ru/interval/Library/InteBooks/InteMath.pdf Интервальная математика]. Красноярск: Издательство КГУ, 2004.
* {{книга |автор=Шарый С. П.
 |заглавие=Конечномерный интервальный анализ
 |ref=Шарый
 |ссылка=http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf
 |место=Новосибирск
 |издательство=XYZ
 |год=2019
 |страниц=635
}}
* {{книга|автор=Шокин Ю. И.
 |заглавие=Интервальный анализ
 |ref=Шокин
 |место=Новосибирск
 |ссылка=http://www.nsc.ru/interval/Library/InteBooks/Shokin.pdf
 |издательство=Сибирское отделение изд-ва «Наука»
 |год=1981
}}

== Ссылки ==
* [http://www.nsc.ru/interval/ Интервальный анализ и его приложения].
** {{h|Исторические заметки}}[http://www.nsc.ru/interval/?page=Introduction/history Исторические заметки].
* [http://mathworld.wolfram.com/IntervalArithmetic.html Интервальная арифметика] на сайте Mathworld{{ref-en}}.

{{Типы данных}}
{{Числа}}
{{Стандарты IEEE}}

[[Категория:Арифметика]]
[[Категория:Численные методы]]
[[Категория:Стандарты IEEE]]
{{Навигационная таблица/Портал/Русская Википедия}}
[[Категория:Русская Википедия]]
[[Категория:Википедия]]
[[Категория:Статья из Википедии]]
[[Категория:Статья из Русской Википедии]]