A Family of Newton Type Iterative Methods for Solving Nonlinear Equations

Solving nonlinear equations by iterative methods have been of great interest to numerical analysts. The most famous one-point iterative method is probably Newton’s Equation [1]: $x_{k+1}=x_k-f\left(x_k\right)/f^{\prime }\left(x_k\right),$ which converges quadratically. However, the condition $f^{\prime }\left(x\right)\ne 0$ in a neighborhood of the required root is severe indeed for convergence of Newton method, which restricts its applications in practical. For resolving this problem, Wu in [2] proposed the following one-point iterative method where $\lambda \in R,0<\left|\lambda \right|<+\infty$ and λ is chosen such that the corresponding function values $\lambda f\left(x_k\right)$ and $f^{\prime }\left(x_k\right)$ have the same signs. This method converges quadratically under the condition $\lambda f\left(x_k\right)+f^{\prime }\left(x_k\right)\ne 0,$ while $f^{\prime }\left(x_k\right)=0$ in some points is permitted. Wang and Zhang in [3] obtained the error equation of the Equation (1) as follows where $e_k=x_k-a,c_k=(1/k!)f^{\left(k\right)}\left(a\right)/f^{\prime }\left(a\right),k=2,3,\cdots$ and a is the root of the nonlinear equation $f\left(x\right)=0.$

The convergence order and computational efficiency of the one-point iterative methods are lower than multipoint iterative methods. Multipoint iterative methods can overcome theoretical limits of one-point methods concerning the convergence order and computational efficiency. In recent years, many multipoint iterative methods have been proposed for solving nonlinear equations, see [4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]. Wang and Liu in [4] developed the following eighth-order iterative method without memory by Hermite interpolation methods where $N(x_k,y_k,z_k)=f[z_k,y_k]+2f[z_k,x_k]-2f[y_k,x_k]+f[y_k,x_k,x_k](y_k-z_k).$ Using the same strategy, Kou in [5] presented a family of eighth-order iterative method without memory. The Equation (3) is a special case of the Kou’s method. Petković in [6] claimed a general class of optimal n-point methods without memory by Hermite interpolation methods, which have the order of convergence $2^n$ and require evaluations of n functions and one first-order derivative. The Equation (3) is a special case of the Petković’s n-point Method for $n=3.$ But, the Petković’s n-point method gives no specific iterative scheme and error relation for $n\ge 4.$ In this paper, we construct a class of n-point iterative methods with and without memory by Hermite interpolation methods and give the specific iterative scheme and error relation for all $n\ge 2.$

This paper is organized as follows. In Section 2, based on Wu’s Equation [2] and Petković’s n-point Equation [6], we derive a family of n-point iterative methods without memory for solving nonlinear equations. We prove that the order of convergence of the n-point methods without memory is $2^n$ requiring the evaluations of n functions and one first-order derivative in per full iteration. Kung and Traub in [7] conjectured that a multipoint iteration without memory based on n functional evaluations could achieve an optimal convergence of order $2^{n-1}$. The new methods without memory agree with the conjecture. Further accelerations of convergence speed are attained in Section 3. A family of n-point iterative methods with memory is obtained by using a self-accelerating parameter in per full iteration. This self-accelerating parameter is calculated using information available from the current and previous iterations. Numerical examples are given in Section 4 to confirm theoretical results.

Based on Wu’s Equation [2] and Petković’s n-point methods [6], we derive a general optimal $2^n$th order family and write it in the following form: where $N(y_{k,n-1},y_{k,n-2},\cdots ,y_{k,1},y_{k,0})=f[y_{k,n-1},y_{k,n-2}]+\cdots +f[y_{k,n-1},y_{k,n-2},\cdots ,y_{k,1},y_{k,0},y_{k,0}](y_{k,n-1}-y_{k,n-2})\cdots (y_{k,n-1}-y_{k,0}),y_{k,0}=x_k,\lambda \in R$ is a constant and k being the iteration index. The entries $y_{k,0},\cdots y_{k,n}$ are approximations with the associated error $e_{k,j}=y_{k,j}-a(j=0,1,\cdots ,n).$

Using the Taylor series and symbolic computation in the programming package Mathematica, we can find the order of convergence and the asymptotic error constant (AEC) of the n-point methods Equation (4) for $n=1,n=2$ and $n=3$, respectively. For simplicity, we sometimes omit the iteration index n and write e instead of $e_k$. The approximation $x_{k+1}$ to the root a will be denoted by $\widehat{x}$. Regarding Equation (4), let us define $x=y_{k,0},y=y_{k,1},z=y_{k,2},e=x-a,d=y-a,p=z-a,e1=\widehat{x}-a.$

