Цифровая сертификация - Numerical certification

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

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

Сертификаты

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

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

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

Есть множество методов для апостериорный сертификация, в том числе

Теория альфа

Краеугольный камень Альфа-теория Смейла ограничивает ошибку для Метод Ньютона. Работа Смейла 1986 года^[1] ввел количество ${ displaystyle alpha}$ , который количественно оценивает сходимость метода Ньютона. Точнее, пусть ${ displaystyle F}$ - система аналитических функций от переменных ${ displaystyle x}$ , ${ displaystyle D}$ то производная оператор и ${ displaystyle N}$ оператор Ньютона. Количество

{ Displaystyle бета (е, х) = | х-N (х) | = | Df (х) ^ {- 1} е (х) |}

{ Displaystyle гамма (е, х) = sup _ {к geq 2} влево | { гидроразрыва {Df (x) ^ {- 1} D ^ {k} f (x)} {к! }} right | ^ { frac {1} {k-1}}}

и

{ Displaystyle альфа (е, х) = бета (е, х) гамма (е, х)}

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

{ Displaystyle альфа (е, х) <{ гидроразрыва {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}}} | хх ^ { аст} |.}

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

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

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

Если ${ displaystyle G}$ карты ${ displaystyle I}$ в себя, т.е. ${ Displaystyle G (I) substeq I}$ , затем по Теорема Брауэра о неподвижной точке, ${ displaystyle G}$ имеет хотя бы одну фиксированную точку в ${ displaystyle I}$ , и поэтому ${ displaystyle F}$ имеет хотя бы один корень в ${ displaystyle I}$ .
Если ${ displaystyle G}$ является сжимающий в регионе, содержащем ${ displaystyle I}$ , то в ${ displaystyle I}$ .

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

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

В одномерном случае метод Ньютона может быть напрямую обобщен для сертификации корня на интервале. На интервал ${ displaystyle J}$ , позволять ${ displaystyle m (J)}$ быть серединой ${ 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 (m (J)) - F '(c) (m (J) -x) = F (x) = 0}$ . Другими словами, ${ Displaystyle F (m (J)) = F '(c) (m (J) -x)}$ . С ${ Displaystyle F '(J)}$ содержит инверсию ${ displaystyle F}$ во всех точках ${ displaystyle J}$ , следует, что ${ Displaystyle m (J) -x in F (m (J)) / F '(J)}$ . Следовательно, ${ Displaystyle х = м (J) - (м (J) -x) in IN (J)}$ .

Кроме того, если ${ displaystyle 0 not in F '(J)}$ , то либо ${ displaystyle m (J)}$ это корень ${ displaystyle F}$ и ${ Displaystyle В (J) = {м (J) }}$ или же ${ Displaystyle м (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 п раз п}$ обратимая матрица в ${ Displaystyle GL (п, mathbb {R})}$ . Обычно берется ${ displaystyle Y}$ быть приближением к ${ Displaystyle F '(у) ^ {- 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 (х) в G (у) + набла G (J) (х-у),}$ где произведение матрицы на вектор вычисляется с использованием интервальной арифметики. Затем, допуская ${ displaystyle x}$ варьироваться в ${ displaystyle J}$ , следует, что образ ${ displaystyle G}$ на ${ displaystyle J}$ удовлетворяет следующему содержанию: ${ Displaystyle G (J) подмножество G (y) + G '(J) (J-y),}$ где вычисления снова производятся с использованием интервальной арифметики. Объединяя это с формулой для ${ displaystyle G}$ , результатом является оператор Кравчика

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

куда ${ displaystyle I}$ - единичная матрица.

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

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

{ Displaystyle | К (Х) -м (Х) | <{ гидроразрыва {ш (Х)} {2}},}

куда ${ Displaystyle ш (Х)}$ длина самой длинной стороны ${ displaystyle J}$ .

Миранда тест

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

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

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

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

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

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

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

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