# Novel Computational Iterative Methods with Optimal Order for Nonlinear Equations

Authors: F. Soleymani
Journal: Advances in Numerical Analysis
 (2011)

---

## Abstract

This paper contributes a very general class of two-point iterative methods without memory for solving nonlinear equations. The class of methods is developed using weight function approach. Per iteration, each method of the class includes two evaluations of the function and one of its first-order derivative. The analytical study of the main theorem is presented in detail to show the fourth order of convergence. Furthermore, it is discussed that many of the existing fourth-order methods without memory are members from this developed class. Finally, numerical examples are taken into account to manifest the accuracy of the derived methods.


---

## Body

## 1. Prerequisites

One of the important and challenging problems in numerical analysis is to find the solution of nonlinear equations. In recent years, several numerical methods for finding roots of nonlinear equations have been developed by using several different techniques; see, for example, [1, 2]. We herein consider the nonlinear equations of the general form(1.1)f(x)=0,
where f:D⊆ℝ→ℝ is a real valued function on an open neighborhood D and α∈D a simple root of (1.1). Many relationships in nature are inherently nonlinear, in which their effects are not in direct proportion to their cause. Accordingly, solving nonlinear scalar equations occurs frequently in scientific works. Many robust and efficient methods for solving such equations are brought forward by many authors; see [3–5] and the references therein. Note that Newton’s method for nonlinear equations is an important and fundamental one.In providing better iterations with better efficiency and order of convergence, a technique as follows is mostly used. The composition of two iterative methods of ordersp and q, respectively, results in a method of order pq, [6]. Usually, new evaluations of the derivative or the nonlinear function are needed in order to increase the order of convergence. On the other hand, one well-known technique to bring generality is to use weight function correctly in which the order does not die down, but the error equation becomes general. In fact, this approach will be used in this paper.Definition 1.1.
The efficiency of a method is measured by the concept ofefficiency index, which is given by
(1.2)EI=p1/β,
where p is the convergence order of the method and β is the whole number of evaluations per one computing process. Meanwhile, we should remember that by Kung-Traub conjecture [7] as comes next, an iterative multipoint scheme without memory for solving nonlinear equations has the optimal efficiency index 2(β-1)/β and optimal rate of convergence 2β-1.
Higher-order methods are widely referenced in literature; see for example, [8, 9] and the references therein. It can be concluded that they are useful in applications, for example, numerical solution of quadratic equations and nonlinear integral equations are needed in the study of dynamical models of chemical reactors or in radiative transfer. Moreover, many of these numerical applications use high precision in their computations; the results of these numerical experiments show that the high-order methods associated with a multiprecision arithmetic floating point are very useful, because they yield a clear reduction in the number of iterations. This simply shows the importance of multipoint methods in solving nonlinear scalar equations.
The two-step family of Geum and Kim, which was given in [10] recently, is one of the most significant two-point optimal fourth-order methods, which includes many of the existing fourth-order methods as its special elements:
(1.3)yn=xn-f(xn)f′(xn),xn+1=yn-(f(xn))2+βf(xn)f(yn)+γ(f(yn))2(f(xn))2+(β-2)f(xn)f(yn)+δ(f(yn))2f(yn)f′(xn).
It satisfies the error equationen+1=(-c2c3+c23(1+2β-γ+δ))en4+O(en5), with β,γ,δ∈ℝ, and ck=(1/k!)f(k)(α)/f′(α),k≥2. Note that (1.3) is in fact the first two steps of the three-step scheme given in [10]. Clearly, choosing γ=δ=0 will end in the well-known King’s optimal fourth-order family [11]:
(1.4)yn=xn-f(xn)f′(xn),xn+1=yn-f(xn)+βf(yn)f(xn)+(β-2)f(yn)f(yn)f′(xn),
which reads the error equation en+1=(-c2c3+c23(1+2β))en4+O(en5) and also contains the Ostrowski’s fourth-order method as its special element for β=0.
Motivated and inspired by the recent activities in this direction, in this paper, we will construct a very general class of new iterative methods free from second- or higher-orders derivatives in computing process based on (1.3) and grounded on the use of weight function in the second step of our proposed class.


## 2. Main Contribution

