离散ADI波形松弛方法的收敛性
|
摘要
大型常微分方程组的求解是计算数学的核心研究之一,而在现代工程与科学计算领域所遇到的许多问题都可以通过数学建模,最后抽象为一个大型的线性常微分方程组.为了求解这一类问题,已有许多学者做了大量的研究工作,构造出许多具有良好性能的数值方法.早在20世纪80年代初,E.Lelarasmee等人在对超大规模集成电路进行数值模拟时,提出了波形松弛方法,用该方法处理模拟电路中相应的微分代数方程系统,取得了良好的数值效果.波形松弛方法借鉴了求解线性代数系统的传统迭代算法,利用矩阵分裂的相关知识,将原大型微分代数系统分解为多个规模较小的子系统,从而实现并行计算,并节省大量的计算时间.随后,鉴于波形松弛方法本身的优越性,越来越多的学者将此方法用于解决电路以外的数学方程的求解问题,并获得了一些较好的结果.
本文首先简要回顾了波形松弛方法的产生背景,该算法的基本思想及其早期的研究成果.第二章详尽介绍波形松弛方法的基础知识,基于前人的研究工作阐述波形松弛方法的主要理论结果.
考虑到连续波形松弛方法要在计算机上实现,第三章在交替方向隐式波形松弛方法的基础上,用线性多步法去离散,再引入误差向量从而导出相应的迭代格式,并分别研究其离散解在有限时间区间和无限时间区间上的收敛性.
第四章尝试用块逐次超松弛迭代法去加速交替方向隐式波形松弛,并利用块矩阵的相关理论知识,详尽讨论了经线性多步法离散之后的解的收敛性,通过引入一个自由参数,可以在一定程度上加速原方法的收敛性.
随后,第五章针对本文所得的主要结论,给出了具体的数值试验,验证结论的正确性和方法的有效性.最后,第六章总结全文,并展望该领域的研究前景.
To solve large-scale ordinary differential equations is one of the most important researches of computational mathematics.And what we are encountered in the field of modern engineering and science computation would be modeled as a large-scale linear ordinary differential equations. There are a great number of scholars who have done every effort and designed lots of numerical methods of good performance so as to solve large-scale ordinary differential equations.As early as in the the beginning of 1980s, E.Lelarasmee with other people proposed waveform relaxation method to solve differential-algebra equations which were from large-scale integrad circuit,and obtained very good effect.Alike traditional iterative methods to solve linear algebra equations, waveform relaxation method decomposes the large-scale differential-algebra into many subsystems by splitting the coefficient matrices.So it is easy to realize parallel computation and saves much time to compute .Waveform relaxation method has so many good performances that more and more scholars have successfully applied the algorithm to other area besides the problems of electric circuit.
In this paper,we first briefly review the background of waveform relaxation method,basic thought and introduce the history and development of research about this approach.In section two,we introduce basic knowledge of waveform relaxation method,and discuss some major theorical results basing on the previous studies.
With regards of the realization of the continuous waveform relaxation method on the computer,in the third chapter we use linear multi-step method to discrete the alternating direction implicit waveform relaxation method.By introducing the error vector ,we can get the iterative form of error vector and study its convergence property in detail.
The forth section will try to use block SOR to accelerate alternating direction implicit waveform relaxation method.We apply linear multi-step method to discrete it and discuss its convergence character according to the knowledge of block matrices.The results show that this algorithm can improve the speed of convergence by introducing the parameter in some ways .
Then in the fifth section ,numerical experiments prove the correctness and effectiveness of our main work.Finally,in the sixth chapter we summarizes the full text and forcasts the development prospect of the waveform relaxation method.
本文首先简要回顾了波形松弛方法的产生背景,该算法的基本思想及其早期的研究成果.第二章详尽介绍波形松弛方法的基础知识,基于前人的研究工作阐述波形松弛方法的主要理论结果.
考虑到连续波形松弛方法要在计算机上实现,第三章在交替方向隐式波形松弛方法的基础上,用线性多步法去离散,再引入误差向量从而导出相应的迭代格式,并分别研究其离散解在有限时间区间和无限时间区间上的收敛性.
第四章尝试用块逐次超松弛迭代法去加速交替方向隐式波形松弛,并利用块矩阵的相关理论知识,详尽讨论了经线性多步法离散之后的解的收敛性,通过引入一个自由参数,可以在一定程度上加速原方法的收敛性.
随后,第五章针对本文所得的主要结论,给出了具体的数值试验,验证结论的正确性和方法的有效性.最后,第六章总结全文,并展望该领域的研究前景.
To solve large-scale ordinary differential equations is one of the most important researches of computational mathematics.And what we are encountered in the field of modern engineering and science computation would be modeled as a large-scale linear ordinary differential equations. There are a great number of scholars who have done every effort and designed lots of numerical methods of good performance so as to solve large-scale ordinary differential equations.As early as in the the beginning of 1980s, E.Lelarasmee with other people proposed waveform relaxation method to solve differential-algebra equations which were from large-scale integrad circuit,and obtained very good effect.Alike traditional iterative methods to solve linear algebra equations, waveform relaxation method decomposes the large-scale differential-algebra into many subsystems by splitting the coefficient matrices.So it is easy to realize parallel computation and saves much time to compute .Waveform relaxation method has so many good performances that more and more scholars have successfully applied the algorithm to other area besides the problems of electric circuit.
In this paper,we first briefly review the background of waveform relaxation method,basic thought and introduce the history and development of research about this approach.In section two,we introduce basic knowledge of waveform relaxation method,and discuss some major theorical results basing on the previous studies.
With regards of the realization of the continuous waveform relaxation method on the computer,in the third chapter we use linear multi-step method to discrete the alternating direction implicit waveform relaxation method.By introducing the error vector ,we can get the iterative form of error vector and study its convergence property in detail.
The forth section will try to use block SOR to accelerate alternating direction implicit waveform relaxation method.We apply linear multi-step method to discrete it and discuss its convergence character according to the knowledge of block matrices.The results show that this algorithm can improve the speed of convergence by introducing the parameter in some ways .
Then in the fifth section ,numerical experiments prove the correctness and effectiveness of our main work.Finally,in the sixth chapter we summarizes the full text and forcasts the development prospect of the waveform relaxation method.
引文
[1] Lelarasmee E, Ruehli A E, Sangiovanni A L. 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:131~145.
[2] Miekkala U, Nevanlinna O. Convergence of dynamic iteration methods for initial value problems. SIAM J. Sci. Stat. Comput.,1987, 8: 459~482.
[3] Miekkala U, Nevanlinna O. Set of convergence and stability regions. BIT,1987, 27: 554~584.
[4] Lubich C, Ostermann A. Multi-grid dynamic iteration for parabolic equations. BIT,1987, 27: 216~234.
[5] Nevanlinna O. Remarks on picard-lindel?f iteration. BIT,1989, 29: 328~346.
[6] Nevanlinna O. Remarks on picard-lindel?f iteration. BIT, 1989, 29: 535~562.
[7] Miekkala U. Dynamic iteration methods applied to linear DAE systems. J. Comput. Appl.Mathe., 1989, 25: 133~151.
[8] Pohl B. On the convergence of the discretized multisplitting waveform relaxation algorithm. Applied Numerical Mathematics, 1993, 11: 251~258.
[9] Schneider K R. A note on the waveform relaxation method. Anal. Model. Simul., 1991, 8: 599~605.
[10] Pan J Y,Bai Z Z,Ng M K.Two-step waveform relaxation methods for implicit linear initial value problems.Numer.Linear Algebra Appl.,2005,12:293~304.
[11] Bai Z Z, Ng M K, Pan J Y. Alternating splitting waveform relaxation method and its successive overrelaxation acceleration. Computers and Mathematics with Applic- ations, 2005, 49: 157~170.
[12] Jeltsch R, Pohl B. Waveform relaxation with overlapping splittings. SIAM J. Sci. Comput., 1995, 16(1): 40~49.
[13] Yuan D J, Burrage K. Convergence of the parallel chaotic waveform relaxation method for stiff systems. Journal of Computational and Applied Mathematics,2003, 151: 201~213.
[14] Reichelt M W, White J K, Allen J. Optimal convolution SOR acceleration of waveform relaxation with application to parallel simulation of semiconductor devices. SIAM J. Sci.Comput., 1995, 16(5): 1137~1158.
[15] Yuan D J. On the accelerative convergence of discretized waveform method for solving ordinary differential systems. Mathematical Application,2002, 15(1): 133~137.
[16] Garrappa R. An analysis of convergence for two-stage waveform relaxation methods. Journal of Computational and Applied Mathematics, 2004, 169: 377~392.
[17] Wang J, Bai Z Z. Convergence analysis of two-stage waveform relaxation method for the initial value problems. Applied Mathematics and Computation,2006, 172: 797~808.
[18] Jackiewicz Z, Kwapisz M. Convergence of waveform relaxation methods for differential-algebraic systems. SIAM J. Numer. Anal., 1996, 33(6): 2303~2317.
[19] Jiang Y L, Wing O. A note on convergence conditions of waveform relaxation algorithms for nonlinear differential-algebraic equations. Applied Numerical Mathematics,2001, 36: 281~297.
[20] Bjqrhus M. A note on the convergence of discretized dynamic iteration. BIT,1995, 35: 291~296.
[21] Gu T X, Li W Q. Discretized multisplitting AOR waveform relaxation algorithms for initial value problem of systems of ODEs. Chinese Quarterly Journal of Mathematics, 1997, 12(4): 27~35.
[22] Jin X Q, Vaikuong S, Song L L. Circulant preconditioned WR-BVM methods for ODE systems. Journal of Computational and Applied Mathematics, 2004, 162: 431~444.
[23] Crow M L, Ilic D C. The waveform relaxation method for systems of differential- algebraic equations. Mathematical and Computer Modeling, 1994, 19: 67~84.
[24] Jiang Y L, Luk W S, Wing O. Convergence theoretics of classical and krylov waveform relaxation methods for differential-algebraic equations. IEICE Transac- tions on Fundamentals of Electronics, Communications and Computer Sciences, 1997, E80-A(10): 1961 ~1972.
[25] Aleksandar I, Zecevic L, Gacic N. 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.
[26] Jiang Y L, Wing O. Monotone waveform relaxation for systems of nonlinear differential-algebraic equations. SIAM Journal on Numerical Analysis, 2000, 38(1):170~185.
[27] Bahi J M, Rhofir K, Miellou J C. Parallel solution of linear DAEs by multisplitting waveform relaxation methods. Linear Algebra and Its Applications, 2001, 332-334: 181~196.
[28] Jiang Y L, Chen R M, Wing O. Waveform relaxation of nonlinear second-order differential equations. IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications,2001, 48(11): 1344~1347.
[29]马菊侠,吴云天,白云霄.非线性高阶微分方程初值问题的波形松弛方法.哈尔滨工业大学学报,2004, 36(8): 1077~1079.
[30] Crisci M R, Ferraro N, Russo E. Convergence results for continuous-time waveform methods for volterra integral equations. Journal of Computational and Applied Mathematics, 1996, 71(1 ): 33~45.
[31] Crisci M R, Russo E, Vecchio A. Time point relaxation methods for Volterra integral-differential equations. Computers Math. Applic.,1998, 36(9): 59~70.
[32] Bjqrhus M. On dynamic iteration for delay differential equations. BIT, 1994, 34: 325~336.
[33] Bartoszewski Z, Kwapisz M. On error estimates for waveform relaxation methods for delay-diferential equations. SIAM J. Numer. Anal.,2000, 38(2): 639~659.
[34] Bartoszewski Z, Kwapisz M. Remarks on evaluation of spectral radius of operators arising in WR methods for linear systems of ODEs. Applied Numerical Mathe- matics,2006, 56: 332~344.
[35] Jankowski T, Kwapisz M, Gdansk L. Convergence of numerical methods for systems of neutral functional-differential-algebraic equations. Applications of Mathematics, 1995, 40(6): 457~472.
[36] Jackiewicz Z, Kwapisz M, Elo K. Waveform relaxation methods for functional differential systems of neutral type. Journal of Mathematical Analysis and Applic- ations, 1997, 207: 255~285.
[37] Bartoszewski Z, Kwapisz M. On the convergence of waveform relaxation methods for differential-functional systems of equations. Journal of Mathematical Analysis and Applications,1999, 235: 478~496.
[38] Zubikkowal B, Vandewalle S. Waveform relaxation for functional-differential equations. SIAM J. Sci.Comput., 1999, 21(1): 207~226.
[39] Zubikkowal B. Error bounds for spatial discretization and waveform relaxation applied to parabolic functional differential equations. J. Math. Anal. Appl., 2004, 293: 496~510.
[40] Bartoszewski Z, Jankowski T, Kwapisz M. On the convergence of iterative methods for general differential-algebraic systems. Journal of Computational and Applied Mathematics,2004, 169: 393~418.
[41] Bartoszewski Z, Kwapisz M. Delay dependent estimates for waveform relaxation methods for neutral differential-functional systems. Computers and Mathematics with Applications,2004, 48: 1877~1892.
[42]王宇莹,赵炜,王峰.一类泛函微分代数系统的波形松弛方法.工程数学学报, 2006, 23(1): 71~78.
[43] Janssen J, Vandewalle S. Multigrid waveform relaxation on spatial finite element meshes: the continuous-time case. SIAM J. Numer. Anal.,1996, 33(2): 456~474.
[44] Janssen J, Vandewalle S. Multigrid waveform relaxation on spatial finite element meshes: the discrete-time case. SIAM J. Sci. Comput.,1996, 17(1): 133~155.
[45]潘建瑜.波形松弛算法及其理论与应用:[博士学位论文].北京:中科院数学与系统科学研究院,2002.
[46] O’Leary D, White R E.Multi-splittings of matrices and parallel solution of linear systems.SIAM J.Alg.Disc.Meth.,1985,6:630~644.
[47] Varga R S. Matrix iterative analysis, second edition. Springer, Berlin, 2000.
[48]李耀堂,仲从磊.关于块H-矩阵的判定条件.昆明师范高等专科学校学报,2002,4:12~15.
[49]黄廷祝,黎稳.块H-矩阵与块矩阵的谱.应用数学和力学,2002,2:217~220.
[50]白中治.并行矩阵多分裂块松弛迭代算法.计算数学, 1995,3:238~252.
[2] Miekkala U, Nevanlinna O. Convergence of dynamic iteration methods for initial value problems. SIAM J. Sci. Stat. Comput.,1987, 8: 459~482.
[3] Miekkala U, Nevanlinna O. Set of convergence and stability regions. BIT,1987, 27: 554~584.
[4] Lubich C, Ostermann A. Multi-grid dynamic iteration for parabolic equations. BIT,1987, 27: 216~234.
[5] Nevanlinna O. Remarks on picard-lindel?f iteration. BIT,1989, 29: 328~346.
[6] Nevanlinna O. Remarks on picard-lindel?f iteration. BIT, 1989, 29: 535~562.
[7] Miekkala U. Dynamic iteration methods applied to linear DAE systems. J. Comput. Appl.Mathe., 1989, 25: 133~151.
[8] Pohl B. On the convergence of the discretized multisplitting waveform relaxation algorithm. Applied Numerical Mathematics, 1993, 11: 251~258.
[9] Schneider K R. A note on the waveform relaxation method. Anal. Model. Simul., 1991, 8: 599~605.
[10] Pan J Y,Bai Z Z,Ng M K.Two-step waveform relaxation methods for implicit linear initial value problems.Numer.Linear Algebra Appl.,2005,12:293~304.
[11] Bai Z Z, Ng M K, Pan J Y. Alternating splitting waveform relaxation method and its successive overrelaxation acceleration. Computers and Mathematics with Applic- ations, 2005, 49: 157~170.
[12] Jeltsch R, Pohl B. Waveform relaxation with overlapping splittings. SIAM J. Sci. Comput., 1995, 16(1): 40~49.
[13] Yuan D J, Burrage K. Convergence of the parallel chaotic waveform relaxation method for stiff systems. Journal of Computational and Applied Mathematics,2003, 151: 201~213.
[14] Reichelt M W, White J K, Allen J. Optimal convolution SOR acceleration of waveform relaxation with application to parallel simulation of semiconductor devices. SIAM J. Sci.Comput., 1995, 16(5): 1137~1158.
[15] Yuan D J. On the accelerative convergence of discretized waveform method for solving ordinary differential systems. Mathematical Application,2002, 15(1): 133~137.
[16] Garrappa R. An analysis of convergence for two-stage waveform relaxation methods. Journal of Computational and Applied Mathematics, 2004, 169: 377~392.
[17] Wang J, Bai Z Z. Convergence analysis of two-stage waveform relaxation method for the initial value problems. Applied Mathematics and Computation,2006, 172: 797~808.
[18] Jackiewicz Z, Kwapisz M. Convergence of waveform relaxation methods for differential-algebraic systems. SIAM J. Numer. Anal., 1996, 33(6): 2303~2317.
[19] Jiang Y L, Wing O. A note on convergence conditions of waveform relaxation algorithms for nonlinear differential-algebraic equations. Applied Numerical Mathematics,2001, 36: 281~297.
[20] Bjqrhus M. A note on the convergence of discretized dynamic iteration. BIT,1995, 35: 291~296.
[21] Gu T X, Li W Q. Discretized multisplitting AOR waveform relaxation algorithms for initial value problem of systems of ODEs. Chinese Quarterly Journal of Mathematics, 1997, 12(4): 27~35.
[22] Jin X Q, Vaikuong S, Song L L. Circulant preconditioned WR-BVM methods for ODE systems. Journal of Computational and Applied Mathematics, 2004, 162: 431~444.
[23] Crow M L, Ilic D C. The waveform relaxation method for systems of differential- algebraic equations. Mathematical and Computer Modeling, 1994, 19: 67~84.
[24] Jiang Y L, Luk W S, Wing O. Convergence theoretics of classical and krylov waveform relaxation methods for differential-algebraic equations. IEICE Transac- tions on Fundamentals of Electronics, Communications and Computer Sciences, 1997, E80-A(10): 1961 ~1972.
[25] Aleksandar I, Zecevic L, Gacic N. 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.
[26] Jiang Y L, Wing O. Monotone waveform relaxation for systems of nonlinear differential-algebraic equations. SIAM Journal on Numerical Analysis, 2000, 38(1):170~185.
[27] Bahi J M, Rhofir K, Miellou J C. Parallel solution of linear DAEs by multisplitting waveform relaxation methods. Linear Algebra and Its Applications, 2001, 332-334: 181~196.
[28] Jiang Y L, Chen R M, Wing O. Waveform relaxation of nonlinear second-order differential equations. IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications,2001, 48(11): 1344~1347.
[29]马菊侠,吴云天,白云霄.非线性高阶微分方程初值问题的波形松弛方法.哈尔滨工业大学学报,2004, 36(8): 1077~1079.
[30] Crisci M R, Ferraro N, Russo E. Convergence results for continuous-time waveform methods for volterra integral equations. Journal of Computational and Applied Mathematics, 1996, 71(1 ): 33~45.
[31] Crisci M R, Russo E, Vecchio A. Time point relaxation methods for Volterra integral-differential equations. Computers Math. Applic.,1998, 36(9): 59~70.
[32] Bjqrhus M. On dynamic iteration for delay differential equations. BIT, 1994, 34: 325~336.
[33] Bartoszewski Z, Kwapisz M. On error estimates for waveform relaxation methods for delay-diferential equations. SIAM J. Numer. Anal.,2000, 38(2): 639~659.
[34] Bartoszewski Z, Kwapisz M. Remarks on evaluation of spectral radius of operators arising in WR methods for linear systems of ODEs. Applied Numerical Mathe- matics,2006, 56: 332~344.
[35] Jankowski T, Kwapisz M, Gdansk L. Convergence of numerical methods for systems of neutral functional-differential-algebraic equations. Applications of Mathematics, 1995, 40(6): 457~472.
[36] Jackiewicz Z, Kwapisz M, Elo K. Waveform relaxation methods for functional differential systems of neutral type. Journal of Mathematical Analysis and Applic- ations, 1997, 207: 255~285.
[37] Bartoszewski Z, Kwapisz M. On the convergence of waveform relaxation methods for differential-functional systems of equations. Journal of Mathematical Analysis and Applications,1999, 235: 478~496.
[38] Zubikkowal B, Vandewalle S. Waveform relaxation for functional-differential equations. SIAM J. Sci.Comput., 1999, 21(1): 207~226.
[39] Zubikkowal B. Error bounds for spatial discretization and waveform relaxation applied to parabolic functional differential equations. J. Math. Anal. Appl., 2004, 293: 496~510.
[40] Bartoszewski Z, Jankowski T, Kwapisz M. On the convergence of iterative methods for general differential-algebraic systems. Journal of Computational and Applied Mathematics,2004, 169: 393~418.
[41] Bartoszewski Z, Kwapisz M. Delay dependent estimates for waveform relaxation methods for neutral differential-functional systems. Computers and Mathematics with Applications,2004, 48: 1877~1892.
[42]王宇莹,赵炜,王峰.一类泛函微分代数系统的波形松弛方法.工程数学学报, 2006, 23(1): 71~78.
[43] Janssen J, Vandewalle S. Multigrid waveform relaxation on spatial finite element meshes: the continuous-time case. SIAM J. Numer. Anal.,1996, 33(2): 456~474.
[44] Janssen J, Vandewalle S. Multigrid waveform relaxation on spatial finite element meshes: the discrete-time case. SIAM J. Sci. Comput.,1996, 17(1): 133~155.
[45]潘建瑜.波形松弛算法及其理论与应用:[博士学位论文].北京:中科院数学与系统科学研究院,2002.
[46] O’Leary D, White R E.Multi-splittings of matrices and parallel solution of linear systems.SIAM J.Alg.Disc.Meth.,1985,6:630~644.
[47] Varga R S. Matrix iterative analysis, second edition. Springer, Berlin, 2000.
[48]李耀堂,仲从磊.关于块H-矩阵的判定条件.昆明师范高等专科学校学报,2002,4:12~15.
[49]黄廷祝,黎稳.块H-矩阵与块矩阵的谱.应用数学和力学,2002,2:217~220.
[50]白中治.并行矩阵多分裂块松弛迭代算法.计算数学, 1995,3:238~252.