常微分方程数值方法

求常微分方程数值解的方法

常微分方程数值方法是用以寻找常微分方程(ODE)解的数值近似值的方法。其使用也称作“数值积分”,不过“数值积分”主要是指积分的计算。

微分方程的数值积分求解图。
  蓝:欧拉法
  绿:中点法
  红:精确解:
步长
时的同一图。时,中点法比欧拉法收敛得更快。

很多微分方程无法精确求解。但在工程学等领域的实际应用中,通常只需得到数值近似解。本文介绍的算法可用于计算这种近似值,另一种方法是用微积分技术得到解的级数展开表达。

常微分方程出现于物理学化学生物学经济学等学科中。[1]此外,偏微分方程数值方法中的一部分将偏微分方程转为常微分方程,然后可用本文所述方法求解。

问题

编辑

一阶微分方程是有如下形式的初值问题(IVP):[2]:533–655

  1

其中f是函数 ,初始条件 是已知向量。“一阶”是说方程中只出现了y的一阶导。

在不失高阶系统一般性的前提下,限制(l)式为一阶微分方程,因为高阶ODE可通过引入额外变量转换为更大的一阶方程组。例如,二阶方程 可重写为2个一阶方程: 

本文介绍IVP的数值方法,并指出边值问题(BVP)需要一套不同的工具:需要在多个点上定义解y的值或成分,因此要用不同方法求解BVP,如打靶法(及其变体),或差分[3]伽辽金法[4]配置法英语Collocation method之类全局方法,都适用于此类问题。

Picard–Lindelöf定理指出,只要f利普希茨连续的,就有唯一解。

方法

编辑

解一阶IVP的数值方法可分为两大类:[5]线性多步法英语Linear multistep method龙格-库塔法。还可进一步划为显式或隐式,例如隐式线性多步法包括亚当斯-莫尔顿法(Adams-Moulton methods)与向后微分公式英语Backward differentiation formula(BDF),隐式龙格-库塔法[6]:204–215包括对角隐式龙格-库塔法(DIRK)、[7][8]单对角隐式龙格-库塔法(SDIRK)[9]与基于高斯求积[10]的高斯–拉道法[11]等等。线性多步法中的显式方法有亚当斯-巴什福思法,布彻表(Butcher tableau)为下对角的龙格-库塔法都是显式方法。根据经验,刚性微分方程需要用隐式方案,而非刚性问题则可用显示方案更有效地求解。

所谓一般线性方法英语General linear methods(GLM)是上述两大类方法的概括。[12]

欧拉法

编辑

从曲线上任意一点出发,沿与曲线相切的直线移动一小段距离,就能得到曲线上邻近点的近似值。

从微分方程(1)开始,可用差分近似代替导数y′:

  2

重新排列后得到以下公式

 

利用(1)可得

  3

此式的应用通常如下:择步长h,构造序列 记精确解 的数值估计值为 。受(3)启发,可用下面的递归方法计算估计值:

  4

这就是(前向)欧拉法,是莱昂哈德·欧拉(1768)描述的方法。

欧拉法是显式方法的一个例子,这是说新值 是根据已知值(如 )定义的。

反向欧拉法

编辑

若不用(2),而用近似值

  5

则得到反向欧拉法

  6

反向欧拉法是隐式方法,这是说需要求解一个方程才能得到新值 。通常用定点迭代牛顿-拉弗森法(的某种修改版)实现之。

隐式方法求解这方程比显示方法直接代入要花更多时间,选择方法时必须考虑这一成本。隐式方法(如(6))的优点是求解刚性方程时通常更稳定,便可以使用更大的步长h

一阶指数积分法

编辑

指数积分英语Exponential integrator描述了一大类积分器,近来得到了长足发展。[13]它们至少可以追溯到20世纪60年代。

此处不用(1),假设微分方程形式为

  7

或已被局部线性化,围绕背景状态产生线性项 与非线性项 

