Grid approximation of a parabolic convection-diffusion equation on a priori adapted grids: ε-uniformly convergent schemes

The boundary value problem for a singularly perturbed parabolic convection-diffusion equation is considered. A finite difference scheme on a priori (sequentially) adapted grids is constructed and its convergence is examined. The construction of the scheme on a priori adapted grids is based on a majorant of the singular component of the grid solution that makes it possible to a priori find a subdomain in which the grid solution should be further refined given the perturbation parameter ε, the size of the uniform mesh in x, the desired accuracy of the grid solution, and the prescribed number of iterations K used to refine the solution. In the subdomains where the solution is refined, the grid problems are solved on uniform grids. The error of the solution thus constructed weakly depends on ε. The scheme converges almost ε-uniformly; namely, it converges under the condition N ^?1 = o(ε^v), where v = v(K) can be chosen arbitrarily small when K is sufficiently large. If a piecewise uniform grid is used instead of a uniform one at the final Kth iteration, the difference scheme converges ε-uniformly. For this piecewise uniform grid, the ratio of the mesh sizes in x on the parts of the mesh with a constant size (outside the boundary layer and inside it) is considerably less than that for the known ε-uniformly convergent schemes on piecewise uniform grids.     

地形构造中地震波传播的非对称交错网格模拟

提出了一种新的三维空间对称交错网格差分方法,模拟地形构造中弹性波传播过程．通过具有二阶时间精度和四阶空间精度的不规则网格差分算子用来近似一阶弹性波动方程,引入附加差分公式解决非均匀交错网格的不对称问题．该方法无需在精细网格和粗糙网格间进行插值,所有网格点上的计算在同一次空间迭代中完成．使用精细不规则网格处理海底粗糙界面、 断层和空间界面等复杂几何构造, 理论分析和数值算例表明, 该方法不但节省了大量内存和计算时间, 而且具有令人满意的稳定性和精度．在模拟地形构造中地震波传播时,该方法比常规方法效率更高．     

An approach combining the Ritz-Galerkin and finite difference methods

The nonconforming combination of Ritz-Galerkin and finite difference methods is presented for solving elliptic boundary value problems with singularities. The Ritz-Galerkin method is used in the subdomains including singularities, the finite difference method is used in the rest of the solution domain. Moreover, on the common boundary of two regions where two different methods are used, the continuity conditions are constrained only on the nodes of difference grids. Theoretical analysis and numerical experiments have shown that average errors of numerical solutions and their generalized derivatives can reach the convergence rate O(h^2-δ), where h is the mesh spacing of uniform difference grids, and δ is an arbitrarily small, positive number. This convergence rate is better than O(h), obtained by the nonconforming combination of the Ritz-Galerkin and finite element methods.     

A holistic finite difference approach models linear dynamics consistently

I prove that a centre manifold approach to creating finite difference models will consistently model linear dynamics as the grid spacing becomes small. Using such tools of dynamical systems theory gives new assurances about the quality of finite difference models under nonlinear and other perturbations on grids with finite spacing. For example, the linear advection-diffusion equation is found to be stably modelled for all advection speeds and all grid spacings. The theorems establish an extremely good form for the artificial internal boundary conditions that need to be introduced to apply centre manifold theory. When numerically solving nonlinear partial differential equations, this approach can be used to systematically derive finite difference models which automatically have excellent characteristics. Their good performance for finite grid spacing implies that fewer grid points may be used and consequently there will be less difficulties with stiff rapidly decaying modes in continuum problems.

     

A high order HODIE finite difference scheme for 1D parabolic singularly perturbed reaction-diffusion problems

This paper deals with the numerical approximation of the solution of 1D parabolic singularly perturbed problems of reaction-diffusion type. The numerical method combines the standard implicit Euler method on a uniform mesh to discretize in time and a HODIE compact fourth order finite difference scheme to discretize in space, which is defined on a priori special meshes condensing the grid points in the boundary layer regions. The method is uniformly convergent having first order in time and almost fourth order in space. The analysis of the uniform convergence is made in two steps, splitting the contribution to the error from the time and the space discretization. Although this idea has been previously used to prove the uniform convergence for parabolic singularly perturbed problems, here the proof is based on a new study of the asymptotic behavior of the exact solution of the semidiscrete problems obtained after the time discretization by using the Euler method. Some numerical results are given corroborating in practice the theoretical results.     

Numerical experiments on the condition number of the interpolation matrices for radial basis functions

