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.     

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.     

Three-step iterative methods with eighth-order convergence for solving nonlinear equations

A family of eighth-order iterative methods for the solution of nonlinear equations is presented. The new family of eighth-order methods is based on King’s fourth-order methods and the family of sixth-order iteration methods developed by Chun et al. Per iteration the new methods require three evaluations of the function and one evaluation of its first derivative. Therefore this family of methods has the efficiency index which equals 1.682. Kung and Traub conjectured that a multipoint iteration without memory based on n$n$ evaluations could achieve optimal convergence order 2ⁿ⁻¹$2^{n-1}$. Thus we provide a new example which agrees with the conjecture of Kung–Traub for n=4$n=4$. Numerical comparisons are made to show the performance of the presented methods.     

New eighth-order iterative methods for solving nonlinear equations

In this paper, three new families of eighth-order iterative methods for solving simple roots of nonlinear equations are developed by using weight function methods. Per iteration these iterative methods require three evaluations of the function and one evaluation of the first derivative. This implies that the efficiency index of the developed methods is 1.682, which is optimal according to Kung and Traub’s conjecture [7] for four function evaluations per iteration. Notice that Bi et al.’s method in [2] and [3] are special cases of the developed families of methods. In this study, several new examples of eighth-order methods with efficiency index 1.682 are provided after the development of each family of methods. Numerical comparisons are made with several other existing methods to show the performance of the presented methods.     

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.     

A new family of modified Ostrowski’s methods with accelerated eighth order convergence

Based on Ostrowski’s fourth order method, we derive a family of eighth order methods for the solution of nonlinear equations. In terms of computational cost the family requires three evaluations of the function and one evaluation of first derivative. Therefore, the efficiency index of the present methods is 1.682 which is better than the efficiency index 1.587 of Ostrowski’s method. Kung and Traub conjectured that multipoint iteration methods without memory based on n evaluations have optimal order 2 ^n − 1. Thus, the family agrees with Kung–Traub conjecture for the case n = 4. The efficacy of the present methods is tested on a number of numerical examples. It is observed that our methods are competitive with other similar robust methods and very effective in high precision computations.     

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.     

A family of three-point methods of optimal order for solving nonlinear equations

A family of three-point iterative methods for solving nonlinear equations is constructed using a suitable parametric function and two arbitrary real parameters. It is proved that these methods have the convergence order eight requiring only four function evaluations per iteration. In this way it is demonstrated that the proposed class of methods supports the Kung-Traub hypothesis (1974) [3] on the upper bound 2ⁿ of the order of multipoint methods based on n+1 function evaluations. Consequently, this class of root solvers possesses very high computational efficiency. Numerical examples are included to demonstrate exceptional convergence speed with only few function evaluations.     

Some modifications of Newton’s method with higher-order convergence for solving nonlinear equations

In [YoonMee Ham etal., Some higher-order modifications of Newton’s method for solving nonlinear equations, J. Comput. Appl. Math., 222 (2008) 477–486], some higher-order modifications of Newton’s method for solving nonlinear equations are constructed. But if p=2$p=2$, then their main theorem did not hold. In this paper, we first give an example to show that YoonMee Ham etal.’s methods are not always correct in the case p=2$p=2$. Then, we present the condition that H(x,y)$H(x,y)$ should satisfy such that the order of convergence increases three or four or five units. Per iteration they only need two additional function evaluations to increase the order. Based on this and multi-step Newton’s scheme, we give further modifications of the method to obtain higher-order convergent iterative methods. Finally, several examples are given to demonstrate the efficiency and performance of our modified methods and compare them with some other 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.     

Zero-finder methods derived from Obreshkov’s techniques