将(7)乘以 ,并在时间区间 内精确积分,便构造得到了指数积分:

 

此积分方程是精确的,但并没有定义积分。

使 在整个区间内不变,可实现一阶指数积分:

  8

推广

编辑

欧拉法往往不够精确。更准确地说,只有一阶(下面将介绍阶的概念),这就促使数学家寻找高阶方法。

一种方法是,用 以及更多之前的值确定 ,所谓多步法便实现了这种想法。最简单的可能是蛙跳积分法,其是二阶方法,(粗略地说)依赖于2个时间值。

几乎所有实用的多步法都属于线性多步法英语Linear multistep method,形式为  

另一种方法是在区间 内取更多点。这产生了得名于卡尔·龙格马丁·威廉·库塔龙格-库塔法,其中一种4阶方法尤为流行。

高级特征

编辑

要用这些方法求解ODE,需要的不仅是时间步长公式。始终相同的步长效率不高,于是开发了可变步长方法。通常,步长的选择应使每步的(局部)误差低于某容差水平,这意味着方法还要计算误差指标(error indicator),即对局部误差的估计。

这一思想的延伸是在不同阶方法之间动态选择(称作可变阶数方法)。基于理查德森外推法[14]Bulirsch–Stoer算法之类方法[15][16]通常用于构建各种不同阶的方法。

其他理想特征还有:

  • 输出稠密:不仅对点 ,还对整个积分区间进行低成本数值逼近;
  • 事件定位:找到事件发生的位置,例如某函数取0的时间。通常用求根算法
  • 支持并行计算
  • 用于时间积分时,具有时间可逆性。

其他方法

编辑

很多方法不在讨论的框架内,如

实时并行方法

编辑

有些IVP要求积分具有很高的时间分辨率和/或很长的时间区间,传统的序列时间步进法无法实时计算(如数值天气预报、等离子体建模与分子动力学中的IVP)。针对这些问题,人们开发了实时并行(PinT)法以便用并行计算缩短运行时间。

早期的PinT法(最早提出于20世纪60年代)[20]最初被研究人员忽视,因为其所需的并行计算架构尚未普及。2000年代初,随着算力的提高,灵活易用的PinT算法——Parareal算法英语Parareal重新吸引了兴趣,它适用于求解各种IVP。百亿亿次级运算英语Exascale computing的出现使PinT算法获得更多关注,并启动了能用于世界上最强大的超级计算机的算法开发。截至2023年,最流行的方法有Parareal、PFASST、ParaDiag、MGRIT等,[21]

分析

编辑

数值分析不仅包括数值方法的设计,还包括其分析。分析中的3个核心概念是:

  • 收敛性:方法是否逼近解;
  • 阶数:近似解的程度;
  • 数值稳定性:误差是否能得到抑制。[22]

收敛性

编辑

若数值解随着步长h趋近于0而逼近精确解,则称此数值方法具有收敛性(convergent)。更确切地说,要求对利普希茨函数f与每个 ,ODE (1)

 

上述所有方法都收敛。

一致性与阶数

编辑

设数值方法

 

方法的局部(截断)误差定义为迭代一步产生的误差。即,假设之前的迭代无误差,则是此方法结果与精确解之间的差

 

 

则称此方法一致(consistent)。若

 

则称此方法阶数为p。因此,阶数不为0的方法是一致的。上文介绍的两种欧拉法(4、6)都是1阶的,因此是一致的。实践中使用的大多数方法阶数更高。一致性是收敛的必要条件[来源请求],但不是充分条件;方法要收敛,必须同时具有一致性与零稳性(zero-stable)。

一个相关概念是全局(截断)误差,即达到固定时间t所需所有步骤中持续存在的误差。明确地说,t时刻的全局误差是 ,其中 。第p阶一步法是收敛的,其全局误差是 。对多阶方法,这一说法不一定成立。

稳定性与刚性

编辑

