Численное интегрирование дифференциальных уравнений

Численное интегрирование дифференциальных уравнений

Симуляция физики делает небольшие предсказания на основании законов физики. Эти предсказания на самом деле достаточно просты, что-то вроде «если объект вот здесь и он движется с такой скоростью в этом направлении, то за краткий промежуток времени он окажется вот тут». Мы создаём такие предсказания с помощью математической техники под названием интегрирование.

Темой этой статьи как раз и будет реализация такого интегрирования.

Интегрирование уравнений движения

Вы можете помнить из курса старшей школы или вуза, что сила равна произведению массы на ускорение.

Преобразуем это уравнение и увидим, что ускорение равно силе, делённой на массу. Это соответствует нашим интуитивным ожиданиям, потому что тяжёлые объекты труднее бросать.

Ускорение — это темп изменения скорости от времени:

Аналогично, скорость — это темп изменения позиции от времени:

Это значит, что если мы знаем текущие позицию и скорость объекта, а также приложенные к нему силы, то сможем проинтегрировать, чтобы найти его позицию и скорость в определённый момент времени.

Численное интегрирование

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

Вот как работает численное интегрирование: во-первых, начнём с исходной позиции и скорости, затем сделаем небольшой шаг вперёд, чтобы найти скорость и позицию в будущем. Затем повторим это, двигаясь вперёд небольшими шагами, используя результат предыдущих вычислений как исходную точку следующих.

Но как нам найти изменение скорости и позиции на каждом шаге?

Ответ лежит в уравнениях движения.

Давайте назовём наше текущее время t, а шаг времени dt или «delta time».

Теперь мы можем представить уравнения движения в понятном всем виде:

Интуитивно это понятно: если вы находитесь в автомобиле, движущемся со скоростью 60 км/ч, то за один час вы проедете 60 км. Аналогично, автомобиль, ускоряющийся на 10 км/ч в секунду, через 10 секунд будет двигаться на 100 км/ч быстрее.

Разумеется, эта логика сохраняется, только когда ускорение и скорость постоянны. Но даже если они меняются, то это для начала вполне неплохая аппроксимация.

Давайте представим это в коде. Начнём с стационарного объекта массой один килограмм и приложим к нему постоянную силу в 10 кН (килоньютонов) и сделаем шаг вперёд, принимая, что один временной шаг равен одной секунде:

Вот каким будет результат:

Как вы видите, на каждом шаге мы знаем и позицию, и скорость объекта. Это и есть численное интегрирование.

Явный метод Эйлера

Вид интегрирования, который мы только что использовали, называется явным методом Эйлера.

Он назван в честь швейцарского математика Леонарда Эйлера, впервые открывшего эту технику.

Интегрирование Эйлера — это простейшая техника численного интегрирования. Она точна на 100% только когда темп изменений в течение шага времени постоянен.

Поскольку в примере выше ускорение постоянно, интегрирование скорости выполняется без ошибок. Однако мы ещё интегрируем и скорость для получения позиции, а скорость увеличивается из-за ускорения. Это значит, что в проинтегрированной позиции возникает ошибка.

Но насколько велика эта ошибка? Давайте выясним!

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

Через 10 секунд объект должен был переместиться на 500 метров, но явным метод Эйлера даёт нам результат 450. То есть погрешность в целых 50 метров всего за 10 секунд!

Кажется, что это невероятно плохо, но в играх обычно для шага физики берётся не такой большой временной интервал. На самом деле, физика обычно вычисляется с частотой, примерно равной частоте кадров дисплея.

Если задать шаг dt = 1 ⁄100, то мы получим гораздо лучший результат:

Как вы видите, это достаточно хороший результат, определённо вполне достаточный для игры.

Почему явный метод Эйлера не (всегда) так уж хорош

С достаточно малым шагом времени явный метод Эйлера при постоянном ускорении даёт вполне достойные результаты, но что будет, если ускорение не постоянно?

Хорошим примером переменного ускорения является система пружинного амортизатора.

