# A New Family of Fourth-Order Optimal Iterative Schemes and Remark on Kung and Traub’s Conjecture

Authors: Chein-Shan Liu; Tsung-Lin Lee
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Kung and Traub conjectured that a multipoint iterative scheme without memory based onm evaluations of functions has an optimal convergence order p=2m−1. In the paper, we first prove that the two-step fourth-order optimal iterative schemes of the same class have a common feature including a same term in the error equations, resorting on the conjecture of Kung and Traub. Based on the error equations, we derive a constantly weighting algorithm obtained from the combination of two iterative schemes, which converges faster than the departed ones. Then, a new family of fourth-order optimal iterative schemes is developed by using a new weight function technique, which needs three evaluations of functions and whose convergence order is proved to be p=23−1=4.


---

## Body

## 1. Introduction

The most basic problem in engineering and scientific applications is to find the root of a given nonlinear equation(1)fx=0,where f∈CI,ℝ and I⊂ℝ is an interval we are interested in, and we suppose that r∈I is a simple solution with fr=0 and f′r≠0.The famous Newton method (NM) for iteratively solving equation (1) is given by(2)xn+1=xn−fxnf′xn,n=0,1,…,which is quadratically convergent. Due to its simplicity and rapid convergence, the Newton method is still the first choice to solve equation (1).An extension of the NM to a third-order iterative scheme was made by Halley [1]:(3)xn+1=xn−2fxnf′xn2f′xn2−fxnf″xn.For the engineering design of the vibrating modes of an elastic system, sometimes we may need to know the eigenvalues of a large-size square matrix, which results in a highly nonlinear and high-order polynomial equation. More often, the functionfx is itself obtained from other nonlinear ordinary differential equations or partial differential equations. In this situation, it is hard to calculate f″x when we apply the Halley method to solve the nonlinear problem.Kung and Traub conjectured that a multipoint iteration without memory based onm evaluations of functions has an optimal convergence order p=2m−1. It means that the upper bound of the efficiency index (E.I.) = p1/m is 21−1/m<2. For m=2, the NM is one of the second-order optimal iterative schemes; however, with m=3, the Halley method is not the optimal one whose E.I. = 1.44225 is low.The pioneering work of Newton has inspired a lot of studies to solve nonlinear equations, whereby different fourth-order iterative methods were developed for more quickly and stably solving nonlinear equations [2–9]. Many methods to construct the two-step fourth-order optimal schemes were based on the operations of fxn,f′xn,fyn where yn is obtained from the first Newton step [2, 4–8, 10–14]. Recently, Chicharro et al. [9] proposed a new technique to construct the optimal fourth-order iterative schemes based on the weight function technique.


## 2. Preliminaries

Before deriving the main results in the next section, we begin with some standard terminologies.Definition 1.
Let the iterative sequencexn generated from an iterative scheme converge to a simple root r. If there exists a positive integer p and a real number C such that(4)limn⟶∞xn+1−rxn−rp=C,then p is the order of convergence and C is the asymptotic error constant.
Leten=xn−r be the error in the nth iterate. Then, the relation(5)en+1=Cenp+Oenp+1,is called the error equation of an iterative scheme. For example, for the Newton method, the error equation reads as(6)en+1=c2en2+Oen3,where(7)cn≔fnrn!f′r,n=2,….Definition 2.
(see [10]). An iterative scheme is said to have the optimal order p, if p=2m−1 where m is the number of evaluations of functions (including derivatives).Definition 3.
The efficiency index (E.I.) of an iterative scheme is defined by E.I. =p1/m.Definition 4.
The conjecture of Kung and Traub asserted that a multipoint iteration without memory based onm evaluations of functions has an optimal order p=2m−1 of convergence [11]. It indicates that the upper bound of the efficiency index is 21−1/m<2.Definition 5.
The iterative schemes are of the same class, if they are of the same orderp and have the same m evaluations of the same functions.


## 3. Main Results

