Computation of the differentiation matrix for the Hermite interpolating polynomials

We obtain formulas for computing the elements of the differentiation matrix for special cases of the Hermite interpolating polynomials. They are expressed in terms of the elements of the differentiation matrices of the Lagrange interpolating polynomials in various systems of interpolation nodes, which can easily be calculated on a computer. These formulas find application in numerical realization of collocation finiteelement methods for solving differential problems.Translated fromVychislitel'naya i Prikladnaya Matematika, Issue 71, 1990, pp. 43–49.     

Reliable determination of interpolating polynomials

This paper addresses a fundamental problem in mathematics and numerical analysis, that of determining a polynomial interpolant to specified data. The data is taken as consisting of a set of points (abscissae), at each of which is specified a function value. Additionally, at each point, any number of leading derivative values of the function may be given. Mathematically, this problem is solved. The classical Lagrangian interpolation formula applies in the derivative-free case, and the Newton form of the interpolating polynomial in general.Numerically, few reliable algorithms are available; most published algorithms concentrate on speed of computation. This paper describes an algorithm that delivers the required polynomial in Chebyshev form. It is based on the repeated use of the Newton representation, with a data ordering strategy and iterative refinement to improve accuracy, using a carefully devised merit function to measure success. The algorithm attempts to provide a polynomial that is stable in the sense of backward error analysis, i.e. that is exact for slightly perturbed data.Implementations of the algorithm have been in use since the early 1980s in the NAG Library and NPL's Data Approximation Subroutine Library (DASL). In addition to providing polynomial interpolants in their own right, these implementations are used as computational modules in the NAG and DASL routines for constrained least-squares polynomial data fitting.This paper constitutes the first detailed presentation of the algorithm.     

Computation of best possible low degree expanders

We present an algorithm for computing a best possible bipartite cubic expander for a given number of vertices. Such graphs are needed in many applications and are also the basis for many results in theoretical computer science. Known construction methods for expander graphs yield expanders that have a fairly poor expansion compared to the best possible expansion. Our algorithm is based on a lemma which allows to calculate an upper bound for the expansion of cubic bipartite graphs.     

Converse results on equiconvergence of interpolating polynomials

, n- n- 1 , . , , ( « ») f .     

Bivariate interpolating polynomials and splines (I)

The multivariate splines which were first presented by de Boor as a complete theoretical system have intrigued many mathematicians who have devoted many works in this field which is still in the process of development. The author of this paper is interested in the area of interpolation with special emphasis on the interpolation methods and their approximation orders. But such B-splines (both univariate and multivariate) do not interpolated directly, so I approached this problem in another way which is to extend my interpolating spline of degree 2n-1 in univariate case (See[7]) to multivariate case. I selected triangulated region which is inspired by other mathematician’s works (e.g. [2] and [3]) and extend the interpolating polynomials from univariate to m-variate case (See [10])In this paper some results in the case m=2 are discussed and proved in more concrete details. Based on these polynomials, the interpolating splines (it is defined by me as piecewise polynomials in which the unknown partial derivatives are determined under certain continuous conditions) are also discussed. The approximation orders of interpolating polynomials and of cubic interpolating splines are inverstigated. We limited our discussion on the rectangular domain which is partitioned into equal right triangles. As to the case in which the rectangular domain is partitioned into unequal right triangles as well as the case of more complicated domains, we will discuss in the next paper.     

Arc graphs and their possible application to sparse matrix problems

In continuation of earlier work on the graph algorithmic language GRAAL, a new type of graph representation is introduced involving solely the arcs and their incidence relations. In line with the set theoretical foundation of GRAAL, the are graph structure is defined in terms of four Boolean mappings over the power set of the ares. A simple data structure is available for are graphs requiring only storage of the order of the cardinality of the are set. As an application, the LU decomposition of large sparse matrices and the solution of the corresponding linear systems are formulated in terms of are graphs and their operators, and experimental results involving these algorithms are presented.     

Some isoperimetric inequalities and their application to problems on polynomials

We prove sharp inequalities for the product of the Lebesgue integral of certain power of a positive absolutely continuous and nondecreasing function (or a linear combination of such distinct powers) and the Lebesgue integral of the square of its derivative. These inequalities are related to some problems for polynomials having small Mahler measure. As an application, we give a lower bound for the logarithmic height of a noncyclotomic algebraic number in terms of its degree.     

Learning to select the recombination operator for derivative-free optimization

Extensive studies on selecting recombination operators adaptively, namely, adaptive operator selection(AOS), during the search process of an evolutionary algorithm(EA), have shown that AOS is promising for improving EA’s performance. A variety of heuristic mechanisms for AOS have been proposed in recent decades, which usually contain two main components: the feature extraction and the policy setting. The feature extraction refers to as extracting relevant features from the information collected ...     

The convergence of partial sums of interpolating polynomials

For functions of ΛBV, we study the convergence of the partial sums of interpolating polynomials. An estimate is found for the Fourier-Lagrange coefficients of these functions. For functions in BV, convergence is shown at points of discontinuity if the order of the polynomial increases sufficiently rapidly compared to the order of the partial sum. A Dirichlet-Jordan type theorem is shown for functions of harmonic bounded variation, and this result is shown to be best possible.     

Some remarks on overconvergence of Hermite interpolating polynomials

In this paper, a quantitative estimate for Hermite interpolant to function ψ(z)=(z ^m −β ^m )^r on the zeros of (z ⁿ −α ⁿ ) ^r is obtained. Using this estimate, a rather wide extension of the theorem of Walsh is proved and five special cases of it are given. The Project is supported by National Natural Science Foundation of China.     

Sobolev seminorm of quadratic functions with applications to derivative-free optimization

This paper studies the \(H^1\) Sobolev seminorm of quadratic functions. The research is motivated by the least-norm interpolation that is widely used in derivative-free optimization. We express the \(H^1\) seminorm of a quadratic function explicitly in terms of the Hessian and the gradient when the underlying domain is a ball. The seminorm gives new insights into least-norm interpolation. It clarifies the analytical and geometrical meaning of the objective function in least-norm interpolation. We employ the seminorm to study the extended symmetric Broyden update proposed by Powell. Numerical results show that the new thoery helps improve the performance of the update. Apart from the theoretical results, we propose a new method of comparing derivative-free solvers, which is more convincing than merely counting the numbers of function evaluations.     

Permutation polynomials and orthomorphism polynomials of degree six

A classic paper of Dickson gives a complete list of permutation polynomials of degree less than 6 over arbitrary finite fields, and degree 6 over finite fields of odd characteristic. However, some published statements have hinted that Dicksonʼs classification might be incomplete in the degree 6 case. We uncover the reason for this confusion, and confirm the list of degree 6 permutation polynomials over all finite fields. Using this classification, we determine the complete list of degree 6 orthomorphism polynomials. Additionally, we note that a family of permutation polynomials from Dicksonʼs list provides counterexamples to a published conjecture of Mullen.     

Convex interpolating splines of arbitrary degree II

For given data {(x _i ,y _i )} _i=0 ⁿ , (x ₀<x ₁<...<x _n ) we consider the possibility of finding a spline functions of arbitrary degreek+1 (k 1) with preassigned smoothnessl, where 1 l [(k+1)/2]. The splines should be such thats(x _i )=y _i ,i=0, 1,...,n ands is increasing and convex on [x ₀,x _n ]. Sufficient conditions which guarantee the existence ofs and an explicit formula for this function are derived.