对某些微分方程,欧拉法、显式龙格-库塔法、多步法(如亚当斯-巴什福思法)之类标准方法会表现出解的不稳定性,其他方法则可能产生稳定的解。方程中的这种“困难行为”(本身不一定复杂)称作“刚性”(stiffness),通常是由于底问题中存在不同时间尺度造成的。[23]例如,机械系统中的碰撞(如碰撞振子中的)发生的时间尺度通常比物体运动的时间尺度小得多,这种差异使状态参数曲线变得非常陡峭。

刚性问题在化学动力学控制论固体力学天气预报生物学等离子体物理、电子学等领域中无处不在。克服刚性的一种方法是将微分方程推广到微分包含式,从而允许非光滑性并建立其模型。[24][25]

历史

编辑

下面是该领域一些重要进展的时间线。[26][27]

二阶一维边值问题的数值解法

编辑

边值问题(BVPs)通常要离散化,得到近似相等的矩阵问题再数值求解。[28]最常用的一维BVP数值求解方法称作有限差分法[3]这种方法用点值的线性组合构造描述函数导数的有限差分系数,例如一阶导数的二阶中心差分近似为:

 

二阶导数的二阶中心差分近似为:

 

两式中, 是离散域上相邻x值间的距离。这样就构建了线性系统,然后可用标准矩阵法求解。例如,待解方程:

 

下一步是将问题离散化,用线性导数近似,如

 

并解所得线性方程组。将有如下方程

 

初看之下,这个方程组似乎有困难,因为方程中没有不与变量相乘的项,但事实上这是错误的。i = 1或n − 1时,有一项涉及边值  ,由于两值已知,可以简单地代入,就得到了具有非平凡解的非齐次线性方程组

相关条目

编辑

注释

