Derivative free two-point methods with and without memory for solving nonlinear equations

Two families of derivative free two-point iterative methods for solving nonlinear equations are constructed. These methods use a suitable parametric function and an arbitrary real parameter. It is proved that the first family has the convergence order four requiring only three function evaluations per iteration. In this way it is demonstrated that the proposed family without memory supports the Kung-Traub hypothesis (1974) on the upper bound 2ⁿ of the order of multipoint methods based on n + 1 function evaluations. Further acceleration of the convergence rate is attained by varying a free parameter from step to step using information available from the previous step. This approach leads to a family of two-step self-accelerating methods with memory whose order of convergence is at least and even in special cases. The increase of convergence order is attained without any additional calculations so that the family of methods with memory possesses a very high computational efficiency. Numerical examples are included to demonstrate exceptional convergence speed of the proposed methods using only few function evaluations.     

A class of Steffensen type methods with optimal order of convergence

In this paper, a family of Steffensen type methods of fourth-order convergence for solving nonlinear smooth equations is suggested. In the proposed methods, a linear combination of divided differences is used to get a better approximation to the derivative of the given function. Each derivative-free member of the family requires only three evaluations of the given function per iteration. Therefore, this class of methods has efficiency index equal to 1.587. Kung and Traub conjectured that the order of convergence of any multipoint method without memory cannot exceed the bound 2^d-1, where d is the number of functional evaluations per step. The new class of methods agrees with this conjecture for the case d=3. Numerical examples are made to show the performance of the presented methods, on smooth and nonsmooth equations, and to compare with other ones.     

A new family of eighth-order iterative methods for solving nonlinear equations

A family of eighth-order iterative methods with four evaluations for the solution of nonlinear equations is presented. Kung and Traub conjectured that an iteration method without memory based on n evaluations could achieve optimal convergence order 2^n-1. The new family of eighth-order methods agrees with the conjecture of Kung-Traub for the case n=4. Therefore this family of methods has efficiency index equal to 1.682. Numerical comparisons are made with several other existing methods to show the performance of the presented methods.     

A family of optimal three-point methods for solving nonlinear equations using two parametric functions

Using an interactive approach which combines symbolic computation and Taylor’s series, a wide family of three-point iterative methods for solving nonlinear equations is constructed. These methods use two suitable parametric functions at the second and third step and reach the eighth order of convergence consuming only four function evaluations per iteration. This means that the proposed family supports the Kung-Traub hypothesis (1974) on the upper bound 2^m of the order of multipoint methods based on m + 1 function evaluations, providing very high computational efficiency. Different methods are obtained by taking specific parametric functions. The presented numerical examples demonstrate exceptional convergence speed with only few function evaluations.     

New modifications of Potra-Pták’s method with optimal fourth and eighth orders of convergence

In this paper, we present two new iterative methods for solving nonlinear equations by using suitable Taylor and divided difference approximations. Both methods are obtained by modifying Potra-Pták’s method trying to get optimal order. We prove that the new methods reach orders of convergence four and eight with three and four functional evaluations, respectively. So, Kung and Traub’s conjecture Kung and Traub (1974) [2], that establishes for an iterative method based on n evaluations an optimal order p=2ⁿ⁻¹ is fulfilled, getting the highest efficiency indices for orders p=4 and p=8, which are 1.587 and 1.682.We also perform different numerical tests that confirm the theoretical results and allow us to compare these methods with Potra-Pták’s method from which they have been derived, and with other recently published eighth-order methods.     

A New Iterative Method for the Computation of the Solutions of Nonlinear Equations

Recently, by Costabile, Gualtieri and Serra (1999), an iterative method was presented for the computation of zeros of C ¹ functions. This method combines the assured convergence of the bisection-like algorithms with a superlinear convergence speed which characterizes Newton-like methods. The order of the method and the cost per iteration is exactly equivalent to the Newton method. In this paper we present a new iterative method for the computation of the zeros of C ¹ functions with the same properties of convergence as the method proposed by Costabile, Gualtieri and Serra (1999) but with order 1+ $\sqrt 2 $ ?2.41 for C ³ functions. Compared with the methods of order 1+ $\sqrt 2 $ presented by Traub (1964), our methods ensure global convergence. Then we consider a generalization of this procedure which gives a class of methods of order (n+ $\sqrt {n^2 + 4} $ )/2, where n is the degree of the approximating polynomial, with one-point iteration functions with memory. Finally a number of numerical tests are performed. The numerical results seem to show that, at least on a set of problems, the new methods work better than the methods proposed, and, therefore, than both the Newton and Alefeld and Potra (1992) methods.     

