5.1 Some comments on higher-order multipoint methods

In this chapter we give a short review of optimal multipoint methods of arbitrary order of convergence. These methods require F.E. with optimal order and include some particular families of n-point methods of optimal order for arbitrary . Before presenting higher-order multipoint methods, let us consider a natural question of practical interest: Is the construction of extremely fast multipoint methods always justified?

There are arguments for and against very fast root-solvers. In general, for solving most practical problems at the moment, which are not ill-conditioned or unstable, double-precision arithmetic is good enough giving the accuracy of desired solutions, or results of calculation with approximately 16 significant decimal digits, that is, an error of about . This also holds for mathematical models where algorithms for solving nonlinear equations (most frequently polynomial equations) make a part of a global problem.

However, there are some classes of problems when multi-precision capabilities are very important, such as Number theory, Experimental mathematics, and many research fields including high energy physics, nonlinear process simulation, finite element modeling CAD, 3-D real-time graphic, statistics, security cryptography, and so on. Therefore, in some special applications there is a need for the implementation of very fast algorithms but even in these cases there is a reasonable limit in view of desired accuracy. For example, approximations to the roots of nonlinear equations with 300 or more accurate decimal digits are not required in practice at present.

In particular, the application of very fast root-solvers is justified if they serve for testing multi-precision arithmetic, whose improvement and development is a permanent work of many computer scientists and numerical analysts, see Brent and Zimmermann (2011). Second, a specific multipoint method of very high order (say 16 or higher) could be of interest, at least from the theoretical point of view, if such a method is a member of a family of an arbitrary order of convergence. Typical examples are the Kung-Traub families (5.3) and (5.4) with optimal order for arbitrary .

In this book we consider mainly multipoint methods having optimal order of convergence. Non-optimal methods with very high order are not of interest for two reasons: first, extremely high accuracy of produced approximations is very seldom needed for solving practical problems and second, extra F.E. additionally decrease computational efficiency.

5.2 Geum-Kim’s family of four-point methods

We begin with an optimal four-point method of order sixteen proposed by Geum and Kim (2011c). Recall that Geum-Kim’s three-point methods are considered in Section 4.3. Introduce the following variables

which will serve as arguments of suitable weight functions. In a similar way as in the papers Geum and Kim (2010,2011a,b,c), Geum and Kim (2011c) have stated the four-point method using weight functions,

(5.1)

where

(5.2)

Let

define partial derivatives. The main goal in the convergence analysis of the family (5.1) is stating suitable relationships between parameters of , , and so that the order is at least sixteen. These relations are given in the following theorem (Geum and Kim, 2011c).

The proof is derived using a standard technique and Taylor’s series. Since a lot of cumbersome expressions appear in the proof, symbolic computation in the computational software package Mathematica was used. The authors also give the explicit expression for the error relation. This relation is very complicated and includes many parameters and coefficients of the form . For this reason and the fact that error relations of iterative methods of very high order are of a little practical interest, we do not display the mentioned error relation.

According to Theorem 5.1, the weight functions defined by (5.2) take specific forms:

where satisfy the conditions given in Theorem 5.1.

Note that the method (5.1) is not a member of any class of optimal methods of arbitrary order of convergence. Although the applied model of construction has already been used in the authors’ methods (4.80), (4.82), and (4.83), further acceleration to order 32 would be very complicated. However, methods of order 32 have no practical importance and could be at most a matter of academic competition.

Speaking about the convergence speed of multipoint methods, it is worth noting that most authors test their methods in numerical examples taking sufficiently close approximations to the sought zeros. Methods for the localization and determination of good starting approximations have been almost entirely neglected. However, without reasonably good initial approximations it is impossible to attain the expected convergence speed (determined in theoretical analysis). Practical experiments show that multipoint methods can converge very slowly at the beginning of the iterative process. It is often reasonable to put an effort into a localization procedure, including the determination of a good initial approximation, instead of using very fast algorithm with poor starting guesses. An efficient algorithm for finding good initial approximations, proposed by Yun (2008), is described in Section 1.4.

5.3 Kung-Traub’s families of arbitrary order of convergence

