By virtue of (3.39) the condition (3.22) is satisfied for large \(n\). Then by Theorem 3.2, the relation (3.29) holds. Using (3.39) in (3.29), we get

The proof is completed.

However, the speed of convergence of these iterations depends on the factor \(q_1\) and \(q\) in (3.39) and (3.40), respectively. Since \(q_1=q^{k+2}{\lt}q\) for \(k=1,2,3\), one can expect a more rapid convergence of iteration (3.8). Of course, the higher is acceleration of iteration attained at \(k=3\).

From (3.39) and (3.40) it is clear that the iteration (3.8) converges to \(x^*\) more rapidly than iteration (3.6) by virtue of \(q_1=q^{k+1}{\lt}q\). This accelerating procedure is useful, especially at the beginning of iterations, but under condition (3.22). From Theorem 3.3, it is clear that the sequence \(\{ y_n\} \) given by (3.8) together with (3.6) can be considered as a new iteration process with a small factor compared to (3.6). The acceleration procedure is achieved without additional calculations, so that the iteration (3.8) possesses a high computational efficiency. However, despite the sequence \(x_n\) is monotone, the new iteration (3.8) may not be monotone. For instance, when \(k=1\) it is easy to show that

From this it is clear that

and

Let us know two successive approximations \(x_{n}\) and \(x_{n+1}\), for which

holds. We consider

The acceleration technique will be the same as a previous case with \(m=1\). In this case, according to (3.45) we have \(P_k(0)P_k(1)=f(x_{n})f(x_{n+1}){\lt}0\) for \(k=1,2,3.\) Hence, Eq. (3.13) has a root \(t_{\textnormal{opt}}\in (0,1)\). Obviously, the new approximation

will be situated more close to \(x^*\) as compared to \(x_{n}\), \(x_{n+1}\) and Theorem 3.2 holds true for this case, too. It indicates that the two-sided approximations are useful not only for estimations of roots, but also for finding it approximately with a higher accuracy. Of course, the acceleration procedure (3.8) can be continued further with \(x_{n+m}:=y_n\), \(x_n:=x_{n+m}\) and with \(t{\gt}1\) if \(y_n\) and \(x_{n+m}\) are located on side of \(x^*\) and with \(t\in (0,1)\) if \(y_n\) and \(x_{n+m}\) are located on two-sides of root. Note that the accelerating procedure (3.8) is applicable not only for iterations (3.6), but also for any iteration, in particular, for the following iterations (A), (B), (C) and (D).

Now we consider the accelerated iteration

The iteration (A) is a damped Newton’s method [ 20 , 17 ] with optimal parameter \(\tau _n=t_{\textnormal{opt}}\). The first step \(y_n\) is used for finding the optimal parameter.

which completes the proof of the Theorem 3.4.

Now let us consider another three-step iteration

Note that if \(t\equiv 1\) in (B), then it leads to

The iteration (\(B'\)) is a particular case of scheme (40) given in [ 16 ] with \(\sigma =0\) end \(\tau =1\) and has a third order of convergence. Therefore, the iteration (B) can be considered as improvement of iteration (B\('\)).

where

From this and from (3.52) we obtained

i.e., we have

which means that the convergence order of iteration (B) is equal to \(d=2k+3\), \(k=1,2,3\).

