A family of multi-point iterative methods for solving systems of nonlinear equations

We extend to n$n$-dimensional case a known multi-point family of iterative methods for solving nonlinear equations. This family includes as particular cases some well known and also some new methods. The main advantage of these methods is they have order three or four and they do not require the evaluation of any second or higher order Fréchet derivatives. A local convergence analysis and numerical examples are provided.     

Third-order iterative methods with applications to Hammerstein equations: A unified approach

The geometrical interpretation of a family of higher order iterative methods for solving nonlinear scalar equations was presented in [S. Amat, S. Busquier, J.M. Gutiérrez, Geometric constructions of iterative functions to solve nonlinear equations. J. Comput. Appl. Math. 157(1) (2003) 197-205]. This family includes, as particular cases, some of the most famous third-order iterative methods: Chebyshev methods, Halley methods, super-Halley methods, C-methods and Newton-type two-step methods. The aim of the present paper is to analyze the convergence of this family for equations defined between two Banach spaces by using a technique developed in [J.A. Ezquerro, M.A. Hernández, Halley’s method for operators with unbounded second derivative. Appl. Numer. Math. 57(3) (2007) 354-360]. This technique allows us to obtain a general semilocal convergence result for these methods, where the usual conditions on the second derivative are relaxed. On the other hand, the main practical difficulty related to the classical third-order iterative methods is the evaluation of bilinear operators, typically second-order Fréchet derivatives. However, in some cases, the second derivative is easy to evaluate. A clear example is provided by the approximation of Hammerstein equations, where it is diagonal by blocks. We finish the paper by applying our methods to some nonlinear integral equations of this type.     

On diagonally structured problems in unconstrained optimization using an inexact super Halley method

We consider solving the unconstrained minimization problem using an iterative method derived from the third order super Halley method. Each iteration of the super Halley method requires the solution of two linear systems of equations. We show a practical implementation using an iterative method to solve the linear systems. This paper introduces an array of arrays (jagged) data structure for storing the second and third derivative of a multivariate function and suitable termination criteria for the (inner) iterative method to achieve a cubic rate of convergence. Using a jagged compressed diagonal storage of the Hessian matrices and for the tensor, numerical results show that storing the diagonals are more efficient than the row or column oriented approach when we use an iterative method for solving the linear systems of equations.     

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.     

A biparametric family of optimally convergent sixteenth-order multipoint methods with their fourth-step weighting function as a sum of a rational and a generic two-variable function

A biparametric family of four-step multipoint iterative methods of order sixteen to numerically solve nonlinear equations are developed and their convergence properties are investigated. The efficiency indices of these methods are all found to be 16^1/5≈1.741101, being optimally consistent with the conjecture of Kung-Traub. Numerical examples as well as comparison with existing methods developed by Kung-Traub and Neta are demonstrated to confirm the developed theory in this paper.     

On new higher order families of simultaneous methods for finding polynomial zeros

Two one parameter families of iterative methods for the simultaneous determination of simple zeros of algebraic polynomials are presented. The construction of these families are based on a one parameter family of the third order for finding a single root of nonlinear equation f(x)=0. Some previously derived simultaneous methods can be obtained from the presented families as special cases. We prove that the local convergence of the proposed families is of the order four. Numerical results are included to demonstrate the convergence properties of considered methods.     

On generalized multipoint root-solvers with memory

The improved versions of the Kung–Traub family and the Zheng–Li–Huang family of n$n$-point derivative free methods for solving nonlinear equations are proposed. The convergence speed of the modified families is considerably accelerated by employing a self-correcting parameter. This parameter is calculated in each iteration using information from the current and previous iteration so that the proposed families can be regarded as the families with memory. The increase of convergence order is attained without any additional function evaluations meaning that these families with memory possess high computational efficiency. Numerical examples are included to confirm theoretical results and demonstrate convergence behaviour of the proposed methods.     

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

In this paper we consider constructing some higher-order modifications of Newton’s method for solving nonlinear equations which increase the order of convergence of existing iterative methods by one or two or three units. This construction can be applied to any iteration formula, and per iteration the resulting methods add only one additional function evaluation to increase the order. Some illustrative examples are provided and several numerical results are given to show the performance of the presented methods.     

An efficient higher order family of root finders

