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

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

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

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

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

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

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

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

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

Фундамент итерационной математики

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

Чтобы применить этот метод, исходное уравнение f(x) = 0 необходимо алгебраически преобразовать к эквивалентному виду: x = phi(x). Это можно сделать бесконечным числом способов (например, просто прибавив x к обеим частям, или выразив x из сложного логарифма). Теперь наша задача поиска корня превратилась в задачу поиска неподвижной точки отображения phi (fixed point). Неподвижная точка — это такое значение x, которое при подстановке в функцию phi выдает на выходе в точности то же самое значение x. Вычислительный алгоритм становится тривиальным: мы берем начальное случайное приближение x0, вычисляем x1 = phi(x0), затем x2 = phi(x1) и так далее до бесконечности.

Сжимающие отображения и теорема Банаха

Главный вопрос вычислительной математики: при каких условиях эта бесконечная последовательность x_n действительно сойдется к истинному корню, а не улетит в бесконечность и не зациклится? Ответ дает знаменитая теорема Банаха о неподвижной точке (принцип сжимающих отображений), доказанная польским математиком Стефаном Банахом в 1922 году.

Теорема гласит: если функция phi(x) является сжимающим отображением на замкнутом интервале (то есть расстояние между любыми двумя точками после применения функции строго уменьшается с коэффициентом сжатия q < 1), то на этом интервале существует ровно одна неподвижная точка, и метод простой итерации гарантированно сойдется к ней из абсолютно любого начального приближения! С точки зрения дифференциального исчисления, условие сжатия означает, что модуль производной функции phi(x) в окрестности корня должен быть строго меньше единицы. Чем ближе производная к нулю, тем меньше коэффициент сжатия q, и тем феноменально быстрее алгоритм будет сходиться. Если же производная по модулю больше единицы (отображение растягивающее), алгоритм неминуемо разойдется, как бы близко к корню мы ни стартовали. Искусство применения метода простой итерации заключается именно в таком хитром алгебраическом преобразовании f(x) = 0 в x = phi(x), чтобы искусственно сделать производную phi(x) максимально близкой к нулю.