Вычислительная алгебраическая геометрия: базисы Грёбнера и полиномиальные системы

Когда метод Ньютона бессилен

Решение систем нелинейных уравнений — одна из сложнейших задач численного анализа. Если система состоит из многочленов (полиномиальная система), она возникает в криптографии, робототехнике (обратная кинематика манипуляторов), компьютерном зрении и молекулярной химии. Обычно для таких систем применяют многомерный метод Ньютона-Канторовича. Но метод Ньютона — локальный. Он найдет лишь один корень вблизи начальной точки. Что если инженеру нужно найти строго все корни системы (или доказать, что их вообще не существует)? Что если корней бесконечно много и они образуют кривые поверхности (алгебраические многообразия)? Здесь численные приближения пасуют, и в дело вступает вычислительная коммутативная алгебра.

Революционным прорывом в этой области стало создание в 1965 году Бруно Бухбергером (в его докторской диссертации под руководством Вольфганга Грёбнера) алгоритма построения базисов Грёбнера. Этот алгоритм стал для нелинейных полиномиальных систем тем же, чем является алгоритм Гаусса для линейных систем уравнений. Он позволяет строго алгоритмически, за конечное число шагов, преобразовать любую сложную систему полиномов в эквивалентную ей систему, но имеющую особую, «удобную» треугольную форму.

Алгоритм Бухбергера: нелинейный аналог исключения Гаусса

Основная идея Бухбергера опирается на понятие идеала в кольце многочленов (множества всех полиномов, которые обращаются в ноль там же, где и исходные уравнения). Любая система задает свой базис этого идеала. Базис Грёбнера — это такой «идеальный» базис, в котором старшие члены полиномов обладают специальным свойством делимости.

Алгоритм Бухбергера берет пары исходных полиномов и вычисляет их S-полиномы (специальные комбинации, в которых искусственно уничтожаются старшие степени, подобно обнулению коэффициентов в методе Гаусса). Затем эти S-полиномы делятся на исходный базис с остатком. Если остаток не равен нулю, он добавляется в систему как новое уравнение (не меняющее корней!). Этот процесс генерации новых полиномов продолжается до тех пор, пока все возможные остатки не станут нулями. Теорема Гильберта о базисе гарантирует, что этот процесс обязательно остановится.

Триумф лексикографического порядка

Самая мощная магия базисов Грёбнера раскрывается при использовании лексикографического порядка сортировки одночленов (как слова в словаре). Если мы вычислим базис Грёбнера с таким порядком, то в полученной эквивалентной системе уравнений последний полином будет содержать только одну неизвестную переменную (например, только z)! Предпоследний полином будет содержать z и y, и так далее. Мы получаем строго треугольную систему.

Теперь решение нелинейной многомерной системы сводится к банальному вычислению корней одного полинома от одной переменной (что можно сделать численно с огромной точностью), а затем обратной подстановкой найденных значений в верхние уравнения системы. Алгоритм Бухбергера, интегрированный в системы компьютерной алгебры (Maple, Mathematica), требует гигантских объемов памяти (сложность алгоритма часто дважды экспоненциальная EXPSPACE), но его способность находить абсолютно все скрытые корни сделала его незаменимым аналитическим инструментом современной прикладной геометрии.