The following abbreviations are used in the program.

Program (written in Mathematica)

fx=fla*(e+c2*e^2+c3*e^3+c4*e^4+c5*e^5+c6*e^6+c7*e^7+c8*e^8);

dfx=D[fx,e];

t=Series[fx/(L*fx+dfx),{e,0,8}];

d=Series[e-t,{e,0,8}]//Simplify

fy=Series[fla*(d+c2*d^2+c3*d^3+c4*d^4),{e,0,8}];

fxy=Series[(fy-fx)/(d-e),{e,0,8}];

z=Series[d-fy/(2*fxy-dfx),{e,0,8}]//Simplify

fz=Series[fla*(z+c2*z^2),{e,0,8}];

fyz=Series[(fy-fz)/(d-z),{e,0,8}];

fxz=Series[(fx-fz)/(e-z),{e,0,8}];

fxxy=Series[(dfx-fxy)/(e-d),{e,0,8}];

fzxx=Series[(dfx-fxz)/(e-z),{e,0,8}];

fzxxy=Series[(fzxx-fxxy)/(z-d),{e,0,8}];

fzxy=Series[(fxz-fyz)/(e-d),{e,0,8}];

e1=Series[z-fz/(fyz+fzxy*(z-d)+fzxxy*(z-e)*(z-d)),{e,0,8}]//Simplify

We obtain the asymptotic error constants of n-point methods Equation (4) with $n=1,2,3$. Altogether, we can state the following theorem.

Theorem 1. Let I be an open interval and $a\in I$ a simple zero point of a sufficiently differentiable function $f:I\to R$. Then the new method defined by Equation (4) $(n=2)$is fourth order, and satisfies the error equation the Equation (4) ($n=3$) is eighth-order and satisfies the error equation where $e_k=x_k-a,d_0=1,d_1=1,d_2=c_2^2+c_2\lambda -c_3 \mathrm{and} d_3=d_2(c_2{d}_2+c_4{d}_1{d}_0).$

The order of the convergence of the Equation (4) is analyzed in the following theorem.

Theorem 2. Let I be an open interval and $a\in I$ a simple zero point of a sufficiently differentiable function $f:I\to R$. Then the n-point family Equation (4) converges with at least $2^n$th order and satisfies the error relation where $e_k=e_{k,0}=y_{k,0}-a$ and $d_n=d_{n-1}(c_2{d}_{n-1}+{(-1)}^{n-1}{c}_{n+1}{d}_{n-2}\cdots d_1{d}_0),$$n\ge 3$

Proof. We prove the theorem by induction. For $n=3,$ the theorem is valid by Theorem 1. Let us assume that Equation (10) is true for the intermediate error relations, then the intermediate error relations are of the form where $e_{k,j}=y_{k,j}-a,d_j=d_{j-1}(c_2{d}_{j-1}+{(-1)}^{j-1}{c}_{j+1}{d}_{j-2}\cdots d_1{d}_0),j=3,\cdots n-1.$ Using Equation (4) and Equation (11) and noting that $e_{k,0}{e}_{k,0}{e}_{k,1}{e}_{k,2}\cdots e_{k,n-1}=O(e_k^{1+1+2+4+\cdots +2^{n-2}})=O(e_k^{2^{n-1}})$, we have

Hence, by induction, we conclude that the error relations can be written in the following form

