Search

In this paper quasi-Monte Carlo (QMC) methods are applied to a class of elliptic partial differential equations (PDEs) with random coefficients, where the random coefficient is parametrized by a countably infinite number of terms in a Karhunen--Loeve expansion. Models of this kind appear frequently in numerical models of physical systems, and in uncertainty quantification. The method uses a QMC method to estimate expected values of linear functionals of the exact or approximate solution of the PDE, with the expected value considered as an infinite dimensional integral in the parameter space corresponding to the randomness induced by the random coefficient. The error analysis, arguably the first rigorous application of the modern theory of QMC in weighted spaces, exploits the regularity with respect to both the physical variables (the variables in the physical domain) and the parametric variables (the parameters corresponding to randomness). In the weighted-space theory of QMC methods, "weights," describing the varying difficulty of different subsets of the variables, are introduced in order to make sure that the high-dimensional integration problem is tractable. It turns out that the weights arising from the present analysis are of a nonstandard kind, being of neither product nor order dependent form, but instead a hybrid of the two--we refer to these as "product and order dependent weights," or "POD weights" for short. These POD weights are of a simple enough form to permit a component-by-component construction of a randomly shifted lattice rule that has optimal convergence properties for the given weighted space setting. If the terms in the expansion for the random coefficient have an appropriate decay property, and if we choose POD weights that minimize a certain upper bound on the error, then the solution of the PDE belongs to the joint function space needed for the analysis, and the QMC error (in the sense of a root-mean-square error averaged over shifts) is of order O(N-1-δ) for arbitrary δ > 0, where N denotes the number of sampling points in the parameter space. Moreover, this convergence rate and slower convergence rates under more relaxed conditions are achieved under conditions similar to those found recently by Cohen, De Vore, and Schwab [Found. Comput. Math., 10 (2010), pp. 615-646] for the same model by best N-term approximation. We analyze the impact of a finite element (FE) discretization on the overall efficiency of the scheme, in terms of accuracy versus overall cost, with results that are comparable to those of the best N-term approximation. [ABSTRACT FROM AUTHOR]

This paper continues the convergence analysis in [M. Giles and S. Ulbrich, SIAM J. Numer. Anal., 48 (2010), pp. 882-904] of discrete approximations to the linearized and adjoint equations arising from an unsteady one-dimensional hyperbolic equation with a convex flux function. We consider a simple modified Lax-Friedrichs discretization on a uniform grid, and a key point is that the numerical smoothing increases the number of points across the nonlinear discontinuity as the grid is refined. It is proved that there is convergence in the discrete approximation of linearized output functionals even for Dirac initial perturbations and pointwise convergence almost everywhere for the solution of the adjoint discrete equations. In particular, the adjoint approximation converges to the correct uniform value in the region in which characteristics propagate into the discontinuity. Moreover, it is shown that the results of [M. Giles and S. Ulbrich, SIAM J. Numer. Anal., 48 (2010), pp. 882-904] and the present paper hold also for quite general nonlinear initial data which contain multiple shocks and for which shocks form at a later time and/or merge. [ABSTRACT FROM AUTHOR]

This paper studies a new recovery-based a posteriori error estimator for the conforming linear finite element approximation to elliptic interface problems. Instead of recovering the gradient in the continuous finite element space, the flux is recovered through a weighted L2 projection onto H(div) conforming finite element spaces. The resulting error estimator is analyzed by establishing the reliability and efficiency bounds and is supported by numerical results. This paper also proposes an adaptive finite element method based on either the recovery-based estimators or the edge estimator through local mesh refinement and establishes its convergence. In particular, it is shown that the reliability and efficiency constants as well as the convergence rate of the adaptive method are independent of the size of jumps. [ABSTRACT FROM AUTHOR]