В этой системе масса присоединена к пружине, и её движение гасится чем-то вроде трения. Существует сила, пропорциональная расстоянию до объекта, которая притягивает его к исходной точке, и сила, пропорциональная скорости объекта, но направленная в противоположном направлении, которая замедляет его.

Здесь ускорение в течение шага времени совершенно точно изменяется, но эта постоянно меняющаяся функция является сочетанием позиции и скорости, которые сами постоянно изменяются за шаг времени.

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

Давайте начнём со слабозатухающей системы, в которой масса колеблется рядом с исходной точкой, постепенно замедляясь.

Вот входные параметры системы масса-пружина:

  • Масса: 1 килограмм
  • Исходная позиция: 1000 метров от исходной точки
  • Коэффициент упругости по закону Гука: k = 15
  • Коэффициент затухания по закону Гука: b = 0.1

И вот график точного решения:

Если для интегрирования этой системы мы применим явный метод Эйлера, то получим следующий результа, который я отмасштабировал по вертикали:

Вместо затухания и сближения с исходной точкой, система со временем набирает энергию!

Читайте также:  Беспроводные наушники defender как подключить

При интегрировании явным методом Эйлера и с dt= 1 ⁄100 такая система нестабильна.

К сожалению, поскольку мы уже интегрируем с малым шагом времени, то не имеем практичных способов повышения точности. Даже если мы уменьшим шаг времени, то всегда будет коэффициент упругости k, при котором мы получим такое поведение.

Симплектический метод Эйлера

Мы можем рассмотреть ещё один интегратор — симплектический метод Эйлера.

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

Переход от явного к симплектическому методу Эйлера заключается только в замене:

Использование симплектического интегратора Эйлера при dt = 1 ⁄100 для системы пружинного амортизатора даёт стабильный результат, очень близкий к точному решению:

Даже несмотря на то, что симплектический метод Эйлера имеет ту же степень точности, что и явный метод (степень 1), при интегрировании уравнений движения мы получаем намного лучший результат, потому что оно является симплектическим.

Существует множество других методов интегрирования

И теперь нечто совершенно другое.

Неявный метод Эйлера — это способ интегрирования, хорошо подходящий для интегрирования жёстких уравнений, которые при других методах становятся нестабильными. Его недостаток заключается в том, что он требует решения системы уравнений на каждом шаге времени.

Интегрирование Верле обеспечивает бо́льшую точность, чем неявный метод Эйлера, и требует меньше памяти при симуляции большого числа частиц. Это интегратор второй степени, который тоже является симплектическим.

Существует целое семейство интеграторов, называемое методами Рунге-Кутты. На самом деле, явный метод Эйлера считается частью этого семейства, но в него входят интеграторы и более высокого порядка, самым классическим из которых является метод Рунге-Кутты порядка 4 (Runge Kutta order 4) или просто RK4.

Это семейство интеграторов названо в честь открывших их немецких физиков: Карла Рунге и Мартина Кутты.

RK4 — это интегратор четвёртого порядка, то есть накапливаемая ошибка имеет порядок четвёртой производной. Это делает метод очень точным, гораздо более точным, чем явный и неявный методы Эйлера, имеющие только первый порядок.

Но хотя он более точен, нельзя сказать, что RK4 автоматически становится «лучшим» интегратором, или даже что он лучше симплектического метода Эйлера. Всё гораздо сложнее. Тем не менее, это довольно интересный интегратор и его стоит изучить.

Реализация RK4

Существует уже много объяснений математики, используемой в RK4. Например: здесь, здесь и здесь. Я настоятельно рекомендую изучить его выведение и понять, как и почему он работает на математическом уровне. Но я понимаю, что целевая аудитория этой статьи — программисты, а не математики, поэтому мы здесь будем рассматривать только реализацию. Так что давайте приступим.

Прежде чем приступить, давайте зададим состояние объекта как struct в C++, чтобы можно было удобно хранить позицию и скорость в одном месте:

Также нам нужна структура для хранения производных значений состояний:

