Аффинная арифметика

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

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

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

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

В аффинной арифметике каждое входное или вычисленное количество x представлено формулой, где - известные числа с плавающей запятой и символьные переменные, значения которых, как известно, лежат только в диапазоне [-1, + 1].${\ 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}}$

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

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

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

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

Аффинные операции [ править ]

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

Неаффинные операции [ править ]

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

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

Объединение операций [ править ]

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

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

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

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

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

Модель аффинной проекции [ править ]

Аффинную арифметику можно рассматривать в матричной форме следующим образом. Пусть будут все входные и вычисленные количества, используемые в какой-то момент во время вычисления. Аффинные формы для этих величин могут быть представлены одной матрицей коэффициентов A и вектором b , где element - коэффициент символа в аффинной форме ; и является независимым термином этой формы. Тогда общий диапазон величин - то есть диапазон точки - это изображение гиперкуба аффинным отображением от до, определяемое с помощью .${\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}$

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

Упрощение аффинной формы [ править ]

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

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

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

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

Векторная реализация [ править ]

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

Реализация разреженных векторов [ править ]

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

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

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

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

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

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