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

Не путать с экспоненциальный интеграл из экспоненциальные функции.

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

Фон

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

Вступление

Мы считаем проблемы начального значения формы,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}),}$

${\displaystyle 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})}$

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

${\displaystyle \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.}$

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

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

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

${\displaystyle 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},}$

${\displaystyle 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}.}$

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

${\displaystyle {\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},}$

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

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

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

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

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

${\displaystyle {\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}}}$

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

Анализ сходимости

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

Примеры

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

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

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

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

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

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

exprb32:

1
	${\displaystyle 2\varphi _{3}}$
	0

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

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

${\displaystyle 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},}$

куда ${\displaystyle D_{n2}=N_{n}(U_{n2})-N_{n}(u_{n}).}$

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

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

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

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

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

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

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

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

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

Окончательное обновление дается,

${\displaystyle 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}}(u_{n},t_{n})+2\left[2+Lh+e^{Lh}\left(-2+Lh\right)\right]\left({\mathcal {N}}(a_{n},t_{n}+h/2)+{\mathcal {N}}(b_{n},t_{n}+h/2)\right)+\left[-4-3Lh-(Lh)^{2}+e^{Lh}\left(4-Lh\right)\right]{\mathcal {N}}(c_{n},t_{n}+h)\right\}.}$

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

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

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

Приложения

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

Смотрите также

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

Примечания

1. Certaine (1960)
2. Папа (1963)
3. Хохбрук и Остерманн (2010)
4. Хохбрук и Остерманн (2006) Ошибка harvtxt: нет цели: CITEREFHochbruckOstermann2006 (помощь)
5. Кокс и Мэтьюз (2002)
6. Токман (2006)
7. Токман (2011)
8. Луан и Остерман (2014a) Ошибка harvtxt: нет цели: CITEREFLuanOsterman2014a (помощь)
9. Луан и Остерман (2013) Ошибка harvtxt: нет цели: CITEREFLuanOsterman2013 (помощь)
10. Кокс и Мэтьюз (2002)
11. Кассам и Трефетен (2005) Ошибка harvtxt: нет цели: CITEREFKassamTrefethen2005 (помощь)
12. Берляндия (2007) Ошибка harvtxt: цель отсутствует: CITEREFBerland2007 (помощь)
13. Michels и Desbrun (2015)
14. Чжуан (2014) Ошибка harvtxt: нет цели: CITEREFZhuang2014 (помощь)
15. Вэн (2012) Ошибка harvtxt: цель отсутствует: CITEREFWeng2012 (помощь)
16. Михельс (2014) Ошибка harvtxt: цель отсутствует: CITEREFMichels2014 (помощь)
17. Чао (2015) Ошибка harvtxt: нет цели: CITEREFChao2015 (помощь)

Рекомендации

• Берляндия, Гавард; Оурен, Бринджульф; Скафлестад, Бард (2005). «Серия B и условия порядка для экспоненциальных интеграторов». Журнал SIAM по численному анализу. 43 (4): 1715–1727. CiteSeerX  10.1.1.216.5645. Дои:10.1137/040612683.
• Берляндия, Гавард; Скафлестад, Бард; Райт, Уилл М. (2007). "Пакет EXPINT-A MATLAB для экспоненциальных интеграторов". Транзакции ACM на математическом ПО. 33 (1): 4 – es. Дои:10.1145/1206040.1206044.
• Чао, Вэй-Лунь; Соломон, Джастин; Михельс, Доминик Л .; Ша, Фэй (2015). «Экспоненциальное интегрирование для гамильтониана Монте-Карло». Материалы 32-й Международной конференции по машинному обучению (ICML-15): 1142–1151.
• Certaine, Джон (1960). Решение обыкновенных дифференциальных уравнений с большими постоянными времени. Вайли. С. 128–132.
• Cox, S.M .; Мэтьюз, П. (Март 2002 г.). «Экспоненциальное разложение во времени для жестких систем». Журнал вычислительной физики. 176 (2): 430–455. Bibcode:2002JCoPh.176..430C. Дои:10.1006 / jcph.2002.6995.
• Хохбрук, Марлис; Остерманн, Александр (май 2010 г.). «Экспоненциальные интеграторы». Acta Numerica. 19: 209–286. Bibcode:2010AcNum..19..209H. CiteSeerX  10.1.1.187.6794. Дои:10.1017 / S0962492910000048.
• Хохбрук, Марлис; Остерманн, Александр (2005). «Явные экспоненциальные методы Рунге-Кутты для полулинейных параболических задач». Журнал SIAM по численному анализу. 43 (3): 1069–1090. CiteSeerX  10.1.1.561.5501. Дои:10.1137/040611434.
• Хохбрук, Марлис; Остерманн, Александр (май 2005 г.). «Экспоненциальные методы Рунге – Кутты для параболических задач». Прикладная вычислительная математика. 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.
• Луан, Ву Тай; Остерманн, Александр (2013). «Экспоненциальная серия B: жесткий случай». Журнал SIAM по численному анализу. 51 (6): 3431–3445. Дои:10.1137/130920204.
• Луан, Ву Тай; Остерманн, Александр (2014b). Условия жесткого порядка для экспоненциальных методов Рунге-Кутты пятого порядка. Моделирование, моделирование и оптимизация сложных процессов - HPSC 2012 (H.G. Bock et al. Eds.). С. 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. Bibcode:2015JCoPh.303..336M. Дои:10.1016 / j.jcp.2015.10.009.
• Михельс, Доминик Л .; Соботтка, Геррит А .; Вебер, Андреас Г. (2014). "Экспоненциальные интеграторы для задач жесткой эластодинамики". Транзакции ACM на графике. 33: 7:1–7:20. Дои:10.1145/2508462.
• Папа, Дэвид А. (1963). «Экспоненциальный метод численного интегрирования обыкновенных дифференциальных уравнений». Коммуникации ACM. 6 (8): 491–493. Дои:10.1145/366707.367592.
• Токман, Майя (октябрь 2011). «Новый класс итерационных методов экспоненциального распространения типа Рунге – Кутта (EPIRK)». Журнал вычислительной физики. 230 (24): 8762–8778. Bibcode:2011JCoPh.230.8762T. Дои:10.1016 / j.jcp.2011.08.023.
• Токман, Майя (апрель 2006 г.). «Эффективная интеграция больших жестких систем ODE с итеративными методами экспоненциального распространения (EPI)». Журнал вычислительной физики. 213 (2): 748–776. Bibcode:2006JCoPh.213..748T. Дои:10.1016 / j.jcp.2005.08.032.
• Trefethen, Lloyd N .; Али-Хан Кассам (2005). «Шаг по времени четвертого порядка для жестких PDE». Журнал SIAM по научным вычислениям. 26 (4): 1214–1233. 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.
• Венга, Ши-Хун; Чен, Цюань; Ченг, Чунг-Куан (2012). «Анализ во временной области крупномасштабных схем матричным экспоненциальным методом с адаптивным управлением». IEEE Transactions по автоматизированному проектированию интегральных схем и систем. 32 (8): 1180–1193. Дои:10.1109 / TCAD.2012.2189396.

внешняя ссылка

• интеграторы на GPGPU
• код для бессеточного экспоненциального интегратора