Жесткие краевые задачи: метод многократной пристрелки по параметру
Когда одиночный выстрел уходит в бесконечность
Мы уже рассматривали классический метод стрельбы (пристрелки) для решения нелинейных краевых задач. В нем мы подбираем недостающее начальное условие на одном конце отрезка, решаем задачу Коши и проверяем попадание во второе граничное условие. Метод невероятно прост и интуитивен, однако он абсолютно бессилен перед классом жестких краевых задач. К таким задачам часто приводят уравнения гидродинамического пограничного слоя, задачи тепломассопереноса с сильными химическими реакциями или расчеты оптимальных космических траекторий.
Суть проблемы заключается в жесточайшей чувствительности дифференциальной системы к начальным данным. Если в задаче присутствуют быстрорастущие экспоненциальные компоненты, то даже микроскопическая ошибка (в миллиардных долях) при выборе начального угла «орудия» приведет к тому, что к середине расчетного интервала численное решение улетит в математическую бесконечность из-за переполнения регистров памяти компьютера. Алгоритм просто не сможет дойти до правого края, чтобы оценить ошибку промаха. Невозможно прицелиться, если любое малейшее дрожание руки приводит к отклонению снаряда на миллионы километров.
Метод многократной (параллельной) стрельбы
Чтобы обуздать экспоненциальный взрыв и восстановить вычислительную стабильность, математиками Келлером, Осборном и Деуфлхардом был разработан метод многократной стрельбы (Multiple Shooting Method). Идея этого метода заключается в том, чтобы не пытаться «прострелить» весь длинный и сложный интервал одним выстрелом.
Алгоритм искусственно разбивает весь длинный расчетный интервал на N небольших коротких подынтервалов (сегментов). На каждом из этих коротких отрезков вводится свой собственный вектор фиктивных начальных условий. Теперь мы осуществляем не один длинный выстрел, а сразу N независимых коротких выстрелов, стартующих одновременно из разных точек. Поскольку каждый интервал короткий, быстрорастущие решения просто не успевают раздуться до машинной бесконечности, и интегрирование каждого кусочка проходит успешно и стабильно.
Сшивка решений и матрица Якоби
Возникает логичный вопрос: как эти разрозненные, случайные куски превратить в единое непрерывное решение физической задачи? Алгоритм накладывает строгие условия сшивки (непрерывности). Он требует, чтобы конец траектории на первом интервале строго совпадал с началом траектории на втором интервале, конец второго — с началом третьего, и так далее. Кроме того, должны удовлетворяться исходные краевые условия на самом первом и самом последнем краях области.
Математически это приводит к формулировке огромной системы нелинейных алгебраических уравнений относительно неизвестных векторов параметров на стыках всех интервалов. Для решения этой нелинейной системы применяется многомерный итерационный метод Ньютона. В процессе работы метода Ньютона генерируется огромная матрица Якоби, которая обладает специфической разреженной ленточной структурой (или блочно-диагональной с окаймлением). Обращение этой матрицы специальными блочными алгоритмами выполняется крайне быстро. Метод многократной стрельбы блестяще параллелится на многоядерных процессорах и является мощнейшим индустриальным алгоритмом для решения задач оптимального управления (например, расчета траектории вывода спутника на орбиту с минимальным расходом топлива).