Let F be a compact set of a Banach space X. This paper analyzes the "generalized empirical interpolation method," which, given a function f ∊ F, builds an interpolant Jn[f] in an n dimensional subspace Xn ⊂ X with the knowledge of n outputs (σi(f))ni=1, where σi ∊ X' and X' is the dual space of X. The space Xn is built with a greedy algorithm that is adapted to F in the sense that it is generated by elements of F itself. The algorithm also selects the linear functionals (σi)ni=1 from a dictionary Σ ⊂ X'. In this paper, we study the interpolation error maxf∊F ‖f - Jn[f]‖X by comparing it with the best possible performance on an n dimensional space, i.e., the Kolmogorov n-width of F in X, dn(F,X). For polynomial or exponential decay rates of dn(F,X), we prove that the interpolation error has the same behavior modulo the norm of the interpolation operator. Sharper results are obtained in the case where X is a Hilbert space. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the numerical solution of certain matrix-valued PDEs. Such PDEs arise, for example, when constructing a Riemannian contraction metric for a dynamical system given by an autonomous ODE. We develop and analyze a new meshfree discretization scheme using kernel-based approximation spaces. However, since these approximation spaces have now to be matrix-valued, the kernels we need to use are fourth-order tensors. We will review and extend recent results on even more general reproducing kernel Hilbert spaces. We will then apply this general theory to solve a matrix-valued PDE and derive error estimates for the approximate solution. The paper ends with applications to typical examples from dynamical systems. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of computing the effective diffusivity for a particle moving in chaotic and stochastic flows. In addition, we numerically investigate the residual diffusion phenomenon in chaotic advection. The residual diffusion refers to the nonzero effective (homogenized) diffusion in the limit of zero molecular diffusion as a result of chaotic mixing of the streamlines. In this limit, traditional numerical methods typically fail since the solutions of the advection-diffusion equations develop sharp gradients. Instead of solving the Fokker-Planck equation in the Eulerian formulation, we compute the motion of particles in the Lagrangian formulation, which is modeled by stochastic differential equations (SDEs). We propose an effective numerical integrator based on a splitting method to solve the corresponding SDEs in which the deterministic subproblem is symplectic preserving while the random subproblem can be viewed as a perturbation. We provide rigorous error analysis for the new numerical integrator using the backward error analysis technique and show that our method outperforms standard Euler-based integrators. Numerical results are presented to demonstrate the accuracy and efficiency of the proposed method for several typical chaotic and stochastic flow problems of physical interest. The existence of residual diffusivity for these flow problems is also investigated. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the damped stochastic nonlinear Schrödinger (NLS) equation with multiplicative noise and its splitting-based approximation. When the damped effect is large enough, we prove that the solutions of both the damped stochastic NLS equation and the splitting scheme are exponentially stable and possess some exponential integrability. These properties show that the strong order of the scheme is 1 and independent of time. Additionally, we analyze the regularity of the Kolmogorov equation with respect to the stochastic NLS equation. As a consequence, the weak order of the scheme is shown to be 1 and independent of time. [ABSTRACT FROM AUTHOR]

We propose a new discretization method for the Stokes equations. The method is an improved version of the method recently presented in [C. Lehrenfeld and J. Schöberl, Comp. Meth. Appl. Mech. Eng., 361 (2016)] which is based on an H(div)-conforming finite element space and a hybrid discontinuous Galerkin (HDG) formulation of the viscous forces. H(div)-conformity results in favorable properties such as pointwise divergence-free solutions and pressure robustness. However, for the approximation of the velocity with a polynomial degree k, it requires unknowns of degree k on every facet of the mesh. In view of the superconvergence property of other HDG methods, where only unknowns of polynomial degree k-1 on the facets are required to obtain an accurate polynomial approximation of order k (possibly after a local postprocessing), this is suboptimal. The key idea in this paper is to slightly relax the H(div)-conformity so that only unknowns of polynomial degree k-1 are involved for normal continuity. This allows for optimality of the method also in the sense of superconvergent HDG methods. In order not to lose the benefits of H(div)-conformity, we introduce a cheap reconstruction operator which restores pressure robustness and pointwise divergence-free solutions and suits well to the finite element space with relaxed H(div)-conformity. We present this new method, carry out a thorough h-version error analysis, and demonstrate the performance of the method on numerical examples. [ABSTRACT FROM AUTHOR]

In this paper, a numerical solution of partial differential equations on the unit sphere is given by using a kernel trial approximation in combination with a special Petrov-Galerkin test discretization. The solvability of the scheme is proved, and the error bounds are obtained for functions in appropriate Sobolev spaces. The condition number of the final system is estimated in terms of discretization parameters. The method is meshless because in the trial side the numerical solution parameterizes entirely in terms of scattered points and in the test side everything breaks down to simple numerical integrations over independent spherical caps. This means that no connected background mesh is required for either approximation or integration. [ABSTRACT FROM AUTHOR]