Теперь нам нужна функция для вычисления состояния физики из t в t+dt с помощью одного набора производных, а после этого для вычисления производных в новом состоянии:

Функция ускорения управляет всей симуляцией. Давайте используем её в системе пружинного амортизатора и вернём ускорение для единичной массы:

То, что нужно здесь записать, разумеется, зависит от симуляции, но необходимо структурировать симуляцию таким образом, чтобы можно было вычислять ускорение внутри этого метода для заданных состояния и времени, в противном случае он не подойдёт для интегратора RK4.

Наконец, мы получаем саму процедуру интегрирования:

Интегратор RK4 делает выборку производной в четырёх точках, чтобы определить кривизну. Заметьте, как производная a используется при вычислении b, b используется при вычислении c, и c для d. Эта передача текущей производной в вычисление следующей и даёт интегратору RK4 его точность.

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

После вычисления четырёх производных наилучшая общая производная вычисляется как взвешенная сумма, полученная из разложения в ряд Тейлора. Эта комбинированная производная используется для перемещения позиции и скорости вперёд во времени, точно так же, как мы делали это в явном интеграторе Эйлера.

Сравнение симплектического метода Эйлера и RK4

Давайте подвергнем проверке интегратор RK4.

Очевидно, что поскольку он является интегратором более высокого порядка (четвёртый против первого) он наглядно будет более точен, чем симплектический метод Эйлера, правда?

Неправда. Оба интегратора так близки к точному результату, что при таком масштабе почти невозможно найти между ними разницу. Оба интегратора стабильны и очень хорошо повторяют точное решение при dt= 1 ⁄100.

При увеличении видно, что RK4 действительно более точен, чем симплектический метод Эйлера, но стоит ли эта точность сложности и лишнего времени выполнения RK4? Трудно судить.

Давайте постараемся и посмотрим, сможем ли мы найти значительное различие между двумя интеграторами. К сожалению, мы не сможем долго наблюдать за этой системой, потому что она быстро затухает до нуля, поэтому давайте перейдём к простому гармоническому осциллятору, который колеблется бесконечно и без затуханий.

Вот точный результат, к которому мы будем стремиться:

Чтобы усложнить интеграторам задачу, давайте увеличим шаг времени до 0,1 секунды.

Теперь запустим интеграторы на 90 секунд и увеличим масштаб:

Через 90 секунд симплектический метод Эйлера (оранжевая кривая) сдвинулся по фазе относительно точного решения, потому что его частота немного отличалась, в то время как зелёная кривая RK4 соответствует частоте, но теряет энергию!

Читайте также:  Прием старых жестких дисков

Мы чётко можем это заметить, увеличив шаг времени до 0,25 секунды.

RK4 сохраняет верную частоту, но теряет энергию:

А симплектический метод Эйлера в среднем намного лучше сохраняет энергию:

Но от сдвигается от фазы. Какой интересный результат! Как вы видите, если RK4 имеет более высокий порядок точности, то он не обязательно «лучше». В этом вопросе есть множество нюансов.

Заключение

Мы реализовали три различных интегратора и сравнили результаты.

  1. Явный метод Эйлера
  2. Симплектический метод Эйлера
  3. Метод Рунге-Кутты порядка 4 (RK4)

Так какой же интегратор стоит использовать в игре?

Я рекомендую симплектический метод Эйлера. Он «дёшев» и прост в реализации, гораздо стабильнее явного метода Эйлера и в среднем стремится к сохранению энергии даже при близких к предельным условиях.

Если вам действительно нужна бОльшая точность, чем у симплектического метода Эйлера, я рекомендую посмотреть на симплектические интеграторы более высокого порядка, рассчитанные на гамильтоновы системы. Таким образом вы изучите более современные техники интегрирования высокого порядка, которые лучше подходят для симуляций, чем RK4.

И наконец, если вы всё ещё пишете в игре такое:

То потратьте секунду и замените эти строки на:

Системой дифференциальных уравнений называется система вида

