On an iterative method for variational inequalities

Summary A number of numerical solutions are presented as examples of a new iterative method for variational inequalities. The iterative method is based on the reduction of variational inequalities to the Wiener-Hopf equations. For obstacle problems the convergence is guaranteed inW ^1,p spaces forp2. The examples presented are one and two dimensional obstacle problems in cases when the Greens function is known, but the method is very general.     

On multi-grid methods for variational inequalities

Summary We consider here a general class of algorithms for the numerical solution of variational inequalities. A convergence proof is given and in particular a multi-grid method is described. Numerical results are presented for the finite-difference discretization of an obstacle problem for minimal surfaces     

Steplength optimization and linear multigrid methods

Summary Recently steplength parameters have been used in linear multigrid methods. In this paper we give a theoretical analysis of the effects of steplength optimization in a rather general framework which covers two different implementations of steplength optimization in standard multigrid methods.     

Domain imbedding methods for the Stokes equations

Summary We study direct and iterative domain imbedding methods for the Stokes equations on certain non-rectangular domains in two space dimensions. We analyze a continuous analog of numerical domain imbedding for bounded, smooth domains, and give an example of a simple numerical algorithm suggested by the continuous analysis. This algorithms is applicable for simply connected domains which can be covered by rectangular grids, with uniformly spaced grid lines in at least one coordinate direction. We also discuss a related FFT-based fast solver for Stokes problems with physical boundary conditions on rectangles, and present some numerical results.     

Multi-grid methods for stokes and navier-stokes equations

Summary In the present paper we introduce transforming iterations, an approach to construct smoothers for indefinite systems. This turns out to be a convenient tool to classify several well-known smoothing iterations for Stokes and Navier-Stokes equations and to predict their convergence behaviour, epecially in the case of high Reynolds-numbers. Using this approach, we are able to construct a new smoother for the Navier-Stokes equations, based on incomplete LU-decompositions, yielding a highly effective and robust multi-grid method. Besides some qualitative theoretical convergence results, we give large numerical comparisons and tests for the Stokes as well as for the Navier-Stokes equations. For a general convergence theory we refer to [29].This work was supported in part by Deutsche Forschungsgemeinschaft     

Multi-grid methods for Hamilton-Jacobi-Bellman equations

Summary In this paper we develop multi-grid algorithms for the numerical solution of Hamilton-Jacobi-Bellman equations. The proposed schemes result from a combination of standard multi-grid techniques and the iterative methods used by Lions and mercier in [11]. A convergence result is given and the efficiency of the algorithms is illustrated by some numerical examples.     

Estimates for multigrid methods based on red-black Gauss-Seidel smoothings

Summary TheMGR[v] algorithms of Ries, Trottenberg and Winter, the Algorithms 2.1 and 6.1 of Braess and the Algorithm 4.1 of Verfürth are all multigrid algorithms for the solution of the discrete Poisson equation (with Dirichlet boundary conditions) based on red-black Gauss-Seidel smoothing. Both Braess and Verfürth give explicit numerical upper bounds on the rate of convergence of their methods in convex polygonal domains. In this work we reconsider these problems and obtain improved estimates for theh–2h Algorithm 4.1 as well asW-cycle estimates for both schemes in non-convex polygonal domains. The proofs do not depend on the strengthened Cauchy inequality.Sponsored by the Air Force Office of Scientific Research under Contract No. AFOSR-86-0163     

On the convergence of multi-grid methods with transforming smoothers

Summary In the present paper we give a convergence theory for multi-grid methods with transforming smoothers as introduced in [31] applied to a general system of partial differential equations. The theory follows Hackbusch's approach for scalar pde and allows a convergence proof for some well-known multi-grid methods for Stokes- and Navier-Stokes equations as DGS by Brandt-Dinar, [5], TILU from [31] and the SIMPLE-methods by Patankar-Spalding, [23].This work was supported in part by Deutsche Forschungsgemeinschaft     

