• 论文 •    下一篇

Parareal 算法的均方稳定性分析

吴树林1, 王志勇2, 黄乘明3   

  1. 1. 四川理工学院理学院, 四川自贡 643000;
    2. 电子科技大学应用数学学院, 成都 610054;
    3. 华中科技大学数学与统计学院, 武汉 430074
  • 收稿日期:2009-06-20 出版日期:2011-05-15 发布日期:2011-06-04
  • 基金资助:

    本工作得到四川理工学院人才引进项目资助(项目编号:2010XJKRL005)以及国家自然科学基金资助(项目编号:10971077, 60973015).

吴树林, 王志勇, 黄乘明. Parareal 算法的均方稳定性分析[J]. 计算数学, 2011, 33(2): 113-124.

Wu Shulin, Wang Zhiyong, Huang Chengming. ANALYSIS OF MEAN-SQUARE STABILITY OF THE PARAREAL ALGORITHM[J]. Mathematica Numerica Sinica, 2011, 33(2): 113-124.

ANALYSIS OF MEAN-SQUARE STABILITY OF THE PARAREAL ALGORITHM

Wu Shulin1, Wang Zhiyong2, Huang Chengming3   

  1. 1. School of Science, Sichuan University of Science and Engineering, Zigong 643000, Sichuan, China;
    2. School of Applied Mathematics, University of Electronic Science and Technology of China, Chengdu 610054, China;
    3. School of Mathematics and Statistics, Huazhong University of Science and Technology, Wuhan 430074, China
  • Received:2009-06-20 Online:2011-05-15 Published:2011-06-04

Parareal 算法是一种非常有效的实时并行计算方法. 与传统的并行计算方法相比,该算法的显著特点是它的时间并行性 | 先将整个计算时间划分成若干个子区间,然后在每个子区间内同时进行计算. Parareal算法收敛速度快, 并行效率高, 且易于编程实现, 从 2001 年由 Lions,Maday 和 Turinici等人首次提出至今, 在短短的几年间得到了广泛的研究和应用. 最近, Parareal 算法在随机微分方程数值解中的应用也得到了一些学者的关注. 本文中, 我们研究 Parareal算法在随机微分方程数值解中的均方稳定性, 分析保持算法稳定的充分性条件. 通过分析, 我们得到了如下结论: a)Parareal 算法在有限时间区间内是超线性收敛的; b)在无限时间区间内, 该算法是线性收敛的. 最后, 通过数值试验, 我们验证了本文中的理论结果.

Parareal algorithm is a very efficient parallel in time computation methods. Compared with traditional parallel methods, this algorithm has the advantages of faster convergence, higher parallel performance and easy coding. This algorithm was first proposed by Lions, Maday and Turinici in 2001 and has attracted many researchers over the past few years. Recently, the application and theoretical analysis of this algorithm for stochastic computation have been investigated by some researchers. In this paper, we analyze the Mean-square stability of the Parareal algorithm in stochastic computation. The sufficient conditions under which the Parareal algorithm is stable are obtained and it is shown that: a) the algorithm converges superlinearly on any bounded time interval and b) the convergence speed is only linear on unbounded time intervals. Finally, numerical results are given to validate our theoretical conclusions.

MR(2010)主题分类: 

()