We begin with the error equation of the NM:(8)en+1=c2en2−A3en3−A4en4+⋯,where(9)A3=2c22−2c3,(10)A4=7c2c3−4c23−3c4.Refer the papers, for instance, [6, 12, 13].Throughout of the paper, we fix the following notation:(11)yn=xn−fxnf′xn,which is the first step of many two-step iterative schemes.We summarize some fourth-order optimal iterative schemes which were modified from the NM by Chun [14]:(12)xn+1=xn−fxnf′xn−fxnfxn−fyn2fynf′xn,en+1=2c23−c2c3en4+⋯,(13)xn+1=xn−fxnf′xn−f2xnf2xn−2fxnfyn+2f2ynfynf′xn,en+1=3c23−c2c3en4+⋯,by Chun [4]:(14)xn+1=xn−fxnf′xn−1+2fynfxn+f2ynf2xnfynf′xn,en+1=4c23−c2c3en4+⋯,(15)xn+1=xn−fxnf′xn−1+2fynfxnfynf′xn,en+1=5c23−c2c3en4+⋯,by King [5]:(16)xn+1=xn−fxnf′xn−fxn+γfynfxn+γ−2fynfynf′xn,en+1=1+2γc23−c2c3en4+⋯,where γ∈ℝ, by Chun and Ham [2]:(17)xn+1=xn−fxnf′xn−4f2xn+6fxnfyn+3f2yn4f2xn−2fxnfyn−f2ynfynf′xn,en+1=3c23−c2c3en4+⋯,by Kuo et al. [8]:(18)xn+1=xn−f2xn+f2ynf′xnfxn−fyn,en+1=3c23−c2c3en4+⋯,by Ostrowski [15]:(19)xn+1=xn−fxnfxn−fynf′xnfxn−2fyn,en+1=c23−c2c3en4+⋯,by Maheshwari et al. [16]:(20)xn+1=xn−fxnf′xnf2ynf2xn+fxnfxn−fyn,en+1=4c23−c2c3en4+⋯,and by Ghanbari [12]:(21)xn+1=xn−fxnf′xn−fxn+2fynfxn+fyn2fynf′xn,en+1=6c23−c2c3en4+⋯,(22)xn+1=xn−fxnf′xn−fxn+fynfxn−fynfynf′xn,en+1=3c23−c2c3en4+⋯.It is interesting that the iterative schemes (12)-(22) are of the same class because they have same convergence order p=4 and operated with the same evaluations on fxn,f′xn,fyn. The efficiency index (E.I.) of the above eleven iterative schemes is the same 43=1.5874, and they are of the optimal fourth-order iterative schemes with three evaluations of fxn,f′xn,fyn in the sense of Kung and Traub, such that p=2m−1=4. They belong to the same class with the error equations having a common type:(23)en+1=aic23−c2c3en4+Oen5,where ai are different constants for different optimal fourth-order iterative schemes, which may be zero. Can we raise the order to five by a suitable combination of these iterative schemes? Later, we will reply to this problem.Theorem 1.
If the conjecture of Kung and Traub is true, then the two-step optimal fourth-order iterative scheme(24)yn=xn−fxnf′xn,xn+1=xn−Hfxn,f′xn,fyn,which is based on the evaluations of fxn,f′xn,fyn, must have the following form of error equation:(25)en+1=a0c23−c2c3en4+Oen5,where a0 is some constant, which may be zero.Proof.
Suppose that equation (25) is not true, such that we have(26)en+1=a0c23−b0c2c3en4+Oen5,where b0≠1.
The weighting factorsw1, w2, and w3 are subjected to(27)w1+w2+w3=1.
Then, we consider the weighting average of the error equations in equation (23) with i=1,2 and equation (26) to be zero in en4:(28)w1a1c23−c2c3+w2a2c23−c2c3+w3a0c23−b0c2c3=0,which leads to(29)a1w1+a2w2+a0w3=0,w1+w2+b0w3=0.
The determinant of the coefficient matrix of the linear equations (27) and (29) is b0−1a2−a1≠0 because b0≠1 and a1≠a2. From equations (27) and (29), we have the unique solution of w1,w2,w3. Thus, we can derive a new iterative scheme by a weighting combination of three optimal fourth-order iterative schemes with the solved factors w1,w2,w3 whose convergence order is raised to five. This contradicts the conjecture of Kung and Traub, who asserted that the optimal order for the iterative scheme with m=3 is 2m−1=4 for a multipoint iteration without memory based on m evaluations of functions.
Obviously, Theorem1 demonstrates that we cannot raise the convergence order to five by a weighting combination of any three optimal fourth-order convergence iterative schemes.Theorem 2.
The following two-step iterative scheme:(30)xn+1=xn−fxnf′xn−Hηnfynf′xn,for solving fx=0 has fourth-order convergence, where yn is computed by equation (11), and H is a weight function in terms of(31)ηn≔fynfxn,with(32)H0=1,H′0=2.
The corresponding error equation is(33)en+1=5−H″02c23−c2c3en4+Oen5.Proof.
For the proof of the convergence, we letr be a simple solution of fx=0, i.e., fr=0 and f′r≠0. We suppose that xn is sufficiently close to the exact solution r, such that(34)en=xn−ris a small quantity, and it follows that(35)en+1=en+xn+1−xn.
By using the Taylor series, we have(36)fxn=f′ren+c2en2+c3en3+c4en4+⋯,(37)f′xn=f′r1+2c2en+3c3en2+4c4en3+⋯.
It immediately leads to(38)fxnf′xn=en+c2en2+c3en3+c4en4+⋯1+2c2en+3c3en2+4c4en3+⋯+⋯=en−c2en2+A3en3+A4en4+⋯.
From equations (11) and (38), we have(39)yn=r+c2en2−A3en3−A4en4+⋯,(40)fyn=f′rc2en2−A3en3−A4−c23en4+⋯.
From equations (40), (37), and (36), it follows that(41)fynf′xn=c2en2−A3en3−A4−c23en4+⋯1+2c2en+3c3en2+4c4en3+⋯=c2en2+2c3−4c22en3+13c23−14c2c3+3c4en4+⋯,(42)fynfxn=c2en2−A3en3−A4−c23en4+⋯en+c2en2+c3en3+c4en4+⋯=c2en+2c3−3c22en2+3c4−10c2c3+8c23en3+⋯.
From equations (31) and (42), we have(43)ηn=c2en+2c3−3c22en2+3c4−10c2c3+8c23en3+⋯.
Because the least order of the termfyn/f′xn as shown in equation (41) is two, we only need to expand Hηn around zero to the second-order by using equation (43) and(44)Hηn=H0+H′0ηn+H″02ηn2+⋯=H0+c2H′0en+c222H″0−6H′0+2c3H′0en2+⋯.
Inserting equations (11), (39), (44), and (41) into equation (30), we have(45)en+1=c2en2−A3en3−A4en4−H0+c2H′0en+c222H″0−6H′0+2c3H′0en2,×c2en2+2c3−4c22en3+13c23−14c2c3+3c4en4+⋯.
Through some manipulations, we can derive(46)en+1=c2−c2H0en2−2c22−4c22H0+H′0c22+2H0c3−2c3en3,−7c2c3−4c23−3c4+H013c23−14c2c3+3c4+c2H′02c3−4c22en4,−c2c222H″0−6H′0+2c3H′0en4+⋯,which, due to equation (32), can be arranged to that in equation (33).Theorem 3.
(see [12]). The following two-step iterative scheme:(47)xn+1=xn−fxnf′xn−f2xn+2+αfxnfxn+θf2xnf2xn+αfxnfxn+βf2xnfynf′xn,for solving fx=0 has fourth-order convergence, where yn is computed by equation (11). The error equation reads as(48)en+1=5+2α−θ+βc23−c2c3en4+Oen5,which is not supplied in [12].Proof.
It is easy to check that the weight function in iterative scheme (47):(49)Hη=1+2+αη+θη21+αη+βη2,satisfies equation (32); hence, iterative scheme (47) is a special case of iterative scheme (30).
We can derive(50)H″η=1A4ηA2ηAηB′′η−BηA′η−2AηB′η−BηA′ηAηA′η,where(51)A≔1+αη+βη2,B≔1+2+αη+θη2.
InsertingA0=1,A′0=α,A″0=2β,B0=1,B′0=2+α,B″0=2θ into equation (50) by taking η=0, we have(52)H″0=−22α−θ+β.
Inserting equation (52) into equation (33), we can derive(53)en+1=5+2α−θ+βc23−c2c3en4+Oen5.
This ends the proof of this theorem.
Theorem2 includes those in [9, 17] as special cases. The family developed by Chicharro et al. [9]:(54)xn+1=xn−Gηnfxnf′xn,with G0=G′0=1 and G″0=4 is a special case because we can derive(55)Hηnηn=Gηn−1.
Accordingly,(56)Hηn+ηnH′ηn=G′ηn,2H′ηn+ηnH″ηn=G″ηn,and H0=1 and H′0=2 imply G0=G′0=1 and G″0=4. For H, we have only two constraints, but for G, there are three constraints. Hence, iterative scheme (30) is more general than the iterative scheme (54). Moreover, a further differential of the last term in equation (56),(57)3H″ηn+ηnH″′ηn=G″′ηn,leads to(58)3H″0=G″′0,and hence the error equation of iterative scheme (54) is(59)en+1=5−G″′06c23−c2c3en4+Oen5.
In [9], Chicharro et al. derived the error equation as en+1=5c23−c2c3en4+Oen5 (equation (2) in [9]), which is incorrect to miss the term −G″′0c23en4/6 in the error equation.
The general function ofHη is given by(60)Hη=1+2η+∫0η∫0ξFzdzdξ,where Fz is any integrable function. There are two interesting iterative schemes generated from Fz=cosz (COSM) and Fz=sinz (SINM):(61)xn+1=xn−fxnf′xn−2+2fynfxn−cosfynfxnfynf′xn,xn+1=xn−fxnf′xn−1+3fynfxn−sinfynfxnfynf′xn.