In this section we will improve the convergence order of the family Equation (4). We observe from Equation (13) that the order of convergence of the family Equation (4) is $2^n$ when $\lambda \ne -c_2.$ With the choice $\lambda =-c_2=-f^{″}\left(a\right)/(2f^{\prime }\left(a\right))$, it can be proved that the order of the family Equation (4) would exceed $2^n$. However, the exact values of $f^{\prime }\left(a\right)$ and $f^{″}\left(a\right)$ are not available in practice and such acceleration of convergence can not be realized. But we could approximate the parameter λ by ${\lambda }_k$. The parameter ${\lambda }_k$ can be computed by using information available from the current and previous iterations and satisfies ${lim}_{k\to \infty }{\lambda }_k=-c_2=-f^{″}\left(a\right)/\left(2f^{\prime }\left(a\right)\right),$ such that the $2^n$th order asymptotic convergence constant to be zero in Equation (13). We consider the following three methods for ${\lambda }_k$: where $H_2\left(x\right)=f\left(y_{k,0}\right)+f[y_{k,0},y_{k,0}](x-y_{k,0})+f[y_{k,0},y_{k,0},y_{k-1,n-1}]{(x-y_{k,0})}^2,$ and $H_2^{″}\left(y_{k,0}\right)=$$2f[y_{k,0},y_{k,0},y_{k-1,n-1}].$ where $H_3\left(x\right)=H_2\left(x\right)+f[y_{k,0},y_{k,0},y_{k-1,n-1},y_{k-1,n-2}]{(x-y_{k,0})}^2(x-y_{k-1,n-1}),$ and $H_3^{″}\left(y_{k,0}\right)=$$H_2^{\prime \prime }\left(y_{k,0}\right)+2f[y_{k,0},y_{k,0},y_{k-1,n-1},y_{k-1,n-2}](y_{k,0}-y_{k-1,n-1}).$ where $H_4\left(x\right)=H_3\left(x\right)+f[y_{k,0},y_{k,0},y_{k-1,n-1},y_{k-1,n-2},y_{k-1,n-3}]{(x-y_{k,0})}^2(x-y_{k-1,n-1})(x-y_{k-1,n-2})$ and $H_4^{″}\left(y_{k,0}\right)=H_3^{″}\left(y_{k,0}\right)+2f[y_{k,0},y_{k,0},y_{k-1,n-1},y_{k-1,n-2},y_{k-1,n-3}](y_{k,0}-y_{k-1,n-1})(y_{k,0}-y_{k-1,n-2}).$

The parameter ${\lambda }_k$ is recursively calculated as the iteration proceeds using Equation (14)–Equation (16) in Equation (4). Substituting ${\lambda }_k$ instead of λ in Equation (4), we can obtain the following iterative method with memory where $N(y_{k,n-1},y_{k,n-2},\cdots ,y_{k,1},y_{k,0})=f[y_{k,n-1},y_{k,n-2}]+\cdots +f[y_{k,n-1},y_{k,n-2},\cdots ,y_{k,1},y_{k,0},y_{k,0}]\times (y_{k,n-1}-y_{k,n-2})\cdots (y_{k,n-1}-y_{k,0}),$ and the parameter${\lambda }_k$ is calculated by using one of the Equations (14)– (16) and depends on the data available from the current and the previous iterations.

Lemma 1. Let $H_m$ be the Hermite interpolating polynomial of the degree m that interpolates a function f at m distinct interpolation nodes $y_{k,0},y_{k-1,n-1},\cdots y_{k-1,n-m+1}$ contained in an interval Iand the derivative $f^{(m+1)}$ is continuous in I and the Hermite interpolating polynomial $H_m\left(x\right)$ satisfied the condition $H_m\left(y_{k,0}\right)=f\left(y_{k,0}\right),H_m^{\prime }\left(y_{k,0}\right)=f^{\prime }\left(y_{k,0}\right),H_m\left(y_{k-1,n-j}\right)=f\left(y_{k-1,n-j}\right)(j=1,\cdots m-1)$. Define the errors $e_{k-1,n-j}=y_{k-1,n-j}-a(i=1\cdots m-1)$ and assume that

• all nodes $y_{k,0},y_{k-1,n-1,}\cdots y_{k-1,n-m+1}$ are sufficiently close to the zero a;
• the condition $e_k=O(e_{k-1,n-1}\cdots e_{k-1,n-m+1})$ holds.

Then and

Proof. The error of the Hermite interpolation can be expressed as follows

Differentiating Equation (20) at the point $x=y_{k,0}$, we obtain

Taylor’s series of derivatives of fat the point $y_{k,0}\in I$ and $\xi \in I$ about the zero a of fgive where $e_{\xi }=\xi -a.$

Substituting Equation (24) and Equation (25) into Equation (22), we have and

The concept of the R-order of convergence [1] and the following assertion (see [8]) will be applied to estimate the convergence order of the iterative method with memory Equation (17). Now we can state the following convergence theorem for iterative method with memory Equation (17).

Theorem 3. Let the varying parameter ${\lambda }_k$ in the iterative Equation (17) be calculated by Equation (14). If an initial approximation $x_0$ is sufficiently close to a simple zero a of $f\left(x\right)$, then the R-order of convergence of the n-point Equation (17) with memory is at least $2^n+2^{n-3}$ for $n\ge 3$ and at least $(5+\sqrt{17})/2\approx 4.5616$ for $n=2.$