This section contains our novel contributed general class. According to the conjecture of Kung-Traub for constructing optimal without memory iterations, we must use only three evaluations per full cycle to reach the convergence order four. Therefore, we consider the following very general two-step two-point without memory iteration:(2.1)yn=xn-f(xn)f′(xn),xn+1=yn-(f(xn))2+βf(xn)f(yn)+γ(f(yn))2(f(xn))2+(β-2)f(xn)f(yn)+δ(f(yn))2f(yn)f′(xn){G(t)H(τ)K(φ)},
where G(t), H(τ), and K(φ) are three real-valued weight functions with t=f(y)/f(x), τ=f(y)/f′(x), and φ=f(x)/f′(x), without the index n, that should be chosen such that the order of convergence reaches the optimal level four. This is done in Theorem 2.1.Theorem 2.1.
Letα∈D be a simple zero of a sufficiently differentiable function  f:D⊂ℝ→ℝ for an open interval  D, which contains  x0 as an initial approximation of  α. If   G(t), H(τ), and K(φ) satisfy the conditions:
(2.2)G(0)=1,G′(0)=0,|G′′(0)|<∞,H(0)=1,|H′(0)|<∞,K(0)=1,K′(0)=0,|K′′(0)|<∞,
then the class of iterative without memory methods defined by (2.1) is of optimal order four.Proof.
By definingen=xn-α as the error of the iterative scheme in the nth iterate, applying Taylor’s expansion and taking into account f(α)=0, we have
(2.3)f(xn)=f′(α)[en+c2en2+c3en3+c4en4+O(en5)],
where ck=(1/k!)(f(k)(α)/f′(α)),k≥2. Furthermore, we have
(2.4)f′(xn)=f′(α)[1+2c2en+3c3en2+4c4en3+O(en4)].
Dividing (2.3) by (2.4) gives us
(2.5)f(xn)f′(xn)=en-c2en2+2(c22-c3)en3+(7c2c3-4c23-3c4)en4+O(en5).
By substituting (2.5) in the first step of (2.1) for yn, we obtain
(2.6)yn=α+c2en2+(-2c22+2c3)en3+(4c23-7c2c3+3c4)en4+O(en5),
and similarly f(yn)=c1f′(α)en2+2(-c22+c3)f′(α)en3+(5c23-7c2c3+3c4)f′(α)en4+O(en5). Again, by Taylor’s series expanding around the simple root and using the attained formulas, we have
(2.7)(f(xn))2+βf(xn)f(yn)+γ(f(yn))2(f(xn))2+(β-2)f(xn)f(yn)+δ(f(yn))2=1+2c2en1+(4c3-c22(2+2β-γ+δ))en2+(6c4-4c2c3(1+2β-γ+δ)+c23(-4γ+2δ+β(4+2β-γ+δ)))en3+O(en4).
Also, by Taylor expanding, we attain yn-f(yn)/f′(xn)=α+2c22en3+(-9c23+7c2c3)en4+O(en5).At this time, by taking into consideration (2.6), (2.7), and the conditions (2.2) for the weight functions into the last step of (2.1), we attain the follow-up error equation for the whole iteration (2.1) per computing process:
(2.8)en+1=12c2(-2c3-2c2H′(0)+c22(2+4β-2γ+2δ-G′′(0))-K′′(0))en4+O(en5).
This shows that the iterative class (2.1)-(2.2) will arrive at the optimal local order of convergence four. This concludes the proof.In standpoint of computational efficiency, each derived member from our class includes three evaluations per full cycle, that is, one evaluation of the first-order derivative and two evaluations of the function. Therefore, the resulted methods are optimal and consistent with the optimality conjecture of Kung-Traub for multipoint without memory iterations. The class possesses the optimal efficiency index 1.587, which is much better than that of Newton’s scheme efficiency. Furthermore, the error equation (2.8) completely reveals the generality of our class. Choosing any desired values for the three parameters and also the three real-valued weight functions, based on (2.2), will result in new methods. In what follows, we briefly provide some of the well-known methods in the literature as special members from our class of iterations.Case 1.
ChoosingG(t)=1+t3, H(τ)=1+τ2, and K(φ)=1+φ3 will result in the family of Geum-Kim (1.3).Case 2.
ChoosingG(t)=1+t3, H(τ)=1+τ2, K(φ)=1+φ3, and γ=δ=0 will result in the family of King (1.4)Case 3.
ChoosingG(t)=1+t3, H(τ)=1+τ2, K(φ)=1+φ3, γ=δ=0, and β=-1/2 will result in the method of Khattri et al. in [12] as comes next with the same error equation:
(2.9)yn=xn-f(xn)f′(xn),xn+1=xn-1f′(xn){1+f(yn)f(xn)+2(f(yn)f(xn))2+5(f(yn)f(xn))3+14(f(yn)f(xn))4}.
Some typical forms of the weight function, which make the order of our general class optimal according to (2.2), are listed in Table 1.Table 1
Typical forms ofG(t), H(τ), and K(φ) based on (2.2) where t=f(y)/f(x), τ=f(y)/f′(x), φ=f(x)/f′(x), and θ∈ℝ-{0}.
FormsWeight function forG(t)Weight function forH(τ)Weight function forK(φ)11+t21+τ+θτ21+φ221+θt3(1+τ)/(1-τ)1+θφ3According to Table1, we can produce any desire method of optimal order four by using only three functional evaluations per full cycle. Hence, we can have as contributed examples from our class:(2.10)yn=xn-f(xn)f′(xn),xn+1=yn-f(xn)2f(xn)2-2f(xn)f(yn)f(yn)f′(xn)(1+(f(yn)f(xn))2)×(1+(f(yn)f′(xn))2)(1+(f(xn)f′(xn))2),
with en+1=-c2(1+c3)en4+O(en5), and(2.11)yn=xn-f(xn)f′(xn),xn+1=yn-f(xn)2f(xn)2-2f(xn)f(yn)f(yn)f′(xn)(1+(f(yn)f(xn))2)×(1+f(yn)f′(xn))(1+(f(xn)f′(xn))3),
where en+1=-c2(c2+c3)en4+O(en5) is its error relation; or the following efficient method:(2.12)yn=xn-f(xn)f′(xn),xn+1=yn-f(xn)2f(xn)2-2f(xn)f(yn)f(yn)f′(xn)(1+(f(yn)f(xn))2)×(1+f(yn)f′(xn))(1-(f(xn)f′(xn))2),
with the follow-up error equation en+1=-c2(c2+c3-1)en4+O(en5).As positively pointed out by the reviewer, the novel fourth-order methods can be applied in providing higher-order convergent methods. That is to say, in order to fulfill the optimality conjecture of Kung-Traub (1974), optimal eighth- and sixteenth-order derivative-involved methods can only be built grounded on the optimal quartically methods. Now and according to the contributed class in this paper, very general eighth- and sixteenth-order optimal iterations without memory can be constructed by using (2.1)-(2.2) in the first two steps of a three- or four-step cycle.The error relation (2.8) relies fully on the first, second, third derivatives of a given nonlinear function, as well as β,γ,δ,H′(0),G′′(0),K′′(0). Thus, in order to save the space and also giving some of the other optimal fourth-order methods according to (2.1) and (2.2), we list the interesting ones in Table 2.Table 2
Interesting choices ofβ,γ,δ,H′(0),G′′(0),K′′(0) in (2.8), which provide efficient optimal root solvers.
MethodβγδG′′(0)H′(0)K′′(0)Error equation1111604en+1=-c2(2+c3)en4+O(en5)2100014en+1=c2(-2+c2(-1+3c2)-c3)en4+O(en5)3000010en+1=c2((-1+c2)c2-c3)en4+O(en5)400000-1/10en+1=c2(1/20+c22-c3)en4+O(en5)51/101111-1/10en+1=(1/20)c2(1+2c2(-10+7c2)-20c3)en4+O(en5)6-1/2000-1/20en+1=(1/2)c2(c2-2c3)en4+O(en5)70000-1/22en+1=(1/2)c2(c2+2c22-2(1+c3))en4+O(en5)8111112en+1=(1/2)c2(c2(-2+5c2)-2(1+c3))en4+O(en5)9111111en+1=(1/2)c2(-1+c2(-2+5c2)-2c3)en4+O(en5)10000111en+1=(1/2)c2(-1+(-2+c2)c2-2c3)en4+O(en5)


