Accurate fourteenth-order methods for solving nonlinear equations

We establish new iterative methods of local order fourteen to approximate the simple roots of nonlinear equations. The considered three-step eighth-order construction can be viewed as a variant of Newton’s method in which the concept of Hermite interpolation is used at the third step to reduce the number of evaluations. This scheme includes three evaluations of the function and one evaluation of the first derivative per iteration, hence its efficiency index is 1.6817. Next, the obtained approximation for the derivative of the Newton’s iteration quotient is again taken into consideration to furnish novel fourteenth-order techniques consuming four function and one first derivative evaluations per iteration. In providing such new fourteenth-order methods, we also take a special heed to the computational burden. The contributed four-step methods have 1.6952 as their efficiency index. Finally, various numerical examples are given to illustrate the accuracy of the developed techniques.     

Rational approximation of vertical segments

In many applications, observations are prone to imprecise measurements. When constructing a model based on such data, an approximation rather than an interpolation approach is needed. Very often a least squares approximation is used. Here we follow a different approach. A natural way for dealing with uncertainty in the data is by means of an uncertainty interval. We assume that the uncertainty in the independent variables is negligible and that for each observation an uncertainty interval can be given which contains the (unknown) exact value. To approximate such data we look for functions which intersect all uncertainty intervals. In the past this problem has been studied for polynomials, or more generally for functions which are linear in the unknown coefficients. Here we study the problem for a particular class of functions which are nonlinear in the unknown coefficients, namely rational functions. We show how to reduce the problem to a quadratic programming problem with a strictly convex objective function, yielding a unique rational function which intersects all uncertainty intervals and satisfies some additional properties. Compared to rational least squares approximation which reduces to a nonlinear optimization problem where the objective function may have many local minima, this makes the new approach attractive.     

Adaptive radial basis function interpolation using an error indicator

In some approximation problems, sampling from the target function can be both expensive and time-consuming. It would be convenient to have a method for indicating where approximation quality is poor, so that generation of new data provides the user with greater accuracy where needed. In this paper, we propose a new adaptive algorithm for radial basis function (RBF) interpolation which aims to assess the local approximation quality, and add or remove points as required to improve the error in the specified region. For Gaussian and multiquadric approximation, we have the flexibility of a shape parameter which we can use to keep the condition number of interpolation matrix at a moderate size. Numerical results for test functions which appear in the literature are given for dimensions 1 and 2, to show that our method performs well. We also give a three-dimensional example from the finance world, since we would like to advertise RBF techniques as useful tools for approximation in the high-dimensional settings one often meets in finance.     

Constrained optimization involving expensive function evaluations: A sequential approach

This paper presents a new sequential method for constrained nonlinear optimization problems. The principal characteristics of these problems are very time consuming function evaluations and the absence of derivative information. Such problems are common in design optimization, where time consuming function evaluations are carried out by simulation tools (e.g., FEM, CFD). Classical optimization methods, based on derivatives, are not applicable because often derivative information is not available and is too expensive to approximate through finite differencing.The algorithm first creates an experimental design. In the design points the underlying functions are evaluated. Local linear approximations of the real model are obtained with help of weighted regression techniques. The approximating model is then optimized within a trust region to find the best feasible objective improving point. This trust region moves along the most promising direction, which is determined on the basis of the evaluated objective values and constraint violations combined in a filter criterion. If the geometry of the points that determine the local approximations becomes bad, i.e. the points are located in such a way that they result in a bad approximation of the actual model, then we evaluate a geometry improving instead of an objective improving point. In each iteration a new local linear approximation is built, and either a new point is evaluated (objective or geometry improving) or the trust region is decreased. Convergence of the algorithm is guided by the size of this trust region. The focus of the approach is on getting good solutions with a limited number of function evaluations.     

Shape-preserving dynamic programming

Dynamic programming is the essential tool in dynamic economic analysis. Problems such as portfolio allocation for individuals and optimal growth of national economies are typical examples. Numerical methods typically approximate the value function and use value function iteration to compute the value function for the optimal policy. Polynomial approximations are natural choices for approximating value functions when we know that the true value function is smooth. However, numerical value function iteration with polynomial approximations is unstable because standard methods such as interpolation and least squares fitting do not preserve shape. We introduce shape-preserving approximation methods that stabilize value function iteration, and are generally faster than previous stable methods such as piecewise linear interpolation.     

Constructing composite search directions with parameters in quadratic interpolation models

In this paper, we introduce the weighted composite search directions to develop the quadratic approximation methods. The purpose is to make fully use of the information disclosed by the former steps to construct possibly more promising directions. Firstly, we obtain these composite directions based on the properties of simplex methods and use them to construct trust region subproblems. Then, these subproblems are solved in the algorithm to find solutions of some benchmark optimization problems. The computation results show that for most tested problems, the improved quadratic approximation methods can obviously reduce the number of function evaluations compared with the existing ones. Finally, we conclude that the algorithm will perform better if the composite directions approach the previous steepest descent direction of the sub-simplex so far. We also point out the potential applications of this improved quadratic interpolation method in business intelligence systems.     