In this paper two families of zero-finding iterative methods for solving nonlinear equations f(x)=0 are presented. The key idea to derive them is to solve an initial value problem applying Obreshkov-like techniques. More explicitly, Obreshkov’s methods have been used to numerically solve an initial value problem that involves the inverse of the function f that defines the equation. Carrying out this procedure, several methods with different orders of local convergence have been obtained. An analysis of the efficiency of these methods is given. Finally we introduce the concept of extrapolated computational order of convergence with the aim of numerically test the given methods. A procedure for the implementation of an iterative method with an adaptive multi-precision arithmetic is also presented.     

Quadrature Based Optimal Iterative Methods with Applications in High-Precision Computing

We present a simple yet effective and applicable scheme, based on quadrature, for constructing optimal iterative methods. According to the, still unproved, Kung-Traub conjecture an optimal iterative method based on $n+1$ evaluations could achieve a maximum convergence order of $2^n$. Through quadrature, we develop optimal iterative methods of orders four and eight. The scheme can further be applied to develop iterative methods of even higher orders. Computational results demonstrate that the developed methods are efficient as compared with many well known methods.     

Three-step iterative methods with optimal eighth-order convergence

In this paper, based on Ostrowski’s method, a new family of eighth-order methods for solving nonlinear equations is derived. In terms of computational cost, each iteration of these methods requires three evaluations of the function and one evaluation of its first derivative, so that their efficiency indices are 1.682, which is optimal according to Kung and Traub’s conjecture. Numerical comparisons are made to show the performance of the new family.     

Derivative free multipoint iterative methods for simple and multiple roots

A one-parameter family of derivative free multipoint iterative methods of orders three and four are derived for finding the simple and multiple roots off(x)=0. For simple roots, the third order methods require three function evaluations while the fourth order methods require four function evaluations. For multiple roots, the third order methods require six function evaluations while the fourth order methods require eight function evaluations. Numerical results show the robustness of these methods.     

Chebyshev-type methods and preconditioning techniques

Recently, a Newton’s iterative method is attracting more and more attention from various fields of science and engineering. This method is generally quadratically convergent. In this paper, some Chebyshev-type methods with the third order convergence are analyzed in detail and used to compute approximate inverse preconditioners for solving the linear system Ax = b. Theoretic analysis and numerical experiments show that Chebyshev’s method is more effective than Newton’s one in the case of constructing approximate inverse preconditioners.     

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.     

Attracting cycles for the relaxed Newton’s method

We study the relaxed Newton’s method applied to polynomials. In particular, we give a technique such that for any n≥2, we may construct a polynomial so that when the method is applied to a polynomial, the resulting rational function has an attracting cycle of period n. We show that when we use the method to extract radicals, the set consisting of the points at which the method fails to converge to the roots of the polynomial p(z)=z^m−c (this set includes the Julia set) has zero Lebesgue measure. Consequently, iterate sequences under the relaxed Newton’s method converge to the roots of the preceding polynomial with probability one.     

Approximate preservation of quadratic first integrals by explicit Runge–Kutta methods

The approximate preservation of quadratic first integrals (QFIs) of differential systems in the numerical integration with Runge–Kutta (RK) methods is studied. Conditions on the coefficients of the RK method to preserve all QFIs up to a given order are obtained, showing that the pseudo-symplectic methods studied by Aubry and Chartier (BIT 98(3):439–461, 1998) of algebraic order p preserve QFIs with order q = 2p. An expression of the error of conservation of QFIs by a RK method is given, and a new explicit six-stage formula with classical order four and seventh order of QFI-conservation is obtained by choosing their coefficients so that they minimize both local truncation and conservation errors. Several formulas with algebraic orders 3 and 4 and different orders of conservation have been tested with some problems with quadratic and general first integrals. It is shown that the new fourth-order explicit method preserves much better the qualitative properties of the flow than the standard fourth-order RK method at the price of two extra function evaluations per step and it is a practical and efficient alternative to the fully implicit methods required for a complete preservation of QFIs.     

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.     

Spaces of orders and their Turing degree spectra

We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora’s (2004) [28] investigation of orders on groups in topology and Solomon’s (2002) [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group F_n of rank n>1 has a bi-order in every Turing degree.