Аффинная арифметика - Affine arithmetic

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

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

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

Определение

В аффинной арифметике каждое входное или вычисленное количество Икс представлен формулой${ displaystyle x = x_ {0} + x_ {1} epsilon _ {1} + x_ {2} epsilon _ {2} + {}}$${ displaystyle cdots}$${ displaystyle {} + x_ {n} epsilon _ {n}}$куда ${ displaystyle x_ {0}, x_ {1}, x_ {2},}$${ displaystyle dots,}$${ displaystyle x_ {n}}$ известные числа с плавающей запятой, и ${ displaystyle epsilon _ {1}, epsilon _ {2}, epsilon _ {n}}$ являются символьными переменными, значения которых, как известно, лежат только в диапазоне [-1, + 1].

Так, например, величина Икс которая, как известно, лежит в диапазоне [3,7], может быть представлена ​​аффинной формой ${ displaystyle x = 5 + 2 epsilon _ {k}}$, для некоторых k. Наоборот, форма ${ displaystyle x = 10 + 2 epsilon _ {3} -5 epsilon _ {8}}$ следует, что соответствующая величина Икс лежит в диапазоне [3,17].

Совместное использование символа ${ displaystyle epsilon _ {j}}$ среди двух аффинных форм ${ displaystyle x}$, ${ displaystyle y}$ следует, что соответствующие величины Икс, Y частично зависимы, в том смысле, что их совместный диапазон меньше, чем Декартово произведение их отдельных диапазонов. Например, если ${ displaystyle x = 10 + 2 epsilon _ {3} -6 epsilon _ {8}}$ и ${ displaystyle y = 20 + 3 epsilon _ {4} +4 epsilon _ {8}}$, то отдельные диапазоны Икс и Y равны [2,18] и [13,27], но совместный диапазон пары (Икс,Y) это шестиугольник с углами (2,27), (6,27), (18,19), (18,13), (14,13), (2,21) - что является собственным подмножеством прямоугольник [2,18]×[13,27].

Аффинные арифметические операции

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

Аффинные операции

Например, учитывая аффинные формы ${ displaystyle x, y}$ за Икс и Y, можно получить аффинную форму ${ displaystyle z}$ за Z = Икс + Y просто добавив формы, то есть установив ${ displaystyle z_ {j}}$ ${ displaystyle gets}$ ${ displaystyle x_ {j} + y_ {j}}$ для каждого j. Аналогичным образом можно вычислить аффинную форму ${ displaystyle z}$ за Z = ${ displaystyle alpha}$Икс, куда ${ displaystyle alpha}$ - известная константа, задав ${ displaystyle z_ {j}}$ ${ displaystyle gets}$ ${ displaystyle alpha x_ {j}}$ для каждого j. Это обобщается на произвольные аффинные операции, такие как Z = ${ displaystyle alpha}$Икс + ${ displaystyle beta}$Y + ${ displaystyle gamma}$.

Неаффинные операции

Неаффинная операция ${ displaystyle Z}$ ${ displaystyle gets}$ ${ Displaystyle F (X, Y,}$${ displaystyle dots}$${ displaystyle)}$, как умножение ${ displaystyle Z}$ ${ displaystyle gets}$ ${ displaystyle XY}$ или же ${ displaystyle Z}$ ${ displaystyle gets}$ ${ Displaystyle грех (Х)}$, не может быть выполнено точно, так как результат не был бы аффинной формой ${ displaystyle epsilon _ {я}}$. В этом случае следует взять подходящую аффинную функцию грамм это приблизительно F до первого порядка в диапазонах, подразумеваемых ${ displaystyle x}$ и ${ displaystyle y}$; и вычислить ${ displaystyle z}$ ${ displaystyle gets}$ ${ Displaystyle G (х, у,}$${ displaystyle dots}$${ displaystyle) + z_ {k} epsilon _ {k}}$, куда ${ displaystyle z_ {k}}$ - верхняя граница абсолютной ошибки ${ displaystyle | F-G |}$ в этом диапазоне, и ${ displaystyle epsilon _ {k}}$ это новая символьная переменная, не встречающаяся ни в какой предыдущей форме.

Форма ${ displaystyle z}$ затем дает гарантированное вложение для количества Z; кроме того, аффинные формы ${ displaystyle x, y,}$${ displaystyle dots}$${ displaystyle, z}$ совместно обеспечить гарантированное ограждение точки (Икс,Y,...,Z), который часто намного меньше, чем декартово произведение диапазонов отдельных форм.

Объединение операций

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

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

Ошибки округления

