Search

In this work we extend some ideas about greedy algorithms, which are well-established tools for, e.g., kernel bases, and exponential-polynomial splines whose main drawback consists in possible overfitting and consequent oscillations of the approximant. To partially overcome this issue, we develop some results on theoretically optimal interpolation points. Moreover, we introduce two algorithms which perform an adaptive selection of the spline interpolation points based on the minimization either of the sample residuals (f-greedy), or of an upper bound for the approximation error based on the spline Lebesgue function (λ -greedy). Both methods allow us to obtain an adaptive selection of the sampling points, i.e., the spline nodes. While the f-greedy selection is tailored to one specific target function, the λ -greedy algorithm enables us to define target-data-independent interpolation nodes. [ABSTRACT FROM AUTHOR]

In this article, two new techniques of approximation of the reliability of a two-terminal network are developed based on the constructive theory of functions and related methods. Two methods of generating an approximation cubic spline are used: Lagrange-type interpolation procedures and Bernstein approximation operator. A possibility of minimizing the total error of approximation, based on keeping some properties invariant, is described in case of a large class of pairs of dual two-terminal networks. Simulations are included, showing that the error of approximation is negligible in case of some special initial data. [ABSTRACT FROM AUTHOR]

In contour machining, contour error is a major factor affecting machining quality. In order to improve the performance of contour following, many control techniques based on real-time contour error estimation have been developed. In this paper, a Double Circle contour error estimation method is proposed. First, based on the kinematic information of the reference point on the command trajectory, five interpolation points closest to the actual point are obtained. Then the approximate contour error is obtained by employing the Double Circle approximation method. Compared with the common contour error approximation methods, the proposed method can achieve high precision approximation. In addition, according to the proposed contour error approximation method, the cross-coupled control strategy is improved. Experiments prove the effectiveness of the proposed estimation method and control strategy. [ABSTRACT FROM AUTHOR]

The hierarchical deep-learning neural network (HiDeNN) is systematically developed through the construction of structured deep neural networks (DNNs) in a hierarchical manner, and a special case of HiDeNN for representing Finite Element Method (or HiDeNN-FEM in short) is established. In HiDeNN-FEM, weights and biases are functions of the nodal positions, hence the training process in HiDeNN-FEM includes the optimization of the nodal coordinates. This is the spirit of r-adaptivity, and it increases both the local and global accuracy of the interpolants. By fixing the number of hidden layers and increasing the number of neurons by training the DNNs, rh-adaptivity can be achieved, which leads to further improvement of the accuracy for the solutions. The generalization of rational functions is achieved by the development of three fundamental building blocks of constructing deep hierarchical neural networks. The three building blocks are linear functions, multiplication, and inversion. With these building blocks, the class of deep learning interpolation functions are demonstrated for interpolation theories such as Lagrange polynomials, NURBS, isogeometric, reproducing kernel particle method, and others. In HiDeNN-FEM, enrichment functions through the multiplication of neurons is equivalent to the enrichment in standard finite element methods, that is, generalized, extended, and partition of unity finite element methods. Numerical examples performed by HiDeNN-FEM exhibit reduced approximation error compared with the standard FEM. Finally, an outlook for the generalized HiDeNN to high-order continuity for multiple dimensions and topology optimizations are illustrated through the hierarchy of the proposed DNNs. [ABSTRACT FROM AUTHOR]

In this study, a polyhedral approximation method for reachable sets of linear delay systems is investigated. For a continuous linear system with multiple delays, the first Euler scheme combining with linear interpolation is used to transform it into a discrete one. Then a polyhedral approximation method based on optimisation techniques is proposed to compute the discrete reachable set. By specifying an approximation error and solving a finite number of convex optimisation problems, a polyhedron can be constructed as the approximation of the discrete reachable set. The approximation quality measured in Hausdorff distance can be directly controlled. Next, illustrated examples are given to demonstrate the effectiveness of the proposed method. Finally, the authors show some reachable sets of linear delay control systems, and they compare the proposed method with some other methods in the literature. Numerical results clearly show the superior performance of the proposed method. [ABSTRACT FROM AUTHOR]