Learning mixtures of polynomials of multidimensional probability densities from data using B-spline interpolation

Non-parametric density estimation is an important technique in probabilistic modeling and reasoning with uncertainty. We present a method for learning mixtures of polynomials (MoPs) approximations of one-dimensional and multidimensional probability densities from data. The method is based on basis spline interpolation, where a density is approximated as a linear combination of basis splines. We compute maximum likelihood estimators of the mixing coefficients of the linear combination. The Bayesian information criterion is used as the score function to select the order of the polynomials and the number of pieces of the MoP. The method is evaluated in two ways. First, we test the approximation fitting. We sample artificial datasets from known one-dimensional and multidimensional densities and learn MoP approximations from the datasets. The quality of the approximations is analyzed according to different criteria, and the new proposal is compared with MoPs learned with Lagrange interpolation and mixtures of truncated basis functions. Second, the proposed method is used as a non-parametric density estimation technique in Bayesian classifiers. Two of the most widely studied Bayesian classifiers, i.e., the naive Bayes and tree-augmented naive Bayes classifiers, are implemented and compared. Results on real datasets show that the non-parametric Bayesian classifiers using MoPs are comparable to the kernel density-based Bayesian classifiers. We provide a free R package implementing the proposed methods.     

Meshless method with ridge basis functions

Meshless collocation methods for the numerical solutions of PDEs are increasingly adopted due to their advantages including efficiency and flexibility, and radial basis functions are popularly employed to represent the solutions of PDEs. Motivated by the advantages of ridge basis function representation of a given function, such as the connection to neural network, fast convergence as the number of terms is increased, better approximation effects and various applications in engineering problems, a meshless method is developed based on the collocation method and ridge basis function interpolation. This method is a truly meshless technique without mesh discretization: it neither needs the computation of integrals, nor requires a partition of the region and its boundary. Moreover, the method is applied to elliptic equations to examine its appropriateness, numerical results are compared to that obtained from other (meshless) methods, and influence factors of accuracy for numerical solutions are analyzed.     

MODIFIED NEWTON AND SECANT METHODS FOR SOLVING AN ORDER O(h~4) FINITE-DIFFERENCE PROBLEM

1IntroductionSolution0fn0nlineartwo-pointb0undaryvaIuepr0blems(NBVP)canoftenbefoundbythefinite-differenceappr0ach,wheref(t,y)isaconti-nuousfunction.Collatz[1]firstpresentedanapproximation0ffourthorderfwherey=(y1,''tyN)',g=(g1,'-,gN)'andtherelativepaperscanals0beseenin[2].Toestablishthesolutionof(1.l),thef0llowingmethodscanbeusedfnonlinearsuccessiverelaxati0n(NSOR)method[3],thedifferenceNewt0nmethod(0rNewtonmethod)[4],therelativesparsenonlinearequationpr0blemscanals0beseenin[5-8]-lnthisp…     

Reproducing Kernel Hilbert Spaces and fractal interpolation

Reproducing Kernel Hilbert Spaces (RKHSs) are a very useful and powerful tool of functional analysis with application in many diverse paradigms, such as multivariate statistics and machine learning. Fractal interpolation, on the other hand, is a relatively recent technique that generalizes traditional interpolation through the introduction of self-similarity. In this work we show that the functional space of any family of (recurrent) fractal interpolation functions ((R)FIFs) constitutes an RKHS with a specific associated kernel function, thus, extending considerably the toolbox of known kernel functions and introducing fractals to the RKHS world. We also provide the means for the computation of the kernel function that corresponds to any specific fractal RKHS and give several examples.     

Efficient Global Optimization of Expensive Black-Box Functions

In many engineering optimization problems, the number of function evaluations is severely limited by time or cost. These problems pose a special challenge to the field of global optimization, since existing methods often require more function evaluations than can be comfortably afforded. One way to address this challenge is to fit response surfaces to data collected by evaluating the objective and constraint functions at a few points. These surfaces can then be used for visualization, tradeoff analysis, and optimization. In this paper, we introduce the reader to a response surface methodology that is especially good at modeling the nonlinear, multimodal functions that often occur in engineering. We then show how these approximating functions can be used to construct an efficient global optimization algorithm with a credible stopping rule. The key to using response surfaces for global optimization lies in balancing the need to exploit the approximating surface (by sampling where it is minimized) with the need to improve the approximation (by sampling where prediction error may be high). Striking this balance requires solving certain auxiliary problems which have previously been considered intractable, but we show how these computational obstacles can be overcome.     

曲边三角形及曲边四边形上的混合函数插值格式

