Введение

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

Аффины

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

Сродственные операции

Например, если заданы аффинные формы для X и Y, то аффинную форму для Z = X + Y можно получить, просто сложив эти формы, то есть, установив для каждого j. Аналогично, можно вычислить аффинную форму для Z = X, где является известной константой, установив для каждого j. Это обобщается на произвольные аффинные операции, такие как Z = X + Y + .

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

Неаффинную операцию, такую как умножение или деление, нельзя выполнить точно, поскольку результат не будет аффинной формой от X. В этом случае следует выбрать подходящую аффинную функцию G, которая аппроксимирует F с точностью до первого порядка в диапазонах, задаваемых условиями x и y; и вычислить G + ε, где ε является верхней границей абсолютной погрешности в этом диапазоне, а ε – новая символическая переменная, не входящая ни в одну из предыдущих форм. Тогда эта форма дает гарантированное включение для величины Z; более того, аффинные формы совместно обеспечивают гарантированное включение для точки (X, Y, ε, Z), которое часто значительно меньше, чем декартово произведение диапазонов отдельных форм.

Операции по цепочке

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

Ошибки в окружном отборе

Для обеспечения гарантированного охвата, аффинные арифметические операции должны учитывать ошибки округления при вычислении результирующих коэффициентов. Это нельзя сделать, округляя каждое значение в определенном направлении, поскольку любое такое округление исказит зависимости между аффинными формами, использующими один и тот же символ. Вместо этого необходимо вычислить верхнюю границу ошибки округления для каждого значения и добавить все эти границы к коэффициенту нового символа (округляя вверх). Таким образом, из-за ошибок округления даже простые аффинные операции, такие как Z = X и Z = X + Y, добавят дополнительный член. Учет ошибок округления увеличивает сложность кода и время выполнения аффинных арифметических операций. В приложениях, где эти ошибки несущественны (поскольку они незначительны по сравнению с неопределенностями входных данных и/или ошибками линеаризации), можно использовать упрощенную библиотеку аффинной арифметики, не реализующую контроль ошибок округления.

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

Аффиновую арифметику можно рассматривать в матричной форме следующим образом. Пусть все входные и вычисленные величины, используемые в какой-то момент вычисления, обозначены как . Аффинные формы этих величин могут быть представлены единой матрицей коэффициентов A и вектором b, где элемент является коэффициентом символа в аффинной форме величины ; а – независимым членом этой формы. Тогда совместная область определения величин – то есть область определения точки – является образом гиперкуба при аффинном преобразовании из в , определяемом выражением . Область определения этого аффинного преобразования представляет собой зонотоп, ограничивающий совместную область определения величин . Таким образом, можно сказать, что АА является "зонотоповой арифметикой". Каждый шаг АА обычно включает добавление одной строки и одного столбца к матрице A.

Упрощение аффиновой формы

Поскольку каждая операция АА обычно создает новый символ, количество слагаемых в аффинной форме может быть пропорционально числу операций, использованных для её вычисления. Таким образом, часто необходимо применять шаги "конденсации символов", при которых два или более символов заменяются меньшим набором новых символов. Геометрически это означает замену сложного зонотопа P более простым зонотопом Q, содержащим его. Эта операция может быть выполнена без потери свойства приближения первого порядка конечного зонотопа.

Внедрение матрицы

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

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

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

Реализация спарсового вектора

При достаточно длительных вычислениях множество "активных" величин (которые будут использованы в последующих вычислениях) значительно меньше, чем множество всех вычисленных величин; и то же самое справедливо для множества "активных" символов. В этой ситуации матричные и векторные реализации неэффективно расходуют время и память. В таких случаях следует использовать разреженное представление. А именно, каждая аффинная форма хранится в виде списка пар (j, c<sub>j</sub>), содержащего только слагаемые с ненулевым коэффициентом. Для повышения эффективности слагаемые должны быть отсортированы по возрастанию j. Данное представление несколько усложняет операции над аффинными формами, однако стоимость каждой операции становится пропорциональной числу ненулевых слагаемых в операндах, а не общему числу символов, использованных на данный момент. Именно такое представление используется в LibAffa.