\(^{\ast }\)Naval Postgraduate School, Department of Applied Mathematics, Monterey, CA 93943, USA, e-mail: bneta@nps.edu.

1 Introduction

The literature for solving a single nonlinear equation is vast, see Traub [ 1 ] and the more recent book by Petković et al. [ 2 ] . This is a fundamental problem in many areas of engineering and science. Here we are interested in analyzing the one-step family of third order methods for simple roots due to Popovski [ 3 ] . The method is given by

where the parameter \(r \ne 1.\) This family includes Chebyshev’s method [ 1 ] (when \(r=1/2\)), Halley’s method [ 4 ] (when \(r=-1\)), Euler-Cauchy’s method see [ 5 ] or [ 6 ] (when \(r=2\)). At the limit as \(r \to 1\) the method becomes the well known Newton’s method of order only two. See also Neta [ 7 ] .

Halley’s method was compared to various schemes available in the literature in Scott et al. [ 8 ] , Neta et al. [ 9 ] , [ 10 ] and [ 11 ] . Neta and Chun [ 10 ] has shown that Halley’s method has no extraneous fixed points, i.e. fixed points of the iteration that are not zeros of the function \(f(z)\) (see, Vrcsay and Gilbert [ 12 ] ). It is easy to show that all members of Popovski’s family of methods have no extraneous fixed points. It was shown that Halley’s method performed better than Chebyshev’s and Euler-Cauchy’s method. Therefore in the sequel we only compare Halley’s method to other members not considered in the literature. Recently, Herceg and Petković [ 13 ] analyzed Popovski’s family for \(r=-1\) (Halley) and \(r=-2\). They concluded that overall HM and Pm2 are better than Chebyshev and Euler-Cauchy. They also developed an equivalent family for multiple roots when the multiplicity is known in advance.

