Экспоненциальный интегратор

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

Фон

Начиная, по крайней мере, с 1960-х годов, эти методы были признаны компанией Suree. ^[1] и Папа. ^[2] В последнее время экспоненциальные интеграторыстать активной областью исследований, см. Hochbruck and Ostermann (2010). ^[3] Первоначально разработанные для решения жестких дифференциальных уравнений , эти методы использовались для решения уравнений в частных производных, включая гиперболические , а также параболические. проблемы ^[4] например, уравнение теплопроводности .

Введение

Мы рассматриваем задачи начального значения вида:

u'(t)=Lu(t)+N(u(t)),\qquad u(t_{0})=u_{0},\qquad \qquad (1)

где $L$ состоит из линейных членов , и $N$ состоит из нелинейных членов.Эти проблемы могут возникать из более типичной проблемы начального значения.

u'(t)=f(u(t)),\qquad u(t_{0})=u_{0},

после локальной линеаризации относительно фиксированного или локального состояния $u^{*}$ :

L={\frac {\partial f}{\partial u}}(u^{*});\qquad N=f(u)-Lu.

Здесь, ${\frac {\partial f}{\partial u}}$ относится к частной производной $f$ относительно $u$ (якобиан f).

Точная интеграция этой задачи от момента времени 0 до более позднего времени. $t$ может быть выполнено с использованием матричной экспоненты для определения интегрального уравнения для точного решения: ^[3]

u(t)=e^{Lt}u_{0}+\int _{0}^{t}e^{L(t-\tau )}N\left(u\left(\tau \right)\right)\,d\tau .\qquad (2)

Это похоже на точный интеграл, используемый в теореме Пикара–Линделёфа . В случае $N\equiv 0$ , эта формулировка является точным решением линейного дифференциального уравнения .

Численные методы требуют дискретизации уравнения (2). Они могут быть основаны на Рунге-Кутты , Дискретизация ^[5]^[6]^[7]линейные многошаговые методы или множество других вариантов.

Экспоненциальные методы Розенброка

Было показано, что экспоненциальные методы Розенброка очень эффективны при решении больших систем жестких обыкновенных дифференциальных уравнений, обычно возникающих в результате пространственной дискретизации зависящих от времени (параболических) УЧП. Эти интеграторы построены на основе непрерывной линеаризации (1) вдоль численного решения $u_{n}$

u'(t)=L_{n}u(t)+N_{n}(u(t)),\qquad u(t_{0})=u_{0},\qquad (3)

где $L_{n}={\frac {\partial f}{\partial u}}(u_{n}),N_{n}(u)=f(u)-L_{n}u.$ Эта процедура на каждом этапе имеет то преимущество, что ${\frac {\partial N_{n}}{\partial u}}(u_{n})=0.$ Это существенно упрощает вывод условий порядка и повышает устойчивость при интегрировании нелинейности. $N(u(t))$ .Опять же, применение формулы вариации констант (2) дает точное решение в момент времени $t_{n+1}$ как

u(t_{n+1})=e^{h_{n}L_{n}}u(t_{n})+\int _{0}^{h_{n}}e^{(h_{n}-\tau )L_{n}}N_{n}(u(t_{n}+\tau ))d\tau .\qquad (4)

Теперь идея состоит в том, чтобы аппроксимировать интеграл в (4) некоторым правилом квадратур с узлами $c_{i}$ и веса $b_{i}(h_{n}L_{n})$ ( $1\leq i\leq s$ ). Это дает следующий класс $s-stage$ явные экспоненциальные методы Розенброка, см. Hochbruck and Ostermann (2006), Hochbruck, Ostermann and Schweitzer (2009):

U_{ni}=e^{c_{i}h_{n}L_{n}}u_{n}+h_{n}\sum _{j=1}^{i-1}a_{ij}(h_{n}L_{n})N_{n}(U_{nj}),

u_{n+1}=e^{h_{n}L_{n}}u_{n}+h_{n}\sum _{i=1}^{s}b_{i}(h_{n}L_{n})N_{n}(U_{ni})

