На первый взгляд, задача применения размерных ограничений к чертежу кажется не сложнее упражнения из школьного учебника. Точно так же показалось и мне, когда я впервые узнал о ней. В то время я работал в компании, которая занималась разработкой программного комплекса для проектирования индивидуальных жилых домов с подготовкой проектной документации "под ключ". В этом проекте я занимался разработкой алгоритма генерации многоскатных крыш, а впоследствии и всего геометрического ядра на основе Булевых операций, поэтому за дальнейшей историей я следил издалека. В какой-то определенный момент, заказчику захотелось, чтобы проектировщики могли просто указать размеры комнат, углы эркеров и ширину дверных проемов, а программа автоматически рассчитала бы все остальные параметры внешнего и внутреннего устройства дома. Эта мысль возникла у заказчика спонтанно, и поэтому срочно нужно было сделать “точно так же, как в CATIA”. Наш тимлид подошел к решению задачи с энтузиазмом и начал разрабатывать прототип. Он решал сотни уравнений в MathCAD, весь кабинет был завален графиками частных решений для двух, трех, четырех точек… Его изначальное предположение о том, что задачу можно решить аналитически, потерпело фиаско: на дворе был 2005, а это значило, что в интернете невозможно было найти хоть какую-то информацию по данной теме. В результате, после двух месяцев напряженных исследований, данную функциональность пришлось исключить.
Метод Ньютона
Эта история закончилась печально, поскольку задача решения геометрических ограничений в общем случае сводится к решению системы нелинейных уравнений, которую в аналитической форме современные математики решать не умеют. Поэтому все, что остается в условиях современных реалий — это пользоваться методом, названным в честь великого гения яблочных озарений: методом Ньютона. Данный метод позволяет найти нуль (корень) любой нелинейной функции (уравнения) итерационным методом с квадратичной сходимостью. Это означает, что количество точных значащих цифр удваивается с каждой итерацией метода. Простыми словами, вычисление нуля функции с высокой степенью точности достигается за сравнительно небольшое количество итераций. В большинстве практических случаев достаточно 5-12 итераций.
С вынужденной необходимостью применения метода Ньютона ситуация становится более драматичной: ведь этот метод не гарантирует нам сходимости даже при наличии решений, и успешность нахождения решения в основном зависит от начального значения параметров на старте метода. Кроме того, этот метод не позволяет нам найти все нули функции или корни уравнения, поскольку результат сходится к первому попавшемуся корню. Поэтому инженеру-конструктору все же приходится рисовать чертеж, наиболее приближенный к конечному результату. Если начальное приближение параметров слишком далеко от решения, метод Ньютона может не сойтись, либо сойтись к неожиданному решению.
Иллюстрация расхождения метода Ньютона, примененного к функции f(x)=x^{3}-2x+2. Возьмём нуль в качестве начального приближения. Первая итерация дает в качестве приближения единицу. В свою очередь, вторая снова дает нуль. Метод зациклится и решение не будет найдено. В общем случае построение последовательности приближений может быть очень запутанным.
С учетом всего вышеизложенного, к методу Ньютона можно относиться как к магическому черному ящику, который может дать нам ответ, если он его нашел, но не может сказать, есть ли решение в случае, если метод не сходится. Неисповедимы пути решений, в чем можно убедиться на следующих изображениях пути достижения решения (визуализирован след каждой точки чертежа, координаты точек записаны на каждом из шагов метода Ньютона):
Червоточины Ньютона
Как же победить "Червей Сомнений"?
Улучшаем сходимость (декомпозиция задачи)
Для того, чтобы улучшить сходимость метода и скорость его работы, обычно применяют хитрые методы декомпозиции исходной задачи. Анализируя степени свободы и уравнения, можно разбить чертеж на различные независимые группы так, что эти части можно решить отдельно, а затем, зафиксировав значения уже полученных параметров, решить систему уравнений окончательно. Методы декомпозиции позволяют сильно улучшить как сходимость, так и скорость работы алгоритма за счет того, что мы решаем не всю систему уравнений целиком, а несколько небольших систем уравнений. Алгоритмическая сложность метода Ньютона имеет полиномиальный характер, а значит мы можем получить существенную выгоду, если будем решать систему "по кусочкам". Но реализация такой декомпозиции требует разработки алгоритма, который будет привязан к геометрической интерпретации исходных уравнений, то есть будет оперировать терминами предметной области, а это ограничивает область применения решателя только геометрическими задачами. Например, декомпозиция для двумерного случая не очень эффективно будет работать для трехмерного, и скорее всего, такую задачу следует решать отдельно.
Увеличиваем точность (обусловленность системы уравнений)
В основе реализации метода Ньютона для решения систем нелинейных уравнений лежит метод линеаризации. Решение уравнения производится пошагово, и на каждом из шагов нелинейные функции представляется как линейные, что позволяет вместо системы нелинейных уравнений решать систему линейных уравнений. В результате, от точности решения этой самой системы линейных уравнений и зависит сходимость метода Ньютона. Чем точнее решение на каждом шаге, тем быстрее и стабильнее сходится метод Ньютона, и тем меньше других проблем, приводящих к тому, что решение не будет найдено.
В математике существует понятие обусловленности системы уравнений. Простыми словами, это некоторая величина, которая может нам сказать о том, насколько точным (достоверным) будет решение данной системы уравнений. В качестве примера можно привести решение простейшего уравнения, которое в абстрактном мире математики можно рассматривать как частный случай системы уравнений:
ax + b = 0.
Его решение:
x = -b / a
Если воспользоваться геометрической интерпретацией, то ax + b — уравнение прямой, а ее пересечение с осью абсцисс и является решением уравнения. Теперь представьте, что исходные данные (a, b) для этого уравнения заданы с некоторой степенью точности. В таком случае, чем меньше величина a, и прямая ближе к параллельности оси абсцисс, тем больше будет неоднозначность решения. При малых относительных изменениях a значения x будут изменяться значительно. Если же мы будем рассматривать систему из многих уравнений, то в ходе решения ошибка может накапливаться, и результат решения будет больше похож на характеристики погодных условий удаленных планет, нежели на верный результат решения системы линейных уравнений. Поэтому очень важным моментом является контроль числа обусловленности системы уравнений и предпринятие ряда мер по приведению системы к такому виду, при котором можно получить наилучшую точность.
Примером, когда эта проблема может проявляться, может служить несогласованность уравнений по величинам. Например, с помощью геометрических ограничений мы можем создать треугольник, зафиксировав длины двух сторон и угол между ними. Уравнение ограничения длин записывается в миллиметрах, а ограничение угла, например, задается через равенство косинусов. Несогласованность этих величин может служить причиной для реализации различных сценариев потери точности: когда мы делаем небольшие треугольники размера порядка миллиметров — мы можем получать достаточно хорошую точность, но когда начинаем решать те же уравнения, но с длинами порядка километров — мы будем получать совершенно другую относительную точность результата. Это случается потому, что величины длин меняются значительно, при этом значения косинусов углов остаются в неизменном диапазоне значений. Я верю, что одним из вариантов решения проблемы несогласованности уравнений может служить формирование системы уравнений в однородной системе координат, с использованием методов проективной геометрии, но это умозаключение является предчувствием, ввиду моих весьма скромных познаний в области проективной геометрии в частности, да всей математики в целом. Есть вероятность, что эта тема уже была раскрыта, но возможно, кто-то сможет найти в ней способ защитить пару-тройку диссертаций.
Увеличиваем производительность
Алгоритмическая сложность решения системы нелинейных уравнений методом Ньютона в основном определяется сложностью решения системы линейных уравнений. Например, оригинальный SolveSpace по версии Джонатана Вэстхью, автора SolveSpace, в качестве метода решения использует метод Гаусса, обладающий алгоритмической сложностью O(n^3). Это не очень-то быстро, если вдруг захочется решать большие скетчи, содержащие тысячи уравнений и неизвестных. Но учитывая тот факт, что матрица системы линейных уравнений практически вся состоит из нулей и является сильно разреженной, для решения можно применять алгоритмы с более низкой алгоритмической сложностью.
Дополнительным преимуществом записи уравнений в символьном виде является возможность их предварительной символьной оптимизации. Такой операцией, например, является сокращение подобных. Но серьезного прироста производительности удается добиться за счет символьного решения некоторых уравнений методом подстановки. Например, в SolveSpace методом символьной подстановки решаются такие ограничения, как совпадение точек и горизонтальность/вертикальность. Применение этого метода может существенно уменьшить количество уравнений и неизвестных, служащих исходными данными для метода Ньютона. Подробнее о том, как устроены символьные выражения, вы можете узнать из этого видео.
Заключение
Несмотря на то, что тема решения систем нелинейных уравнений кажется изначально простой, она содержит множество подводных камней и фундаментальных проблем. Я считаю, что в этой области еще есть над чем поработать, поскольку кроме геометрических приложений, решение систем нелинейных уравнений может быть полезно во многих областях: от решения задач оптимизации затрат до использования в системах искусственного интеллекта.
Часть 1: Введение
Часть 2: Эскиз
Часть 3: Степени свободы и уравнения ограничений
Часть 4: «Неисповедимы пути Решателя» или «Червоточины Ньютона»
Автор: Алексей Егоров
