Tight linear envelopes for splines

Summary. A sharp bound on the distance between a spline and its B-spline control polygon is derived. The bound yields a piecewise linear envelope enclosing spline and polygon. This envelope is particularly simple for uniform splines and splines in Bernstein-Bézier form and shrinks by a factor of 4 for each uniform subdivision step. The envelope can be easily and efficiently implemented due to its explicit and constructive nature. Received February 12, 1999 / Revised version received October 15, 1999 / Published online May 4, 2001     

Error bounds for minimal energy bivariate polynomial splines

Summary. We derive error bounds for bivariate spline interpolants which are calculated by minimizing certain natural energy norms. Received March 28, 2000 / Revised version received June 23, 2000 / Published online March 8, 2002 RID="*" ID="*" Supported by the National Science Foundation under grant DMS-9870187 RID="**" ID="**" Supported by the National Science Foundation under grant DMS-9803340 and by the Army Research Office under grant DAAD-19-99-1-0160     

Least supported bases and local linear independence

Summary. We introduce the concept of least supported basis, which is very useful for numerical purposes. We prove that this concept is equivalent to the local linear independence of the basis. For any given locally linearly independent basis we characterize all the bases of the space sharing the same property. Several examples for spline spaces are given. Received December 4, 1992 / Revised version received March 2, 1993     

The uniform convergence of thin plate spline interpolation in two dimensions

Summary. Let be a function from to that has square integrable second derivatives and let be the thin plate spline interpolant to at the points in . We seek bounds on the error when is in the convex hull of the interpolation points or when is close to at least one of the interpolation points but need not be in the convex hull. We find, for example, that, if is inside a triangle whose vertices are any three of the interpolation points, then is bounded above by a multiple of , where is the length of the longest side of the triangle and where the multiplier is independent of the interpolation points. Further, if is any bounded set in that is not a subset of a single straight line, then we prove that a sequence of thin plate spline interpolants converges to uniformly on . Specifically, we require , where is now the least upper bound on the numbers and where , , is the least Euclidean distance from to an interpolation point. Our method of analysis applies integration by parts and the Cauchy--Schwarz inequality to the scalar product between second derivatives that occurs in the variational calculation of thin plate spline interpolation. Received November 10, 1993 / Revised version received March 1994     

Smooth macro-elements based on Clough-Tocher triangle splits

Summary. Macro-elements of smoothness on Clough-Tocher triangle splits are constructed for all . These new elements are improvements on elements constructed in [11] in that (disproving a conjecture made there) certain unneeded degrees of freedom have been removed. Numerical experiments on Hermite interpolation with the new elements are included. Received September 6, 2000 / Revised version received November 15, 2000 / Published online July 25, 2001     

Piecewise linear prewavelets on arbitrary triangulations

This paper studies locally supported piecewise linear prewavelets on bounded triangulations of arbitrary topology. It is shown that a concrete choice of prewavelets form a basis of the wavelet space when the degree of the vertices in the triangulation is not too high. Received December 29, 1997 / Revised version received April 14, 1998     

Semi-discrete Galerkin approximation of the single layer equation by general splines

This paper deals with a semi-discrete version of the Galerkin method for the single-layer equation in a plane, in which the outer integral is approximated by a quadrature rule. A feature of the analysis is that it does not require high precision quadrature or exceptional smoothness of the data. Instead, the assumptions on the quadrature rule are that constant functions are integrated exactly, that the rule is based on sufficiently many quadrature points to resolve the approximation space, and that the Peano constant of the rule is sufficiently small. It is then shown that the semi-discrete Galerkin approximation is well posed. For the trial and test spaces we consider quite general piecewise polynomials on quasi-uniform meshes, ranging from discontinuous piecewise polynomials to smoothest splines. Since it is not assumed that the quadrature rule integrates products of basis functions exactly, one might expect degradation in the rate of convergence. To the contrary, it is shown that the semi-discrete Galerkin approximation will converge at the same rate as the corresponding Galerkin approximation in the and norms. Received March 15, 1996 / Revised version received June 2, 1997     