编辑
  1. ^ Chicone, C. (2006). Ordinary differential equations with applications (Vol. 34). Springer Science & Business Media.
  2. ^ Bradie (2006)
  3. ^ 3.0 3.1 LeVeque, R. J. (2007). Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems (Vol. 98). SIAM.
  4. ^ Slimane Adjerid and Mahboub Baccouch (2010) Galerkin methods. Scholarpedia, 5(10):10056.
  5. ^ Griffiths, D. F., & Higham, D. J. (2010). Numerical methods for ordinary differential equations: initial value problems. Springer Science & Business Media.
  6. ^ Hairer, Nørsett & Wanner (1993)
  7. ^ Alexander, R. (1977). Diagonally implicit Runge–Kutta methods for stiff ODE’s. SIAM Journal on Numerical Analysis, 14(6), 1006-1021.
  8. ^ Cash, J. R. (1979). Diagonally implicit Runge-Kutta formulae with error estimates. IMA Journal of Applied Mathematics, 24(3), 293-301.
  9. ^ Ferracina, L., & Spijker, M. N. (2008). Strong stability of singly-diagonally-implicit Runge–Kutta methods. Applied Numerical Mathematics, 58(11), 1675-1686.
  10. ^ Weisstein, Eric W. "Gaussian Quadrature." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GaussianQuadrature.html页面存档备份,存于互联网档案馆
  11. ^ Everhart, E. (1985). An efficient integrator that uses Gauss-Radau spacings. In International Astronomical Union Colloquium (Vol. 83, pp. 185-202). Cambridge University Press.
  12. ^ Butcher, J. C. (1987). The numerical analysis of ordinary differential equations: Runge-Kutta and general linear methods. Wiley-Interscience.
  13. ^ Hochbruck (2010,第209–286页) This is a modern and extensive review paper for exponential integrators
  14. ^ Brezinski, C., & Zaglia, M. R. (2013). Extrapolation methods: theory and practice. Elsevier.
  15. ^ Monroe, J. L. (2002). Extrapolation and the Bulirsch-Stoer algorithm. Physical Review E, 65(6), 066116.
  16. ^ Kirpekar, S. (2003). Implementation of the Bulirsch Stoer extrapolation method. Department of Mechanical Engineering, UC Berkeley/California.
  17. ^ Nurminskii, E. A., & Buryi, A. A. (2011). Parker-Sochacki method for solving systems of ordinary differential equations using graphics processors. Numerical Analysis and Applications, 4(3), 223.
  18. ^ Hairer, E., Lubich, C., & Wanner, G. (2006). Geometric numerical integration: structure-preserving algorithms for ordinary differential equations (Vol. 31). Springer Science & Business Media.
  19. ^ Hairer, E., Lubich, C., & Wanner, G. (2003). Geometric numerical integration illustrated by the Störmer–Verlet method. Acta Numerica, 12, 399-450.
  20. ^ Nievergelt, Jürg. Parallel methods for integrating ordinary differential equations. Communications of the ACM. 1964, 7 (12): 731–733. S2CID 6361754. doi:10.1145/355588.365137 . 
  21. ^ Parallel-in-Time.org. Parallel-in-Time.org. [2023-11-15]. (原始内容存档于2023-11-15). 
  22. ^ Higham, N. J. (2002). Accuracy and stability of numerical algorithms (Vol. 80). SIAM.
  23. ^ Miranker, A. (2001). Numerical Methods for Stiff Equations and Singular Perturbation Problems: and singular perturbation problems (Vol. 5). Springer Science & Business Media.
  24. ^ Markus Kunze; Tassilo Kupper. Non-smooth Dynamical Systems: An Overview. Bernold Fiedler (编). Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems. Springer Science & Business Media. 2001: 431. ISBN 978-3-540-41290-8. 
  25. ^ Thao Dang. Model-Based Testing of Hybrid Systems. Justyna Zander, Ina Schieferdecker and Pieter J. Mosterman (编). Model-Based Testing for Embedded Systems. CRC Press. 2011: 411. ISBN 978-1-4398-1845-9. 
  26. ^ Brezinski, C., & Wuytack, L. (2012). Numerical analysis: Historical developments in the 20th century. Elsevier.
  27. ^ Butcher, J. C. (1996). A history of Runge-Kutta methods. Applied numerical mathematics, 20(3), 247-260.
  28. ^ Ascher, U. M., Mattheij, R. M., & Russell, R. D. (1995). Numerical solution of boundary value problems for ordinary differential equations. Society for Industrial and Applied Mathematics.

参考文献

编辑
  • Bradie, Brian. A Friendly Introduction to Numerical Analysis. Upper Saddle River, New Jersey: Pearson Prentice Hall. 2006. ISBN 978-0-13-013054-9. 
  • J. C. Butcher, Numerical methods for ordinary differential equations, ISBN 0-471-96758-0
  • Ernst Hairer, Syvert Paul Nørsett and Gerhard Wanner, Solving ordinary differential equations I: Nonstiff problems, second edition, Springer Verlag, Berlin, 1993. ISBN 3-540-56670-8.
  • Ernst Hairer and Gerhard Wanner, Solving ordinary differential equations II: Stiff and differential-algebraic problems, second edition, Springer Verlag, Berlin, 1996. ISBN 3-540-60452-9.
    (This two-volume monograph systematically covers all aspects of the field.)
  • Hochbruck, Marlis; Ostermann, Alexander. Exponential integrators. Acta Numerica. May 2010, 19: 209–286. Bibcode:2010AcNum..19..209H. CiteSeerX 10.1.1.187.6794 . S2CID 4841957. doi:10.1017/S0962492910000048. 
  • Arieh Iserles, A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, 1996. ISBN 0-521-55376-8 (hardback), ISBN 0-521-55655-4 (paperback).
    (Textbook, targeting advanced undergraduate and postgraduate students in mathematics, which also discusses numerical partial differential equations.)
  • John Denholm Lambert, Numerical Methods for Ordinary Differential Systems, John Wiley & Sons, Chichester, 1991. ISBN 0-471-92990-5.
    (Textbook, slightly more demanding than the book by Iserles.)

外部链接

编辑