# Attracting Periodic Cycles for an Optimal Fourth-Order Nonlinear Solver

Authors: Mi Young Lee; Changbum Chun
Journal: Abstract and Applied Analysis
 (2012)

---

## Abstract

We consider an optimal fourth-order method for solving nonlinear
equations and construct polynomials such that the rational map arising from the method applied to these polynomials has an attracting periodic orbit of any prescribed period.


---

## Body

## 1. Introduction

Recently, an optimal fourth-order iterative method to find a simple rootρ, that is, f(ρ)=0 and f′(ρ)≠0, of a nonlinear equation f(x)=0, which is given by(1.1)xn+1=xn-16f(xn)f′(xn)-5f′2(xn)+30f′(xn)f′(yn)-9f′2(yn),
where yn=xn-(2/3)(f(xn)/f′(xn)) was proposed in [1] and its dynamics behavior was investigated and analyzed in detail. By an optimal method, we mean a multipoint method without memory which requires n+1 functional evaluations per iteration, but achieves the order of convergence 2n [2].The method (1.1) may be used to approximate both real and complex roots of the nonlinear equation with x0∈ℂ. If the initial guess x0 is chosen sufficiently near a zero of f, then an iterative method is expected to converge. This is, however, not true in general if there exists an attracting periodic orbit or cycle of period k≥2 (whose definition will be introduced below). If the initial guess happens to be chosen from the basin of attraction of an attractive periodic cycle, the sequence {xn}n=0∞ converges to the attractive cycle, not to a zero of f since any root of f(x)=0 may be considered as a period orbit of period 1. Thus the existence of attracting periodic cycles of period greater than or equal to 2 could interfere with an iterative method searching for a root of the nonlinear equation. As a result, it has been an important concern from practical aspect in iteration theory to construct specific polynomials for a given method such that the map arising from the iterative method applied to the polynomials has an attractive periodic orbit. In this direction there was some result in [3] where attractive periodic orbits of any prescribed period were constructed for some classical third-order methods. Motivated by this, in this paper we extend the construction of attractive periodic cycles of any prescribed period to higher-order iterative methods. To this end, we will recall some preliminaries, see for example Milnor [4], Amat et al. [5], and Chun et al. [1]. Let R:ℂ̂→ℂ̂ be a rational map on the Riemann sphere.Definition 1.1.
Forz∈ℂ̂ we define its orbit as the set(1.2)orb(z)={z,R(z),R2(z),…,Rn(z),…}.Definition 1.2.
A pointz0 is a fixed point of R if R(z0)=z0.Definition 1.3.
A periodic pointz0 of period m is such that Rm(z0)=z0 where m is the smallest such integer. The set of the m distinct points {z,R(z),R2(z),…,Rm-1(z)} is called a periodic cycle.Remark 1.4.
Ifz0 is periodic of period m then it is a fixed point for Rm.Definition 1.5.
Ifz0 is a periodic point of period m, then the derivative (Rm)′(z0) is called the eigenvalue of the periodic point z0.Remark 1.6.
By the chain rule, ifz0 is a periodic point of period m, then its eigenvalue is the product of the derivatives of R at each point on the orbit of z0, and we have
(1.3)(Rm)′(z0)=(Rm)′(z1)=⋯=(Rm)′(zn-1),
that is, all the points of a cycle have the same eigenvalue.We classify the fixed points of a map based on the magnitude of the derivative.Definition 1.7.
A pointz0 is called attracting if |R′(z0)|<1, repelling if |R′(z0)|>1, and neutral if |R′(z0)|=1. If the derivative is zero then the point is called superattracting.Definition 1.8.
The Julia set of a nonlinear mapR(z), denoted J(R), is the closure of the set of its repelling periodic points. The complement of J(R) is the Fatou set 𝔽(R).
By its definition,J(R) is a closed subset of ℂ̂. A point z0 belongs to the Julia set if and only if dynamics in a neighborhood of z0 displays sensitive dependence on the initial conditions, so that nearby initial conditions lead to wildly different behavior after a number of iterations. As a simple example, consider the map R(z)=z2 on ℂ̂. The entire open disk is contained in 𝔽(R), since successive iterates on any compact subset converge uniformly to zero. Similarly the exterior is contained in 𝔽(R). On the other hand if z0 is on the unit circle than in any neighborhood of z0 any limit of the iterates would necessarily have a jump discontinuity as we cross the unit circle. Therefore J(R) is the unit circle. Such smooth Julia sets are exceptional.Lemma 1.9 (Invariance lemma (Milnor [4])).
The Julia setJ(R) of a holomorphic map R:ℂ̂→ℂ̂ is fully invariant under R. That is, z belongs to J if and only if R(z) belongs to J.Lemma 1.10 (Iteration Lemma).
For anyk>0, the Julia set J(Rk) of the k-fold iterate coincides with J(R).Definition 1.11.
IfO is an attracting periodic orbit of period m, we define the basin of attraction to be the open set A∈ℂ̂ consisting of all points z∈ℂ̂ for which the successive iterates Rm(z),R2m(z),… converge towards some point of O.
The basin of attraction of a periodic orbit may have infinitely many components.Definition 1.12.
The immediate basin of attraction of a periodic orbit is the connected component containing the periodic orbit.Lemma 1.13.
Every attracting periodic orbit is contained in the Fatou set ofR. In fact the entire basin of attraction  A for an attracting periodic orbit is contained in the Fatou set. However, every repelling periodic orbit is contained in the Julia set.


