A note on the discrete approximation of discontinuous curves and surfaces

This is a note on the paper [A. Kouibia, A.J. López-Linares, M. Pasadas, Approximation of discontinuous curves and surfaces with tangent conditions, J. Comput. Appl. Math. 193 (2006) 51–64]. We consider the constructing problem of a discontinuous parametric curve or surface from a finite set of points and tangent conditions. We develop a method based on the theory of discrete smoothing variational splines conveniently adapted to introduce the tangent conditions and the discontinuity set. We give a convergence result and we analyze some numerical and graphical examples in order to illustrate the effectiveness of the presented method.     

Multivariate approximation by PDE splines

This work deals with an approximation method for multivariate functions from data constituted by a given data point set and a partial differential equation (PDE). The solution of our problem is called a PDE spline. We establish a variational characterization of the PDE spline and a convergence result of it to the function which the data are obtained. We estimate the order of the approximation error and finally, we present an example to illustrate the fitting method.     

Error estimates in W 2,∞-semi-norms for discrete interpolating D 2-splines

We derive error estimates in W^2,∞-semi-norms for multivariate discrete D²-splines that interpolate an unknown function at the vertices of given triangulations. These results are widely based on the construction of approximation operators and linear projectors onto piecewise polynomial spaces having weakly stable local bases.     

Quasi-interpolation for linear functional data

Quasi-interpolation has been studied extensively in the literature. However, most studies of quasi-interpolation are usually only for discrete function values (or a finite linear combination of discrete function values). Note that in practical applications, more commonly, we can sample the linear functional data (the discrete values of the right-hand side of some differential equations) rather than the discrete function values (e.g., remote sensing, seismic data, etc). Therefore, it is more meaningful to study quasi-interpolation for the linear functional data. The main result of this paper is to propose such a quasi-interpolation scheme. Error estimate of the scheme is also given in the paper. Based on the error estimate, one can find a quasi-interpolant that provides an optimal approximation order with respect to the smoothness of the right-hand side of the differential equation. The scheme can be applied in many situations such as the numerical solution of the differential equation, construction of the Lyapunov function and so on. Respective examples are presented in the end of this paper.     

Sur le choix du paramètre d'ajustement dans le lissage par fonctions spline

Summary We consider the problem of approximating an unknown functionf, known with error atn equally spaced points of the real interval [a, b].To solve this problem, we use the natural polynomial smoothing splines. We show that the eigenvalues associated to these splines converge to the eigenvalues of a differential operator and we use this fact to obtain an algorithm, based on the Generalized Cross Validation method, to calculate the smoothing parameter.With this algorithm, we divide byn the time used by classical methods.

     

Approximation by smoothing variational vector splines for noisy data

This paper addresses the problem of constructing some free-form curves and surfaces from given to different types of data: exact and noisy data. We extend the theory of D^m${\mathrm{D}}^m$-splines over a bounded domain for noisy data to the smoothing variational vector splines. Both results of convergence for respectively the exact and noisy data are established, as soon as some estimations of errors are given.     

A penalty continuation method for the ∓∞ solution of overdetermined linear systems

A new algorithm for the ∓_∞ solution of overdetermined linear systems is given. The algorithm is based on the application of quadratic penalty functions to a primal linear programming formulation of the ∓_∞ problem. The minimizers of the quadratic penalty function generate piecewise-linear non-interior paths to the set of ∓_∞ solutions. It is shown that the entire set of ∓_∞ solutions is obtained from the paths for sufficiently small values of a scalar parameter. This leads to a finite penalty/continuation algorithm for ∓_∞ problems. The algorithm is implemented and extensively tested using random and function approximation problems. Comparisons with the Barrodale-Phillips simplex based algorithm and the more recent predictor-corrector primal-dual interior point algorithm are given. The results indicate that the new algorithm shows a promising performance on random (non-function approximation) problems.     

Convergence rates to discrete shocks for nonconvex conservation laws