с $u_{n}\approx u(t_{n}),U_{ni}\approx u(t_{n}+c_{i}h_{n}),h_{n}=t_{n+1}-t_{n}$ . Коэффициенты $a_{ij}(z),b_{i}(z)$ обычно выбираются как линейные комбинации целых функций $\varphi _{k}(c_{i}z),\varphi _{k}(z)$ , соответственно, где

\varphi _{0}(z)=e^{z},\quad \varphi _{k}(z)=\int _{0}^{1}e^{(1-\theta )z}{\frac {\theta ^{k-1}}{(k-1)!}}d\theta ,\quad k\geq 1.

Эти функции удовлетворяют рекурсивному соотношению

\varphi _{k+1}(z)={\frac {\varphi _{k}(z)-\varphi _{k}(0)}{z}},\ k\geq 0.

Введя разницу $D_{ni}=N_{n}(U_{ni})-N_{n}(u_{n})$ , их можно переформулировать для более эффективной реализации (см. также ^[3]) как

U_{ni}=u_{n}+c_{i}h_{n}\varphi _{1}(c_{i}h_{n}L_{n})f(u_{n})+h_{n}\sum _{j=2}^{i-1}a_{ij}(h_{n}L_{n})D_{nj},

u_{n+1}=u_{n}+h_{n}\varphi _{1}(h_{n}L_{n})f(u_{n})+h_{n}\sum _{i=2}^{s}b_{i}(h_{n}L_{n})D_{ni}.

Чтобы реализовать эту схему с адаптивным размером шага, с целью оценки локальной ошибки можно рассмотреть следующие встроенные методы:

{\bar {u}}_{n+1}=u_{n}+h_{n}\varphi _{1}(h_{n}L_{n})f(u_{n})+h_{n}\sum _{i=2}^{s}{\bar {b}}_{i}(h_{n}L_{n})D_{ni},

которые используют те же этапы $U_{ni}$ но с весами ${\bar {b}}_{i}$ .

Для удобства коэффициенты явных экспоненциальных методов Розенброка вместе с их встроенными методами можно представить с помощью так называемой сокращенной таблицы Бутчера следующим образом:

$c_{2}$
$c_{3}$	$a_{32}$
$\vdots$	$\vdots$		$\ddots$
$c_{s}$	$a_{s2}$	$a_{s3}$	$\cdots$	$a_{s,s-1}$
	$b_{2}$	$b_{3}$	$\cdots$	$b_{s-1}$	$b_{s}$
	${\bar {b}}_{2}$	${\bar {b}}_{3}$	$\cdots$	${\bar {b}}_{s-1}$	${\bar {b}}_{s}$

Жесткие условия заказа

Более того, это показано Луаном и Остерманном (2014a). ^[8] что подход к переформулировке предлагает новый и простой способ анализа локальных ошибок и, таким образом, получения условий жесткого порядка для экспоненциальных методов Розенброка до порядка 5. С помощью этого нового метода вместе с расширением концепции B-серии, теория вывода условий жесткого порядка для экспоненциальных интеграторов Розенброка произвольного порядка была наконец представлена в Луане и Остерманне (2013). ^[9] Например, в этой работе были выведены условия жесткого порядка для экспоненциальных методов Розенброка до порядка 6, которые представлены в следующей таблице:

{\begin{array}{|c|c|c| }\hline No.&{\text{Stiff order condition}}&{\text{Order}}\\\hline 1&\sum _{i=2}^{s}b_{i}(Z)c_{i}^{2}=2\varphi _{3}(Z)&3\\\hline 2&\sum _{i=2}^{s}b_{i}(Z)c_{i}^{3}=6\varphi _{4}(Z)&4\\\hline 3&\sum _{i=2}^{s}b_{i}(Z)c_{i}^{4}=24\varphi _{5}(Z)&5\\4&\sum _{i=2}^{s}b_{i}(Z)c_{i}K\psi _{3,i}(Z)=0&5\\\hline 5&\sum _{i=2}^{s}b_{i}(Z)c_{i}^{5}=120\varphi _{6}(Z)&6\\6&\sum _{i=2}^{s}b_{i}(Z)c_{i}^{2}M\psi _{3,i}(Z)=0&6\\7&\sum _{i=2}^{s}b_{i}(Z)c_{i}K\psi _{4,i}(Z)=0&6\\\hline \end{array}}

Здесь $Z,K,M.\$ обозначают произвольные квадратные матрицы.