Чтобы обеспечить гарантированное вложение, аффинные арифметические операции должны учитывать ошибки округления при вычислении результирующих коэффициентов. ${ displaystyle z_ {j}}$. Этого нельзя сделать путем округления каждого ${ displaystyle z_ {j}}$ в определенном направлении, потому что любое такое округление исказит зависимости между аффинными формами, которые разделяют символ ${ displaystyle epsilon _ {j}}$. Вместо этого необходимо вычислить верхнюю границу ${ displaystyle delta _ {j}}$ к ошибке округления каждого ${ displaystyle z_ {j}}$, и добавьте все эти ${ displaystyle delta _ {j}}$ к коэффициенту ${ displaystyle z_ {k}}$ нового символа ${ displaystyle epsilon _ {k}}$ (округления). Таким образом, из-за ошибок округления даже аффинные операции, такие как Z = ${ displaystyle alpha}$Икс и Z = Икс + Y добавит дополнительный срок ${ displaystyle z_ {k} epsilon _ {k}}$.

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

Модель аффинной проекции

Аффинную арифметику можно рассматривать в матричной форме следующим образом. Позволять ${ displaystyle X_ {1}, X_ {2},}$${ displaystyle dots,}$${ displaystyle X_ {m}}$ быть всеми входными и вычисленными величинами, используемыми в какой-то момент во время вычисления. Аффинные формы для этих величин могут быть представлены одной матрицей коэффициентов А и вектор б, где элемент ${ displaystyle A_ {i, j}}$ коэффициент символа ${ displaystyle epsilon _ {j}}$ в аффинной форме ${ displaystyle X_ {i}}$; и ${ displaystyle b_ {i}}$ является независимым членом этой формы. Тогда общий диапазон величин, то есть диапазон точки ${ displaystyle (X_ {1}, X_ {2},}$${ displaystyle dots,}$${ displaystyle X_ {m})}$ - изображение гиперкуба ${ Displaystyle U ^ {n} = [- 1, + 1] ^ {n}}$ по аффинному отображению из ${ displaystyle U ^ {n}}$ к ${ displaystyle R ^ {m}}$ определяется ${ displaystyle epsilon}$ ${ displaystyle to}$ ${ displaystyle A epsilon + b}$.

Диапазон этого аффинного отображения равен зонотоп ограничивая совместный диапазон величин ${ displaystyle X_ {1}, X_ {2},}$${ displaystyle dots,}$${ displaystyle X_ {m}}$. Таким образом, можно сказать, что AA - это «зонотопическая арифметика». Каждый шаг AA обычно влечет за собой добавление в матрицу еще одной строки и еще одного столбца. А.

Аффинное упрощение формы

Поскольку каждая операция AA обычно создает новый символ ${ displaystyle epsilon _ {k}}$, количество членов в аффинной форме может быть пропорционально количеству операций, используемых для его вычисления. Таким образом, часто необходимо применять этапы «уплотнения символов», когда два или более символа ${ displaystyle epsilon _ {k}}$ заменяются меньшим набором новых символов. Геометрически это означает замену сложного зонотопа п более простым зонотопом Q что его окружает. Эта операция может быть выполнена без нарушения свойства аппроксимации первого порядка конечного зонотопа.

Выполнение

Реализация матрицы

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

Векторная реализация

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

Реализация разреженного вектора

При довольно длительных вычислениях набор «живых» величин (которые будут использоваться в будущих вычислениях) намного меньше, чем набор всех вычисленных величин; и то же самое для набора "живых" символов ${ displaystyle epsilon _ {j}}$. В этой ситуации реализации матрицы и вектора слишком расточительны по времени и пространству.

В таких ситуациях следует использовать редкий выполнение. А именно, каждая аффинная форма хранится в виде списка пар (j,${ displaystyle x_ {j}}$), содержащий только слагаемые с ненулевым коэффициентом ${ displaystyle x_ {j}}$. Для эффективности термины следует отсортировать в порядке j. Это представление несколько усложняет операции AA; однако стоимость каждой операции становится пропорциональной количеству ненулевых членов, появляющихся в операндах, вместо общего количества использованных символов.

Это представление, используемое LibAffa.

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

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

• [1] Страница Столфи об АА.
• [2] LibAffa, реализация аффинной арифметики в LGPL.
  • либаффа на GitHub
• [3] ASOL, метод ветвей и отсечения для поиска всех решений систем нелинейных уравнений с использованием аффинной арифметики
• [4] YalAA, объектно-ориентированная библиотека шаблонов на основе C ++ для аффинной арифметики (AA).
• кв на GitHub (C ++ библиотека, которая может использовать аффинную арифметику)