This paper gives a kind of sharp simultaneous approximation error estimation of Birkhoff interpolation for all  1 ≤ p , q ≤ ∞ , 0 ≤ s ≤ r − 1 , ∥ (f − L r f) (s) ∥ p ≤ C (r , s , p , q) (b − a) r − s + 1 / p − 1 / q ∥ f (r) ∥ q , where f ∈ W q r [ a , b ] and L r is the Birkhoff interpolation based on r pairs of numbers (x i , k i) i = 1 r with its P o ́ lya interpolation matrix to be regular. First, based on the integral remainder formula of Birkhoff interpolation, we refer the computation of C (r , s , p , q) to the norm of an integral operator. Second, we refer the values of C (r , s , 1 , 1) and C (r , s , ∞ , ∞) to two explicit integral expressions and the value of C (r , s , 2 , 2) to the computation of the maximum eigenvalue of a Hilbert–Schmidt operator. At the same time, we give the corresponding sharp Wirtinger inequality (s = 0) and sharp Picone inequality (1 ≤ s ≤ r − 1). [ABSTRACT FROM AUTHOR]

Efficient hardware implementations routinely approximate mathematical functions with look-up tables, while keeping the error of the approximation under control. For a certain class of commonly occurring 1D functions, namely monotonically increasing or decreasing functions, we found that it is possible to approximate such functions by repeated application of a very low resolution 1D look-up table. There are many advantages to cascading multiple identical LUTs, including the promise of a very simple hardware design and the use of standard linear interpolation. Further, the complexity associated with unequal bin sizes can be avoided. We show that for realistic applications, including gamma correction, high dynamic range encoding and decoding curves, as well as tone mapping and inverse tone mapping applications, multiple cascaded look-up tables can reduce the approximation error by more than 50% compared to a single look-up table with the same total memory footprint. [ABSTRACT FROM AUTHOR]

Downsampling and the computation of the bandlimited interpolation of discrete-time signals are two important concepts in signal processing. In this paper we analyze the downsampling operation regarding its impact on the existence and computability of the bounded bandlimited interpolation. We assume that the discrete-time signal is obtained by downsampling the samples of a bounded bandlimited signal that vanishes at infinity, and we study two problems. First, we investigate the existence of the bounded bandlimited interpolation for such discrete-time signals from a signal theoretic perspective and show that there exist signals for which the bounded bandlimited interpolation does not exist. Second, we analyze the algorithmic generation of the bounded bandlimited interpolation, using the concept of Turing computability. Turing computability models what is theoretically implementable on a digital computer. Interestingly, it turns out that even if the bounded bandlimited interpolation exists analytically, it is not always computable, which implies that there exists no algorithm on a digital computer that can always compute it. Computability is important in order that the approximation error be controlled. If a signal is not computable, we cannot ascertain whether the computed signal is sufficiently close to the true signal, i.e., we cannot verify every approximation accuracy. [ABSTRACT FROM AUTHOR]

Time delay or the time-of-flight is a most frequently used parameter in many ultrasonic applications. Delay estimation is based on the sampled signal, so the resolution is limited by the sampling grid. Higher accuracy is available if the signal-to-noise ratio is high, then the subsample estimate is desired. Techniques used for subsample interpolation suffer from bias error. Time-of-flight estimation that is free from bias errors is required. The proposed subsample estimation works in the frequency domain; it is based on the cross-correlation peak temporal position. The phase of the cross-correlation frequency response becomes linear thanks to multiplication by the complex conjugate, and its inclination angle is proportional to the delay. Then, subsample interpolation becomes free from the bias error. Twelve algorithmic implementations of this technique have been proposed in this paper. All algorithmic implementations have been analyzed for bias and random errors using simulation and MATLAB codes are given as supplementary material. Comparison with best-performing interpolation techniques (spline approximation, cosine interpolation, carrier phase) is given for both bias and random errors. It was demonstrated that frequency domain interpolation has no bias errors, and noise performance is better or comparable to other subsample estimation techniques. Weighted regression using L2 norm minimization has the best performance: total errors (bias and random) are within 3% of theoretical lower bound. [ABSTRACT FROM AUTHOR]