A stable and conservative finite difference scheme for the Cahn-Hilliard equation

Summary. We propose a stable and conservative finite difference scheme to solve numerically the Cahn-Hilliard equation which describes a phase separation phenomenon. Numerical solutions to the equation is hard to obtain because it is a nonlinear and nearly ill-posed problem. We design a new difference scheme based on a general strategy proposed recently by Furihata and Mori. The new scheme inherits characteristic properties, the conservation of mass and the decrease of the total energy, from the equation. The decrease of the total energy implies boundedness of discretized Sobolev norm of the solution. This in turn implies, by discretized Sobolev's lemma, boundedness of max norm of the solution, and hence the stability of the solution. An error estimate for the solution is obtained and the order is . Numerical examples demonstrate the effectiveness of the proposed scheme. Received July 22, 1997 / Revised version received October 19, 1999 / Published online August 2, 2000     

A fourth/second order accurate collocation method for singularly perturbed two-point boundary value problems using tension splines

Summary.   The collocation tension spline is considered as a numerical solution of a singularly perturbed two-point boundary value problem: . The collocation points are chosen as a generalization of the classical Gaussian points. Unlike the traditional approach, we employ the B-spline representation in the analysis. This leads to global quadratic convergence of the method for small perturbation parameters, and, for large values, the order of convergence is four. Received October 4, 1996 / Revised version received September 23, 1999 / Published online October 16, 2000     

Parallel algorithms for maximal monotone operators of local type

Summary. This paper presents general algorithms for the parallel solution of finite element problems associated with maximal monotone operators of local type. The latter concept, which is also introduced here, is well suited to capture the idea that the given operator is the discretization of a differential operator that may involve nonlinearities and/or constraints as long as those are of a local nature. Our algorithms are obtained as a combination of known algorithms for possibly multi-valued maximal monotone operators with appropriate decompositions of the domain. This work extends a method due to two of the authors in the single-valued and linear case. Received April 25, 1994     

Positive definiteness in the numerical solution of Riccati differential equations

Summary. In this work we address the issue of integrating symmetric Riccati and Lyapunov matrix differential equations. In many cases -- typical in applications -- the solutions are positive definite matrices. Our goal is to study when and how this property is maintained for a numerically computed solution. There are two classes of solution methods: direct and indirect algorithms. The first class consists of the schemes resulting from direct discretization of the equations. The second class consists of algorithms which recover the solution by exploiting some special formulae that these solutions are known to satisfy. We show first that using a direct algorithm -- a one-step scheme or a strictly stable multistep scheme (explicit or implicit) -- limits the order of the numerical method to one if we want to guarantee that the computed solution stays positive definite. Then we show two ways to obtain positive definite higher order approximations by using indirect algorithms. The first is to apply a symplectic integrator to an associated Hamiltonian system. The other uses stepwise linearization. Received April 21, 1993     

Exponential decay of C^1- cubic splines vanishing at two symmetric points in each knot interval

Summary. In the course of working on the preconditioning of cubic collocation at Gauss points, one has to deal with the exponential decay of certain cubic splines. Such results were obtained by Kim and Parter in the case of uniform spacing. In this paper we extend these results to arbitrary grids and state its application to the preconditioned cubic collocation method. Received May 30, 1994 / Revised version received March 13, 1996     

Error bounds for Romberg quadrature

Denote by the error of a Romberg quadrature rule applied to the function f. We determine approximately the constants in the bounds of the types and for all classical Romberg rules. By a comparison with the corresponding constants of the Gaussian rule we give the statement “The Gaussian quadrature rule is better than the Romberg method” a precise meaning. Received September 10, 1997 / Revised version received February 16, 1998     

