Return to Article Details Accelerating the convergence of Newton-type iterations

Accelerating the convergence of Newton-type iterations $^{*}$

T. Zhanlav $^{§}$ , O. Chuluunbaatar $^{§, ∙}$ , V. Ulziibayar $^{§, *}$

January 2, 2017.

$^{§}$ Institute of Mathematics, National University of Mongolia, Mongolia, e-mail: tzhanlav@yahoo.com

$^{∙}$ Joint Institute for Nuclear Research, Dubna, 141980 Moscow region, Russia, e-mail: chuka@jinr.ru

$^{*}$ School of Applied Sciences, Mongolian University of Science and Technology, Mongolia, e-mail: ulzii@jinr.ru

In this paper, we present a new accelerating procedure in order to speed up the convergence of Newton-type methods. In particular, we derive iterations with a high and optimal order of convergence. This technique can be applied to any iteration with a low order of convergence. As expected, the convergence of the proposed methods is remarkably fast. The effectiveness of this technique is illustrated by numerical experiments.

MSC. 65H05

Keywords. Newton-type iterations, accelerating procedure, convergence order, efficiency index

1 Introduction

As it is known, the monotone approximations for the solutions of nonlinear equations in $R$ is interesting not only from theoretical, but also from practical view points. In particular, two-sided approximations can be efficiently used as a posteriori estimations for the errors in approximating the desired solution. It means that one can control the error at each iteration step. In the last decade, many authors have developed new monotone iterative methods [ 9 , 19 , 18 ] . The main advantage of the monotone iterations is that it does not require good initial approximations contrary to what occurs in the other iteration methods, such as secant-like methods, Newton’s methods and others [ 4 ] . On the other hand, accelerating the convergence of iterative methods is also of interest both from theoretical and computational view points [ 1 , 2 , 3 , 10 , 12 , 14 , 5 , 11 , 13 , 16 ] . For example, in [ 4 ] was constructed a family of the predictor-corrector iterative method from the simplified secant method and a family of secant-like methods; the authors analyzed the initial conditions on the starting point in order to improve the semilocal convergence of the method. In general, it is desirable to choose the starting point from the convergence domain [ 15 , 16 , 19 ] .

In recent years, many iterative methods for solving nonlinear equations have been developed [ 1 , 2 , 3 , 10 , 12 , 14 , 5 , 11 , 13 , 16 ] to improve the local order of convergence of some methods such as Newton, Ostrowski, Potra-Ptak’s methods and so on. The most efficient methods studied in the literature are the optimal eighth-order methods with four function evaluations per iteration, see [ 1 , 2 , 3 , 10 , 12 ] and references therein. The methods developed in [ 1 , 12 , 7 ] are based on optimal Ostrowski’s or King’s method and use arbitrary real parameters and weight functions. The methods proposed in [ 2 , 3 , 10 ] are obtained by composing an iterative method proposed by Chun and Potra-Ptak’s method with Newton’s method.

In this paper we propose a new accelerating procedure for Newton-type methods. By virtue of this procedure, we obtain a higher order, in particular optimal order methods. The usage of the optimal choice of parameter allows us to improve the convergence speed. This may be also helpful in order to extend the domain of convergence.

The paper is organized as follows. Section 2 describes monotone and two-sided approximations. In Section 3, we show the accelerating procedure and establish a convergence order of the new proposed methods. Section 4 is devoted to finding an optimal parameter in the proposed iterations. Finally, Section 5 presents various numerical examples which confirm the theoretical results, and a numerical comparison with other existing optimal order methods.

2 Statement of the problems

Let $a, b \in R, a < b, f : [a, b] \to R$ and consider the following nonlinear equation

\begin{array}{r} f (x) = 0. \end{array}

