Числовая сертификация

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

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

Сертификаты

Сертификат корня — это вычислительное доказательство правильности возможного решения. Например, сертификат может состоять из приближенного решения $x$ , регион $R$ содержащий $x$ и доказательство того, что $R$ содержит ровно одно решение системы уравнений.

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

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

Существует множество методов апостериорной сертификации, в том числе

Альфа-теория

Краеугольным камнем альфа-теории Смейла является ограничение погрешности метода Ньютона . Работа Смейла 1986 года ^[1] представил количество $\alpha$ , что количественно определяет сходимость метода Ньютона. Точнее, пусть $F$ — система аналитических функций от переменных $x$ , $D$ оператор производной и $N$ оператор Ньютона. Количества $\beta (f,x)=\|x-N(x)\|=\|Df(x)^{-1}f(x)\|$ $\gamma (f,x)=\sup _{k\geq 2}\left\|{\frac {Df(x)^{-1}D^{k}f(x)}{k!}}\right\|^{\frac {1}{k-1}}$ и $\alpha (f,x)=\beta (f,x)\gamma (f,x)$ используются для сертификации возможного решения. В частности, если $\alpha (f,x)<{\frac {13-3{\sqrt {17}}}{4}},$ затем $x$ является приближенным решением для $f$ , т. е. кандидат находится в области квадратичной сходимости метода Ньютона. Другими словами, если это неравенство выполнено, то существует корень $x^{\ast }$ из $F$ так что итерации оператора Ньютона сходятся как $\left\|N^{k}(x)-x^{\ast }\right\|\leq {\frac {1}{2^{2^{k}-1}}}\|x-x^{\ast }\|.$

Программный пакет AlphaCertified обеспечивает реализацию альфа-теста полиномов путем оценки $\beta$ и $\gamma$ . ^[2]

Интервальные методы Ньютона и Кравчика.

Предполагать $G:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}$ — функция, неподвижные точки которой соответствуют корням $F$ . Например, таким свойством обладает оператор Ньютона. Предположим, что $I$ это регион, то,

Если $G$ карты $I$ в себя, т.е. $G(I)\subseteq I$ , то по теореме Брауэра о неподвижной точке , $G$ имеет хотя бы одну неподвижную точку $I$ , и, следовательно, $F$ имеет хотя бы один корень $I$ .
Если $G$ сжимается содержащей в области, $I$ , то существует не более одного корня $I$ .

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

Интервальный метод Ньютона

В одномерном случае метод Ньютона можно напрямую обобщить для подтверждения корня на интервале. На интервал $J$ , позволять $m(J)$ быть серединой $J$ . Затем интервальный оператор Ньютона был применен к $J$ является

IN(J)=m(J)-F(m(J))/F'(J).

На практике любой интервал, содержащий $F'(J)$ можно использовать в этом вычислении. Если $x$ является корнем $F$ , то по теореме о среднем значении существует некоторый $c\in J$ такой, что $F(m(J))-F'(c)(m(J)-x)=F(x)=0$ . Другими словами, $F(m(J))=F'(c)(m(J)-x)$ . С $F'(J)$ содержит обратную величину $F$ во всех точках $J$ , отсюда следует, что $m(J)-x\in F(m(J))/F'(J)$ . Поэтому, $x=m(J)-(m(J)-x)\in IN(J)$ .

Кроме того, если $0\not \in F'(J)$ , то либо $m(J)$ является корнем $F$ и $IN(J)=\{m(J)\}$ или $m(J)\not \in IN(J)$ . Поэтому, $J\cap N(J)$ составляет не более половины ширины $J$ . Следовательно, если существует некоторый корень $F$ в $J$ , итерационная процедура замены $J$ к $J\cap IN(J)$ будет сходиться к этому корню. Если же нет корня $F$ в $J$ , эта итерационная процедура в конечном итоге приведет к появлению пустого интервала, свидетельствующего об отсутствии корней.

См. интервальный метод Ньютона для более многомерных аналогов этого подхода.

метод Кравчика

Позволять $Y$ быть любым $n\times n$ обратимая матрица в $GL(n,\mathbb {R} )$ . Обычно принимают $Y$ быть приближением к $F'(y)^{-1}$ . Затем определите функцию $G(x)=x-YF(x).$ Мы наблюдаем, что $x$ является фиксированным из $G$ тогда и только тогда, когда $x$ является корнем $F$ . Таким образом, описанный выше подход можно использовать для выявления корней $F$ . Этот подход аналогичен многомерной версии метода Ньютона, в которой производная заменяется фиксированной матрицей. $Y$ .

Мы наблюдаем, что если $J$ представляет собой компактную и выпуклую область и $y\in J$ , то для любого $x\in J$ , существуют $c_{1},\dots ,c_{n}\in J$ такой, что