## 4. Combinations of Iterative Schemes

In this section, we give some methods to combine the iterative schemes as listed in Table1, which are special cases of the iterative schemes (47) and (30).Table 1
The comparison of different iterative schemes on the error equations.
AlgorithmαβθError equationen+1(12)–2102c23−c2c3en4+Oen5(13)–2203c23−c2c3en4+Oen5(14)0014c23−c2c3en4+Oen5(15)0005c23−c2c3en4+Oen5(16)γ−2001+2γc23−c2c3en4+Oen5(17)–1/2–1/43/43c23−c2c3en4+Oen5(18)–1003c23−c2c3en4+Oen5(19)–200c23−c2c3en4+Oen5(20)–10–14c23−c2c3en4+Oen5(21)2146c23−c2c3en4+Oen5(22)–21–13c23−c2c3en4+Oen5From Table1, we can observe that there exists a cubic term c23 in the error equation for most iterative schemes. Indeed, this term is a dominant factor to enlarge the error, and thus we can combine two iterative schemes by eliminating this term.Theorem 4.
For the following two-step iterative scheme:(62)xn+1=xn−fxnf′xn−w1f2xn+2+α1fxnfyn+θ1f2ynf2xn+α1fxnfyn+β1f2ynfynf′xn−w2f2xn+2+α2fxnfyn+θ2f2ynf2xn+α2fxnfyn+β2f2ynfynf′xn,if(63)a1≔5+2α1−θ1+β1≠a2≔5+2α2−θ2+β2,(64)w1=−a2a1−a2,w2=a1a1−a2,then the error equation reads as(65)en+1=−c2c3en4+Oen5.Proof.
The weighting factors are subjected to(66)w1+w2=1.
We seek the combination of iterative scheme (47) with two sets of the parameters α1,β1,θ1 and α2,β2,θ2 and demand the coefficient preceding c23en4 being zero,(67)w1a1+w2a2=w15+2α1−θ1+β1+w25+2α2−θ2+β2=0.
Solving equations (66) and (67), we can derive equation (64), and the error equation (48) reduces to that in equation (65).
We cannot exhaust all the combinations of the iterative schemes; however, we list the following two: one is the combination of equations (16) and (19), namely, the KOM:(68)xn+1=xn+fxn2γf′xn+12γfxn+γfynfxn+γ−2fynfynf′xn−1+2γfxnfxn−fyn2γf′xnfxn−2fyn.
The other one is the combination of equations (12) and (19), namely, the COM:(69)xn+1=xn+fxnf′xn+fxnfxn−fyn2fynf′xn−2fxnfxn−fynf′xnfxn−2fyn.