Through numerical experiments, we examine the condition numbers of the interpolation matrix for many species of radial basis functions (RBFs), mostly on uniform grids. For most RBF species that give infinite order accuracy when interpolating smooth f(x)—Gaussians, sech's and Inverse Quadratics—the condition number κ(α,N) rapidly asymptotes to a limit κasymp(α) that is independent of N and depends only on α, the inverse width relative to the grid spacing. Multiquadrics are an exception in that the condition number for fixed α grows as N². For all four, there is growth proportional to an exponential of 1/α (1/α² for Gaussians). For splines and thin-plate splines, which contain no width parameter, the condition numbers grows asymptotically as a power of N—a large power as the order of the RBF increases. Random grids typically increase the condition number (for fixed RBF width) by orders of magnitude. The quasi-random, low discrepancy Halton grid may, however, have a lower condition number than a uniform grid of the same size.     

A parameter-uniform numerical method for time-dependent singularly perturbed differential-difference equations

A numerical study is made for solving a class of time-dependent singularly perturbed convection–diffusion problems with retarded terms which often arise in computational neuroscience. To approximate the retarded terms, a Taylor’s series expansion has been used and the resulting time-dependent singularly perturbed differential equation is approximated using parameter-uniform numerical methods comprised of a standard implicit finite difference scheme to discretize in the temporal direction on a uniform mesh by means of Rothe’s method and a B-spline collocation method in the spatial direction on a piecewise-uniform mesh of Shishkin type. The method is shown to be accurate of order O(M⁻¹ + N⁻² ln³N), where M and N are the number of mesh points used in the temporal direction and in the spatial direction respectively. An extensive amount of analysis has been carried out to prove the uniform convergence with respect to the singular perturbation parameter. Numerical results are given to illustrate the parameter-uniform convergence of the numerical approximations. Comparisons of the numerical solutions are performed with an upwind and midpoint upwind finite difference scheme on a piecewise-uniform mesh to demonstrate the efficiency of the method.     

On the convergence of nonnested multigrid methods with nested spaces on coarse grids

Multigrid methods for discretized partial differential problems using nonnested conforming and nonconforming finite elements are here defined in the general setting. The coarse‐grid corrections of these multigrid methods make use of different finite element spaces from those on the finest grid. In general, the finite element spaces on the finest grid are nonnested, while the spaces are nested on the coarse grids. An abstract convergence theory is developed for these multigrid methods for differential problems without full elliptic regularity. This theory applies to multigrid methods of nonnested conforming and nonconforming finite elements with the coarse‐grid corrections established on nested conforming finite element spaces. Uniform convergence rates (independent of the number of grid levels) are obtained for both the V and W‐cycle methods with one smoothing on all coarse grids and with a sufficiently large number of smoothings solely on the finest grid. In some cases, these uniform rates are attained even with one smoothing on all grids. The present theory also applies to multigrid methods for discretized partial differential problems using mixed finite element methods. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 265–284, 2000     

Strong-form approach to elasticity: Hybrid finite difference-meshless collocation method (FDMCM)

We propose a numerical method that combines the finite difference (FD) and strong form (collocation) meshless method (MM) for solving linear elasticity equations. We call this new method FDMCM. The FDMCM scheme uses a uniform Cartesian grid embedded in complex geometries and applies both methods to calculate spatial derivatives. The spatial domain is represented by a set of nodes categorized as (i) boundary and near boundary nodes, and (ii) interior nodes. For boundary and near boundary nodes, where the finite difference stencil cannot be defined, the Discretization Corrected Particle Strength Exchange (DC PSE) scheme is used for derivative evaluation, while for interior nodes standard second order finite differences are used. FDMCM method combines the advantages of both FD and DC PSE methods. It supports a fast and simple generation of grids and provides convergence rates comparable to weak formulations. We demonstrate the appropriateness and robustness of the proposed scheme through various benchmark problems in 2D and 3D. Numerical results show good accuracy and h-convergence properties. The ease of computational grid generation makes the method particularly suited for problems where geometries are very complicated and known only imperfectly from images, frequently occurring in e.g. geomechanics and patient-specific biomechanics, where the proposed FDMCM method, after its extension to non-linear regime, appears to be a promising alternative to the traditional weak form-based numerical schemes used in the field.     

Two-scale sparse finite element approximations