In this paper we consider also the cases \(r=-3\), \(r=-4\) and \(r=-8.\) We also develop a family for multiple roots that does not require the knowledge of the multiplicity. Instead we use the idea that the quotient \(\frac{f}{f'}\) must have simple roots at the points that \(f\) has multiple roots. The use of such function was mentioned in [ 1 ] , [ 2 ] and [ 14 ] . several third order methods for multiple roots were compared in [ 15 ] . Those methods all assume the knowledge of the multiplicity. See also [ 16 ] on Laguerre family of methods which tend to Halley’s method for multiple roots when the parameter tends to zero.

2 Corresponding Conjugacy Maps for Quadratic polynomials

Given two maps \(\phi \) and \(\psi \) from the Riemann sphere into itself, an analytic conjugacy between the two maps is a diffemorphism \(H\) from the Riemann sphere onto itself such that \(H \circ \phi = \psi \circ H\). Here we consider only quadratic polynomials. For more details, see Amat et al. [ 17 ] and Beardon [ 18 ] .

Let \(q(z)=((z-a)(z-b)),\ a\neq b\) and let \(M\) be the Möbius transformation given by \(M(z)={\frac{z-a}{z-b}}\) with its inverse \(M^{-1}(u)={\frac{ub-a}{u-1}}\), which may be considered as a map from \(\mathbb {C}\cup \{ \infty \} \). We then have

and \(A\) is given as above. The computation was done using Maple symbolic software. â–¡

3 Extraneous fixed points

The iterative procedure given by (1) can be written as

A fixed point of the iteration is a point \(\zeta \) such that \(R(\zeta )=0\). For our method, there are points \(\zeta \) which are not the solution of the nonlinear equation. These points are called extraneous fixed points. The points are classified as attracting, repelling or indifferent, based on the derivative of \(R_m\).

In our case the map \(R_m\) is given by

For the quadratic polynomial \((z-a)(z-b)\), we have

This map for any value of \(m\) vanishes at \(z=a\), \(z=b\) and \(z=\frac{a+b}2\). The last one is the only extraneous fixed point.

We have found that \(|R’_m (\frac{a+b}2)| {\gt} 1 \) for all values of interest of \(m\) and thus the point is repelling. These results are demonstrated in figure 1 where we can see that the boundary of the basins is the imaginary axis and the repelling point is on the boundary.

4 Numerical experiments

In this section, we compare 5 members of Popovski’s method. The methods are:

• HM, Halley’s method \(r=-1\)

• Pm2, Popovski’s method with \(r=-2\)

• Pm3, Popovski’s method with \(r=-3\)

• Pm4, Popovski’s method with \(r=-4\)

• Pm8, Popovski’s method with \(r=-8\)

The computation of the cubic root (for \(r=-3\)) is more expensive than square root and thus in the case of \(r=-4\) and \(r=-8\), we have used square root successively.

We ran these five methods on seven examples on a 6 by 6 square centered at the origin. The functions are:

The square is divided horizontally and vertically by equally spaced lines. We took the intersection of all these lines as initial points in the complex plane for the iterative schemes. The code collected the number of iterations required to converge within a tolerance of \(10^{-7}\) and the root to which the sequence converged. If the sequence did not converge within 40 iteration, we denote it as a divergent point. Each point is colored by the color corresponding to the root. Note that we have used 6 different colors, therefore some roots will have the same color but they are far apart. Moreover, the shade of the color is darker for slower converging initial point. A divergent point is colored black. We also collected the CPU run-time to execute the code on all initial points using MacBook Pro computer.

In figure 1 we have depicted the basins of attraction for the 5 methods of the first function. It is clear that all methods have performed the same and very well. The basins are separated by a vertical line through the origin, separating the square exactly in the middle. There are no lobes.

We have also collected in ??, the average number of iterations per point for each scheme, the CPU run-time in seconds and the percentage of divergent points. The method Pm8 has the lowest number of iterations but the other schemes use only slightly more. On average Pm8 uses 4.89 and HM (the highest) uses 5.82. The fastest method is HM and the slowest is Pm3. The extra cost of Pm2-Pm4 and Pm8 is compensated by having fewer divergent points. But maybe Pm3 is much too costly to justify its use.

The basins of attraction for the methods in the second example are given in figure 2. Again Pm8 has the lowest number and HM the highest number of iterations. In fact this is true consistently for all seven examples. The method HM is again the fastest, but it has more divergent points than Pm2, Pm4 and Pm8.

The numerical results over the seven examples show that Pm8 uses the lowest number of iterations but require more CPU run-time than the others. The fastest methods on average are HM and Pm2 and the slowest method is Pm3. In terms of divergent points Pm3, Pm4 and Pm8 have fewer than other methods on average. In fact, HM has fewer divergent points only for \(f_6\). In all other examples, Pm8 has the lowest number. We can conclude that Pm2 and Pm4 are competitive except for the CPU run-time. Pm3 is the slowest of all because of the cost of computing the cubic root at each step. We should note that for the non-polynomial (last) example the basins are not equally divided as in the first example, even though both have the same roots \(z=\pm 1.\)

We have included a problem related to Planck’s radiation law [ 19 ] . The energy density \(H(y)\) is related to the wavelength of radiation (\(y\)), absolute temperature of the black-body (\(T\)), Boltzman constant (\(k\)), speed of light (\(c\)) and Planck’s constant (\(h\)) via

In order to evaluate the wavelength corresponding to the maximum energy density, we solve \(H'(y)=0\). Let us introduce the variable \(x=\frac{ch}{ykT}\), then we get

The two solutions of this equation are \(x_1=0\) and \(x_2=5+LambertW(-5e^{-5})\approx 4.9651142317.\) For the LambertW function see Corless et al. [ 20 ] . Clearly the only physical solution is the second. We ran all 5 methods on this example on a rectangle \([-3,8]\times [-3,3]\) and the results did not change our conclusions.

5 Multiple roots

In contrast to Herceg and Petković, we developed a family of methods for multiple roots by applying Popovski’s family to the quotient \(\frac{f}{f'}\). Of course, this will require the knowledge of the third order derivative of \(f\) and thus the number of function-evaluation per iteration is increased by one.

The family of methods becomes

where \(g(z)=\frac{f(z)}{f'(z)}\).

We ran five members of the family, denoted gHM (\(r=-1\)), gPm2 (\(r=-2\)), gPm3 (\(r=-3\)), gPm4 (\(r=-4\)) and gPm8 (\(r=-8\)) on six examples with various multiplicities and various sizes of squares centered in the origin. Because the domains are of different sizes, then the number of initial points is different. Therefore we should not average the results across the examples as was done in the simple root case, but take the CPU run-time per, say, 1000 initial points.

The basins of attraction for the first example are given in figure 8. It seems that Halley’s method has more lobes at the boundary than the other methods.

We have collected the numerical results in ??. Note that table 5 lists the CPU run-time in sec per 1000 initial points to account for the disparity in domain size. The method gPm2 has the lowest number of iterations in the first example, gPm4 in the second example. The member gHm has the lowest number of iterations in ?? and also on average across the examples. The member gPm8 has the lowest number in ??. The method gPm3 never reached that low. Based on table 5, we see that the run-time is the highest for gPm3, even higher than gPm8. The fastest method in four examples and average overall is gHM followed by gPm4 and gPm8. The number of divergent points is zero for gHM for ??. For example 1 all methods have the same number of divergent points. For example 4, all methods except gHM have the same small number of divergent points. On average gPm2 has the lowest number of divergent points.

Based on the 6 examples we find that gHM and gPm2 are better than the other members tested.

6 Conclusions

In this manuscript, we have analyzed five members of the Popovski’s family. We have noted that methods with \(r=-2^k\) for k integer can use the square root successively and cost less than using \(1/r\) power directly. In the case of simple roots, we have shown that there is some benefit in taking \(r=-2\) and \(r=-4\). In the multiple root case, we find that gHm and gPm2 are better than the other members. This is the same conclusion reached by Herceg and Petković for their idea for multiple roots requiring the knowledge of the multiplicity instead of another function evaluation.