Planar mesh refinement cannot be both local and regular

We show that two desirable properties for planar mesh refinement techniques are incompatible. Mesh refinement is a common technique for adaptive error control in generating unstructured planar triangular meshes for piecewise polynomial representations of data. Local refinements are modifications of the mesh that involve a fixed maximum amount of computation, independent of the number of triangles in the mesh. Regular meshes are meshes for which every interior vertex has degree 6. At least for some simple model meshing problems, optimal meshes are known to be regular, hence it would be desirable to have a refinement technique that, if applied to a regular mesh, produced a larger regular mesh. We call such a technique a regular refinement. In this paper, we prove that no refinement technique can be both local and regular. Our results also have implications for non-local refinement techniques such as Delaunay insertion or Rivara's refinement. Received August 1, 1996 / Revised version received February 28, 1997     

On the optimal stability of bases of univariate functions

Summary. This paper is concerned with bases of finite dimensional spaces of univariate continuous functions which are optimally stable for evaluation. The only bases considered are those whose elements have no sign changes. Among these, an optimally stable basis is characterized under the assumption that the set of points where each basis function is nonzero is an interval. A uniqueness result and many examples of such optimally stable bases are also provided. Received May 26, 2000 / Published online August 17, 2001     

Quadrature rules for rational functions

Summary. It is shown how recent ideas on rational Gauss-type quadrature rules can be extended to Gauss-Kronrod, Gauss-Turán, and Cauchy principal value quadrature rules. Numerical examples illustrate the advantages in accuracy thus achievable. Received June 21, 1999 / Revised version received September 14, 1999 / Published online June 21, 2000     

A numerically stable, structure preserving method for computing the eigenvalues of real Hamiltonian or symplectic pencils

A new method is presented for the numerical computation of the generalized eigenvalues of real Hamiltonian or symplectic pencils and matrices. The method is numerically backward stable and preserves the structure (i.e., Hamiltonian or symplectic). In the case of a Hamiltonian matrix the method is closely related to the square reduced method of Van Loan, but in contrast to that method which may suffer from a loss of accuracy of order , where is the machine precision, the new method computes the eigenvalues to full possible accuracy. Received April 8, 1996 / Revised version received December 20, 1996     

Asymptotic formula for the error in cardinal interpolation

Summary. We give the asymptotic formula for the error in cardinal interpolation. We generalize the Mazur Orlicz Theorem for periodic function. Received February 22, 1999 / Revised version received October 15, 1999 / Published online March 20, 2001     

Smolyak cubature of given polynomial degree with few nodes for increasing dimension

Summary. Some recent investigations (see e.g., Gerstner and Griebel [5], Novak and Ritter [9] and [10], Novak, Ritter and Steinbauer [11], Wasilkowski and Woźniakowski [18] or Petras [13]) show that the so-called Smolyak algorithm applied to a cubature problem on the d-dimensional cube seems to be particularly useful for smooth integrands. The problem is still that the numbers of nodes grow (polynomially but) fast for increasing dimensions. We therefore investigate how to obtain Smolyak cubature formulae with a given degree of polynomial exactness and the asymptotically minimal number of nodes for increasing dimension d and obtain their characterization for a subset of Smolyak formulae. Error bounds and numerical examples show their good behaviour for smooth integrands. A modification can be applied successfully to problems of mathematical finance as indicated by a further numerical example. Received September 24, 2001 / Revised version received January 24, 2002 / Published online April 17, 2002 RID="*" ID="*" The author is supported by a Heisenberg scholarship of the Deutsche Forschungsgemeinschaft     

Barycentric formulae for cardinal (SINC-) interpolants by Jean-Paul Berrut

Summary. A formula for the efficient evaluation of the (truncated) cardinal series is known to be numerically unstable near the interpolation abscissae. Here it is shown how the series can be evaluated in an entirely stable manner. Received February 14, 2000 / Published online October 16, 2000