Summary. This paper is concerned with polynomial decay rates of perturbations to stationary discrete shocks for the Lax-Friedrichs scheme approximating non-convex scalar conservation laws. We assume that the discrete initial data tend to constant states as , respectively, and that the Riemann problem for the corresponding hyperbolic equation admits a stationary shock wave. If the summation of the initial perturbation over is small and decays with an algebraic rate as , then the perturbations to discrete shocks are shown to decay with the corresponding rate as . The proof is given by applying weighted energy estimates. A discrete weight function, which depends on the space-time variables for the decay rate and the state of the discrete shocks in order to treat the non-convexity, plays a crucial role. Received November 25, 1998 / Published online November 8, 2000     

An algorithm for smoothing,differentiation and integration of experimental data using spline functions

This paper presents an algorithm for fitting a smoothing spline function to a set of experimental or tabulated data. The obtained spline approximation can be used for differentiation and integration of the given discrete function. Because of the ease of computation and the good conditioning properties we use normalised B-splines to represent the smoothing spline. A Fortran implementation of the algorithm is given.     

Computation of the Riesz-Herglotz transform and its application to quadrature formulas over the unit circle

Summary A method is proposed for the computation of the Riesz-Herglotz transform. Numerical experiments show the effectiveness of this method. We study its application to the computation of integrals over the unit circle in the complex plane of analytic functions. This approach leads us to the integration by Taylor polynomials. On the other hand, with the goal of minimizing the quadrature error bound for analytic functions, in the set of quadrature formulas of Hermite interpolatory type, we found that this minimum is attained by the quadrature formula based on the integration of the Taylor polynomial. These two different approaches suggest the effectiveness of this formula. Numerical experiments comparing with other quadrature methods with the same domain of validity, or even greater such as Szeg? formulas, (traditionally considered as the counterpart of the Gauss formulas for integrals on the unit circle) confirm the superiority of the numerical estimations. This work was supported by the ministry of education and culture of Spain under contract PB96-1029.     

Progressive stable interpolation

In this paper, we study several interpolating and smoothing methods for data which are known “progressively”. The algorithms proposed are governed by recurrence relations and our principal goal is to study their stability. A recurrence relation will be said stable if the spectral radius of the associated matrix is less than one. The iteration matrices depend on shape parameters which come either from the connection at the knots, or from the nature of the interpolant between two knots. We obtain various stability domains. Moving the parameters inside these domains leads to interesting shape effects. This revised version was published online in June 2006 with corrections to the Cover Date.     

On near-best discrete quasi-interpolation on a four-directional mesh

Spline quasi-interpolants are practical and effective approximation operators. In this paper, we construct QIs with optimal approximation orders and small infinity norms called near-best discrete quasi-interpolants which are based on Ω-splines, i.e. B-splines with octagonal supports on the uniform four-directional mesh of the plane. These quasi-interpolants are exact on some space of polynomials and they minimize an upper bound of their infinity norms depending on a finite number of free parameters. We show that this problem has always a solution, in general nonunique. Concrete examples of such quasi-interpolants are given in the last section.     

On the effect of numerical integration in the Galerkin boundary element method

Summary. We discuss the effect of cubature errors when using the Galerkin method for approximating the solution of Fredholm integral equations in three dimensions. The accuracy of the cubature method has to be chosen such that the error resulting from this further discretization does not increase the asymptotic discretization error. We will show that the asymptotic accuracy is not influenced provided that polynomials of a certain degree are integrated exactly by the cubature method. This is done by applying the Bramble-Hilbert Lemma to the boundary element method. Received May 24, 1995     

An axiomatic approach to scalar data interpolation on surfaces

We discuss possible algorithms for interpolating data given on a set of curves in a surface of ℝ³. We propose a set of basic assumptions to be satisfied by the interpolation algorithms which lead to a set of models in terms of possibly degenerate elliptic partial differential equations. The Absolutely Minimizing Lipschitz Extension model (AMLE) is singled out and studied in more detail. We study the correctness of our numerical approach and we show experiments illustrating the interpolation of data on some simple test surfaces like the sphere and the torus.     

A finite difference analysis of a streamline diffusion method on a Shishkin mesh