The application of inverse interpolation is a useful technique that gives a uniform method for constructing iterative methods for solving nonlinear equations. Let be approximations to a zero of f and let be the inverse of f. Let be any interpolating polynomial for at the points with . A new approximation to is uniquely determined by . The Kung-Traub families, which will be discussed in this section, belong to the best known and most powerful root-finding methods constructed by inverse interpolation. Even from a historical point of view, these families deserve to be first; namely, they appeared almost forty years before other optimal multipoint methods of arbitrary order.

As mentioned in Section 2.5, Kung-Traub’s paper (Kung and Traub, 1974) is probably one of the most influential papers in the area of multipoint methods for solving nonlinear equations. For a fixed number of function evaluations, two families presented by Kung and Traub (1974) attain the order of convergence , the limit not exceeded yet. Special cases of the Kung-Traub families (K-T for short) are presented in Chapter 2 (two-point methods (2.111) and (2.113)) and in Chapter 3 (three-point methods (3.1) and (3.2)).

Although the K-T families are given in a general form in Section 2.5, we present the corresponding recursive algorithms again in this chapter for self-contained purpose and better insight into the programs (written in Mathematica) for generating the K-T iterative formulas for arbitrary .

K-T (5.3): For and for any , define iteration function as follows:

(5.3)

for, where is the inverse interpolating polynomial of degree at most j such that .

K-T (5.4): For and for any , define iteration function as follows:

(5.4)

for , where is the inverse interpolating polynomial of degree at most j such that

Let us note that the K-T family (5.3) requires no evaluation of derivatives of f.

For a fixed n, the methods (5.3) and (5.4) can be easily constructed using a recursive procedure by programs presented below, previously given by Kung and Traub (1974) in pseudo-code as an adaptation from Krough (1970).

Generation of K-T family (5.3).

Generation of K-T family (5.4).

The given entry n determines the number of steps ( in these programs). If then the two-point methods are given by psi (for (5.3)) and om (for (5.4)) before the k-loop, while psi and omwithin this loop generate the n-point methods for .

Let G be a set of real analytic functions f defined on an open interval which contains a simple zero of f. Now we present convergence theorems for the Kung-Traub families (5.3) and (5.4) in a form similar to that given in Kung and Traub (1974).

Using (5.6), by successive application of (5.9) we find that the asymptotic error constant of the Kung-Traub family (5.3) is

(5.10)

A convergence theorem for the Kung-Traub family (5.4) is similar to Theorem 5.2.

The proof of this theorem is derived in the same manner as for Theorem 5.2 using the relation (5.8). Since , in this case we have from (5.8) that ; hence, the asymptotic error constant of the Kung-Traub family (5.4) is given by

According to this relation and (5.10) we find

In regard to the relation (5.10) we note that the parameter in the family (5.3) should be chosen so that is as small as possible. In Chapter 6 we will see that the factor plays a key role in the construction of methods with memory that have a higher order of convergence.

Studying multipoint methods, Kung and Traub (1974) have introduced the set of functions which maps every to with the following properties:

of variables for such that, for all ,

where

(5.11)

(5.12)

If , then an iterative method is called a method without memory, since uses only information at the current point . For example, the Kung-Traub families (5.3) and (5.4) are methods without memory. The upper bound on the order of convergence of a multipoint iteration is given in the following theorem.

From Theorem 5.4 we observe that the presented upper bound is within a factor of two of the order of the Kung-Traub families (5.3) and (5.4) (see Theorems 5.2 and 5.3). The bound is pretty crude, which is evident from particular examples; for instance, optimal two-point methods have the order four, but the upper bound considered in Theorem 5.4 is even eight. This modest result of Theorem 5.4 and a good anticipation led Kung and Traub to state the following hypothesis.

(5.16)

This conjecture, today known as the Kung-Traub conjecture, is mentioned several times throughout this book. It is confirmed in practice that all existing multipoint methods, constructed at present, support Conjecture 5.1. Experts in the considered topic believe that the Kung-Traub bound cannot be exceeded.

5.4 Methods of higher-order based on inverse interpolation

