От принципа Д'Аламбера до задачи о линейном дополнении
Статья предназначена для людей, которым интересны основы, заложенные в фундаменте современных алгоритмов моделирования динамики твердых тел с ограничениями; рассказывает она о том, как пройти путь от фундаментального вариационного принципа до системы неравенств с дополнительными ограничениями.
Итак, начнем с упомянутого выше принципа, являющегося одним из основных для современной механики - вариационного приципа Д'Аламбера-Лагранжа, суть которого выражается формулой
а словесная формулировка звучит как "Среди всех движений системы с идеальными ограничениями, кинематически возможным является такое, для которого в любой момент времени сумма элементарных работ приложенных сил и сил инерции равна нулю". Говоря проще, Д'Аламбер постулировал, что в системе с идеальными ограничениями, перемещения являются "допустимыми" - ортогональными к вектору ограничивающих сил.
Приняв во внимание этот принцип, начнем с "идеализации" ограничивающих сил моделируемой системы - минимизации их работы:
Данная формулировка является задачей математической оптимизации, и решить ее можно применением метода множителей Лагранжа. Для начала нужно задать функцию - лагранжиан, минимум которой будет соответствовать минимуму целевой функции на допустимом множестве (не нарушающем заданных ограничений):
Для того, чтобы решение полученной задачи было оптимальным, необходимо соблюдение условий Каруша-Куна-Такера [1]:
Условие стационарности прямиком следует из условия первого порядка для существования оптимума функции (производная в точке оптимума равна нулю), а первичное условие допустимости - из первоначального условия задачи, собственно. Матрица Якоби ([J]) в условии - матрица частных производных - производная одного вектора по другому вектору, в данном случае dc/dx. Вывести аналитическую формулу для конкретного соединения можно по правилу взятия производной сложной функции:
Исходя из того, что целевая функция - сумма элементарных работ ограничивающих сил на перемещении r, производная этой суммы - сама ограничивающая сила, и таким образом, условие стационарности можно переписать в виде
Это условие стационарности и является первопричиной обозначения ограничивающих сил через транспонированную матрицу Якоби, помноженную на вектор неизвестных множителей Лагранжа. Напомню, какой смысл в себе несет данная конструкция: матрица Якоби по сути своей - матрица частных производных, полученная при дифференцировании вектора по вектору, dc/dx = [J]. Следовательно, в строке матрицы находится градиент скалярного компонента вектора c, ci/dx. Математическое ограничение имеет форму c = 0, значит градиент, указывает в направлении наискорейшего роста скалярной функции ci. Схематическое изображение:
Но поскольку нам нужен 0 это функции, то градиент показывает "запретное направление". Транспонирование матрицы [J] и умножение ее на вектор дает линейную комбинацию "запретных" градиентов, т.е. ограничивающая сила действует перпендикулярно допустимым перемещениям, а это суть определения идеальной ограничивающей силы.
Далее, ограничивающие силы можно представить через фиктивную силу - силу инерции:
Подобная формулировка использовалась некоторое время назад для решения системы для ускорений, но решение на уровне вторых производных вызвало некоторые проблемы в стабильности и введении в систему сил трения [2][3]. Поэтому было использовано положение интегратора первого порядка (явный Эйлера или Эйлера-Кромера):
и система принимала следующий вид:
Теперь, рассмотрим первичное условие допустимости из условий ККТ решения задачи. Поскольку положения тел после применения ограничивающих сил неизвестны, нужно их как-то приблизить ограничивающую функцию в новом положении; например, с помощью ряда Тейлора (положения на предыдущем кадре нам известны, новое положение можно представить как xt = xt-1 + r, где r = vt*dt - это искомое "допустимое" смещение), а затем подставим выражение скорости, полученное выше:
Стоит отметить, что по результатом разложения в ряд ограничивающей функции, приблизить можно также и матрицу Якоби в точке xt (производная берется с тем учетом, что c(xt-1) константна в отношении r, следовательно и матрица Якоби в этой точке константна):
Теперь, переформулируем неравенство относительно неизвестных множителей Лагранжа, получим искомую формулировку задачи в виде LCP - задачи о линейном дополнении:
[1] М. Интрилигатор, "Математические методы оптимизации и экономическая теория";
[2] M. Cline, "Rigid Body Simulation with Contact and Constraints";
[3] M. Anitescu and F. Potra, "Formulating dynamic multi-rigidbody contact problems with friction as solvable linear complementarity problems".
