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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Интервальная арифметика»  -  новости  · газеты  · книги  · ученый  · JSTOR ( январь 2020 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

Тон или стиль этой статьи могут не отражать энциклопедический тон, используемый в Википедии . См. Рекомендации в руководстве Википедии по написанию лучших статей . ( Февраль 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Функция допуска (бирюза) и интервальная аппроксимация (красный цвет)

Интервал арифметика (также известная как интервальная математика , интервальный анализ , или интервал вычислений ) представляет собой математический метод , используемый для поставить ограничения на ошибки округления и погрешность измерения в математическом вычислении . Численные методы с использованием интервальной арифметики могут гарантировать надежные, математически правильные результаты. Вместо представления значения как одного числа, интервальная арифметика представляет каждое значение как диапазон возможных. Например, вместо того, чтобы оценивать рост человека как точно 2,0 метра, используя интервальную арифметику, можно быть уверенным, что рост этого человека находится где-то между 1,97 и 2,03 метра.

Математически вместо того, чтобы работать с неопределенным вещественным числом , можно работать с концами интервала, который содержит . В интервальной арифметике любая переменная находится в закрытом интервале между и . Функция , примененная к ней , дает неопределенный результат; создает интервал, включающий все возможные значения для всех .${\ displaystyle x}$${\ Displaystyle [а, б]}$${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle f}$${\ displaystyle x}$${\ displaystyle f}$${\ displaystyle [c, d]}$${\ displaystyle f (x)}$${\ Displaystyle х \ в [а, б]}$

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

Введение [ править ]

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

Эта обработка обычно ограничивается реальными интервалами, поэтому количество форм

${\ displaystyle [a, b] = \ {x \ in \ mathbb {R} \, | \, a \ leq x \ leq b \},}$

где и разрешены. С одним из , бесконечного, то интервал будет неограниченная интервал; с обоими бесконечными, интервал будет расширенной линией действительного числа. Поскольку действительное число можно интерпретировать как интервал, интервалы и действительные числа можно свободно комбинировать.${\ Displaystyle а = {- \ infty}}$${\ displaystyle b = {\ infty}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle r}$${\ Displaystyle [г, г],}$

Как и в случае традиционных вычислений с действительными числами, сначала необходимо определить простые арифметические операции и функции на элементарных интервалах. ^[1] Из этих основных элементов можно рассчитать более сложные функции. ^[1]

Пример [ править ]

В качестве примера рассмотрим расчет индекса массы тела (ИМТ) и оценку того, есть ли у человека лишний вес. ИМТ рассчитывается как масса тела человека в килограммах, деленная на квадрат его роста в метрах. Весы для ванной могут иметь разрешение в один килограмм. Промежуточные значения не различаются - например, 79,6 кг и 80,3 кг неразличимы, - но истинный вес округляется до ближайшего целого числа. Маловероятно, что когда весы показывают 80 кг, человек весит ровно 80,0 кг. При обычном округлении до ближайшего значения 80 кг на шкале показывают вес от 79,5 кг до 80,5 кг. Это соответствует интервалу .${\ displaystyle [79,5,80,5]}$

Для мужчины весом 80 кг и ростом 1,80 м ИМТ составляет примерно 24,7. Вес 79,5 кг и такая же высота дают прибл. 24,537, а вес 80,5 кг дает прибл. 24,846. Поскольку функция монотонно возрастает, мы заключаем, что истинный ИМТ находится в диапазоне . Поскольку весь диапазон составляет менее 25, что является порогом между нормальным и избыточным весом, мы заключаем, что мужчина имеет нормальный вес.${\displaystyle [24.537,24.846]}$

Ошибка в этом случае не влияет на вывод (нормальный вес), но это не всегда так. Если мужчина был немного тяжелее, диапазон ИМТ может включать пороговое значение 25. В этом случае точность шкалы была недостаточной, чтобы сделать окончательный вывод.

Также обратите внимание, что диапазон примеров ИМТ может быть представлен как , поскольку этот интервал является надмножеством рассчитанного интервала. Однако диапазон не может быть представлен как , поскольку теперь интервал не содержит возможных значений ИМТ.${\displaystyle [24.5,24.9]}$${\displaystyle [24.6,24.8]}$

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

Несколько интервалов [ править ]

Рост и масса тела влияют на значение ИМТ. Мы уже рассматривали вес как неопределенное измерение, но рост также может быть неопределенным. Измерения высоты в метрах обычно округляются до ближайшего сантиметра: зарегистрированное значение 1,79 метра фактически означает высоту в интервале . Теперь необходимо рассмотреть все четыре комбинации возможных значений роста / веса. При использовании интервальных методов, описанных ниже, ИМТ находится в интервале${\displaystyle [1.785,1.795]}$

${\displaystyle {\frac {[79.5,80.5]}{[1.785,1.795]^{2}}}\subseteq [24.673,25.266].}$

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

Операторы интервалов [ править ]

Бинарная операция над двумя интервалами, такая как сложение или умножение, определяется как${\displaystyle \star }$

${\displaystyle [x_{1},x_{2}]{\,\star \,}[y_{1},y_{2}]=\{x\star y\,|\,x\in [x_{1},x_{2}]\,\land \,y\in [y_{1},y_{2}]\}.}$

Другими словами, это набор всех возможных значений , где и находятся в соответствующих им интервалах. Если является монотонным в каждом операнде на интервалах, что имеет место для четырех основных арифметических операций (за исключением деления, когда знаменатель содержит ), крайние значения возникают в конечных точках интервалов операндов. Записывая все комбинации, можно сказать, что это${\displaystyle x\star y}$${\displaystyle x}$${\displaystyle y}$${\displaystyle \star }$${\displaystyle 0}$

${\displaystyle [x_{1},x_{2}]\star [y_{1},y_{2}]=\left[\min\{x_{1}\star y_{1},x_{1}\star y_{2},x_{2}\star y_{1},x_{2}\star y_{2}\},\max\{x_{1}\star y_{1},x_{1}\star y_{2},x_{2}\star y_{1},x_{2}\star y_{2}\}\right],}$

при условии, что определено для всех и .${\displaystyle x\star y}$${\displaystyle x\in [x_{1},x_{2}]}$${\displaystyle y\in [y_{1},y_{2}]}$

Для практических приложений это можно еще упростить:

• Дополнение :${\displaystyle [x_{1},x_{2}]+[y_{1},y_{2}]=[x_{1}+y_{1},x_{2}+y_{2}]}$
• Вычитание :${\displaystyle [x_{1},x_{2}]-[y_{1},y_{2}]=[x_{1}-y_{2},x_{2}-y_{1}]}$
• Умножение :${\displaystyle [x_{1},x_{2}]\cdot [y_{1},y_{2}]=[\min\{x_{1}y_{1},x_{1}y_{2},x_{2}y_{1},x_{2}y_{2}\},\max\{x_{1}y_{1},x_{1}y_{2},x_{2}y_{1},x_{2}y_{2}\}]}$
• Подразделение :

${\displaystyle {\frac {[x_{1},x_{2}]}{[y_{1},y_{2}]}}=[x_{1},x_{2}]\cdot {\frac {1}{[y_{1},y_{2}]}},}$

куда

${\displaystyle {\begin{aligned}{\frac {1}{[y_{1},y_{2}]}}&=\left[{\tfrac {1}{y_{2}}},{\tfrac {1}{y_{1}}}\right]&&\mathrm {if} \;0\notin [y_{1},y_{2}]\\{\frac {1}{[y_{1},0]}}&=\left[-\infty ,{\tfrac {1}{y_{1}}}\right]\\{\frac {1}{[0,y_{2}]}}&=\left[{\tfrac {1}{y_{2}}},\infty \right]\\{\frac {1}{[y_{1},y_{2}]}}&=\left[-\infty ,{\tfrac {1}{y_{1}}}\right]\cup \left[{\tfrac {1}{y_{2}}},\infty \right]\subseteq [-\infty ,\infty ]&&\mathrm {if} \;0\in (y_{1},y_{2})\end{aligned}}}$

В последнем случае теряется полезная информация об исключении . Таким образом, обычно работают с отдельными интервалами и как с отдельными интервалами. В более общем смысле, при работе с прерывными функциями иногда полезно выполнять вычисления с так называемыми многоинтервальными значениями формы . Соответствующая многоинтервальная арифметика поддерживает набор (обычно непересекающихся) интервалов, а также обеспечивает перекрывающиеся интервалы для объединения . ^[2]${\displaystyle (1/y_{1},1/y_{2})}$${\displaystyle \left[-\infty ,{\tfrac {1}{y_{1}}}\right]}$${\displaystyle \left[{\tfrac {1}{y_{2}}},\infty \right]}$${\textstyle \bigcup _{i}\left[a_{i},b_{i}\right].}$

Интервальное умножение часто требует только двух умножений. Если , неотрицательны,${\displaystyle x_{1}}$${\displaystyle y_{1}}$

${\displaystyle [x_{1},x_{2}]\cdot [y_{1},y_{2}]=[x_{1}\cdot y_{1},x_{2}\cdot y_{2}],\qquad {\text{ if }}x_{1},y_{1}\geq 0.}$

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

С помощью этих определений уже можно вычислить ряд простых функций, таких как Например, if , и :${\displaystyle f(a,b,x)=a\cdot x+b.}$${\displaystyle a=[1,2]}$${\displaystyle b=[5,7]}$${\displaystyle x=[2,3]}$

${\displaystyle f(a,b,x)=([1,2]\cdot [2,3])+[5,7]=[1\cdot 2,2\cdot 3]+[5,7]=[7,13]}$.

Обозначение [ править ]

Для уменьшения обозначения интервалов в формулах можно использовать скобки.

${\displaystyle [x]\equiv [x_{1},x_{2}]}$может использоваться для обозначения интервала. Обратите внимание, что в такой компактной записи не следует путать одноточечный интервал и общий интервал. Для набора всех интервалов мы можем использовать${\displaystyle [x]}$${\displaystyle [x_{1},x_{1}]}$

${\displaystyle [\mathbb {R} ]:=\left\{\,[x_{1},x_{2}]\,|\,x_{1}\leq x_{2}{\text{ and }}x_{1},x_{2}\in \mathbb {R} \cup \{-\infty ,\infty \}\right\}}$

как сокращение. Для вектора интервалов можно использовать жирный шрифт: .${\displaystyle \left([x]_{1},\ldots ,[x]_{n}\right)\in [\mathbb {R} ]^{n}}$${\displaystyle [\mathbf {x} ]}$

Элементарные функции [ править ]

Также могут быть определены интервальные функции помимо четырех основных операторов.

Для монотонных функций от одной переменной диапазон значений легко вычислить. Если монотонно возрастает (соответственно убывает) в интервале, то для всех таких, что (соответственно ).${\displaystyle f:\mathbb {R} \to \mathbb {R} }$${\displaystyle [x_{1},x_{2}],}$${\displaystyle y_{1},y_{2}\in [x_{1},x_{2}]}$${\displaystyle y_{1}\leq y_{2},}$ ${\displaystyle f(y_{1})<f(y_{2})}$${\displaystyle f(y_{2})<f(y_{1})}$

Поэтому диапазон, соответствующий интервалу, можно вычислить, применив функцию к его конечным точкам:${\displaystyle [y_{1},y_{2}]\subseteq [x_{1},x_{2}]}$

${\displaystyle f([y_{1},y_{2}])=\left[\min \left\{f(y_{1}),f(y_{2})\right\},\max \left\{f(y_{1}),f(y_{2})\right\}\right].}$

Исходя из этого, можно легко определить следующие основные характеристики интервальных функций:

• Экспоненциальная функция : для${\displaystyle a^{[x_{1},x_{2}]}=[a^{x_{1}},a^{x_{2}}]}$${\displaystyle a>1,}$
• Логарифм : для положительных интервалов и${\displaystyle \log _{a}[x_{1},x_{2}]=[\log _{a}{x_{1}},\log _{a}{x_{2}}]}$${\displaystyle [x_{1},x_{2}]}$${\displaystyle a>1,}$
• Нечетные полномочия:, для нечетных${\displaystyle [x_{1},x_{2}]^{n}=[x_{1}^{n},x_{2}^{n}]}$${\displaystyle n\in \mathbb {N} .}$

Для четных степеней важен диапазон рассматриваемых значений, и с ним нужно иметь дело, прежде чем производить какое-либо умножение. Например, for должен производить интервал, когда. Но если берется путем повторения интервального умножения формы, то результат будет шире, чем необходимо.${\displaystyle x^{n}}$${\displaystyle x\in [-1,1]}$${\displaystyle [0,1]}$${\displaystyle n=2,4,6,\ldots .}$${\displaystyle [-1,1]^{n}}$${\displaystyle [-1,1]\cdot [-1,1]\cdot \cdots \cdot [-1,1]}$${\displaystyle [-1,1],}$

В целом можно сказать , что для кусочно - монотонных функций, достаточно рассмотреть конечные точки , интервал, вместе с так называемыми критическими точками в пределах интервала, будучи те точки , где монотонность функции меняет направление. Для функций синуса и косинуса критические точки находятся в точке или для соответственно. Таким образом, необходимо учитывать только до пяти точек в пределах интервала, поскольку результирующий интервал будет, если интервал включает как минимум два экстремума. Для синуса и косинуса только конечные точки нуждаются в полной оценке, поскольку критические точки приводят к легко предварительно вычисленным значениям, а именно -1, 0 и 1.${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle \left({\tfrac {1}{2}}+n\right)\pi }$${\displaystyle n\pi }$${\displaystyle n\in \mathbb {Z} }$${\displaystyle [-1,1]}$

Расширения интервалов общих функций [ править ]

В общем, найти такое простое описание интервала вывода для многих функций может быть непросто. Но все же возможно расширение функций до интервальной арифметики. Если есть функция от действительного вектора на действительное число, то   называется интервал расширения в случае${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle [f]:[\mathbb {R} ]^{n}\rightarrow [\mathbb {R} ]}$${\displaystyle f}$

${\displaystyle [f]([\mathbf {x} ])\supseteq \{f(\mathbf {y} )|\mathbf {y} \in [\mathbf {x} ]\}}$.

Это определение расширения интервала не дает точного результата. Например, оба и являются допустимыми расширениями экспоненциальной функции. Желательны более узкие удлинения, хотя следует учитывать относительные затраты на расчет и неточность; в этом случае следует выбирать, так как он дает максимально точный результат.${\displaystyle [f]([x_{1},x_{2}])=[e^{x_{1}},e^{x_{2}}]}$${\displaystyle [g]([x_{1},x_{2}])=[{-\infty },{\infty }]}$${\displaystyle [f]}$

Для реального выражения его естественное расширение интервала достигается за счет использования интервального расширения каждого из его подвыражений, функций и операторов.

Расширение интервала Тейлора (степени ) - это функция, дифференцируемая по времени, определяемая формулой${\displaystyle k}$${\displaystyle k+1}$${\displaystyle f}$

${\displaystyle [f]([\mathbf {x} ]):=f(\mathbf {y} )+\sum _{i=1}^{k}{\frac {1}{i!}}\mathrm {D} ^{i}f(\mathbf {y} )\cdot ([\mathbf {x} ]-\mathbf {y} )^{i}+[r]([\mathbf {x} ],[\mathbf {x} ],\mathbf {y} )}$,

для некоторых , где - дифференциал порядка в точке, а - интервальное расширение остатка Тейлора${\displaystyle \mathbf {y} \in [\mathbf {x} ]}$${\displaystyle \mathrm {D} ^{i}f(\mathbf {y} )}$${\displaystyle i}$${\displaystyle f}$${\displaystyle \mathbf {y} }$${\displaystyle [r]}$

${\displaystyle r(\mathbf {x} ,\xi ,\mathbf {y} )={\frac {1}{(k+1)!}}\mathrm {D} ^{k+1}f(\xi )\cdot (\mathbf {x} -\mathbf {y} )^{k+1}.}$

Вектор лежит между и с , защищен . Обычно выбирают середину интервала и используют естественное расширение интервала для оценки остатка.${\displaystyle \xi }$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {y} }$${\displaystyle \mathbf {x} ,\mathbf {y} \in [\mathbf {x} ]}$${\displaystyle \xi }$${\displaystyle [\mathbf {x} ]}$${\displaystyle \mathbf {y} }$

Частный случай расширения степени интервала Тейлора также называется формой среднего значения .${\displaystyle k=0}$

Комплексная интервальная арифметика [ править ]

Интервал также можно определить как геометрическое место точек на заданном расстоянии от центра ^{[ требуется пояснение ],} и это определение может быть расширено от действительных чисел до комплексных чисел . ^[3] Как и в случае с вычислениями с действительными числами, вычисления с комплексными числами связаны с неопределенными данными. Итак, учитывая тот факт, что номер интервала - это реальный закрытый интервал, а комплексное число - это упорядоченная пара действительных чисел , нет причин ограничивать применение интервальной арифметики мерой неопределенностей в вычислениях с действительными числами. ^[4]Таким образом, интервальная арифметика может быть расширена с помощью комплексных интервальных чисел для определения областей неопределенности при вычислениях с комплексными числами. ^[4]

Основные алгебраические операции с вещественными интервальными числами (действительными отрезками) могут быть расширены до комплексных чисел. Поэтому неудивительно, что арифметика со сложными интервалами похожа на обычную сложную арифметику, но отличается от нее. ^[4] Можно показать, что, как и в случае с вещественной интервальной арифметикой, нет распределенности между сложением и умножением комплексных интервальных чисел, за исключением некоторых особых случаев, а обратные элементы не всегда существуют для комплексных интервальных чисел. ^[4] Два других полезных свойства обычной комплексной арифметики не соблюдаются в арифметике комплексных интервалов: аддитивные и мультипликативные свойства обычных комплексно-сопряженных чисел не выполняются для сопряженных комплексных интервалов. ^[4]

Аналогичным образом интервальная арифметика может быть расширена на другие многомерные системы счисления, такие как кватернионы и октонионы , но за счет того, что мы должны пожертвовать другими полезными свойствами обычной арифметики. ^[4]

Интервальные методы [ править ]

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

Арифметика с округленными интервалами [ править ]

Чтобы эффективно работать в реальной реализации, интервалы должны быть совместимы с вычислениями с плавающей запятой. Ранние операции были основаны на точной арифметике, но в целом методы быстрого численного решения могут быть недоступны. Диапазон значений функции для и представляют собой, например . Если такой же расчет выполняется с точностью до одной цифры, результат обычно будет . Но , таким образом, этот подход противоречил бы основным принципам интервальной арифметики, поскольку часть области была бы потеряна. Вместо этого используется решение с закругленными краями .${\displaystyle f(x,y)=x+y}$${\displaystyle x\in [0.1,0.8]}$${\displaystyle y\in [0.06,0.08]}$${\displaystyle [0.16,0.88]}$${\displaystyle [0.2,0.9]}$${\displaystyle [0.2,0.9]\not \supseteq [0.16,0.88]}$${\displaystyle f([0.1,0.8],[0.06,0.08])}$${\displaystyle [0.1,0.9]}$

Стандарт IEEE 754 для двоичной арифметики с плавающей запятой также устанавливает процедуры для реализации округления. Система, соответствующая IEEE 754, позволяет программистам округлять до ближайшего числа с плавающей запятой; альтернативы - округление до 0 (усечение), округление до положительной бесконечности (то есть вверх) или округление до отрицательной бесконечности (то есть вниз).

Таким образом, требуемое внешнее округление для интервальной арифметики может быть достигнуто путем изменения настроек округления процессора при вычислении верхнего предела (вверх) и нижнего предела (вниз). В качестве альтернативы можно добавить соответствующий небольшой интервал .${\displaystyle [\varepsilon _{1},\varepsilon _{2}]}$

Проблема зависимости [ править ]

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

В качестве иллюстрации возьмем функцию, определенную в . Значения этой функции на интервале равны. Как естественное расширение интервала, оно рассчитывается как:${\displaystyle f}$${\displaystyle f(x)=x^{2}+x.}$${\displaystyle [-1,1]}$${\displaystyle \left[-{\tfrac {1}{4}},2\right].}$

${\displaystyle [-1,1]^{2}+[-1,1]=[0,1]+[-1,1]=[-1,2],}$

который немного больше; вместо этого мы вычислили нижнюю и верхнюю границу функции по. Есть лучшее выражение, в котором переменная появляется только один раз, а именно путем переписывания как сложения и возведения в квадрат в квадратичном${\displaystyle h(x,y)=x^{2}+y}$${\displaystyle x,y\in [-1,1].}$${\displaystyle f}$${\displaystyle x}$${\displaystyle f(x)=x^{2}+x}$

${\displaystyle f(x)=\left(x+{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}.}$

Таким образом, подходящий расчет интервала

${\displaystyle \left([-1,1]+{\frac {1}{2}}\right)^{2}-{\frac {1}{4}}=\left[-{\frac {1}{2}},{\frac {3}{2}}\right]^{2}-{\frac {1}{4}}=\left[0,{\frac {9}{4}}\right]-{\frac {1}{4}}=\left[-{\frac {1}{4}},2\right]}$

и дает правильные значения.

В общем, можно показать, что точный диапазон значений может быть достигнут, если каждая переменная появляется только один раз и если она непрерывна внутри рамки. Однако не все функции можно переписать таким образом.${\displaystyle f}$

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

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

${\displaystyle {\begin{cases}x=p\\y=p\end{cases}}\qquad p\in [-1,1]}$

это точно линия между точками, и использование интервальных методов приводит к единичному квадрату. Это известно как эффект переноса .${\displaystyle (-1,-1)}$${\displaystyle (1,1).}$${\displaystyle [-1,1]\times [-1,1].}$

Линейные интервальные системы [ править ]

Линейная интервальная система состоит из расширения интервалов матрицы и вектора интервалов . Мы хотим , чтобы наималейшее кубоид , для всех векторов , которые есть пара с и удовлетворяющим${\displaystyle [\mathbf {A} ]\in [\mathbb {R} ]^{n\times m}}$${\displaystyle [\mathbf {b} ]\in [\mathbb {R} ]^{n}}$${\displaystyle [\mathbf {x} ]\in [\mathbb {R} ]^{m}}$${\displaystyle \mathbf {x} \in \mathbb {R} ^{m}}$${\displaystyle (\mathbf {A} ,\mathbf {b} )}$${\displaystyle \mathbf {A} \in [\mathbf {A} ]}$${\displaystyle \mathbf {b} \in [\mathbf {b} ]}$

${\displaystyle \mathbf {A} \cdot \mathbf {x} =\mathbf {b} }$.

Для квадратичных систем - другими словами, для - может существовать такой интервальный вектор , который охватывает все возможные решения, найденные просто с помощью интервального метода Гаусса. Это заменяет числовые операции, поскольку метод линейной алгебры, известный как исключение Гаусса, становится его интервальной версией. Однако, поскольку этот метод использует интервальные объекты и многократно в вычислениях, он может дать плохие результаты для некоторых проблем. Следовательно, использование результата интервального значения Гаусса дает только первые грубые оценки, поскольку, хотя он содержит все множество решений, он также имеет большую область за его пределами.${\displaystyle n=m}$${\displaystyle [\mathbf {x} ]}$${\displaystyle [\mathbf {A} ]}$${\displaystyle [\mathbf {b} ]}$

Грубое решение часто можно улучшить с помощью интервальной версии метода Гаусса – Зейделя . Причина этого в том, что -я строка интервального расширения линейного уравнения${\displaystyle [\mathbf {x} ]}$${\displaystyle i}$

${\displaystyle {\begin{pmatrix}{[a_{11}]}&\cdots &{[a_{1n}]}\\\vdots &\ddots &\vdots \\{[a_{n1}]}&\cdots &{[a_{nn}]}\end{pmatrix}}\cdot {\begin{pmatrix}{x_{1}}\\\vdots \\{x_{n}}\end{pmatrix}}={\begin{pmatrix}{[b_{1}]}\\\vdots \\{[b_{n}]}\end{pmatrix}}}$

может быть определено переменной, если разделение разрешено. Поэтому одновременно${\displaystyle x_{i}}$${\displaystyle 1/[a_{ii}]}$

${\displaystyle x_{j}\in [x_{j}]}$и .${\displaystyle x_{j}\in {\frac {[b_{i}]-\sum \limits _{k\not =j}[a_{ik}]\cdot [x_{k}]}{[a_{ii}]}}}$

Итак, теперь мы можем заменить на${\displaystyle [x_{j}]}$

${\displaystyle [x_{j}]\cap {\frac {[b_{i}]-\sum \limits _{k\not =j}[a_{ik}]\cdot [x_{k}]}{[a_{ii}]}}}$,

и так вектор по каждому элементу. Поскольку процедура более эффективна для матрицы с диагональным преобладанием , вместо системы часто можно попробовать умножить ее на подходящую рациональную матрицу с полученным матричным уравнением${\displaystyle [\mathbf {x} ]}$${\displaystyle [\mathbf {A} ]\cdot \mathbf {x} =[\mathbf {b} ]{\mbox{,}}}$${\displaystyle \mathbf {M} }$

${\displaystyle (\mathbf {M} \cdot [\mathbf {A} ])\cdot \mathbf {x} =\mathbf {M} \cdot [\mathbf {b} ]}$

осталось решить. Если выбрать, например, центральную матрицу , то это внешнее расширение единичной матрицы.${\displaystyle \mathbf {M} =\mathbf {A} ^{-1}}$${\displaystyle \mathbf {A} \in [\mathbf {A} ]}$${\displaystyle \mathbf {M} \cdot [\mathbf {A} ]}$

Эти методы работают хорошо, только если ширина возникающих интервалов достаточно мала. Для более широких интервалов может быть полезно использовать интервально-линейную систему на конечных (хотя и больших) линейных системах, эквивалентных действительным числам. Если все матрицы обратимы, достаточно рассмотреть все возможные комбинации (верхние и нижние) конечных точек, встречающиеся в интервалах. Возникающие проблемы могут быть решены с помощью обычных численных методов. Для определения ошибок округления по-прежнему используется интервальная арифметика.${\displaystyle \mathbf {A} \in [\mathbf {A} ]}$

Это подходит только для систем меньшего размера, так как при полностью заполненной матрице необходимо инвертировать действительные матрицы с векторами для правой части. Этот подход был разработан Иржи Роном и продолжает развиваться. ^[5]${\displaystyle n\times n}$${\displaystyle 2^{n^{2}}}$${\displaystyle 2^{n}}$

Интервальный метод Ньютона [ править ]

Интервальный вариант метода Ньютона для нахождения нулей в интервальном векторе может быть получен из расширения среднего значения. ^[6] Для неизвестного вектора, примененного к , дает${\displaystyle [\mathbf {x} ]}$${\displaystyle \mathbf {z} \in [\mathbf {x} ]}$${\displaystyle \mathbf {y} \in [\mathbf {x} ]}$

${\displaystyle f(\mathbf {z} )\in f(\mathbf {y} )+[J_{f}](\mathbf {[x]} )\cdot (\mathbf {z} -\mathbf {y} )}$.

Для нуля , то есть и, следовательно, должно удовлетворять${\displaystyle \mathbf {z} }$${\displaystyle f(z)=0}$

${\displaystyle f(\mathbf {y} )+[J_{f}](\mathbf {[x]} )\cdot (\mathbf {z} -\mathbf {y} )=0}$.

Это эквивалентно . Внешнюю оценку можно определить линейными методами.${\displaystyle \mathbf {z} \in \mathbf {y} -[J_{f}](\mathbf {[x]} )^{-1}\cdot f(\mathbf {y} )}$${\displaystyle [J_{f}](\mathbf {[x]} )^{-1}\cdot f(\mathbf {y} ))}$

На каждом этапе интервального метода Ньютона приблизительное начальное значение заменяется на, поэтому результат может быть улучшен итеративно. В отличие от традиционных методов, интервальный метод приближается к результату, содержащему нули. Это гарантирует, что результат выдаст все нули в исходном диапазоне. И наоборот, это доказывает, что в начальном диапазоне не было нулей, если шаг Ньютона дает пустое множество.${\displaystyle [\mathbf {x} ]\in [\mathbb {R} ]^{n}}$${\displaystyle [\mathbf {x} ]\cap \left(\mathbf {y} -[J_{f}](\mathbf {[x]} )^{-1}\cdot f(\mathbf {y} )\right)}$${\displaystyle f}$${\displaystyle [\mathbf {x} ]}$

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

В качестве примера рассмотрим функцию , начальный диапазон и точку . Тогда у нас есть и первый шаг Ньютона дает${\displaystyle f(x)=x^{2}-2}$${\displaystyle [x]=[-2,2]}$${\displaystyle y=0}$${\displaystyle J_{f}(x)=2\,x}$

${\displaystyle [-2,2]\cap \left(0-{\frac {1}{2\cdot [-2,2]}}(0-2)\right)=[-2,2]\cap {\Big (}[{-\infty },{-0.5}]\cup [{0.5},{\infty }]{\Big )}=[{-2},{-0.5}]\cup [{0.5},{2}]}$.

Больше шагов Ньютона используются отдельно на и . Они сходятся к сколь угодно малым интервалам вокруг и .${\displaystyle x\in [{-2},{-0.5}]}$${\displaystyle [{0.5},{2}]}$${\displaystyle -{\sqrt {2}}}$${\displaystyle +{\sqrt {2}}}$

Метод Interval Newton также можно использовать с толстыми функциями, такими как , которые в любом случае будут иметь интервальные результаты. В результате получаются интервалы, содержащие .${\displaystyle g(x)=x^{2}-[2,3]}$${\displaystyle \left[-{\sqrt {3}},-{\sqrt {2}}\right]\cup \left[{\sqrt {2}},{\sqrt {3}}\right]}$

Биссекция и обложки [ править ]

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

Покрытие интервального вектора меньшими прямоугольниками так, чтобы${\displaystyle [\mathbf {x} ]}$${\displaystyle [\mathbf {x} _{1}],\ldots ,[\mathbf {x} _{k}],}$

${\displaystyle [\mathbf {x} ]=\bigcup _{i=1}^{k}[\mathbf {x} _{i}],}$

тогда действительно для диапазона значений

${\displaystyle f([\mathbf {x} ])=\bigcup _{i=1}^{k}f([\mathbf {x} _{i}]).}$

Итак, для описанных выше расширений интервалов выполняется следующее:

${\displaystyle [f]([\mathbf {x} ])\supseteq \bigcup _{i=1}^{k}[f]([\mathbf {x} _{i}]).}$

Поскольку часто это подлинное надмножество правой части, это обычно приводит к улучшенной оценке.${\displaystyle [f]([\mathbf {x} ])}$

Такое покрытие может быть создано методом деления пополам, например, толстыми элементами вектора интервалов путем разделения в центре на два интервала и, если результат все еще не подходит, возможно дальнейшее постепенное разделение. Покрытие интервалов является результатом деления векторных элементов, что существенно увеличивает затраты на вычисление.${\displaystyle [x_{i1},x_{i2}]}$${\displaystyle [\mathbf {x} ]=([x_{11},x_{12}],\ldots ,[x_{n1},x_{n2}])}$${\displaystyle \left[x_{i1},{\tfrac {1}{2}}(x_{i1}+x_{i2})\right]}$${\displaystyle \left[{\tfrac {1}{2}}(x_{i1}+x_{i2}),x_{i2}\right].}$${\displaystyle 2^{r}}$${\displaystyle r}$

При очень широких интервалах может быть полезно разбить все интервалы на несколько подинтервалов с постоянной (и меньшей) шириной, метод, известный как измельчение . Это позволяет избежать вычислений для промежуточных этапов деления пополам. Оба метода подходят только для задач небольшой размерности.

Заявление [ править ]

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

Анализ ошибок округления [ править ]

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

Ошибка = для заданного интервала .${\displaystyle \mathrm {abs} (a-b)}$${\displaystyle [a,b]}$

Интервальный анализ дополняет, а не заменяет традиционные методы уменьшения ошибок, такие как поворот .

Анализ толерантности [ править ]

Параметры, для которых невозможно выделить точные цифры, часто возникают при моделировании технических и физических процессов. Процесс производства технических компонентов допускает определенные допуски, поэтому некоторые параметры колеблются в определенных интервалах. Кроме того, многие фундаментальные константы точно неизвестны. ^[2]

Если поведение такой системы, на которую влияют допуски, удовлетворяет, например , при и неизвестно, то набор возможных решений${\displaystyle f(\mathbf {x} ,\mathbf {p} )=0}$${\displaystyle \mathbf {p} \in [\mathbf {p} ]}$${\displaystyle \mathbf {x} }$

${\displaystyle \{\mathbf {x} \,|\,\exists \mathbf {p} \in [\mathbf {p} ],f(\mathbf {x} ,\mathbf {p} )=0\}}$,

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

Арифметика с нечеткими интервалами [ править ]

Интервальная арифметика также может использоваться с функциями принадлежности для нечетких величин, поскольку они используются в нечеткой логике . Помимо строгих операторов и возможны также промежуточные значения, которым присваиваются действительные числа . соответствует определенному членству, а не членству. Функция распределения определяет неопределенность, которую можно понимать как дополнительный интервал.${\displaystyle x\in [x]}$${\displaystyle x\not \in [x]}$${\displaystyle \mu \in [0,1]}$${\displaystyle \mu =1}$${\displaystyle \mu =0}$

Для нечеткой арифметики ^[8] рассматривается только конечное число дискретных этапов присоединения . Форма такого распределения для нечеткого значения может тогда быть представлена ​​последовательностью интервалов${\displaystyle \mu _{i}\in [0,1]}$

${\displaystyle \left[x^{(1)}\right]\supset \left[x^{(2)}\right]\supset \cdots \supset \left[x^{(k)}\right].}$

Интервал точно соответствует диапазону колебаний ступени.${\displaystyle \left[x^{(i)}\right]}$${\displaystyle \mu _{i}.}$

Соответствующее распределение для функции относительно нечетких значений и соответствующих последовательностей${\displaystyle f(x_{1},\ldots ,x_{n})}$${\displaystyle x_{1},\ldots ,x_{n}}$

${\displaystyle \left[x_{1}^{(1)}\right]\supset \cdots \supset \left[x_{1}^{(k)}\right],\ldots ,\left[x_{n}^{(1)}\right]\supset \cdots \supset \left[x_{n}^{(k)}\right]}$

можно аппроксимировать последовательностью

${\displaystyle \left[y^{(1)}\right]\supset \cdots \supset \left[y^{(k)}\right],}$

куда

${\displaystyle \left[y^{(i)}\right]=f\left(\left[x_{1}^{(i)}\right],\ldots \left[x_{n}^{(i)}\right]\right)}$

и может быть рассчитан интервальными методами. Значение соответствует результату расчета интервала.${\displaystyle \left[y^{(1)}\right]}$

Компьютерное доказательство [ править ]

Уорвик Такер использовал интервальную арифметику для решения 14-й проблемы Смейла , то есть для того, чтобы показать, что аттрактор Лоренца является странным аттрактором . ^[9] Томас Хейлз использовал интервальную арифметику для решения гипотезы Кеплера .

История [ править ]

Интервальная арифметика - не совсем новое явление в математике; он несколько раз появлялся под разными названиями в ходе истории. Например, Архимед вычислил нижнюю и верхнюю границы 223/71 < π <22/7 в 3 веке до нашей эры. Фактические вычисления с интервалами не были так популярны, как другие численные методы, и не были полностью забыты.

Правила вычисления с интервалами и другими подмножествами действительных чисел были опубликованы в 1931 году в работе Розалинд Сисели Янг. ^[10] Работа по арифметике чисел диапазона для повышения надежности цифровых систем была затем опубликована в учебнике по линейной алгебре Пола С. Дуайера 1951 года  [ de ] ; ^[11] интервалы использовались для измерения ошибок округления, связанных с числами с плавающей запятой. Подробную статью по интервальной алгебре в численном анализе опубликовал Теруо Сунага (1958). ^[12]

Рождение современной интервальной арифметики ознаменовалось появлением в 1966 году книги Рамона Мура « Интервальный анализ » . ^{[13] [14]} Идея пришла ему в голову весной 1958 года, а через год он опубликовал статью о компьютерной интервальной арифметике . ^[15] Его заслуга заключалась в том, что, исходя из простого принципа, он предоставлял общий метод автоматического анализа ошибок, а не только ошибок, возникающих в результате округления.

Независимо в 1956 году Мечислав Вармус предложил формулы для вычислений с интервалами ^[16], хотя Мур нашел первые нетривиальные приложения.

В последующие двадцать лет немецкие группы исследователей провели новаторскую работу с Ульрихом В. Кулишом ^{[1] [17]} и Гетцем Алефельдом  [ де ] ^[18] в Университете Карлсруэ, а затем и в Университете Бергише в Вуппертале . Например, Карл Никель  [ de ] исследовал более эффективные реализации, в то время как улучшенные процедуры локализации для набора решений систем уравнений были созданы, в частности, Арнольдом Ноймайером. В 1960-е годы Элдон Р. Хансензанимался расширениями интервалов для линейных уравнений, а затем внес решающий вклад в глобальную оптимизацию, включая то, что теперь известно как метод Хансена, возможно, наиболее широко используемый интервальный алгоритм. ^[6] Классические методы при этом часто имеют проблему определения наибольшего (или наименьшего) глобального значения, но могут найти только локальный оптимум и не могут найти лучшие значения; Хельмут Ратчек и Джон Джордж Рокне разработали методы ветвей и границ , которые до этого применялись только к целочисленным значениям, используя интервалы для обеспечения приложений для непрерывных значений.

В 1988 году Рудольф Лонер разработал программное обеспечение на основе Fortran для надежного решения задач начального значения с использованием обыкновенных дифференциальных уравнений . ^[19]

Журнал Reliable Computing (первоначально Interval Computations ) издается с 1990-х годов и посвящен надежности компьютерных вычислений. В качестве ведущего редактора Р. Бейкер Кирфотт помимо своей работы по глобальной оптимизации внес значительный вклад в унификацию обозначений и терминологии, используемых в интервальной арифметике. ^[20]

В последние годы работа рабочей группы COPRIN INRIA в Софии Антиполис во Франции, в частности, была сосредоточена на оценке прообразов параметризованных функций и теории робастного управления . ^[21]

Реализации [ править ]

Существует множество программных пакетов, которые позволяют разрабатывать численные приложения с использованием интервальной арифметики. ^[22] Обычно они предоставляются в виде программных библиотек. Существуют также компиляторы C ++ и Fortran, которые обрабатывают интервальные типы данных и подходящие операции в качестве расширения языка, поэтому интервальная арифметика поддерживается напрямую.

С 1967 года в Университете Карлсруэ разрабатываются расширения для научных вычислений (XSC) для различных языков программирования , таких как C ++, Fortran и Pascal . ^[23] Первой платформой была Zuse Z23 , для которой был доступен новый тип данных интервала с соответствующими элементарными операторами. В 1976 году последовал Pascal-SC , вариант Pascal для Zilog Z80, который позволил создавать быстрые и сложные процедуры для автоматической проверки результатов. Затем появился ACRITH-XSC на основе Fortran 77 для System / 370. архитектура (FORTRAN-SC), которая позже была поставлена ​​IBM. Начиная с 1991 года можно было создавать код для компиляторов C с помощью Pascal-XSC ; год спустя библиотека классов C ++ поддерживала C-XSC во многих компьютерных системах. В 1997 году все варианты XSC стали доступны под Стандартной общественной лицензией GNU . В начале 2000 года C-XSC 2.0 был выпущен под руководством рабочей группы по научным вычислениям в Университете Бергише в Вуппертале, чтобы соответствовать улучшенному стандарту C ++.

Еще одна библиотека классов C ++ была создана в 1993 году в Гамбургском технологическом университете под названием Profil / BIAS (оптимизированная во время выполнения программа для быстрой интервальной библиотеки, базовая интервальная арифметика), которая сделала обычные интервальные операции более удобными для пользователя. Он подчеркнул эффективное использование аппаратного обеспечения, портативность и независимость от конкретного представления интервалов.

Коллекция библиотек C ++ Boost содержит шаблонный класс для интервалов. Его авторы стремятся использовать интервальную арифметику на стандартном языке C ++. ^[24]

В языке программирования Frink реализована интервальная арифметика, которая обрабатывает числа произвольной точности . Программы, написанные на Frink, могут использовать интервалы без переписывания или перекомпиляции.

Gaol ^[25] - это еще одна библиотека интервальной арифметики C ++, которая уникальна тем, что предлагает реляционные интервальные операторы, используемые в программировании интервальных ограничений .

Библиотека Мура ^[26] представляет собой эффективную реализацию интервальной арифметики в C ++. Он предоставляет интервалы с конечными точками произвольной точности и основан на «концептуальной» особенности C ++.

В языке программирования Julia ^[27] есть реализация интервальной арифметики вместе с высокоуровневыми функциями, такими как поиск корня (как для вещественных, так и для комплексных функций) и программирование интервальных ограничений , через пакет ValidatedNumerics.jl. ^[28]

Кроме того, системы компьютерной алгебры, такие как FriCAS , Mathematica , Maple , Maxima (программное обеспечение) ^[29] и MuPAD , могут обрабатывать интервалы. Matlab расширение Intlab ^[30] опирается на BLAS подпрограмм, а также b4m Toolbox делает интерфейс Профиля / BIAS. ^{[30] [31]} Кроме того, Software Euler Math Toolbox включает в себя интервальную арифметику.

Библиотека функционального языка OCaml была написана на ассемблере и C. ^[32]

Стандарт IEEE 1788 [ править ]

Стандарт интервальной арифметики IEEE Std 1788-2015 был утвержден в июне 2015 года. ^[33] Две эталонные реализации доступны бесплатно. ^[34] Они были разработаны членами рабочей группы по стандарту: библиотека libieeep1788 ^[35] для C ++ и пакет interval ^[36] для GNU Octave .

Минимальное подмножество стандарта, IEEE Std 1788.1-2017, было одобрено в декабре 2017 года и опубликовано в феврале 2018 года. Это должно быть проще в реализации и может ускорить производство реализаций. ^[37]

Конференции и семинары [ править ]

Ежегодно в мире проводится несколько международных конференций или семинаров. Основной конференцией, вероятно, является SCAN (Международный симпозиум по научным вычислениям, компьютерной арифметике и проверенным численным вычислениям), но есть также SWIM (небольшой семинар по интервальным методам), PPAM (Международная конференция по параллельной обработке и прикладной математике), REC (Международный Практикум по надежным инженерным вычислениям.

См. Также [ править ]

• Аффинная арифметика
• ИНТЛАБ (Интервальная лаборатория)
• Автоматическая дифференциация
• Многосеточный метод
• Моделирование Монте-Карло
• Интервальный конечный элемент
• Нечеткое число
• Значимые фигуры
• Карлсруэ Точная арифметика (KAA)
• Unum

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Хейс, Брайан (ноябрь – декабрь 2003 г.). «Осознанный интервал» (PDF) . Американский ученый . Сигма Си. 91 (6): 484–488. DOI : 10.1511 / 2003.6.484 .
• Такер, Уорик (2011). Подтвержденные числа: краткое введение в строгие вычисления . Издательство Принстонского университета .

Внешние ссылки [ править ]

• Интервальная арифметика (Wolfram Mathworld)
• Подтвержденные цифры для пешеходов
• Интервальные методы от Арнольда Ноймайера , Венский университет

Мастерские [ править ]

• SWIM (Летний семинар по интервальным методам)
• Международная конференция по параллельной обработке и прикладной математике

Библиотеки [ править ]

• ИНТЛАБ, Институт надежных вычислений , Гамбургский технологический университет
• Арифметика с мячом Йориса ван дер Хувена
• kv - библиотека C ++ для проверенных численных вычислений
  • kv на GitHub
• Arb - C-библиотека для арифметики с мячом произвольной точности
  • arb на GitHub
• JuliaIntervals на GitHub