From the Theorem 3.5, we see that the convergence order of iteration (B\('\)) can be increased two or four units at the expense of only two additional evaluations of the function. So the order of convergence and the computational efficiency of the method are greatly improved.

In [ 5 ] Algorithm 2 was constructed:

and it is proved that the order of convergence equals 5, 6, 7 depending on a suitable choice of two-variable function \(H(x_n,y_n)\). For comparison purpose we can rewrite iteration (B) as

We see that these two methods are different from one another only by chosen factors \(t\) and \(H(x_n,y_n)\).

Now we consider the following iteration:

The iteration (C) can be considered as improvement of iteration

since if \(t\equiv 1\) in (C), then it leads to (C\('\)).

In [ 16 ] , it was proven that the convergence order of (C\('\)) is four.

From (C), we find that

Substituting here the expansion of \(f(x^*)\)

we have

Using the last estimate in (3.52), we obtain

which means that the convergence order of iteration (C) equals \(d=2(k+2)\), \(k=1,2,3\).

respectively. The unified representation (3.61) of different iterations shows that the choice of the damped parameter \(\tau _n\) in (3.61) is essentially affected for the convergence order. Of course, the parameter \(\tau _n\) in (3.61) is defined by different ways, but in all cases \(\tau _n\rightarrow 1\) as \(n\rightarrow \infty \).

The speed of convergence of sequence \(\{ \tau _n\} \) to unit is different for each iteration methods. In [ 17 ] the conjecture was proposed:

Now we consider the following three-point iterative method:

where \(\bar{t}\) and \(t\) in (D) are some parameters to be determined. We can formulate the following theorem.

we get

Analogously, the Taylor expansion of \(f(x_{n+1})\) at point \(x=z_n\) gives

Using \(f'(z_n)=f'(y_n)+f''(y_n)(z_n-y_n)+\mathcal{O}\big((z_n-y_n)^2\big)\) in the last expansion, we have

Using \(f'(z_n)=f'(y_n)+f''(y_n)(z_n-y_n)+\mathcal{O}\Bigl((z_n-y_n)^2\Bigr)\) in the last expansion, we have

From (3.71) and (3.74) one can eliminate term with \(\displaystyle \tfrac {f’(y_n)}{f’(x_n)}f(x_n)\). As a result, we have

Note that in driving (3.75), we keep in mind that

Further, using Taylor expansion of \(f(x)\in \mathcal{C}^4(\mathfrak {D})\) at points \(y_n\) we obtain

The same technique gives us

For (3.77) and (3.78) one can eliminate the term with \(f'''(y_n)\). As a result, we obtain

Substituting (3.79) into (3.74), we obtain

where

On the other hand, by virtue of (D) we have

If we take (3.67) and (3.76) into account in (3.82), from it we deduce

Then, from (3.72) we get

Now we approximate \(f'(z_n)\) by the method of undetermined coefficient such that

This can be done by means of Taylor expansion of \(f(x)\in \mathcal{C}^4(a,b)\) at point \(z_n\) and we obtain the following linear system of equations

which has a unique solution

where

Substituting (3.84) with coefficients defined by (??) into (3.83), we get

where

The linear combination of (3.80) and (3.86) gives

Clearly, if we choose \(t\) as a root of quadratic equations

then we have

which completes the proof.

It is easy to show that

Then taking this into account and passing to the limit \(t\rightarrow 1\) in Eq. (3.88), we get

It means that Eq. (3.88) or (3.68) has a root tending to unit for any \(\alpha \in [0,1]\).

We recall that, according to Kung-Traub hypothesis, the order of convergence of any multipoint method without memory cannot exceed the bound \(2^{n-1}\) (called optimal order), where \(n\) is the number of function evaluations per iteration. As is known, the efficiency index of iteration defined by formula \(E=d^{\frac1m}\), where \(d\) is the convergence order and \(m\) is the number of function and its derivative evaluations per iteration. Therefore, the optimal efficiency index would be \(2^{\frac{n-1}{n}}\).

According to the Theorem 3.4, the iteration (A) has the convergence order fourth for \(k=2\), requiring only three function evaluations (\(f(x_n)\), \(f(y_n)\) and \(f'(x_n)\)), whereas Theorem 3.7 shows that the iteration (D) has the convergence order eight, requiring four function evaluations \((f(x_n),f(y_n),f(z_n),f'(x_n))\).

Hence, this order of convergence is optimal in the above mentioned sense of the Kung-Traub conjecture. This efficiency index is \(4^{\frac13}\approx 1.587\) and \(8^{\frac14}\approx 1.681\), respectively.

Thus, we obtain the iterations (A) and (D) with the optimal order of convergence 4 and 8, accelerating Newton’s method. Our procedure of accelerations gives a genuine improvement of Newton’s method. One of the advantages of iterations (A) and (D) is that these methods work well for the system of nonlinear equations, whereas the optimal order methods in [ 1 , 2 , 3 , 10 , 12 ] do not extend to the system of equations.

For convenience we present the efficiency index of the proposed above methods (A), (B), (C) and (D) in Table 3.. From Table 3. one can see that the efficiency index of the iterations (A), (B), (C) and (D) is better or much better than that of Newton’s method \(\sqrt2\approx 1.414.\)

4 Finding optimal parameter

Let \(m=1\) in (3.8). Then the root (3.18) can be written as

For \(k=2\), from (??) we obtain

or

By the well known assertion and (3.19) we have

Hence

From this we obtian

The root of (4.93) greater than 1 is

In a similar way, from (3.6) and (??) we obtain

where

Since in all iterations (A), (B), (C) we have

then

Using (3.26) and (4.98) in (4.95) we obtain approximates equation

Eq. (4.99) approximates (4.95) with accuracy \(\mathcal{O}(f_n^4)\) in case of (A) and with accuracy \(\mathcal{O}(f_n^5)\) in case of (B) and (C) since \(t_{\textnormal{opt}}-1=\mathcal{O}(\varepsilon _n^2)\) for (A) and \(t_{\textnormal{opt}}-1=\mathcal{O}(\varepsilon _n^3)\) for (B) and (C). Therefore, Eq. (4.99) may be useful especially for (A).

Above, we obtain formula (4.90) for finding optimal value \(t_{\textnormal{opt}}\) for iteration (A). However, it may be changed for iteration (B) and (C). Since \(x_{n+m}:=z_n\), \(x_n:=y_n\) and \(y_n:=x_{n+1}\) for iteration (B), then according to (??) we have

or

We rewrite (4.100) as

From the last equation, it is clear that if we take into account the following estimate

and

which follows from (3.26), then the equation (??) with \(\theta _n=\frac{f(z_n)}{f(y_n)}\) holds within the accuracy \(\mathcal{O}\big(f^4(x_n)\big)\).

If we wish to include the precise correction to (4.100), one can replace \(1-\displaystyle \tfrac {f’(y_n)}{f’(x_n)}\) by \(2\displaystyle \tfrac {f(y_n)}{f(x_n)}\), then we arrive at

By virtue of (4.102) and (4.103), Eq. (4.104) approximates Eq. (4.100) with accuracy \(\mathcal{O}\big(f^5(x_n)\big)\).

With respect to the iteration (C), Eq. (??) remains true with \(\theta _n=\frac{f(z_n)}{f(y_n)}\).

Note that in most cases the value of the iteration parameter of the damped Newton’s method varies from zero to unit, whereas in our case the value of the optimal parameter may be greater than unit.

5 Numerical experiments

We consider the following four examples [ 18 , 2 , 12 , 8 ] .

All numerical calculations were performed using Maple 16 system. Also, to study the convergence of iterations (3.6), (A), (B) (C) and (D), we compute the computational order of convergence \(d_{x_n}\) using the formulae [ 14 ]

where \(x_{n+1}\), \(x_n\), \(x_{n-1}\) are three consecutive approximations. In numerical examples we also check out the computational order of convergence (COC) of \(\tau _n\) by formula [ 14 ]

which is included in the presented tables (see Tables 5.–5.) and agrees with the conjecture.

Comparisons of the convergence of the iterations (A), (B) and (C) are given in Tables 5.–5.. The third, fourth, fifth and sixth columns show the absolute errors \(|x^*-x_n|\) in the first four iterations. The last four columns display the computational order of convergence \(d_{x_2}\), \(d_{x_3}\), \(\rho _{\tau _2}\) and \(\rho _{\tau _3}\), respectively. The factor \(l\) in the brackets denotes \(10^l\). As expected, the convergence of the proposed methods was remarkably fast. A comparison of the convergence of (D) iteration with other optimal order iterations with eighth order of convergence [ 1 , 12 ] is given in Table 5.. From the Tables we see that the COC perfectly coincides with the theoretical order.

Conclusions

We propose a new acceleration procedure for Newton-type methods. The effect of the acceleration is more perceptible when \(k\) increases. The proposed accelerating procedure allows us to derive high and optimal order iteration methods. Numerical results clear demonstrate the theoretical analysis (speed of convergence, and effect of acceleration). Moreover, our acceleration procedure can also be applied to any iteration and systems of nonlinear equations, to which a forthcoming paper will be devoted.