共查询到20条相似文献,搜索用时 31 毫秒
1.
We prove the convergence of some multiplicative and additive Schwarz methods for inequalities which contain contraction operators. The problem is stated in a reflexive Banach space and it generalizes the well-known fixed-point problem in the Hilbert spaces. Error estimation theorems are given for three multiplicative algorithms and two additive algorithms. We show that these algorithms are in fact Schwarz methods if the subspaces are associated with a decomposition of the domain. Also, for the one- and two-level methods in the finite element spaces, we write the convergence rates as functions of the overlapping and mesh parameters. They are similar with the convergence rates of these methods for linear problems. Besides the direct use of the five algorithms for the inequalities with contraction operators, we can use the above results to obtain the convergence rate of the Schwarz method for other types of inequalities or nonlinear equations. In this way, we prove the convergence and estimate the error of the one- and two-level Schwarz methods for some inequalities in Hilbert spaces which are not of the variational type, and also, for the Navier–Stokes problem. Finally, we give conditions of existence and uniqueness of the solution for all problems we consider. We point out that these conditions and the convergence conditions of the proposed algorithms are of the same type. 相似文献
2.
Summary. Multilevel preconditioners are proposed for the iterative solution of the discrete problems which arise when orthogonal spline
collocation with piecewise Hermite bicubics is applied to the Dirichlet boundary value problem for a self-adjoint elliptic
partial differential equation on a rectangle. Additive and multiplicative preconditioners are defined respectively as sums
and products of independent operators on a sequence of nested subspaces of the fine partition approximation space. A general
theory of additive and multiplicative Schwarz methods is used to prove that the preconditioners are spectrally equivalent
to the collocation discretization of the Laplacian with the spectral constants independent of the fine partition stepsize
and the number of levels. The preconditioned conjugate gradient and preconditioned Orthomin methods are considered for the
solution of collocation problems. An implementation of the methods is discussed and the results of numerical experiments are
presented.
Received March 1, 1994 / Revised version received January 23, 1996 相似文献
3.
Xuejun Zhang 《Numerische Mathematik》1992,63(1):521-539
Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.This work was supported in part by the National Science Foundation under Grants NSF-CCR-8903003 at Courant Institute of Mathematical Sciences, New York University and NSF-ASC-8958544 at Department of Computer Science, University of Maryland. 相似文献
4.
In recent years, domain decomposition methods have attracted much attention due to their successful application to many elliptic
and parabolic problems. Domain decomposition methods treat problems based on a domain substructuring, which is attractive
for parallel computation, due to the independence among the subdomains. In principle, domain decomposition methods may be
applied to the system resulting from a standard discretization of the parabolic problems or, directly, be carried out through
a discretization of parabolic problems. In this paper, a direct domain decomposition method is introduced to discretize the
parabolic problems. The stability and convergence of this algorithm are analyzed.
This work was supported in part by Polish Sciences Foundation under grant 2P03A00524.
This work was supported in part by the US Department of Energy under Contracts DE-FG02-92ER25127 and by the Director, Office
of Science, Advanced Scientific Computing Research, U.S. Department of Energy under contract DE-AC02-05CH11231. 相似文献
5.
Xiao-Chuan Cai 《Numerische Mathematik》1991,60(1):41-61
Summary In this paper, we consider the solution of linear systems of algebraic equations that arise from parabolic finite element problems. We introduce three additive Schwarz type domain decomposition methods for general, not necessarily selfadjoint, linear, second order, parabolic partial differential equations and also study the convergence rates of these algorithms. The resulting preconditioned linear system of equations is solved by the generalized minimal residual method. Numerical results are also reported.This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003 at the Courant Institute, New York University and in part by the National Science Foundation under contract number DCR-8521451 and ECS-8957475 at Yale University 相似文献
6.
Rate of Convergence for some constraint decomposition methods for nonlinear variational inequalities 总被引:3,自引:0,他引:3
Xue-Cheng Tai 《Numerische Mathematik》2003,93(4):755-786
Summary. Some general subspace correction algorithms are proposed for a convex optimization problem over a convex constraint subset.
One of the nontrivial applications of the algorithms is the solving of some obstacle problems by multilevel domain decomposition
and multigrid methods. For domain decomposition and multigrid methods, the rate of convergence for the algorithms for obstacle
problems is of the same order as the rate of convergence for jump coefficient linear elliptic problems. In order to analyse
the convergence rate, we need to decompose a finite element function into a sum of functions from the subspaces and also satisfying
some constraints. A special nonlinear interpolation operator is introduced for decomposing the functions.
Received December 13, 2001 / Revised version received February 19, 2002 / Published online June 17, 2002
This work was partially supported by the Norwegian Research Council under projects 128224/431 and SEP-115837/431. 相似文献
7.
Tarek P. Mathew 《Numerische Mathematik》1993,65(1):469-492
Summary In this paper we discuss bounds for the convergence rates of several domain decomposition algorithms to solve symmetric, indefinite linear systems arising from mixed finite element discretizations of elliptic problems. The algorithms include Schwarz methods and iterative refinement methods on locally refined grids. The implementation of Schwarz and iterative refinement algorithms have been discussed in part I. A discussion on the stability of mixed discretizations on locally refined grids is included and quantiative estimates for the convergence rates of some iterative refinement algorithms are also derived.Department of Mathematics, University of Wyoming, Laramie, WY 82071-3036. This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by NSF Grant ASC 9003002, while the author was a Visiting, Assistant Researcher at UCLA. 相似文献
8.
In this paper, we propose two variants of the additive Schwarz method for the approximation of second order elliptic boundary
value problems with discontinuous coefficients, on nonmatching grids using the lowest order Crouzeix-Raviart element for the
discretization in each subdomain. The overall discretization is based on the mortar technique for coupling nonmatching grids.
The convergence behavior of the proposed methods is similar to that of their closely related methods for conforming elements.
The condition number bound for the preconditioned systems is independent of the jumps of the coefficient, and depend linearly
on the ratio between the subdomain size and the mesh size. The performance of the methods is illustrated by some numerical
results.
This work has been supported by the Alexander von Humboldt Foundation and the special funds for major state basic research
projects (973) under 2005CB321701 and the National Science Foundation (NSF) of China (No.10471144)
This work has been supported in part by the Bergen Center for Computational Science, University of Bergen 相似文献
9.
Summary For solving second order elliptic problems discretized on a sequence of nested mixed finite element spaces nearly optimal iterative methods are proposed. The methods are within the general framework of the product (multiplicative) scheme for operators in a Hilbert space, proposed recently by Bramble, Pasciak, Wang, and Xu [5,6,26,27] and make use of certain multilevel decomposition of the corresponding spaces for the flux variable. 相似文献
10.
Summary.
We consider two level overlapping Schwarz domain decomposition methods
for solving the finite element problems that arise from
discretizations of elliptic problems on general unstructured meshes
in two and three dimensions. Standard finite element interpolation
from
the coarse to the fine grid may be used. Our theory requires no
assumption on the substructures
that constitute the whole domain, so the
substructures can be of arbitrary shape and of different
size. The global coarse mesh is allowed to be non-nested
to the fine grid on which the discrete problem is to be solved, and
neither
the coarse mesh nor the fine mesh need be quasi-uniform.
In addition, the domains defined by the fine and coarse grid need
not be identical. The one important constraint is that the closure
of the coarse grid must cover any portion of the fine grid boundary
for which Neumann boundary conditions are given.
In this general setting, our algorithms have the same optimal
convergence rate as the usual two level overlapping domain decomposition
methods on structured meshes.
The condition number of the preconditioned system depends only on the
(possibly small)
overlap of the
substructures and the size of the coarse grid, but is independent of
the sizes of the subdomains.
Received
March 23, 1994 / Revised version received June 2, 1995 相似文献
11.
S.H. Lui 《Journal of Computational and Applied Mathematics》2010,235(1):301-314
Optimized Schwarz methods form a class of domain decomposition methods for the solution of elliptic partial differential equations. Optimized Schwarz methods employ a first or higher order boundary condition along the artificial interface to accelerate convergence. In the literature, the analysis of optimized Schwarz methods relies on Fourier analysis and so the domains are restricted to be regular (rectangular). In this paper, we express the interface operator of an optimized Schwarz method in terms of Poincare-Steklov operators. This enables us to derive an upper bound of the spectral radius of the operator arising in this method of 1−O(h1/4) on a class of general domains, where h is the discretization parameter. This is the predicted rate for a second order optimized Schwarz method in the literature on rectangular subdomains and is also the observed rate in numerical simulations. 相似文献
12.
In the present paper we develop a representation of a norm frequently used in the analysis of multilevel methods. This allows
us to examine the convergence of additive Schwarz schemes also in the case of non-nested subspaces. We demonstrate the usefulness
of the given norm representation by studying in detail the stability of sparse grid splittings due to Griebel and Oswald,
which turns out to be a special case of our unified theory. Further applications concerning approximation spaces and non-nested
finite element spaces are given.
This revised version was published online in August 2006 with corrections to the Cover Date. 相似文献
13.
Multilevel Schwarz methods for elliptic problems
with discontinuous coefficients in three dimensions
Summary.
Multilevel Schwarz methods are developed for a
conforming finite element approximation of second order elliptic problems. We
focus on problems in three dimensions with
possibly large jumps in the coefficients across the
interface separating the subregions. We establish
a condition number estimate for the iterative operator, which is
independent of the coefficients, and grows at most as the square
of the number of levels. We also characterize a class of distributions
of the coefficients,
called quasi-monotone, for which the weighted
-projection is
stable and for which we can use the standard piecewise
linear functions as a coarse space. In this case,
we obtain optimal methods, i.e. bounds which are independent of the number
of levels and subregions. We also design and analyze multilevel
methods with new coarse spaces
given by simple explicit formulas. We consider nonuniform meshes
and conclude by an analysis of multilevel iterative substructuring methods.
Received April 6, 1994 / Revised version received December 7,
1994 相似文献
14.
Xiao-Chuan Cai William D. Gropp David E. Keyes 《Numerical Linear Algebra with Applications》1994,1(5):477-504
In recent years, competitive domain-decomposed preconditioned iterative techniques of Krylov-Schwarz type have been developed for nonsymmetric linear elliptic systems. Such systems arise when convection-diffusion-reaction problems from computational fluid dynamics or heat and mass transfer are linearized for iterative solution. Through domain decomposition, a large problem is divided into many smaller problems whose requirements for coordination can be controlled to allow effective solution on parallel machines. A central question is how to choose these small problems and how to arrange the order of their solution. Different specifications of decomposition and solution order lead to a plethora of algorithms possessing complementary advantages and disadvantages. In this report we compare several methods, including the additive Schwarz algorithm, the classical multiplicative Schwarz algorithm, an accelerated multiplicative Schwarz algorithm, the tile algorithm, the CGK algorithm, the CSPD algorithm, and also the popular global ILU-family of preconditioners, on some nonsymmetric or indefinite elliptic model problems discretized by finite difference methods. The preconditioned problems are solved by the unrestarted GMRES method. A version of the accelerated multiplicative Schwarz method is a consistently good performer. 相似文献
15.
Summary Based on the framework of subspace splitting and the additive Schwarz scheme, we give bounds for the condition number of multilevel preconditioners for sparse grid discretizations of elliptic model problems. For a BXP-like preconditioner we derive an estimate of the optimal orderO(1) and for a HB-like variant we obtain an estimate of the orderO(k
2
·2
k/2
), wherek denotes the number of levels employed. Furthermore, we confirm these results by numerically computed condition numbers. 相似文献
16.
Summary We introduce in this article a new domain decomposition algorithm for parabolic problems that combines Mortar Mixed Finite
Element methods for the space discretization with operator splitting schemes for the time discretization. The main advantage
of this method is to be fully parallel. The algorithm is proven to be unconditionally stable and a convergence result in
(Δt/h
1/2) is presented. 相似文献
17.
Summary. We study the additive and multiplicative Schwarz domain decomposition methods for elliptic boundary value problem of order
2 r based on an appropriate spline space of smoothness . The finite element method reduces an elliptic boundary value problem to a linear system of equations. It is well known that
as the number of triangles in the underlying triangulation is increased, which is indispensable for increasing the accuracy
of the approximate solution, the size and condition number of the linear system increases. The Schwarz domain decomposition
methods will enable us to break the linear system into several linear subsystems of smaller size. We shall show in this paper
that the approximate solutions from the multiplicative Schwarz domain decomposition method converge to the exact solution
of the linear system geometrically. We also show that the additive Schwarz domain decomposition method yields a preconditioner
for the preconditioned conjugate gradient method. We tested these methods for the biharmonic equation with Dirichlet boundary
condition over an arbitrary polygonal domain using cubic spline functions over a quadrangulation of the given domain. The computer experiments agree with our theoretical results.
Received December 28, 1995 / Revised version received November 17, 1998 / Published online September 24, 1999 相似文献
18.
In this paper we consider second order scalar elliptic boundary value problems posed over three–dimensional domains and their
discretization by means of mixed Raviart–Thomas finite elements [18]. This leads to saddle point problems featuring a discrete
flux vector field as additional unknown. Following Ewing and Wang [26], the proposed solution procedure is based on splitting
the flux into divergence free components and a remainder. It leads to a variational problem involving solenoidal Raviart–Thomas
vector fields. A fast iterative solution method for this problem is presented. It exploits the representation of divergence
free vector fields as s of the –conforming finite element functions introduced by Nédélec [43]. We show that a nodal multilevel splitting of these finite
element spaces gives rise to an optimal preconditioner for the solenoidal variational problem: Duality techniques in quotient
spaces and modern algebraic multigrid theory [50, 10, 31] are the main tools for the proof.
Received November 4, 1996 / Revised version received February 2, 1998 相似文献
19.
Summary. We compare additive and multiplicative Schwarz preconditioners for the iterative solution of regularized linear inverse problems,
extending and complementing earlier results of Hackbusch, King, and Rieder. Our main findings are that the classical convergence
estimates are not useful in this context: rather, we observe that for regularized ill-posed problems with relevant parameter
values the additive Schwarz preconditioner significantly increases the condition number. On the other hand, the multiplicative version greatly improves conditioning, much beyond the existing
theoretical worst-case bounds.
We present a theoretical analysis to support these results, and include a brief numerical example. More numerical examples
with real applications will be given elsewhere.
Received May 28, 1998 / Published online: July 7, 1999 相似文献
20.
Summary. Three iterative domain decomposition methods are considered: simultaneous updates on all subdomains (Additive Schwarz Method),
flow directed sweeps and double sweeps. By using some techniques of formal language theory we obtain a unique criterion
of convergence for the three methods. The convergence rate is a function of the criterion and depends on the algorithm.
Received October 24, 1994 / Revised version received November 27, 1995 相似文献