## 2. Attractive Cycles Results

Let us consider the mapRf associated to f(2.1)Rf(z)=z+16f(z)f′(z)5f′2(z)-30f′(z)f′(y)+9f′2(y),
where(2.2)y=z-23f(z)f′(z),
for which the optimal method (1.1) is written as(2.3)xn+1=Rf(xn),n≥0.Toward the aim to construct periodic orbits of any prescribed period for the method (1.1), we have the following characterization.Proposition 2.1.
LetΩ={x1,x2,…,xn} be a set of  n distinct complex numbers, and let  f be a complex analytic function. Then  Ω is periodic orbit of period  n of iteration function  Rf if and only if
(2.4)16f′(xi)f(xi)xi+1-xi=5f′2(xi)-30f′(xi)f′(yi)+9f′2(yi),i=1,2,…,n-1,16f′(xn)f(xn)x1-xn=5f′2(xn)-30f′(xn)f′(yn)+9f′2(yn),
where yi=xi-(2/3)(f(xi)/f′(xi)), i=1,2,…,n.Proof.
Assume thatΩ is a periodic orbit of Rf. Then Rf(xi)=xi+1 for i=1,2,…,n-1 and Rf(xn)=x1. We have
(2.5)xi+1=xi+16f′(xi)f(xi)5f′2(xi)-30f′(xi)f′(yi)+9f′2(yi),i=1,2,…,n-1,x1=xn+16f′(xn)f(xn)5f′2(xn)-30f′(xn)f′(yn)+9f′2(yn).
Therefore, we obtain
(2.6)xi+1-xi=16f′(xi)f(xi)5f′2(xi)-30f′(xi)f′(yi)+9f′2(yi),i=1,2,…,n-1,x1-xn=16f′(xn)f(xn)5f′2(xn)-30f′(xn)f′(yn)+9f′2(yn).
Conversely, suppose that f satisfies condition (2.4). Then we easily have
(2.7)Rf(xi)=xi+16f′(xi)f(xi)(16f′(xi)f(xi))/(xi+1-xi)=xi+1,i=1,2,…,n-1,Rf(xn)=xn+16f′(xn)f(xn)(16f′(xn)f(xn))/(x1-xn)=x1.Proposition 2.2.
For any positive integern≥2, there exists a polynomial  f(x) of degree less than or equal to  3n-1 for which  Rf has a periodic orbit of period  n.Proof.
Letx1,x2,…,xn be a given a set of n distinct complex numbers, let z1,z2,…,zn be a set of n nonzero complex numbers, and let s1,s2,…,sn be another set of nonzero complex numbers such that
(2.8)yi≠yj∀i≠j,yi≠xj∀i,j=1,2,…,n,152-9(5si2-16sizixi+1-xi)≥0,i=1,2,…,n-1,152-9(5sn2-16snznx1-xn)≥0,
where yi=xi-(2/3)(zisi).
Assume that there exists a polynomialf(x) such that
(2.9)f(xi)=zi,i=1,2,…,n,f′(xi)=si,i=1,2,…,n,9f′2(yi)-30sif′(yi)+5si2=16sizixi+1-xi,i=1,2,…,n-1,9f′2(yn)-30snf′(yn)+5sn2=16snznx1-xn.
Then by Proposition 2.1, Ω={x1,x2,…,xn} is a periodic orbit of period n of Rf. Using (2.9) and condition (2.8) yields
(2.10)f′(yi)=15±152-9(5si2-(16sizi/(xi+1-xi)))9i=1,2,…,n-1,f′(yn)=15±152-9(5sn2-(16snzn/(x1-xn)))9.
We now show that such a polynomial exists. For this, we use the Hermite interpolation procedure. We begin the construction by writingf(x) as
(2.11)f(x)=∑i=13naifi(x),
where the functions fi(x) are polynomials defined as follows:
(2.12)f1(x)=1,f2(x)=(x-x1),f3(x)=(x-x1)2,f4(x)=(x-x1)2(x-y1)2,f5(x)=(x-x1)2(x-y1)2(x-x2),f6(x)=(x-x1)2(x-y1)2(x-x2)2,f7(x)=(x-x1)2(x-y1)2(x-x2)2(x-y2)2,⋮f3n(x)=(x-x1)2(x-y1)2(x-x2)2(x-y2)2⋯(x-xn)2.
To determine the polynomialf(x) we must find suitable coefficients ai for i=1,2,…,3n. For this we must solve a linear system of 3n equations with 3n unknown of the form AX=B. The matrix A associated with the linear system of equations is given by
(2.13)A=(f1(x1)f2(x1)f3(x1)⋯f3n(x1)f1′(x1)f2′(x1)f3′(x1)⋯f3n′(x1)f1′(y1)f2′(y1)f3′(y1)⋯f3n′(y1)f1(x2)f2(x2)f3(x2)⋯f3n(x2)f1′(x2)f2′(x2)f3′(x2)⋯f3n′(x2)f1′(y2)f2′(y2)f3′(y2)⋯f3n′(y2)⋯⋯⋯⋯⋯f1′(yn)f2′(yn)f3′(yn)⋯f3n′(yn))
and the column vectors X,B∈ℝn are given by X=(a1,a2,…,a3n)T and B=(f(x1),f′(x1),f′(y1),…,f(xn),f′(xn),f′(yn))T. The components of the upper triangle of the matrix A are zero, and the components of the diagonal of A are nonzero. Therefore, the linear system AX=B has a unique solution.Example 2.3.
Let us construct a polynomialf(x) for which the iterative method Rf has a periodic orbit of period 2. For this, we let x1=0,x2=1,z1=f(x1)=2,z2=f(x2)=2,s1=f′(x1)=2 and s2=f′(x2)=2. Then we have y1=x1-(2/3)(z1/s1)=-2/3, y2=x2-(2/3)(z2/s2)=1/3, f′(y1)=(15±152-9(5s12-16s1z1/(x2-x1)))/9=22/3,-2/3, and f′(y2)=(15±152-9(5s22-16s2z2/(x1-x2)))/9=14/3,2. We construct a polynomial f(x)=∑i=16aifi(x), where f1(x)=1, f2(x)=x, f3(x)=x2, f4(x)=x2(x+(2/3))2, f5(x)=x2(x+(2/3))2(x-1), f6(x)=x2(x+(2/3))2(x-1)2. Then matrix A is given by
(2.14)A=(f1(x1)00000f1′(x1)f2′(x1)0000f1′(y1)f2′(y1)f3′(y1)000f1(x2)f2(x2)f3(x2)f4(x2)00f1′(x2)f2′(x2)f3′(x2)f4′(x2)f5′(x2)0f1′(y2)f2′(y2)f3′(y2)f4′(y2)f5′(y2)f6′(y2)).
By evaluating A we obtain
(2.15)A=(10000001000001-43000111259000128092590012389-13272081).
Now we consider the system of linear equationsAX=B, where X=(a1,a2,a3,a4,a5,a6)T and B=(f(x1),f′(x1),f′(y1),f(x2),f′(x2),f′(y2))T. Here, we can take B=(2,2,22/3,2,2,14/3)T. Hence we have the following system:
(2.16)(10000001000001-43000111259000128092590012389-13272081)(a1a2a3a4a5a6)=(2222322143)
whose solution is X=(2,2,-4,18/25,72/125,12582/625)T. Therefore, the polynomial f is given by f(x)=2+2x-4x2+(18/25)x2(x+(2/3))2+(72/125)x2(x+2/3)2(x-1)+(12582/625)x2(x+2/3)2(x-1)2 = 2+2x+(3132/625)x2-(14808/625)x4+(5872/625)x3-(8028/625)x5+(12582/625)x6. From (2.1), we obtain Rf(0)=1 and Rf(1)=0. So, Ω={0,1} is a periodic orbit of period 2 for the method Rf(x).Proposition 2.4.
Letf(x) be a polynomial for which  Rf has a periodic orbit of period  n, say  Ω={x1,x2,…,xn}. If  f′′(xi)=0=f′′(yi) and  f′(xi)=f′(yi) or  f′′(xi)=0=f′′(yi) and  7f′(xi)=3f′(yi) for some  i=1,2,…,n, then  Ω is an superattracting periodic orbit of period  n for  Rf.Proof..
Without loss of generality, we may assume thatf′′(x1)=0=f′′(y1) and f′(x1)=f′(y1). By the chain rule, we have
(2.17)(Rfn)′(x1)=Rf′(xn)Rf′(xn-1)Rf′(xn-2)⋯Rf′(x1).
Note that on differentiating (2.1) we have
(2.18)Rf′(x)=[f′(x)(5f′2(x)-30f′(x)f′(y)+9f′2(y))2]-1×[f′(x)(5f′2(x)-30f′(x)f′(y)+9f′2(y))(21f′(x)2-30f′(x)f′(y))+9f′2(y)+16f(x)f′′(x)-16f(x)[(f′2(x)+2f(x)f′′(x))10f′3(x)f′′(x)-30f′2(x)f′′(x)f′(y)-2(f′2(x)+2f(x)f′′(x))(5f′(x)f′′(y)-3f′(y)f′′(y))]].
We therefore obtain Rf′(x1)=0. By (2.17) we conclude that (Rfn)′(x1)=0.



---

*Source: 263893-2012-04-29.xml*