где x — независимый аргумент;

yi — зависимая функция, ;

Функции yi(x), при подстановке которой система уравнений обращается в тождество, называется решением системой дифференциальных уравнений.

Численные методы решения систем дифференциальных уравнений.

2. Модифицированный метод Эйлера.

3. Метод Рунге-Кутта четвертого порядка.

Дифференциальным уравнением второго порядка называется уравнение вида:

F(x,y,у’,y")=0 (1)
y"=f(x,y,y’). (2)

Функция y(x), при подстановке которой уравнение обращается в тождество, называется решением дифференциального уравнения.

Численно ищется частное решение уравнения (2), которое удовлетворяет заданным начальным условиям, то есть решается задача Коши.

Для численного решения дифференциальное уравнение второго порядка преобразуется в систему двух дифференциальных уравнений первого порядка и приводится к машинному виду (3). Для этого вводится новая неизвестная функция , слева в каждом уравнении системы оставляют только первые производные неизвестных функций, а в правых частях производных быть не должно:

(3)

Функция f2(x, y1, y) в систему (3) введена формально для того, чтобы методы, которые будут показаны ниже, могли быть использованы для решения произвольной системы дифференциальных уравнений первого порядка. Рассмотрим несколько численных методов решения системы (3). Расчетные зависимости для i+1 шага интегрирования имеют следующий вид. Для решения системы из n уравнений расчетные формулы приведены выше. Для решения системы из двух уравнений расчетные формулы удобно записать без двойных индексов в следующем виде:

2. Метод Рунге-Кутта четвертого порядка.

где h — шаг интегрирования. Начальные условия при численном интегрировании учитываются на нулевом шаге: i=0, x=x, y1=y10, y=y.

Задание для самостоятельной работы

Изучение численных методов решения дифференциальных уравнений второго порядка и систем дифференциальных уравнений первого порядка.

Численно и аналитически найти:

a. закон движения материальной точки на пружине х(t),

b. закон изменения силы тока I(t) в колебательном контуре (RLC — цепи) для заданных в табл.1,2 режимов. Построить графики искомых функций.

Варианты заданий

Режим
Свободные незатухающие колебания
Затухающее колебательное движение
Апериодическое движение
Предельное апериодическое движение
Вынужденное колебание без сопротивления
Вынужденное колебание без сопротивления, явление резонанса
Вынужденное колебание с линейным сопротивлением
Вынужденное колебание с линейным сопротивлением, явление резонанса

Варианты заданий и номера режимов:

1. движение точк;

Вар. Задание Вар. Задание
а) 1,2,5 б)1,2,6
а) 1,3,6 а) 1,4,7
б)1,3,7 б)1,2,7
а) 1,4,8 а) 1,2,5
б)1,2,8 б)1,4,6
а) 1,4,7 а) 1,3,5
б)1,3,6 б)1,3,8
а) 1,4,5 б)1,4,5
б)1,3,8 а) 1,3,6
а) 1,3,5 б)1,4,7
б)1,4,6 а) 1,2,8
а) 1,2,7 б)1,4,8
б)1,2,5 а) 1,3,6
а) 1,2,6 б)1,3,7
б)1,4,7 а) 1,2,5

Рассмотрим более подробно порядок составления дифференциальных уравнений и приведения их к машинному виду для описания движения тела на пружине и RLC-цепи.

a. Движение материальной точки на пружине.

При выполнении этого задания необходимо рассмотреть движение материальной точки массой m на пружине (рис. 14.1) жесткостью c в среде с линейным сопротивлением под действием синусоидальной вынуждающей силы по горизонтальной поверхности.

Рис. 14.1 — движение материальной точки на пружине

Уравнение движения (второй закон Ньютона) для материальной точки с учетом действия сил линейного сопротивления (-βx’), упругости пружины (-cx) и синусоидальной силы F∙sin(pt) может быть записано следующим образом:

,

