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

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

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

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

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

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

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

Программный пакет alphaCertified обеспечивает реализацию альфа-теста для полиномов путем оценки и . ^[2]${\displaystyle \бета}$${\displaystyle \гамма}$

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

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

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

В одномерном случае метод Ньютона можно напрямую обобщить для подтверждения корня на интервале. Для интервала пусть будет серединой . Тогда оператор Ньютона, примененный к интервалу, будет${\displaystyle J}$${\displaystyle м(Дж)}$${\displaystyle J}$${\displaystyle J}$

${\displaystyle IN(J)=m(J)-F(m(J))/F'(J).}$

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

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

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

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

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

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

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

${\displaystyle K_{y,Y}(J)=y-YF(y)+(IF'(J))(Jy),}$

где — единичная матрица.${\displaystyle Я}$

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

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

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

где - длина самой длинной стороны .${\displaystyle w(X)}$${\displaystyle J}$

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

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

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

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

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