To reduce computational cost,we study some two-scale finite element approximations on sparse grids for elliptic partial differential equations of second order in a general setting.Over any tensor product domain ?R~d with d = 2,3,we construct the two-scale finite element approximations for both boundary value and eigenvalue problems by using a Boolean sum of some existing finite element approximations on a coarse grid and some univariate fine grids and hence they are cheaper approximations.As applications,we obtain some new efficient finite element discretizations for the two classes of problem:The new two-scale finite element approximation on a sparse grid not only has the less degrees of freedom but also achieves a good accuracy of approximation.     

Adaptive energy preserving methods for partial differential equations

A framework for constructing integral preserving numerical schemes for time-dependent partial differential equations on non-uniform grids is presented. The approach can be used with both finite difference and partition of unity methods, thereby including finite element methods. The schemes are then extended to accommodate r-, h- and p-adaptivity. To illustrate the ideas, the method is applied to the Korteweg–de Vries equation and the sine-Gordon equation. Results from numerical experiments are presented.     

Adaptive p-version of the finite element method for solving boundary value problems for ordinary second-order differential equations

We suggest an adaptive strategy for constructing a hierarchical basis for a p-version of the finite element method used to solve boundary value problems for second-order ordinary differential equations. The choice of the order of an element on each grid interval is based on estimates of the change, in the norm of C, of the approximate solution or the value of the functional to be minimized when increasing the degree of the basis function added on this interval. The results of numerical experiments estimating the method efficiency are given for sample problems whose solutions have singularities of the boundary layer type. We make a comparison with the p-version of the finite element method, which uses a uniform growth of the degree of the basis functions, and with the h-version, which uses uniform grid refinement along with an adaptive grid refinement and coarsening strategy.     

A parameter-free stabilized finite element method for scalar advection-diffusion problems

We formulate and study numerically a new, parameter-free stabilized finite element method for advection-diffusion problems. Using properties of compatible finite element spaces we establish connection between nodal diffusive fluxes and one-dimensional diffusion equations on the edges of the mesh. To define the stabilized method we extend this relationship to the advection-diffusion case by solving simplified one-dimensional versions of the governing equations on the edges. Then we use H(curl)-conforming edge elements to expand the resulting edge fluxes into an exponentially fitted flux field inside each element. Substitution of the nodal flux by this new flux completes the formulation of the method. Utilization of edge elements to define the numerical flux and the lack of stabilization parameters differentiate our approach from other stabilized methods. Numerical studies with representative advection-diffusion test problems confirm the excellent stability and robustness of the new method. In particular, the results show minimal overshoots and undershoots for both internal and boundary layers on uniform and non-uniform grids.     

The impact of smooth W-grids in the numerical solution of singular perturbation two-point boundary value problems

This paper develops a semi-analytic technique for generating smooth nonuniform grids for the numerical solution of singularly perturbed two-point boundary value problems. It is based on the usual idea of mapping a uniform grid to the desired nonuniform grid. We introduce the W-grid, which depends on the perturbation parameter ? ? 1. For problems on [0, 1] with a boundary layer at one end point, the local mesh width h_i = x_i+1 − x_i, with 0 = x₀ < x₁ < ? < x_N = 1, is condensed at either 0 or 1. Two simple 2nd order finite element and finite difference methods are combined with the new mesh, and computational experiments demonstrate the advantages of the smooth W-grid compared to the well-known piecewise uniform Shishkin mesh. For small ?, neither the finite difference method nor the finite element method produces satisfactory results on the Shishkin mesh. By contrast, accuracy is vastly improved on the W-grid, which typically produces the nominal 2nd order behavior in L², for large as well as small values of N, and over a wide range of values of ?. We conclude that the smoothness of the mesh is of crucial importance to accuracy, efficiency and robustness.     

Using Richardson's method to construct high-order accurate adaptive grids

An algorithm is proposed to construct a sequence of evolutionary adaptive grids, each consisting of segments of uniform grids compatible with the Richardson extrapolation procedure. The necessary numerical accuracy is achieved by using Richardson's extrapolation method to increase the accuracy of the difference solution and by controlling the nonhomogeneity parameter on passing from one segment to the next. The numerical model used in the article is the diffusion-convection equation, whose solution contains large gradients. Numerical calculations show that the algorithm attains the prespecified accuracy on a nonuniform difference grid. Numerical examples support the universality of the proposed algorithm. High accuracy results can be obtained without changing the structure of the difference schemes approximating the original problem; only the grid spacing has to be changed. Translated from Chislennye Metody v Matematicheskoi Fizike, Moscow State University, pp. 22–36, 1998.     