一、引言 二元函数在标准三角形上的混合函数插值格式在许多文献,例如,Birkhofft,Barnhill,Gordon及Gregory等的文章中都有讨论。在三角形周边上对高阶偏导数进行插值,而且计算比较简单的是J.A.Gregory的文章中所给出的一种混合函数插值格式。这种格式是由简单函数的线性组合所构成的,而且格式是对称的,因此计算比较简便。但是J.A.Gregory只是对直边三角形给出了格式。本文企图推广Gregory的格式,给出曲边三角形上对高阶偏导数进行插值的插值格式。我们还进一步给出了曲边四边形上     

A new family of conjugate gradient methods

In this paper we develop a new class of conjugate gradient methods for unconstrained optimization problems. A new nonmonotone line search technique is proposed to guarantee the global convergence of these conjugate gradient methods under some mild conditions. In particular, Polak–Ribiére–Polyak and Liu–Storey conjugate gradient methods are special cases of the new class of conjugate gradient methods. By estimating the local Lipschitz constant of the derivative of objective functions, we can find an adequate step size and substantially decrease the function evaluations at each iteration. Numerical results show that these new conjugate gradient methods are effective in minimizing large-scale non-convex non-quadratic functions.     

基于三次样条插值函数的非线性动力系统数值求解

三次样条插值函数具有良好的收敛性、稳定性与二阶光滑性.研究了借助三次样条插值函数构造的非线性动力系统数值求解方法,分析了该方法与已有的非线性动力系统数值求解方法的优缺点,刻画了误差估计且给出了数值算例.结果表明基于三次样条插值函数构造的数值方法比已有的方法收敛速度快、逼近精度高且能够很好地逼近非线性动力系统的解析解.     

A class of three-point root-solvers of optimal order of convergence

The construction of a class of three-point methods for solving nonlinear equations of the eighth order is presented. These methods are developed by combining fourth order methods from the class of optimal two-point methods and a modified Newton’s method in the third step, obtained by a suitable approximation of the first derivative based on interpolation by a nonlinear fraction. It is proved that the new three-step methods reach the eighth order of convergence using only four function evaluations, which supports the Kung-Traub conjecture on the optimal order of convergence. Numerical examples for the selected special cases of two-step methods are given to demonstrate very fast convergence and a high computational efficiency of the proposed multipoint methods. Some computational aspects and the comparison with existing methods are also included.     

伪二元函数的Hermite插值

将一元函数的Hermite插值方法与伪二元函数结合,得到了伪二元函数的Hermite插值函数,并对插值函数进行了误差分析,最后给出了一个实例.     

Effective numerical evaluation of the double Hilbert transform

In this paper, we propose two methods to compute the double Hilbert transform of periodic functions. First, we establish the quadratic formula of trigonometric interpolation type for double Hilbert transform and obtain an estimation of the remainder. We call this method 2D mechanical quadrature method (2D-MQM). Numerical experiments show that 2D-MQM outperforms the library function “hilbert” in Matlab when the values of the functions being handled are very large or approach to infinity. Second, we propose a complex analytic method to calculate the double Hilbert transform, which is based on the 2D adaptive Fourier decomposition, and the method is called as 2D-HAFD. In contrast to the pointwise approximation, 2D-HAFD provides explicit rational functional approximations and is valid for all signals of finite energy.     

A Radial Basis Function Method for Global Optimization

We introduce a method that aims to find the global minimum of a continuous nonconvex function on a compact subset of . It is assumed that function evaluations are expensive and that no additional information is available. Radial basis function interpolation is used to define a utility function. The maximizer of this function is the next point where the objective function is evaluated. We show that, for most types of radial basis functions that are considered in this paper, convergence can be achieved without further assumptions on the objective function. Besides, it turns out that our method is closely related to a statistical global optimization method, the P-algorithm. A general framework for both methods is presented. Finally, a few numerical examples show that on the set of Dixon-Szegö test functions our method yields favourable results in comparison to other global optimization methods.     

Decent flow methods for inverse Sturm–Liouville problem

In this paper, we propose three numerical methods for the inverse Sturm–Liouville operator in impedance form. We use a finite difference method to discretize the Sturm–Liouville operator and expand the impedance function with some basis functions. The correction technique is discussed. By solving an un-weighted least squares problem, we find an approximation to the impedance function. Numerical experiments are presented to show the accuracy and stability of the numerical methods.     

THE SMOOTHNESS AND DIMENSION OF FRACTAL INTERPOLATION FUNCTIONS

In this paper, we investigate the smoothness of non-equidistant fractal interpolation functions We obtain the Holder exponents of such fractal interpolation functions by using the technique of operator approximation. At last, We discuss the series expressiong of these functions and give a Box-counting dimension estimation of “critical” fractal interpohltion functions by using our smoothness results.