On box schemes for elartliptic variational inequalities

General finite volume approximations in two and three space dimensions are studied for the discretization of interior and boundary obstacle problems with mixed boundary conditions. First order convergence of the finite volume (box) solution is shown in the energy norm. Based on a discrete maximum principle there are proposed two penalization techniques for the solution of the finite volume inequalities. By coupling of discretization and penalty parameters the overall error is analyzed. The iterative solution of the penalty problems is discussed. Finally, results of numerical experiments are presented to illustrate the convergence behaviour between the exact, the box and the penalty solutions.     

A mortar mimetic finite difference method on non-matching grids

We consider mimetic finite difference approximations to second order elliptic problems on non-matching multiblock grids. Mortar finite elements are employed on the non-matching interfaces to impose weak flux continuity. Optimal convergence and, in certain cases, superconvergence is established for both the scalar variable and its flux. The theory is confirmed by computational results. Supported by the US Department of Energy, under contractW-7405-ENG-36. LA-UR-04-4740. Partially supported by NSF grants EIA 0121523 and DMS 0411413, by NPACI grant UCSD 10181410, and by DOE grant DE-FGO2-04ER25617. Partially supported by NSF grants DMS 0107389, DMS 0112239 and DMS 0411694 and by DOE grant DE-FG02-04ER25618.     

A regularized penalty method for solving convex semi-infinite programs

This paper is concerned with the stable solution of ill-posed convex semi-infinite problems on the base of their sequential approximation by finite dimensional convex problems on a sequence of grids. These auxiliary programs are constructed by using the iterative Prox-regularization and for solving each of them only one step of a penalty method is applied. A simple deletion procedure of inactive constraints is suggested. The choice of the control parameters secure the convergence of the methods and a linear convergence rate is obtained     

Adaptive finite elements for exterior domain problems

Summary. We present an adaptive finite element method for solving elliptic problems in exterior domains, that is for problems in the exterior of a bounded closed domain in , . We describe a procedure to generate a sequence of bounded computational domains , , more precisely, a sequence of successively finer and larger grids, until the desired accuracy of the solution is reached. To this end we prove an a posteriori error estimate for the error on the unbounded domain in the energy norm by means of a residual based error estimator. Furthermore we prove convergence of the adaptive algorithm. Numerical examples show the optimal order of convergence. Received July 8, 1997 /Revised version received October 23, 1997     

A penalty method for a mixed nonlinear complementarity problem

We propose a power penalty method for a mixed nonlinear complementarity problem (MNCP) and show that the solution to the penalty equation converges to that of the MNCP exponentially as the penalty parameter approaches infinity, provided that the mapping involved in the MNCP is both continuous and ξ-monotone. Furthermore, a convergence theorem is established when the monotonicity assumption on the mapping is removed. To demonstrate the usefulness and the convergence rates of this method, we design a non-trivial test MNCP problem arising in shape-preserving bi-harmonic interpolation and apply our method to this test problem. The numerical results confirm our theoretical findings.     

Convergence of a penalty-finite element approximation for an obstacle problem

Summary This study establishes an error estimate for a penalty-finite element approximation of the variational inequality obtained by a class of obstacle problems. By special identification of the penalty term, we first show that the penalty solution converges to the solution of a mixed formulation of the variational inequality. The rate of convergence of the penalization is where is the penalty parameter. To obtain the error of finite element approximation, we apply the results obtained by Brezzi, Hager and Raviart for the mixed finite element method to the variational inequality.     

Two-level preconditioners for regularized inverse problems I: Theory

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     

A scalable FETI-DP algorithm with non-penetration mortar conditions on contact interface

By combining FETI algorithms of dual-primal type with recent results for bound constrained quadratic programming problems, we develop an optimal algorithm for the numerical solution of coercive variational inequalities. The model problem is discretized using non-penetration conditions of mortar type across the potential contact interface, and a FETI-DP algorithm is formulated. The resulting quadratic programming problem with bound constraints is solved by a scalable algorithm with a known rate of convergence given in terms of the spectral condition number of the quadratic problem. Numerical experiments for non-matching meshes across the contact interface confirm the theoretical scalability of the algorithm.     

Finite element methods with numerical quadrature for elliptic problems with smooth interfaces

The purpose of this paper is to study the effect of the numerical quadrature on the finite element approximation to the exact solution of elliptic equations with discontinuous coefficients. Due to low global regularity of the solution, it seems difficult to achieve optimal order of convergence with classical finite element methods [Z. Chen, J. Zou, Finite element methods and their convergence for elliptic and parabolic interface problems, Numer. Math. 79 (1998) 175-202]. We derive error estimates in finite element method with quadrature for elliptic interface problems in a two-dimensional convex polygonal domain. Optimal order error estimates in L² and H¹ norms are shown to hold even if the regularity of the solution is low on the whole domain. Finally, numerical experiment for two dimensional test problem is presented in support of our theoretical findings.     

Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems,part II: Convergence theory

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.     

An adaptive stabilized finite element method for the generalized Stokes problem

In this work we present an adaptive strategy (based on an a posteriori error estimator) for a stabilized finite element method for the Stokes problem, with and without a reaction term. The hierarchical type estimator is based on the solution of local problems posed on appropriate finite dimensional spaces of bubble-like functions. An equivalence result between the norm of the finite element error and the estimator is given, where the dependence of the constants on the physics of the problem is explicited. Several numerical results confirming both the theoretical results and the good performance of the estimator are given.     

Adaptive Strategy for the Damping Parameters in an Iteratively Regularized Gauss–Newton Method

