In this paper, we study certain iterative methods for solving nonlinear equations

where $f:[a,b]\rightarrow\mathbb{R},a,b\in\mathbb{R},a<b$. The Aitken and Steffensen-type methods consider two more equations, equivalent to the above one:

where $g_{i}:[a,b]\rightarrow[a,b]$.
We admit that
(A) Eq. (1) has a solution $\left.x^{*}\in\right]a,b[$.

The most known methods of Steffensen, Aitken, or Aitken-Steffensen type are obtained from inverse interpolation polynomials of degree 1 , having the knots determined with the aid of different functions $g_{1},g_{2}$ (see, e.g., $[1-5,13]$ ).

More general methods of this type have been obtained by using inverse interpolation polynomials of degree 2 [11]; they have led to iterative methods of $q$-order at least 3 , and with efficiency indexes usually higher than for the case of
interpolation polynomials of degree 1 [15]. Obviously, the convergence order and the efficiency index of the resulted methods depend on the functions $g_{i}$.

Here, we study a method based on the Hermite inverse interpolation polynomial of degree 2, with the nodes generated with the aid of the Newton iteration function, $x-f(x)/f^{\prime}(x)$, in (2).

We need the following assumption on $f$ :
(B) $f$ is three times derivable on $[a,b]$ and $f^{\prime}(x)\neq 0,\forall x\in[a,b]$.

This assumption implies that function $f$ is monotone and continuous on $[a,b]$, therefore $\exists f^{-1}:J\rightarrow[a,b],J:=f([a,b])$, and by (B) we have

In order to approximate the solution $x^{*}$ we shall consider the Hermite inverse interpolation polynomial of degree 2.
Let $a_{1},a_{2}\in[a,b]$, denote $b_{1}=f\left(a_{1}\right),b_{2}=f\left(a_{2}\right)$ so that

and

The polynomial of degree 2 which satisfies

is the Hermite polynomial, given by

having the remainder

where $[u,v;h],[u,v,w;h]$ denote the first, respectively the second order divided difference of the function $h$ at the nodes $u,v$ resp. $u,v,w$.

Setting $y=0$ in (3) we are led to another approximation for $x^{*}$ :

having the error

Formula (4) will be used in an iterative fashion, by setting $a_{3}=P(0)$, and so on. However, instead of (4) and (5) we need formulas which do not need the evaluation of the inverse function.

It is known that the divided differences satisfy the following relations (see, e.g., [12]):

which lead us to a formula for $a_{3}$ based only on the values of $f$ and its derivatives:

Taking into account (B) and the Mean Value Theorem on the divided differences, the error in (5) becomes

Since (see, e.g., [12])

and $f$ is one-to-one, it follows that $\exists\xi\in]a,b[$ with $\eta=f(\xi)$ such that

tiie Ellul iii (// is vvilletil as

As we have mentioned, the functions $g_{1}$ and $g_{2}$ in (2) are taken, with the aid of the Newton iteration function, as:

so that, setting $a_{1}=z_{n}$ and $a_{2}=y_{n}$ in (6), we are led to the following iterations:

We refer to this as the Aitken-Newton method.
We shall show in Section 2 that under some very simple conditions, this method converges locally with $q$-order 8. Since, at each iteration step we need to compute 5 function evaluations (i.e., $f\left(x_{n}\right),f^{\prime}\left(x_{n}\right),f\left(y_{n}\right),f^{\prime}\left(y_{n}\right)$ and $f\left(z_{n}\right)$ ), the efficiency index is $\sqrt[5]{8}\approx 1.51$, which is not optimal in the sense of Kung and Traub.

There are a lot of optimal methods (see, e.g., $[7,8,10,16]$ ) but, as we shall see in the numerical examples section, the optimal efficiency index is not a paramount by itself, since there exist situations when some optimal methods may have very small attraction sets for certain solutions.

In Section 3 we show that if there exists a set $D\subseteq[a,b]$ containing a solution $x^{*}$ such that on this set, $f$ has monotone and convex properties, $E_{f}$ is positive, and the Fourier condition is verified, then for any initial approximation in $D$, the method converges monotonically to $x^{*}$ :

It is important to note that the convergence holds as large as the domain $D$ is, and this domain may extend to the left or to the right of the solution much more than ensured by (even sharp) estimates for the radius of an attraction ball.

The above inequalities show another advantage of this method, since the stopping criterions (such as $\left|x_{n-1}-x_{n}\right|<tol_{1}$ or $\left.\left|f\left(x_{n}\right)\right|<tol_{2}\right)$ may be considered for the extended (inner) iterates $x_{n},y_{n},z_{n},x_{n+1}$ (resp. for the values of $f$ at them), avoiding divisions by zeros.

These aspects, as well as other ones, are treated in Section 4, regarding numerical examples.

The following result holds.
Theorem 1. Under assumptions (A) and (B), the Aitken-Newton method (10) converges locally, with $q$-convergence order 8 :

where

for certain $\left.\xi_{n},\theta_{n},\delta_{n},\mu_{n},\nu_{n}\in\right]a,b[$. The asymptotic constant is given by

Proof. We assume in the beginning that the elements of the sequences $\left(x_{n}\right)_{n\geq 0},\left(y_{n}\right)_{n\geq 0}$ and $\left(z_{n}\right)_{n\geq 0}$ remain in $[a,b]$.
Assumption ( $B$ ) and the first relation in (4) imply the existence of $\left.\delta_{n}\in\right]a,b[$ such that

Analogously, the second relation in (4) attracts

with $\left.\theta_{n}\in\right]a,b[$.

Considering (9), with $a_{3}=x_{n+1},b_{1}=f\left(z_{n}\right)$ and $b_{2}=f\left(y_{n}\right)$, we get

The values $f\left(z_{n}\right)$ și $f\left(y_{n}\right)$ are easily expressed by

with $\left.\mu_{n},v_{n}\in\right]a,b[$.
Relations (12)-(14) imply (11).
The induction holds if $x_{0}$ is chosen sufficiently close to $x^{*}$.

We consider the following supplementary conditions on $f$
(C) Function $E_{f}$ given by (8) is strictly positive on $[a,b]$ :

(D) The initial approximation $x_{0}\in[a,b]$ satisfies the Fourier condition:

Remark 1. As we shall see in the numerical examples, condition (C) may sometimes be easily verified (e.g, when $f^{\prime}$ and $f^{\prime\prime}$ have different signs, etc.).

We obtain the following results:
Theorem 2. If $f$ and $x_{0}$ satisfy assumptions (A)-(D) and, moreover:
$\left(i_{1}\right)f^{\prime}(x)>0,\forall x\in[a,b];$
$\left(ii_{1}\right)f^{\prime\prime}(x)>0,\forall x\in[a,b]$;
then the iterates of the Aitken-Newton method (10) satisfy:
$\left(j_{1}\right)x^{*}<x_{n+1}<z_{n}<y_{n}<x_{n},\quad n=0,1,\ldots$
( $\left.jj_{1}\right)\lim x_{n}=\lim y_{n}=\lim z_{n}=x^{*}$.
Proof. We proceed by induction.
Let $x_{n}\in[a,b]$ satisfy the Fourier condition. By (ii) we have that $f\left(x_{n}\right)>0$, therefore $x_{n}>x^{*}$, by ( $i_{1}$ ). Relations (12) and (13) attract $y_{n}>x^{*}$ and $z_{n}>x^{*}$. The first relation in (10), together with $f\left(x_{n}\right)>0$ imply that $y_{n}<x_{n}$. Analogously, $z_{n}<y_{n}$. The third relation in (10) and the hypotheses imply that $z_{n}>x_{n+1}>x^{*}$. Statement ( $j_{1}$ ) is proved.

It follows that sequences $\left(x_{n}\right),\left(y_{n}\right),\left(z_{n}\right)$ are convergent to the same limit $\ell$, and (10) shows that $f(\ell)=0$, i.e., $\ell=x^{*}$.
Theorem 3. If $f$ and $x_{0}$ satisfy ( $A$ )- ( $D$ ) and moreover,
$\left(i_{2}\right)f^{\prime}(x)<0,\forall x\in[a,b];$
(ii ) $f^{\prime\prime}(x)<0,\forall x\in[a,b]$,
then the same conclusions as those in Theorem 2 hold.
The proof is easily obtained applying Theorem 2 to the function $h=-f$.
The following two theorems have similar proofs.
Theorem 4. If $f$ and $x_{0}$ satisfy conditions (A)-(D) and moreover,
$\left(i_{3}\right)f^{\prime}(x)<0,\forall x\in[a,b];$
$\left(ii_{3}\right)f^{\prime\prime}(x)>0,\forall x\in[a,b]$;
then the iterates of the Aitken-Newton method (10) satisfy
$\left(j_{3}\right)x_{n}<y_{n}<z_{n}<x_{n+1}<x^{*},n=0,1,\ldots$,
(jjo) $\lim x_{n}=\lim y_{n}=\lim z_{n}=x^{*}$.
Theorem 5. If $f$ and $x_{0}$ satisfy conditions (A)-(D) and moreover,

$\left(i_{4}\right)f^{\prime}(x)>0,\forall x\in[a,b];$
$\left(ii_{4}\right)f^{\prime\prime}(x)<0,\forall x\in[a,b]$,
then the iterates of (10) satisfy the conclusion of Theorem 4.
Remark 2. As we shall see in the numerical examples, even if the hypotheses of the above monotone convergence results are not fulfilled, the iterates may converge (due to the local convergence Theorem 1) and sometimes even monotonically (Theorems 2-5 offer sufficient but not also necessary conditions).

In this section we shall consider some examples for which we run programs in Matlab, in double precision floating point arithmetic (this is the setting most encountered in practice). As we shall see, the high convergence orders and the monotone properties are properly reflected in this setting, and we do not need higher precision.

There are a lot of optimal iterative methods having the convergence order 8. We shall present only a few of them, for which we have found a better convergence of the Aitken-Newton iterates in certain situations.

We begin with two examples, which show the rapid convergence of the Aitken-Newton iterates (10).
Example 1. Let

We have: $f(0)=-1,f(1)=e^{2}+\sin 1-2>0,f^{\prime}(x)=2e^{2x}+\cos x>0,x\in[0,1],f^{\prime\prime}(x)=4e^{2x}-\sin x>0,f^{\prime\prime\prime}(x)=8e^{2x}-\cos x$ and

Taking $x_{0}=1$, Theorem 2 applies and we obtain decreasing sequences $x_{n},y_{n},z_{n}$, as can be seen in Table 1 .
Example 2. Consider

We have $f\left(\frac{1}{2}\right)=\sqrt{e}-1>0,f(1)=e-4<0,f^{\prime}(x)=e^{x}-8x<0,f^{\prime\prime}(x)=e^{x}-8<0,f^{\prime\prime\prime}(x)=e^{x}$ and $E_{f}(x)=2e^{2x}-48e^{x}+8xe^{x}+192>0,x\in\left[\frac{1}{2},1\right]$.

Taking $x_{0}=1$, Theorem 2 applies again and we obtain the results presented in Table 2.
Next, we present two examples and we compare the studied method to other methods. In order to obtain smaller tables, we used the format short command in Matlab. It is worth mentioning that such choice may lead to results that appear integers, while they are not (e.g., the value of $y_{4}$ in Table 6 is shown to be 2 , while $f\left(y_{4}\right)$ should be 0 ); the explanation resides in the rounding made in the conversion process.

Example 3. Consider the following equation (see, e.g., [6])

The largest interval to study the monotone convergence of our method by Theorems $2-5$ is $[a,b]:=\left[x^{*},1.54\ldots\right]$, since $f^{\prime\prime}$ vanishes at $b$ (being positive on $[a,b]$ ). The Fourier condition (D) holds on $[a,b]$ (and does not hold for $x<a$ ), $E_{f}(x)>0$ on $[a,b]$, while the derivatives $f^{\prime},f^{\prime\prime}$ are positive on this interval. The conclusions of Theorem 2 apply.

The Aitken-Newton method leads to the following results, presented in Table 3.

The convergence may be not very fast for initial approximations away from the solution.
It is worth noting that the method converges for $-0.3\leq x_{0}<x_{1}^{*}$ too (local convergence near $x^{*}=0$ assured by Theorem 1), despite the Fourier condition does not hold. For $x_{0}=-0.3$ one obtains $x_{1}\approx-0.25<0$, then $y_{1}\approx 1.7>0$ and the rest of the iterates remain positive, converging monotonically to $x_{1}^{*}$. For $x_{0}=-0.4$, the method converges to another solution of the equation, $x_{2}^{*}=-0.603\ldots$

The optimal method introduced by Cordero et al. [8] has a smaller convergence domain for $x_{0}>x_{1}^{*}$, since the iterates converge for $x_{0}=1.48\left(x_{4}=1.3741e-32\right)$, while for $x_{0}=1.49$ the iterates jump over $x_{1}^{*}$ and converge to $x_{2}^{*}$ as can be seen in Table 4. By checking all the initial approximations between 0 and 1.48 with step 0.001 , we found out that the convergence domain is even smaller, since taking 1.442 as initial approximation does not lead to convergence.

The Kou-Wang method (formula (25) in [9]) converges for $x_{0}=1.48\left(x_{4}=0\right)$ and diverges for $x_{0}=1.49$, as can be seen in Table 5.

Example 4. Consider the following equation (see, e.g., [14])

The largest interval to study the monotone convergence of our method by Theorems $2-5$ is $[a,b]:=\left[x^{*},7.9\ldots\right]$, since $f^{\prime\prime}$ vanishes at $b$ (being positive on $[a,b]$ ).

The Fourier condition (D) holds on $[a,b]$ (and does not hold for $x<a$ ), $E_{f}(x)>0$ on $[a,b]$, while both the derivatives $f^{\prime}$, $f^{\prime\prime}$ are positive on this interval. The conclusions of Theorem 2 apply.

It is interesting to note that in [14, Remark 6] Petković observed that the methods studied there have a small convergence domain to the left of the solution: the choice of $x_{0}=1.8$ caused a bad convergence behavior of those iterates. We believe that this behavior may be explained by the fact that the derivative of $f$ vanishes at $x=1.78\ldots$

The Aitken-Newton method leads to the results presented in Table 6. The iterates converge even for $x_{0}>7.9$ (and to the left of the solution as well, but for $x_{0}$ higher than 1.72). Of course the convergence may be not very fast when the initial approximations are away from the solution.

The optimal method introduced by Cordero et al. [8] converges to $x^{*}$ for $x_{0}=6.46$ and it does not for $x_{0}=6.47$, as shown in Table 7.

The optimal method introduced by Liu and Wang (formula (18) in [10]) converges to $x^{*}=2$ for $x_{0}=2.359$ (it needs 5 iterates) but for $x_{0}=2.36$ it converges to another solution, $x_{1}^{*}=1512.626\ldots$. The results are presented in Table 8.

Among the optimal methods in [14] (the methods with convergence orders higher than 8 were corrected in a subsequent paper), the modified Ostrowski and Maheshwari methods behave very well for this example (we have studied the convergence only to the right of the solution). The modified Euler-like method has a small domain of convergence (in $\mathbb{R}$ ), since it converges to $x^{*}$ for $x_{0}=2.15$, while for $x_{0}=2.16$ it generates square roots of negative numbers. Matlab has the feature of implicitly dealing with complex numbers, and the iterates finally converge (in $\mathbb{C}$ ) to the solution (see Table 9).

The Aitken-Newton method studied in this paper present, under certain circumstances, some advantages over the optimal methods; the obtained sufficient conditions for guaranteed convergence may theoretically lead to larger convergence domains (especially sided convergence intervals) than from estimates of attraction balls, while a few examples shown that the attraction domain of the method is larger than for some optimal methods.

[1] S. Amat, J. Blanda, S. Busquier, A Steffensen type method with modified functions, Riv. Mat. Univ. Parma 7 (2007) 125-133.
[2] S. Amat, S. Busquier, J.A. Ezquerro, M.A. Hernández-Verón, A Steffensen type method of two steps in banach spaces with applications, J. Comput. Appl. Math. 291 (2016) 317-331.
[3] I.K. Argyros, A new convergence theorem for the Steffensen method in Banach space and applications, Rev. Anal. Numér. Théor. Approx. 29 (1) (2000) 119-127.
[4] I.K. Argyros, S. Hilout, An improved local convergence analysis for Newton-Steffensen-type method, J. Appl. Math. Comp. 32 (1) (2010) 111-118.
[5] E. Cătinaş, On some Steffensen-type iterative method for a class of nonlinear equations, Rev. Anal. Numér. Théor. Approx. 24 (1-2) (1995) 37-43.
[6] C. Chun, Certain improvements of Chebyshev-Halley methods with accelerated fourth-order convergence, Appl. Math. Comput. 189 (1) (2007) 597-601.
[7] A. Cordero, J.L. Hueso, E. Martinez, J.R. Torregrosa, Generating optimal derivative free iterative methods for nonlinear equations by using polynomial interpolations, Math. Comput. Model. 57 (7-8) (2013) 1950-1956.
[8] A. Cordero, J.R. Torregrosa, M.P. Vassileva, A family of modified Ostrowski’s methods with optimal eighth order of convergence, Appl. Math. Lett. 24 (12) (2011) 2082-2086.
[9] J. Kou, X. Wang, Some improvements of Ostrowski’s method, Appl. Math. Lett. 23 (1) (2010) 92-96.
[10] L. Liu, X. Wang, Eighth-order methods with high efficiency index for solving nonlinear equations, Appl. Math. Comput. 215 (9) (2010) 3449-3454.
[11] I. Păvăloiu, Approximation of the root of equations by Aitken-Steffensen-type monotonic sequences, Calcolo 32 (1-2) (1995) 69-82.
[12] I. Păvăloiu, E. Cătinaş, Bilateral approximation for some Aitken-Steffensen-Hermite type method of order three, Appl. Math. Comput. 217 (12) (2011) 5838-5846.
[13] I. Păvăloiu, E. Cătinaş, On an Aitken-Newton type method, Numer. Algorithm 62 (2) (2013) 253-260.
[14] M.S. Petković, On a general class of multipoint root-finding methods of high computational efficiency, SIAM J. Numer. Anal. 47 (6) (2010) 4402-4414.
[15] J.R. Sharma, A composite third order Newton-Steffensen method for solving nonlinear equations, Appl. Math. Comput. 169 (1) (2005) 242-246.
[16] F. Soleymani, S.K. Vanani, Optimal Steffensen-type method with eighth order of convergence, Comput. Math. Appl. 62 (12) (2011) 4619-4626.