Анализ конвергенции

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

Примеры

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

Метод второго порядка

Простейшим экспоненциальным методом Розенброка является экспоненциальная схема Розенброка–Эйлера, имеющая порядок 2, см., например, Hochbruck et al. (2009):

u_{n+1}=u_{n}+h_{n}\ \varphi _{1}(h_{n}L_{n})f(u_{n}).

Методы третьего порядка

Класс экспоненциальных методов Розенброка третьего порядка был выведен Hochbruck et al. (2009), названный exprb32, задается как:

выражениеb32:

1
	$2\varphi _{3}$
	0

который читается как

U_{n2}=u_{n}+h_{n}\ \varphi _{1}(h_{n}L_{n})f(u_{n}),

u_{n+1}=u_{n}+h_{n}\ \varphi _{1}(h_{n}L_{n})f(u_{n})+h_{n}\ 2\varphi _{3}(h_{n}L_{n})D_{n2},

где $D_{n2}=N_{n}(U_{n2})-N_{n}(u_{n}).$

Для реализации этой схемы с переменным размером шага можно встроить в нее экспоненциальную функцию Розенброка – Эйлера:

{\hat {u}}_{n+1}=u_{n}+h_{n}\ \varphi _{1}(h_{n}L_{n})f(u_{n}).

Метод ETDRK4 четвертого порядка Кокса и Мэтьюза

Кокс и Мэтьюз ^[5] описать метод экспоненциальной разницы во времени (ETD) четвертого порядка, для получения которого они использовали Maple .

Мы используем их обозначения и предполагаем, что неизвестная функция равна $u$ , и что у нас есть известное решение $u_{n}$ во время $t_{n}$ .Кроме того, мы будем явно использовать правую часть, которая может зависеть от времени: ${\mathcal {N}}={\mathcal {N}}(t,u)$ .

Сначала строятся три значения этапа:

a_{n}=e^{Lh/2}u_{n}+L^{-1}\left(e^{Lh/2}-I\right){\mathcal {N}}(t_{n},u_{n})

b_{n}=e^{Lh/2}u_{n}+L^{-1}\left(e^{Lh/2}-I\right){\mathcal {N}}(t_{n}+h/2,a_{n})

c_{n}=e^{Lh/2}a_{n}+L^{-1}\left(e^{Lh/2}-I\right)\left(2{\mathcal {N}}(t_{n}+h/2,b_{n})-{\mathcal {N}}(t_{n},u_{n})\right)

Окончательное обновление предоставлено:

u_{n+1}=e^{Lh}u_{n}+h^{-2}L^{-3}\left\{\left[-4-Lh+e^{Lh}\left(4-3Lh+(Lh)^{2}\right)\right]{\mathcal {N}}(t_{n},u_{n})+2\left[2+Lh+e^{Lh}\left(-2+Lh\right)\right]\left({\mathcal {N}}(t_{n}+h/2,a_{n})+{\mathcal {N}}(t_{n}+h/2,b_{n})\right)+\left[-4-3Lh-(Lh)^{2}+e^{Lh}\left(4-Lh\right)\right]{\mathcal {N}}(t_{n}+h,c_{n})\right\}.

При примитивной реализации приведенный выше алгоритм страдает числовой нестабильностью из-за с плавающей запятой . ошибок округления ^[10] Чтобы понять почему, рассмотрим первую функцию:

\varphi _{1}(z)={\frac {e^{z}-1}{z}},

который присутствует в методе Эйлера первого порядка, а также во всех трех этапах ETDRK4. Для небольших значений $z$ , эта функция страдает от ошибок численного сокращения. Однако этих числовых проблем можно избежать, оценив $\varphi _{1}$ функция с помощью контурного интегрального подхода ^[10] или аппроксимацией Паде . ^[11]

Приложения

Экспоненциальные интеграторы используются для моделирования жестких сценариев в научных и визуальных вычислениях, например, в молекулярной динамике . ^[12] для СБИС , моделирования схем ^[13]^[14] и в компьютерной графике . ^[15] Они также применяются в контексте гибридных методов Монте-Карло . ^[16] В этих приложениях экспоненциальные интеграторы демонстрируют преимущество возможности большого шага по времени и высокой точности. Чтобы ускорить вычисление матричных функций в таких сложных сценариях, экспоненциальные интеграторы часто комбинируются с методами проецирования подпространства Крылова.