A convergence analysis of hopscotch methods for fourth order parabolic equations

Summary Consider the ODE (ordinary differential equation) that arises from a semi-discretization (discretization of the spatial coordinates) of a first order system form of a fourth order parabolic PDE (partial differential equation). We analyse the stability of the finite difference methods for this fourth order parabolic PDE that arise if one applies the hopscotch idea to this ODE.Often the error propagation of these methods can be represented by a three terms matrix-vector recursion in which the matrices have a certain anti-hermitian structure. We find a (uniform) expression for the stability bound (or error propagation bound) of this recursion in terms of the norms of the matrices. This result yields conditions under which these methods are strongly asymptotically stable (i.e. the stability is uniform both with respect to the spatial and the time stepsizes (tending to 0) and the time level (tending to infinity)), also in case the PDE has (spatial) variable coefficients. A convergence theorem follows immediately.     

Pointwise accuracy of a finite element method for nonlinear variational inequalities

Summary Consider the following quasilinear elliptic PDE, which is equivalent to a nonlinear variational inequality: –divF(u)+(u)f. Here is a singular maximal monotone graph and the nonlinear differential operator is only assumed to be monotone; surfaces of prescribed mean curvature over obstacles may thus be viewed as relevant examples. The numerical approximation proposed in this paper consists of combining continuous piecewise linear finite elements with a preliminary regularization of . The resulting scheme is shown to be quasi-optimally accurate inL . The underlying analysis makes use of both a topological technique and a sharpL ^p -duality argument.This work was partially supported by Consiglio Nazionale delle Ricerche of Italy while the author was in residence at the Istituto di Analisi Numerica del C.N.R. di Pavia     

A class of iterative methods for solving saddle point problems

Summary We consider the numerical solution of indefinite systems of linear equations arising in the calculation of saddle points. We are mainly concerned with sparse systems of this type resulting from certain discretizations of partial differential equations. We present an iterative method involving two levels of iteration, similar in some respects to the Uzawa algorithm. We relate the rates of convergence of the outer and inner iterations, proving that, under natural hypotheses, the outer iteration achieves the rate of convergence of the inner iteration. The technique is applied to finite element approximations of the Stokes equations.The work of this author was supported by the Office of Naval Research under contract N00014-82K-0197, by Avions Marcel Dassault, 78 Quai Marcel Dassault, 92214 St Cloud, France, and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, FranceThe work of this author was supported by Avions Marcel Daussault-Breguet Aviation, 78 quai Marcel Daussault, F-92214 St Cloud, France and by Direction des Recherches Etudes et Techniques, 26 boulevard Victor, F-75996 Paris Armées, FranceThe work of this author was supported by Konrad-Zuse-Zentrum für Informationstechnik Berlin, Federal Republic of Germany     

A new class of variational problems arising in the modeling of elastic multi-structures

Summary It is shown howelastic multi-structures that comprise substructures of possibly different dimensions (three-dimensional structures, plates, rods) are modeled bycoupled, pluri-dimensional, variational problems of a new type. Following recent work by the author, H. LeDret, and R. Nzengwa, we describe here in detail one such problem, which is simultaneously posed over a threedimensional open set with a slit and a two-dimensional open set. The numerical analysis of such problems is also discussed and finally, some numerical results are presented.Dedicated to R. S. Varga on the occasion of his sixtieth birthdayInvited lecture,Conference on Approximation Theory and Numerical Linear Algebra, in honor of Richard S. Varga on the occasion of his 60th birthday, March 30–April 1, 1989, Kent State University, Kent, USALaboratoire du Centre National de la Recherche Scientifique associé à l'Université Pierre et Marie Curie     

Fully discrete Galerkin approximations of parabolic boundary-value problems with nonsmooth boundary data