Inverse interpolation, utilized in developing Kung-Traub’s families (5.3) and (5.4), was also applied for the construction of very fast methods developed by Neta (1981). Consider the three-step scheme that combines Newton’s method and King’s fourth-order method (2.57)

(5.17)

Putting , Neta obtained the sixth-order family (Neta, 1979).

To accelerate the convergence rate of the family (5.17), Neta (1981) applied inverse interpolation to compute . Let

(5.18)

be a polynomial of degree four satisfying

(5.19)

where are computed from (5.17). The first two relations of (5.19) give

Introduce the notation

(5.20)

The last three relations of (5.19) give the system of linear equations

with the solution

Once the coefficients were computed, then from (5.18) we can state the following four-point iterative method,

(5.21)

In the same paper (Neta, 1981) the order of the iterative scheme (5.21) was improved by replacing the third step of (5.17) with a step similar to the fourth. Let

(5.24)

be a cubic polynomial satisfying

(5.25)

From the first two relations we immediately obtain

(5.26)

Using the notation given in (5.20), the last two equations of (5.25) give the system

Hence we determine the coefficients and ,

(5.27)

With the coefficients given by (5.26) and (5.27), the iterative method for improving the approximation was stated by Neta (1981),

(5.28)

Combining the first two steps of (5.17) (King’s method), (5.28), and (5.21), the following improved four-point method is obtained,

(5.29)

(5.32)

where and are given by (5.27). This family is of order eight (according to (5.31)) and requires four F.E. Therefore, the family (5.32) is optimal. This fact has not been noticed in the literature. Instead, excepting the Kung-Traub families (5.1) and (5.2), the family (4.2) proposed by Bi et al. (2009b) is usually taken as the first three-point method with optimal order eight. It should be emphasized that another optimal three-point method was published by Milovanović and Cvetković (2007) two years before Bi et al. (2009b).

Designing the optimal family of four-step methods (5.29) points to the idea for constructing multipoint methods of arbitrary order. We write and choose

Assume that are iteration functions in an n-point method with respective orders , that is,

(5.33)

Regarding the fourth-step of the iterative scheme (5.29), we start with inverse interpolating polynomial of degree n

(5.34)

and the conditions

(5.35)

From the first two relations of (5.35) we immediately obtain and . The other coefficients are determined from a system of linear equations formed according to (5.35). Then we construct -point method by combining n previous steps with the iteration functions

(5.36)

and the st step

(5.37)

which follows from (5.34) setting .

The order of convergence of the -point method (5.36)–(5.37) is obtained from the error relation (4.46) for and written in the form

Taking into account the errors given by (5.33), from the last relation we obtain

Therefore, the order of the -point method (5.36)–(5.37) is , attained by function evaluations. The presented procedure shows a simple way of obtaining an optimal multipoint method of order by inverse interpolation when we know an optimal multipoint method of order .

5.5 Multipoint methods based on Hermite’s interpolation

Let denote Newton’s method and let be an optimal two-point method of order four. Defining we form an iterative scheme of Newton’s type consisting of n steps in the following way:

(5.38)

Starting from an initial approximation , from (5.38) we define the family of iterative methods .

Applying Theorem 1.3 we find that the n-point methods (5.38), written in the composite form,

have the order of convergence since the iteration function defines a fourth-order iterative method. However, note that the iterative scheme (5.38) requires function evaluations per iterations, which is rather inefficient. Therefore, it is ultimately necessary to reduce the number of F.E. using suitable approximations to all derivatives that appear in the steps (3)–.

For simplicity, we drop the argument of iteration functions whenever it does not create a confusion. To carry out the substitution of the derivatives by a suitable approximation , we apply some efficient procedure such as Hermite’s interpolation, inverse interpolation, Newton’s interpolation, etc. A suitable approximation means that a modified Newton’s method

(5.39)

is also of second order. If P is an interpolating polynomial obtained by some of the above-mentioned interpolations, then it should be

which is sufficient to provide quadratic convergence of the modified Newton method (5.39). There are other methods for approximating first derivative, but it is preferable to take interpolation procedures since they possess a unique algorithmic structure, suitable for programming and applications.

In this section we present a family of optimal n-point methods constructed by Hermite’s interpolation. Its order is requiring function evaluations. This family starts with any two-point method of optimal order four in the first two steps (1) and (2) of (5.38) and uses Hermite’s interpolation for approximating .