The modified improved interpolating moving least squares (MIIMLS) method for meshless approaches has been developed. In a meshless method, the approximation accuracy of the derivative is directly proportional to the simulation accuracy. For improving the approximation accuracy of a derivative, we propose MIIMLS using Chebyshev nodes. In the approximation of a function, the results of MIIMLS reach the precision limit. In the approximation of a derivative, the MIIMLS method has high approximation accuracy between the nodes as compared to the conventional methods. [ABSTRACT FROM AUTHOR]

Abstract Radial basis function-generated finite differences (RBF-FD) based on the combination of polyharmonic splines (PHS) with high degree polynomials have recently emerged as a powerful and robust numerical approach for the local interpolation and derivative approximation of functions over scattered node layouts. Among the key features, (i) high orders of accuracy can be achieved without the need of selecting a shape parameter or the issues related to numerical ill-conditioning, and (ii) the harmful edge effects associated to the use of high order polynomials (better known as Runge's phenomenon) can be overcome by simply increasing the stencil size for a fixed polynomial degree. The present study complements our previous results, providing an analytical insight into RBF-FD approximations augmented with polynomials. It is based on a closed-form expression for the interpolant, which reveals the mechanisms underlying these features, including the role of polynomials and RBFs in the interpolant, the approximation error, and the behavior of the cardinal functions near boundaries. Numerical examples are included for illustration. [ABSTRACT FROM AUTHOR]

This work provides a new mixed finite element method for the Brinkman problem over arbitrary convex quadrilateral meshes. The velocity is approximated by piecewise polynomial element space which is H ( div ) -nonconforming, and the pressure is approximated by piecewise constant. We give the convergence analysis of our element, and especially show the robustness with respect to the Darcy limit. Moreover, via a discrete de Rham complex, a higher-order approximation error term is obtained for incompressible flow. Numerical examples verify our theoretical findings. [ABSTRACT FROM AUTHOR]

Many applications of finite impulse response (FIR) digital filters impose strict format constraints on the filter coefficients. Such requirements increase the complexity of determining optimal designs for the problem at hand. We introduce a fast and efficient method, based on the computation of good nodes for polynomial interpolation and Euclidean lattice basis reduction. Experiments show that it returns quasi-optimal finite wordlength FIR filters; compared to previous approaches it also scales remarkably well (length 125 filters are treated in $<$ 9 s). It also proves useful for accelerating the determination of optimal finite wordlength FIR filters. [ABSTRACT FROM AUTHOR]

A fully implementable filtered polynomial approximation on spherical shells is considered. The method proposed is a quadrature-based version of a filtered polynomial approximation. The radial direction and the angular direction of the shells are treated separately with constructive filtered polynomial approximation. The approximation error with respect to the supremum norm is shown to decay algebraically for functions in suitable differentiability classes. Numerical experiments support the results. [ABSTRACT FROM AUTHOR]

Orthogonal projection offers the optimal solution for many sampling-reconstruction problems in terms of the least square error. In the standard interpolation setting where the sampling is assumed to be ideal, however, the projection is impossible unless the interpolation kernel is related to the sinc function and the input is bandlimited. In this paper, we propose a notion of shifting kernel toward the orthogonal projection. For a given interpolation kernel, we formulate optimization problems whose solutions lead to shifted interpolations that, while still being interpolatory, are closest to the orthogonal projection in the sense of the minimax regret. The quality of interpolation is evaluated in terms of the average approximation error over input shift. For the standard linear interpolation, we obtain several values of optimal shift, dependent on a priori information on input signals. For evaluation, we apply the new shifted linear interpolations to a Gaussian signal, an ECG signal, a speech signal, a two-dimensional signal, and three natural images. Significant improvements are observed over the standard and the 0.21-shifted linear interpolation proposed early. [ABSTRACT FROM PUBLISHER]

Linear motion commands of computer numerical control (CNC) machine tools need to be smoothed at the transition corners in order to guarantee continuous and steady machining. However, because of the complex kinematic constraints, very few researches have devoted to developing analytical and high order continuous corner smoothing algorithms of five-axis tool paths, although it is important to guarantee both high calculation efficiency and good dynamic performance of five-axis CNC machining. This paper develops an analytical C 3 continuous corner smoothing algorithm of five-axis tool paths by locally inserting specially designed quintic micro splines into the transition corners of five-axis linear commands. C 3 continuity of the tool tip position and the tool orientation are guaranteed along the entire tool path. The maximal approximation errors of the tool tip position and the tool orientation are both constrained in the workpiece coordinate system. The synchronization of the tool tip position and tool orientation are mathematically guaranteed at the junctions of the linear and spline segments. The proposed corner smoothing algorithm can calculate all control points of the locally inserted tool tip position and tool orientation splines analytically without any iteration, which makes it very suitable to on-line calculation. Experiments on an in-house developed five-axis CNC platform verify that the maximal approximation errors of both tool tip position and tool orientation are constrained, and the proposed C 3 continuous corner smoothing algorithm has higher tracking accuracy and lower acceleration frequency content at higher frequencies than the C 2 continuous algorithm. [ABSTRACT FROM AUTHOR]

The linear canonical transform (LCT), which generalizes many classical transforms, has been shown to be a powerful tool for signal processing and optics. Sampling theory of the LCT for bandlimited signals has blossomed in recent years. However, in practice signals are never perfectly bandlimited, and in many cases measurement devices are nonideal. The objective of this paper is to develop a sampling theorem for the LCT from general measurements, which can provide a suitable and realistic model of sampling and approximation for real-world applications. We first describe a general class of approximation spaces for the LCT and provide a full characterization of their basis functions. Then, we propose a generalized sampling theorem for arbitrary measurement and approximation spaces associated with the LCT. Several properties of the proposed sampling theorem are also discussed. Furthermore, the approximation error is estimated. Finally, numerical results and several applications of the derived results are presented. [ABSTRACT FROM PUBLISHER]

To reduce the feedrate fluctuation in non-uniform rational B-spline (NURBS) interpolation caused by approximation errors of interpolation methods, a new NURBS interpolation method with minimal feedrate fluctuation for CNC machine tools is proposed to obtain the sampling curve parameter by solving a quartic equation with respect to the curve parameter increment according to the scheduled feedrate using Ferrari's formulas and Shengjin's formulas. Firstly, the second-order Taylor expansion is applied on the numerator and denominator in the NURBS representation separately with unknown curve parameter increment. Then, a quartic equation with respect to the curve parameter increment is formed and solved by Ferrari's formulas and Shengjin's formulas efficiently, which can achieve minimal feedrate fluctuation in real-time interpolation. In principle, the proposed method can totally eliminate the feedrate fluctuation for second-degree NURBS curves and can reduce it to a satisfied value for other high-degree NURBS curves. Finally, numerical simulations and experiments are conducted to verify the feasibility and applicability of the proposed method. [ABSTRACT FROM AUTHOR]

A class of methods constructed to numerically approximate the solution of two-point singularly perturbed boundary value problems of the form ϵu'' + bu' + cu = f use exponentials to mimic exponential behavior of the solution in the boundary layer(s). We refer to them as exponentially fitted methods. Such methods are usually exact on polynomials of certain degree and some exponential functions. Shortly, they are exact on exponential sums. It is often possible that consistency of the method follows from the convergence of the interpolating function standing behind the method. Because of that, we consider the interpolation error for exponential sums. The main result of the paper is an error bound for interpolation by the exponential sum to the solution of the singularly perturbed problem that does not depend on perturbation parameter ϵ when ϵ is small with the respect to mesh width. The numerical experiment implies that the use of a dense mesh in the boundary layer for small meshwidth results in ϵ-uniform convergence. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we consider the approximation of a function by its interpolating multilinear spline and the approximation of its derivatives by the derivatives of the corresponding spline. We obtain the exact uniform approximation error on classes of functions with moduli of continuity bounded above by certain majorants. [Copyright &y& Elsevier]

Cutting speed is a key factor that influences machined surface quality and tool life in milling. To date, the study of its distribution over a machined surface has not been established. This paper presents a mathematical model to evaluate cutting speed on the machined surface in 3-axis ball nose milling. The approximation errors introduced by surface shape, step-over and CNC interpolation are analysed. The model is used to predict visible areas which have different colour intensities on finished surfaces in the machining of a wood-plastic composite. A good agreement is obtained between the prediction and experimental results. [ABSTRACT FROM AUTHOR]

• We construct a new representation of CSRBF, which unites interpolation and approximation. • A further adaptive algorithm to determine interpolation and approximation at each point is presented. • We develop the quasi-interpolation method into a method combining interpolation and approximation. • With our multi-level scheme, we can interpolate all the data points and hold a low shape approximation error. Interpolation and approximation radial basis function (RBF) has been widely used in the implicit surface reconstruction. However, a simple interpolation or approximation method may either have unwanted oscillation around the scattered points, or have low accuracy at scattered points. In this paper, we construct a new representation of RBF, which unites interpolation and approximation. A further adaptive algorithm to determine interpolation and approximation is presented. With the new representation, we can develop quasi-interpolation method from an approximation method into a method combining interpolation and approximation. And we can determine interpolation or approximation at each of scattered points without solving large linear systems. Experiments show that the given method is precision-controlled and fast in implicit surface reconstruction. [ABSTRACT FROM AUTHOR]

We present a method for real-time computation of clothoid coordinates that guarantees bounded approximation error over a wide range of clothoid parameters provided that the clothoid’s orientation change and length are bounded. It is shown that coordinates of clothoid with any parameters can be computed from those of a single clothoid (with fixed parameters), using appropriate geometrical transformations. A comprehensive analysis is given on how to determine a required set of clothoids and, based on this, how to sample a clothoid in a lookup table in order to achieve required approximation precision. The algorithm is computationally very efficient and therefore suitable for real-time path planning, as well as for other applications that benefit from fast clothoid computation. [ABSTRACT FROM PUBLISHER]

Abstract: Traditionally, approximation methods are utilized in the parametric interpolation because of the nonanalytic relationship between the spline parameter and the arc length. The approximation error has been considered as the source of the feedrate fluctuation. This paper shows that the discrepancy between the desired tool path and the target trajectory of the motion system is another primary source, and presents a feedback interpolator to eliminate the feedrate fluctuation. To evaluate the initial parameter value for the interpolator, an arc-length based Taylor's expansion with arc-length compensation is proposed, which alleviates greatly the feedrate command error caused by the trajectory deviation. Then, a feedback correction scheme is developed to further reduce the feedrate command error that results from the approximation error. Both computational load analysis and numerical simulations are conducted, and the results show that the present interpolator has very good performance in both efficiency and accuracy, thus is a good choice for high speed and high precision CNC machines. [Copyright &y& Elsevier]

Abstract: In this paper a class of Birkhoff-type interpolation problems on arbitrary nodal points is studied. The explicit representation (characterization), the uniqueness and the error function are explicitly given. Furthermore, we apply the obtained Birkhoff-type interpolation method to find: (i) the numerical solution of high order initial-value problems (IVPs) and the corresponding error of this approximation, (ii) the approximation of some special functions with their explicit error functions, and (iii) new interpolatory type quadrature formulae of precision degree at least and . Numerical examples are included to demonstrate the validity and applicability of the technique proposed in this paper and a comparison is made with the existing results. The results reveal that the new method is effective, simple and accurate. [Copyright &y& Elsevier]

We present a new class of continuously defined parametric snakes using a special kind of exponential splines as basis functions. We have enforced our bases to have the shortest possible support subject to some design constraints to maximize efficiency. While the resulting snakes are versatile enough to provide a good approximation of any closed curve in the plane, their most important feature is the fact that they admit ellipses within their span. Thus, they can perfectly generate circular and elliptical shapes. These features are appropriate to delineate cross sections of cylindrical-like conduits and to outline bloblike objects. We address the implementation details and illustrate the capabilities of our snake with synthetic and real data. [ABSTRACT FROM AUTHOR]

Abstract: Moving least-square (MLS) is an approximation method for data interpolation, numerical analysis and statistics. In this paper we consider the MLS method in learning theory for the regression problem. Essential differences between MLS and other common learning algorithms are pointed out: lack of a natural uniform bound for estimators and the pointwise definition. The sample error is estimated in terms of the weight function and the finite dimensional hypothesis space. The approximation error is dealt with for two special cases for which convergence rates for the total error measuring the global approximation on the whole domain are provided. [Copyright &y& Elsevier]

In this paper, we formally investigate two mathematical aspects of Hermite splines that are relevant to practical applications. We first demonstrate that Hermite splines are maximally localized, in the sense that the size of their support is minimal among pairs of functions with identical reproduction properties. Then, we precisely quantify the approximation power of Hermite splines for the reconstruction of functions and their derivatives. It is known that the Hermite and B-spline approximation schemes have the same approximation order. More precisely, their approximation error vanishes as O (T 4) when the step size T goes to zero. In this work, we show that they actually have the same asymptotic approximation error constants, too. Therefore, they have identical asymptotic approximation properties. Hermite splines combine optimal localization and excellent approximation power, while retaining interpolation properties and closed-form expression, in contrast to existing similar functions. These findings shed a new light on the convenience of Hermite splines in the context of computer graphics and geometrical design. [ABSTRACT FROM AUTHOR]

In this paper we introduce a method for reconstruction of 3D objects from their 1D parallel cross-sections by set-valued interpolation. We regard a 3D object as the graph of a set-valued function defined on a planar domain, with the given 1D cross-sections as its samples. The method is based on a triangulation T of the sampling points in the planar domain and it is modular: for each triangle in T the corresponding 1D cross-sections are geometrically interpolated by a union of polyhedrons. The union of these interpolants over all triangles of T constitutes the approximating 3D object. Properties of this approximation are studied, in particular we derive the approximation order of the error, measured by the symmetric difference metric. [ABSTRACT FROM AUTHOR]

A novel numerical method, which uses linear edge elements in eddy current region and nodal finite elements in non eddy current regions, is presented for solving 3D eddy current problems. The mathematical models are divided into two parts according to their properties. The theory of linear edge elements is developed. The test results show the validity of the algorithm. [ABSTRACT FROM PUBLISHER]

A novel technique for designing piecewise-polynomial interpolators for hardware implementation of elementary functions is investigated in this paper. In the proposed approach, the interval where the function is approximated is subdivided in equal length segments and two adjacent segments are grouped in a segment pair. Suitable constraints are then imposed between the coefficients of the two interpolating polynomials in each segment pair. This allows reducing the total number of stored coefficients. It is found that the increase in the approximation error due to constraints between polynomial coefficients can easily be overcome by increasing the fractional bits of the coefficients. Overall, compared with standard unconstrained piecewise-polynomial approximation having the same accuracy, the proposed method results in a considerable advantage in terms of the size of the lookup table needed to store polynomial coefficients. The calculus of the coefficients of constrained polynomials and the optimization of coefficients bit width is also investigated in this paper. Results for several elementary functions and target precision ranging from 12 to 42 bits are presented. The paper also presents VLSI implementation results, targeting a 90 nm CMOS technology, and using both direct and Horner architectures for constrained degree-1, degree-2, and degree-3 approximations. [ABSTRACT FROM AUTHOR]