[1] Bal G. On the convergence and the stability of the parareal algorithm to solve partial differential equations [J]. In Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng., 2003, 40: 426-432.
[2] Bal G and Maday Y. A “parareal” time discretization for non-linear pde’s with application to the pricing of an American put. In Recent Developments in Domain Decomposition Methods[J]. Lect. Notes Comput. Sci. Eng., 2002, 23: 189-202.
[3] Bal G. Parallelization in time of (stochastic) ordinary differential equations[J]. Submitted (a PDF file is available at http://www.columbia.edu/ gb2030).
[4] Cortial J and Farhat C. A time-parallel implicit method for accelerating the solution of non-linear structural dynamics problems[J]. Internat. J. Numer. Methods Engrg., 2008, 77: 451-470.
[5] Engblom S. Parallel in time simulation of multiscale stochastic chemical kinetics[J]. 2008, to appear in the IT technical report series (a PDF file is available at http://user.it.uu.se/stefane/ssa parareal.pdf.
[6] Engblom S. Time-parallel Simulation of Stochastic Chemical Kinetics[J]. Numerical Analysis and Applied Mathematics: International Conference on Numerical Analysis and Applied Mathematics. AIP Conference Proceedings, 2008, 1048: 174-177.
[7] Farhat C and Chandesris M. Time-decomposed parallel time-integrators: Theory and feasibility studies for fluid, structure, and fluid-structure applications[J]. Internat. J. Numer. Methods Engrg., 2003, 58: 1397-1434.
[8] Farhat C, Cortial J, Dastillung C. and Bavestrello H. Time-parallel implicit integrators for the near-real-time prediction of linear structural dynamic responses[J]. Internat. J. Numer. Methods Engrg., 2006, 67: 697-724.
[9] Gander M J and Petcu M. Analysis of a Krylov Subspace Enhanced Parareal Algorithm[J]. ESAIM Proc., 2008, in press.
[10] Gander M J, Vandewalle S. Analysis of the parareal time-parallel time-integration method[J]. SIAM J. Sci. Comput., 2007, 29: 556-578.
[11] Higham D J. Mean-square and asymptotic stability of the stochastic theta method[J]. SIAM J. Numer. Anal., 2001, 38: 753-769.
[12] Koskodan R and Allen E. Extrapolation of the Stochastic Theta Numerical Method for Stochastic Differential Equations[J]. Stochastic Analysis and Applications, 2006, 24: 475-487.
[13] Lions J L, Maday Y and Turinici G. A “parareal” in time discretization of PDE’s[J]. C. R. Acad. Sci. Paris S′er. I Math., 2001, 332: 661-668.
[14] SubberWand Sarkar A. Performance of A Parallel Time Integrator For Noisy Nonlinear System[J]. Journal of Probabilistic Engineering Mechanics, 2008, to appear.
[15] Staff G A and R?nquist E M. Stability of the parareal algorithm[J]. In Proceedings of the 15th International Domain Decomposition Conference, Lect. Notes Comput. Sci. Eng., 2003, 40: 449-56.
[16] Wu S L, Shi B C and Huang C M. Parareal-Richardson Algorithm for Solving Nonlinear ODEs and PDEs[J]. Communication in Computational Physics, 2009, 6: 883-902.
[17] Wu S L, Shi B C and Huang C M. Convergence and Stability analysis of the Parareal-Richardson Algorithm[J]. Manuscript.

[1] 尚在久, 宋丽娜. 关于辛算法稳定性的若干注记[J]. 计算数学, 2020, 42(4): 405-418.
[2] 洪庆国, 刘春梅, 许进超. 一种抽象的稳定化方法及在非线性不可压缩弹性问题上的应用[J]. 计算数学, 2020, 42(3): 298-309.
[3] 戴小英. 电子结构计算的数值方法与理论[J]. 计算数学, 2020, 42(2): 131-158.
[4] 胡冬冬, 曹学年, 蒋慧灵. 带非线性源项的双侧空间分数阶扩散方程的隐式中点方法[J]. 计算数学, 2019, 41(3): 295-307.
[5] 盛秀兰, 赵润苗, 吴宏伟. 二维线性双曲型方程Neumann边值问题的紧交替方向隐格式[J]. 计算数学, 2019, 41(3): 266-294.
[6] 杨晋平, 李志强, 闫玉斌. 求解Riesz空间分数阶扩散方程的一种新的数值方法[J]. 计算数学, 2019, 41(2): 170-190.
[7] 王志强, 文立平, 朱珍民. 时间延迟扩散-波动分数阶微分方程有限差分方法[J]. 计算数学, 2019, 41(1): 82-90.
[8] 丛玉豪, 胡洋, 王艳沛. 含分布时滞的时滞微分系统多步龙格-库塔方法的时滞相关稳定性[J]. 计算数学, 2019, 41(1): 104-112.
[9] 张根根, 唐蕾, 肖爱国. 求解刚性Volterra延迟积分微分方程的隐显单支方法的稳定性与误差分析[J]. 计算数学, 2018, 40(1): 33-48.
[10] 陈丰, 吴峻峰. 分布式通信响应优化问题及其内点法求解[J]. 计算数学, 2017, 39(4): 378-392.
[11] 肖飞雁, 李旭旭, 陈飞盛. 非线性延迟积分微分方程连续Runge-Kutta方法的稳定性分析[J]. 计算数学, 2017, 39(1): 1-13.
[12] 王涛, 刘铁钢. 求解对流扩散方程的一致四阶紧致格式[J]. 计算数学, 2016, 38(4): 391-404.
[13] 毛文亭, 王文强, 林伟贤. 一类带乘性噪声随机分数阶微分方程Euler方法的弱收敛性与弱稳定性[J]. 计算数学, 2016, 38(4): 442-452.
[14] 刘金存, 李宏, 刘洋, 何斯日古楞. 非线性分数阶反应扩散方程组的间断时空有限元方法[J]. 计算数学, 2016, 38(2): 143-160.
[15] 杨容, 袁光伟, 朱少红. 粒子输运方程的子网格平衡格式的稳定性和收敛性[J]. 计算数学, 2015, 37(4): 439-448.
阅读次数
全文


摘要