This paper focuses on the numerical analysis for three-dimensional Bean's critical-state model in type-II superconductivity. We derive hyperbolic mixed variational inequalities of the second kind for the evolution Maxwell equations with Bean's constitutive law between the electric Field and the current density. On the basis of the variational inequality in the magnetic induction formulation, a semidiscrete Ritz-Galerkin approximation problem is rigorously analyzed, and a strong convergence result is proven. Thereafter, we propose a concrete realization of the Ritz-Galerkin approximation through a mixed Finite element method based on edge elements of Nédélec's First family, Raviart-Thomas face elements, divergence-free Raviart-Thomas face elements, and piecewise constant elements. As a Final result, we prove error estimates for the proposed mixed Finite element method. [ABSTRACT FROM AUTHOR]

This paper derives a posteriori error estimates for conforming numerical approximations of the Laplace eigenvalue problem with a homogeneous Dirichlet boundary condition. In particular, upper and lower bounds for an arbitrary simple eigenvalue are given. These bounds are guaranteed, fully computable, and converge with optimal speed to the given exact eigenvalue. They are valid without restrictions on the computational mesh or on the approximate eigenvector; we only need to assume that the approximate eigenvalue is separated from the surrounding smaller and larger exact ones, which can be checked in practice. Guaranteed, fully computable, optimally convergent, and polynomial-degree robust bounds on the energy error in the approximation of the associated eigenvector are derived as well, under the same hyp otheses. Remarkably, there appears no unknown (solution-, regularity-, or polynomial-degree-dependent) constant in our theory, and no convexity/regularity assumption on the computational domain/exact eigenvector(s) is needed. The multiplicative constant appearing in our estimates depends on (computable estimates of) the gaps to the surrounding exact eigenvalues. Its two improvements are presented. First, it is reduced by a fixed factor under an explicit, a posteriori calculable condition on the mesh and on the approximate eigenvector--eigenvalue pair. Second, when an elliptic regularity assumption on the corresponding source problem is satisfied with known constants, this multiplicative constant can be brought to the optimal value of one. Inexact algebraic solvers are taken into account; the estimates are valid on each iteration and can serve for the design of adaptive stopping criter ia. The application of our framework to conforming finite element approximations of arbitrary polynomial degree is provided, along with a numerical illustration on a set of test problems. [ABSTRACT FROM AUTHOR]

The present paper is concerned with the unilateral contact model in linear elastostatics, the so-called Signorini problem. (Our results can also be applied to the scalar Signorini problem.) A standard continuous linear finite element approximation is first chosen to approach the two-dimensional problem. We develop a new error analysis in the H¹-norm using estimates on Poincaré constants with respect to the size of the areas of the noncontact sets. In particular we do not assume any additional hypothesis on the finiteness of the set of transition points between contact and noncontact. This approach allows us to establish better error bounds under sole Hτ assumptions on the solution: if 3/2 < τ < 2 we improve the existing rate by a factor h(τ-3/2)² and if τ = 2 the existing rate (h¾) is improved by a new rate of h √"ln(h)|. Using the same finite element spaces as previously we then consider another discrete approximation of the (nonlinear) contact condition in which the same kind of analysis leads to the same convergence rates as for the first approximation. [ABSTRACT FROM AUTHOR]

This paper is devoted to the numerical approximation of Lyapunov and Sacker-Sell Spectral intervals for linear differential-algebraic equations (DAEs). The spectral analysis for DAEs is improved and the concepts of leading directions and solution subspaces associated with spectral intervals are extended to DAEs. Numerical methods based on smooth singular value decompositions are introduced for Computing all or only some spectral intervals and their associated leading directions. The numerical algorithms as well as implementation issues are discussed in detail and Numerical examples are presented to illustrate the theoretical results. [ABSTRACT FROM AUTHOR]

This paper analyzes the convergence of discrete approximations to the linearized equations arising from an unsteady one-dimensional hyperbolic equation with a convex flux function. A simple modified Lax-Friedrichs discretization is used on a uniform grid, and a key point is that the numerical smoothing increases the number of points across the nonlinear discontinuity as the grid is refined. It is proved that this gives pointwise convergence almost everywhere for the solution to the linearized discrete equations with smooth initial data, and also convergence in the discrete approximation of linearized output functionals. In Part 2 [M. Giles and S. Ulbrich, SIAM J. Numer. Anal., 48 (2010), pp. 905-921] we extend the results to Dirac initial data for the linearized equation and will prove the pointwise convergence almost everywhere for the solution of the adjoint discrete equations. In addition, we present numerical results illustrating the asymptotic behavior which is analyzed. [ABSTRACT FROM AUTHOR]

