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

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

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

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

Определение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реализация

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

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

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

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

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

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

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

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

Ссылки

• Л. Х. де Фигейредо и Дж. Столфи (2004) «Аффинная арифметика: концепции и приложения». Численные алгоритмы 37 (1–4), 147–158.
• Дж. Л. Д. Комба и Дж. Столфи (1993), «Аффинная арифметика и ее приложения к компьютерной графике». Учеб. SIBGRAPI'93 — VI Бразильский симпозиум по компьютерной графике и обработке изображений (Ресифи, Бразилия) , 9–18.
• Л. Х. де Фигейредо и Дж. Столфи (1996), «Адаптивное перечисление неявных поверхностей с помощью аффинной арифметики». Форум компьютерной графики , 15 5 , 287–296.
• В. Хайдрих (1997), «Сборник аффинных арифметических версий общих математических библиотечных функций». Технический отчет 1997-3, Университет Эрланген-Нюрнберг.
• М. Кашиваги (1998), «Алгоритм решения всех задач с использованием аффинной арифметики». NOLTA'98 — Международный симпозиум 1998 года по нелинейной теории и ее приложениям (Кран-Монтана, Швейцария) , 14–17.
• Л. Эгициано, Н. Фемиа и Г. Спаньоло (1998), «Новые подходы к истинной оценке наихудшего случая в анализе толерантности и чувствительности схемы - Часть II: Расчет внешнего решения с использованием аффинной арифметики». Учеб. COMPEL'98 — 6-й семинар «Компьютер в силовой электронике» (Вилла Эрба, Италия) , 19–22.
• В. Гейдрих, Ф. Слюсаллек и Х.-П. Зайдель (1998), «Выборка процедурных шейдеров с использованием аффинной арифметики». Транзакции ACM по графике , 17 3 , 158–176.
• Ф. Мессин и А. Махфуди (1998), «Использование аффинной арифметики в алгоритмах интервальной оптимизации для решения задач многомерного масштабирования». Учеб. SCAN'98 — Международный симпозиум IMACS/GAMM по научным вычислениям, компьютерной арифметике и проверенным числам (Будапешт, Венгрия) , 22–25.
• А. де Кусатис-младший, Л. Х. Фигейредо и М. Гаттасс (1999), «Интервальные методы для поверхностей отбрасывания лучей с аффинной арифметикой». Учеб. SIBGRAPI'99 — 12-й Бразильский симпозиум по компьютерной графике и обработке изображений , 65–71.
• К. Бюлер и В. Барт (2000), «Новый алгоритм пересечения параметрических поверхностей, основанный на линейных интервальных оценках». Учеб. СКАН 2000 / Интервал 2000 — 9-й Международный симпозиум GAMM-IMACS по научным вычислениям, компьютерной арифметике и проверенным цифровым данным , ???–???.
• И. Войкулеску, Дж. Бертольд, А. Бойер, Р. Р. Мартин и К. Чжан (2000), «Интервальная и аффинная арифметика для поверхностного расположения полиномов степенной формы и полиномов Бернштейна». Учеб. Математика поверхностей IX , 410–423. Спрингер, ISBN   1-85233-358-8 .
• К. Чжан и Р.Р. Мартин (2000), «Полиномиальная оценка с использованием аффинной арифметики для построения кривых». Учеб. конференции Eurographics UK 2000 , 49–56. ISBN   0-9521097-9-4 .
• Д. Мичелуччи (2000), «Надежные вычисления для динамических систем». Учеб. СКАН 2000 / Интервал 2000 — 9-й Международный симпозиум GAMM-IMACS по научным вычислениям, компьютерной арифметике и проверенным цифровым данным , ???–???.
• Н. Фемиа и Г. Спаньоло (2000), «Истинный анализ толерантности схемы для наихудшего случая с использованием генетического алгоритма и аффинной арифметики - Часть I». Транзакции IEEE в схемах и системах , 47 9 , 1285–1296.
• Р. Мартин, Х. Шу, И. Войкулеску и Г. Ван (2001), «Сравнение оболочки Бернштейна и методов аффинной арифметики для рисования алгебраических кривых». Учеб. Неопределенность в геометрических вычислениях , 143–154. Академическое издательство Клувер, ISBN   0-7923-7309-X .
• А. Бойер, Р. Мартин, Х. Шу и И. Войкулеску (2001), «Аффинные интервалы в средстве геометрического моделирования CSG». Учеб. Неопределенность в геометрических вычислениях , 1–14. Академическое издательство Клувер, ISBN   0-7923-7309-X .
• Т. Кикучи и М. Кашиваги (2001), «Устранение областей несуществования решения нелинейных уравнений с использованием аффинной арифметики». Учеб. NOLTA'01 — 2001 Международный симпозиум по нелинейной теории и ее приложениям .
• Т. Мията и М. Кашиваги (2001), «Об оценке диапазона полиномов аффинной арифметики». Учеб. NOLTA'01-2001 Международный симпозиум по нелинейной теории и ее приложениям .
• Ю. Канадзава и С. Оиси (2002), «Численный метод доказательства существования решений нелинейных ОДУ с использованием аффинной арифметики». Учеб. SCAN'02 — 10-й Международный симпозиум GAMM-IMACS по научным вычислениям, компьютерной арифметике и проверенным числам .
• Х. Шу, Р.Р.Мартин, И. Войкулеску, А. Бойер и Г. Ван (2002), «Аффинная арифметика в матричной форме для полиномиальной оценки и рисования алгебраических кривых». Прогресс естествознания , 12 1 , 77–81.
• А. Лемке, Л. Хедрич и Э. Барк (2002), «Определение размеров аналоговых схем на основе формальных методов с использованием аффинной арифметики». Учеб. ICCAD-2002 — Международная конференция по автоматизированному проектированию , 486–489.
• Ф. Мессин (2002), «Расширения аффинной арифметики: применение к неограниченной глобальной оптимизации». Журнал универсальной информатики , 8 11 , 992–1015.
• К. Бюлер (2002), «Неявные линейные интервальные оценки». Учеб. 18-я весенняя конференция по компьютерной графике (Будмерице, Словакия) , 123–132. АКМ Пресс, ISBN   1-58113-608-0 .
• Л. Х. де Фигейредо, Дж. Столфи и Л. Велью (2003), «Аппроксимация параметрических кривых ленточными деревьями с использованием аффинной арифметики». Форум компьютерной графики , 22 2 , 171–179.
• К.Ф. Фанг, Т. Чен и Р. Рутенбар (2003), «Анализ ошибок с плавающей запятой на основе аффинной арифметики». Учеб. 2003 Международная конференция. по акустике, речи и обработке сигналов .
• А. Пайва, Л. Х. де Фигейредо и Дж. Столфи (2006), «Надежная визуализация странных аттракторов с использованием аффинной арифметики». Компьютеры и графика , 30 6 , 1020–1026.

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

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