Summary In this paper we study the convergence properties of a fully discrete Galerkin approximation with a backwark Euler time discretization scheme. An approach based on semigroup theory is used to deal with the nonsmooth Dirichlet boundary data which cannot be handled by standard techniques. This approach gives rise to optimal rates of convergence inL _p[O,T;L ₂()] norms for boundary conditions inL _p[O,T;L ₂()], 1p.     

AnL 2-error estimate for an approximation of the solution of a parabolic variational inequality

Summary We estimate the order of the difference between the numerical approximation and the solution of a parabolic variational inequality. The numerical approximation is obtained using a finite element discretization in space and a finite difference discretization in time which is more general than is used in the literature. We obtain better error estimates than those given in the literature. The error estimates are compared with numerical experiments.     

Spectral methods with sparse matrices

Summary Spectral methods employ global polynomials for approximation. Hence they give very accurate approximations for smooth solutions. Unfortunately, for Dirichlet problems the matrices involved are dense and have condition numbers growing asO(N ⁴) for polynomials of degree N in each variable. We propose a new spectral method for the Helmholtz equation with a symmetric and sparse matrix whose condition number grows only asO(N ²). Certain algebraic spectral multigrid methods can be efficiently used for solving the resulting system. Numerical results are presented which show that we have probably found the most effective solver for spectral systems.     

Convergence and comparison analysis of some numerical Schwarz methods

Summary Domain decomposition methods are a natural means for solving partial differential equations on multi-processors. The spatial domain of the equation is expressed as a collection of overlapping subdomains and the solution of an associated equation is solved on each of these subdomains. The global solution is then obtained by piecing together the subsolutions in some manner. For elliptic equations, the global solution is obtained by iterating on the subdomains in a fashion that resembles the classical Schwarz alternating method. In this paper, we examine the convergence behavior of different subdomain iteration procedures as well as different subdomain approximations. For elliptic equations, it is shown that certain iterative procedures are equivalent to block Gauss-Siedel and Jacobi methods. Using different subdomain approximations, an inner-outer iterative procedure is defined.M-matrix analysis yields a comparison of different inner-outer iterations.Dedicated to the memory of Peter HenriciThis work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under contract No. W-7405-Eng-48     

Convergence of the multilevel Full Approximation Scheme including theV-cycle

Summary The multilevel Full Approximation Scheme (FAS ML) is a well-known solver for nonlinear boundary value problems. In this paper we prove local quantitative convergence statements for a class of FAS ML algorithms in a general Hilbertspace setting. This setting clearly exhibits the structure of FAS ML. We prove local convergence of a nested iteration for a rather concrete class of FAS ML algorithms in whichV-cycles and only one Jacobilike pre- and post-smoothing on each level are used.     

Preconditioning indefinite discretization matrices

Summary The finite element discretization of many elliptic boundary value problems leads to linear systems with positive definite and symmetric coefficient matrices. Many efficient preconditioners are known for these systems. We show that these preconditioning matrices can also be used for the linear systems arising from boundary value problems which are potentially indefinite due to lower order terms in the partial differential equation. Our main tool is a careful algebraic analysis of the condition numbers and the spectra of perturbed matrices which are preconditioned by the same matrices as in the unperturbed case.     

On the regularization of projection methods for solving III-posed problems

Summary In this paper we consider a class of regularization methods for a discretized version of an operator equation (which includes the case that the problem is ill-posed) with approximately given right-hand side. We propose an a priori- as well as an a posteriori parameter choice method which is similar to the discrepancy principle of Ivanov-Morozov. From results on fractional powers of selfadjoint operators we obtain convergence rates, which are (in many cases) the same for both parameter choices.     

On the approximate solution of nonlinear variational inequalities

Summary Nonlinear locally coercive variational inequalities are considered and especially the minimal surface over an obstacle. Optimal or nearly optimal error estimates are proved for a direct discretization of the problem with linear finite elements on a regular triangulation of the not necessarily convex domain. It is shown that the solution may be computed by a globally convergent relaxation method. Some numerical results are presented.