The stress-displacement-pressure formulation of the elasticity problem may suffer from two types of numerical instabilities related to the finite element interpolation of the unknowns. The first is the classical pressure instability that occurs when the solid is incompressible, whereas the second is the lack of stability in the stresses. To overcome these instabilities, there are two options. The first is to use different interpolation for all the unknowns satisfying two inf-sup conditions. Whereas there are several displacement-pressure interpolations that render the pressure stable, less possibilities are known for the stress interpolation. The second option is to use a stabilized finite element formulation instead of the plain Galerkin approach. If this formulation is properly designed, it is possible to use arbitrary interpolation for all the unknowns. The purpose of this paper is precisely to present one of such formulations. In particular, it is based on the decomposition of the unknowns into their finite element component and a subscale, which will be approximated and whose goal is to yield a stable formulation. A singular feature of the method to be presented is that the subscales will be considered orthogonal to the finite element space. We describe the design of the formulation and present the results of its numerical analysis. [ABSTRACT FROM AUTHOR]

This paper develops and analyzes some fully discrete finite element methods for a parabolic system consisting of the Navier-Stokes equations and the Cahn-Hilliard equation, which arises as a diffuse interface model for the flow of two immiscible and incompressible fluids. In the model the two sets of equations are coupled through an extra phase induced stress term in the Navier-Stokes equations and a fluid induced transport term in the Cahn-Hilliard equation. Fully discrete mixed finite element methods are proposed for approximating the coupled system, it is shown that the proposed numerical methods satisfy a mass conservation law, and a discrete energy law which is analogous to the basic energy law for the phase field model. The convergence of the numerical solutions to the solutions of the phase field model and its sharp interface limit is established by utilizing the discrete energy law. As a by-product, the convergence result also provides a constructive proof of the existence of weak solutions to the Navier-Stokes-Cahn-Hilliard phase field model. Numerical experiments are also presented to validate the theory and to show the effectiveness of the combined phase field and finite element approach. [ABSTRACT FROM AUTHOR]

In this paper we establish an explicit asymptotic formula for the steady state voltage perturbations caused by closely spaced small conductivity inhomogeneities. Based on this new formula we design a very effective numerical method to identify the location and some geometric features of these inhomogeneities from a finite number of boundary measurements. The viability of our approach is documented by numerical examples. [ABSTRACT FROM AUTHOR]

In this paper discontinuous Galerkin methods with penalty for solving second-order elliptic problems are considered. Error estimates are studied for these methods. In particular, optimal localized pointwise error estimates are established on quasi-uniform grids in RN (N ≥ 2). [ABSTRACT FROM AUTHOR]

This paper deals with the numerical approximation of the bending of a plate modeled by Reissner-Mindlin equations. It is well known that, in order to avoid locking, some kind of reduced integration or mixed interpolation has to be used when solving these equations by finite element methods. In particular, one of the most widely used procedures is based on the family of elements called MITC (mixed interpolation of tensorial components). We consider two lowest-order methods of this family on quadrilateral meshes. Under mild assumptions we obtain optimal H¹ and L² error estimates for both methods. These estimates are valid with constants independent of the plate thickness. We also obtain error estimates for the approximation of the plate vibration problem. Finally, we report some numerical experiments showing the very good behavior of the methods, even in some cases not covered by our theory. [ABSTRACT FROM AUTHOR]

In this paper we show that the use of spectral Galerkin methods for the approximation of the Boltzmann equation in the velocity space permits one to obtain spectrally accurate numerical solutions at a reduced computational cost. We prove that the spectral algorithm preserves the total mass and approximates with infinite-order accuracy momentum and energy. Consistency of the method is also proved, and a stability result for a smoothed positive scheme is given. We demonstrate that the Fourier coefficients associated with the collision kernel of the equation have a very simple structure and in some cases can be computed explicitly. Numerical examples for homogeneous test problems in two and three dimensions confirm the advantages of the method. [ABSTRACT FROM AUTHOR]

In this paper we construct an "interior penalty" discontinuous Galerkin method to approximate the minimizer of a variational problem related to the p(x)-Laplacian. The function p : Ω → [p1,p2] is log-Hölder continuous and 1 < p1 ≤ p2 < ∞. We prove that the minimizers of the discrete functional converge to the solution. We also make some numerical experiments in dimension one to compare this method with the conforming Galerkin method, in the case where p1 is close to one. This example is motivated by its applications to image processing. [ABSTRACT FROM AUTHOR]