To state the n-point method (thus, each iteration consists of n steps) for arbitrary , the derivative in the st step should be replaced by the derivative of Hermite’s interpolating polynomial

of degree at the nodes constructed using the conditions

(5.40)

In other words, we utilize Hermite’s polynomials of higher degree satisfying (5.40), whose construction requires additional basic arithmetic operations, but not new F.E. for a fixed number of steps. The family of n-point methods, proposed by Petković (2010, 2011b), consists of n steps:

(5.41)

The family of three-point methods based on Hermite’s interpolation, which follows from (5.41) for is considered in Section 4.2, see (4.12). In Theorem 4.3 it has been proved that its order eight is attained using four F.E. The main idea for the construction of optimal multipoint methods of arbitrary order, based on Hermite’s interpolation, has been presented by Petković (2010). An oversight in the construction for was corrected by Petković (2011b).

We now present the convergence theorem for the family (5.41).

5.6 Generalized derivative free family based on Newtonian interpolation

Zheng et al. (2011) have proposed a one-parameter derivative free families of n-point methods of arbitrary order of convergence . These families are constructed by Newton’s interpolation with forward divided differences and require function evaluations, which means that they generate optimal methods in the sense of the Kung-Traub conjecture.

Newton’s interpolating polynomial of degree m with divided differences for a given function f at different nodes

(5.48)

is constructed under the conditions . Recall that divided differences are calculated recursively as

(5.49)

for . The error of Newton’s interpolating polynomial is given by

(5.50)

(see (4.114)), where lies in an interval containing these nodes.

Let be an approximation to a simple zero of f and let , where is a parameter. In regard to (5.50), the function f can be represented in the form

(5.51)

The error factor (and, more generally, ) depends on the iteration index k. To find an improved approximation to the zero of f, we apply Newton’s method at the point to the function defined by the expression on the right-hand side of (5.51) and obtain

(5.52)

The error factor from (5.50) is given by or , where and are points from the interval

However, and are unknown and the best we can do is to adopt that in (5.52) is a constant. Fortunately, appears only in the corresponding error relation but does not influence the order of convergence of the method (5.52). Numerical examples confirms this fact. For this reason, we can set and simplify (5.52) to the form

(5.53)

The last iterative formula defines the Steffensen-like method (Traub, 1964, p.179), mentioned several times in this book. For the method (5.53) reduces to the method given by Steffensen (1933). For this similarity, a family proposed by Zheng et al. (2011) is referred to as the Steffensen-like family.

To accelerate methods of Steffensen’s type, in the next step we use the approximation

calculated from (5.53) and set

Applying Newton’s method at the point as above, we obtain the two-point method

(5.54)

The family (5.54) generalizes Ren-Wu-Bi’s method (2.104) with the parameter and reduces to (2.104) when and , see Ren et al. (2009).

As above, we emphasize that the term , actually a remainder in Newton’s interpolation, does not influence the order of convergence of the family of two-point methods (5.54). In practice, it is preferable to choose . In that case, the iterative method (5.54) becomes similar to the Kung-Traub method (2.111) arising from (5.3) for , but still different.

A family of three-point methods is constructed in a similar way. Using Newton’s interpolating polynomial of third degree with the new point calculated by (5.54), we represent f in the form

After applying Newton’s method at the point , the following family of three-point methods is obtained,

(5.55)

where

In practice, we take since the last term in the denominator behaves as a “parasite” supplement without influencing the convergence rate. This choice is also preferable for the factors appearing in other methods of higher order given later in the form of a generalized family.

The following convergence theorem has been proved by Zheng et al. (2011).

When then

so that the error relations (5.54), (5.57), and (5.58) deliver the asymptotic error constants

(5.59)

The technique described for constructing families of multipoint methods by using Newton’s interpolation with divided differences can be applied successively up to points, as shown by Zheng et al. (2011). In this way a family of optimal order can be derived. For simplicity and better presentation, we use the notation

omitting the iteration index k in . Then Zheng-Li-Huang’s n-point family may be written in the form

(5.60)

where

The following theorem was proved by Zheng et al. (2011).

From the proofs of Theorems 5.8 and 5.9 we observe that the factor appears in the expression of the asymptotic error constant but does not influence the order of convergence. As already mentioned, a number of numerical examples confirmed this fact so that it is reasonable to take in the iterative scheme (5.60) in practice. Then the asymptotic error constants differ from those given in Theorem 5.9 and read

and

where

From the results displayed in Table 5.1 and a number of numerical experiments, it can be concluded that the convergence of the tested multipoint methods is remarkably fast. Even the accuracy of approximations obtained by two iterations is spectacular. All tested methods (5.3), (5.4), (5.41) (with variants), and (5.60) demonstrate similar behavior and very fast convergence for good initial approximations. The methods (2.47)–(5.41), (2.122)–(5.41), and (2.33)–(5.41) give the most accurate approximations in this particular example, but some other methods are better for other functions.

We end this chapter with a remark that Hermite’s and Newton’s interpolation can be used for obtaining an optimal -step method based on an n-step optimal method in a similar way as for inverse interpolation (see the end of Section 5.4). An additional (-st) step is then of the form

and is the interpolation polynomial set through all available information from the current iteration.

References

1. Bi W, Wu Q, Ren H. A new family of eight-order iterative methods for solving nonlinear equations. Appl Math Comput. 2009b;214:236–245.

2. Brent R, Zimmermann P. Modern Computer Arithmetic. Cambridge: Cambridge University Press; 2011.

3. Brent R, Winograd S, Wolfe P. Optimal iterative processes for root-finding. Numer Math. 1973;80:327–341.

4. Geum YH, Kim YI. A multi-parameter family of three-step eighth-order iterative methods locating a simple root. Appl Math Comput. 2010;215:3375–3382.

5. Geum YH, Kim YI. A uniparametric family of three-step eighth-order multipoint iterative methods for simple roots. Appl Math Lett. 2011a;24:929–935.

6. Geum YH, Kim YI. A biparametric family of eighth-order methods with their third-step weighting function decomposed into a one-variable linear fraction and a two-variable generic function. Comput Math Appl. 2011b;61:708–714.

7. Geum YH, Kim YI. 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. J Comput Appl Math. 2011c;235:3178–3188.

8. Krough FT. Efficient algorithms for polynomial interpolation and numerical differentiation. Math Comp. 1970;24:185–190.

9. Kung HT, Traub JF. Optimal order of one-point and multipoint iteration. J ACM. 1974;21:643–651.

10. Milovanović GV, Cvetković AS. A note on three-step iterative methods for nonlinear equations. Stud Univ Babeş-Bolyai Math. 2007;52:137–146.

11. Neta B. A sixth order family of methods for nonlinear equations. Int J Comput Math. 1979;7:157–161.

12. Neta B. On a family of multipoint methods for nonlinear equations. Int J Comput Math. 1981;9:353–361.

13. Neta B. A new family of higher order methods for solving equations. Int J Comput Math. 1983;14:191–195.

14. Neta B, Petković MS. Construction of optimal order nonlinear solvers using inverse interpolation. Appl Math Comput. 2010;217(2448–2455):b0075.

15. Petković MS. On a general class of multipoint root-finding methods of high computational efficiency. SIAM J Numer Anal. 2010;47:4402–4414.

16. Petković MS. Remarks on On a general class of multipoint root-finding methods of high computational efficiency. SIAM J Numer Anal. 2011;49:1317–1319.

17. Ren H, Wu Q, Bi W. A class of two-step Steffensen type methods with fourth-order convergence. Appl Math Comput. 2009;209:206–210.

18. Steffensen IF. Remarks on iteration Skand Aktuarietidskr. 1933;16:64–72.

19. Traub JF. Iterative Methods for the Solution of Equations. Englewood Cliffs, New Jersey: Prentice-Hall; 1964.

20. Yun BI. A non-iterative method for solving nonlinear equations. Appl Math Comput. 2008;198:691–699.

21. Zheng Q, Li J, Huang F. Optimal Steffensen-type families for solving nonlinear equations. Appl Math Comput. 2011;217:9592–9597.