Assume that $f (x) \in C^{4} [a, b], f^{'} (x) \neq 0, x \in (a, b)$ and Eq. (2.1) has a unique root $x^{*} \in (a, b)$ . In [ 19 , 18 ] the following iterations were proposed:

\begin{array}{rcl} x_{2 n + 1} = x_{2 n} - τ_{n} \frac{f (x_{2 n})}{f^{'} (x_{2 n})}, \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q 2 a \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q 2 a \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \\ x_{2 n + 2} = x_{2 n + 1} - \frac{f (x_{2 n + 1})}{f^{'} (x_{2 n + 1})}, n = 0, 1, \dots \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q 2 b \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q 2 b \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \end{array}

In [ 19 ] it is shown that the iterations (??) and (??) monotone convergent under conditions

\begin{array}{r} 0 < τ_{n} \leq 1, a_{n} = \frac{M_{2} | f (x_{n}) |}{(f^{'} (x_{n}))^{2}} < \frac{1}{2}, M_{2} = sup_{x \in U_{r} (x^{*})} | f ” (x) |, \end{array}

and under the assumption H : $f^{'} (x) \neq 0$ , $f^{″} (x)$ preserve sign in the small neighborhood $U_{r} (x^{*}) = {x : | f (x) | < r} .$ However the iterations (??) and (??) are not equipped with a suitable choice of parameter $τ_{n}$ . In [ 18 ] it was shown that the iterations (??) and (??) have a two-sided approximation behavior under conditions

\begin{array}{rcl} τ_{n} \in I_{2 n} = [t \frac{1 - \sqrt{1 - 2 a_{2 n}}}{a_{2 n}}, \frac{- 1 + \sqrt{1 + 4 a_{2 n}}}{a_{2 n}}) \subseteq (1, 2), a_{2 n} < \frac{4}{9} . \end{array}

It is also proved that the convergence rate of these iterations is at least 2, and the order of convergence is increased up to 4, when $τ_{n} \to 1$ . From this it is clear that the accelerating of the convergence of iterations (??) and (??) is important, especially at the early stage of iterations.

3 Monotone and two-sided convergence of iterations
and their acceleration

If $τ_{n} \equiv 1$ , then the iterations (??) and (??) become as Newton’s one

\begin{array}{r} x_{n + 1} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}, n = 0, 1 \dots \end{array}

According to [ 19 ] the iteration (3.6) is a monotone convergent under condition (2.4) and assumption H.

Let $θ_{n} = \frac{f (x_{n + 1})}{f (x_{n})}$ . Then the Taylor expansion of $f (x_{n + 1})$ gives

\begin{array}{r} 0 < θ_{n} \leq \frac{a_{n}}{2} < \frac{1}{4} . \end{array}

Now we proceed to accelerate the convergence of monotone iteration (3.6). To this end, we use two known approximations $x_{n}$ , $x_{n + m}$ satisfying either $x_{n} < x_{n + m} < x^{*}$ or $x^{*} < x_{n + m} < x_{n}$ and consider

\begin{array}{r} y_{n} = x_{n} + t (x_{n + m} - x_{n}), t > 1. \end{array}

From (3.8) it is clear that $y_{n}$ belongs to interval connecting $x_{n}$ and $x_{n + m}$ under condition $0 \leq t \leq 1$ . Hence, the extrapolating approach corresponds to the case $t > 1$ . Our aim is to find the optimal value of $t = t_{opt}$ in (3.8) such that the new approximation $y_{n}$ given by (3.8) will be situated more close to $x^{*}$ as compared with $x_{n}$ and $x_{n + m}$ . We use Taylor expansion of the smooth function $f (x) \in C^{k + 1} [a, b]$ :

\begin{array}{rcl} f (y_{n}) = f (x_{n}) + f^{'} (x_{n}) t (x_{n + m} - x_{n}) + \dots \\ + \frac{f^{(k)} (x_{n})}{k!} t^{k} (x_{n + m} - x_{n})^{k} + O ((x_{n + m} - x_{n})^{k + 1}) . \end{array}

Neglecting small term $O ((x_{n + m} - x_{n})^{k + 1})$ in (3.9), we have

f (y_{n}) \approx f (x_{n}) + f^{'} (x_{n}) t (x_{n + m} - x_{n}) + \dots + \frac{f^{(k)} (x_{n})}{k!} t^{k} (x_{n + m} - x_{n})^{k} \equiv P_{k} (t) .

3.10

From (3.10) it is clear that

\begin{array}{r} f (x_{n}) = P_{k} (0) . \end{array}

We also require that

\begin{array}{r} f (x_{n + m}) = P_{k} (1) . \end{array}

From (3.12) we find $\frac{f^{(k)} (x_{n})}{k!} (x_{n + m} - x_{n})^{k}$ and substituting it into (3.10), we get $P_{k} (t)$ . From this we find $t > 1$ such that

\begin{array}{r} f (y_{n}) \approx P_{k} (t) = 0. \end{array}

Geometrically, (3.10) means that the graph (plot) of $f (x)$ in the vicinity of root $x^{*}$ is replaced by curve $P_{k} (t)$ passing through the given points $(x_{n}, f (x_{n}))$ and $(x_{n + m}, f (x_{n + m}))$ . Thus, Eq. (3.10) for $k = 1, 2$ and $k = 3$ gives us

\begin{array}{rcl} P_{0} (t) & = & f (x_{n}) \approx f (y_{n}), y_{n} = x_{n}, \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q n 19 a \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q n 19 a \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \\ P_{1} (t) & = & f (x_{n}) + (f (x_{n + m}) - f (x_{n})) t, \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q 19 a \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q 19 a \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \\ P_{2} (t) & = & f (x_{n}) + f^{'} (x_{n}) (x_{n + m} - x_{n}) t \\ + (f (x_{n + m}) - f (x_{n}) - f^{'} (x_{n}) (x_{n + m} - x_{n})) t^{2}, \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q 19 b \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q 19 b \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \\ P_{3} (t) & = & f (x_{n}) + f^{'} (x_{n}) (x_{n + m} - x_{n}) t + \frac{f ” (x_{n})}{2} (x_{n + m} - x_{n})^{2} t^{2} \\ + (f (x_{n + m}) - f (x_{n}) - f^{'} (x_{n}) (x_{n + m} - x_{n}) \\ - \frac{f ” (x_{n})}{2} (x_{n + m} - x_{n})^{2}) t^{3}, \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q 19 c \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q 19 c \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \end{array}

respectively. Thus, the parameter $t$ in (3.8) is calculated as a root greater than 1 of Eq. (3.13). In particular, for $k = 1$ , we have

\begin{array}{r} t_{opt} = \frac{f (x_{n})}{f (x_{n}) - f (x_{n + m})} > 1. \end{array}

Since $P_{k} (0) P_{k} (1) = f (x_{n}) f (x_{n + m}) > 0$ for $k \geq 1$ , Eq. (3.13) may have at least one root satisfying the condition $t^{*} > 1$ . From (3.7) it follows that

\begin{array}{r} | f (x_{n + 1}) | < \frac{1}{4} | f (x_{n}) | . \end{array}

Therefore, it is desirable to choose $n$ and $m$ such that

\begin{array}{r} | f (x_{n + m}) | < (\frac{1}{4})^{m} | f (x_{n}) | ≪ 0.1 . \end{array}

This inequality is written in term of $P_{k} (t)$ as

\begin{array}{r} | P_{k} (1) | \leq (\frac{1}{4})^{m} | P_{k} (0) | < 0.1 . \end{array}

On the other hand, from (3.10) we see that $P_{k}^{'} (1)$ is not equal to 0 under the assumption H, i.e. $t = 1$ is not a critical point of $P_{k} (t)$ . Thus, $P_{k} (t)$ is decreasing around $t = 1$ . Therefore, there exists $t_{opt} > 1$ such that $P_{k} (t_{opt}) = 0$ .

Lemma 3.1

Assume that $f \in C^{4} [a, b]$ , the assumption H is satisfied and

\begin{array}{r} | x^{*} - x_{n} | = ε_{n} < 1. \end{array}

Then the following holds

\begin{array}{r} t_{opt} - 1 = O (ε_{n}) . \end{array}

Proof â–¼

First of all, let us note that the inequality (3.22) is equivalent to

\begin{array}{r} | f (x_{n}) | = O (ε_{n}), \end{array}

which follows from the expansion

\begin{array}{r} 0 = f (x^{*}) = f (x_{n}) + f^{'} (ξ) (x^{*} - x_{n}) . \end{array}

Of course, $| x^{*} - x_{n + m} | < ε_{n}$ and $| x_{n + m} - x_{n} | < ε_{n}$ under (3.22).

We also use an analogous expansion for $P_{k} (t)$

\begin{array}{r} 0 = P_{k} (t_{opt}) = P_{k} (1) + P_{k}^{'} (η) (t_{opt} - 1), η \in (1, t_{opt}) . \end{array}

Since $P_{k} (t)$ is decreasing around $t = 1$ , then $P_{k}^{'} (η) \neq 0$ .

Hence, from (3.24), (3.25) and (3.20) we conclude that

\begin{array}{r} t_{opt} - 1 = - \frac{f (x_{n + m})}{P_{k}^{'} (η)} \approx O (ε_{n}) . \end{array}

The Lemma is proved.

Proof â–¼

Note that in [ 16 ] the iterations was proposed:

\begin{array}{rcl} x_{2 n + 1} = x_{2 n} - τ_{n} \frac{f (x_{2 n})}{f^{'} (x_{2 n})}, \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q 37 a \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q 37 a \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \\ x_{2 n + 2} = x_{2 n + 1} - \frac{x_{2 n + 1} - x_{2 n}}{f (x_{2 n + 1}) - f (x_{2 n})} f (x_{2 n + 1}), n = 0, 1, \dots, \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q 37 b \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q 37 b \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \end{array}

which has a third order of convergence when $τ_{n} = 1$ or $τ_{n}$ tends to 1. It is easy to show that the iteration (??) coincides fully with our acceleration procedure (3.8) and (3.18) with $m = 1$ and $k = 1$ . Therefore, one can expect a high acceleration when $k = 2, 3$ for Newton’s method.

How to accelerate the convergence rate of iteration (3.6)? The answer of this question gives the following theorem.

Theorem 3.2

Assume $f (x) \in C^{k + 2}$ and the condition (3.22) is satisfied. Then for $y_{n}$ with $t_{opt}$ we have

\begin{array}{r} \frac{| x^{*} - y_{n} |}{| x^{*} - x_{n} |^{k + 2}} \approx O (1), \end{array}

where $O$ is the Landau symbol.

Proof â–¼

Let

\begin{array}{rcl} x^{*} = x_{n} + t^{*} (x_{n + m} - x_{n}), t^{*} \geq 1, \\ y_{n} = x_{n} + t_{opt} (x_{n + m} - x_{n}) . \end{array}

We use Taylor expansions of $f (x) \in C^{k + 2}$

\begin{aligned} 0 = & f (x^{*}) = \\ = & \sum_{p = 0}^{k} \frac{f^{(p)} (x_{n})}{p!} (t^{*})^{p} (x_{n + m} - x_{n})^{p} + \frac{f^{(k + 1)} (η_{n})}{(k + 1)!} (t^{*})^{(k + 1)} (x_{n + m} - x_{n})^{(k + 1)}, \end{aligned}

\begin{aligned} f (x_{n + m}) - \sum_{p = 0}^{k - 1} \frac{f^{(p)} (x_{n})}{p!} (x_{n + m} - x_{n})^{p} = \\ = \frac{f^{(k)} (x_{n})}{k!} (x_{n + m} - x_{n})^{k} + \frac{f^{(k + 1)} (ξ_{n})}{(k + 1)!} (x_{n + m} - x_{n})^{k + 1}, \end{aligned}

and

\begin{aligned} 0 = P_{k} (t_{opt}) = & \sum_{p = 0}^{k - 1} \frac{f^{(p)} (x_{n})}{p!} (t_{opt})^{p} (x_{n + m} - x_{n})^{p} \\ + (f (x_{n + m}) - \sum_{p = 0}^{k - 1} \frac{f^{(p)} (x_{n})}{p!} (x_{n + m} - x_{n})^{p}) (t_{opt})^{k}, \end{aligned}

where $η_{n} \in (x_{n}, x^{*})$ and $ξ_{n} \in (x_{n}, x_{n + m})$ . Using (3.31) in (3.32) and subtracting (3.32) from (3.31) we get

\begin{array}{rcl} [f^{'} (x_{n}) + \frac{f ” (x_{n})}{2} (x_{n + m} - x_{n}) (t^{*} + t_{opt}) + \frac{f ”^{'} (x_{n})}{6} (x_{n + m} - x_{n})^{2} \\ (t^{*^{2}} + t^{*} t_{opt} + t_{opt}^{2}) + \dots + \frac{f^{(k)} (x_{n})}{k!} (t^{*^{k - 1}} + t^{*^{k - 2}} t_{opt} + \dots + t_{opt}^{k - 1}) \\ (x_{n + m} - x_{n})^{k - 1}] (t^{*} - t_{opt}) = \\ = - \frac{(x_{n + m} - x_{n})^{k}}{(k + 1)!} (f^{(k + 1)} (η_{n}) t^{*^{k + 1}} - f^{(k + 1)} (ξ_{n}) t_{opt}^{k}) . \end{array}

Since $f^{'} (x_{n}) \neq 0$ , then from last expression we deduce that

\begin{array}{r} t^{*} - t_{opt} = O (ε_{n}^{k}) . \end{array}

It is possible to derive a more precise estimation than (3.34). Indeed, using (3.34) and $f \in C^{k + 2}$ we evaluate

\begin{aligned} A_{n} & = f^{(k + 1)} (η_{n}) t^{*^{k + 1}} - f^{(k + 1)} (ξ_{n}) t_{opt}^{k} \\ = f^{(k + 1)} (ξ_{n}) (t^{*^{k + 1}} - t_{opt}^{k}) + f^{(k + 2)} (ω_{n}) (η_{n} - ξ_{n}) . \end{aligned}

By definition we have

\begin{array}{r} | η_{n} - ξ_{n} | \leq | x^{*} - x_{n} | = ε_{n} . \end{array}

Using (3.23) and (3.34) we have

\begin{array}{rcl} t^{*^{k + 1}} - t_{opt}^{k} = (t_{opt} + O (ε_{n}^{k}))^{k + 1} - t_{opt}^{k} \\ = t_{opt}^{k} (t_{opt} (1 + O (ε_{n}^{k}))^{k + 1} - 1) = t_{opt}^{k} (t_{opt} + O (ε_{n}^{k}) - 1) = O (ε_{n}) . \end{array}

Then $A_{n} = O (ε_{n})$ and thereby from (3.33) we get

\begin{array}{r} t^{*} - t_{opt} = O (ε_{n}^{k + 1}) . \end{array}

Hence, from (3.30) and (3.31) we find that

\begin{array}{r} x^{*} - y_{n} = O (ε_{n}^{k + 2}) . \end{array}

which proves (3.29).

Proof â–¼

The sequence

{y_{n}}

given by formula (3.8) can be considered as a new a iteration. For it we have the followlng:

Theorem 3.3

Assume $f (x) \in C^{k + 1}$ and the convergence order of iterations (3.6) equal to 2 i.e., the following holds

\begin{array}{r} | x^{*} - x_{n} | \leq M q^{2^{n}} | x^{*} - x_{0} |, 0 < q < 1, M = c o n s t . \end{array}

If the equation (3.13) has at least one root $t_{opt}$ , greater than 1, then the convergence order of new iteration (3.8) is the same as (3.6) and we have

\begin{equation} |x^*-y_n|\leq M_1q_1^{2^n}|x^*-y_0|,\quad 0 3.40

Proof â–¼

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

\begin{aligned} | x^{*} - y_{n} | & \leq C (q^{d^{n}})^{k + 2} | x^{*} - x_{0} |^{k + 2} = C (q^{k + 2})^{d^{n}} | x^{*} - x_{0} |^{k + 2} \\ = C q_{1}^{d^{n}} | x^{*} - x_{0} |^{k + 2} \leq M_{1} q_{1}^{d^{n}} | x^{*} - y_{0} |, q_{1} = q^{k + 2} < q < 1. \end{aligned}

The proof is completed.

Proof â–¼

Theorem 3.3 shows that the convergence order of iteration (3.8) is the same as iteration (3.6).

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} < 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} < 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

\begin{array}{r} f (y_{n}) = \frac{f ” (ξ_{n})}{2} (x_{n + m} - x_{n})^{2} . \end{array}

From this it is clear that

\begin{array}{r} f (y_{n}) > 0 if f ” (x) > 0, \end{array}

and

\begin{array}{r} f (y_{n}) < 0 if f ” (x) < 0. \end{array}

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

\begin{array}{r} f (x_{n}) f (x_{n + 1}) < 0 \end{array}

holds. We consider

\begin{array}{r} y_{n} = x_{n} + t (x_{n + 1} - x_{n}), 0 \leq t \leq 1. \end{array}

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}) < 0$ for $k = 1, 2, 3.$ Hence, Eq. (3.13) has a root $t_{opt} \in (0, 1)$ . Obviously, the new approximation

\begin{array}{r} y_{n} = x_{n} + t_{opt} (x_{n + 1} - x_{n}), 0 \leq t \leq 1, \end{array}

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 > 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

\begin{matrix} (A) & y_{n} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}, x_{n + 1} = x_{n} + t_{opt} (y_{n} - x_{n}), n = 0, 1, \dots \end{matrix}

3.48

The iteration (A) is a damped Newton’s method [ 20 , 17 ] with optimal parameter $τ_{n} = t_{opt}$ . The first step $y_{n}$ is used for finding the optimal parameter.

Theorem 3.4

Assume that the assumptions of Theorem 3.2 are fulfilled. Then the convergence order of iteration (A) with optimal $t_{opt}$ is $d = k + 2, k = 1, 2, 3$ , depending on the smoothness of $f$ .

Proof â–¼

If we compare (A) with (3.6) and (3.8), then

x_{n + m} := y_{n}

and

y_{n} := x_{n + 1}

. Therefore, the expression (3.29) in the Theorem 3.2 has a form

\begin{array}{r} \frac{| x^{*} - x_{n + 1} |}{| x^{*} - x_{n} |^{k + 2}} = O (1) ⟺ | x^{*} - x_{n + 1} | \leq M | x^{*} - x_{n} |^{k + 2}, \end{array}

which completes the proof of the Theorem 3.4.

Proof â–¼

Now let us consider another three-step iteration

\begin{aligned} y_{n} = & x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}, z_{n} = y_{n} - \frac{f (y_{n})}{f^{'} (x_{n})}, \\ (B) & x_{n + 1} = & y_{n} + t (z_{n} - y_{n}), n = 0, 1, \dots \end{aligned}

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

\begin{matrix} (B^{'}) & y_{n} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}, x_{n + 1} = y_{n} - \frac{f (y_{n})}{f^{'} (x_{n})}, n = 0, 1, \dots \end{matrix}

3.51

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

Theorem 3.5

The assumptions of the Theorem 3.2 are fulfilled. Then the convergence order of iteration (B) with optimal $t_{opt}$ equal to $d = 2 k + 3$ .

Proof â–¼

If we compare (B) with (3.8), then

x_{n} := y_{n}

x_{n + m} := z_{n}

y_{n} := x_{n + 1}

. Then form (3.33) and (3.24) we get

\begin{array}{r} t^{*} - t_{opt} = M A_{n} (z_{n} - y_{n})^{k} \approx O (ε_{n}^{2 k + 1}), \end{array}

where

\begin{array}{rcl} x^{*} = y_{n} + t^{*} (z_{n} - y_{n}), x_{n + 1} = y_{n} + t_{opt} (z_{n} - y_{n}) . \end{array}

From this and from (3.52) we obtained

x^{*} - x_{n + 1} = (t^{*} - t_{opt}) (z_{n} - y_{n}) \approx O (ε_{n}^{2 k + 1}) O (ε_{n}^{2}) = O (ε_{n}^{2 k + 3}),

3.54

i.e., we have

\begin{array}{r} | x^{*} - x_{n + 1} | \leq M_{1} | x^{*} - x_{n} |^{2 k + 3}, \end{array}

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

Proof â–¼

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:

\begin{array}{r} z_{n} = x_{n} - \frac{(x_{n})}{f^{'} (x_{n})}, x_{n + 1} = z_{n} - H (x_{n}, y_{n}) \frac{f (z_{n})}{f^{'} (x_{n})}, \end{array}

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

\begin{array}{r} y_{n} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}, x_{n + 1} = y_{n} - t \frac{f (y_{n})}{f^{'} (y_{n})} . \end{array}

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:

\begin{matrix} (C) & y_{n} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}, z_{n} = y_{n} - \frac{f (y_{n})}{f^{'} (y_{n})}, x_{n + 1} = y_{n} + t (z_{n} - y_{n}), n = 0, 1, \dots \end{matrix}

3.55

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

\begin{matrix} (C^{'}) & y_{n} = x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}, x_{n + 1} = y_{n} - \frac{f (y_{n})}{f^{'} (y_{n})}, n = 0, 1, \dots, \end{matrix}

3.56

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.

Theorem 3.6

The assumptions of Theorem 3.2 are fulfilled. Then the convergence order of iteration (C) with optimal $t_{opt}$ equal to $d = 2 (k + 2)$ , $k = 1, 2, 3$ .

Proof â–¼

If we compare (C) with (3.8), then

x_{n} := y_{n}

x_{n + m} := z_{n}

y_{n} := x_{n + 1}

. Therefore, the expression (3.29) reads as

\begin{array}{r} \frac{| x^{*} - x_{n + 1} |}{| x^{*} - y_{n} |^{k + 2}} = O (1) ⟺ | x^{*} - x_{n + 1} | \leq M | x^{*} - y_{n} |^{k + 2} . \end{array}

From (C), we find that

\begin{array}{r} x^{*} - y_{n} = x^{*} - x_{n} + \frac{f (x_{n}) - f (x^{*})}{f^{'} (x_{n})} . \end{array}

Substituting here the expansion of $f (x^{*})$

\begin{array}{r} f (x^{*}) = f (x_{n}) + f^{'} (x_{n}) (x^{*} - x_{n}) + \frac{f ” (ξ_{n})}{2} (x^{*} - x_{n})^{2}, \end{array}

we have

\begin{array}{r} | x^{*} - y_{n} | \leq \frac{| f ” (ξ_{n}) |}{| f^{'} (x_{n}) |} | x^{*} - x_{n} |^{2} . \end{array}

Using the last estimate in (3.52), we obtain

\begin{array}{r} | x^{*} - x_{n + 1} | \leq M_{1} | x^{*} - x_{n} |^{2 (k + 2)}, \end{array}

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

Proof â–¼

Note that the iterations (A), (B) and (C) can be rewritten as a damped Newton’s method [ 20 ]

\begin{aligned} x_{n + 1} = & x_{n} - τ_{n} \frac{f (x_{n})}{f^{'} (x_{n})}, \\ τ_{n} = & t_{opt}, \\ τ_{n} = & 1 + t_{opt} \frac{f (y_{n})}{f (x_{n})}, \\ τ_{n} = & 1 + t_{opt} \frac{f (y_{n})}{f (x_{n})} \frac{f^{'} (x_{n})}{f^{'} (y_{n})}, \end{aligned}

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

The speed of convergence of sequence ${τ_{n}}$ to unit is different for each iteration methods. In [ 17 ] the conjecture was proposed:

\begin{array}{r} | 1 - τ_{n} | \leq M q^{ρ^{n}}, 0 < q < 1. \end{array}

Now we consider the following three-point iterative method:

\begin{aligned} y_{n} = & x_{n} - \frac{f (x_{n})}{f^{'} (x_{n})}, z_{n} = x_{n} + \bar{t} (y_{n} - x_{n}), \\ (D) & x_{n + 1} = & y_{n} + t (z_{n} - y_{n}), n = 0, 1, \dots, \end{aligned}

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

Theorem 3.7

Assume that $f (x) \in C^{4} (a, b)$ and an initial approximation $x_{0}$ is sufficiently close to the zero $x^{*} \in (a, b)$ and the parameter $\bar{t}$ is chosen by as a root of equation

\begin{array}{r} θ_{n} {\bar{t}}^{2} - \bar{t} + 1 = 0, θ_{n} = \frac{f (y_{n})}{f (x_{n})}, \end{array}

and $t$ is a root of equation

\begin{array}{r} Ψ (t, α) = α Ψ_{1} (t) + (1 - α) Ψ_{2} (t) = 0, \end{array}

where

\begin{aligned} Ψ_{1} (t) & = a t^{2} - (a + \frac{f (x_{n})}{f (y_{n})} (f (z_{n}) - f (y_{n}))) t - f (x_{n}), \\ a & = - 2 f (z_{n}) - f (x_{n}) (1 - \bar{t})^{2}, \end{aligned}

and

\begin{aligned} Ψ_{2} (t) & = ((1 - \bar{t}) (2 - \bar{t}) f (x_{n}) - (2 - 3 \bar{t}) f (z_{n})) t \\ + (1 - \bar{t}) (2 f (z_{n}) - (2 - \bar{t}) f (x_{n})) . \end{aligned}

Then the three-point methods (D) is of eight order of convergence.

Proof â–¼

Using

z_{n} - y_{n} = (1 - \bar{t}) \frac{f (x_{n})}{f^{'} (x_{n})}

in Taylor expansion

\begin{array}{r} f (x_{n + 1}) = f (y_{n}) + f^{'} (y_{n}) t (z_{n} - y_{n}) + \frac{f ” (y_{n})}{2} t^{2} (z_{n} - y_{n})^{2} + O ((z_{n} - y_{n})^{3}), \end{array}

we get

\begin{aligned} f (x_{n + 1}) & = f (y_{n}) + t (1 - \bar{t}) \frac{f^{'} (y_{n})}{f^{'} (x_{n})} f (x_{n}) \\ + \frac{f ” (y_{n})}{2} t^{2} (1 - \bar{t})^{2} \frac{f^{2} (x_{n})}{(f^{'} (x_{n}))^{2}} + O (f^{6} (x_{n})) . \end{aligned}

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

\begin{aligned} f (x_{n + 1}) & = f (z_{n}) - (1 - t) (1 - \bar{t}) \frac{f^{'} (z_{n})}{f^{'} (x_{n})} f (x_{n}) \\ + \frac{f ” (z_{n})}{2} (1 - t)^{2} (1 - \bar{t})^{2} \frac{f^{2} (x_{n})}{(f^{'} (x_{n}))^{2}} + O ((1 - t)^{3} f^{6} (x_{n})) . \end{aligned}

Using $f^{'} (z_{n}) = f^{'} (y_{n}) + f^{″} (y_{n}) (z_{n} - y_{n}) + O ((z_{n} - y_{n})^{2})$ in the last expansion, we have

\begin{aligned} f (x_{n + 1}) & = f (z_{n}) - (1 - t) (1 - \bar{t}) \frac{f^{'} (z_{n})}{f^{'} (x_{n})} f (x_{n}) \\ + \frac{f ” (z_{n})}{2} (1 - t)^{2} (1 - \bar{t})^{2} \frac{f^{2} (x_{n})}{(f^{'} (x_{n}))^{2}} + O ((1 - t)^{3} f^{6} (x_{n})) . \end{aligned}

Using $f^{'} (z_{n}) = f^{'} (y_{n}) + f^{″} (y_{n}) (z_{n} - y_{n}) + O ((z_{n} - y_{n})^{2})$ in the last expansion, we have

\begin{aligned} f (x_{n + 1}) = & f (z_{n}) - (1 - t) (1 - \bar{t}) \frac{f^{'} (y_{n})}{f^{'} (x_{n})} f (x_{n}) \\ - \frac{f ” (y_{n}) f^{2} (x_{n})}{2 (f^{'} (x_{n}))^{2}} (1 - t^{2}) (1 - \bar{t})^{2} + O (f^{8} (x_{n})) . \end{aligned}

From (3.71) and (3.74) one can eliminate term with $\frac{f^{'} (y_{n})}{f^{'} (x_{n})} f (x_{n})$ . As a result, we have

\begin{aligned} f (x_{n + 1}) = & t f (z_{n}) + (1 - t) f (y_{n}) - \frac{f ” (y_{n}) f^{2} (x_{n})}{2 (f^{'} (x_{n}))^{2}} (1 - \bar{t})^{2} t (1 - t) + O (f^{8} (x_{n})) . \end{aligned}

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

\begin{array}{r} 1 - t = O (f^{2} (x_{n})) . \end{array}

Further, using Taylor expansion of $f (x) \in C^{4} (D)$ at points $y_{n}$ we obtain

\begin{aligned} f ” (y_{n}) = & \frac{2 (f^{'} (x_{n}))^{2}}{f^{2} (x_{n}) \bar{t} (1 - \bar{t})} [(1 - \bar{t}) f (x_{n}) + \bar{t} f (y_{n}) - f (z_{n})) \\ - \frac{f ”^{'} (y_{n})}{3} \frac{f (x_{n})}{f^{'} (x_{n})} (2 - \bar{t}) + O (f^{2} (x_{n})] . \end{aligned}

The same technique gives us

\begin{aligned} f ” (y_{n}) = & \frac{2 (f (z_{n}) - (1 - \bar{t}) f (x_{n}))}{{\bar{t}}^{2} f^{2} (x_{n})} (f^{'} (x_{n}))^{2} - \frac{f ”^{'} (y_{n})}{3} \frac{f (x_{n})}{f^{'} (x_{n})} (3 - \bar{t}) + O (f^{2} (x_{n})) . \end{aligned}

For (3.77) and (3.78) one can eliminate the term with $f^{‴} (y_{n})$ . As a result, we obtain

\begin{aligned} \frac{f ” (y_{n}) f^{2} (x_{n})}{2 (f^{'} (x_{n}))^{2}} = & \frac{1}{{\bar{t}}^{2} (1 - \bar{t})} ((3 - \bar{t}) \bar{t} (- f (z_{n}) + \bar{t} f (y_{n}) + (1 - \bar{t}) f (x_{n})) \\ - (2 - \bar{t}) (1 - \bar{t}) (f (z_{n}) - (1 - \bar{t}) f (x_{n}))) + O (f^{4} (x_{n})) . \end{aligned}

Substituting (3.79) into (3.74), we obtain

\begin{array}{r} f (x_{n + 1}) = Ψ_{1} (t) + O (f^{8} (x_{n})), \end{array}

where

\begin{aligned} Ψ_{1} (t) & = a t^{2} - (a + \frac{f (x_{n})}{f (y_{n})} (f (z_{n}) - f (y_{n}))) t - f (x_{n}), \\ a & = - 2 f (z_{n}) - f (x_{n}) (1 - \bar{t})^{2} . \end{aligned}

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

\begin{array}{r} x_{n + 1} - z_{n} = - (1 - \bar{t}) (1 - t) \frac{f (x_{n})}{f^{'} (x_{n})} . \end{array}

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

\begin{array}{r} x_{n + 1} - z_{n} = O (f^{4} (x_{n})) . \end{array}

Then, from (3.72) we get

\begin{array}{r} f (x_{n + 1}) = f (z_{n}) + (1 - \bar{t}) (1 - t) \frac{f^{'} (z_{n})}{f^{'} (x_{n})} f (x_{n}) + O (f^{8} (x_{n})) . \end{array}

Now we approximate $f^{'} (z_{n})$ by the method of undetermined coefficient such that

f^{'} (z_{n}) \approx a_{n} f (x_{n}) + b_{n} f (y_{n}) + c_{n} f (z_{n}) + d_{n} f^{'} (x_{n}) + O (f^{4} (x_{n})),

3.84

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

\begin{array}{r} {\begin{cases} a_{n} + b_{n} + c_{n} = 0, \\ a_{n} (x_{n} - z_{n}) + b_{n} (y_{n} - z_{n}) + d_{n} = 1, \\ a_{n} (x_{n} - z_{n})^{2} + b_{n} (y_{n} - z_{n})^{2} + 2 d_{n} (x_{n} - z_{n}) = 0, \\ a_{n} (x_{n} - z_{n})^{3} + b_{n} (y_{n} - z_{n})^{3} + 2 d_{n} (x_{n} - z_{n})^{2} = 0, \end{cases} \end{array}

which has a unique solution

\begin{array}{rcl} a_{n} = \frac{β_{n} (2 β_{n} - 3 ω_{n})}{ω_{n} (β_{n} - ω_{n})^{2}}, b_{n} = \frac{ω_{n}^{2}}{β_{n} (β_{n} - ω_{n})^{2}}, \\ c_{n} = - \frac{2 β_{n} + ω_{n}}{β_{n} ω_{n}}, d_{n} = - \frac{β_{n}}{β_{n} - ω_{n}}, \end{array}

where

\begin{array}{r} ω_{n} = x_{n} - z_{n} = \bar{t} \frac{f (x_{n})}{f^{'} (x_{n})}, β_{n} = y_{n} - z_{n} = (1 - \bar{t}) \frac{f (x_{n})}{f^{'} (x_{n})} . \end{array}

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

\begin{array}{r} f (x_{n + 1}) = Ψ_{2} (t) + O (f^{8} (x_{n})), \end{array}

where

\begin{aligned} Ψ_{2} (t) & = ((1 - \bar{t}) (2 - \bar{t}) f (x_{n}) - (2 - 3 \bar{t}) f (z_{n})) t \\ + (1 - \bar{t}) (2 f (z_{n}) - (2 - \bar{t}) f (x_{n})) . \end{aligned}

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

\begin{array}{r} f (x_{n + 1}) = α Ψ_{1} (t) + (1 - α) Ψ_{2} (t) + O (f^{8} (x_{n})) . \end{array}

Clearly, if we choose $t$ as a root of quadratic equations

\begin{array}{r} Ψ (t, α) = α Ψ_{1} (t) + (1 - α) Ψ_{2} (t) = 0, \end{array}

then we have

\begin{array}{r} f (x_{n + 1}) = O (f^{8} (x_{n})) \end{array}

which completes the proof.

Proof â–¼

Remark 3.8

Since $t$ is a root of Eq. (3.88), it depends on the parameter $α$ , i.e. $t = t (α)$ . Therefore, (D) are one parameter family of iterations.â–¡

It is easy to show that

\begin{array}{r} Ψ_{2} (\hat{t}) = 0, \hat{t} \to 1, Ψ_{1} (\overset{˘}{t}) = 0, \overset{˘}{t} \to 1. \end{array}

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

\begin{array}{r} Ψ (t, α) \overset{t \to 1}{\to} α Ψ_{1} (1) + (1 - α) Ψ_{2} (1) \approx 0. \end{array}

It means that Eq. (3.88) or (3.68) has a root tending to unit for any $α \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^{\frac{1}{m}}$ , 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}))$ .

Methods	$k$	$d$	$E$
	1	3	$3^{\frac{1}{3}} \approx 1.442249$
(A)	2	4	$4^{\frac{1}{3}} \approx 1.587401$
	3	5	$5^{\frac{1}{4}} \approx 1.495348$
	1	5	$5^{\frac{1}{4}} \approx 1.495348$
(B)	2	7	$7^{\frac{1}{5}} \approx 1.475773$
	3	9	$9^{\frac{1}{5}} \approx 1.551845$
	1	6	$6^{\frac{1}{5}} \approx 1.430969$
(C)	2	8	$8^{\frac{1}{5}} \approx 1.515716$
	3	10	$10^{\frac{1}{6}} \approx 1.467799$
(D)	-	8	$8^{\frac{1}{4}} \approx 1.681792$

Table 3. The efficiency index of the methods (A), (B), (C) and (D).

Hence, this order of convergence is optimal in the above mentioned sense of the Kung-Traub conjecture. This efficiency index is $4^{\frac{1}{3}} \approx 1.587$ and $8^{\frac{1}{4}} \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 $\sqrt{2} \approx 1.414 .$

4 Finding optimal parameter

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

\begin{array}{r} t_{opt}^{(1)} = \frac{1}{1 - θ_{n}}, θ_{n} = \frac{f (y_{n})}{f (x_{n})} . \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q n 8^{'} \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q n 8^{'} \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \end{array}

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

\begin{array}{r} P_{2} (t) \equiv f (y_{n}) t^{2} - f (x_{n}) t + f (x_{n}) = 0, \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q n 9 a \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q n 9 a \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \end{array}

\begin{array}{r} P_{2} (t) \equiv θ_{n} t^{2} - t + 1 = 0. \@ b s p h a c k \if @ f i l e s w \edef \@ t e m p a \write \@ a u x o u t \string \newlabel e q n 9 b \thesubequation \thepage \write \@ a u x o u t \string \newlabel e q n 9 b \thesubequation \thepage \if @ n o b r e a k \fi \fi \@ e s p h a c k \end{array}

By the well known assertion and (3.19) we have

\begin{array}{r} t_{1} + t_{2} = \frac{f (x_{n})}{f (y_{n})} > 1, t_{1} t_{2} = \frac{f (x_{n})}{f (y_{n})} . \end{array}

Hence

\begin{array}{r} t_{1} + t_{2} = t_{1} t_{2} . \end{array}

From this we obtian

\begin{array}{r} t_{1}^{2} - \frac{f (x_{n})}{f (y_{n})} t_{1} + \frac{f (x_{n})}{f (y_{n})} = 0. \end{array}

The root of (4.93) greater than 1 is

\begin{array}{r} t_{opt}^{(2)} = \frac{1 - \sqrt{1 - 4 θ_{n}}}{2 θ_{n}} = \frac{2}{1 + \sqrt{1 - 4 θ_{n}}} . \end{array}

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

\begin{array}{r} P_{3} (t) = (θ_{n} - ω_{n}) t^{3} + ω_{n} t^{2} - t + 1 = 0, \end{array}

where

\begin{array}{r} ω_{n} = \frac{f ” (x_{n}) f (x_{n})}{2 (f^{'} (x_{n}))^{2}} . \end{array}

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

\begin{array}{r} f (y_{n}) = \frac{f ” (x_{n})}{2} \frac{f_{n}^{2}}{(f_{n}^{'})^{2}} + O (f^{3} (x_{n})), \end{array}

then

\begin{array}{r} ω_{n} = \frac{f (y_{n})}{f (x_{n})} + O (f^{2} (x_{n})) . \end{array}

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

\begin{array}{r} (\frac{f (z_{n})}{f (y_{n})} - \frac{f (y_{n})}{f (x_{n})}) t^{3} + \frac{f (y_{n})}{f (x_{n})} t^{2} - t + 1 = 0. \end{array}

Eq. (4.99) approximates (4.95) with accuracy $O (f_{n}^{4})$ in case of (A) and with accuracy $O (f_{n}^{5})$ in case of (B) and (C) since $t_{opt} - 1 = O (ε_{n}^{2})$ for (A) and $t_{opt} - 1 = O (ε_{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_{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

\begin{array}{r} P_{2} (t) \equiv f (y_{n}) + f^{'} (y_{n}) (z_{n} - y_{n}) t + (f (z_{n}) - f (y_{n}) - f^{'} (y_{n}) (z_{n} - y_{n})) t^{2} = 0, \end{array}

\begin{array}{r} P_{2} (t) \equiv (\frac{f (z_{n})}{f (y_{n})} - 1 + \frac{f^{'} (y_{n})}{f^{'} (x_{n})}) t^{2} - \frac{f^{'} (y_{n})}{f^{'} (x_{n})} t + 1 = 0. \end{array}

We rewrite (4.100) as

\begin{array}{r} P_{2} (t) = \frac{f (z_{n})}{f (y_{n})} t^{2} - t + 1 + (1 - \frac{f^{'} (y_{n})}{f^{'} (x_{n})}) t (1 - t) = 0. \end{array}

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

\begin{array}{r} 1 - \frac{f^{'} (y_{n})}{f^{'} (x_{n})} = 2 \frac{f (y_{n})}{f (x_{n})} + O (f^{2} (x_{n})) = O (f (x_{n})) \end{array}

and

\begin{array}{r} 1 - t = O (f (x_{n + m})) = O (f (z_{n})) = O (f^{3} (x_{n})), \end{array}

which follows from (3.26), then the equation (??) with $θ_{n} = \frac{f (z_{n})}{f (y_{n})}$ holds within the accuracy $O (f^{4} (x_{n}))$ .

If we wish to include the precise correction to (4.100), one can replace $1 - \frac{f^{'} (y_{n})}{f^{'} (x_{n})}$ by $2 \frac{f (y_{n})}{f (x_{n})}$ , then we arrive at

\begin{array}{r} (θ_{n} - 2 \frac{f (y_{n})}{f (x_{n})}) t^{2} + (2 \frac{f (y_{n})}{f (x_{n})} - 1) t + 1 = 0. \end{array}

By virtue of (4.102) and (4.103), Eq. (4.104) approximates Eq. (4.100) with accuracy $O (f^{5} (x_{n}))$ .

With respect to the iteration (C), Eq. (??) remains true with $θ_{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 ] .

Example 5.1

Let $f (x) = \exp (x) - 4 x^{2} = 0$ . This equation has three roots. It is easy to show that

\begin{array}{rcl} (a) f^{'} (x) > 0, f ” (x) > 0 at x \in [4, \frac{9}{2}], and x^{*} \in (4, \frac{9}{2}), \\ (b) f^{'} (x) > 0, f ” (x) < 0 at x \in [- \frac{1}{2}, 0], and x^{*} \in (- \frac{1}{2}, 0) . \end{array}

We considered only first and third roots.

Method	$k$	$\| x^{*} - x_{0} \|$	$\| x^{*} - x_{1} \|$	$\| x^{*} - x_{2} \|$	$\| x^{*} - x_{3} \|$	$d_{x_{2}}$	$d_{x_{3}}$	$ρ_{τ_{2}}$	$ρ_{τ_{3}}$
	1	1.93(-01)	3.87(-03)	4.00(-08)	4.45(-023)	2.93	3.00	2.93	3.00
(A)	2	1.93(-01)	3.48(-04)	3.80(-15)	5.40(-059)	3.99	4.00	3.99	4.00
	3	1.93(-01)	1.68(-05)	8.74(-26)	3.31(-127)	5.00	5.00	5.00	5.00
	1	1.93(-01)	1.43(-04)	5.70(-20)	5.78(-097)	4.92	5.00	4.92	5.00
(B)	2	1.93(-01)	1.46(-06)	4.15(-42)	6.35(-291)	6.94	7.00	6.94	7.00
	3	1.93(-01)	9.66(-09)	4.56(-74)	5.31(-662)	8.94	9.00	8.94	9.00
	1	1.93(-01)	1.24(-05)	1.47(-30)	4.13(-180)	5.95	6.00	5.95	6.00
(C)	2	1.93(-01)	1.26(-07)	8.02(-57)	2.14(-450)	7.95	8.00	7.95	8.00
	3	1.93(-01)	8.38(-10)	4.41(-93)	7.23(-926)	9.96	10.00	9.96	10.00

Table 5. Example 1a.

x^{*} = 4.306584 \dots

Method	$k$	$\| x^{*} - x_{0} \|$	$\| x^{*} - x_{1} \|$	$\| x^{*} - x_{2} \|$	$\| x^{*} - x_{3} \|$	$d_{x_{2}}$	$d_{x_{3}}$	$ρ_{τ_{2}}$	$ρ_{τ_{3}}$
	1	9.22(-02)	5.38(-04)	1.36(-010)	2.18(-0030)	2.95	3.00	2.95	3.00
(A)	2	9.22(-02)	1.56(-06)	1.56(-025)	1.55(-0101)	3.98	4.00	3.98	4.00
	3	9.22(-02)	3.56(-08)	3.77(-040)	5.04(-0200)	4.99	5.00	4.99	5.00
	1	9.22(-02)	6.10(-06)	1.29(-026)	5.39(-0130)	4.95	5.00	4.95	5.00
(B)	2	9.22(-02)	1.26(-09)	2.17(-064)	9.62(-0448)	6.96	7.00	6.96	7.00
	3	9.22(-02)	2.14(-12)	9.57(-108)	6.74(-0966)	8.96	9.00	8.96	9.00
	1	9.22(-02)	2.70(-07)	2.76(-040)	3.13(-0238)	5.96	6.00	5.96	6.00
(C)	2	9.22(-02)	5.57(-11)	1.87(-084)	2.96(-0672)	7.97	8.00	7.97	8.00
	3	9.22(-02)	9.48(-14)	2.74(-133)	1.12(-1328)	9.97	10.00	9.97	10.00

Table 5. Example 1b.

x^{*} = - 0.4077767 \dots

Example 5.2

$f (x) = x^{2} - 2 \cos (x) = 0$ . This equation has two roots. It is also easy to show that

\begin{array}{rcl} f^{'} (x) > 0, f ” (x) > 0 at x \in [\frac{π}{6}, \frac{π}{2}], and x^{*} \in (\frac{π}{6}, \frac{π}{2}), \end{array}

We considered only first root, because $f (x)$ is an even function with respect to $x$ .

Method	$k$	$\| x^{*} - x_{0} \|$	$\| x^{*} - x_{1} \|$	$\| x^{*} - x_{2} \|$	$\| x^{*} - x_{3} \|$	$d_{x_{2}}$	$d_{x_{3}}$	$ρ_{τ_{2}}$	$ρ_{τ_{3}}$
	1	5.49(-01)	1.11(-02)	2.18(-07)	1.71(-021)	2.77	3.00	2.77	3.00
(A)	2	5.49(-01)	1.73(-03)	2.73(-13)	1.71(-052)	3.92	4.00	3.92	4.00
	3	5.49(-01)	5.18(-05)	1.76(-24)	7.93(-122)	4.84	5.00	4.84	5.00
	1	5.49(-01)	4.63(-04)	1.16(-18)	1.12(-091)	4.75	5.00	4.75	5.00
(B)	2	5.49(-01)	6.44(-06)	1.90(-39)	3.62(-274)	6.80	7.00	6.80	7.00
	3	5.49(-01)	6.17(-08)	3.33(-69)	1.29(-620)	8.81	9.00	8.81	9.00
	1	5.49(-01)	4.84(-05)	1.41(-28)	8.72(-170)	5.80	6.00	5.80	6.00
(C)	2	5.49(-01)	6.65(-07)	3.21(-53)	9.36(-424)	7.83	8.00	7.83	8.00
	3	5.49(-01)	6.42(-09)	6.22(-87)	4.48(-867)	9.84	10.00	9.84	10.00

Table 5. Example 2.

x^{*} = 1.021689 \dots

Example 5.3

Let $f (x) = (x - 2) (x^{10} + x + 1) \exp (- x - 1) = 0$ . We chose the initial approximation $x_{0} = 2.1$ for $x^{*} = 2$ .

Method	$\| x^{*} - x_{1} \|$	$\| x^{*} - x_{2} \|$	$\| x^{*} - x_{3} \|$	$d_{x_{3}}$
$h (t) = 1 + \frac{4 t}{2 - 5 t}, β = 3$ in [ 1 , (14) ]	1.83(-5)	3.15(-34)	2.45(-264)	7.99986
$h (t) = \frac{1}{1 - 2 t - t^{2} + t^{3}}, β = 3$ in [ 1 , (14) ]	6.02(-6)	7.91(-38)	6.99(-293)	8.00007
$ψ (t) = \frac{5 - 2 t + t^{2}}{5 - 12 t}$ in [ 12 , (12) ]	6.12(-5)	1.11(-29)	1.34(-224)	7.99947
$ψ (t) = \frac{1}{1 - 2 t - t^{2}}$ in [ 12 , (12) ]	6.01(-5)	9.29(-30)	3.02(-228 )	8.00050
(D), $α = 0$	2.18(-5)	1.12(-34)	5.40(-269)	7.99999
(D), $α = 0.5$	2.14(-5)	2.25(-34)	3.39(-266)	8.00003
(D), $α = 1$	2.89(-5)	2.45(-33)	6.63(-258)	7.99999

Table 5. Example 3.

x^{*} = 2

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 ]

\begin{array}{r} d_{x_{n}} = \frac{\ln (| x_{n + 1} - x^{*} | / | x_{n} - x^{*} |)}{\ln (| x_{n} - x^{*} | / | x_{n - 1} - x^{*} |)}, \end{array}

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 $τ_{n}$ by formula [ 14 ]

\begin{array}{r} ρ_{τ_{n}} = \frac{\ln | (τ_{n + 1} - 1) / (τ_{n} - 1) |}{\ln | (τ_{n} - 1) / (τ_{n - 1} - 1) |}, \end{array}

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}}$ , $ρ_{τ_{2}}$ and $ρ_{τ_{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.

Acknowledgement

The authors would like to thank the anonymous referee for the valuable comments and suggestions which substantially improved the quality of this article. The work was supported partially by the Foundation of Science and Technology of Mongolia under grant SST $_$ 007/2015. O. Ch. acknowledges support within the Hulubei-Meshcheryakov programme JINR-Romania.