## 5. Second Family of Optimal Fourth-Order Iterative Schemes

In Theorem2, we have derived a new family of optimal fourth-order iterative schemes with the assumption that the H-function satisfies H0=1 and H′0=2. We can relax the conditions to H0=1 and derive the following result.Theorem 5.
Suppose that there are two different functionsH1η and H2η satisfying(70)H10=1,H20=1,(71)H1′0≠H2′0.
The following two-step iterative scheme:(72)xn+1=xn−fxnf′xn−w1H1ηn+w2H2ηnfynf′xn,for solving fx=0 has fourth-order convergence, where yn is computed by equation (11), and η is defined by equation (31). The corresponding error equation is(73)en+1=5−w1H1″0+w2H2″02c23−c2c3en4+Oen5,where(74)w1=H2′0−2H2′0−H1′0,w2=2−H1′0H2′0−H1′0.Proof.
From equations (46) and (70), it follows that the error equations corresponding to H1 and H2 are, respectively,(75)en+1=2−H1′0c22en3−A1en4+⋯,en+1=2−H2′0c22en3−A2en4+⋯,where(76)A1≔9c23−7c2c3+c2H1′02c3−4c22+c2c222H1″0−6H1′0+2c3H1′0,A2≔9c23−7c2c3+c2H2′02c3−4c22+c2c222H2″0−6H2′0+2c3H2′0.
We seek a combination of the two iterative schemes corresponding toH1 and H2 and ask the coefficient preceding en3 to be zero, such that we have to solve w1 and w2 from(77)w1+w2=1,w12−H1′0+w22−H2′0=0,whose solutions are given by equation (74). At the same time, the combined error equation is given by(78)en+1=−w1A1en4−w2A2en4+⋯,=−9c23−7c2c3+2c22c3−4c22+c232w1H1″0+w2H2″0+4c2c3−6c23en4+⋯,which can be arranged to that in equation (73).
The family in equation (72) includes some optimal fourth-order iterative schemes with two parameters w1 and w2, whose error equation again belongs to the type in equation (23). It can be seen that the functions with H0=1 are very general, and for this class of iterative schemes, the conjecture of Kung and Traub is also true.