См. также

Общие линейные методы

Примечания

Ссылки

Берланд, Гавард; Оурен, Брюнюльф; Скафлестад, Бард (2005). «B-серия и условия порядка для экспоненциальных интеграторов». SIAM Journal по численному анализу . 43 (4): 1715–1727. CiteSeerX 10.1.1.216.5645 . дои : 10.1137/040612683 .
Берланд, Гавард; Скафлестад, Бард; Райт, Уилл М. (2007). «EXPINT-Пакет MATLAB для экспоненциальных интеграторов» . Транзакции ACM в математическом программном обеспечении . 33 (1): 4–с. дои : 10.1145/1206040.1206044 . S2CID 1525599 .
Чао, Вэй-Лунь; Соломон, Джастин; Михельс, Доминик Л.; Ша, Фей (2015). «Экспоненциальное интегрирование гамильтониана Монте-Карло». Материалы 32-й Международной конференции по машинному обучению (ICML-15) : 1142–1151.
Определенно, Джон (1960). «Решение обыкновенных дифференциальных уравнений с большими постоянными времени». Математические методы для цифровых вычислительных машин . Уайли. стр. 128–132.
Кокс, С.М.; Мэтьюз, ПК (март 2002 г.). «Экспоненциальная разница во времени для жестких систем». Журнал вычислительной физики . 176 (2): 430–455. Бибкод : 2002JCoPh.176..430C . дои : 10.1006/jcph.2002.6995 .
Хохбрук, Марлис ; Остерманн, Александр (май 2010 г.). «Экспоненциальные интеграторы». Акта Нумерика . 19 : 209–286. Бибкод : 2010AcNum..19..209H . CiteSeerX 10.1.1.187.6794 . дои : 10.1017/S0962492910000048 . S2CID 4841957 .
Хохбрук, Марлис ; Остерманн, Александр (2005a). «Явные экспоненциальные методы Рунге-Кутты для полулинейных параболических задач» . SIAM Journal по численному анализу . 43 (3): 1069–1090. CiteSeerX 10.1.1.561.5501 . дои : 10.1137/040611434 .
Хохбрук, Марлис ; Остерманн, Александр (май 2005b). «Экспоненциальные методы Рунге – Кутты для параболических задач» . Прикладная численная математика . 53 (2–4): 323–339. дои : 10.1016/j.apnum.2004.08.005 .
Луан, Ву Тай; Остерманн, Александр (2014a). «Экспоненциальные методы Розенброка пятого порядка построения, анализа и числовых сравнений» . Журнал вычислительной и прикладной математики . 255 : 417–431. дои : 10.1016/j.cam.2013.04.041 .
Луан, Ву Тай; Остерманн, Александр (2014c). «Явные экспоненциальные методы Рунге-Кутты высокого порядка для параболических задач». Журнал вычислительной и прикладной математики . 256 : 168–179. arXiv : 1307.0661 . дои : 10.1016/j.cam.2013.07.027 . S2CID 18448807 .
Луан, Ву Тай; Остерманн, Александр (2013). «Экспоненциальная B-серия: жесткий случай». SIAM Journal по численному анализу . 51 (6): 3431–3445. дои : 10.1137/130920204 .
Луан, Ву Тай; Остерманн, Александр (2014). «Условия жесткого порядка для экспоненциальных методов Рунге – Кутты пятого порядка». В Боке, Ханс Георг; Хоанг, Суан Фу; Раннахер, Рольф; Шлёдер, Йоханнес П. (ред.). Моделирование, симуляция и оптимизация сложных процессов – HPSC 2012: Материалы пятой международной конференции по высокопроизводительным научным вычислениям, 5–9 марта 2012 г., Ханой, Вьетнам . Спрингер. стр. 133–143. дои : 10.1007/978-3-319-09063-4_11 . ISBN 978-3-319-09062-7 .
Луан, Ву Тай; Остерманн, Александр (2016). «Параллельные экспоненциальные методы Розенброка» . Компьютеры и математика с приложениями . 71 (5): 1137–1150. дои : 10.1016/j.camwa.2016.01.020 .
Михельс, Доминик Л.; Дебрен, Матье (2015). «Полуаналитический подход к молекулярной динамике» . Журнал вычислительной физики . 303 : 336–354. Бибкод : 2015JCoPh.303..336M . дои : 10.1016/j.jcp.2015.10.009 .
Михельс, Доминик Л.; Соботтка, Геррит А.; Вебер, Андреас Г. (2014). «Экспоненциальные интеграторы для задач жесткой упругости». Транзакции ACM с графикой . 33 : 7:1–7:20. дои : 10.1145/2508462 . S2CID 207207156 .
Папа, Дэвид А. (1963). «Экспоненциальный метод численного интегрирования обыкновенных дифференциальных уравнений» . Коммуникации АКМ . 6 (8): 491–493. дои : 10.1145/366707.367592 . S2CID 18598461 .
Токман, Майя (октябрь 2011 г.). «Новый класс итерационных методов экспоненциального распространения типа Рунге – Кутты (EPIRK)». Журнал вычислительной физики . 230 (24): 8762–8778. Бибкод : 2011JCoPh.230.8762T . дои : 10.1016/j.jcp.2011.08.023 .
Токман, Майя (апрель 2006 г.). «Эффективная интеграция больших жестких систем ОДУ с итерационными методами экспоненциального распространения (EPI)». Журнал вычислительной физики . 213 (2): 748–776. Бибкод : 2006JCoPh.213..748T . дои : 10.1016/j.jcp.2005.08.032 .
Кассам, Али-Хан; Трефетен, Ллойд Н. (2005). «Шаг по времени четвертого порядка для жестких PDE». SIAM Журнал по научным вычислениям . 26 (4): 1214–1233. Бибкод : 2005ГАК...26.1214К . CiteSeerX 10.1.1.15.6467 . дои : 10.1137/S1064827502410633 .
Чжуан, Хао; Венг, Ши-Хун; Лин, Дженг-Хау; Ченг, Чунг-Куан (2014). «МАТЕКС» (PDF) . Материалы 51-й ежегодной конференции по автоматизации проектирования на конференции по автоматизации проектирования - DAC '14 . стр. 1–6. arXiv : 1511.04519 . дои : 10.1145/2593069.2593160 . ISBN 9781450327305 . S2CID 10585362 .
Венг, Ши-Хун; Чен, Цюань; Ченг, Чунг-Куан (2012). «Анализ крупномасштабных схем во временной области матричным экспоненциальным методом с адаптивным управлением». Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 32 (8): 1180–1193. дои : 10.1109/TCAD.2012.2189396 . S2CID 14977067 .