Fast orthogonalization to the kernel of the discrete gradient operator with application to Stokes problem

We obtain a simple tensor representation of the kernel of the discrete d-dimensional gradient operator defined on tensor semi-staggered grids. We show that the dimension of the nullspace grows as O(n^d-2), where d is the dimension of the problem, and n is one-dimensional grid size. The tensor structure allows fast orthogonalization to the kernel. The usefulness of such procedure is demonstrated on three-dimensional Stokes problem, discretized by finite differences on semi-staggered grids, and it is shown by numerical experiments that the new method outperforms usually used stabilization approach.     

Time stepping for vectorial operator splitting

We present a fully implicit finite difference method for the unsteady incompressible Navier-Stokes equations. It is based on the one-step θ-method for discretization in time and a special coordinate splitting (called vectorial operator splitting) for efficiently solving the nonlinear stationary problems for the solution at each new time level. The resulting system is solved in a fully coupled approach that does not require a boundary condition for the pressure. A staggered arrangement of velocity and pressure on a structured Cartesian grid combined with the fully implicit treatment of the boundary conditions helps us to preserve the properties of the differential operators and thus leads to excellent stability of the overall algorithm. The convergence properties of the method are confirmed via numerical experiments.     

A numerical method for solving the Dirichlet problem for the wave equation

In this paper we present a numerical method for solving the Dirichlet problem for a two-dimensional wave equation. We analyze the ill-posedness of the problem and construct a regularization algorithm. Using the Fourier series expansion with respect to one variable, we reduce the problem to a sequence of Dirichlet problems for one-dimensional wave equations. The first stage of regularization consists in selecting a finite number of problems from this sequence. Each of the selected Dirichlet problems is formulated as an inverse problem Aq = f with respect to a direct (well-posed) problem. We derive formulas for singular values of the operator A in the case of constant coefficients and analyze their behavior to judge the degree of ill-posedness of the corresponding problem. The problem Aq = f on a uniform grid is reduced to a system of linear algebraic equations A _ll q = F. Using the singular value decomposition, we find singular values of the matrix A _ll and develop a numerical algorithm for constructing the r-solution of the original problem. This algorithm was tested on a discrete problem with relatively small number of grid nodes. To improve the calculated r-solution, we applied optimization but observed no noticeable changes. The results of computational experiments are illustrated.     

The necessity of Shishkin decompositions

In the present paper, we study model singularly perturbed convection-diffusion problems with exponential boundary layers. It has been believed for some time that only a complete splitting of the exact solution into regular and layer parts provides the information necessary for the study of the uniform convergence properties of numerical methods for these problems on layer-adapted grids (such as Shishkin meshes). In the present paper, we give new proofs of uniform interpolation error estimates for linear and bilinear interpolation; these proofs are based on the older a priori bounds derived by Kellogg and Tsan [1].     

The use of solutions on embedded grids for the approximation of singularly perturbed parabolic convection-diffusion equations on adapted grids

The Dirichlet problem on a closed interval for a parabolic convection-diffusion equation is considered. The higher order derivative is multiplied by a parameter ? taking arbitrary values in the semi-open interval (0, 1]. For the boundary value problem, a finite difference scheme on a posteriori adapted grids is constructed. The classical approximations of the equation on uniform grids in the main domain are used; in some subdomains, these grids are subjected to refinement to improve the grid solution. The subdomains in which the grid should be refined are determined using the difference of the grid solutions of intermediate problems solved on embedded grids. Special schemes on a posteriori piecewise uniform grids are constructed that make it possible to obtain approximate solutions that converge almost ?-uniformly, i.e., with an error that weakly depends on the parameter ?: |u(x, t) ? z(x, t)| ≤ M[N ₁ ^?1 ln² N ₁ + N ₀ ^?1 lnN ₀ + ?^?1 N ₁ ^?K ln ^K?1 N ₁], (x, t) ε ? _h , where N ₁ + 1 and N ₀ + 1 are the numbers of grid points in x and t, respectively; K is the number of refinement iterations (with respect to x) in the adapted grid; and M = M(K). Outside the σ-neighborhood of the outflow part of the boundary (in a neighborhood of the boundary layer), the scheme converges ?-uniformly at a rate O(N ₁ ^?1 ln² N ₁ + N ₀ ^?1 lnN ₀), where σ ≤ MN ₁ ^{?K + 1} ln ^K?1 N ₁ for K ≥ 2.