A one parameter family of iterative methods for the simultaneous approximation of simple complex zeros of a polynomial, based on a cubically convergent Hansen–Patrick's family, is studied. We show that the convergence of the basic family of the fourth order can be increased to five and six using Newton's and Halley's corrections, respectively. Since these corrections use the already calculated values, the computational efficiency of the accelerated methods is significantly increased. Further acceleration is achieved by applying the Gauss–Seidel approach (single-step mode). One of the most important problems in solving nonlinear equations, the construction of initial conditions which provide both the guaranteed and fast convergence, is considered for the proposed accelerated family. These conditions are computationally verifiable; they depend only on the polynomial coefficients, its degree and initial approximations, which is of practical importance. Some modifications of the considered family, providing the computation of multiple zeros of polynomials and simple zeros of a wide class of analytic functions, are also studied. Numerical examples demonstrate the convergence properties of the presented family of root-finding methods.     

On Schröder’s families of root-finding methods

Schröder’s methods of the first and second kind for solving a nonlinear equation f(x)=0, originally derived in 1870, are of great importance in the theory and practice of iteration processes. They were rediscovered several times and expressed in different forms during the last 130 years. It was proved in the paper of Petkovi? and Herceg (1999) [7] that even seven families of iteration methods for solving nonlinear equations are mutually equivalent. In this paper we show that these families are also equivalent to another four families of iteration methods and find that all of them have the origin in Schröder’s generalized method (of the second kind) presented in 1870. In the continuation we consider Smale’s open problem from 1994 about possible link between Schröder’s methods of the first and second kind and state the link in a simple way.     

Point estimation and some applications to iterative methods

We consider one of the crucial problems in solving polynomial equations concerning the construction of such initial conditions which provide a safe convergence of simultaneous zero-finding methods. In the first part we deal with the localization of polynomial zeros using disks in the complex plane. These disks are used for the construction of initial inclusion disks which, under suitable conditions, provide the convergence of the Gargantini-Henrici interval method. They also play a key role in the convergence analysis of the fourth order Ehrlich-Aberth method with Newton's correction for the simultaneous approximation of all zeros of a polynomial. For this method we state the initial condition which enables the safe convergence. The initial condition is computationally verifiable since it depends only on initial approximations, which is of practical importance.     

Improvements of the efficiency of some three-step iterative like-Newton methods

An improvement of the local order of convergence is presented to increase the efficiency of the iterative method with an appropriate number of evaluations of the function and its derivative. The third and fourth order of known two-step like Newton methods have been improved and the efficiency has also been increased.     

Improving order and efficiency: Composition with a modified Newton’s method

In this paper a zero-finding technique for solving nonlinear equations more efficiently than they usually are with traditional iterative methods in which the order of convergence is improved is presented. The key idea in deriving this procedure is to compose a given iterative method with a modified Newton’s method that introduces just one evaluation of the function. To carry out this procedure some classical methods with different orders of convergence are used to obtain new methods that can be generalized in Banach spaces.     

Construction of Newton-like iteration methods for solving nonlinear equations

In this paper, we present a simple, and yet powerful and easily applicable scheme in constructing the Newton-like iteration formulae for the computation of the solutions of nonlinear equations. The new scheme is based on the homotopy analysis method applied to equations in general form equivalent to the nonlinear equations. It provides a tool to develop new Newton-like iteration methods or to improve the existing iteration methods which contains the well-known Newton iteration formula in logic; those all improve the Newton method. The orders of convergence and corresponding error equations of the obtained iteration formulae are derived analytically or with the help of Maple. Some numerical tests are given to support the theory developed in this paper.     

Weak second order S-ROCK methods for Stratonovich stochastic differential equations

It is well known that the numerical solution of stiff stochastic ordinary differential equations leads to a step size reduction when explicit methods are used. This has led to a plethora of implicit or semi-implicit methods with a wide variety of stability properties. However, for stiff stochastic problems in which the eigenvalues of a drift term lie near the negative real axis, such as those arising from stochastic partial differential equations, explicit methods with extended stability regions can be very effective. In the present paper our aim is to derive explicit Runge–Kutta schemes for non-commutative Stratonovich stochastic differential equations, which are of weak order two and which have large stability regions. This will be achieved by the use of a technique in Chebyshev methods for ordinary differential equations.     

Point estimation of simultaneous methods for solving polynomial equations: A survey (II)

