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

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

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

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

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

Введение

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

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

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

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

Пример

Индекс массы тела человека ростом 1,80 м по отношению к массе тела м (в килограммах)

человека Рассмотрим расчет индекса массы тела (ИМТ). ИМТ рассчитывается как масса тела человека в килограммах, деленная на квадрат его роста в метрах. Предположим, человек пользуется весами с точностью до одного килограмма, на которых невозможно различить промежуточные значения, а истинный вес округляется до ближайшего целого числа. Например, 79,6 кг и 80,3 кг неотличимы, поскольку весы могут отображать значения только с точностью до килограмма. Маловероятно, что когда весы показывают 80 кг, человек имеет вес ровно 80,0 кг. Таким образом, весы, показывающие 80 кг, показывают вес от 79,5 кг до 80,5 кг, или интервал $[79.5,80.5)$.

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

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

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

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

Индекс массы тела для разного веса в зависимости от роста L (в метрах)

Рост и масса тела влияют на значение ИМТ. Хотя в приведенном выше примере учитывались только различия в весе, рост также подвержен неопределенности. Измерения высоты в метрах обычно округляются до ближайшего сантиметра: зарегистрированное измерение 1,79 метра представляет собой высоту в интервале $[1.785,1.795)$. Поскольку ИМТ равномерно увеличивается по отношению к весу и уменьшается по отношению к росту, интервал ошибок можно рассчитать, подставив самые низкие и самые высокие значения каждого интервала, а затем выбрав самый низкий и самый высокий результаты в качестве границ. Следовательно, ИМТ должен существовать в интервале

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

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

Интервальные операторы

Бинарная операция $\star$ на двух интервалах, таких как сложение или умножение, определяется формулой

$[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}]\}.$

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

$[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],$

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

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

• Добавление : $$[x_{1},x_{2}]+[y_{1},y_{2}]=[x_{1}+y_{1},x_{2}+y_{2}]$$
• Вычитание : $$[x_{1},x_{2}]-[y_{1},y_{2}]=[x_{1}-y_{2},x_{2}-y_{1}]$$
• Умножение : $$[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}\}]$$
• Разделение : $${\frac {[x_{1},x_{2}]}{[y_{1},y_{2}]}}=[x_{1},x_{2}]\cdot {\frac {1}{[y_{1},y_{2}]}},$$ где $${\begin{aligned}{\frac {1}{[y_{1},y_{2}]}}&=\left[{\tfrac {1}{y_{2}}},{\tfrac {1}{y_{1}}}\right]&&{\textrm {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 ]&&{\textrm {if}}\;0\in (y_{1},y_{2})\end{aligned}}$$

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

Умножение положительных интервалов

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

$[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.$

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

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

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

Обозначения

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

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

$[\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\}$

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

Элементарные функции

Значения монотонной функции

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

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

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

$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].$

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

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

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

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

Интервальные расширения общих функций

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

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

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

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

( Расширение интервала Тейлора степени $k$ ) представляет собой $k+1$ раз дифференцируемая функция $f$ определяется

$[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} ),$

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

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

Форма среднего значения

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

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

Сложная интервальная арифметика

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

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

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

Интервальные методы

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

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

Внешние границы на разном уровне округления

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

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

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

Проблема зависимости

Приблизительная оценка диапазона значений

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

Независимая обработка каждого появления переменной

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

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

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

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

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

$\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]$

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

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

Эффект обертывания

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

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

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

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

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

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

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

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

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

${\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}}$

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

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

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

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

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

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

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

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

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

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

Уменьшение области поиска в интервале шага Ньютона в «толстых» функциях.

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

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

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

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

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

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

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

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

$[-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}]$.

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

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

Бисекция и крышки

Грубая оценка (бирюзовый) и уточненная оценка за счет «измельчения» (красный)

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

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

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

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

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

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

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

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

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

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

Приложение

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

Анализ ошибок округления

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

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

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

Анализ толерантности

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

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

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

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

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

Аппроксимация нормального распределения последовательностью интервалов

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

Для нечеткой арифметики только конечное число дискретных стадий принадлежности $\mu _{i}\in [0,1]$ считаются. Тогда форму такого распределения для нечеткой величины можно представить последовательностью интервалов.

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

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

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

$\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]$

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

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

где

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

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

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

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

История

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

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

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

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

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

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

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

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

Реализации

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

С 1967 года расширения для научных вычислений разрабатываются в Университете Карлсруэ (XSC) для различных языков программирования , таких как C++, Fortran и Pascal . Первой платформой стала 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 General Public License . В начале 2000 года под руководством рабочей группы по научным вычислениям Бергишского университета в Вуппертале был выпущен C-XSC 2.0 , соответствующий улучшенному стандарту C++.

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

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

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

ТЮРЬМА — еще одна библиотека интервальной арифметики C++, уникальная тем, что предлагает операторы реляционных интервалов, используемые при программировании с интервальными ограничениями .

Библиотека Мура — эффективная реализация интервальной арифметики в C++. Он предоставляет интервалы с конечными точками произвольной точности и основан на концепциях C++ .

Язык Джулия. программирования имеет реализацию интервальной арифметики наряду с функциями высокого уровня, такими как поиск корня (как для вещественных, так и для комплексных функций) и программирование интервальных ограничений , через пакет ValidatedNumerics.jl.

Кроме того, системы компьютерной алгебры, такие как FriCAS , Mathematica , Maple , Maxima (программное обеспечение) и MuPAD могут обрабатывать интервалы. Matlab ​ Расширение Intlab основан на процедурах BLAS , а Toolbox b4m создает интерфейс Profil/BIAS. Более того, Software Euler Math Toolbox включает в себя интервальную арифметику.

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

Стандарт IEEE 1788

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

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

Конференции и семинары

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

См. также

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

Дальнейшее чтение

• Хейс, Брайан (ноябрь – декабрь 2003 г.). «Осознанный интервал» (PDF) . Американский учёный . 91 (6). Сигма Си: 484–488. дои : 10.1511/2003.6.484 .
• Такер, Уорик (2011). Проверенные цифры: краткое введение в строгие вычисления . Издательство Принстонского университета . ISBN  978-1400838974 .
• Випперманн, Ханс-Вильм (1968) [15 июня 1967, 1966]. «Определение связанных чисел в Триплекс-АЛГОЛ». Вычисление (на немецком языке). 3 (2). Карлсруэ, Германия: Springer: 99–109. дои : 10.1007/BF02277452 . ISSN   0010-485X . S2CID   36685400 . (11 страниц) (Примечание. О Triplex-ALGOL Karlsruhe , реализации ALGOL 60 (1963) с поддержкой триплексных чисел.)

Внешние ссылки

• Интервальная арифметика (Wolfram Mathworld)
• Проверенные цифры для пешеходов
• Интервальные методы от Арнольда Ноймайера , Венский университет
• SWIM (Летний семинар по интервальным методам)
• Международная конференция по параллельной обработке и прикладной математике
• INTLAB, Институт надежных вычислений. Архивировано 30 января 2020 г. в Wayback Machine , Гамбургский технологический университет.
• Шаровая арифметика Йориса ван дер Хувена.
• kv — библиотека C++ для проверенных численных вычислений
  • кв на GitHub
• Arb - библиотека C для шаровой арифметики произвольной точности.
  • вилка на GitHub
• JuliaIntervals на GitHub