Construction of optimal order nonlinear solvers using inverse interpolation

There is a vast literature on finding simple roots of nonlinear equations by iterative methods. These methods can be classified by order, by the information used or by efficiency. There are very few optimal methods, that is methods of order 2^m requiring m + 1 function evaluations per iteration. Here we give a general way to construct such methods by using inverse interpolation and any optimal two-point method. The presented optimal multipoint methods are tested on numerical examples and compared to existing methods of the same order of convergence.     

A Constructive Approach to Strong Tractability Using Quasi-Monte Carlo Algorithms

We prove in a constructive way that multivariate integration in appropriate weighted Sobolev classes is strongly tractable and the ε-exponent of strong tractability is 1 (which is the best-possible value) under a stronger assumption than Sloan and Woźniakowski's assumption. We show that quasi-Monte Carlo algorithms based on the Sobol sequence and Halton sequence achieve the convergence order O(n^−1+δ) for any δ>0 independent of the dimension with a worst-case deterministic guarantee (where n is the number of function evaluations). This implies that quasi-Monte Carlo algorithms based on the Sobol and Halton sequences converge faster and therefore are superior to Monte Carlo methods independent of the dimension for integrands in suitable weighted Sobolev classes.     

On the guaranteed convergence of new two-point root-finding methods for polynomial zeros

We presented new two-point methods for the simultaneous approximation of all n simple (real or complex) zeros of a polynomial of degree n. We proved that the R-order of convergence of the total-step version is three. Moreover, computationally verifiable initial conditions that guarantee the convergence of one of the proposed methods are stated. These conditions are stated in the spirit of Smale’s point estimation theory; they depend only on available data, the polynomial coefficients, polynomial degree n and initial approximations \(x_{1}^{(0)},\ldots ,x_{n}^{(0)}\) , which is of practical importance. Using the Gauss-Seidel approach we state the corresponding single-step version and consequently its prove that the lower bound of its R-order of convergence is at least 2 + y _n > 3, where y _n ∈ (1, 2) is the unique positive root of the equation y ⁿ ? y ? 2 = 0. Two numerical examples are given to demonstrate the convergence behavior of the considered methods, including global convergence.     

An efficient fourth order weighted-Newton method for systems of nonlinear equations

In this paper, we develop a fourth order method for solving the systems of nonlinear equations. The algorithm is composed of two weighted-Newton steps and requires the information of one function and two first Fréchet derivatives. Therefore, for a system of n equations, per iteration it uses n?+?2n ² evaluations. Computational efficiency is compared with Newton’s method and some other recently published methods. Numerical tests are performed, which confirm the theoretical results. From the comparison with known methods it is observed that present method shows good stability and robustness.     

Central limit asymptotics for shifts of finite type

We study the rate of convergence and asymptotic expansions in the central limit theorem for the class of Hölder continuous functions on a shift of finite type endowed with a stationary equilibrium state. It is shown that the rate of convergence in the theorem isO(n ^?1/2) and when the function defines a non-lattice distribution an asymptotic expansion to the order ofo(n ^?1/2) is given. Higher-order expansions can be obtained for a subclass of functions. We also make a remark on the central limit theorem for (closed) orbital measures.     

Modified Kantorovich theorem and asymptotic approximations of solutions to singularly perturbed systems of ordinary differential equations

The functional equation f(x,ε) = 0 containing a small parameter ε and admitting regular and singular degeneracy as ε → 0 is considered. By the methods of small parameter, a function x _n ⁰(ε) satisfying this equation within a residual error of O(ε ⁿ⁺¹) is found. A modified Newton’s sequence starting from the element x _n ⁰(ε) is constructed. The existence of the limit of Newton’s sequence is based on the NK theorem proven in this work (a new variant of the proof of the Kantorovich theorem substantiating the convergence of Newton’s iterative sequence). The deviation of the limit of Newton’s sequence from the initial approximation x _n ⁰(ε) has the order of O(ε ⁿ⁺¹), which proves the asymptotic character of the approximation x _n ⁰(ε). The method proposed is implemented in constructing an asymptotic approximation of a system of ordinary differential equations on a finite or infinite time interval with a small parameter multiplying the derivatives, but it can be applied to a wider class of functional equations with a small parameters.     

Two- and three-point with memory methods for solving nonlinear equations