где m=1+int(n/2) — масса материальной точки, β — коэффициент сопротивления, с=2+int(n/3) — жесткость пружины, х — координата (х=0 в положении равновесия точки), t — время, p — частота вынужденных колебаний, F=n — амплитуда силы, n — номер варианта, int — целая часть числа. Параметры β, p и начальные условия выбираются самостоятельно с учетом рассматриваемого режима.

b. Колебательный контур (RLC цепь) (рис. 14.2):

Рис. 14.2. — колебательный контур (RLC цепь)

Уравнение падения напряжения в цепи переменного тока имеет вид

,

где L=1+int(n/2) — индуктивность, R — сопротивление, C=2+int(n/3) — емкость конденсатора, q — заряд, U=nамплитуда напряжения, p — частота, — сила тока. Параметры R, p и начальные условия выбираются самостоятельно с учетом рассматриваемого режима.

15 Преобразование Фурье

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

Читайте также:  Приложение для съемки видео с эффектами

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

Простейшие алгоритмы численного интегрировании. Идеи численных методов проиллюстрируем на примере интегрирования уравнения первого порядка

где х, t— зависимая и независимая переменные; fix, /) — известная (линейная или нелинейная) функция.

Эти идеи можно перенести на системы уравнений первого порядка и обобщить на случай уравнений высших порядков.

Уравнению (1) на интервале /-../1 соответствует интеграл (отсюда понятие интегрирование дифференциального уравнения)

=> начальное значение x(to) = хо известно;

=> функцияfix, t) на интервале /о. t изменяется незначительно.

В этом случае интеграл (2) с учетом (1) может быть представлен в следующих двух формах, известных соответственно как прямая (явная) и обратная (неявная) формулы Эйлера [8]:

x(t); h = t- fo; *о, ,v’i — значение производных искомой функции x(t) при /() и (1).

С помощью рис. 1 можно дать геометрическую трактовку соотношениям

(3) и (4). При получении прямой формулы Эйлера (3) искомая функция .*(/) аппроксимируется на интервале (шаге) интегрирования прямой линией, совпадающей с касательной к этой функции в точке jc= х(/о) (рис. ,а), а при получении образной формулы Эйлера (4) — касательной в точке *(fi), выходящей из точки Хо = x(to) (рис. 1 ,б). В обоих случаях значение искомой функции x(t) определяется с некоторой ошибкой ? = x(t) — Х].

Представив (3) в виде соотношения (xj — Xo)/h = *’, а (4) — в виде соотношения (Х| — xo)/h = х и используя линейную комбинацию производных box’o + Ьх = (xi -xo)/h, можно получить при Ь = Ь = 1/2 известную формулу трапеций

Рис. 1. Геометрическая трактовка прямой (а) и обратной (б) формулы Эйлера

При численном интегрировании промежуток времени /. /т, в пределах которого требуется получить решение л*(/) уравнения (1), разбивают на малые интервалы времени At = h, называемые шагом интегрирования. Полагают, что начальное значение x(to) = л*о известно и решение, притом единственное, существует на всем интересующем интервале времени. Соотношения (3)-(5) записывают в форме алгоритма

позволяющего последовательно (задаваясь к = 0, 1,2. ) вычислить значения*), *2,д:з. от начальной расчетной точки /] до конечной tm с шагом h. Результаты численного интегрирования представляют собой таблицу соответствующих значений tn wxn (п = 0, 1,2, 3. ).

