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

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

Революционным прорывом в этой области стало создание в 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) максимально близкой к нулю.

Коллективный интеллект на службе математики

В области глобальной стохастической оптимизации генетические алгоритмы (ГА) и дифференциальная эволюция (DE), основанные на теории естественного отбора, десятилетиями удерживали лидерство. Однако в конце 1990-х годов возникла мощная альтернативная парадигма эвристического поиска, вдохновленная не эволюцией видов, а социальным поведением животных. Как стая птиц находит лучшее место для кормежки в огромном лесу? Как муравьи без единого лидера строят оптимальные кратчайшие маршруты от муравейника к источнику пищи? Оказалось, что математическая формализация этих природных механизмов дает потрясающе быстрые численные алгоритмы оптимизации сложных недифференцируемых функций.

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

Оптимизация роем частиц (Particle Swarm Optimization, PSO)

Алгоритм PSO был разработан в 1995 году Кеннеди и Эберхартом. Пространство поиска заполняется «частицами» (математическими векторами возможных решений). Каждая частица имеет свою координату и вектор скорости. На каждом шаге частица оценивает значение целевой функции в своей точке. Направление ее следующего шага (новая скорость) вычисляется как векторная сумма трех составляющих.

Первая составляющая — инерция: частица склонна двигаться туда, куда летела на предыдущем шаге. Вторая составляющая — личная (когнитивная) память: частица всегда помнит ту точку пространства, где она лично находила наилучший результат (наименьший минимум), и ее притягивает к этой точке. Третья составляющая — социальный опыт: частицу притягивает к той точке, которая является наилучшей среди всей стаи (глобальный лидер). Коэффициенты доверия к себе и к социуму являются настроечными параметрами. В результате этого простого математического взаимодействия частиц возникает невероятно сложный и целенаправленный танец роя, который быстро стягивается в самые глубокие минимумы сложных ландшафтов (функций Розенброка, Растригина и др.). PSO превосходно подходит для настройки весов в системах управления и проектирования СВЧ-антенн.

Муравьиные алгоритмы (Ant Colony Optimization, ACO)

Если PSO отлично работает в непрерывных пространствах, то для сложнейших задач дискретной комбинаторной оптимизации (например, задача коммивояжера, разводка печатных плат, маршрутизация пакетов в интернете) Марко Дориго в 1992 году создал Муравьиные алгоритмы (ACO). Идея заимствована из механизма стигмергии: непрямой коммуникации муравьев через отложение химических следов (феромонов).

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