In this paper, a convergence analysis of an adaptive choice of the sequence of damping parameters in the iteratively regularized Gauss–Newton method for solving nonlinear ill-posed operator equations is presented. The selection criterion is motivated from the damping parameter choice criteria, which are used for the efficient solution of nonlinear least-square problems. The performance of this selection criterion is tested for the solution of nonlinear ill-posed model problems.     

A family of multistep methods to integrate orbits on spheres

Summary A trajectory problem is an initial value problem where the interest lies in obtaining the curve traced by the solution, rather than in finding the actual correspondence between the values of the parameter and the points on that curve. This paper introduces a family of multi-stage, multi-step numerical methods to integrate trajectory problems whose solution is on a spherical surface. It has been shown that this kind of algorithms has good numerical properties: consistency, stability, convergence and others that are not standard. The latest ones make them a better choice for certain problems.     

A Regularized Iterative Scheme for Solving Nonlinear Ill-Posed Problems

In this article, we consider a regularized iterative scheme for solving nonlinear ill-posed problems. The convergence analysis and error estimates are derived by choosing the regularization parameter according to both a priori and a posteriori methods. The iterative scheme is stopped using an a posteriori stopping rule, and we prove that the scheme converges to the solution of the well-known Lavrentiev scheme. The salient features of the proposed scheme are: (i) convergence and error estimate analysis require only weaker assumptions compared to standard assumptions followed in literature, and (ii) consideration of an adaptive a posteriori stopping rule and a parameter choice strategy that gives the same convergence rate as that of an a priori method without using the smallness assumption, the source condition. The above features are very useful from theory and application points of view. We also supply the numerical results to illustrate that the method is adaptable. Further, we compare the numerical result of the proposed method with the standard approach to demonstrate that our scheme is stable and achieves good computational output.     

Boundary element collocation methods using splines with multiple knots

Summary. We extend the theory of boundary element collocation methods by allowing reduced inter-element smoothness (or in other words, by allowing trial functions that are splines with multiple knots). Our convergence analysis is based on a recurrence relation for the Fourier coefficients of the numerical solution, and so is restricted to uniform grids on smooth, closed curves. Superconvergence is possible with special choices of the collocation points. Numerical experiments with a model problem confirm the convergence rates predicted by our theory. Received September 19, 1995     

Hybrid extragradient proximal algorithm coupled with parametric approximation and penalty/barrier methods

In this article we study the hybrid extragradient method coupled with approximation and penalty schemes for convex minimization problems. Under certain hypotheses, which include, for example, the case of Tikhonov regularization, we prove asymptotic convergence of the method to the solution set of our minimization problem. When we use schemes of penalization or barrier, we can show asymptotic convergence using the well-known fast/slow parameterization techniques and exploiting the existence and finite length of an optimal path.     

A characterization of mapping unstructured grids onto structured grids and using multigrid as a preconditioner

Many problems based on unstructured grids provide a natural multigrid framework due to using an adaptive gridding procedure. When the grids are saved, even starting from just a fine grid problem poses no serious theoretical difficulties in applying multigrid. A more difficult case occurs when a highly unstructured grid problem is to be solved with no hints how the grid was produced. Here, there may be no natural multigrid structure and applying such a solver may be quite difficult to do. Since unstructured grids play a vital role in scientific computing, many modifications have been proposed in order to apply a fast, robust multigrid solver. One suggested solution is to map the unstructured grid onto a structured grid and then apply multigrid to a sequence of structured grids as a preconditioner. In this paper, we derive both general upper and lower bounds on the condition number of this procedure in terms of computable grid parameters. We provide examples to illuminate when this preconditioner is a useful (e. g.,p orh-p formulated finite element problems on semi-structured grids) or should be avoided (e.g., typical computational fluid dynamics (CFD) or boundary layer problems). We show that unless great care is taken, this mapping can lead to a system with a high condition number which eliminates the advantage of the multigrid method. This work was partially supported by ONR Grant # N0014-91-J-1576.     

Patch-adaptive multilevel iteration

Themultilevel adaptive iteration is an attempt to improve both the robustness and efficiency of iterative sparse system solvers. Unlike in most other iterative methods, the order of processing and sequence of operations is not determined a priori. The method consists of a relaxation scheme with an active set strategy and can be viewed as an efficient implementation of the Gauß-Southwell relaxation. With this strategy, computational work is focused on where it can efficiently improve the solution quality. To obtain full efficiency, the algorithm must be used on a multilevel structure. This algorithm is then closely related to multigrid or multilevel preconditioning algorithms, and can be shown to have asymptotically optimal convergence. In this paper the focus is on a variant that uses data structures with a locally uniform grid refinement. The resulting grid system consists of a collection of patches where each patch is a uniform rectangular grid and where adaptive refinement is accomplished by arranging the patches flexibly in space. This construction permits improved implementations that better exploit high performance computer designs. This will be demonstrated by numerical examples.     

Stability and error estimation for component adaptive grid methods

Component adaptive grid (CAG) methods for solving hyperbolic partial differential equations (PDEs) are discussed in this paper. Applying recent stability results for a class of numerical methods on uniform grids, the convergence of these methods for linear problems on component adaptive grids is established here. Furthermore, the computational error can be estimated on CAGs using these stability results. Using these estimates, the error can be controlled on CAGs. Thus, the solution can be computed efficiently on CAGs within a given error tolerance. Computational results for time dependent linear problems in one and two space dimensions are presented.     

A generalization of Arcangeli's method for ill-posed problems leading to optimal rates

Schock (1984) considered a general a posteriori parameter choice strategy for the regularization of ill-posed problems which provide nearly the optimal rate of convergence. We improve the result of Schock and give a class of parameter choice strategies leading to optimal rates As a particular case we prove that the Arcangeli's method do give optimal rate of convergence.