We consider streamline diffusion finite element methods applied to a singularly perturbed convection–diffusion two‐point boundary value problem whose solution has a single boundary layer. To analyse the convergence of these methods, we rewrite them as finite difference schemes. We first consider arbitrary meshes, then, in analysing the scheme on a Shishkin mesh, we consider two formulations on the fine part of the mesh: the usual streamline diffusion upwinding and the standard Galerkin method. The error estimates are given in the discrete L _∞ norm; in particular we give the first analysis that shows precisely how the error depends on the user-chosen parameter _τ0 specifying the mesh. When _τ0 is too small, the error becomes O(1), but for _τ0 above a certain threshold value, the error is small and increases either linearly or quadratically as a function of . Numerical tests support our theoretical results. This revised version was published online in August 2006 with corrections to the Cover Date.     

Pseudo-polyharmonic vectorial approximation for div-curl and elastic semi-norms

Vector field reconstruction is a problem arising in many scientific applications. In this paper, we study a div-curl approximation of vector fields by pseudo-polyharmonic splines. This leads to the variational smoothing and interpolating spline problems with minimization of an energy involving the curl and the divergence of the vector field. The relationship between the div-curl energy and elastic energy is established. Some examples are given to illustrate the effectiveness of our approach for a vector field reconstruction.     

An interpolation matched interface and boundary method for elliptic interface problems

An interpolation matched interface and boundary (IMIB) method with second-order accuracy is developed for elliptic interface problems on Cartesian grids, based on original MIB method proposed by Zhou et al. [Y. Zhou, G. Wei, On the fictious-domain and interpolation formulations of the matched interface and boundary method, J. Comput. Phys. 219 (2006) 228-246]. Explicit and symmetric finite difference formulas at irregular grid points are derived by virtue of the level set function. The difference scheme using IMIB method is shown to satisfy the discrete maximum principle for a certain class of problems. Rigorous error analyses are given for the IMIB method applied to one-dimensional (1D) problems with piecewise constant coefficients and two-dimensional (2D) problems with singular sources. Comparison functions are constructed to obtain a sharp error bound for 1D approximate solutions. Furthermore, we compare the ghost fluid method (GFM), immersed interface method (IIM), MIB and IMIB methods for 1D problems. Finally, numerical examples are provided to show the efficiency and robustness of the proposed method.     

A cascadic multigrid algorithm for semilinear elliptic problems

Summary. We propose a cascadic multigrid algorithm for a semilinear elliptic problem. The nonlinear equations arising from linear finite element discretizations are solved by Newton's method. Given an approximate solution on the coarsest grid on each finer grid we perform exactly one Newton step taking the approximate solution from the previous grid as initial guess. The Newton systems are solved iteratively by an appropriate smoothing method. We prove that the algorithm yields an approximate solution within the discretization error on the finest grid provided that the start approximation is sufficiently accurate and that the initial grid size is sufficiently small. Moreover, we show that the method has multigrid complexity. Received February 12, 1998 / Revised version received July 22, 1999 / Published online June 8, 2000     

Improved estimates of statistical regularization parameters in fourier differentiation and smoothing

Summary We investigate the statistical methods of cross-validation (CV) and maximum-likelihood (ML) for estimating optimal regularization parameters in the numerical differentiation and smoothing of non-exact data. Various criteria for optimality are examined, and the (asymptotic) notions of strong optimality, weak optimality and suboptimality are introduced relative to these criteria. By restricting attention to certainN-dimensional Hilbert spaces of smooth and stochastic functions, whereN is the number of data, we give regularity conditions on the data under which _CV, the regularization parameter predicted by CV, is strongly optimal with respect to the predictive mean-square signal error. We show that _ML is at best weakly optimal with respect to this criterion but is strongly optimal with respect to the innovation variance of the data. For numerical differentiation, _CV and _ML are both shown to be suboptimal with respect to the predictive mean-square derivative error.     

Spaces of distributions, interpolation by translates of a basis function and error estimates

Summary. Interpolation with translates of a basis function is a common process in approximation theory. The most elementary form of the interpolant consists of a linear combination of all translates by interpolation points of a single basis function. Frequently, low degree polynomials are added to the interpolant. One of the significant features of this type of interpolant is that it is often the solution of a variational problem. In this paper we concentrate on developing a wide variety of spaces for which a variational theory is available. For each of these spaces, we show that there is a natural choice of basis function. We also show how the theory leads to efficient ways of calculating the interpolant and to new error estimates. Received December 10, 1996 / Revised version received August 29, 1997