## 3. Computational Aspects

Here, to demonstrate the performance of the new fourth-order methods, we take a lot of nonlinear equations as follows:(i)
f1=(sinx)2+x,α=0,(ii)
f2=(1+x3)cos(πx/2)+1-x2-(2(92+73)/27), α=1/3,(iii)
f3=(sinx)2-x2+1,  α≈1.404491648215341226035086817786,(iv)
f4=e-x+sin(x)-1,  α≈2.076831274533112613070044244750,(v)
f5=xe-x-0.1,  α≈0.111832559158962964833569456820,(vi)
f6=x2+sin(x)+x,
α=0,(vii)
f7=sin(2cos(x))-1-x2+esin(x3),
α≈1.306175201846827825014842909066,(viii)
f8=sin(2cos(x))-1-x2+esin(x3),
α≈-0.784895987661212535224856018448,(ix)
f9=cos(x)+sin(2x)1-x2+sin(x2)+x14+x3+1/2x,
α≈-0.925772249827561423326931990067,(x)
f10=tan(lnx)+cos(x3)×1/(2x),
α≈0.443260783556767073513472596321,(xi)
f11=tan-1x,
α=0,(xii)
f12=x6-10x3+x2-x+3,
α≈0.658604847118140436763860014710,(xiii)
f13=x4-x3+11x-7,
α≈0.803511199110777688978137660293,(xiv)
f14=x3-cosx+2,
α≈-1.172577964753970012673332714868,(xv)
f15=x-cosx,
α≈0.641714370872882658398565300316,(xvi)
f16=ln(x)-x3+2sinx,
α≈1.297997743280371847164479238286.We shall determine the consistency and the stability of results by examining the convergence of the new second-derivative-free iterative methods. The findings are shown by illustrating the effectiveness of the fourth-order methods for determining the simple root of a nonlinear equation. Consequently, we can give estimates of the approximate solution produced by the fourth-order methods. The numerical computations listed in Table3 were performed with MATLAB 7.6. For comparisons, we have used the fourth-order derivative-free method of Kung-Traub (KTM) as comes next:(3.1)yn=xn+f(xn),zn=yn-f(xn)f(yn)f(yn)-f(xn),xn+1=zn-f(xn)f(yn)f(zn)-f(xn)[1f[yn,xn]-1f[zn,yn]],
where f[yn,xn] and f[zn,yn] are divided differences, and the Ostrowski’s method (OM) as follows: (3.2)kn=xn-f(xn)f′(xn),xn+1=kn-(xn-kn)f(xn)-2f(kn)f(kn).Table 3
Comparison of different methods with the same total number of evaluations (TNE=12).
FunctionsGuessesKTMOMK(-1/2)(2.10)(2.11)(2.12)f10.60.7e−880.2e−1080.7e−1740.4e−1380.3e−1720.7e−157f10.70.1e−840.7e−1000.4e−1590.5e−1250.6e−1480.4e−135f1−0.10.1e−1620.2e−2460.3e−3850.1e−2290.6e−2280.8e−460f20.80.1e−790.2e−1400.1e−930.7e−920.6e−850.1e−119f20.60.1e−2320.5e−1810.2e−1690.1e−1450.2e−1400.8e−182f20.40.1e−4680.5e−2940.5e−3240.2e−2950.1e−2890.9e−349f31.70.1e−720.3e−1850.3e−1980.3e−1720.3e−1840.1e−189f31.20.8e−1680.3e−1960.4e−1480.2e−1480.3e−1550.3e−195f31.80.1e−110.1e−1580.3e−1730.1e−1470.1e−1590.7e−158f41.90.1e−2630.6e−2240.7e−2080.4e−1890.2e−2050.4e−318f42.30.1e−2860.2e−2280.6e−2440.1e−2080.4e−2320.2e−211f41.80.1e−2000.1e−1650.5e−1180.2e−1170.2e−1330.6e−163f50.20.3e−1970.1e−2820.1e−2390.2e−2370.1e−3070.7e−248f500.2e−1870.1e−2660.3e−2690.1e−2400.6e−2620.9e−232f5−0.10.1e−1240.1e−2000.1e−1890.5e−1820.2e−1920.1e−166f60.30.9e−1380.2e−2190.1e−2320.8e−1810.5e−2050.1e−184f6−0.10.7e−2030.3e−3140.1e−3420.6e−2750.1e−3030.9e−302f60.70.4e−810.1e−1470.2e−1520.5e−1010.4e−1140.4e−101f71.290.2e−2130.6e−3480.3e−3780.2e−3760.4e−3860.2e−376f71.310.4e−3230.1e−5150.4e−5280.7e−5350.9e−5400.6e−533f71.30.3e−1440.1e−4580.7e−4470.1e−4810.2e−4880.2e−480f8−0.70.3e−1440.4e−2760.2e−2950.1e−2820.8e−2750.8e−248f8−0.90.1e−1760.2e−2640.5e−2750.3e−3020.5e−2540.2e−234f8−0.820.3e−2800.3e−3870.7e−4060.3e−4150.3e−3790.9e−358f9−0.920.4e−2410.2e−4180.4e−3580.2e−3680.3e−3770.1e−378f9−0.930.5e−2670.1e−4530.6e−4240.1e−4100.3e−4200.9e−422f9−0.90.2e−930.6e−2520.1e−1510.3e−1860.3e−1940.2e−195f100.410.2e−980.5e−3720.8e−2660.1e−2210.3e−2330.8e−236f100.420.1e−1400.3e−4130.7e−3220.1e−2590.4e−2410.1e−273f100.430.1e−2050.9e−4780.1e−3420.7e−3200.1e−3310.3e−334f110.50.8e−1750.4e−3010.1e−4710.3e−2150.3e−3490.5e−185f110.30.4e−3080.5e−4330.1e−4450.9e−3710.2e−4760.3e−327f11−0.20.2e−4140.1e−5400.1e−5440.1e−4860.3e−5310.5e−450f120.810.1e−810.5e−1990.7e−2080.1e−2410.2e−2320.2e−229f120.80.5e−1790.1e−2050.5e−2150.1e−2440.1e−2350.8e−239f120.50.5e−630.5e−1650.1e−830.5e−1250.7e−1190.5e−133f130.90.3e−1080.1e−3140.6e−3420.1e−2750.5e−2870.2e−324f130.80.1e−4260.5e−6770.2e−7130.2e−6350.7e−6470.6e−705f130.850.1e−1680.6e−3930.4e−4550.1e−3520.3e−3640.1e−409f14−1.10.3e−1470.7e−2970.7e−2740.8e−2650.1e−3100.2e−266f14−1.30.1e−380.1e−2470.6e−2540.2e−2350.2e−2410.1e−215f14−1.50.5e−1240.2e−1550.1e−1520.3e−1550.7e−1440.1e−123f150.40.5e−2250.3e−3300.2e−3270.2e−2530.1e−4200.6e−269f150.90.1e−2820.2e−3710.2e−4120.1e−2260.1e−2680.3e−233f151.30.1e−2470.3e−2390.3e−2380.7e−1390.3e−1640.1e−139f161.40.7e−800.1e−2350.1e−2520.3e−2670.7e−2570.6e−289f161.150.2e−1030.4e−1600.4e−830.3e−1280.9e−1210.1e−134f161.30.1e−5560.4e−6600.2e−7390.1e−6700.6e−6610.6e−697We also have used King’s family withβ=-1/2, as K(−1/2) in comparisons with our novel methods (2.10), (2.11), (2.12) from the suggested class. For convergence, it is required that the distance of two consecutive approximations (|xn+1-xn| with n≥0) be less than ϵ. And the absolute value of the function |f(xn)|, also referred to as residual, be less than ϵ=800. Note that the residuals are listed in Table 3 for each starting point and by considering the total number of evaluations as 12. We accept an approximate solution rather than the exact root, depending on the precision ϵ of the computer. The test results in Table 3show that the order of convergence and accuracy of the proposed methods are in accordance with the theory developed in the previous section. For most of the functions we have tested, the methods introduced in the present work behave well in comparison to the other methods of order four. The important characteristic of the novel methods is that they do not require the computation of second-order or higher-order derivatives of the function to carry out iterations. However, it should be emphasized that the order of convergence is a property of iteration formula near root: the order of convergence is one thing; the total number of iterations is another one. In general, for a given iteration formula, the total number of iterations depends not only on the order of convergence but also on the initial approximation x0.In Table3, as an instance, 0.3e−172 shows that the absolute value of the corresponding (test) function after 4 full iterations is zero up to 172 decimal digits.


## 4. Concluding Remarks

In numerical analysis, many methods produce sequences of real numbers, for instance the iterative methods for solving nonlinear equations. Sometimes, the convergence of these sequences is slow and their utility in solving practical problems quite limited. Convergence acceleration methods try to transform a slowly converging sequence into a fast convergent one. Due to this, this paper has aimed to give a rapidly convergent two-point class for approximating simple roots. As high as possible of convergence order was attained by using as small as possible number of evaluations per full cycle. The local order of our class of iterations was established theoretically, and it has been seen that our class supports the optimality conjecture of Kung-Traub (1974). It was shown that choosing appropriate form of weight functions would end up in both existing and new iterative optimal root solvers without memory. Clearly, our contribution in this paper has unified the existing quartically methods, which are available in literature. In the sequel, numerical examples have used in order to show the efficiency and accuracy of the novel methods from our suggested second-derivative-free class. Finally, it should be noted that, like all other iterative methods, the new methods from the class (2.1)-(2.2) have their own domains of validity and in certain circumstances should not be used.



---

*Source: 270903-2011-12-08.xml*