A new method for smoothing surfaces and computing hermite interpolants

Let Ω be a rectangular bounded domain of a plane equipped with a rectangular partition Δ. Assume a piecewise bivariate function that is differentiable up to order (k,l) except at the knots of Δ, where it is less differentiable. In this paper, we introduce a new method for smoothing the above function at the knots. More precisely, we describe algorithms allowing one to transform it into another function that will be differentiable up to order (k,l) in the whole domain Ω. Then, as an application of this method, we give a recursive computation of tensor product Hermite spline interpolants. To illustrate our results, some numerical examples are presented. AMS subject classification (2000)  41A05, 41A15, 65D05, 65D07, 65D10     

On the stability of polynomial transformations between Taylor,Bernstein and Hermite forms

The stability of transformations between Taylor and Hermite and Bernstein and Hermite forms of the polynomials are investigated. The results are analogous to Farouki's concerning the stability of the transformation between Taylor and Bernstein form. An exact asymptotic is given for the condition numbers in thel ¹ case.Research was partially supported by the Copernicus grant RECCAD 94-1068 and by the National Research Foundation of the Hungarian Academy of Sciences grant 16420.     

A microscopic convexity principle for nonlinear partial differential equations

We study microscopic convexity property of fully nonlinear elliptic and parabolic partial differential equations. Under certain general structure condition, we establish that the rank of Hessian ∇ ² u is of constant rank for any convex solution u of equation F(∇ ² u,∇ u,u,x)=0. The similar result is also proved for parabolic equations. Some of geometric applications are also discussed. Research of the first author was supported in part by NSFC No.10671144 and National Basic Research Program of China (2007CB814903). Research of the second author was supported in part by an NSERC Discovery Grant.     

Adaptive thinning for bivariate scattered data

This paper studies adaptive thinning strategies for approximating a large set of scattered data by piecewise linear functions over triangulated subsets. Our strategies depend on both the locations of the data points in the plane, and the values of the sampled function at these points—adaptive thinning. All our thinning strategies remove data points one by one, so as to minimize an estimate of the error that results by the removal of a point from the current set of points (this estimate is termed “anticipated error”). The thinning process generates subsets of “most significant” points, such that the piecewise linear interpolants over the Delaunay triangulations of these subsets approximate progressively the function values sampled at the original scattered points, and such that the approximation errors are small relative to the number of points in the subsets. We design various methods for computing the anticipated error at reasonable cost, and compare and test the performance of the methods. It is proved that for data sampled from a convex function, with the strategy of convex triangulation, the actual error is minimized by minimizing the best performing measure of anticipated error. It is also shown that for data sampled from certain quadratic polynomials, adaptive thinning is equivalent to thinning which depends only on the locations of the data points—nonadaptive thinning. Based on our numerical tests and comparisons, two practical adaptive thinning algorithms are proposed for thinning large data sets, one which is more accurate and another which is faster.     

Fair upper bounds for the curvature in univariate convex interpolation

In convex interpolation the curvature of the interpolants should be as small as possible. We attack this problem by treating interpolation subject to bounds on the curvature. In view of the concexity the lower bound is equal to zero while the upper bound is assumed to be piecewise constant. The upper bounds are called fair with respect to a function class if the interpolation problem becomes solvable for all data sets in strictly convex position. We derive fair a priori bounds for classes of quadraticC ¹, cubicC ², and quarticC ³ splines on refined grids.     

Inspheres and inner products

Among normed linear spacesX of dimension ≧3, finite-dimensional Hilbert spaces are characterized by the condition that for each convex bodyC inX and each ballB of maximum radius contained inC,B’s center is a convex combination of points ofB ∩ (boundary ofC). Among reflexive Banach spaces of dimension ≧3, general Hilbert spaces are characterized by a related but weaker condition on inscribed balls. Research of the first author was partially supported by the U.S. National Science Foundation. Research of the second and third authors was supported by the Consiglio Nazionale delle Ricerche and the Ministero della Pubblica Istruzione of Italy, while they were visiting the University of Washington, Seattle, USA.     

Pick invariant and affine Gauss-Kronecker curvature

The elliptic paraboloid and the homogeneous affine surface given by (u, v, 1/2(u ²+v ^–2/3)),v>0, are characterized as locally strongly convex affine surfaces inA, with constant Pick invariant and vanishing affine Gauss-Kronecker curvature.Research partially supported by DGICYT Grant PB90-0014-C03-02.     

On the Laguerre-Hahn Intertwining Operator and Application to Connection Formulas

In this paper, we show that the lowering operator D _u indexed by a linear functional on polynomials u, introduced by F. Marcellán and R. Sfaxi, namely the Laguerre-Hahn derivative, is intertwining with the standard derivative D by a linear isomorphism S _u on polynomials. This allows us to establish an intertwining relation between the nonsingular Laguerre-Hahn polynomials of class zero of Hermite type and the Hermite polynomials, as well as some new connection formulas between such Laguerre-Hahn polynomials and the canonical basis.     

Geometric and analytic views in existence theorems for optimal control. II. Distributed and boundary controls

Existence theorems are proved for Lagrange problems of optimization in a given domainG with possibly unbounded distributed controls inG and on the boundary ofG, and with functional relations onG and on the boundary represented by closed operators, not necessarily linear. The case where the functional relations are partial differential equations is emphasized. Recent work concerning the reduction or elimination of seminormality requirements is taken into account. Many examples are given.This research was partially supported by AFOSR Research Project 71-2122.     

A Composition Theorem for Multiple Summing Operators

