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

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. Найдите источники: «Интервальная арифметика»  – Новости  · газеты  · книги  · ученый  · 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]

Пример

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

В качестве примера рассмотрим расчет индекс массы тела (ИМТ) и оценка того, есть ли у человека лишний вес. ИМТ рассчитывается как масса тела человека в килограммах, деленная на квадрат его роста в метрах. Весы для ванной могут иметь разрешение в один килограмм. Промежуточные значения не различаются - например, 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. Поскольку функция монотонно возрастает, мы заключаем, что истинный ИМТ находится в диапазоне ${ displaystyle [24.537,24.846]}$. Поскольку весь диапазон составляет менее 25, что является порогом между нормальным и избыточным весом, мы заключаем, что мужчина имеет нормальный вес.

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

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

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

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

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

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

${ displaystyle { frac {[79.5,80.5]} {[1.785,1.795] ^ {2}}} substeq [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 х звезда у}$, куда ${ 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 х звезда у}$ определено для всех ${ Displaystyle х в [х_ {1}, х_ {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 {align} { 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] substeq [- infty , infty] && mathrm {if} ; 0 in (y_ {1}, y_ {2}) end {align}}}$

В последнем случае теряется полезная информация об исключении ${ Displaystyle (1 / г_ {1}, 1 / г_ {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].}$ Соответствующие многоинтервальная арифметика поддерживает набор (обычно непересекающихся) интервалов, а также обеспечивает объединение перекрывающихся интервалов.^[2]

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

Интервальное умножение часто требует только двух умножений. Если ${ 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.}$

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

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

${ Displaystyle е (а, б, х) = ([1,2] cdot [2,3]) + [5,7] = [1 cdot 2,2 cdot 3] + [5,7] = [7,13]}$.

Обозначение

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

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

${ displaystyle [ mathbb {R}]: = left {, [x_ {1}, x_ {2}] , | , x_ {1} leq x_ {2} { text {и} } 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}) leq f (y_ {2}) quad { text {or}} quad f (y_ {1}) geq f (y_ {2}).}$

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

${ Displaystyle е ([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 [х_ {1}, х_ {2}]}$ и ${ displaystyle a> 1,}$
• Странные полномочия: ${ displaystyle [x_ {1}, x_ {2}] ^ {n} = [x_ {1} ^ {n}, x_ {2} ^ {n}]}$, для нечетных ${ Displaystyle п in mathbb {N}.}$

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

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

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

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

${ Displaystyle [е] ([ mathbf {x}]) supseteq {е ( mathbf {y}) | mathbf {y} in [ mathbf {x}] }}$.

Это определение расширения интервала не дает точного результата. Например, оба ${ displaystyle [f] ([x_ {1}, x_ {2}]) = [e ^ {x_ {1}}, e ^ {x_ {2}}]}$ и ${ Displaystyle [г] ([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} в [ mathbf {x}]}$,куда ${ Displaystyle mathrm {D} ^ {я} е ( 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]

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

Эта секция нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален. (Февраль 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

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

Чтобы эффективно работать в реальной реализации, интервалы должны быть совместимы с вычислениями с плавающей запятой. Ранние операции были основаны на точной арифметике, но в целом методы быстрого численного решения могут быть недоступны. Диапазон значений функции ${ Displaystyle е (х, у) = х + у}$за ${ Displaystyle х в [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 е (х) = х ^ {2} + х.}$ Значения этой функции на интервале ${ displaystyle [-1,1]}$ находятся ${ displaystyle left [- { tfrac {1} {4}}, 2 right].}$ В качестве естественного удлинения интервала он рассчитывается как:

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

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

${ 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 {case} 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}] в [ mathbb {R}] ^ {п раз m}}$ и интервальный вектор ${ Displaystyle [ mathbf {b}] в [ mathbb {R}] ^ {n}}$. Мы хотим самый маленький кубоид ${ Displaystyle [ mathbf {x}] в [ 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 п = м}$ - может быть такой интервальный вектор ${ 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}]} { [а_ {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}]}$ обратимы, достаточно рассмотреть все возможные комбинации (верхние и нижние) концов, встречающиеся в интервалах. Возникающие проблемы могут быть решены с помощью обычных численных методов. Для определения ошибок округления по-прежнему используется интервальная арифметика.

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

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

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

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

${ Displaystyle е ( mathbf {z}) в е ( mathbf {y}) + [J_ {f}] ( mathbf {[x]}) cdot ( mathbf {z} - mathbf {y })}$.

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

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

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

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

${ 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 г (х) = х ^ {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 [е] ([ mathbf {х}])}$ часто подлинный суперсет правой части это обычно приводит к улучшенной оценке.

Такое покрытие может быть создано метод деления пополам такие как толстые элементы ${ 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 {абс} (а-б)}$ для заданного интервала ${ Displaystyle [а, б]}$.

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

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

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

Если поведение такой системы, на которую влияют допуски, удовлетворяет, например, ${ Displaystyle е ( 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 х в [х]}$ и ${ Displaystyle х не в [х]}$, возможны также промежуточные значения, к которым действительные числа ${ Displaystyle му ин [0,1]}$ назначены. ${ displaystyle mu = 1}$ соответствует определенному членству, а ${ displaystyle mu = 0}$ не является членством. Функция распределения определяет неопределенность, которую можно понимать как дополнительный интервал.

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

${ Displaystyle влево [х ^ {(1)} вправо] supset left [x ^ {(2)} right] supset cdots supset left [x ^ {(k)} right] .}$

Интервал ${ Displaystyle влево [х ^ {(я)} вправо]}$ точно соответствует диапазону колебаний ступени ${ 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 влево [у ^ {(1)} вправо]}$ соответствует результату расчета интервала.

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

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

История

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

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

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

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

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

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

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

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

Реализации

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

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

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

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

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

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

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

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

Кроме того, системы компьютерной алгебры, такие как FriCAS, Mathematica, Клен, Maxima (программное обеспечение)^[29] и MuPAD, может обрабатывать интервалы. А Matlab расширение Intlab^[30] опирается на BLAS подпрограмм, а Toolbox b4m создает интерфейс Profil / BIAS.^[30][31] Кроме того, программное обеспечение Набор инструментов "Математика Эйлера" включает интервальную арифметику.

Библиотека функционального языка 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 (Международный Практикум по надежным инженерным вычислениям.

Смотрите также

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

Рекомендации

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

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

внешняя ссылка

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

Мастерские

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

Библиотеки

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