G(y)-G(x)={\begin{bmatrix}\nabla g_{1}(c_{1})^{T}\\\vdots \\\nabla g_{n}(c_{n})^{T}\end{bmatrix}}(y-x).

Позволять $G'(J)$ быть матрицей Якобиана $G$ оценивается на $J$ . Другими словами, запись $(G'(J))_{ij}$ состоит из изображения ${\frac {\partial g_{i}}{\partial x_{j}}}$ над $J$ . Отсюда следует, что $G(x)\in G(y)+\nabla G(J)(x-y),$ где произведение матрицы на вектор вычисляется с использованием интервальной арифметики. Затем, позволив $x$ варьироваться в $J$ , следовательно, образ $G$ на $J$ удовлетворяет следующим требованиям: $G(J)\subset G(y)+G'(J)(J-y),$ где вычисления снова производятся с использованием интервальной арифметики. Объединив это с формулой для $G$ , результатом является оператор Кравчика

K_{y,Y}(J)=y-YF(y)+(I-F'(J))(J-y),

где $I$ является единичной матрицей.

Если $K_{y,Y}(J)\subset J$ , затем $G$ имеет фиксированную точку в $J$ , то есть, $F$ имеет корень в $J$ . С другой стороны, если максимальная матричная норма с использованием супремумной нормы для векторов всех матриц в $I-F'(J)$ меньше, чем $1$ , затем $G$ сжимается внутри $J$ , так $G$ имеет единственную неподвижную точку.

Более простой тест, когда $J$ представляет собой параллелепипед, ориентированный по оси, использует $y=m(J)$ , то есть середина $J$ . В этом случае имеется единственный корень $F$ если

\|K(X)-m(X)\|<{\frac {w(X)}{2}},

где $w(X)$ это длина самой длинной стороны $J$ .

Тест Миранды

Тест Миранды (Яп, Вегтер, Шарма)

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

Интервальная арифметика (Мур, Арб, Меззаробба)
Номера условий (Бельтран – Лейкин)

Интервальная арифметика

Интервальная арифметика может использоваться для предоставления априорного числового сертификата путем вычисления интервалов, содержащих уникальные решения. Благодаря использованию интервалов вместо простых числовых типов во время отслеживания пути результирующие кандидаты представляются интервалами. Кандидатный интервал решения сам по себе является сертификатом в том смысле, что решение гарантированно находится внутри интервала.

Номера условий

Численная алгебраическая геометрия решает полиномиальные системы, используя методы продолжения гомотопии и отслеживания путей. Контролируя число обусловленности отслеживаемой гомотопии на каждом этапе и гарантируя, что никакие два пути решения никогда не пересекаются, можно вычислить числовой сертификат вместе с решением. Эта схема называется априорным отслеживанием пути. ^[3]

Несертифицированное числовое отслеживание пути основано на эвристических методах управления размером и точностью временного шага. ^[4] Напротив, априори сертифицированное отслеживание пути выходит за рамки эвристики и обеспечивает контроль размера шага, который гарантирует , что для каждого шага по пути текущая точка находится в области квадратичной сходимости для текущего пути.

Ссылки

^ Смейл, Стив (1986). «Метод Ньютона оценивает данные в одной точке». Объединение дисциплин: новые направления чистой, прикладной и вычислительной математики : 185–196.
^ Хауэнштайн, Джонатан; Соттиле, Фрэнк (2012). «Алгоритм 921: AlphaCertified: сертификация решений полиномиальных систем». Транзакции ACM в математическом программном обеспечении . 38 (4): 28. дои : 10.1145/2331130.2331136 .
^ Бельтран, Карлос; Лейкин, Антон (2012). «Сертифицированное числовое отслеживание гомотопий». Экспериментальная математика . 21 (1): 69–83.
^ Бейтс, Дэниел; Хауэнштайн, Джонатан; Соммесе, Эндрю; Вамплер, Чарльз (2009). «Регулирование шага для отслеживания пути». Современная математика . 496 (21).

[1] Смейл, Стив (1986). «Метод Ньютона оценивает данные в одной точке». Объединение дисциплин: новые направления чистой, прикладной и вычислительной математики : 185–196.

[alphacertified-2] Хауэнштайн, Джонатан; Соттиле, Фрэнк (2012). «Алгоритм 921: AlphaCertified: сертификация решений полиномиальных систем». Транзакции ACM в математическом программном обеспечении . 38 (4): 28. дои : 10.1145/2331130.2331136 .

[3] Бельтран, Карлос; Лейкин, Антон (2012). «Сертифицированное числовое отслеживание гомотопий». Экспериментальная математика . 21 (1): 69–83.

[4] Бейтс, Дэниел; Хауэнштайн, Джонатан; Соммесе, Эндрю; Вамплер, Чарльз (2009). «Регулирование шага для отслеживания пути». Современная математика . 496 (21).

[1]

[2]

[3]

[4]