We prove that the composition S(u₁, …, u_n) of a multilinear multiple 2-summing operator S with 2-summing linear operators u_j is nuclear, generalizing a linear result of Grothendieck. Both authors were partially supported by DGICYT grant BMF2001-1284.     

Approximations of the partial derivatives by averaging

A straightforward generalization of a classical method of averaging is presented and its essential characteristics are discussed. The method constructs high-order approximations of the l-th partial derivatives of smooth functions u in inner vertices a of conformal simplicial triangulations T of bounded polytopic domains in ℝ ^d for arbitrary d ≥ 2. For any k ≥ l ≥ 1, it uses the interpolants of u in the polynomial Lagrange finite element spaces of degree k on the simplices with vertex a only. The high-order accuracy of the resulting approximations is proved to be a consequence of a certain hypothesis and it is illustrated numerically. The method of averaging studied in [Dalík J., Averaging of directional derivatives in vertices of nonobtuse regular triangulations, Numer. Math., 2010, 116(4), 619–644] provides a solution of this problem in the case d = 2, k = l = 1.     

Construction of basis functions in the finite element method

In many applications of the finite element method, the explicit form of the basis functions is not known. A well-known exception is that of piecewise linear approximation over a triangulation of the plane, where the basis functions are pyramid functions. In the present paper, the basis functions are displayed in closed form for piecewise polynomial approximation of degreen over a triangulation of the plane. These basis functions are expressed simply in terms of the pyramid functions for linear approximation.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

Contractivity and Analyticity in l p of Some Approximation of the Heat Equation

We consider the lumped mass method with piecewise linear finite elements in two dimensions. When the triangulation is of Delaunay type it is known that the discrete scheme satisfies a maximum principle. In this work we pursue the analysis and prove that the discrete semi-group is l ^p contractive in a sector, which implies smoothing effects and provide some resolvent estimates.     

Shape-Preserving Local Interpolation for Plotting Solutions of ODEs

We investigate the use of piecewise rational interpolants ofDelbourgo and Gregory in an important and widely occurring application.We propose the following algorithm for visually pleasing plotsof the solution of an ordinary differential equation (ODE):use piecewise cubic Hermite interpolation where it can be shownto preserve shape (monotonicity and/or convexity) and also wherethere is no shape to preserve, otherwise use the appropriateconvex or monotone piecewise rational interpolant. Bounds arederived which enable efficient plotting of the rational interpolants.This scheme should be useful in any context where both solutionand derivative of a function are available as data.     

Multivariate convexity preserving interpolation by smooth functions

A set of multivariate data is called strictly convex if there exists a strictly convex interpolant to these data. In this paper we characterize strict convexity of Lagrange and Hermite multivariate data by a simple property and show that for strict convex data and given smoothness requirements there exists a smooth strictly convex interpolant. We also show how to construct a multivariate convex smooth interpolant to scattered data. Partially supported by DGICYT PS93-0310 and by the EC project CHRX-CT94-0522.     

Geometric Tomography of Convex Cones

The parallel X-ray of a convex set K⊂ℝ ⁿ in a direction u is the function that associates to each line l, parallel to u, the length of K∩l. The problem of finding a set of directions such that the corresponding X-rays distinguish any two convex bodies has been widely studied in geometric tomography. In this paper we are interested in the restriction of this problem to convex cones, and we are motivated by some applications of this case to the covariogram problem. We prove that the determination of a cone by parallel X-rays is equivalent to the determination of its sections from a different type of tomographic data (namely, point X-rays of a suitable order). We prove some new results for the corresponding problem which imply, for instance, that convex polyhedral cones in ℝ³ are determined by parallel X-rays in certain sets of two or three directions. The obtained results are optimal.     

An analogue of Hoffman's circulation conditions for max-balanced flows

LetD=(V, A) be a directed graph. A real-valued vectorx defined on the arc setA is amax-balanced flow forD if for every cutW the maximum weight over arcs leavingW equals the maximum weight over arcs enteringW. For vectorslu defined onA, we describe an analogue of Hoffman's circulation conditions for the existence of a max-balanced flowx satisfyinglxu. We describe an algorithm for computing such a vector, but show that minimizing a linear function over the set of max-balanced flows satisfyinglxu is NP-hard. We show that the set of all max-balanced flows satisfyinglxu has a greatest element under the usual coordinate partial order, and we describe an algorithm for computing this element. This allows us to solve several related approximation problems. We also investigate the set of minimal elements under the coordinate partial order. We describe an algorithm for finding a minimal element and show that counting the number of minimal elements is #P-hard. Many of our algorithms exploit the relationship between max-balanced flows and bottleneck paths.Research supported in part by NSF grant DMS 89-05645.Research supported in part by NSF grant ECS 87-18971.     

Sur la suite de polynômes orthogonaux associée à la formeu=δ c +λ(x−c) −1 L

We show that, ifL is regular, semi-classical functional, thenu is also regular and semi-classical for every complex λ, except for a discrete set of numbers depending onL andc. We give the second order linear differential equation satisfied by each polynomial of the orthogonal sequence associated withu. The cases whereL is either a classical functional (Hermite, Laguerre, Bessel, Jacobi) or a functional associated with generalized Hermite polynomials are treated in detail.

     

Admissible slopes for monotone and convex interpolation

Summary In many applications, interpolation of experimental data exhibiting some geometric property such as nonnegativity, monotonicity or convexity is unacceptable unless the interpolant reflects these characteristics. This paper identifies admissible slopes at data points of variousC ¹ interpolants which ensure a desirable shape. We discuss this question, in turn for the following function classes commonly used for shape preserving interpolations: monotone polynomials,C ¹ monotone piecewise polynomials, convex polynomials, parametric cubic curves and rational functions.