The construction of computationally verifiable initial conditions which provide both the guaranteed and fast convergence of the numerical root-finding algorithm is one of the most important problems in solving nonlinear equations. Smale's “point estimation theory” from 1981 was a great advance in this topic; it treats convergence conditions and the domain of convergence in solving an equation f(z)=0$f(z)=0$ using only the information of f   at the initial point _z0$z_0$. The study of a general problem of the construction of initial conditions of practical interest providing guaranteed convergence is very difficult, even in the case of algebraic polynomials. In the light of Smale's point estimation theory, an efficient approach based on some results concerning localization of polynomial zeros and convergent sequences is applied in this paper to iterative methods for the simultaneous determination of simple zeros of polynomials. We state new, improved initial conditions which provide the guaranteed convergence of frequently used simultaneous methods for solving algebraic equations: Ehrlich–Aberth's method, Ehrlich–Aberth's method with Newton's correction, Börsch-Supan's method with Weierstrass’ correction and Halley-like (or Wang–Zheng) method. The introduced concept offers not only a clear insight into the convergence analysis of sequences generated by the considered methods, but also explicitly gives their order of convergence. The stated initial conditions are of significant practical importance since they are computationally verifiable; they depend only on the coefficients of a given polynomial, its degree n and initial approximations to polynomial zeros.     

Solving systems of fractional differential equations using differential transform method

This paper presents approximate analytical solutions for systems of fractional differential equations using the differential transform method. The fractional derivatives are described in the Caputo sense. The application of differential transform method, developed for differential equations of integer order, is extended to derive approximate analytical solutions of systems of fractional differential equations. The solutions of our model equations are calculated in the form of convergent series with easily computable components. Some examples are solved as illustrations, using symbolic computation. The numerical results show that the approach is easy to implement and accurate when applied to systems of fractional differential equations. The method introduces a promising tool for solving many linear and nonlinear fractional differential equations.     

On the new fourth-order methods for the simultaneous approximation of polynomial zeros

A new iterative method of the fourth-order for the simultaneous determination of polynomial zeros is proposed. This method is based on a suitable zero-relation derived from the fourth-order method for a single zero belonging to the Schröder basic sequence. One of the most important problems in solving polynomial equations, the construction of initial conditions that enable both guaranteed and fast convergence, is studied in detail for the proposed method. These conditions are computationally verifiable since they depend only on initial approximations, the polynomial coefficients and the polynomial degree, which is of practical importance. The construction of improved methods in ordinary complex arithmetic and complex circular arithmetic is discussed. Finally, numerical examples and the comparison with existing fourth-order methods are given.     

Recurrence relations for a Newton-like method in Banach spaces

The convergence of iterative methods for solving nonlinear operator equations in Banach spaces is established from the convergence of majorizing sequences. An alternative approach is developed to establish this convergence by using recurrence relations. For example, the recurrence relations are used in establishing the convergence of Newton's method [L.B. Rall, Computational Solution of Nonlinear Operator Equations, Robert E. Krieger, New York, 1979] and the third order methods such as Halley's, Chebyshev's and super Halley's [V. Candela, A. Marquina, Recurrence relations for rational cubic methods I: the Halley method, Computing 44 (1990) 169–184; V. Candela, A. Marquina, Recurrence relations for rational cubic methods II: the Halley method, Computing 45 (1990) 355–367; J.A. Ezquerro, M.A. Hernández, Recurrence relations for Chebyshev-type methods, Appl. Math. Optim. 41 (2000) 227–236; J.M. Gutiérrez, M.A. Hernández, Third-order iterative methods for operators with bounded second derivative, J. Comput. Appl. Math. 82 (1997) 171–183; J.M. Gutiérrez, M.A. Hernández, Recurrence relations for the Super–Halley method, Comput. Math. Appl. 7(36) (1998) 1–8; M.A. Hernández, Chebyshev's approximation algorithms and applications, Comput. Math. Appl. 41 (2001) 433–445 [10]].     

Uniform convergence of derivatives of extended Lagrange interpolation

Summary The authors construct some extended interpolation formulae to approximate the derivatives of a function in uniform norm. They prove theorems on uniform convergence and give estimates of pointwise type and of simultaneous approximation.This material is based upon work supported by the Italian Research Council (first and second authors), and by the Ministero dell'Università e della Ricerca Scientifica e Tecnologica (second and third author).