## 6. Numerical Experiments

In this section, we give numerical tests of the proposed combined iterative schemes. The test examples are given by(79)f1x=x3+4x2−10,f2x=x2−ex−3x+2,f3x=x−13−2,f4x=x+2ex−1,f5x=sin2x−x2+1.The corresponding solutions are, respectively,r1=1.3652300134, r2=0.2575302854, r3=2.2599210499, r4=−0.442854401002, and r5=1.4044916482.In Table2, for different functions, we list the number of iterations (NI) obtained by the presently developed algorithms, which are compared to the NM, the CM1 in equation (12), the CM2 in equation (15), the KM in equation (16) with γ=3, the OM in equation (19), the AM in equation (20), the GM in equation (21), the KOM in equation (68) with γ=3, and the COM in equation (69).Table 2
The comparison of different methods for the number of iterations.
Functionsf1,x0=−0.3f2,x0=0f3,x0=3f4,x0=3.5f5,x0=1NM5557117KM493478GM3836711CM1123454CM2243465OM563454AM243475COSM452365SINM452365KOM53456COM53444


## 7. Conclusions

Employing a new weight function, the nonlinear equations were solved by using a new family of the fourth-order iterative scheme, which is optimal according to the conjecture of Kung and Traub, and it was proven to be of fourth-order convergence with E.I. = 1.5874. Theorem1 indicated that if one can develop a fourth-order iterative scheme based on the evaluations of fxn,f′xn,fyn whose coefficient preceding c2c3en4 is not −1, then the Kung–Traub conjecture would be disproved. We also proposed a combination of two fourth-order iterative schemes of which the dominant term c23en4 in the error equation is eliminated. Upon comparing some examples to other methods, we found that the combined iterative scheme converges faster. The present iterative scheme was competitive to other optimal fourth-order iterative schemes.



---

*Source: 5516694-2021-02-17.xml*