Внешние ссылки

[1] Определенно (1960)

[2] Папа (1963)

[Exponential_integrators-3] Jump up to: ^а ^б ^с Хохбрук и Остерманн (2010)

[4] Хохбрук и Остерманн (2005a) , Хохбрук и Остерманн (2005b)

[Cox_and_Matthews_2002-5] Jump up to: ^а ^б Кокс и Мэтьюз (2002)

[6] Токман (2006)

[7] Токман (2011)

[8] Луан и Остерманн (2014a)

[9] Луан и Остерманн (2013)

[Kassam_and_Trefethen_2005-10] Jump up to: ^а ^б Кассам и Трефетен (2005)

[11] Берланд, Скафлестад и Райт (2007)

[12] Михельс и Дебрен (2015)

[13] Чжуан и др. (2014)

[14] Венг, Чен и Ченг (2012)

[15] Михельс, Соботтка и Вебер (2014)

[16] Чао и др. (2015)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

v т и Численные методы для решения обыкновенных дифференциальных уравнений
Методы первого порядка	метод Эйлера Обратный Эйлер Полунеявный Эйлер Экспоненциальный Эйлер
Методы второго порядка	Интеграция Верлет Скорость Верле Правило трапеции Алгоритм Бимана Метод средней точки метод Хойна Метод Ньюмарка-бета Чехарда интеграции
Методы высшего порядка	Экспоненциальный интегратор Методы Рунге-Кутты Список методов Рунге – Кутты Линейный многошаговый метод Общие линейные методы Формула обратного дифференцирования Ёсида Метод Гаусса – Лежандра
Теория	Симплектический интегратор