In this paper we present PDE and finite element analyses for a system of PDEs consisting of the Darcy equation and the Cahn--Hilliard equation, which arises as a diffuse interface model for the two-phase Hele-Shaw flow. In the model the two sets of equations are coupled through an extra phase induced force term in the Darcy equations and a fluid induced transport term in the Cahn--Hilliard equation. We propose a fully discrete implicit finite element method for approximating the PDE system, which consists of the implicit Euler method combined with a convex splitting energy strategy for the temporal discretization, the standard finite element discretization for the pressure, and a split (or mixed) finite element discretization for the fourth-order Cahn--Hilliard equation. It is shown that the proposed numerical method satisfies a mass conservation law in addition to a discrete energy law that mimics the basic energy law for the Darcy--Cahn--Hilliard phase field model and holds uniformly in the phase field parameter ε. With the help of the discrete energy law, we first prove that the fully discrete finite method is unconditionally energy stable and uniquely solvable at each time step. We then show that, using the compactness method, the finite element solution has an accumulation point that is a weak solution of the PDE system. As a result, the convergence result also provides a constructive proof of the existence of global-in-time weak solutions to the Darcy--Cahn--Hilliard phase field model in both two and three dimensions. Numerical experiments based on the overall solution method of combining the proposed finite element discretization and a nonlinear multigrid solver are presented to validate the theoretical results and to show the effectiveness of the proposed fully discrete finite element method for approximating the Darcy--Cahn--Hilliard phase field model. [ABSTRACT FROM AUTHOR]

This paper deals with the approximation of the eigenvalues of evolution operators for linear retarded functional differential equations through the reduction to finite dimensional operators by a pseudospectral collocation. Fundamental applications such as determination of asymptotic stability of equilibria and periodic solutions of nonlinear autonomous retarded functional differential equations follow at once. Numerical tests are provided. [ABSTRACT FROM AUTHOR]

In this paper we study numerical approximations of continuous solutions to the nonlocal p-Laplacian type diffusion equation, ut(t, x) = ∫Ω J(x - y)|u(t, y) - u(t, x)|p-2(u(t, y) - u(t,x)) dy. First, we find that a semidiscretization ill space of this problem gives rise to an ODE system whose solutions converge uniformly to the continuous one as the mesh size goes to zero. Moreover, the semidiscrete approximation shares some properties of the continuous problem: it preserves the total mass and the solution converges to the mean value of the initial condition as t goes to infinity. Next, we also discretize the time variable and present a totally discrete method which also enjoys the above mentioned properties. In addition, we investigate the limit as p goes to infinity in these approximations and obtain a discrete model for the evolution of a sandpile. Finally, we present some numerical experiments that illustrate our results. [ABSTRACT FROM AUTHOR]

This paper investigates backscatter data for the inverse obstacle problem in impedance tomography, when the obstacles are small. It is shown that under this circumstance the backscatter data are close approximations of a rational function that has second or fourth order poles at the locations of the obstacles. Furthermore, a numerical method is presented to locate the obstacles via the poles of certain Laurent-Padé approximations. Numerical experiments explore the potential of this algorithm also for extended obstacles, taking into consideration that the problem is severely ill-posed. [ABSTRACT FROM AUTHOR]

This paper deals with the approximation of the buckling coefficients and modes of a clamped plate modeled by the Reissner-Mindlin equations. These coefficients are the reciprocals of the eigenvalues of a noncompact operator. We give a spectral characterization of this operator and show that the relevant buckling coefficients correspond to isolated nondefective eigenvalues. Then we consider the numerical computation of these coefficients and their corresponding modes. For the finite element approximation of Reissner-Mindlin equations, it is well known that some kind of reduced integration or mixed interpolation has to be used to avoid locking. In particular we consider Durán- Liberman elements, which have been already proved to be locking-free for load and vibration problems. We adapt the classical approximation theory for noncompact operators to obtain optimal order error estimates for the eigenfunctions and a double order for the eigenvalues. These estimates are valid with constants independent of the plate thickness. We report some numerical experiments confirming the theoretical results. Finally, we refine the analysis in the case of a uniformly compressed plate. [ABSTRACT FROM AUTHOR]

Low-order Whitney elements are widely used for electromagnetic field problems. Higher-order approximations are receiving increasing interest, but their definition remains unduly complex. In this paper we propose a new simple construction for Whitney p-elements of polynomial degree higher than one that use only degrees of freedom associated to p-chains. We provide a basis for these elements on simplicial meshes and give a geometrical localization of all degrees of freedom. Properties of the higher-order Whitney complex are deeply investigated. [ABSTRACT FROM AUTHOR]

