Метод прямой многократной стрельбы

В области математики, известной как численные обыкновенные дифференциальные уравнения , метод прямой множественной стрельбы является численным методом решения краевых задач . Метод делит интервал, на котором ищется решение, на несколько меньших интервалов, решает задачу начального значения в каждом из меньших интервалов и накладывает дополнительные условия согласования для формирования решения на всем интервале. Метод представляет собой значительное улучшение распределения нелинейности и численной устойчивости по сравнению с методами одиночной стрельбы .

Методы одиночной стрельбы

Методы стрельбы можно использовать для решения краевых задач (КЗ), например , в которых известны моменты времени t _a и t _{b и мы ищем} $y''(t)=f(t,y(t),y'(t)),\quad y(t_{a})=y_{a},\quad y(t_{b})=y_{b},$ $y(t),\quad t\in (t_{a},t_{b}).$

Методы одиночной стрельбы действуют следующим образом. Пусть y ( t ; t ₀ , y ₀ ) обозначает решение задачи начального значения (IVP). Определим функцию F ( p ) как разность между y ( t _b ; p ) и указанным граничным значением y _b : F ( p ) = y ( t _b ; p ) − y _b . Тогда для каждого решения ( y _a , y _b ) задачи граничного значения мы имеем y _a = y ₀ , в то время как y _b соответствует корню F . Этот корень может быть решен любым методом нахождения корня при условии, что выполнены определенные зависящие от метода предпосылки. Это часто потребует начальных догадок для y _a и y _{b . Обычно аналитическое нахождение корня невозможно, и для}этой задачи используются итерационные методы, такие как метод Ньютона . $y''(t)=f(t,y(t),y'(t)),\quad y(t_{0})=y_{0},\quad y'(t_{0})=p$

Применение метода одиночной стрельбы для численного решения краевых задач имеет ряд недостатков.

Для заданного начального значения y0 решение IVP, очевидно, должно существовать на интервале [ t _a , t _{b ]}_, чтобы мы могли вычислить функцию F , корень которой ищется.

Для высоконелинейных или нестабильных ОДУ это требует, чтобы начальное предположение y ₀ было чрезвычайно близко к фактическому, но неизвестному решению y _a . Начальные значения, выбранные немного в стороне от истинного решения, могут привести к сингулярностям или поломке метода решения ОДУ. Однако выбор таких решений неизбежен в итеративном методе поиска корней.

Конечная точность чисел может сделать вообще невозможным нахождение начальных значений, позволяющих решить ОДУ на всем временном интервале.
Нелинейность ОДУ фактически становится нелинейностью F и требует метода поиска корня, способного решать нелинейные системы. Такие методы обычно сходятся медленнее, когда нелинейности становятся более серьезными. Производительность решателя краевых задач страдает от этого.
Даже устойчивые и хорошо обусловленные ОДУ могут привести к неустойчивым и плохо обусловленным БВП. Небольшое изменение начального значения y ₀ может привести к чрезвычайно большому шагу в решении ОДУ y ( t _b ; t _a , y ₀ ) и, следовательно, в значениях функции F , корень которой ищется. Неаналитические методы поиска корней редко справляются с таким поведением.

Многократная стрельба

Метод прямой множественной стрельбы разбивает интервал [ t _a , t _b ] путем введения дополнительных точек сетки. Метод начинается с угадывания каким-либо образом значений y во всех точках сетки t _k с $0 \leq$ $k$ $\leq$ $N$ $- 1$ . Обозначим эти угадывания через y _k . Пусть y ( t ; t _k , y _k ) обозначает решение, исходящее из k -й точки сетки, то есть решение задачи начального значения. Все эти решения можно объединить, чтобы сформировать непрерывную траекторию, если значения y совпадают в точках сетки. Таким образом, решения краевой задачи соответствуют решениям следующей системы из N уравнений: Центральные N −2 уравнения являются условиями согласования, а первое и последнее уравнения являются условиями $y$ $($ $t$ $a$ $) =$ $y$ $a$ и $y$ $($ $t$ $b$ $) =$ $y$ $b$ из краевой задачи. Метод множественной стрельбы решает краевую задачу путем решения этой системы уравнений. Обычно для последней задачи используют модификацию метода Ньютона . $t_{a}=t_{0}<t_{1}<\cdots <t_{N}=t_{b}.$ $y'(t)=f(t,y(t)),\quad y(t_{k})=y_{k}.$ ${\begin{aligned}y(t_{1};t_{0},y_{0})&=y_{1}\\&\;\,\vdots \\y(t_{N-1};t_{N-2},y_{N-2})&=y_{N-1}\\y(t_{N};t_{N-1},y_{N-1})&=y_{b}.\end{aligned}}$

Методы многократной стрельбы и параллельной съемки во времени

Множественная стрельба была принята для получения параллельных решателей для задач с начальными значениями . ^[1] Например, метод параллельной интеграции Parareal во времени может быть получен как алгоритм множественной стрельбы со специальным приближением якобиана . [ ^2]

Ссылки

^ Киль, Мартин (1994). «Параллельная многократная стрельба для решения задач начального значения». Параллельные вычисления . 20 (3): 275–295. doi :10.1016/S0167-8191(06)80013-X.
^ Гандер, Мартин Дж.; Вандевалле, Стефан (2007). «Анализ метода парареального времени-параллельного времени-интегрирования». Журнал SIAM по научным вычислениям . 29 (2): 556–578. CiteSeerX 10.1.1.92.9922 . doi :10.1137/05064607X.

Стер, Йозеф; Булирш, Роланд (2002), Введение в численный анализ (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-95452-3. См. разделы 7.3.5 и далее.
Бок, Ханс Георг; Плитт, Карл Дж. (1984), «Алгоритм множественной стрельбы для прямого решения задач оптимального управления», Труды 9-го Всемирного конгресса IFAC, 9-й Всемирный конгресс IFAC: Мост между наукой управления и технологией, Будапешт, Венгрия, 2–6 июля 1984 г., т. 17, Будапешт, стр. 1603–1608, doi : 10.1016/S1474-6670(17)61205-9{{citation}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
Моррисон, Дэвид Д.; Райли, Джеймс Д.; Занканаро, Джон Ф. (декабрь 1962 г.), «Метод множественной стрельбы для двухточечных краевых задач» (PDF) , Commun. ACM , 5 (12): 613–614, doi :10.1145/355580.369128, S2CID 8774159