Proof. First, let us consider the case $n\ge 3$ and assume that the iterative sequences $\left\{y_{k,n}\right\}$ and $\left\{y_{k,n-1}\right\}$ have the R-order $r \mathrm{and} q$, respectively, we have where $D_{k,j}(j\in R)$ tends to the asymptotic error constant $D_j$ when $k\to \infty .$

From Equation (13), we obtain the following error relations

Using the Lemma 1 for $m=2$, we obtain

Substituting Equation (32) into Equation (30) and Equation (31) instead of λ, we have

By comparing exponents of $e_{k-1}$ appearing in two pairs of relations Equation (29)–Equation (33) and Equation (28)–Equation (34), we get the following system of equations

The solution of the system Equation (35) is given by $r=2^n+2^{n-3}$ and $q=2^{n-1}+2^{n-4}$. Therefore, the R-order of the methods with memory Equation (17) is at least $r=2^n+2^{n-3}$ for $n\ge 3$. For example, the R-order of the three-point family Equation (17) is at least 9, the four-point family has the R-order at least 18, assuming that ${\lambda }_k$ is calculated by Equation (14).

The case $n=2$ differs from the previous analysis; Hermit’s interpolating polynomial is constructed at the nodes $y_{k,0},y_{k-1,1}$. Substituting Equation (32) into Equation (2) and Equation (8) instead of λ, we have

By comparing exponents of $e_{k-1}$ appearing in two pairs of relations Equation (29)–Equation (36) and Equation (28)–Equation (37), we get the following system of equations

Positive solution of the system Equation (38) is given by $r=(5+\sqrt{17})/2$ and $q=(1+\sqrt{17})/2$. Therefore, the R-order of the methods with memory Equation (17) with Equation (14) is at least $(5+\sqrt{17})/2\approx 4.5616$ for $n=2.$

Theorem 4. Let the varying parameter ${\lambda }_k$ in the iterative Equation (17) be calculated by Equation (15). If an initial approximation $x_0$ is sufficiently close to a simple zero a of $f\left(x\right)$, then the R-order of convergence of the n-point methods Equation (17) with memory is at least $2^n+2^{n-3}+2^{n-4}$ for $n\ge 4$, at least $5+\sqrt{21}\approx 9.5826$ for $n=3$ and at least $(5+\sqrt{21})/2\approx 4.7913$ for $n=2.$

Proof. The proof is similar to the Theorem 3.

Theorem 5. Let the varying parameter ${\lambda }_k$ in the iterative Equation (17) be calculated by Equation (16). If an initial approximation $x_0$ is sufficiently close to a simple zero a of $f\left(x\right)$, then the R-order of convergence of the n-point Equation (17) with memory is at least $2^n+2^{n-3}+2^{n-4}+2^{n-5}$ for $n\ge 5$, at least $10+\sqrt{92}\approx 19.5917$ for $n=4$ and at least $5+\sqrt{23}\approx 9.7958$ for $n=3.$

Proof. The proof is similar to the Theorem 3.

Now, the new family Equation (4) without memory and the corresponding family Equation (17) with memory are employed to solve some nonlinear equations and compared with several known iterative methods. All algorithms are implemented using Symbolic Math Toolbox of MATLAB 7.0. For demonstration, we have selected three methods displayed below.

King’s methods without memory ( KM4, see [9] ): where $\beta \in R$.

Bi-Wu-Ren method without memory ( BRM8, see [10] ): where $h\left(t\right)$is a real-valued function satisfying the conditions$h\left(0\right)=1,h^{\prime }\left(0\right)=2,h^{″}\left(0\right)=10,\left|h^{‴}\left(0\right)\right|<\infty$ and $\gamma \in R.$

Petković-Ilić-Džunić method with memory ( PD, see [12] ) where $z_n=x_n-{\gamma }_{n}f\left(x_n\right).$ The parameter${\gamma }_n$ can be calculated by the following three formulas:

The absolute errors$\left|x_k-a\right|$in the first four iterations are given in Table 1, Table 2, Table 3 and Table 4, where a is the exact root computed with 2400 significant digits. The computational order of convergence ρ is defined by [19]:

The iterative processes of the Equations (4) and (17) are given in Figure 1, where Equation (4) (n=1) is one-point method. The parameters of the Equations (4) and (17) are $\lambda ={\lambda }_0=1.0$. The initial value is $x_0=-1.3$. The stopping criterium is $\left|f\left(x\right)\right|<{10}^{-150}$. We will call $f\left(x\right)$ the nonlinear residual or residual. The Figure 1 is a semilog plot of residual history, the norm of the nonlinear residual against the iteration number.

Following test functions are used: