Chapter 4
Three-point optimal methods
As noted in the previous chapter, optimal multipoint methods of order higher than four were stated by Kung and Traub (1974). In the next 33 years many three-point methods requiring 
were constructed, but their order did not reach optimal order 
, see Chapter 3. However, it is worth noting that an optimal family of three-point methods was implicitly given in Neta’s paper (Neta, 1981) as a composite part of a four-point family of order sixteen, but neither the author emphasized and announced this fact nor other authors noticed this “nested” three-point family. More details are given in Remark 5.3. The above story refers to multipoint methods without memory as classified using Traub’s approach given in Section 1.1, that is, it is assumed that methods use only one starting approximation. We recall that Neta (1983) constructed three-point methods with order 10.815˙ but using three initial approximations so that Neta’s method is treated separately in the class of methods with memory, see Chapter 6. In this chapter we discuss three-point optimal methods without memory. Many iterative methods of optimal order eight, derived using different techniques in the period 2009–2011, are presented.
4.1 Optimal three-point methods of Bi, Wu, and Ren
We ended the previous chapter with the seventh-order method of Bi et al. (2008). To achieve optimal order eight, the same authors have applied a similar approach to approximate 
in the third Newtonian step. In addition, they have introduced a weight function and two parameters in a three-step iterative scheme. Handling suitably chosen weight function and more parameters resulted in a family of three-point methods with optimal order eight presented by Bi et al. (2009b).
(4.1)
derived in Section 3.5 (see (3.81)), the following three-point method was stated by Bi et al. (2009b),
(4.2)
and 
is a real-valued function.
The following convergence theorem was proved by Bi et al. (2009b).
Theorem 4.1
Let 
be a zero of 
on an open interval 
. If 
is sufficiently close to 
, then the sequence 
generated by any method from the family (4.2) converges to 
. If h is a function satisfying
(4.3)
and 
, then any method of the family (4.2) is of order eight.
The proof of this theorem, given by Bi et al. (2009b), uses a standard technique based on Taylor’s series. In the case of multipoint methods, such an approach deals with rather cumbersome and lengthy expressions so that any manipulation and calculation most often require the use of computer. In such circumstances it is reasonable to determine the convergence rate using symbolic computation, as done in this book several times. If necessary, intermediate expressions can always be displayed during this computation. For this reason, we give a proof of Theorem 4.1 using symbolic computation in the computational software package Mathematica.
Let us introduce the following abbreviations used in the program below:
.
,
, 
, 
,
.For simplicity, iteration indices are omitted.
Program (written in Mathematica)
fx = f1a∗(e + c2∗eˆ2 + c3∗eˆ3 + c4∗eˆ4 + c5∗eˆ5);
f1x = D[fx,e]; ey = e-Series[fx/f1x,{e,0,8}];
fy = f1a∗(ey + c2∗eyˆ2 + c3∗eyˆ3 + c4∗eyˆ4);
h = h0 + h10∗t + h20/2∗tˆ2 + h30/6 ∗tˆ3;
ez = ey-h∗Series[fy/f1x,{e,0,8}];
fz = f1a∗(ez + c2∗ezˆ2 + c3∗ezˆ3 + c4∗ezˆ4);
fzy=(fz-fy)/(ez-ey); fzx=(fz-fx)/(ez-e);
From the last expression of e1 we conclude that the order of convergence of the family of methods (4.2) is eight. Since this family requires only 
F.E. and attains the order 
, it supports the Kung-Traub conjecture on the upper bound of the order of convergence of multipoint methods without memory, see Section 1.3.
Remark 4.1
The reader may ask about a method for establishing the conditions (4.3) that guarantee the eight order of the family (4.2). As mentioned several times in this book, old paper-and-pencil fashion is almost impossible in a convergence analysis of multipoint methods of higher order so that symbolic computation is used. The values of 
, 
, and 
in Theorem 4.1 are determined in the same manner as in Section 2.4; suitable conditions are imposed to achieve as high order of convergence as possible. The program above gives automatic computer-aided proof, while the program in Section 2.4 has a constructive character but also serves as automated theorem prover.
Remark 4.2
It was proved by Bi et al. (2009b) that the order of convergence of the family (4.2) is seven if the conditions of Theorem 4.1 are relaxed. If 
and 
are any real parameters and 
, 
with arbitrary but bounded 
and 
, then the order of (4.2) is seven.
Remark 4.3
Observe that the term 
in the third step of (4.2) is King’s correction which appears in King’s two-point method (2.57). Furthermore, the first two steps in (4.2) define a two-point family similar to (2.74), but under stronger conditions for the weight function.
Choosing different forms of the function h in (4.2) satisfying (4.3), a variety of three-point methods can be obtained. The following four particular forms of h were proposed by Bi et al. (2009b):
,
,
,
.For each of these functions the corresponding three-point method, referred to as Method 1,…, Method 4, has been presented and tested in numerical examples. Some of these methods have been compared with other existing three-point methods of order eight, see Tables 4.1, 4.2, 4.5, 4.6, 4.7, 4.8.
Table 4.1 
Table 4.2 
Table 4.3 List of optimal two-point methods
Table 4.4 List of tested functions with initial guesses
Table 4.5 Results of Example 4.1, 
Table 4.6 Results of Example 4.4, 
Table 4.7 Results of Example 4.5, 
Table 4.8 Results of Example 4.7, 
The same authors have proposed another family of three-point methods of optimal order eight by Bi et al. (2009a), which is similar to the already presented family (4.2). King’s method from the third step of (4.2) is shifted to the second step, a weight function is applied in the third instead of second step, while the approximation of 
remains the same (given by (4.1)). This three-point family has the form
(4.4)
and 
is a real-valued function chosen so that the family (4.4) attains eighth order.
The following theorem, concerning convergence conditions and convergence order, was proved by Bi et al. (2009a).
Theorem 4.2
Let 
be a zero of 
on an open interval 
. If 
is sufficiently close to 
, then the sequence 
generated by any method of the family (4.4) converges to 
with order eight if 
and p is any function with the properties
(4.5)
Comparing the family (4.4) to (4.2) we observe that the conditions on the weight function are relaxed (
is arbitrary) but the real parameter 
is fixed. The proof of Theorem 4.2 given by Bi et al. (2009a) uses a standard technique based on Taylor’s series. It can also be carried out in an easy way by symbolic computation.
As for the family (4.2), some particular forms of the weight function p in (4.4) (satisfying (4.5)) were presented by Bi et al. (2009a):
,
,
.4.2 Interpolatory iterative three-point methods
In this section we consider families of three-point interpolatory methods with optimal order eight requiring four F.E. These families rely on optimal two-point methods belonging to the class 
and use the interpolation techniques to approximate 
in the third step, see Petković (2010), Petković (2011b), and Petković and Petković (2010).
4.2.1 Optimal three-point methods based on Hermite’s interpolation
Let f be a real function defined on an open interval 
and 
does not vanish on 
. Let us assume that a simple zero 
of f is isolated in the interval 
and let 
denote an iteration function from the class 
of optimal two-point iterative methods, considered extensively in Chapter 2. Then the improved approximation 
to 
can be found by the following three-step iterative scheme:
(4.6)
For simplicity, we omit the iteration index.We note that the first two steps define an optimal two-point method from the class 
with the order 
using Newton’s method of order two in the first and third step. The presented scheme is simple and, according to Theorem 1.3, its rate of convergence is equal to 
.
Observe that the three-point method (4.6) requires five F.E. per iteration, that is, it is not optimal in the sense of Kung-Traub’s conjecture. To reduce the number of F.E., we approximate 
using available data. Since we have four values 
, 
, 
, and 
, it is convenient to approximate f by its Hermite’s interpolating polynomial 
of degree 3 at the nodes 
and utilize the approximation 
in the third step of the iterative scheme (4.6). This idea was employed by Petković (2010) and Petković (2011b) for a general class of optimal multipoint methods, see Section 5.4. Other techniques for approximating 
are demonstrated in this chapter in the examples of other optimal methods of order eight, including (4.2) and (4.4).
Hermite’s interpolating polynomial of third degree has the form
(4.7)
and its derivative is
(4.8)
The unknown coefficients will be determined using available data from the conditions:
Putting 
into (4.7) and (4.8) we immediately get 
and 
. The coefficients 
and 
are obtained from the system of two linear equations formed by using the remaining two conditions putting 
and 
into (4.7). We obtain
(4.9)
and
(4.10)
Replacing the coefficients 
and 
given by (4.9) and (4.10) into (4.8) and putting 
, we get the explicit formula for 
,
(4.11)
We now use (4.11) to approximate 
in (4.6) and state the following family of three-point methods: Given an initial approximation 
, the improved approximations are calculated by the three-point iterative process
(4.12)
The proposed eighth-order family (4.12), costing only four F.E., is the subject of Theorem 4.3. The proof of this theorem requires the estimation of quality of the approximation 
.
Let 
be Hermite’s interpolating polynomial of degree m satisfying
(4.13)
where 
are interpolation nodes and 
are their respective multiplicities. The error of the Hermite interpolation is given in Theorem 3.1. Using (3.14) we state the following convergence theorem.
Theorem 4.3
If an initial approximation 
is sufficiently close to a zero 
of a function f, then the family of three-point methods (4.12) is of order eight.
Proof.
For brevity, we again omit the iteration index and consider the values 
in one iteration step, denoting the improved approximation with 
. Let us introduce the errors
Since the iteration function 
is of fourth order, we have the estimation
(4.14)
where 
is the asymptotic error constant of the two-step method 
applied in (4.12). It is evident that
(4.15)
Let us find the order of convergence of the modified Newton method
(4.16)
that appears in the third step of (4.12) after substituting 
by 
(given by (4.11)). To do that, we compare (4.16) to Newton’s method 
. Consider a special case of (4.13) when 
, and 
, 
are multiplicities of the nodes 
, 
and 
, respectively. Then, in regard to (3.14), the error of Hermite’s interpolation is given by
(4.17)
Differentiating (4.17) and taking 
, in regard to (4.14) and (4.15) we obtain
This relation yields
and 
. Hence
(4.18)
which means that the modified Newton method (4.16) also possesses the quadratic convergence. Finally, according to (4.14) and (4.18), we get
which completes the proof of Theorem 4.3. 
Remark 4.4
By virtue of (4.14) and (4.18), from Theorem 1.3 it also follows that the order of convergence of the composite iteration (4.12) is 
.
Remark 4.5
Since the convergence order of (4.12) is 
and the number of F.E. is 
for the considered class of three-point methods 
, we conclude that the family (4.12) supports the Kung-Traub conjecture.
Using the Taylor series and symbolic computation in Mathematica we can determine the asymptotic error constant of the three-point method (4.12). The notation is the same as in the previous section.
Program (written in Mathematica):
fx = f1a∗(e + c2∗eˆ2 + c3∗eˆ3 + c4∗eˆ4); f1x = D[fx,e];
ey = e-Series[fx/f1x,{e,0,4}];
fy = f1a∗(ey + c2∗eyˆ2 + c3∗eyˆ3 + c4∗eyˆ4);
ez = A4∗eˆ4; fz = f1a∗(ez + c2∗ezˆ2 + c3∗ezˆ3 + c4∗ezˆ4);
f1z = fxz∗(2+(ez-e)/(ez-ey))-(ez-e)ˆ2/((ey-e)∗(ez-ey))∗fxy + f1x∗(ez-ey)/(ey-e);
Therefore, the asymptotic error constant (AEC) of the class of methods (4.12) is given by
Here 
presents AEC of the particular two-point method 
applied to the iterative scheme (4.12). For example, 
for King’s two-point family
(4.19)
so that the AEC of the three-point method (4.12) in this particular case is
Remark 4.6
Note that the output Out[e1] of the above program points to the eighth order of convergence. In fact, this program determines the rate of convergence of the three-point scheme (4.12) in an easy way using symbolic computation, see Remark 4.14.
Families of three-point methods, which also use Hermite’s interpolation, have been developed by Kou et al. (2010). The following three steps have been chosen as a starting scheme:
(4.20)
is a real function of two variables which is calculated using the already found values 
, 
, and 
. This function should be taken so that a two-point method formed by the first two steps has optimal order four. Recall that such two-step methods are considered in Section 2.3.
The third step in (4.20) is, in fact, Newton’s method (or, more generally, a Newton-like method) so that we can regard 
, without loss of generality. 
is calculated by available data 
, 
, 
, 
.
Kou et al. (2010) have proposed two families of three-point methods of optimal order eight. The first family uses the approximation of 
by the cubic Hermite interpolating polynomial
Proceeding in the same way as for the family (4.12), one obtains (see (4.11))
Putting this approximation in (4.20) instead of 
, Kou et al. (2010) have stated the following family of three-point methods (compare to (4.12))
(4.21)
As noticed above, the first two steps in (4.20) make an optimal method of order four, that is, the following error relation is valid
(4.22)
where 
is the asymptotic error constant of the applied fourth-order method. Using this estimate, the following error relation has been derived by Kou et al. (2010),
proving that the order of convergence of the family (4.21) is eight.
In the same paper (Kou et al., 2010) the authors have extended the family (4.21) by modifying the third step as follows
(4.23)
requiring that the function 
satisfies
(4.24)
It has been proved that the family (4.23) is of eighth order under the condition (4.24). More precisely, the following error relation
is valid, pointing to the eighth order of the family (4.23).
Note that the choice
immediately gives (4.21). Another choice is
(4.25)
where
(4.26)
Since
one obtains
so that
Hence
which means that the function 
, defined by (4.25) and (4.26), is of the required form (4.24).
Remark 4.7
Note that the families (4.21) and (4.23) require four F.E. and have order eight, which means that they support the Kung-Traub conjecture and have optimal efficiency index 
. Choosing different forms of 
and 
, many new three-point methods can be obtained.
Another three-point method of optimal order eight, constructed by Hermite’s interpolation for approximating 
in the third step, has been proposed by Wang and Liu (2010b),
(4.27)
is given by (4.11). The first two steps define Ostrowski’s method (2.47). Since this method is a member of the class 
of optimal fourth-order methods, it turns out that the method (4.27) is a special case of the family (4.12).
4.2.2 Three-point methods based on rational function interpolation
Consider again the family of three-point methods (4.6). Since this family is not optimal, to reduce the number of F.E. we will approximate 
using available data 
, 
, 
, and 
. For this purpose, we interpolate f by a rational fraction
(4.28)
see Petković et al. (2010a). From (4.28) we find
(4.29)
The unknown coefficients 
are determined from the conditions:
(4.30)
Putting 
into (4.28) and (4.29) and using (4.30)-(i) and (4.30)-(iv), we get 
and 
. The coefficients 
and 
are obtained from the system of two linear equations formed by using (4.30)-(ii) and (4.30)-(iii), and putting y and z into (4.28) instead of t. We get
(4.31)
Finally, we find
(4.32)
recalling that 
. Replacing the obtained coefficients into (4.29) and putting 
, we get the explicit formula for 
that uses only available data 
, 
, 
, and 
. In this way, the nonlinear fraction w and its derivative 
are completely determined by (4.28)–(4.32).
Setting 
(calculated from (4.29) for 
) into (4.6) instead of 
, L. Petković, M. Petković, and Džunić (Petković et al, 2010a) have constructed a family of three-point methods: Given an initial approximation 
, the improved approximations 
are calculated by the three-point iterative method
(4.33)
is any two-point method of optimal order four with the asymptotic error constant 
, that is,
The proposed family of root-solvers requires only four F.E. We will see later that its order of convergence is eight, that is, the family of three-point methods (4.33) is optimal.
Using Taylor’s series and symbolic computation in Mathematica, we can find the order of convergence and the asymptotic error constant of the three-point methods (4.33). The same notation from Section 4.1 is used.
Program (written in Mathematica):
fx = f1a∗(e + c2∗eˆ2 + c3∗eˆ3 + c4∗eˆ4);
ey = e-Series[fx/f1x,{e,0,7}];
fy = f1a∗(ey + c2∗eyˆ2 + c3∗eyˆ3 + c4∗eyˆ4);
ez = A4∗eˆ4; fz = f1a∗(ez + c2∗ezˆ2 + c3∗ezˆ3 + c4∗ezˆ4);
b3=(f1x∗fyz-fxy∗fxz)/((e∗(fy-fz)+ey∗fz-ez∗fy)/(ey-ez)-fx);
b4 = b3/fxy+(f1x-fxy)/((ey-e)∗fxy);
w1z=(b2-b1∗b4 + b3(ez-e) ∗(2 + b4(ez-e)))/(1 + b4(ez-e))ˆ2;
(4.34)
The output (4.34) of the above program proves the eighth order of convergence of the family of three-point methods (4.33). Taylor’s expansions used in the program assume sufficiently small 
, which means that the initial approximation should be reasonably close to the root 
. Altogether, we can state the following theorem (Petković et al., 2010a).
Theorem 4.4
If an initial approximation 
is sufficiently close to a zero 
of f, then the order of the family of three-point methods (4.33) is eight.
Remark 4.8
Since the number of F.E. is 
and the convergence order is 
, we conclude that the considered family of three-point methods (4.33) supports the Kung-Traub conjecture.
From (4.34) we observe that the asymptotic error constant of the family (4.33) is given by
The AEC 
is to be determined for each particular two-point method 
applied in the iterative scheme (4.33). For example,
for King’s two-point method (4.19) so that the AEC of the three-point method (4.33)
(4.19) in this particular case is
To demonstrate the convergence behavior of the proposed family of three-point methods (4.33), we present two examples implemented in Mathematica by the use of multi-precision arithmetic. For comparison, we also display results obtained by the family (4.2) constructed by Bi et al. (2009b), referred to as Method 1 and Method 2, Kung-Traub’s families (3.1) and (3.2) developed by Kung and Traub (1974), and by the family of three-point methods (4.12) (see Petković and Petković, 2010).
To represent various two-point methods from the class 
, we have chosen in (4.12) King’s family (4.19) for particular values of parameter 
, Maheshwari’s method (2.85), and the method (2.86) developed by Petković and Petković (2007c). The tables of results also contain the computational order of convergence, evaluated by (1.10).
Example 4.1
We applied the aforementioned methods to the test function
for finding its zero 
isolated in the interval 
. To find an initial approximation 
, we employed Yun’s algorithm described in Section 1.4 with the statement
x0 = 0.5∗(a + b + Sign[f[a]]∗NIntegrate[Tanh[m∗f[x]],{x,a,b}])taking 
, 
, 
, and found very good approximation 
. However, for more realistic investigation of convergence behavior, we dealt with a cruder approximation 
. The absolute values of the approximation errors 
in the first three iterations are displayed in Table 4.1.
Example 4.2
The three-point methods tested in Example 4.1 were also applied to the function
to approximate its zero 
In this test we used the common initial approximation 
. The results are presented in Table 4.2.
Regarding the results given in Tables 4.1 and 4.2 and a number of numerical examples, we conclude that the proposed optimal three-point methods (4.33) are extremely fast and very efficient. Their efficiency index
is higher than the efficiency index of optimal two-point methods. Two iterative steps are usually sufficient in solving most practical problems at present. The third iteration serves only to demonstrate remarkably fast convergence of the root-solvers considered. From the comparison study, we also conclude that the family (4.33) and the eighth-order methods given in the papers (Bi et al., 2009b; Kung and Traub, 1974; Petković and Petković, 2010) produce results of approximately the same quality. We also observe that the values of the computational order of convergence 
, given in the last column of Tables 4.1 and 4.2, very well match the theoretical order of convergence.
4.2.3 Three-point methods constructed by inverse interpolation
The next family of optimal three-point methods relies on optimal two-point methods applied in the first two steps and the inverse interpolating polynomial of third degree used in the third step, see Neta and Petković (2010). A general form of optimal two-point methods with a derivative is as follows
(4.35)
(4.36)
In what follows we consider a rather wide family (2.74) of optimal two-point methods of order four of the form
(4.37)
previously studied in Section 2.3. The function g takes a role of a weight function and commonly involves only a few basic arithmetic operations. Although several forms of g are given in Section 2.3, in order that the material on particular two-point methods from the family (4.37) be self-contained, we give in Table 4.3 six forms of g, denoted by 
. The entry y in Table 4.3 denotes Newton’s approximation 
. All methods listed in Table 4.3 are of optimal order four and possess the efficiency index 
.
We start with any two-step optimal method of order four (using two evaluations of f and one evaluation of 
) and add sub-steps resulting from inverse interpolation. This idea was used by Neta (1981) in constructing an optimal method of order 16.
To get a three-point optimal eighth-order method using four F.E., we use the inverse interpolation with a cubic polynomial
(4.38)
Clearly when substituting 
we have
(4.39)
Differentiating (4.38) we get
Therefore
(4.40)
To find the parameters c and d, we set 
and 
in (4.38), where 
is the result of application of any optimal fourth-order method (4.35). Upon using the values of a and b given by (4.39) and (4.40), we get
Where we denote 
. We can rewrite this system as
(4.41)
Subtracting the second equation of (4.41) from the first gives
Hence
(4.42)
and
(4.43)
Once we have c and d we get the three-point method
(4.44)
To prove that the method (4.44) is of order eight, we quote a theorem due to Traub (1964).
Theorem 4.5
(Traub, 1964) Let 
, 
be 
approximations to a zero 
of f. Let 
be interpolating polynomial at 
in the sense of
where 
is the inverse of f. Define a new approximation to 
by
and let 
, then
(4.45)
for suitable constants 
.
The following theorem was stated by Neta and Petković (2010).
Theorem 4.6
If an initial approximation 
is sufficiently close to a zero 
of a function f, then the order of convergence of the family of three-point methods (4.44) is eight.
Proof.
Theorem 4.5 holds for successive one-point iterations and we will apply it for a fixed iteration but introducing partial errors in each step of a multipoint method. For this purpose, we will rewrite the error relation (4.45) in the form
(4.46)
with
assuming that an 
-step method consists of an array of approximations 
.
Taking 
, 
and 
for the method (4.44), according to Theorem 4.5 and (4.46) we have
where 
and 
. Furthermore, 
since the first (Newton’s) step is of second order. Also 
and therefore
which means that the method (4.44) is of order eight. 
Remark 4.9
The three-point methods (4.44) are optimal of order eight and possess the efficiency index
4.2.4 Numerical examples
We now present numerical experiments that compare the family of three-point methods (4.44) to some other optimal three-point methods of eighth order, taking variants of the two-point optimal method (4.37) in (4.44). We have selected several eighth-order methods for demonstration. Note that approximations obtained by the remaining three-point methods of optimal order eight, not displayed here, are of approximately the same quality.
We now turn to the four examples listed in Table 4.4 along with the initial guess used.
The errors 
in the first three iterations for the tested examples are given in Tables 4.5–4.8. The computational order of convergence, evaluated by the approximate formula (1.10), is included in the presented tables.
From the results shown in Tables 4.5–4.8 and a number of numerical experiments we conclude that the proposed three-point methods (4.44) are remarkably fast. This class of methods is competitive to other existing eighth-order methods. If initial approximations are reasonably close to the desired roots, then two iterations are sufficient for most practical problems. The computational order of convergence 
, defined by (1.10), matches very well the theoretical results given in Theorem 4.6. Finally, from Table 4.8 (Example 4.6) we observe that the methods (4.2) and (4.56) show relatively slower convergence rate compared to other tested methods. Note that finding roots of the tested polynomial 
is not an easy task because this polynomial has very large coefficients in magnitude and roots grouped in the rectangle 
in the complex plane making a cluster, see Figure 4.1. However, other numerical examples (such as Examples 4.3, 4.4 and 4.5) show that the methods (4.2) and (4.56) are not worse compared to other tested methods.
Fig. 4.1 Distribution of the roots of the polynomial 
4.3 Optimal methods based on weight functions
In this section we present several families of three-step methods with optimal order 
using 
F.E. Consequently, these methods support the Kung-Traub conjecture. These families are based on approximations of the derivative 
at the points y (second step) and z (third step) using suitable weight functions with arguments that depend on available data. Note that this classification is not strict; for example, the multipoint methods (4.2), (4.4), (4.20), and (4.21) could also be regarded as methods based on weight function(s).
4.3.1 Family based on the sum of three weight functions
First we consider a family of three-point methods constructed by Thukral and Petković (2010). The first two steps constitute King’s family (4.19), while the third step is constructed using three weight functions determined in such a way that the order of convergence of the three-step method is eight.
For simplicity, we omit the iteration index k and denote a new approximation with 
. We start with the three-step scheme
(4.47)
(4.48)
are independent variables and 
, and 
are arbitrary real functions which should be determined so that the three-point method (4.47) is of order eight. If 
is an approximation to the zero 
of f, then the corresponding iterative method is defined by
We will use Taylor’s expansion about the zero 
to express 
, 
, and 
as series in terms of 
, 
, and 
, respectively. Then, according to (4.48), we represent 
, 
, and 
as Taylor polynomials in 
.
Assume that x is sufficiently close to the zero 
of f, then 
, 
, and 
are close enough to 0. Now represent the real functions 
, and 
appearing in (4.47) by Taylor’s series about 0,
(4.49)
(4.50)
(4.51)
The expressions of Taylor polynomials (in 
) of functions involved in (4.47) are cumbersome and lead to tedious calculations so that we use symbolic computation to find candidates for 
, and 
.
We will find the coefficients 
of the expansions (4.49)–(4.51) using a simple program in Mathematica and an interactive approach explained by the comments C1–C5 (see, also, Section 2.4). First, let us introduce the following abbreviations used in this program.
, 
, 
, 
,
, 
, 
, 
Program (written in Mathematica.)
fx=f1a∗(e + c2∗eˆ2 + c3∗eˆ3 + c4∗eˆ4 + c5∗eˆ5 + c6∗eˆ6 + c7∗eˆ7 + c8∗eˆ8);
f1x = D[fx,e]; ey = e-Series[fx/f1x,{e,0,8}];
fy = f1a∗(ey + c2∗eyˆ2 + c3∗eyˆ3 + c4∗eyˆ4);
ez = ey-fy/f1x∗(fx + b∗fy)/(fx+(b-2) fy);
fz = f1a∗(ez + c2∗ezˆ2 + c3∗ezˆ3 + c4∗ezˆ4);
t1 = fy/fx; t2 = fz/fy; t3 = fz/fx;
fi = fi0 + fi1∗t1 + fi2/2∗t1ˆ2 + fi3/6∗t1ˆ3;
psi1 = 1; fi2 = 10--4b; a7 = Coefficient[e1,eˆ7]//Simplify
om1=4; fi3=12bˆ2-72b+72; a8=Coefficient[e1,eˆ8]//Simplify
Comment C1: From the expression of the error 
we observe that 
is of the form
(4.52)
The iterative three-point method 
will have order eight if the coefficients of the expansions appearing in (4.49)-(4.51), are determined in such a way to annihilate 
, 
, 
, 
in (4.52). We find these coefficients equating shaded expressions in the boxed formulae to 0. First, from Out[a4] we have
We take 
for simplicity, and hence, 
. Then 
, 
, 
, and 
are calculated using the already found coefficients. We could take 
, but this gives only a slight generalization. Comment C2: From Out[a5] we see that the choice 
gives 
. Comment C3:
vanishes if we take simultaneously 
. Comment C4: We obtain 
by choosing 
and 
. Comment C5: Substituting the quantities 
in the expression of 
, found in the described interactive procedure, we obtain the error relation
(4.53)
Therefore, to provide the eighth order of convergence of the three-point method (4.47), it is necessary to choose the triplet of functions 
such that their truncated expansions in (4.49)–(4.51) fulfill the conditions
(4.54)
The higher order term in the expansions of 
and 
(see (4.50) and (4.51)) cannot increase the order of convergence of the considered three-point methods so that we take the simplest form of 
and 
according to (4.50), (4.51), and (4.54), that is,
Slightly more general choice of 
can be attained by introducing a real parameter a:
(4.55)
The asymptotic error constant 
may depend on a, see Remark 4.10. Similar introduction of a parameter for 
is pointless since such a parameter does not appear in the expression for 
, which means that its influence is negligible. Consequently, the three-point scheme (4.47) essentially depends only on one weight function 
since 
and 
are of limited forms, as presented above.
Starting from the iterative scheme (4.47), Thukral and Petković (2010) derived the following family of three-point methods for solving nonlinear equations
(4.56)
is an arbitrary real function satisfying the conditions
(4.57)
and a and 
are real parameters.
The previous arguments and discussion can be summarized in the following theorem proved by Thukral and Petković (2010).
Theorem 4.7
If an initial approximation 
is sufficiently close to a zero 
of f and a real function 
in (4.56) is chosen so that the conditions (4.57) hold, then the three-point method (4.56) has order of convergence eight.
We found that the three-point method (4.56) has optimal order. Its efficiency index is 
, which is better than the efficiency index 
of any two-point fourth-order method requiring three F.E. We recall that the efficiency index of Newton’s method is only 
.
Remark 4.10
According to (4.53), the asymptotic error constant of the family (4.56)
is
However, this expression (4.53) is correct if Taylor’s series in (4.49)–(4.51) are truncated to the displayed members. For a particular triplet of functions (
), the asymptotic error constant is given by a specific expression, see, e.g., Methods 1–4 below. Moreover, taking 
(see (4.55)) in (4.56), one can show that the asymptotic error constant 
depends on both parameters a and 
.
Remark 4.11
We can take some other (suitably chosen) methods in (4.56) instead of King’s method (4.19). For example, the choice of Maheshwari’s method (2.85), presented by Maheshwari (2009), gives the three-point method
satisfies the conditions
In this particular case we obtain the error relation
The function 
in (4.56) can take many forms satisfying the conditions (4.57). For example, the following two functions depending on King’s parameter 
,
(4.58)
and
(4.59)
satisfy the conditions (4.57). In practice, it is reasonable to choose 
as simple as possible. For demonstration, in what follows we give four particular functions 
together with the asymptotic error constants of the corresponding three-point method (4.56) putting 
in the second step, that is, the first two steps in (4.56) are defined by the Ostrowski method (2.47).
Method 1. Iterative formula (4.56) with 
(follows from (4.58) for 
):
Method 2. Iterative formula (4.56) with 
(follows from (4.59) for 
):
Method 3. Iterative formula (4.56) with 
:
Method 4. Iterative formula (4.56) with 
:
Let us note that only the coefficient next to 
is changeable in the asymptotic error constants given above.
The three-point methods (4.56) have been tested on a number of nonlinear equations. To obtain very high accuracy and avoid the loss of significant digits, we employed multi-precision arithmetic in the computational software package Mathematica. As expected, the convergence of the proposed methods is remarkably fast, see Examples 4.7 and 4.8 presented below. The three-point methods (4.56) have been compared to some existing three-point methods having the same convergence rate (eight) and the same computational efficiency 
. Among the optimal methods, we have chosen the Kung-Traub families (3.1) and (3.2) given at the beginning of Chapter 3, and the Bi-Wu-Ren family (4.2) with the above-displayed Methods 1–4.
We select two examples for demonstration. The computational order of convergence, evaluated by the approximate formula (1.10), is included in Tables 4.9 and 4.10.
Example 4.7
We have applied the three-point methods (4.56) (Methods 1–4), (3.1), (3.2), and four variants of (4.2) to the function
To find the zero 
of f we have chosen 
. The absolute errors 
in the first three iterations are given in Table 4.9.
Example 4.8
We have applied the same methods from Example 4.7 to find the zero 
of the function
starting from 
. The absolute errors 
in the first three iterations are given in Table 4.10.
Table 4.9 
Table 4.10 
From the results displayed in Tables 4.9 and 4.10 and a number of numerical experiments, it can be concluded that all tested methods demonstrate approximately similar behavior for good initial approximations. We also observe that the computational order of convergence 
mainly well coincides with the theoretical result.
Remark 4.12
Consider the three-point optimal method presented by Thukral (2010)
(4.60)
. It is obvious that the choice 
in the second step of (4.56) gives
which is equivalent to the second step in (4.60). Functions 
and 
appearing in (4.56) take special forms in (4.60),
(4.61)
where 
and 
. From (4.61) we find
which coincides with the conditions (4.54) for 
, already chosen in the second step of (4.56). According to the previous consideration, we can conclude that the method (4.60) is a special case of the family (4.56) for 
, and 
and 
given by (4.61). Formally, we can take 
in (4.56) but this choice is irrelevant. More details are given by Džunić (2011).
4.3.2 Liu-Wang’s family
In relation to the generalized method (4.56) and its special cases, we may consider another three-point method with similar structure proposed by Liu and Wang (2010)
(4.62)
and G is an arbitrary real function satisfying the conditions 
.
Observe that the second step of (4.62) is obtained from the second step of (4.56) by setting 
(giving Ostrowski’s method (2.47)). Besides, the weight function 
in the third step of (4.56) gives a number of different methods. Moreover, having in mind that 
and taking
(4.63)
in (4.56), we observe that the conditions (4.57) are satisfied (for 
). But the choice of 
defined by (4.63) gives the first term of the expression within the square brackets in the third step of (4.62). Since the functions G (in (4.62)) and 
(in (4.56)) satisfy the same conditions, it is obvious that the three-point method (4.62) is a special case of (4.56).
The discussed similarity cannot be regarded as a drawback since the method (4.62) is only a special case of a family with rich structure proposed by Liu and Wang (2010)
(4.64)
Where 
, and W are real-valued functions. Note that the family (4.64) combines the two-point family (4.37) (Petković and Petković, 2010) and the third step of (4.47).
Conditions that provide the eighth order of the family (4.64) are given in the following theorem (Liu and Wang, 2010).
Theorem 4.8
Assume that functions 
, and f are sufficiently differentiable and f has a simple zero 
. If an initial approximation 
is close enough to 
, then the family of methods defined by (4.64) has order eight under the following conditions
Using a weight function of the form employed in the second step of (2.73) and (2.74), and three additional weight functions in the third step similarly as in (4.64), Wang and Liu (2010a) have developed a general family of the form
(4.65)
Where 
, and W are real-valued functions whose arguments are clearly defined in (4.65).
The following theorem has been proved by Wang and Liu (2010a).
Theorem 4.9
Assume that functions 
, and f are sufficiently differentiable and f has a simple zero 
. If an initial approximation 
is close enough to 
, then the family of three-point methods defined by (4.65) has order eight under the following conditions
The proofs of Theorems 4.8 and 4.9 were derived by Liu and Wang (2010) and Wang and Liu (2010a) using a standard technique by Taylor’s expansions. As already noted, assertions of theorems whose proofs are rather lengthy and use Taylor’s series can be proved using symbolic computation by computer algebra systems. Moreover, symbolic computation is a powerful tool for establishing conditions for the requested order of convergence, as shown in the case of the method (4.56).
The presence of even four weight functions in (4.64) and (4.65) offers the possibility of producing many different three-point methods. On the other hand, an extensive study is requested to find a quadruplet 
of functions which would produce the best results. Choosing these functions as simple as possible is usually a good strategy for decreasing computational cost of obtained methods, although this is not a guarantee for the best choice due to very complex structure of the considered iterative formula. Wang and Liu (2010a) have proposed several simplified variants of (4.64) and (4.65) taking specific forms of the weight functions. We present one of them obtained by choosing 
(Ostrowski’s method (2.47)) and 
in (4.65):
(4.66)
It was proved by Wang and Liu (2010a) that the family (4.66) of three-point methods reaches eighth order if
Observe that this is just a special case of the family (4.56) for 
and 
, see the conditions (4.57).
4.3.3 Family based on two weight functions
Now we present another family of three-point methods with order eight (Džunić et al., 2011), constructed by using two weight functions. We start with a “naive” three-point method:
(4.67)
In fact, Newton’s method is successively applied three times. According to Theorem 1.3, this “three-step method” has order 
, but it requires six F.E. per iteration. The efficiency index of (4.67) is 
, which is equal to that of Newton’s method. To improve the computational efficiency, the iterative scheme (4.67) has to be modified in order to decrease the number of F.E. per iteration but keeping the eighth order.
The approach presented by Džunić et al. (2011) consists of the substitution of the derivatives 
and 
in the second and third step of (4.67) by the approximations
(4.68)
and p and q are some functions of one and two variables, respectively. These functions should be chosen in such a way to provide the eighth order of designed three-point methods with fixed number of four function evaluations. Notice that the entries t and s do not require any new information.
Starting from the scheme (4.67) and the approximations (4.68), the following family of three-point methods, dealing with two weight functions, was stated by Džunić et al. (2011),
(4.69)
The functions p and q should be determined in such a way that the iterative method (4.69) attains eighth order. To realize this plan, the method of undetermined coefficients is used together with Taylor’s series about 0 for 
and about (0,0) for 
, thus,
(4.70)
(4.71)
Here the subscripts denote the respective partial derivatives; for example,
Let 
be the error in the kth iteration. For simplicity, we sometimes omit the iteration index and write 
instead of 
. To find the coefficients 
in the expansions (4.70) and (4.71), symbolic computation in Mathematica is employed together with an interactive approach explained by the comments C1–C7 given below.
Introduce the following abbreviations used in the presented program.
, 
, 
, 
,
, 
, 
,
, 
, 
,
, 
, 
, 
.Program (written in Mathematica)
fx = f1a∗(e + c2∗eˆ2 + c3∗eˆ3 + c4∗eˆ4 + c5∗eˆ5 + c6∗eˆ6 + c7∗eˆ7 + c8∗eˆ8);
f1x = D[fx,e]; ey = e-Series[fx/f1x,{e,0,8}];
fy = f1a∗(ey + c2∗eyˆ2 + c3∗eyˆ3 + c4∗eyˆ4 + c5∗eyˆ5 + c6∗eyˆ6
t = Series[fy/fx,{e,0,8}];f1y = f1x/(p0 + p1∗t + p2∗tˆ2/2 + p3∗tˆ3/6);
fz = f1a∗(ez + c2∗ezˆ2 + c3∗ezˆ3 + c4∗ezˆ4);
f1z = f1x/(q0 + qt∗t + qs∗s + qtt∗tˆ2/2 + qts∗t∗s + qss∗sˆ2/2
+ 1/6∗(qttt∗tˆ3 + 3qtts∗tˆ2∗s + 3∗qtss∗t∗sˆ2 + qsss∗sˆ3));
e1 = ez-Series[fz/f1z,{e,0,8}]//Simplify;
q0=1; a5 = Coefficient[e1,eˆ5]//Simplify
qt=2; a6 = Coefficient[e1,eˆ6]//Simplify
qs=1; qtt=2+p2; a7 = Coefficient[e1,eˆ7]//Simplify
qts=4; p3=0; qttt=0; p2=4; qtt=6;
From the expression for the error 
we observe that 
takes the form
(4.72)
The iterative three-point method 
will have order eight if the coefficients appearing in (4.70) and (4.71) are determined such that 
, 
, 
, 
, 
, 
(in (4.72)) all vanish. These coefficients are calculated by equating shaded expressions in the boxed formulae to 0. Comment C1: First, to provide the fourth order of convergence of the iterative method consisting of the first two steps of (4.67), it is necessary to obtain the error 
. In other words, the coefficients 
and 
in the expression 
should vanish. From Out[b2] we have 
so that we take 
(given in the shaded box) to eliminate 
. Comment C2: From Out[a3] we have the equation 
and we take 
to annihilate 
.
We proceed in a similar way and from C3–C7 we find the remaining coefficients of the expansions (4.70) and (4.71):
In this manner we come at the following theorem (Džunić et al., 2011):
Theorem 4.10
If p and q are arbitrary real functions with Taylor’s series of the form
(4.73)
(4.74)
then the family of three-point methods (4.69) is of order eight. It is assumed that higher order terms in (4.73) and (4.74), which follow after the dots, can take arbitrary values.
Relations in C6 do not deliver unique coefficients. We take 
and 
to eliminate the term 
in (4.70) and (4.71), for simplicity. This is emphasized in Theorem 4.10. We take no care of the terms 
, and 
since they are of higher order and do not influence the order of convergence (not greater than 8). A deep analysis shows that the following more general coefficients can be obtained:
According to these conditions we can state the following more general theorem.
Theorem 4.11
If p and q are arbitrary real functions with Taylor’s series of the form
(4.75)
(4.76)
then the family of three-point methods (4.69) is of order eight. It is assumed that higher order terms in (4.75) and (4.76), which follow after the dots, can take arbitrary values.
Remark 4.13
The entries 
and 
in (4.68) are calculated using the already found quantities 
, 
, and 
so that the total number of F.E. per iteration of the method (4.69) is four. According to this fact and Theorems 4.10 and 4.11, it follows that the iterative method (4.69) is optimal in the Kung-Traub sense and has the efficiency index 
.
The functions p and q in (4.69) can take many forms that satisfy the conditions (4.73)–(4.76). In this way some new and some existing three-point methods in particular forms can be obtained from (4.69). For computational purpose, it is reasonable to choose p and q as simple as possible, for example, in the form of rational functions as follows:
(4.77)
(4.78)
, 
, 
, 
are arbitrary constants. We give the following specific forms:
(4.79)
and 
follow from Remark 4.14
According to C7, the asymptotic error constant of the family of three-point methods (4.69) is
and depends on arbitrary constants 
and 
. For a particular pair of functions p and q the asymptotic error constant is given by a specific expression. For example, choosing two pairs of functions 
and 
(listed in (4.79)) into the iterative formula (4.69), we obtain
4.3.4 Geum-Kim’s families
Geum and Kim (2010) have proposed a variant of the family (4.2) presented by Bi et al. (2009b). They have used the approximation (4.1) of 
(derived by Bi et al. (2008)) and constructed the family of three-point methods
(4.80)
is a real-valued weight function to be determined later and
(4.81)
is a King-like correction (see (4.19)), which reduces to King’s correction 
for 
.
Remark 4.15
In fact, the authors dealt with an analytic function 
. However, although most iterative methods presented in this book can also handle complex zeros, for simplicity we consider real functions and root-finding methods on real domain.
The following convergence theorem was proved by Geum and Kim (2010):
Theorem 4.12
Let 
be an initial approximation in a sufficiently small neighborhood of a zero 
of f. The family of three-point methods (4.80) attains eighth order if
Remark 4.16
The terms 
and 
in King-like correction 
do not influence the order so that they can be omitted. In this way the iterative method (4.80) becomes slightly simpler. On the other hand, setting, for example, 
, 
, one obtains considerably relaxed condition 
with 
. Such a choice gives the simplest form 
of H.
Employing the first two steps as in (4.80), Geum and Kim (2011a) have presented other family of three-point methods,
(4.82)
and 
is given by (4.81).
The choice of parameters 
, and 
in 
plays a crucial role in maximizing the convergence order of (4.82), as shown in the following convergence theorem (Geum and Kim, 2011a):
Theorem 4.13
Let 
be an initial approximation in a sufficiently small neighborhood of a zero 
of f. If 
and 
, then the family of three-point methods (4.82) is of order eight and the error relation
holds.
Note that the parameters 
and 
in the family (4.80) do not influence the order and their main role is to simplify the convergence condition (providing 
, see Remark 4.16). Moreover, they can be omitted in (4.80) to simplify 
. However, the situation is quite different in the case of the family (4.82); their choice in terms of 
directly controls the order of convergence of (4.82). Since the parameters 
and 
are expressed as functions of 
, the King-like correction (4.81) depends only on one parameter 
so that the authors referred (4.82) to as a uniparametric family.
The third family of three-point methods developed by Geum and Kim (2011b) also deals with the same methods in the first two steps,
(4.83)
The weight function 
in the third step is defined by
and consists of the King correction (the first addend) and a function H of two variables. The function H and the relationship among the parameters 
should be determined so that the order of convergence is eight. This is the subject of the following theorem (Geum and Kim, 2011b).
Theorem 4.14
Let 
be an initial approximation in a sufficiently small neighborhood of a zero 
of f. The family of three-point methods (4.83) attains order eight if
and 
hold.
The family (4.83) depends on two parameters a and 
and it is referred to as a biparametric family. The proofs of the presented three root-finding families (4.80), (4.82), and (4.83) were derived by a standard technique based on lengthy Taylor’s expansions and will be omitted.
4.4 Eighth-order Ostrowski-like methods
In this section we present several methods based on Ostrowski’s method (2.47) at the first two steps and constructed by using derivative estimation and weight functions in the third step to approximate 
. Approximations to 
employ only available data to decrease the number of F.E. At the same time, they are constructed as to be order-preserving, that is, they must be of good quality to provide the eighth order. Note that the presented families given below are listed without any specific characteristics such as priority or complexity.
4.4.1 First Ostrowski-like family
We start with three-step scheme (omitting iteration index for simplicity)
(4.84)
Recall that the first two steps form Ostrowski’s two-point method (2.47) of order four.
The iterative method (4.84) has order eight but it requires five F.E., which is expensive from a computational point of view. To decrease this cost from 5 to 4 F.E., it is necessary to approximate 
in the third step of (4.84) using the available data 
. We seek this approximation in the form
(4.85)
where 
, and 
are sufficiently differentiable real-valued functions with the arguments
The functions 
, and 
should be determined in such a way that the iterative method (4.84) attains the order eight. For this purpose, the method of undetermined coefficients is applied with the help of Taylor’s series about 0 since 
, and 
when 
. There follows
(4.86)
(4.87)
(4.88)
The simplest method for determining coefficients of the above Taylor expansions is the use of symbolic computation by a computer algebra system and an interactive procedure (Comments C1–C4 in the program below), as already carried out for some of the previously considered methods. Apart from the already used abbreviations in previous programs in similar procedures, we also introduce
, 
, 
, 
,
, 
,
, 
.Program (written in Mathematica)
fx = f1a∗(e + c2∗eˆ2 + c3∗eˆ3 + c4∗eˆ4); f1x = D[fx,e];
ey = e-Series[fx/f1x,{e,0,8}];
fy = f1a∗(ey + c2∗eyˆ2 + c3∗eyˆ3 + c4∗eyˆ4);
ez = ey-Series[1/(1-2t)∗fy/f1x,{e,0,8}];
fz = f1a∗(ez + c2∗ezˆ2 + c3∗ezˆ3);
Comment C1: From the expression for the error 
we observe that 
is of the form
(4.89)
The iterative three-point method (4.84) will have order eight if we find the coefficients of the expansions appearing in ((4.86)–(4.88)) such that 
, 
, 
, 
(in (4.89)) all vanish. We determine these coefficients by equating shaded expressions in the boxed formulae to 0. First, from Out[a4] we have
Without loss of generality, we can take
with the benefit that the denominator 
of 
becomes 1 simplifying subsequent expressions.
In what follows, equating coefficients 
, 
, 
to 0, we obtain:
.
.
.Comment 5: Substituting the quantities 
in the expression for 
, found in the described interactive procedure, we obtain the error relation
(4.90)
determine the error relations for particular weight functions 
, and 
, it is necessary to substitute 
in (4.90). Observe from (4.90) that 
must be bounded.
According to the above analysis, the following theorem was stated by Džunić and Petković (2012b).
Theorem 4.15
If 
is a sufficiently close approximation to a zero 
of f, then the family of three-point methods
(4.91)
order eight if the functions 
, and 
are sufficiently differentiable and satisfy the following conditions:
(4.92)
higher order derivatives of 
, and 
, not explicitly given in (4.92), can take arbitrary values at the point 0.
The weight functions 
, and 
should be as simple as possible. One of the simplest forms is obtained by using Taylor polynomials of these functions according to (4.92), that is,
Hence the family (4.91) becomes
(4.93)
Using the approximations 
and 
for sufficiently small 
and 
, the method (4.93) can be written in a slightly modified form
give some other simple examples of the functions 
and 
:
is interesting to note that the functions 
and 
satisfy the requested conditions (4.92), but the calculation of an exponential function increases the computational cost so that such a choice is not advisable.
4.4.2 Second Ostrowski-like family
The next family based on the two-step Ostrowski method (2.47) was presented by Sharma and Sharma (2010b). They started with the following iterative scheme
(4.94)
and W is a real-valued weight function. The above method requires five F.E., which is too expensive for a three-point method. Again, the weight function W and an approximation to 
(depending only on available data) should be determined so that the method (4.94) attains optimal order eight.
The improvement of (4.94) was carried out through two steps:
1) apply first a simpler approximation to 
of less accuracy using a rational bilinear function;
2) improve the quality of approximation to 
taking a suitable weight function W.
The first step 1) (approximation of 
) is realized by a rational bilinear interpolation
(4.95)
where the parameters a, b, and c are determined from the interpolation conditions
(4.96)
From (4.95) and (4.96) we immediately obtain 
. Having in mind this value of a, from the last two conditions of (4.96) we form the system of two equations
solution of this system is
(4.97)
Differentiating (4.95) (with 
) yields
Now we substitute 
and taking into account the values of b and c given by (4.97), after a short arrangement we get
Therefore the three-step scheme (4.94) becomes
(4.98)
Assume that 
, which corresponds to the case without any weight function. Then we show by symbolic computation that the error relation of the method (4.98) is
In other words, the method (4.98) produces only seventh order in the absence of the weight function. The following theorem stated by Sharma and Sharma (2010b) gives the form of the weight function W that provides optimal order eight.
Theorem 4.16
If 
is a sufficiently close approximation to a zero 
of f, then the family of three-point methods (4.98) is of order eight if
The error relation is then
The following examples of the weight function W are given by Sharma and Sharma (2010b):
Remark 4.17
Considering the iterative formula (4.98) (with 
) we can observe that 
is approximated by
This approximation (providing order eight) is evidently better than that given by 
above (giving the seventh-order method), which can be usefully applied to other three-point methods of similar type.
can be obtained from the family 
4.4.3 Third Ostrowski-like family
Similarly as in the case of the families (4.91) and (4.98), Ostrowski’s method (2.47) has also been used for the first two steps of a family of three-point methods proposed by Cordero et al. (2011), that is
(4.99)
(4.100)
is an intermediate step and 
.
Throughout this book we follow a rule that only the intermediate approximation (step-point) which appears as an argument of the function f (whose zeros we are seeking) or its derivatives can be regarded as a composite step within the iteration of the considered multipoint method. For this reason, the point 
stands outside the scheme (4.99). In fact, the “quasi-step” (4.100) could be regarded as an intermediate step which enables the family to attain order eight. This is evident from the error relation
derived by Cordero et al. (2011). Consequently, the scheme 
cannot reach order higher than seven so that additional improvement is necessary. This intermediate calculation of 
by (4.100) can be regarded as a kind of preliminary corrector-sub-step for the third step.
There are four parameters in the family (4.99). The following theorem, stated by Cordero et al. (2011), gives relationship among these parameters which provides optimal order eight.
Theorem 4.17
If 
is sufficiently close to a zero 
of f and 
is satisfied, then the family of three-point methods (4.99) has optimal order eight.
Neither motivation nor derivation of the relation (4.100) has been given by Cordero et al. (2011) so that we present a short analysis for reader’s convenience. Considering the structure of possible three-point method 
, we observe that the term
in (4.100) is an approximation to 
. Taking Taylor polynomials
where 
, we may approximate 
in the following way
Substituting this approximation in the third step of the form
from the requirement that the order of the three-step method 
has to be seven, we find by symbolic computation
Hence
which leads to (4.100) with a small difference. Namely, it stands 
in (4.100) but the above analysis shows that this term can be simplified to 
preserving order 7 in the scheme 
and order 8 in the family (4.99).
giving the last step in the form
4.4.4 Family of quasi-Ostrowski’s type
We end this section with a family referred to as modified Potra-Pták method by Cordero et al. (2010). As in (4.99), the presented family uses one intermediate step and reads thus:
(4.101)
is an approximation of 
.
To approximate 
in the third step, the authors have stated by Cordero et al. (2010) a rather complicated procedure consisting of five successive steps:
;
;
;
;
.Recall that there are simpler approximations to the derivative in the third step presented in this chapter and, more generally, various interpolation techniques that can be usefully applied for this purpose.
As mentioned in Remark 2.7, the addend 
in the expression of 
in (4.101) can be omitted without losing the maximal order of convergence. Then (4.101) can be rewritten in the form
(4.102)
If an initial approximation 
is close enough to a zero 
of f, then the quantity 
is small enough so that we can write
so that the method (4.102) becomes
(4.103)
first two steps define Ostrowski’s two-point method (2.47) and 
is an approximation of 
chosen so that the method (4.103) is of order eight.
4.5 Derivative free family of optimal three-point methods
In this section we derive a family of three-point methods of order eight, requiring four F.E. per iteration. This means that the proposed family supports the Kung-Traub conjecture. Besides, this family does not use any derivative of a function f whose zeros are sought, which is another advantage since it is preferable to avoid calculations of derivatives of f in many practical situations. In Chapter 6 we will see that considerable improvement of convergence rate of basic derivative free methods can be attained by suitable variation of a free parameter in each iterative step without new F.E.
As in the case of the Kung-Traub family (2.109), we start with the derivative free method
(4.104)
of Steffensen’s type with quadratic convergence (see Traub, 1964, p. 185), where 
is a real constant. Let
(4.105)
be a function that appears in the Steffensen-like method (4.104). The following derivative free family of two-point iterative methods was derived by Petković et al. (2010c), see (2.91),
(4.106)
is given by (4.105),
and 
is a real-valued function of two variables. In view of Theorem 2.7, the fourth order of (4.106) is provided if the weight function h satisfies the conditions
(4.107)
We will see later that slightly stronger conditions on h enable the construction of a very efficient family of three-point methods.
Remark 4.20
Comparing double Newton’s scheme
(4.108)
(4.106), we see that 
presents an approximation to the first derivative 
in (4.108) assuming that 
is small enough. The derivative 
in the second step of (4.108) is approximated by 
, where 
satisfies the conditions (4.107). Several simple forms of the function h are given below:
;
;
;
;
.Note that the function 
gives the Kung-Traub method
(4.109)
method is obtained as a special case of the general Kung-Traub family (5.3) of derivative free methods, presented by Kung and Traub (1974).
Now we construct a family of three-point methods based on the two-step family (4.106). We start from the scheme where the first two steps are given by (4.106) and the third step is Newton’s method, that is
(4.110)
iterative scheme (4.110) is inefficient since it requires five F.E. For this reason, the derivative 
in the third step of (4.110) should be substituted by a suitable approximation in such a way that 1) only available data, not including calculation of derivatives, are used and 2) the order of convergence of a new iterative three-step scheme should be at least eight consuming four F.E. To provide these requirements, we apply Newton’s interpolating polynomial of degree three at the points 
, and 
, that is,
(4.111)
is obvious that 
. Differentiating (4.111) and setting 
, we obtain
(4.112)
semicolon in (4.112) separates the value of argument t from the nodes of interpolation. Substituting 
in (4.110), Džunić, M. Petković, and L. Petković have stated a family of three-point methods free of derivatives (Džunić et al., 2012),
(4.113)
is defined by (4.105). 
given by (4.112) (that is, the denominator of (4.113)) can be easily calculated by the five-step algorithm:
;
;
;
;
.Now we state the following convergence theorem for the family (4.113).
Theorem 4.18
If an initial approximation 
is sufficiently close to a zero 
of f and the weight function h satisfies the conditions (4.107), then the order of the family of three-point methods (4.113) is eight.
Proof.
Let 
be the Newton interpolating polynomial of degree m that interpolates a function f at 
distinct nodes 
contained in an interval 
and the derivative 
is continuous in 
. Then the error of Newton’s interpolation is given by the well-known formula
(4.114)
(see Theorem 3.1 for simple nodes, that is, 
).
For 
we have from (4.114)
taking 
. Hence
(4.115)
The errors at the first two steps of (4.113) are given by
(4.116)
and
(4.117)
where 
is the asymptotic error constant of the fourth-order family (4.106) (see Remarks 2.9 and (2.94)). From (4.116) and (4.117) we find
(4.118)
Substituting the differences given by (4.118) into (4.115), we obtain
and hence
(4.119)
Substituting (4.119) in the third step of the iterative scheme (4.113) we find
(4.120)
For Newton’s method we have
(4.121)
Also, observe that
(4.122)
Taking into account (4.121) and (4.122), we find from (4.120)
since 
. From the last error relation we conclude that the order of convergence of the family (4.113) is eight, which completes the proof of Theorem 4.18. 
Remark 4.21
In constructing methods with memory, which is the subject of Chapter 6, it is convenient to impose the following stronger conditions
(4.123)
of (4.107). Then the asymptotic error constant 
of the two-point method (4.106) is
symbolic computation in a computer algebra system (e.g., Mathematica or Maple) we derive the error relation of the three-point method (4.113) under the conditions (4.123),
(4.124)
The error relations of the three-point methods (4.113) for a particular forms 1)–5) of h, given above, can be obtained from (4.124). The corresponding expressions are listed below: (with 
)
References
1. Bi W, Ren H, Wu Q. New family of seventh-order methods for nonlinear equations. Appl Math Comput. 2008;203:408–412.
2. Bi W, Ren H, Wu Q. Three-step iterative methods with eight-order convergence for solving nonlinear equations. J Comput Appl Math. 2009a;225:105–112.
3. 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.
4. Chun C. A family of composite fourth-order iterative methods for solving nonlinear equations. Appl Math Comput. 2007a;187:951–956.
5. Chun C. Some fourth-order iterative methods for solving nonlinear equations. Appl Math Comput. 2008;195:454–459.
6. Cordero A, Hueso JL, Martı´nez E, Torregrosa JR. New modifications of Potra-Pták’s method with optimal fourth and eighth orders of convergence. J Comput Appl Math. 2010;234:2969–2976.
7. Cordero A, Torregrosa JR, Vassileva MP. Three-step iterative methods with optimal eighth-order convergence. J Comput Appl Math. 2011;235:3189–3194.
8. Džunić J. On the similarity of some three-point methods for solving nonlinear equations. Appl Math Comput. 2011;217:6633–6635.
9. Džunić, J., Petković, M.S., 2012b. A family of three-point methods of Ostrowski’s type for solving nonlinear equations. J. Appl. Math. 2012, Article ID 425867, 9 pages. doi:10.1155/2012/425867 http://dx.doi.org/10.1155/2012/425867.
10. Džunić J, Petković MS, Petković LD. A family of optimal three-point methods for solving nonlinear equations using two parametric functions. Appl Math Comput. 2011;217:7612–7619.
11. Džunić J, Petković MS, Petković LD. Three-point methods with and without memory for solving nonlinear equations. Appl Math Comput. 2012;218:4917–4927.
12. 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.
13. 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.
14. 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.
15. King RF. A family of fourth order methods for nonlinear equations. SIAM J Numer Anal. 1973a;10:876–879.
16. Kou J, Li Y, Wang X. A composite fourth-order iterative method for solving nonlinear equations. Appl Math Comput. 2007a;184:471–475.
17. Kou J, Wang X, Li Y. Some eighth-order root-finding three-step methods. Commun Nonlinear Sci Numer Simulat. 2010;15:536–544.
18. Kung HT, Traub JF. Optimal order of one-point and multipoint iteration. J ACM. 1974;21:643–651.
19. Liu L, Wang X. Eighth-order methods with high efficiency index for solving nonlinear equations. Appl Math Comput. 2010;215:3449–3454.
20. Maheshwari AK. A fourth-order iterative method for solving nonlinear equations. Appl Math Comput. 2009;211:383–391.
21. Neta B. On a family of multipoint methods for nonlinear equations. Int J Comput Math. 1981;9:353–361.
22. Neta B. A new family of higher order methods for solving equations. Int J Comput Math. 1983;14:191–195.
23. Neta B, Petković MS. Construction of optimal order nonlinear solvers using inverse interpolation. Appl Math Comput. 2010;217:2448–2455.
24. Ostrowski AM. Solution of Equations and Systems of Equations. New York: Academic Press; 1960.
25. Petković MS. On a general class of multipoint root-finding methods of high computational efficiency. SIAM J Numer Anal. 2010;47:4402–4414.
26. 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.
27. Petković MS, Petković LD. A one parameter square root family of two-step root-finders. Appl Math Comput. 2007c;188:339–344.
28. Petković MS, Petković LD. Families of optimal multipoint methods for solving nonlinear equations: a survey. Appl Anal Discrete Math. 2010;4:1–22.
29. Petković LD, Petković MS, Džunić J. A class of three-point root-solvers of optimal order of convergence. Appl Math Comput. 2010a;216:671–676.
30. Petković MS, Ilić S, Džunić J. Derivative free two-point methods with and without memory for solving nonlinear equations. Appl Math Comput. 2010a;217:1887–1895.
31. Sharma JR, Sharma R. A new family of modified Ostrowski’s methods with accelerated eighth order convergence. Numer Algorithms. 2010b;54:445–458.
32. Thukral R. A new eighth-order iterative method for solving nonlinear equations. Appl Math Comput. 2010;217:222–229.
33. Thukral R, Petković MS. Family of three-point methods of optimal order for solving nonlinear equations. J Comput Appl Math. 2010;233:2278–2284.
34. Traub JF. Iterative Methods for the Solution of Equations. Englewood Cliffs, New Jersey: Prentice-Hall; 1964.
35. Wang X, Liu L. Modified Ostrowski’s method with eighth-order convergence and high efficiency index. Appl Math Lett. 2010a;23:549–554.
36. Wang X, Liu L. New eighth-order iterative methods for solving nonlinear equations. J Comput Appl Math. 2010b;234:1611–1620.