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

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

Аффинная арифметика призвана стать улучшением интервальной арифметики (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},\dots ,\epsilon _{n}}$

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

Совместное использование символа двумя аффинными формами подразумевает , что соответствующие величины X , 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 , где элемент — коэффициент символа в аффинной форме ; а — независимый член этой формы. Тогда совместный диапазон величин — то есть диапазон точки — является образом гиперкуба с помощью аффинного отображения из в , определяемого . ${\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 является "зонотопной арифметикой". Каждый шаг 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.

Ссылки

• LH de Figueiredo и J. Stolfi (2004) «Аффинная арифметика: концепции и приложения». Numerical Algorithms 37 (1–4), 147–158.
• Дж. Л. Д. Комба и Дж. Столфи (1993), «Аффинная арифметика и ее приложения к компьютерной графике». Учеб. SIBGRAPI'93 — VI Brasileiro de Computação Gráfica e Processamento de Imagens (Ресифи, Бразилия) , 9–18.
• LH de Figueiredo и J. Stolfi (1996), «Адаптивное перечисление неявных поверхностей с аффинной арифметикой». Computer Graphics Forum , 15 5 , 287–296.
• В. Хайдрих (1997), «Сборник аффинных арифметических версий общих математических библиотечных функций». Технический отчет 1997-3, Университет Эрланген-Нюрнберг.
• M. Kashiwagi (1998), «Алгоритм всех решений с использованием аффинной арифметики». NOLTA'98 — Международный симпозиум по нелинейной теории и ее приложениям 1998 года (Кран-Монтана, Швейцария) , 14–17.
• L. Egiziano, N. Femia и G. Spagnuolo (1998), «Новые подходы к истинной оценке наихудшего случая в анализе устойчивости и чувствительности схем — Часть II: Расчет внешнего решения с использованием аффинной арифметики». Труды COMPEL'98 — 6-й семинар по компьютерам в силовой электронике (Вилла Эрба, Италия) , 19–22.
• W. Heidrich, Ph. Slusallek и H.-P. Seidel (1998), «Выборка процедурных шейдеров с использованием аффинной арифметики». ACM Transactions on Graphics , 17 3 , 158–176.
• F. Messine и A. Mahfoudi (1998), «Использование аффинной арифметики в алгоритмах интервальной оптимизации для решения многомерных задач масштабирования». Proc. SCAN'98 — Международный симпозиум IMACS/GAMM по научным вычислениям, компьютерной арифметике и проверенным числам (Будапешт, Венгрия) , 22–25.
• A. de Cusatis Jr., LH Figueiredo и M. Gattass (1999), «Интервальные методы для поверхностей луча с аффинной арифметикой». Труды SIBGRAPI'99 — 12-й Бразильский симпозиум по компьютерной графике и обработке изображений , 65–71.
• K. Bühler и W. Barth (2000), "Новый алгоритм пересечения параметрических поверхностей на основе линейных интервальных оценок". Proc. SCAN 2000 / Interval 2000 — 9-й Международный симпозиум GAMM-IMACS по научным вычислениям, компьютерной арифметике и проверенным числам , ???–???.
• I. Voiculescu, J. Berchtold, A. Bowyer, RR Martin и Q. Zhang (2000), "Интервальная и аффинная арифметика для поверхностного расположения степенных и бернштейновских полиномов". Proc. Mathematics of Surfaces IX , 410–423. Springer, ISBN  1-85233-358-8 .
• Q. Zhang и RR Martin (2000), «Вычисление полиномов с использованием аффинной арифметики для рисования кривых». Труды конференции Eurographics UK 2000 , 49–56. ISBN 0-9521097-9-4 . 
• D. Michelucci (2000), «Надежные вычисления для динамических систем». Proc. SCAN 2000 / Interval 2000 — 9-й Международный симпозиум GAMM-IMACS по научным вычислениям, компьютерной арифметике и проверенным числам , ???–???.
• N. Femia и G. Spagnuolo (2000), «Анализ допустимых отклонений схем в худшем случае с использованием генетического алгоритма и аффинной арифметики — Часть I». IEEE Transactions on Circuits and Systems , 47 9 , 1285–1296.
• R. Martin, H. Shou, I. Voiculescu и G. Wang (2001), "Сравнение методов бернстейновской оболочки и аффинной арифметики для рисования алгебраических кривых". Proc. Неопределенность в геометрических вычислениях , 143–154. Kluwer Academic Publishers, ISBN 0-7923-7309-X . 
• A. Bowyer, R. Martin, H. Shou и I. Voiculescu (2001), "Аффинные интервалы в геометрическом моделере CSG". Proc. Неопределенность в геометрических вычислениях , 1–14. Kluwer Academic Publishers, ISBN 0-7923-7309-X . 
• T. Kikuchi и M. Kashiwagi (2001), «Устранение областей несуществования решения нелинейных уравнений с использованием аффинной арифметики». Труды NOLTA'01 — 2001 Международный симпозиум по нелинейной теории и ее приложениям .
• T. Miyata и M. Kashiwagi (2001), "О ранговой оценке полиномов аффинной арифметики". Труды NOLTA'01 - 2001 Международный симпозиум по нелинейной теории и ее приложениям .
• Y. Kanazawa и S. Oishi (2002), «Численный метод доказательства существования решений для нелинейных ОДУ с использованием аффинной арифметики». Труды SCAN'02 — 10-го Международного симпозиума GAMM-IMACS по научным вычислениям, компьютерной арифметике и проверенным числовым данным .
• H. Shou, RRMartin, I. Voiculescu, A. Bowyer и G. Wang (2002), «Аффинная арифметика в матричной форме для оценки полиномов и рисования алгебраических кривых». Progress in Natural Science , 12 1 , 77–81.
• A. Lemke, L. Hedrich и E. Barke (2002), «Определение размеров аналоговых схем на основе формальных методов с использованием аффинной арифметики». Труды ICCAD-2002 — Международная конференция по автоматизированному проектированию , 486–489.
• Ф. Мессин (2002), «Расширения аффинной арифметики: применение к безусловной глобальной оптимизации». Журнал универсальной компьютерной науки , 8 11 , 992–1015.
• К. Бюлер (2002), «Неявные линейные интервальные оценки». Труды 18-й весенней конференции по компьютерной графике (Будмерице, Словакия) , 123–132. ACM Press, ISBN 1-58113-608-0 . 
• LH de Figueiredo, J. Stolfi и L. Velho (2003), «Аппроксимация параметрических кривых полосовыми деревьями с использованием аффинной арифметики». Computer Graphics Forum , 22 2 , 171–179.
• CF Fang, T. Chen и R. Rutenbar (2003), "Анализ ошибок с плавающей точкой на основе аффинной арифметики". Труды Международной конференции 2003 года по акустике, речи и обработке сигналов .
• A. Paiva, LH de Figueiredo и J. Stolfi (2006), «Надежная визуализация странных аттракторов с использованием аффинной арифметики». Компьютеры и графика , 30 6 , 1020–1026.

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

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