Алгоритм (6), позволяющий непосредственно определить решение в следующей точке /*+ь называется явным алгоритмом. В неявных алгоритмах Эйлера (7) и трапеций (8) используется производная в следующей точке (/*+))> значение которой неизвестно. Возникает задача определения се приближенного значения, или предсказания. Одна из возможностей ее решения состоит в применении на каждом шаге прямой формулы Эйлера (6). На основе найденного предсказания можно рассчитать значение производной х’ из(1) и использовать его при коррекции, которую можно выполнить по неявным формулам (7), (8). Повторным расчетом по формуле коррекции можно уточнить рассогласование начальных значений * и Хотя непосредственная необходимость в таких повторных расчетах отсутствует, в результате нескольких итераций (как показано в приведенных ниже примерах) можно

получить более точное значение х„. Итерации желательны, поскольку выполняются сравнительно просто. Кроме того, коррекция помогает в фиксации ошибок и управлении размером шага И.

Примеры. Для иллюстрации алгоритмов численного интегрирования решим неоднородное линейное дифференциальное уравнение х’ = х + г, приняв шаг интегрирования Л = 0,025; x(t) = jc = 1 (*о=0). Для оценки погрешности численного интегрирования (решения) воспользуемся точным решением дифференциального уравнения, имеющим следующий вид: л: = Зе 1 -1 2 — 2t — 2. Погрешность е определим как разность точного и полученного (численного) результатов.

Явный алгоритм Эйлера: jc*+i = ** + h(xk + /*“).

Шаг 1 (к = 0): = * + Л(х + Af) = 1 + 0,025(1 + О 2 ) = 1,025.

Шаг 2 = 1): л:2 = *, + Л(*, + г, 2 ) = 1,025 + 0,025(1,025 + 0,025 2 ) = 1,0506406 ит. д.

Неявный алгоритм Эйлера. На каждом шаге алгоритма будем использовать прямую формулу Эйлера ,v*+i n = х* + А(х* + f* 2 ) для предсказания и обратную формулу Эйлера х&.i = xk + h(xk+ + 1 2 ) для

коррекции, используя при этом три итерации. Третья итерация является результатом и используется на следующем шаге алгоритма.

Предсказание: *| П = x+h(xo + fo 2 ) = 1 + 0,025(1+0 2 ) = 1,025.

Итерация 1: *, (1) = * + А(х, п + /, 2 ) = 1 + 0,025(1,025 + 0,025 2 ) = = 1,0256406.

Итерация 2: лг, (2) = хо + h (*, (,) + /, 2 ) = 1 + 0,025(1,0256406 + 0, 025 2 ) = = 1,0256566.

Итерация 3: лг, (3) = лг + h (*, (2) + /, 2 ) = 1 + 0,025(1,0256566 + 0, 025 2 ) = = 1,0256570.

Итерация 2: jc2 = Х + h (jc2 (1) + /2 2 ) = 1,0256570 + 0,025(1,0520023 + + 0,05 2 )= 1,0520195

Итерация 3: л:2 (3) = хх + И (х2 <2) +/2 2 ) = 1,0256570 + 0,025(1,0520195 + + 0,05 2 )= 1,0520199 ит. д.

Неявный алгоритм трапеций. На каждом шаге алгоритма предсказания будем рассчитывать по прямой формуле Эйлера = хк + И(хк + /д 2 ), а для коррекции — использовать три итерации по

формуле трапеций = ** + 0,5Л(дг* + t 2 + jc*+i + /*+1 2 )- Третья итерация является результатом и используется на следующем шаге алгоритма.

Предсказание: „Yi n = x+h(xo + to 2 ) = 1 + 0,025(1 + О 2 ) = 1,025.

= 1 + 0,50,025(1 + 0 2 + 1,025 + 0,025 2 ) = 1,0235203.

= 1 +0,5-0,025(1 +0 2 + 1,0253203 + 0,025 2 )= 1,0253243.

Итерация 3: ,Vi (3) = хо + 0,5Л(дго + to + Xi (l) + t 2 ) =

= 1 + 0,5-0,025(1 + 0 2 + 1,0253243+ 0,025 2 ) = 1,0253244 и т.д.

Результаты расчетов сведены в табл. 1.

Приведенные примеры показывают, что:

=> абсолютная (и относительная) ошибка возрастает с каждым шагом численного интегрирования. При этом ошибки явного и неявного алгоритма Эйлера имеют разные знаки (см. рис. 1). Неявный алгоритм трапеций, представляющий собой комбинацию прямой и обратной формул Эйлера, обладает меньшей погрешностью (этому ниже будет дано объяснение);

Ссылка на основную публикацию
Adblock detector