Many semi-Lagrangian schemes for solving the Vlasov equation use a second order time splitting method proposed by Cheng and Knorr. In this paper a fourth order time splitting method is proposed. This is combined with cubic spline interpolation (in x and v), and a rigorous ℓ2 error bound is obtained for the linear Vlasov equation in arbitrary space dimension. Also, this method and that of Cheng and Knorr are implemented and compared for a test case in one space dimension. [ABSTRACT FROM AUTHOR]

In this paper we propose stabilized finite element methods for both Stokes' and Darcy's problems that accommodate any interpolation of velocities and pressures. Apart from the interest of this fact, the important issue is that we are able to deal with both problems at the same time, in a completely unified manner, in spite of the fact that the functional setting is different. Concerning the stabilization formulation, we discuss the effect of the choice of the length scale appearing in the expression of the stabilization parameters, both in what refers to stability and to accuracy. This choice is shown to be crucial in the case of Darcy's problem. As an additional feature of this work, we treat two types of stabilized formulations, showing that they have a very similar behavior. [ABSTRACT FROM AUTHOR]

In this paper, we consider a variable-order fractional advection-diffusion equation with a nonlinear source term on a finite domain. Explicit and implicit Euler approximations for the equation are proposed. Stability and convergence of the methods are discussed. Moveover, we also present a fractional method of lines, a matrix transfer technique, and an extrapolation method for the equation. Some numerical examples are given, and the results demonstrate the effectiveness of theoretical analysis. [ABSTRACT FROM AUTHOR]

The paper deals with stochastic partial differential equations driven by Poisson random measures of jump type and their numerical approximation. We investigate the accuracy of space and time approximation. As space approximation we consider finite elements and as time approximation the implicit Euler scheme. [ABSTRACT FROM AUTHOR]

In many applications, materials are modeled by a large number of particles (or atoms), where any particle can interact with any other. The computational cost is very high since the number of atoms is huge. Recently much attention has been paid to a so-called quasi-continuum (QC) method, which is a mixed atomistic/continuum model. The QC method uses an adaptive finite element framework to effectively integrate the majority of the atomistic degrees of freedom in regions where there is no serious defect. However, numerical analysis of this method is still in its infancy. In this paper we will conduct a convergence analysis of the QC method in the case when there is no defect. We will also remark on the case when the defect region is small. The difference between our analysis and conventional analysis is that our exact atomistic solution is not a solution of a continuous partial differential equation, but a discrete lattice scale solution which is not approximately related to any conventional partial differential equation. [ABSTRACT FROM AUTHOR]

In this paper we analyze the approximation by standard piecewise linear finite elements of a nonhomogeneous Neumann problem in a cuspidal domain. Since the domain is not Lipschitz, many of the results on Sobolev spaces, which are fundamental in the usual error analysis, do not apply. Therefore, we need to work with weighted Sobolev spaces and to develop some new theorems on traces and extensions. We show that, in the domain considered here, suboptimal order can be obtained with quasi-uniform meshes even when the exact solution is in H², and we prove that the optimal order with respect to the number of nodes can be recovered by using appropriate graded meshes. [ABSTRACT FROM AUTHOR]

The goal of this paper is to provide a theoretical framework allowing one to extend some general concepts related to the numerical approximation of 1-d conservation laws to the more general case of first order quasi-linear hyperbolic systems. In particular this framework is intended to be useful for the design and analysis of well-balanced numerical schemes for solving balance laws or coupled systems of conservation laws. First, the concept of path-conservative numerical schemes is introduced, which is a generalization of the concept of conservative schemes for systems of conservation laws. Then, we introduce the general definition of approximate Riemann solvers and give the general expression of some well-known families of schemes based on these solvers: Godunov, Roe, and relaxation methods. Finally, the general form of a high order scheme based on a first order path-conservative scheme and a reconstruction operator is presented. [ABSTRACT FROM AUTHOR]

We study in this paper a finite volume approximation of linear convection-diffusion equations defined on a sphere using the spherical Voronoi meshes, in particular the spherical centroidal Voronoi meshes. The high quality of spherical centroidal Voronoi meshes is illustrated through both theoretical analysis and computational experiments. In particular, we show that the L2 error of the approximate solution is of quadratic order when the underlying mesh is given by a spherical centroidal Voronoi mesh. We also demonstrate numerically the high accuracy and the superconvergence of the approximate solutions. [ABSTRACT FROM AUTHOR]

