非线性微分代数方程系统的离散波形松弛方法
|
摘要
在电路分析、计算机辅助设计、多体力学系统的实时仿真、化学反应模拟以及管理系统等科学与工程应用领域中的许多问题,都可以抽象为一个微分代数系统。常用于解微分代数方程的方法主要是求解常微分方程的数值方法的推广。20世纪80年代,E.Lelarasmee等人在对超大规模集成电路进行数值模拟时,提出了波形松弛方法,用该方法处理模拟电路中相应的微分代数方程系统,取得了很好的数值效果。波形松弛方法的提出,为微分代数方程的数值求解提供了一种新的途径。随后,波形松弛方法的并行性及解耦性引起了研究者们的注意。
波形松弛方法又称动态迭代方法,是一种连续时间的迭代过程,对迭代后的方程进行时间上的离散称为离散时间的动态迭代过程。波形松弛算法的基本思想就是把原来的大规模系统分解成多个松散耦合的规模较小的子系统,然后分别求解每个子系统。
本文首先回顾了波形松弛方法的产生背景,针对连续时间和离散时间波形松弛迭代格式,总结了这一方法的发展历史及研究概况。接着在吸收前人的优秀成果基础上,研究了微分代数方程的离散波形松弛。第二章涉及隐式微分代数方程,对应用向后微分公式导致的离散时间波形松弛方法进行了进一步的研究,得到了收敛性结果。第三章涉及显式微分代数方程,针对单支方法和线性多步法导致的离散时间波形松弛法开展收敛性研究。通过运用矩阵分裂的相关性质,我们在一定的假设条件下证明了离散波形松弛方法的收敛性,并获得了明确的时间步长收敛区间。第四章针对一类积分微分代数方程,研究了基于单支θ?方法和线性θ?方法的离散时间波形松弛方法,给出了相应的收敛性结论。最后第五章针对本文所得的主要结论,给出了具体的数值试验,验证结论的正确性和方法的有效性。
Many problems in areas of science and engineering can be modeled by differential algebraic systems. Methods commonly used in the solution of differential-algebraic equation are an extension of numerical methods for solving ordinary differential equations. In 1980’s, E.Lelarasmee et.al introduced waveform relaxation approach to solve the dynamical systems which are described by a system of mixed implicit algebraic-differential equations. Theoretical and computational studies show the method to be efficient and reliable. For the numerical solution of differential-algebraic equation waveform relaxation method provides a new way. After that, Parallel and decoupling properties of waveform relaxation approach begin to get more attentions.
Waveform relaxation (WR) is a decoupling technique of large systems, which is first applied in circuit simulation. It is sometimes called dynamic iteration. The iterative equation for the discrete time is called as discrete-time dynamic iterative process. The key idea of waveform relaxation algorithm is to decompose original large systems into several subsystems, and then solve for each subsystem.
In this paper we first review the background to the selection of waveform relaxation algorithm and introduce the history and development of this approach research. We mainly study the convergence conditions of the discrete-time waveform relaxation algorithm. In section two, we first discuss the discrete-time waveform relaxation method for an implicit system of nonlinear differential-algebraic equations which is derived by the backward-differentiation formulas (BDFs) and give some conclusions for the convergence of the methods. Then in section three, by discretising continuous-time waveforms using one-leg methods and linear multistep methods, we study the discrete-time waveform relaxation solutions, and some convergence conclusions are achieved. The proof is based on the properties of matrices. Under some assumptions, we get the convergence interval of the time step. By use of the one legθ-method and the linearθ-method, we obtain some conclusions for the convergence of the discrete waveforms of nonlinear integral-differential-algebraic equations in section four. Numerical experiments are provided to illustrate the theoretical results in section five.
波形松弛方法又称动态迭代方法,是一种连续时间的迭代过程,对迭代后的方程进行时间上的离散称为离散时间的动态迭代过程。波形松弛算法的基本思想就是把原来的大规模系统分解成多个松散耦合的规模较小的子系统,然后分别求解每个子系统。
本文首先回顾了波形松弛方法的产生背景,针对连续时间和离散时间波形松弛迭代格式,总结了这一方法的发展历史及研究概况。接着在吸收前人的优秀成果基础上,研究了微分代数方程的离散波形松弛。第二章涉及隐式微分代数方程,对应用向后微分公式导致的离散时间波形松弛方法进行了进一步的研究,得到了收敛性结果。第三章涉及显式微分代数方程,针对单支方法和线性多步法导致的离散时间波形松弛法开展收敛性研究。通过运用矩阵分裂的相关性质,我们在一定的假设条件下证明了离散波形松弛方法的收敛性,并获得了明确的时间步长收敛区间。第四章针对一类积分微分代数方程,研究了基于单支θ?方法和线性θ?方法的离散时间波形松弛方法,给出了相应的收敛性结论。最后第五章针对本文所得的主要结论,给出了具体的数值试验,验证结论的正确性和方法的有效性。
Many problems in areas of science and engineering can be modeled by differential algebraic systems. Methods commonly used in the solution of differential-algebraic equation are an extension of numerical methods for solving ordinary differential equations. In 1980’s, E.Lelarasmee et.al introduced waveform relaxation approach to solve the dynamical systems which are described by a system of mixed implicit algebraic-differential equations. Theoretical and computational studies show the method to be efficient and reliable. For the numerical solution of differential-algebraic equation waveform relaxation method provides a new way. After that, Parallel and decoupling properties of waveform relaxation approach begin to get more attentions.
Waveform relaxation (WR) is a decoupling technique of large systems, which is first applied in circuit simulation. It is sometimes called dynamic iteration. The iterative equation for the discrete time is called as discrete-time dynamic iterative process. The key idea of waveform relaxation algorithm is to decompose original large systems into several subsystems, and then solve for each subsystem.
In this paper we first review the background to the selection of waveform relaxation algorithm and introduce the history and development of this approach research. We mainly study the convergence conditions of the discrete-time waveform relaxation algorithm. In section two, we first discuss the discrete-time waveform relaxation method for an implicit system of nonlinear differential-algebraic equations which is derived by the backward-differentiation formulas (BDFs) and give some conclusions for the convergence of the methods. Then in section three, by discretising continuous-time waveforms using one-leg methods and linear multistep methods, we study the discrete-time waveform relaxation solutions, and some convergence conclusions are achieved. The proof is based on the properties of matrices. Under some assumptions, we get the convergence interval of the time step. By use of the one legθ-method and the linearθ-method, we obtain some conclusions for the convergence of the discrete waveforms of nonlinear integral-differential-algebraic equations in section four. Numerical experiments are provided to illustrate the theoretical results in section five.
引文
[1] E.Lelarasmee, A.E.Ruehli, A.L.Sangiovanni-Vincentelli. The waveform relaxation method for time-domain analysis of large scale integrated circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982, 1(3): 131~145
[2] Ulla Miekkala, Olavi Nevanlinna. Convergence of dynamic iteration methods for initial value problems. SIAM J. Sci. Stat. Comput., 1987, 8(4): 459~482
[3] Ulla Miekkala, Olavi Nevanlinna. Set of convergence and stability regions. BIT, 1987, 27: 554~584
[4] Ch.Lubich, A.Ostermann. Multi-grid dynamic iteration for parabolic equations. BIT, 1987, 27: 216~234
[5] O.Nevanlinna. Remarks on Picard-lindolof Iteration. BIT, 1989, 29: 328~346
[6] O.Nevanlinna. Remarks on Picard-lindolof Iteration. BIT, 1989, 29: 535~562
[7] U.Miekkala. Dynamic iteration methods applied to linear DAE systems. Journal of Computational and Applied Mathematics, 1989, 25: 133~151
[8] B.Pohl. On the convergence of the discretized multisplitting waveform relaxation algorithm. Applied Numerical Mathematics. 1993, 11: 251~258
[9] K.R.Schneider. A note on the waveform relaxation method. Anal. Model. Simul., 1991, 8: 599~605
[10] Z.Jackiewicz, M.Kwapisz. Convergence of waveform relaxation methods for differential-algebraic systems. SIAM J. Numer. Anal., 1996, 33(6): 2303~2317
[11] Jiang Yaolin, O.Wing. A note on convergence conditions of waveform relaxation algorithms for nonlinear differential-algebraic equations. Applied Numerical Mathematics, 2001, 36: 281~297
[12] Jiang Yaolin. A general approach to waveform relaxation solutions of nonlinear differential-algebraic equations:The continuous-time and discrete-time cases. IEEE Transactions on Circuits and Systems-I: Regular papers, 2004, 51(9): 1770~1780
[13] Jiang Yaolin. Waveform relaxation methods of nonlinear integral-differential- algebraic equations. Journal of Computational Mathematics, 2005, 23(1): 49~66
[14] M.Bjqrhus. A note on the convergence of discretized dynamic iteration. BIT, 1995, 35: 291~296
[15] Gu Tongxiang, Li Wenqiang. Discretized multisplitting AOR waveform relaxationalgorithms for initial value problem of systems of ODEs. Chinese Quarterly Journal of Mathematics. 1997, 12(4): 27~35
[16] Jin Xiaoqing, Vai-kuong Sin, Song Lili. Circulant preconditioned WR-BVM methods for ODE systems. Journal of Computational and Applied Mathematics, 2004, 162: 201~211
[17] Jin Xiaoqing, Vai-kuong Sin, Song Lili. Preconditioned WR-LMF-based method for ODE systems. Journal of Computational and Applied Mathematics, 2004, 162: 431~444
[18] M.L.Crow,D.C.Ilic.The waveform relaxation method for systems of differential/ algebraic equations. Mathematical and Computer Modelling, 1994, 19(12): 67~84
[19] Jiang Yaolin, W.S.Luk, O.Wing. Convergence theoretics of classical and Krylov waveform relaxation methods for differential-algebraic equations. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 1997, E80-A(10):1961 ~1972
[20] Aleksandar I., Zecevic, Nebojsa Gacic. Apartitioning algorithm for the parallel solution of differential-algebraic equations by waveform relaxation. IEEE Transactions on circuits and systems I: Fundamental theory and applications, 1999, 46(4): 421~434
[21] Jiang Yaolin, O.Wing. Monotone waveform relaxation for systems of nonlinear differential-algebraic equations. SIAM Journal on Numerical Analysis, 2000, 38(1): 170~185
[22] J.M.Bahi, K.Rhofir, J.-C.Miellou. Parallel solution of linear DAEs by multisplitting waveform relaxation methods. Linear Algebra and its Applications, 2001, 332-334:181~196
[23] 韩昌玲, 徐建华. 微分代数系统波形松弛法的收敛性. 合肥学院学报(自然科学版),2006, 16(1): 5~7
[24] Jiang Yaolin, R.M.M.Chen, O.Wing. Waveform relaxation of nonlinear second-order diferential equations. IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, 2001, 48(11): 1344~1347
[25] 马菊侠, 吴云天, 白云霄. 非线性高阶微分方程初值问题的波形松弛方法. 哈尔滨工业大学学报, 2004, 36(8):1077~1079
[26] M.R.Crisci, N.Ferraro,E.Russo. Convergence results for continuous-time waveformmethods for Volterra integral equations, Journal of Computational and Applied Mathematics, 1996, 71(1 ): 33~45
[27] M.R.Crisci, E.Russo, A.Vecchio. Time point relaxation methods for Volterra integro-differential equations. Computers Math. Applic., 1998, 36(9): 59~70
[28] M.Bjqrhus. On dynamic iteration for delay differential equations. BIT, 1994, 34:325~336
[29] Z.Bartoszewski, M.Kwapisz. On error estimates for waveform relaxation methods for delay-diferential equations. SIAM J. Numer. Anal., 2000, 38(2): 639~659
[30] Z.Bartoszewski, M.Kwapisz. Remarks on evaluation of spectral radius of operators arising in WR methods for linear systems of ODEs. Applied Numerical Mathematics, 2006, 56: 332~344
[31] T.Jankowski, M.Kwapisz, Gdansk. Convergence of numerical methods for systems of neutral functional-differential-algebraic equations. Applications of Mathematics. 1995, 40(6): 457~472
[32] Z.Jackiewicz, M.Kwapisz, ELo. Waveform relaxation methods for functional differential systems of neutral type. Journal of Mathematical Analysis and Applications, 1997, 207: 255~285
[33] Z.Bartoszewski, M.Kwapisz. On the convergence of waveform relaxation methods for differential-functional systems of equations. Journal of Mathematical Analysis and Applications, 1999, 235: 478~496
[34] B.Zubik-Kowal, S.Vandewalle. Waveform relaxation for functional-differential equations. SIAM J. Sci.Comput., 1999, 21(1): 207~226
[35] Barbara Zubik-Kowal. Error bounds for spatial discretization and waveform relaxation applied to parabolic functional differential equations. J. Math. Anal. Appl., 2004, 293: 496~510
[36] Z.Bartoszewski,T.Jankowski, M.Kwapisz. On the convergence of iterative methods for general differential-algebraic systems. Journal of Computational and Applied Mathematics, 2004, 169: 393~418
[37] Z.Bartoszewski, M.Kwapisz. Delay dependent estimates for waveform relaxation methods for neutral differential-functional systems. Computers and Mathematics with Applications, 2004, 48: 1877~1892
[38] 王宇莹, 赵炜, 王峰. 一类泛函微分代数系统的波形松弛方法. 工程数学学报,2006, 23(1): 71~78
[39] J.Janssen, S.Vandewalle. Multigrid waveform relaxation on spatial finite element meshes:The continuous-time case. SIAM J. Numer. Anal., 1996, 33(2): 456~474
[40] J.Janssen, S.Vandewalle. Multigrid waveform relaxation on spatial finite element meshes: the discrete-time case. SIAM J. Sci. Comput., 1996, 17(1): 133~155
[41] R.Jeltsch, B.Pohl. Waveform relaxation with overlapping splittings. SIAM J. Sci. Comput., 1995, 16(1): 40~49
[42] Yuan Dongjin, Kevin Burrage. Convergence of the parallel chaotic waveform relaxation method for stiff systems. Journal of Computational and Applied Mathematics, 2003, 151: 201~213
[43] M.W.Reichelt, J.K.White, J.Allen. Optimal convolution SOR acceleration of waveform relaxation with application to parallel simulation of semiconductor devices. SIAM J. Sci.Comput., 1995, 16(5):1137~1158
[44] Yuan Dongjin. On the accelerative convergence of discretized waveform method for solving ordinary differential systens. Mathematica Applicata, 2002, 15(1): 133~137
[45] Roberto Garrappa. An analysis of conwergence for two-stage waveform relaxation methods. Journal of Computational and Applied Mathematics, 2004,169: 377~392
[46] Wang Jiang, Bai Zhongzhi. Convergence analysis of two-stage waveform relaxation method for the initial value problems. Applied Mathematics and Computation, 2006, 172: 797~808
[47] Pan Jianyu, Bai Zhongzhi. On the convergence of waveform relaxation methods for linear initial value problem. Journal of Computational Mathematics, 2004, 22(5): 681~698
[48] Bai Zhongzhi, M.K.Ng, Pan Jianyu. Alternating splitting waveform relaxation method and its successive overrelaxation acceleration. Computers and Mathematics with Applications, 2005, 49: 157~170
[49] Jiang Yaolin, O. Wing. Waveform relaxation of linear integral-differential equations for circuit simulation. Proceedings of the ASP-DAC ’99 Asia and South Pacific Design Automation Conference 1999, 1999, 1(1): 61~64
[50] R.S.Varga. Matrix iterative analysis, second edition. Springer, Berlin, 2000, 87~110
[51] 陈景良,陈向晖. 特殊矩阵. 北京: 清华大学出版社, 2001, 239~304
[2] Ulla Miekkala, Olavi Nevanlinna. Convergence of dynamic iteration methods for initial value problems. SIAM J. Sci. Stat. Comput., 1987, 8(4): 459~482
[3] Ulla Miekkala, Olavi Nevanlinna. Set of convergence and stability regions. BIT, 1987, 27: 554~584
[4] Ch.Lubich, A.Ostermann. Multi-grid dynamic iteration for parabolic equations. BIT, 1987, 27: 216~234
[5] O.Nevanlinna. Remarks on Picard-lindolof Iteration. BIT, 1989, 29: 328~346
[6] O.Nevanlinna. Remarks on Picard-lindolof Iteration. BIT, 1989, 29: 535~562
[7] U.Miekkala. Dynamic iteration methods applied to linear DAE systems. Journal of Computational and Applied Mathematics, 1989, 25: 133~151
[8] B.Pohl. On the convergence of the discretized multisplitting waveform relaxation algorithm. Applied Numerical Mathematics. 1993, 11: 251~258
[9] K.R.Schneider. A note on the waveform relaxation method. Anal. Model. Simul., 1991, 8: 599~605
[10] Z.Jackiewicz, M.Kwapisz. Convergence of waveform relaxation methods for differential-algebraic systems. SIAM J. Numer. Anal., 1996, 33(6): 2303~2317
[11] Jiang Yaolin, O.Wing. A note on convergence conditions of waveform relaxation algorithms for nonlinear differential-algebraic equations. Applied Numerical Mathematics, 2001, 36: 281~297
[12] Jiang Yaolin. A general approach to waveform relaxation solutions of nonlinear differential-algebraic equations:The continuous-time and discrete-time cases. IEEE Transactions on Circuits and Systems-I: Regular papers, 2004, 51(9): 1770~1780
[13] Jiang Yaolin. Waveform relaxation methods of nonlinear integral-differential- algebraic equations. Journal of Computational Mathematics, 2005, 23(1): 49~66
[14] M.Bjqrhus. A note on the convergence of discretized dynamic iteration. BIT, 1995, 35: 291~296
[15] Gu Tongxiang, Li Wenqiang. Discretized multisplitting AOR waveform relaxationalgorithms for initial value problem of systems of ODEs. Chinese Quarterly Journal of Mathematics. 1997, 12(4): 27~35
[16] Jin Xiaoqing, Vai-kuong Sin, Song Lili. Circulant preconditioned WR-BVM methods for ODE systems. Journal of Computational and Applied Mathematics, 2004, 162: 201~211
[17] Jin Xiaoqing, Vai-kuong Sin, Song Lili. Preconditioned WR-LMF-based method for ODE systems. Journal of Computational and Applied Mathematics, 2004, 162: 431~444
[18] M.L.Crow,D.C.Ilic.The waveform relaxation method for systems of differential/ algebraic equations. Mathematical and Computer Modelling, 1994, 19(12): 67~84
[19] Jiang Yaolin, W.S.Luk, O.Wing. Convergence theoretics of classical and Krylov waveform relaxation methods for differential-algebraic equations. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 1997, E80-A(10):1961 ~1972
[20] Aleksandar I., Zecevic, Nebojsa Gacic. Apartitioning algorithm for the parallel solution of differential-algebraic equations by waveform relaxation. IEEE Transactions on circuits and systems I: Fundamental theory and applications, 1999, 46(4): 421~434
[21] Jiang Yaolin, O.Wing. Monotone waveform relaxation for systems of nonlinear differential-algebraic equations. SIAM Journal on Numerical Analysis, 2000, 38(1): 170~185
[22] J.M.Bahi, K.Rhofir, J.-C.Miellou. Parallel solution of linear DAEs by multisplitting waveform relaxation methods. Linear Algebra and its Applications, 2001, 332-334:181~196
[23] 韩昌玲, 徐建华. 微分代数系统波形松弛法的收敛性. 合肥学院学报(自然科学版),2006, 16(1): 5~7
[24] Jiang Yaolin, R.M.M.Chen, O.Wing. Waveform relaxation of nonlinear second-order diferential equations. IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, 2001, 48(11): 1344~1347
[25] 马菊侠, 吴云天, 白云霄. 非线性高阶微分方程初值问题的波形松弛方法. 哈尔滨工业大学学报, 2004, 36(8):1077~1079
[26] M.R.Crisci, N.Ferraro,E.Russo. Convergence results for continuous-time waveformmethods for Volterra integral equations, Journal of Computational and Applied Mathematics, 1996, 71(1 ): 33~45
[27] M.R.Crisci, E.Russo, A.Vecchio. Time point relaxation methods for Volterra integro-differential equations. Computers Math. Applic., 1998, 36(9): 59~70
[28] M.Bjqrhus. On dynamic iteration for delay differential equations. BIT, 1994, 34:325~336
[29] Z.Bartoszewski, M.Kwapisz. On error estimates for waveform relaxation methods for delay-diferential equations. SIAM J. Numer. Anal., 2000, 38(2): 639~659
[30] Z.Bartoszewski, M.Kwapisz. Remarks on evaluation of spectral radius of operators arising in WR methods for linear systems of ODEs. Applied Numerical Mathematics, 2006, 56: 332~344
[31] T.Jankowski, M.Kwapisz, Gdansk. Convergence of numerical methods for systems of neutral functional-differential-algebraic equations. Applications of Mathematics. 1995, 40(6): 457~472
[32] Z.Jackiewicz, M.Kwapisz, ELo. Waveform relaxation methods for functional differential systems of neutral type. Journal of Mathematical Analysis and Applications, 1997, 207: 255~285
[33] Z.Bartoszewski, M.Kwapisz. On the convergence of waveform relaxation methods for differential-functional systems of equations. Journal of Mathematical Analysis and Applications, 1999, 235: 478~496
[34] B.Zubik-Kowal, S.Vandewalle. Waveform relaxation for functional-differential equations. SIAM J. Sci.Comput., 1999, 21(1): 207~226
[35] Barbara Zubik-Kowal. Error bounds for spatial discretization and waveform relaxation applied to parabolic functional differential equations. J. Math. Anal. Appl., 2004, 293: 496~510
[36] Z.Bartoszewski,T.Jankowski, M.Kwapisz. On the convergence of iterative methods for general differential-algebraic systems. Journal of Computational and Applied Mathematics, 2004, 169: 393~418
[37] Z.Bartoszewski, M.Kwapisz. Delay dependent estimates for waveform relaxation methods for neutral differential-functional systems. Computers and Mathematics with Applications, 2004, 48: 1877~1892
[38] 王宇莹, 赵炜, 王峰. 一类泛函微分代数系统的波形松弛方法. 工程数学学报,2006, 23(1): 71~78
[39] J.Janssen, S.Vandewalle. Multigrid waveform relaxation on spatial finite element meshes:The continuous-time case. SIAM J. Numer. Anal., 1996, 33(2): 456~474
[40] J.Janssen, S.Vandewalle. Multigrid waveform relaxation on spatial finite element meshes: the discrete-time case. SIAM J. Sci. Comput., 1996, 17(1): 133~155
[41] R.Jeltsch, B.Pohl. Waveform relaxation with overlapping splittings. SIAM J. Sci. Comput., 1995, 16(1): 40~49
[42] Yuan Dongjin, Kevin Burrage. Convergence of the parallel chaotic waveform relaxation method for stiff systems. Journal of Computational and Applied Mathematics, 2003, 151: 201~213
[43] M.W.Reichelt, J.K.White, J.Allen. Optimal convolution SOR acceleration of waveform relaxation with application to parallel simulation of semiconductor devices. SIAM J. Sci.Comput., 1995, 16(5):1137~1158
[44] Yuan Dongjin. On the accelerative convergence of discretized waveform method for solving ordinary differential systens. Mathematica Applicata, 2002, 15(1): 133~137
[45] Roberto Garrappa. An analysis of conwergence for two-stage waveform relaxation methods. Journal of Computational and Applied Mathematics, 2004,169: 377~392
[46] Wang Jiang, Bai Zhongzhi. Convergence analysis of two-stage waveform relaxation method for the initial value problems. Applied Mathematics and Computation, 2006, 172: 797~808
[47] Pan Jianyu, Bai Zhongzhi. On the convergence of waveform relaxation methods for linear initial value problem. Journal of Computational Mathematics, 2004, 22(5): 681~698
[48] Bai Zhongzhi, M.K.Ng, Pan Jianyu. Alternating splitting waveform relaxation method and its successive overrelaxation acceleration. Computers and Mathematics with Applications, 2005, 49: 157~170
[49] Jiang Yaolin, O. Wing. Waveform relaxation of linear integral-differential equations for circuit simulation. Proceedings of the ASP-DAC ’99 Asia and South Pacific Design Automation Conference 1999, 1999, 1(1): 61~64
[50] R.S.Varga. Matrix iterative analysis, second edition. Springer, Berlin, 2000, 87~110
[51] 陈景良,陈向晖. 特殊矩阵. 北京: 清华大学出版社, 2001, 239~304