# Reducing Chaos and Bifurcations in Newton-Type Methods

Authors: S. Amat; S. Busquier; Á. A.  Magreñán
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We study the dynamics of some Newton-type iterative methods when they are applied of polynomials degrees two and three. The methods are free of high-order derivatives which are the main limitation of the classical high-order iterative schemes. The iterative schemes consist of several steps of damped Newton's method with the same derivative. We introduce a damping factor in order to reduce thebad zones of convergence. The conclusion is
that the damped schemes become real alternative to the classical Newton-type method since both chaos and bifurcations of the original schemes are reduced. Therefore, the new schemes can be utilized to obtain good starting
points for the original schemes.


---

## Body

## 1.  Introduction

One of the most important and usual problems in numerical analysis is finding the solutions of a nonlinear equation:(1)f(x)=0,
where f:ℝ→ℝ is a Cr function, with r≥1. To approximate the solutions of these equations, iterative methods can be used. There are many iterative methods with different properties but the most commonly used is Newton’s iterative method:
(2)Nf(x)=x-f(x)f′(x).This method and its variants have been studied by many authors since it was proposed by Newton in 1669. It is well known that under certain assumptions related to the starting pointx0 and to the function f the method provides a sequence {xn}n∈ℕ that converges quadratically to a solution of (1).The classical third-order schemes, such as Halley or Chebyshev methods, evaluate second-order Fréchet derivatives. These evaluations are very time consuming for systems of equations. Indeed, let us observe that, for a nonlinear system ofm equations and m unknowns, the second Fréchet derivative has m3 entries. In particular, these methods are hardly used in practice. For that reason, we are interested in the study of methods that increase the order but evaluating only first-order Fréchet derivatives. The methods consist of two (or more) steps of the Newton method having the same derivative, other main advantage of these methods relays on the fact that if we consider a system of equations only one LU decomposition is necessary in each iteration. Because of these two properties the schemes are considered a real alternative to the classical Newton method.On the other hand, we can find a rigorous and useful procedure to find the best scheme in families of Newton-type methods with frozen derivatives in [1]. For most of the cases, the most efficient candidate of the family is the two-step iterative method. We will study all this family but with special attention to the two-step scheme.In this paper, our main purpose is to study the dynamics of the discrete system defined by the methods but introducing a damping factorλ∈(0,1]. We are interested to search chaos or sensitive dependence on initial conditions for this discrete dynamical system. In [2], Hurley and Martin showed that the classical Newton iterative method exhibits chaos for a large class of functions (see also [3]). The introduction of the damping factor not only reduces the order of convergence but also reduces the chaos and the bifurcations as we will see in Sections 3 and 4. In particular, we can utilize these schemes as starting points for the classical Newton schemes. We conclude this paper by comparing the damped method with the original one and the successive damped high-order methods that come from using more Newton’s steps.The study of the dynamics of the iterative methods attracts the attention of many groups [4–8].The paper is organized as follows. In Section2 we introduce our new scheme and present the associated scaling theorem. The scaling theorem allows up to suitable change of coordinates, to reduce the study of the dynamics of iterations of general maps, to the study of specific families of iterations of simpler maps. The dynamics for polynomials of degree-two and three, having chaotic dynamics in some cases, are presented in Sections 3 and 4, respectively. In these sections, we observe that the inclusion of the damping factor reduces the bad zone of convergence. In Section 5 we give the main conclusions drawn from the study and we summarize the benefits to include the damping factor. Finally, we propose the use of damped methods in order to find good starting points for the original methods.


## 2. A Damped Newton-Type Iterative Method

