摘要
区域分解法是建立在给定的计算区域被划分为几个重叠或非重叠的子区域的假设上的一种算法。Schwarz交替法无疑是最早的区域分解法之一。随着并行计算机的出现，区域分解法以其缩小计算规模和高度并行的优点成为设计并行算法最重要的一种方式。本文讨论椭圆型变分问题，包括椭圆算子对应的变分不等式与互补问题，以及偏微分方程的区域分解法。
互补问题是一类典型的变分不等式，它广泛用于阐述和研究物理学、力学、经济学、运筹学、最优控制等数学模型以及交通运输中出现的各种平衡模型，其数值解法的研究发展迅速。目前求解互补问题的迭代算法有很多，区域分解法是其中的研究热点之一。对于对称线性互补问题，
Ax+6≥0，x≥0，x~T(Ax+b)=0，其中，A是给定的N×N实对称矩阵，b是N×1向量，在已有的研究成果中，大多数要求其中的系数矩阵A对称正定或者为M阵等。本文中讨论了当其中的系数矩阵为对称双正阵时，区域分解法(包括乘性Schwarz算法、非重叠加性Schwarz算法和重叠加性Schwarz算法)的收敛性质。证明了由这些算法产生的迭代序列的聚点是原互补问题的解。数值算例表明，算法的收敛速度快，体现其优越性。
用区域分解法求解偏微分方程于上世纪八十年代蓬勃兴起，并越来越受到人们的重视。它分为重叠型和非重叠型。以Robin条件为界面条件的重叠型区域分解法也被称为广义Schwarz算法，其区别于古典的Schwarz算法的特点是在子区域之间的界面上采用Dirichlet条件和Neumann条件相结合的Robin条件来代替原来的单纯的Dirichlet条件。本文中分析了一种广义加性Schwarz算法求解Dirichlet边值的偏微分方程问题的收敛率。给出了一维和二维问题的算法收敛率的定量分析，并以相应的数值算例说明参数及重叠区域的大小与算法收敛率之间的关系。数值算例表明，适当的Robin参数和减小重叠区域的大小会提高算法的收敛率。这种算法也可以被用于非重叠型的区域分解。非重叠型区域分解方面的研究目前相关结论不是很多。在大多数文献中，讨论的主要是矩形或带状区域。本文中讨论了非规则的区域-L型区域上的Poisson方程的一种加性非重叠区域分解法。而且，在该区域分解法中也采用了Robin型界面传输条件。证明了该算法在连续情形下的收敛性，并讨论了离散后算法的收敛速度与Robin型界面传输条件中的Robin参数之间的关系。数值算例说明，适当的Robin参数的选取会大大加快该算法的收敛速度。
Domain decomposition is one of the most significant way for devising parallel algorithms that can benefit strongly from multiprocessor computers. Domain decomposition methods are generally based on the assumption that the given computational domain is partitioned into subdomains, which may or may not overlap. The alternative Schwarz method is undoubtedly the earliest example of domain decomposition methods. In this dissertation, we consider domain decomposition to solve elliptic variational problems, including variational inequalities, complementarity problem and partial differential equations.
Complementarity problems are used to interpret and study the mathematical models of physics, mechanics, economics and optimal control, and various of equilibrium models that arise from traffic conveyance. The methods for the numerical solution of the complementarity problems are developed rapidly. At the present time, there are many iterative methods for solving complementarity problems. Domain decomposition method is a kind of pop iterative method studied by many researchers. For symmetric linear complementarity problems, most results are based on the assumption that the coefficient matrices are symmetric and positive definite or M matrices. In this dissertation, domain decomposition methods for the case of the coefficient matrices are symmetric and copositive are proposed. Convergence of the methods is established. And numerical results are present to show the efficiency of the methods.
Domain decomposition methods for partial differential equations were developed in 1980s. From then on, the methods are recognized by more and more researchers. The Schwarz algorithms, which use Robin transmission conditions on the inner boundaries of the subdomains, is also called generalized Schwarz algorithms. Compared with the classical Schwarz algorithm, the generalized Schwarz algorithms replace transmission conditions on the interface between subdomains by the Robin conditions with parameters. In this dissertation, the convergence rate of a generalized additive Schwarz algorithm for solving boundary value problems of differential equations is studied. A quantitative analysis of the convergence rate is given for the one and two dimensional model Dirichlet problems. It shows that small overlapping is preferred for the generalized additive Schwarz algorithm. Some numerical tests also show that a greater acceleration of the algorithm can be obtained by choosing the parameter suitably. The alternative Schwarz method
引文
[1] Schwarz H A. Uber einen Grenzubergang durch alternierendes Verfahren. Vierteli-jahrsschrift der Naturforschenden Gesellschaft in Zurich, 1870, 15:272-286
[2] 吕涛，石济民，林振宝．区域分解算法．北京：科学出版社，1992，19-115
[3] Lions P L. On the Schwarz alternating method Ⅰ. In:Proceedings of Domain Decomposition Method. SIAM, Philadelphia, 1988, 1-40
[4] Miller K., Numerical analogs to the Schwarz alternating procedure. Numerische Mathematik, 1965, 7:91-103
[5] 康立山，孙乐林，陈毓平．解数学物理问题的异步并行算法．北京：科学出版社，1985，21-42
[6] Lions P L. On the Schwarz alternating method Ⅱ:Stochastic interpretation and order properties. In:2nd International Symposium on Domain Decomposition Methods for Partial Differential Equations. SIAM. Philadelphia, PA, 1989, 47-71
[7] Engquist B, Majda A. Absorbing boundary conditions for the numerical simulation of waves. Mathematical computing, 1997, 31(139):629-651
[8] Engquist B, Zhao H K. Absorbing boundary condition for domain decomposition. Applied Numerical Mathematics, 1998, 27:341-356
[9] Japhet C, Nataf F. The best interface conditions for domain decomposition methods:Absorbing boundary conditions. In:Artificial Boundary Conditions with Applications to Computational Fluid Dynamics Problems. Nova Science Publishers, NY, 2000, 348-373
[10] Gander M J, Halpern L, Nataf F. Optimized Schwarz methods. In:Proceedings of the 12th International Conference on Domain Decomposition Methods, Chiba, Japan, 2001, 15-27
[11] Nataf F, Rogier F. Factorization of the convection-diffusion operator and the Schwarz algorithm. Models Methods Applied Scientific, 1995, 5(1):67-93
[12] Natal F. Absorbing boundary conditions in block Gauss-Seidel methods for the convection problems. Math, Models Methods Application Scientific, 1996, 6(4):481-502
[13] Gander M J, Magoules F, Nataf F. Optimal Schwarz methods without overlap for the Helmholtz equation. SIAM Journal on Scientific Computing, 2002, 24(1):38-60
[14] Bjφrstad P E, Widlund O B. Iterative methods for the solution of elliptic problems on regions partitioned into substructures. SIAM Journal on Numerical Analysis, 1986, 23:1097-1120
[15] Bramble J H, Pasciak J E, Schatz A H. An iterative method for elliptic problems on regions partitioned into substructures. Mathematics and Computation, 1986, 46: 361-369
[16] Funaro D, Quarteroni A, Zanolli P. An iterative procedure with interface relaxation for domain decomposition methods. SIAM Journal on Numerical Analysis, 1988, 25: 1213-1236
[17] Marini L D, Quarteroni A. An iterative procedure for domain decomposition methods: a finite element approach. In: First International Symposium on Domain Decomposition Methods for Partial Differential Equations. SIAM, Philadelphia, 1988, 129-143
[18] Marini L D, Quarteroni A. A relaxation procedure for domain decomposition methods using finite elements. Numerical Mathematics, 1989, 55: 575-598
[19] Bourgat J F, Glowinski R, Le Tallec P, et al. Variational formulation and algorithm for trace operator in domain decomposition calculations. In: Domain Decomposition Methods. SIAM, Philadelphia, 1989, 3-16
[20] Agoshkov V I, Lebedev V I. Poincare-Steklov operators and the methods of partition of the domain in variational problems. In: Computational processes and systems. Nauka, Moscow, 1985, 173-227 [Russian]
[21] Lions P L. On the Schwarz alternating method III. In: Third International Symposium on Domain Decomposition Methods. SIAM, Philadelphia, 1990, 202-223
[22] Agoshkov V I. Poincare-Steklov's operators and domain decomposition methods in finite dimensionsal spaces. In: First International Symposium on Domain Decomposition Methods for Partial Differential Equations. SIAM, Philadelphia, 1988, 73-112
[23] Lui S H. On accelerated convergence of nonoverlapping Schwarz methods. Journal of Computational Application and Mathematics, 2000, 130: 309-321
[24] Chevalier P, Nataf F. An oo2 (optimized order 2) method for the Helmholtz and Maxwell equations. In: 10th International Conference on Domain Decomposition Methods in Science and in Engineering. AMS, Providence, 1998, 400-407
[25] Dryja M, Smith B F, Widlund O B. Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions. SIAM Journal on Numerical Analysis, 1994, 31: 1662-1694
[26] Japhet C. Optimized Krylov-ventcell method application to convection diffusion problems. In: 9th International Conference on Domain Decomposition Methods in Science and in Engineering. SIAM, Philadelphia, PA, 1998, 382-389
[27] Nataf F. Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains. Numerische Mathematik, 1997, 75: 357-377
[28] Sun H, Tang W P. An overdetermined Schwarz alternating method. SIAM Journal on Scientific Computing, 1996, 17:884-905
[29] White R E. Domain decomposition splittings. Linear Algebra and its Applications, 2000, 316:105-112
[30] Gander M J. Overlapping Schwarz Waveform Relaxation for Parabolic Problems. Contemporary Mathematics, 1998, 218:425-431
[31] Hadjidimos A, Noutsos D, Tzoumas M. Nonoverlapping domain decomposition:A linear algebra viewpoint. Mathematics and Computer in Simulation, 2000, 51:597-625
[32] Yang D. A parallel iterative nonoverlapping domain decomposition procedure for elliptic problems. IMA Journal of Numerical Analysis, 1996, 16:75-91
[33] Tan K H, Borsboom M J A. On generalized Schwarz coupling applied to advection-dominated problems. Contemporary Mathematics, 1994, 180:125-130
[34] 李宏伟．Robin传递条件中的最优参数．见：第六届全国并行计算学术会议论文集．国防科技大学出版社，2000，73-76
[35] 李宏伟．椭圆型偏微分方程的加法Schwarz方法．数值计算和计算机应用，2003．24：44-52
[36] Chan T, Glowinski R, Periaux J, et al. Domain Decomposition Methods. SIAM. Philadelphia, PA, 1989, 65-118
[37] Chart T, Glowinski R, Periaux J, et al. Proceedings of Third International Symposium on Domain Decomposition Methods for Partial Differential Equations. SIAM, Philadelphia, PA, 1990, 12-98
[38] Glowinski R, Golub G H, Meurant G A, et al. Domain Decomposition Methods for Partial Differential Equations. SIAM, Philadelphia, PA, 1988, 228-654
[39] Glowinski R, Kuznetsov Y A, Meurant G A, et al. Proceedings of Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations. SIAM, Philadelphia, PA, 1991, 24-91
[40] Bank R E, Jimack P K, Nadeem S A, et al. A weakly overlapping domain decomposition preconditioner for the finite element solution of elliptic partial differential equations. SIAM Journal on Scientific Computation, 2002, 23(6):1817-1841
[41] Despres B. Domain decomposition method and the helmholtz problem, In:Mathematical and Numerical Aspects of Wave Propagation Phenomena. SIAM, Philadelphia, 1991, 72-131
[42] Despres B. Domain decomposition method and the helmholtz problem. In:Mathematical and Numerical Aspects of Wave Propagation Phenomena. SIAM, Philadelphia, 1993, 15-34
[43] Engquist B, Zhao H H. Analysis of generalized Schwarz alternating procedure for domain decomposition. Technical Report, UCLA CAM Report, 1996, 20-53
[44] Gastaldi F, Gastaldi L, Quarteroni A. Adaptative domain decomposition methods for advection dominated equations. East-West Journal of Numerical Mathematics, 1996, 3: 165-206
[45] Ghanemi S, Joly P, Collino F. Domain decomposition method for harmonic wave equations. In: Mathematical and Numerical Aspects of Wave Propagation. SIAM, Philadelphia, 1995, 123-189
[46] Sarkis M. Two-level Schwarz methods for nonconforming finite elements and discontinuous coefficients. In: Proceedings of the sixth Copper Mountain Conference on Multigrid Methods. NASA, Hampton VA, 1993(2), 210-287
[47] Xu J, Zou J. Nonoverlapping domain decomposition method. SIAM Review, 1998,1140-1186
[48] Xu J. Iterative methods by space decomposition and subspace correction. SIAM Review, 1992, 34: 581-613
[49] Dryja M, Widlund O. An additive variant of the Schwarz alternating method for the case of many subregions, Technical report 339, also Ultracomputer note 131, Department of Computer Science, Courant Institute, New York, 1987, 25-69
[50] Magoules F, Roux F, Salmon S. Optimal discrete transmission conditions for a nonoverlapping domain decomposition method for the Helmholtz equation. SIAM Journal on Scientific Computation, 2004, 25(5): 1497-1515
[51] Tang W P. Generalized Schwarz splittings. SIAM Journal on Scientific Statistic Computation, 1992, 13: 573-595
[52] Douglas J, Huang C -S. An accelerated domain decomposition iterative procedures based on Robin transmission conditions. BIT, 1997, 37: 678-686
[53] Douglas J, Huang C -S. Accelerated domain decomposition iterative procedures for mixed methods based on Robin transmission conditions. CALCOLO, 1998, 35: 131-147
[54] Alonso A, Trotta R L, Valli A. Coercive domain decomposition algorithms for advection-diffusion equations and systems. Journal of Computational Application and Mathematics, 1998, 96: 51-76
[55] Lions J L, Stampacchia G. Variational inequalities, Communications on Pure and Applied Mathematics, 1967, 20: 493-519
[56] Mancino O, Stampacchia G. Convex programming and variational inequalities, Journal of Optimization Theory and Application, 1972, 9: 3-23
[57] Stampacchia G. Theory and Applications of Monotone Operators. In: Proceedings of the NATO Advanced Study Institute. Venice, Italy, 1968, 24-73
[58] Kinderlehrer D., Stampacchia G. An Introduction to Variational Inequalities and Their Application, New York:Academic Press, 1980, 30-49
[59] Baiochi C, Capelo A. Variational and Quasivariational Inequalities:Application to Free Boundary Problems, New York:Wiley, 1984, 54-71
[60] Badea L, Tai X, Wang J. Convergence rate analysis of a multiplicative Schwarz method for variational inequalities. SIAM Journal on Numerical Analysis, 2003, 41:1052-1073
[61] Badea L, Wang J. An additive Schwarz method for variational inequalities. Mathematics and Computation, 2000, 69:1341-1354
[62] Kuznetsov Y, Neittaamaki P, Tarvainen P. Schwarz methods for obstacle problems with convection diffusion operators. In:Domain Decomposition Methods in Scientific and Engineering Computing. AMS. Providence, RI, 1995, 251-256
[63] Kuznetsov Y, Neittaamaki P, Tarvednen P. Schwarz methods for obstacle problem. East-West Journal of Numerical Mathematics, 2001, 9:233-252
[64] 李郴良，曾金平，周叔子．解含非线性源项的变分不等式问题的非重叠区域分解法．计算数学，2001，23(1)：37-48
[65] Lu T, Liem T C B, Shih M. Parallel algorithms for variational inequalities based on domain decomposition. System Science and Mathematics Science, 1991, 4:341-348
[66] Scarpini F, The alternative Schwarz method applied to some biharmonic variational inequalities. Calcolo, 1990, 27:57-72
[67] Tai X. Convergence rate analysis of domain decomposition method for obstacle problem. East-West Journal of Numerical Mathematics, 2001, 9:233-252
[68] Tai X, Rate of convergence for some constraint decomposition methods for nonlinear variational inequalities. Numerical Mathematics, 2003, 93:755-786
[69] Tai X, Tseng P. Convergence rate analysis of an asynchronous space decomposition method for convex minimization. Mathematics and Computation, 2001, 71:1105-1135
[70] 曾金平，王烈衡．解单障碍问题的非重叠区域分解法．计算数学，1997，19： 421-430
[71] Zeng J, Zhou S. On monotone and geometric convergence of Schwarz methods for two-sided obstacle problems. SIAM Joural on Numerical Analysis, 1998, 35:600-616
[72] Zeng J, Zhou S. Schwarz algorithm for the solution of variational inequalities with nonlinear source terms. Applied Mathematics and Computation, 1998, 97:23-35
[73] Zhou S, Ding L. A parallel Schwarz algorithm for variational inequalities. Chinese Science Bulletin, 1996, 41:1061-1064
[74] Meyer G H. Free boundary problems with nonlinear source terms. Numerical Mathematics, 1984, 43:463-482
[75] Hoffmann K H, Zou J. Parallel solution of variational inequality problems with nonlinear source terms. IMA Journal of Numerical Analysis, 1996, 16:31-45
[76] 周叔子，曾金平，一类非线性算子障碍问题的Schwarz算法．应用数学学报，1997．20：521-530
[77] Zeng J, Zhou S. Schwarz algorithm for the solution of variational inequalities with nonlinear source terms. Applied Mathematics and Computation, 1998, 97:23-35
[78] Li C, Zeng J, Zhou S. Convergence analysis of generalized Schwarz algorithms for solving obstacle problems with T-monotone operator. Computation and Mathematics Application, 2004, 48:373-386
[79] Zhou S, Zeng J, Tang X. Generalized Schwarz algorithm for obstacle problems. Computation and Mathematics Application, 1999, 38:263-271
[80] Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problem. New York, Academic Press, 1992, 107-219
[81] Mangasarian O L. Solution of symmetric linear complementarity problems by iterative methods. Journal of Optimization Theory and Applications, 1977, 22(4):465-485
[82] Mangasarian O L, Leone R De. Parallel successive overrelaxation methods for symmetric linear complementarity problems and linear program. Journal of Optimization Theory and Applications, 1987, 54(3):437-446
[83] Quarteroni A, Valli A. Domain Decomposition Methods for Partial Differential Equations. New York:Oxford University Press, 1999, 98-164
[84] 曾金平，李董辉．对称双正型线性互补问题的多重网格迭代解收敛性理论．计算数学，1994，16(1)：25-30
[85] 曾金平．近似求解子问题的乘性Schwarz算法．湖南大学学报，1996，23(5)： 4-9
[86] Zeng J P, Zhou S Z. A domain decomposition method for a kind of optimization problems. Journal of Computation and Applied Mathematics, 2002, 146:127-139
[87] Glowinski R, Lions J, Tremolieres R. Numerical Analysis of Variational Inequalities. North-Holland, Amsterdam, 1981, 16-198
[88] Kinderlehrer D, Stampachia G. An Introduction to Variational Inequalities and Their Applications. New York, Academic, 1980, 21-56
[89] Fischer CF, Usmani R A. Properties of some tridiagonal matrices and their application to boundary value problems. SIAM Journal on Numerical Analysis, 1969, 6:127-142
[90] Achodou Y, Japhet C, Maday Y, Nataf F. A new cement to glue non-conforming grids with Robin interface conditions:the finite volume case. Numerical Mathematics, 2002, 92:593-620
[91] Matsokin A M, Nepomnyaschikh S V. A Schwarz alternating method in a subspace. Izv. VUZ Mat., 1985, 29(10):61-66
[92] Mikhlin S G. On the Schwarz algorithm. Dokl. Akad. Nauk S. S. S. R., 1951, 77:569-571
[93] Smith B, Bjφrstad P, Gropp W. Domain Decomposition. Cambridge:Cambridge University Press, 1996, 132-204
[94] Sobolov S L. Schwarz algorithm in the theory of elasticity. Dokl. Akad. Nauk S. S. S. R., 1936, 4:235-238