The main objective and inspiration in the construction of two- and three-point with memory method is to attain the utmost computational efficiency, without any additional function evaluations. At this juncture, we have modified the existing fourth and eighth order without memory method with optimal order of convergence by means of different approximations of self-accelerating parameters. The parameters have been calculated by Hermite interpolating polynomial, which accelerates the order of convergence of the without memory methods. In particular, the R-order convergence of the proposed two- and three-step with memory methods is increased from four to five and eight to ten. One more advantage of these methods is that the condition f′(x) ≠ 0, in the neighborhood of the required root, imposed on Newton’s method, can be removed. Numerical comparison is also stated to confirm the theoretical results.     

Algorithm for forming derivative-free optimal methods

We develop a simple yet effective and applicable scheme for constructing derivative free optimal iterative methods, consisting of one parameter, for solving nonlinear equations. According to the, still unproved, Kung-Traub conjecture an optimal iterative method based on k+1 evaluations could achieve a maximum convergence order of $2^{k}$ . Through the scheme, we construct derivative free optimal iterative methods of orders two, four and eight which request evaluations of two, three and four functions, respectively. The scheme can be further applied to develop iterative methods of even higher orders. An optimal value of the free-parameter is obtained through optimization and this optimal value is applied adaptively to enhance the convergence order without increasing the functional evaluations. Computational results demonstrate that the developed methods are efficient and robust as compared with many well known methods.     

An optimal Steffensen-type family for solving nonlinear equations

In this paper, a general family of Steffensen-type methods with optimal order of convergence for solving nonlinear equations is constructed by using Newton’s iteration for the direct Newtonian interpolation. It satisfies the conjecture proposed by Kung and Traub [H.T. Kung, J.F. Traub, Optimal order of one-point and multipoint iteration, J. Assoc. Comput. Math. 21 (1974) 634-651] that an iterative method based on m evaluations per iteration without memory would arrive at the optimal convergence of order 2^m−1. Its error equations and asymptotic convergence constants are obtained. Finally, it is compared with the related methods for solving nonlinear equations in the numerical examples.     

On convergence analysis of space homeomorphisms

Various theorems on convergence of general spatial homeomorphisms are proved and, on this basis, theorems on convergence and compactness for classes of the so-called ring Q-homeomorphisms are obtained. In particular, it is established that a family of all ring Q-homeomorphisms f in ? ⁿ fixing two points is compact provided that the function Q is of finite mean oscillation. The corresponding applications have been given to mappings in the Sobolev classes W _loc ^1,p for the case p > n ? 1.     

Random Gradient-Free Minimization of Convex Functions

In this paper, we prove new complexity bounds for methods of convex optimization based only on computation of the function value. The search directions of our schemes are normally distributed random Gaussian vectors. It appears that such methods usually need at most n times more iterations than the standard gradient methods, where n is the dimension of the space of variables. This conclusion is true for both nonsmooth and smooth problems. For the latter class, we present also an accelerated scheme with the expected rate of convergence \(O\Big ({n^2 \over k^2}\Big )\), where k is the iteration counter. For stochastic optimization, we propose a zero-order scheme and justify its expected rate of convergence \(O\Big ({n \over k^{1/2}}\Big )\). We give also some bounds for the rate of convergence of the random gradient-free methods to stationary points of nonconvex functions, for both smooth and nonsmooth cases. Our theoretical results are supported by preliminary computational experiments.     

On the convergence of Filon quadrature

We analyze the convergence behavior of Filon-type quadrature rules by making explicit the dependence on both k, the parameter that controls the oscillatory behavior of the integrand, and n, the number of function evaluations. We provide explicit conditions on the domain of analyticity of the integrand to ensure convergence for n→∞.     

Improving an estimate of the convergence rate of the seidel method by selecting the optimal order of equations in the system of linear algebraic equations

The Seidel method for solving a system of linear algebraic equations and an estimate of its convergence rate are considered. It is proposed to change the order of equations. It is shown that the method described in Faddeevs’ book Computational Methods of Linear Algebra can deteriorate the convergence rate estimate rather than improve it. An algorithm for establishing the optimal order of equations is proposed, and its validity is proved. It is shown that the computational complexity of the reordering is 2n ² additions and (12)n ² divisions. Numerical results for random matrices of order 100 are presented that confirm the proposed improvement.     

Contraction mappings in interval analysis

Under certain conditions, the contraction mapping fixed point theorem guarantees the convergence of the iterationx _i+1=f(x _i ) toward a fixed point of the functionf:R ⁿ →R ⁿ. When an interval extensionF off is used in a similar iteration scheme to obtain a sequence of interval vectors these conditions need not provide convergence to a degenerate interval vector representing the fixed point, even if the width of the initial interval vector is chosen arbitrarily small. We give a sufficient condition on the extensionF in order that the convergence is guaranteed. The centered form of Moore satisfies this condition.