Our first goal is to analyze the dynamics of a modification of the following third-order iterative root-finding method [9]:
(3)yn=xn-f(xn)f′(xn),xn+1=yn-f(yn)f′(xn).This iterative root-finding algorithm is defined by the following iterative function:(4)Mf(x)=Nf(x)-f(Nf(x))f′(x),
where Nf(x)=x-uf(x) and uf(x)=f(x)/f′(x). In other words, xn+1=Mf(xn). The dynamics of this method were studied in [10]. Now, we introduce a damping factor λ∈(0,1] and we analyze its influence on the dynamics in the iterative method (4). By introducing the damping factor the root-finding algorithm has the following form:
(5)yn=xn-λf(xn)f′(xn),xn+1=yn-λf(yn)f′(xn).Thus the following iterative function describes the root-finding algorithm:(6)Mλ,f(x)=Nλ,f(x)-λf(Nλ,f(x))f′(x),0<λ≤1,
where Nλ,f(x)=x-λf(x)/f′(x).Notice that it is easy to proof that the roots of the functionf are fixed points of Mλ,f. Moreover, we have that
(7)Mλ,f′(x)=1-λf′(x)2-f(x)f′′(x)f′(x)2-λ((f′(x-λf(x)f′(x))×(1-λf′(x)2-f(x)f′′(x)f′(x)2)×(1-λf′(x)2-f(x)f′′(x)f′(x)2)f′(x)×(1-λf′(x)2-f(x)f′′(x)f′(x)2)-f(x-λf(x)f′(x))f′′(x))×(1-λf′(x)2-f(x)f′′(x)f′(x)2)×(f′(x)2)-1).In particular, ifα is a simple root of f, that is, f(α)=0 and f′(α)≠0, then Mλ,f′(α)=(1-λ)2. Thus every simple root of f is an attracting point of Mλ,f and for λ=1 a superattracting fixed point. If β is a multiple root of multiplicity m of f, then it is an attracting fixed point for every value of λ. There are fixed points of Mλ,f(x) different from the roots. These points are called extraneous fixed points. In [10], Amat et al. showed that this method for λ=1 (without damping factor) presents chaos and bifurcations when it is applied to a one-parameter family of cubic polynomials. Chaos behavior are related to the existence of points x* such that f′(x*)=0 and f(x*)≠0.When we apply the iterative methodMλ,f to a polynomial, we may have some problems, since we obtain a rational map, say Mλ,p(x)=P(x)/Q(x), where P and Q, are polynomials, that we may suppose without common factors. The difficulty arises at those points where the evaluation of numerator is nonzero and the denominator is zero, one such points correspond to the poles of the iterative method.In order to study the dynamics ofMλ,f by means of graphical analysis we consider it as a map M~λ,f on  [0,1[. For this, let G:ℝ→]0,1[   be given by G(x)=(1/π)arctan(x)+1/2. This map is an homeomorphism from ℝ into  ]0,1[. Define the maps M~λ,f:]0,1[→]0,1[  by M~λ,f=(G∘Mλ,f∘G-1)(x), where Mλ,f is the iterative root-finding method introduced above for a map f:ℝ→ℝ. We may extend M~λ,f to maps from [0,1] into itself. We use the same notation for this extension. Note that the extended function has fixed points at x=0 and at x=1 and that these fixed points are repelling.Now we have the following useful result.Theorem 1 (the scaling theorem).
Letf(x) be an analytic function, and let T(x)=αx+β, with α≠0, be an affine map. Let g(x)=(f∘T)(x). Then T∘Mλ,g∘T-1(x)=Mλ,f(x); that is, Mλ,g and Mλ,f are affine conjugated by T.Proof.
We have(8)Mλ,g(T-1(x))=T-1(x)-λug(T-1(x))-λg(T-1(x)-λug(T-1(x)))g′(T-1(x)).
On the other hand, since g∘T-1(x)=f(x) and (g∘T-1)′(x)=(1/α)g′(T-1(x)), then g′(T-1(x))=α(g∘T-1)′(x)=αf′(x), and by an easy induction process it follows that g(k)(T-1(x))=αkf(k)(x). Hence, ug(T-1(x))=(1/α)uf(x).
Substituting these quantities inMλ,g(T-1(x)) we obtain
(9)T∘Mλ,g∘T-1(x)=T(Mλ,g(T-1(x)))=αMλ,g(T-1(x))+β=αT-1(x)-αλug(T-1(x))-αλg(T-1(x)-λug(T-1(x)))g′(T-1(x))+β=αT-1(x)-λuf(x)-λg(T-1(x)-(λ/α)uf(x))f′(x)+β=x-λuf(x)-λg(T-1(x)-(λ/α)uf(x))f′(x).
Finally, by a comparison of Taylor series expansions off and g, we obtain
(10)g(T-1(x)-λαuf(x))=g(T-1(x))-λαg′(T-1(x)uf(x))⋯=f(x)-λαf′(x)1αuf(x)+⋯=f(x-λuf(x)).
Therefore,T∘Mλ,g∘T-1(x)=Mλ,f(x).
This ends the proof.The theorem remains valid for any nonzero constantc such that g(x)=c(f∘T)(x).The Scaling Theorem allows up to suitable change of coordinates, to reduce the study of the dynamics of iterationsMλ,f, to the study of specific families of iterations of simpler maps. For example, each quadratic polynomial f(x)=ax2+bx+c, with a≠0, that we suppose that is monic, by an affine change of variables reduces to one of the following polynomials: (i)
f-(x)=x2-1,(ii)
f+(x)=x2+1,(iii)
f0(x)=x2,depending on the number of real roots off(x)=0 (two, one (double), or not real roots). Therefore the study of the dynamics of Mλ,f, when it is applied to a quadratic polynomial, reduces to the study of the dynamics of Mλ,fs where s=+,0,-, up to affine change of variables. On the other hand, the study of the dynamics of the iterative method M~λ,f reduces to the study of the dynamics of the interval map M~λ,fs. Similarly, any cubic polynomial reduces to one of the simplest cubic polynomials:(I)
f-(x)=x3-x,(II)
f+(x)=x3+x,(III)
f0(x)=x3,(IV)
fγ(x)=x3+γx+1.The last one is an appropriate rescaling that putsMλ,f inside the conjugacy class.


## 3. Quadratic Polynomials

Following the analysis of Section2, we have to study three cases.Case 1 (f0(x)=x2).
In this case form (6) we have
(11)Mλ,f0(x)=-18x(-2+λ)(4+(-2+λ)λ).
This function for λ∈(0,1] is a linear contraction. The unique fixed point are x=0, which is a global attractor, but not super-attracting. Therefore, its dynamics is trivial.Case 2 (f-(x)=x2-1).
Forf-(x)=x2-1 from (6) and (7) we have that
(12)Mλ,f-(x)=-({11}(λ3+x4(-2+λ)(4+(-2+λ)λ)-2x2λ(4+(-2+λ)λ))×(8x3)-1{11}{(λ3+x4(-2+λ)(4+(-2+λ)λ)}),Mλ,f-′(x)=({12}-(-3λ3+x4(-2+λ)(4+(-2+λ)λ)+2x2λ(4+(-2+λ)λ))×(8x4)-1{12}).
Now the fixed points of Mλ,f-(x) are x1,2=±1 and x3,4=±λ/8-4λ+λ2. The points x1,2 are the roots of f-, and we have that Mλ,f-′(x1,2)=(λ-1)2; thus x1,2 are attracting fixed points for λ∈(0,1), and superattracting for λ=1. On the other hand, we have that Mλ,f-′(x3,4)=-15+16/λ+6λ-λ2. Thus, the extraneous fixed points x3,4 are repelling. Note that Mλ,f-(x) has a vertical asymptote at x=0.Letλ=1 and I=[p1,p2] be the interval determined by the repelling fixed points p1=G(x3)=0.36614… and p2=G(x4)=0.63386… of M~1.0,f-. Figure 1 shows M~1.0,f- and Figure 2 shows a zoom of the restriction of the function to the interval I.Figure 1
M
~
1.0
,
f
- as a circle map.Figure 2
M
~
1.0
,
f
- restricted to the interval I.It is clear thatM~1.0,f- restricted to the interval I has an invariant Cantor set Δ- of zero Lebesgue measure of nonescaping points; that is, Δ- is the set of points whose orbits remain in the interval I under iteration by M~1.0,f-. In other words, these points are not attracted to one of the superattracting fixed points of M~1.0,f- (note that when λ=1 the fixed points are superattracting).From the above analysis, we have that the orbit of any pointx∈[0,1]∖(Δ-∪p1,p2) is attracted to one of the superattracting fixed points of M~1.0,f-. Consequently, the orbit of any point in ℝ∖(G-1(Δ-)∪{x3,x4}) is attracted to one of the fixed points of M1.0,f-.Thus we can define the “bad zone” asBZ=Δ-∪{p1,p2} since if x∈BZ, then it is not attracted by any of the attracting points of M~λ,f-.Lemma 2.
The “bad zone” of the damping two-step Newton-like method defined in (6) applied to quadratic polynomials with two different roots decreases with the damping parameter λ.Proof.
We begin by calculating(13)p1=G(x3)=12-arctan[λ/8+(-4+λ)λ]π,p2=G(x4)=12+arctan[λ/8+(-4+λ)λ]π.
So we have that(14)Iλ=[12-arctan[λ/8+(-4+λ)λ]π,12+arctan[λ/8+(-4+λ)λ]π].
ThusI is an interval centered in 0.5 and width 2(arctan(λ/8+(-4+λ)λ)/π)=2a. It is easy to see that Δ- decreases when a decreases. Taking into account that the functions (λ/8+(-4+λ)λ)(x) and arctan(x) are increasing functions, it follows that a decreases as λ so with smaller λ we have smaller BZ.Thus we have seen analytically and graphically, in Figures3, 4, 5, and 6, that the size of (Δ-∪{p1,p2}) decreases with the damping factor λ and as a consequence we can state that the chaotic zone decreases with λ.Figure 3
Graphics ofM~λ,f- with λ=0.75, where the BZ interval is I0.75=[0.401996⋯,0.598004⋯].Figure 4
Graphics ofM~λ,f- with λ=0.5, where the BZ interval is I0.5=[0.437167⋯,0.562833⋯].Figure 5
Graphics ofM~λ,f- with λ=0.25, where the BZ interval is I0.25=[0.470144⋯,0.529856⋯].Figure 6
Graphics ofM~λ,f- with λ=0.01, where the BZ interval is I0.01=[0.498872⋯,0.501128⋯].Case 3 (f+(x)=x2+1).
In this case, the equationf+ has no real roots, thus Mλ,f+(x) has not real fixed points, and its dynamics is chaotic. Figures 7 and 8 illustrate this behavior.Figure 7
Graphics ofM1.0,f+.Figure 8
Graphics ofM~1.0,f+ as a circle map.


## 4. Cubic Polynomials

In this section we consider cubic polynomials. As we have seen in Section2, by an affine change of coordinates, every cubic polynomial f reduces to one of the simplest f0,f-,f+ or to a member of the one-parameter family of cubic polynomials fγ. Therefore, we analyze the dynamics of these simpler cubic polynomials.Case 4 (f+(x)=x3+x).
In this case,f has only one real root at x=0, and the method (6) has the following form:
(15)Mf+,λ=x-(x+x3)λ1+3x2-(λ(x-(x+x3)λ1+3x2+(x-(x+x3)λ1+3x2)3)×(1+3x2)-1{(x-(x+x3)λ1+3x2+(x-(x+x3)λ1+3x2)3)}).Sincef+′(x)=1+3x2>0 for all x, it follows that f+ has no critical points; hence, Mf+,λ(x) is a global homeomorphism from ℝ into itself and its dynamics is trivial.Case 5 (f-(x)=x3-x).
In this casef has 3 real roots, x=0, x=1 and x=-1. Mf-,λ(x) is given by (6)
(16)Mf-,λ(x)=x-x(-1+x2)λ-1+3x2-(λ(-x+x(-1+x2)λ-1+3x2(x-x(-1+x2)λ-1+3x2)3(x-x(-1+x2)λ-1+3x2)3+(x-x(-1+x2)λ-1+3x2)3)(-1+3x2)-1).
Notice that Mf-,λ(x) has two asymptotes at the points a1=3/3 and a2=-3/3. We have that when x→a1, then Mf-,λ(x)→-∞, and when x→a2, then Mf-,λ(x)→∞. If we now calculate the fixed points of Mf-,λ(x), there exist 9 fixed points which are the three roots of f(x1=-1,x2=0,x3=1) and the following extraneous fixed points:(17)
x
4
=
-
3
9
-
3
λ
+
λ
2
-
λ
2
(
9
-
3
λ
+
λ
2
)
+
λ
2
2
(
9
-
3
λ
+
λ
2
)
-
λ
9
-
2
λ
+
λ
2
2
(
9
-
3
λ
+
λ
2
)
,
x
5
=
3
9
-
3
λ
+
λ
2
-
λ
2
(
9
-
3
λ
+
λ
2
)
+
λ
2
2
(
9
-
3
λ
+
λ
2
)
-
λ
9
-
2
λ
+
λ
2
2
(
9
-
3
λ
+
λ
2
)
,
x
6
=
-
3
9
-
3
λ
+
λ
2
-
λ
2
(
9
-
3
λ
+
λ
2
)
+
λ
2
2
(
9
-
3
λ
+
λ
2
)
+
λ
9
-
2
λ
+
λ
2
2
(
9
-
3
λ
+
λ
2
)
,
x
7
=
3
9
-
3
λ
+
λ
2
-
λ
2
(
9
-
3
λ
+
λ
2
)
+
λ
2
2
(
9
-
3
λ
+
λ
2
)
+
λ
9
-
2
λ
+
λ
2
2
(
9
-
3
λ
+
λ
2
)
,wherex8=-(-2+λ)/(-6+λ) and x9=(-2+λ)/(-6+λ). Evaluating all these points in Mf-,λ′ (7), we obtain that the first 3 ones (the roots of f) are attracting fixed points for every λ≠1 and superattracting for λ=1. The extraneous fixed points are repelling ones since Mf-,λ′(x1,2,3)=(-1+λ)2:
(18)Mf-,λ′(x4,5)=-(9(-3+9+(-2+λ)λ)+λ(47+λ(-13+5λ+39+(-2+λ)λ+39+(-2+λ)λ)))(4λ)-1,Mf-,λ′(x6,7)=(9(3+9+(-2+λ)λ)+λ(+39+(-2+λ)λ-47+λ(13-5λ39+(-2+λ)λ+39+(-2+λ)λ)))(4λ)-1,Mf-,λ′(x8,9)=13+(-8+λ)λ.
In particular, the dynamics is trivial.Case 6 (f0(x)=x3).
The functionf0 only has one triple root at x=0. We have that (6) has the following form:
(19)Mf0,λ=181x(-3+λ)(-27+(-3+λ)2λ),
which is a linear contraction for every value of λ∈(0,1]. The only fixed point is attracting, but not superattracting and the dynamics of Mf0,λ is trivial.Case 7 (fγ(x)=x3+γx+1).
We have from (6) that
(20)Mfγ,λ(x)=x-(1+x3+xγ)λ3x2+γ-({∑21}λ(+(x-(1+x3+xγ)λ3x2+γ)31+γ(x-(1+x3+xγ)λ3x2+γ)+(x-(1+x3+xγ)λ3x2+γ)3)+(x-(1+x3+xγ)λ3x2+γ)3×(3x2+γ)-1{∑11}).
We are going to analyze in this section the dynamics of Mfγ,λ(x) depending on the two parameters γ and λ. Our main purpose is to compare the results by fixing the parameter γ for different values of the damping parameter λ and to study how it changes the dynamics.We begin by studying the caseγ<0. In this case, our function fγ has two critical points: γ+,-=±-γ/3. Let be γ*=-3/43≈-1.88988. Notice that fγ* has a double root at the positive critical point γ+. Hence, this value of the parameter will be very significant in the study of the dynamics.We have three different possibilities.(i)
Ifγ<γ*, the polynomial fγ has three real roots.(ii)
Ifγ=γ*, the polynomial fγ has one positive double real root and a simple one which is negative.(iii)
Ifγ>γ*, the polynomial fγ has only one real root.Forγ<γ* the iterative method Mfγ,λ(x) has two vertical asymptotes. Mfγ,λ(x) has 7 fixed points, the 3 real roots of the polynomial (attracting fixed points), and the extraneous fixed points (repelling). See Figure 9 as an example. As we can observe in Figures 10, and 11 if the damping factor decreases, then extraneous fixed points tend to be closer to the asymptotes.Figure 9
M
f
-
3
,
λ for λ=0.9.Figure 10
M
f
-
3
,
λ for λ=0.3.Figure 11
M
f
-
3
,
λ for λ=0.1.Forγ*≤γ<0 the iterative method Mfγ,λ(x) has two vertical asymptotes at γ- and γ+, as we can see in Figure 12. Notice that limx→γ-±Mfγ,0(x)=∞ and limx→γ+±Mfγ,0(x)=∞. Mfγ,λ(x) has 3 fixed points, the one which corresponds to the real solution of the polynomial fγ is attracting and two repelling extraneous fixed points. Again we obtain that when the damping factor decreases the chaotic zone also decreases.Figure 12
M
f
-
1
,
λ for λ=0.9.Now we are going to consider the simplest case which corresponds toγ=0, and we have
(21)Mf0,λ(x)=({(81x8)-1}(3x3(-3+λ)λ3+λ4+3x6λ(-18+9λ-6λ2+λ3)+x9(81-54λ+27λ2-9λ3+λ4))×(81x8)-1).
This map has one attracting point at x1=-1 which corresponds to the root of f0. Moreover it has another two extraneous fixed points which are the real solutions of the equation:
(22)λ3+(-9λ2+2λ3)x3+(-54+27λ-9λ2+λ3)x6=0.
As we see in Figure 13 both extraneous fixed points are repelling.Figure 13
M
f
0
,
λ for λ=0.9.Now if we focus our attention on the damping factor, we obtain that whenλ decreases, the extraneous fixed points tend to be closer to the asymptote x=0. This behavior can be observed in Figures 14 and 15. Notice that x=0 is the critical point of f0.Figure 14
M
f
0
,
λ for λ=0.7.Figure 15
M
f
0
,
λ for λ=0.1.The last study is related withγ>0. Notice that for, every value of γ≠0, Mfγ,λ presents a maximum which increases when γ decreases. Moreover there exists a value γλ that depends on the value of the damping factor, such that, for each γ>γλ, Mfγ,λ has only one fixed point (the root of the function) and the dynamics is trivial. In Table 1, it shows the different approximations of γλ for some values of λ. Figure 16 illustrates this case.Table 1
Approximations ofγλ for some values of  λ.
λ
γ
λ
0.01
0.00795
0.1
0.081
0.2
0.1657
0.3
0.254
0.4
0.346
0.5
0.442
0.6
0.543
0.7
0.649
0.8
0.762
0.9
0.881
1.0
1.00768Figure 16
M
f
γ
,
λ for λ=0.5 and γ=γ0.5=0.442.Whenγ=γλ, Mfγ,1 presents another fixed point which is a saddle node (as Amat et al. showed in [10]) and when the parameter γ decreases, it appears bifurcations. If we now see Figures 17, 18, 19, and 20, it is clear that the problems decrease with λ; even for small values (λ<0.2) they seem they disappear.Figure 17
Feigembaun diagram forλ=1.0.Figure 18
Feigembaun diagram forλ=0.8.Figure 19
Feigembaun diagram forλ=0.5.Figure 20
Feigembaun diagram forλ=0.3.Finally, we conclude with the following conjecture:ifλ=n/2k withn,k∈ℕ, thenMfγ,λ  has only three fixed points.


## 5. Concluding Remarks

In this work we have analyzed the dynamics of a new damped third-order Newton-like method. We have stated the following conclusions drawn from the study(i)
The connected component of the basin of attraction increases when the damping factor decreases.(ii)
The sizes of the chaotic and the bifurcation zones decrease when the damping factor decreases.(iii)
The nonconvergence zone decreases when the damping factor decreases.In addition, we have performed a similar study including more Newton’s steps. The conclusions remain valid. Figures21, 22, 23, and 24 show examples of the behavior with more Newton’s steps. Therefore, we can propose the use of damped methods in order to find good starting points for the original methods. We would like to analyze these hybrid methods in a forthcoming paper. We are also interested to analyze the situation of nonfixed damping factors.Figure 21
M
f
-
,
λ for λ=1.0 and f-(x)=x3-x with three Newton steps.Figure 22
M
f
-
,
λ for λ=0.25 and f-(x)=x3-x with three Newton steps.Figure 23
M
~
f
+
,
λ for λ=1.0 and f+(x)=x3+x with three Newton steps.Figure 24
M
~
f
+
,
λ for λ=0.25 and f+(x)=x3+x with three Newton steps.



---

*Source: 726701-2013-07-21.xml*