This paper presents the natural framework to residual based a posteriori error estimation of some cell-centered finite volume methods for the Laplace equation in $\R^d, d=2$ or 3. For that purpose we associate with the finite volume solution a reconstructed approximation, which is a kind of Morley interpolant. The error is then the difference between the exact solution and this Morley interpolant. The residual error estimator is based on the jump of normal and tangential derivatives of the Morley interpolant. We then prove the equivalence between the discrete H1 seminorm of the error and the residual error estimator. Numerical tests confirm our theoretical results. [ABSTRACT FROM AUTHOR]

A complete error analysis is performed for the spectral-Galerkin approximation of a model Helmholtz equation with high wave numbers. The analysis presented in this paper does not rely on the explicit knowledge of continuous/discrete Green's functions and does not require any mesh condition to be satisfied. Furthermore, new error estimates are also established for multi-dimensional radial and spherical symmetric domains. Illustrative numerical results in agreement with the theoretical analysis are presented. [ABSTRACT FROM AUTHOR]

This paper provides approximation orders for a class of nonlinear interpolation procedures for uniformly sampled univariate data. The interpolation is based on essentially nonoscillatory (ENO) and subcell resolution (SR) reconstruction techniques. These nonlinear techniques aim at reducing significantly the approximation error for functions with isolated singularities and are therefore attractive for applications such as shock computations or image compression. We prove that in the presence of isolated singularities, the approximation order provided by the interpolation procedure is improved by a factor of $h$ relative to the linear methods, where h is the sampling rate. Moreover, for h below a critical value, we recover the optimal approximation order as for uniformly smooth functions. [ABSTRACT FROM AUTHOR]

In this paper, we attempt to reveal the precise relation between the error of linear interpolation on a general triangle and the geometric characters of the triangle. Taking the model problem of interpolating quadratic functions, we derive two exact formulas for the $H^1$-seminorm and $L^2$-norm of the interpolation error in terms of the area, aspect ratio, orientation, and internal angles of the triangle. These formulas indicate that (1) for highly anisotropic triangular meshes the $H^1$-seminorm of the interpolation error is almost a monotonically decreasing function of the angle between the orientations of the triangle and the function; (2) maximum angle condition is not essential if the mesh is aligned with the function and the aspect ratio is of magnitude $\sqrt{|\lambda_1/\lambda_2|}$ or less, where $\lambda_1$ and $\lambda_2$ are the eigenvalues of the Hessian matrix of the function. With these formulas we identify the optimal triangles, which produce the smallest $H^1$-seminorm of the interpolation error, to be the acute isosceles aligned with the solution and of an aspect ratio about $0.8 |\frac{\lambda_1}{\lambda_2}|$. The $L^2$-norm of the interpolation error depends on the orientation and the aspect ratio of the triangle, but not directly on its maximum or minimum angles. The optimal triangles for the $L^2$-norm are those aligned with the solution and of an aspect ratio $\sqrt{|\lambda_1/\lambda_2|}$. These formulas can be used to formulate more accurate mesh quality measures and to derive tighter error bounds for interpolations. [ABSTRACT FROM AUTHOR]

This paper deals with the finite element approximation of evolution problems in mixed form. Following [D. Boffi, F. Brezzi, and L. Gastaldi, Math. Comp., 69 (2000), pp. 121-140], we handle separately two types of problems. A model for the first case is the heat equation in mixed form, while the time dependent Stokes problem fits within the second one. For either case, we give sufficient conditions for a good approximation in the natural functional spaces. The results are not obvious in the first situation. In this case, the well-known conditions for the well posedness and convergence of the corresponding steady problem are not sufficient for the good approximation of the time dependent problem. This issue is demonstrated with a numerical (counter-) example and justified analytically. [ABSTRACT FROM AUTHOR]

In this paper we propose and analyze a finite element scheme for a class of variational nonlinear and nondifferentiable mixed inequalities including balance equations governing incompressible creeping flows of Bingham fluids. For numerical efficiency reasons, equal-order piecewise linear approximations are used for both velocity and pressure, and the numerical scheme is stabilized by a Brezzi-Pitkäranta perturbation term. We obtain error estimates of the same order as for stable discretizations, namely h½ for velocity and pressure solutions in [H²(Ω)]d and H¹(Ω), respectively. A decomposition-coordination algorithm to solve the discrete nonlinear algebraic system is presented, together with its convergence properties. Finally, numerical tests are performed. The solution of the problem under consideration presents particular regularity properties that are shown to permit convergence order improvement to h¦log(h)¦½. This estimate is confirmed by numerical results. [ABSTRACT FROM AUTHOR]

