Числовая алгебраическая геометрия

редактировать

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

Содержание

  • 1 Продолжение гомотопии
  • 2 Набор свидетелей
  • 3 Сертификация
  • 4 Программное обеспечение
  • 5 Ссылки
  • 6 внешние ссылки

Продолжение гомотопии

Смотрите также: Система полиномиальных уравнений § Метод продолжения гомотопии

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

Позвольте представить переменные системы. Из-за злоупотребления обозначениями и для облегчения спектра окружающих пространств, по которым можно решить систему, мы не используем векторные обозначения для. Аналогично для полиномиальных систем и. z {\ displaystyle z} z {\ displaystyle z} ж {\ displaystyle f} грамм {\ displaystyle g}

Текущая каноническая запись называет систему запуска, и целевая система, то есть система, чтобы решить,. Очень распространенная гомотопия, прямолинейная гомотопия между и есть грамм {\ displaystyle g} ж {\ displaystyle f} ж {\ displaystyle f} грамм {\ displaystyle g}

ЧАС ( z , т ) знак равно ( 1 - т ) ж ( z ) + т грамм ( z ) . {\ Displaystyle H (z, t) = (1-t) f (z) + tg (z).}

В приведенной выше гомотопии переменная пути начинается с и продолжается в направлении. Другой распространенный выбор - бежать от до. В принципе выбор совершенно произвольный. На практике, что касается методов эндшпиля для вычисления сингулярных решений с использованием продолжения гомотопии, целевое время может значительно облегчить анализ, поэтому здесь мы придерживаемся этой точки зрения. т Начало знак равно 1 {\ Displaystyle т _ {\ текст {начало}} = 1} т конец знак равно 0 {\ displaystyle t _ {\ text {end}} = 0} 0 {\ displaystyle 0} 1 {\ displaystyle 1} 0 {\ displaystyle 0}

Независимо от выбора времени начала и целевого времени, следует сформулировать так, чтобы, и. ЧАС {\ displaystyle H} ЧАС ( z , т Начало ) знак равно грамм ( z ) {\ Displaystyle Н (г, т _ {\ текст {начало}}) = г (г)} ЧАС ( z , т конец ) знак равно ж ( z ) {\ Displaystyle Н (г, т _ {\ текст {конец}}) = е (г)}

Есть выбор, в том числе грамм ( z ) {\ displaystyle g (z)}

  • Корни единства
  • Общая степень
  • Многогранник
  • Мульти-однородный

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

Фактическое продолжение обычно выполняется с использованием методов предиктора – корректора с добавлением дополнительных функций. Прогнозирование выполняется с использованием стандартного метода прогнозирования ODE, такого как метод Рунге – Кутты, а для коррекции часто используется итерация Ньютона – Рафсона.

Поскольку и являются полиномиальными, продолжение гомотопии в этом контексте теоретически гарантирует вычисление всех решений, в соответствии с теоремой Бертини. Однако на практике эта гарантия не всегда достигается из-за проблем, возникающих из-за ограничений современного компьютера, а именно из-за конечной точности. То есть, несмотря на силу аргумента «вероятность 1», лежащего в основе этой теории, без использования априори сертифицированных методов отслеживания некоторые пути могут не отслеживаться идеально по разным причинам. ж {\ displaystyle f} грамм {\ displaystyle g} ж {\ displaystyle f}

Набор свидетелей

Набор свидетелей - это структура данных, используемая для описания алгебраических разновидностей. Набор свидетелей для аффинного многообразия, которое равноразмерно, состоит из трех частей информации. Первая часть информации - это система уравнений. Эти уравнения определяют изучаемое алгебраическое многообразие. Вторая часть информации - это линейное пространство. Размерность является коразмерностью и выбрана для поперечного пересечения. Третья информация - это список точек пересечения. Это пересечение имеет конечное число точек, и число точек - это степень алгебраического многообразия. Таким образом, наборы свидетелей кодируют ответ на первые два вопроса об алгебраическом разнообразии: каково измерение и какова степень? Наборы свидетелей также позволяют выполнять числовую неразложимую декомпозицию, тесты на принадлежность компонентов и выборку компонентов. Это делает наборы свидетелей хорошим описанием алгебраического многообразия. W {\ displaystyle W} F {\ displaystyle F} V ( F ) {\ Displaystyle {\ mathbf {V}} (F)} L {\ Displaystyle {\ mathcal {L}}} L {\ Displaystyle {\ mathcal {L}}} V ( F ) {\ Displaystyle {\ mathbf {V}} (F)} V ( F ) {\ Displaystyle {\ mathbf {V}} (F)} L V ( F ) {\ Displaystyle {\ mathcal {L}} \ cap {\ mathbf {V}} (F)} V ( F ) {\ Displaystyle {\ mathbf {V}} (F)}

Сертификация

Решения полиномиальных систем, вычисленные с использованием методов численно-алгебраической геометрии, могут быть сертифицированы, что означает, что приближенное решение является «правильным». Это может быть достигнуто несколькими способами: либо априори с использованием сертифицированного трекера, либо апостериори, показывая, что точка находится, скажем, в области сходимости метода Ньютона.

Программное обеспечение

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

  • alphaCertified
  • Бертини
  • Hom4PS
  • HomotopyContinuation.jl
  • Macaulay2 (основная реализация гомотопического отслеживания и NumericalAlgebraicGeometryупаковки)
  • PHCPack

Ссылки

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

Последняя правка сделана 2023-04-13 12:21:15
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте