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.     

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.     

Convergence and nonlinear stability of the Lagrange-Galerkin method for the Navier-Stokes equations

Summary The Lagrange-Galerkin method is a numerical technique for solving convection — dominated diffusion problems, based on combining a special discretisation of the Lagrangian material derivative along particle trajectories with a Galerkin finite element method. We present optimal error estimates for the Lagrange-Galerkin mixed finite element approximation of the Navier-Stokes equations in a velocity/pressure formulation. The method is shown to be nonlinearly stable.     

Regions of stability,equivalence theorems and the Courant-Friedrichs-Lewy condition

Summary The celebrated CFL condition for discretizations of hyperbolic PDEs is shown to be equivalent to some results of Jeltsch and Nevanlinna concerning regions of stability ofk-step,m-stage linear methods for the integration of ODEs. We characterize the methods for the numerical integration of the model equation,u _t=u _x which are weakly stable when the mesh-ratio takes the maximum value allowed by the CFL condition. We provide new equivalence theorems between stability and convergence, which improve on the classical results.     

Analysis of a damped nonlinear multilevel method

Summary In this paper, we present a new algorithm that is obtained by introducing a damping parameter in the classical Nonlinear Multilevel Method. We analyse this Damped Nonlinear Multilevel Method. In particular, we prove global convergence and local efficiency for a suitable class of problems.     

The frequency decomposition multi-grid method

Summary A new variant of the multi-grid algorithms is presented. It uses multiple coarse-grid corrections with particularly associated prolongations and restrictions. In this paper the robustness with respect to anisotropic problems is considered.Dedicated to the memory of Peter Henrici     

Counterexamples to a stability barrier

Summary We consider multistep difference schemes for the linear, constant coefficient advection equationu _t=cu_x. In the last section of Strang [5], a barrier for the order of stable schemes has been given which was independent of the number of time levels. Here we give two types of counterexamples to this barrier. The first type consists of formulas of highest possible order to a given stencil, which are stable for small positive Courant numbers. Further a formula is given where one does not insist on having the highest possible order for the stencil and uses the gained freedom to ensure stability for small positive and negative Courant numbers. In addition, an explicit formula is derived for the schemes of highest possible order when stability is disregarded.This work has been performed in the project Mehrschritt-Differenzenschemata of the Schwerpunktprogramm Finite Approximationen in der Strömungsmechanik which is supported by the DFG     

A particle method for first-order symmetric systems

Summary We present and study a conservative particle method of approximation of linear hyperbolic and parabolic systems. This method is based on an extensive use of cut-off functions. We prove its convergence inL ² at the order as soon as the cut-off function belongs toW ^m+1.1.Dedicated to Professor Joachim Nitsche on the occasion of his 60th birthday     

Applications of fixed-point methods to discrete variational and quasi-variational inequalities

Summary In this paper, discrete analogues of variational inequalities (V.I.) and quasi-variational inequalities (Q.V.I.), encountered in stochastic control and mathematical physics, are discussed.It is shown that those discrete V.I.'s and Q.V.I.'s can be written in the fixed point formx=Tx such that eitherT or some power ofT is a contraction. This leads to globally convergent iterative methods for the solution of discrete V.I.'s and Q.V.I.'s, which are very suitable for implementation on parallel computers with single-instruction, multiple-data architecture, particularly on massively parallel processors (M.P.P.'s).This research is in part supported by the U.S. Department of Energy, Engineering Research Program, under Contract No. DE-AS05-84EH13145     

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.     

Nonlinear stability and convergence of finite-difference methods for the “good” Boussinesq equation

Summary The good Boussinesq equationu _tt =–u _xxxx +u _xx +(u ²) _xx has recently been found to possess an interesting soliton-interaction mechanism. In this paper we study the nonlinear stability and the convergence of some simple finite-difference schemes for the numerical solution of problems involving the good Boussinesq equation. Numerical experimentas are also reported.     

Convergence of mixed finite element approximations for the shallow arch problem

Summary The stability and convergence of mixed finite element methods are investigated, for an equilibrium problem for thin shallow elastic arches. The problem in its standard form contains two terms, corresponding to the contributions from the shear and axial strains, with a small parameter. Lagrange multipliers are introduced, to formulate the problem in an alternative mixed form. Questions of existence and uniqueness of solutions to the standard and mixed problems are addressed. It is shown that finite element approximations of the mixed problem are stable and convergent. Reduced integration formulations are equivalent to a mixed formulation which in general is distinct from the formulation shown to be stable and convergent, except when the order of polynomial interpolationt of the arch shape satisfies 1tmin (2,r) wherer is the order of polynomial approximation of the unknown variables.     

An optimal order multigrid method for biharmonic,C 1 finite element equations

Summary In this paper, we study a special multigrid method for solving large linear systems which arise from discretizing biharmonic problems by the Hsieh-Clough-Tocher,C ¹ macro finite elements or several otherC ¹ finite elements. Since the multipleC ¹ finite element spaces considered are not nested, the nodal interpolation operator is used to transfer functions between consecutive levels in the multigrid method. This method converges with the optimal computational order.     

Stability and accuracy for implicit semidiscretizations of hyperbolic problems

Summary In this paper we give bounds for the error constants of certain classes of stable implicit finite difference methods for first order hyperbolic equations in one space dimension. We consider classes of methods that user downwind ands upwind points in the explicit part andR downwind andS upwind points in the implicit part, respectively, and that are of optimal orderp=min (r+R+s+S, 2(r+R+1), 2(s+S)).In some cases the error constant of interpolatory methods [5] can be improved. The results are proved via the order star technique. They are further used to determine methods of optimal order that are stable.     

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     

Alpha well-posedness,alpha stability,and the matrix theorems of H.-O. Kreiss

Summary For systems of partial differential equations with constant coefficients and for the corresponding difference equations the concepts of well-posedness and stability are introduced. These concepts are more general than strong well-posedness and stability on the one hand, and more restrictive than weak well-posedness (Petrovskii condition) and weak stability (von Neumann condition) on the other. Characterizations of these properties are established which partly extend the matrix theorems of H.-O. Kreiss. Also a Lax type theorem is valid in this setting.This author was supported by the Deutsche Forschungsgemeinschaft (Grant Go 261/4)     

Absolute monotonicity of rational functions occurring in the numerical solution of initial value problems

Summary This paper deals with rational functions ø(z) approximating the exponential function exp(z) related to numerical procedures for solving initial value problems. Motivated by positivity and contractivity requirements imposed on these numerical procedures we study the greatest nonnegative numberR, denoted byR(ø), such that ø is absolutely monotonic on (–R, 0]. An algorithm for the computation ofR(ø) is presented. Application of this algorithm yields the valueR(ø) for the well-known Padé approximations to exp(z). For some specific values ofm, n andp we determine the maximum ofR(ø) when ø varies over the class of all rational functions ø with degree of the numerator m, degree of the denominator n and ø(z)=exp(z)+(z ^p+1 ) (forz0).     

Analysis of the Kleiser-Schumann method

Summary The Kleiser-Schumann algorithm for the approximation of the Stokes problem by Fourier/Legendre polynomials is analized. Stability when the degree of the polynomials increases is established, whereas error estimates in Sobolev spaces are proven.The research of this author has been partially supported by the U.S. Army through its European Research Office under contract No. DAJA-84-C-0035     

A fast iterative method for solving stationary heat conduction problems on regions partitioned into rectangles

Summary The paper deals with some finite element approximation of stationary heat conduction problems on regions which can be partitioned into rectangular subregions. By a special superelement-technique employing fast elimination of the inner nodal parameters, the original finite element problem is reduced to a smaller problem, which is only connected with the nodes on the boundary of the superelements. To solve the reduced system of finite element equations, an efficient iterative algorithm is proposed. This algorithm is based either on the conjugate gradient method or the Tshebysheff method, using a special matrix by vector multiplication procedure. The explicit form of the matrix is not used. The presented numerical method is asymptotically optimal with respect to the memory requirement as well as to the operation count.     

On the finite volume element method

Summary The finite volume element method (FVE) is a discretization technique for partial differential equations. It uses a volume integral formulation of the problem with a finite partitioning set of volumes to discretize the equations, then restricts the admissible functions to a finite element space to discretize the solution. this paper develops discretization error estimates for general selfadjoint elliptic boundary value problems with FVE based on triangulations with linear finite element spaces and a general type of control volume. We establishO(h) estimates of the error in a discreteH ¹ semi-norm. Under an additional assumption of local uniformity of the triangulation the estimate is improved toO(h ²). Results on the effects of numerical integration are also included.This research was sponsored in part by the Air Force Office of Scientific Research under grant number AFOSR-86-0126 and the National Science Foundation under grant number DMS-8704169. This work was performed while the author was at the University of Colorado at Denver