In this paper, geometric interpolation by parametric polynomial curves is considered. Discussion is focused on the case where the number of interpolated points is equal to r + 2, and n = r denotes the degree of the interpolating polynomial curve. The interpolation takes place in Rd with d = n. Even though the problem is nonlinear, simple necessary and sufficient conditions for existence of the solution are stated. These conditions are entirely geometric and do not depend on the asymptotic analysis. Furthermore, they provide an efficient and stable way to the numeric solution of the problem. [ABSTRACT FROM AUTHOR]

Replacing the median by a general M-estimator, we construct in this paper a host of variants of the robust nonlinear pyramid transforms proposed by Donoho and Yu [SIAM J. Math. Anal., 31 (2000) pp. 1030-1061]. Some of these new variants are more amenable to numerical implementations with provable properties when compared to the Donoho-Yu median-based pyramid transforms. At the crux of this generalized construction is the following result: the inverse problem of interpolating a univariate polynomial of degree n with n + 1 prescribed values for any given continuous M-estimator on n + 1 nonoverlapping intervals is a well-posed procedure. While the proof of this result is nonconstructive, we study the use of Newton methods for constructing such a polynomial interpolant and report numerical results in some test cases. [ABSTRACT FROM AUTHOR]

The fast multipole methods are used for solving a scalar acoustic or vector electromagnetic wave equation by integral equation methods with a large number of unknowns. In this paper a new method is presented for performing interpolation and anterpolation in both spherical coordinates θ and φ by FFT in the three-dimensional (3-D) multilevel fast multipole algorithm (MLFMA). The key idea is to approximate functions on the unit sphere by truncated Fourier series in two variables rather than by the usual spherical harmonics. The proposed method is exact in interpolating and anterpolating and has the high numerical efficiency of FFT. The method is numerically compared to the method of performing interpolation and anterpolation using Lagrangian interpolation, which presently is probably the fastest method for those operations, and the results suggest that the proposed new method is equally or more efficient, depending on the desired accuracy. [ABSTRACT FROM AUTHOR]

It has been long recognized that the determination of optimal parameters for the classical alternating direction implicit (ADI) method leads to the Zolotarev problem [This symbol cannot be presented in ASCII format] for disjoint compact sets E,F ⊆ C, where Rnn is the collection of rational functions of order n. In the case where E and F are real intervals, it was more recently pointed out that if they have different lengths, it is of interest to generalize the foregoing problem to the set Rmn with unequal numerator degree m and denominator degree n. The object of the paper is to investigate the generalized Zolotarev problem in the complex plane. A method is proposed to construct the optimal rational function, which is then applied to the particular example of two line segments—E on the real axis, F parallel to the imaginary axis. Numerical experiments show that the improvement on the classical solution may be amazingly great. Explicit expressions are also provided for special values of data. [ABSTRACT FROM AUTHOR]

Convergence is established for a scalar finite difference scheme, based on the Godunov or Engquist­Osher (EO) flux, for scalar conservation laws having a flux that is spatially dependent through a possibly discontinuous coefficient. Other works in this direction have established convergence for methods employing the solution of 2 × 2 Riemann problems. The algorithm discussed here uses only scalar Riemann solvers. Satisfaction of a set of Kruzkov-type entropy inequalities is established for the limit solution, from which geometric entropy conditions follow. Assuming a piecewise constant coefficient, it is shown that these conditions imply L¹-contractiveness for piecewise C¹ solutions, thus extending a well-known theorem. [ABSTRACT FROM AUTHOR]

In this paper we present error estimates for the finite element approximation of linear elliptic problems in unbounded domains that are outside an obstacle and a semi-infinite strip in the plane. The finite element approximation is formulated on a bounded domain using a nonlocal approximate artificial boundary condition. In fact there is a family of approximate boundary conditions with increasing accuracy (and computational cost) for a given artificial boundary. Our error estimates are based on the mesh size, the terms used in the approximate artificial boundary condition, and the location of the artificial boundary. Numerical examples for Poisson's problem outside a circle and in a semi-infinite strip are presented. Numerical results demonstrate the performance of our error estimates. [ABSTRACT FROM AUTHOR]

In this paper we present the construction and study the properties of a new parametric cubic element having tension properties. The element is based on the Clough­Tocher split of a given triangle. Due to its tension properties the element can be used to obtain a local interpolation scheme for scattered data. [ABSTRACT FROM AUTHOR]