# On the Complex Dynamics of Continued and Discrete Cauchy’s Method

Authors: Mohamed Lamine Sahari
Journal: Journal of Nonlinear Dynamics
 (2015)

---

## Abstract

Letp be a complex polynomial of fixed degree n. In this paper we show that Cauchy’s method may fail to find all zeros of p for any initial guess z
0 lying in the complex plane and we propose several ways to find all zeros of a given polynomial using scaled Cauchy’s methods.


---

## Body

## 1. Introduction

For a large class of computational problems a zero of a polynomialp in the complex plane C has to be found. Cauchy’s method [1] is an interesting candidate for the numerical solution. Let z
0
∈
C be a starting point for a zero of p. We set(1)
z
k
+
1
=
g
λ
z
k
=
z
k
-
λ
p
z
k
,
λ
∈
R
.If α is a simple root of p
(
z
) and λ is selected in such way that the following criterion is satisfied,(2)
1
-
λ
p
′
α
<
1
,the Cauchy method has the following properties:(a)
αis an attractive fixed point of a map g
λ
:
C
¯
→
C
¯ (C
¯
=
C
∪
∞).
(b)
Forz
0 sufficiently close to α, the sequence of iterates,(3)
z
k
=
g
λ
k
z
0
=
g
λ
g
λ
k
-
1
z
0
,will converge to the root α and(4)
z
k
+
1
-
α
z
k
-
α
=
1
-
λ
p
′
α
; that is, the sequence (3) converges linearly.However, someone may wonder about the basin of attraction(5)
A
α
=
z
∈
C
:
g
λ
k
z
⟶
α
,
k
⟶
∞
,of a root α of p  and the relationship with the vector field and trajectories of the differential system:(6)
d
z
t
d
t
=
-
σ
p
z
t
,
t
≥
0
,
σ
=
±
1
,
z
0
=
z
0
,known as the continuous Cauchy’s method. It is assumed that discrete Cauchy’s method (1) may be interpreted as Euler step for the differential equation (6).


## 2. Examples and Graphics

Let us consider a famous example given by Cayley (1879, [2]). Let(7)
p
z
=
z
3
-
1
,for α
1
=
1, α
2
=
-
1
/
2
+
i
1
/
2
3, and α
3
=
-
1
/
2
-
i
1
/
2
3, the three roots of p
(
z
), and color a point z
0
∈
C blue if {
z
k
}
k
=
0
k
=
∞ converges to α
1, color it green if {
z
k
}
k
=
0
k
=
∞ converges to α
2, and color it red if {
z
k
}
k
=
0
k
=
∞ converges to α
3
. Any remaining point gets coloured white (e.g., if z
k
↛
α
1,2
,
3). Figure 1 shows basins of attraction for (7) with a value of λ, respectively, taken -
0.1 and 0.1 for the region [
-
3.0,3.0
]
×
[
-
5.0,5.0
] in Figure 1(a) and [
-
5.0,5.0
]
×
[
-
3.0,3.0
] in Figure 1(b). Figure 2 indicates corresponding basins of attraction for the gradient method with λ
=
-
0.01 and λ
=
0.01 for the region [
-
2.1,2.1
]
×
[
9.5,14.5
] in Figure 2(a) and [
-
15.0
,
-
10.0
]
×
[
-
1.5,1.5
] in Figure 2(b). Note that the boundary of the basins of attraction for each root of p exhibits a fractal structure (see Figures 1–5). These figures show also the role played by the parameter λ; this parameter is used on one hand to enlarge the domains in the basins of attraction which contain the roots of the polynomial and on the other hand to ensure the convergence of the method. The question which arises naturally is of knowing what happens when λ
→
0 in (1). The answer can be given by differential system (6). Denote Δ
t
=
λ
σ, where σ
=
sign
⁡
(
λ
)
. To see this, let(8)
z
k
+
1
=
z
k
-
σ
Δ
t
p
z
k
. Rearranging yields(9)
z
k
+
1
-
z
k
Δ
t
=
-
σ
p
z
k
. Finally, letting Δ
t
→
0
(
⇒
λ
→
0
) we have(10)
d
z
t
d
t
=
-
σ
p
z
t
.Figure 1
Basins of attraction forp
(
z
)
=
z
3
-
1 with (a) λ
=
-
0.1 and z
∈
[
-
3.00,3.00
]
×
[
-
3.00,3.00
]
i. (b) λ
=
0.1 and z
∈
[
-
5.00,5.00
]
×
[
-
3.00,3.00
]
i.
(a)
(b)Figure 2
Basins of attraction forp
(
z
)
=
z
3
-
1 with (a) λ
=
-
0.01
. (b) λ
=
0.01.
(a)
(b)Figure 3
Vector field for continuous Cauchy’s method whenp
(
z
)
=
z
3
-
1, with σ
=
-
1 in (a) and σ
=
1 in (b).
(a)
(b)Figure 4
(a) Basins of attraction forp
(
z
)
=
z
3
-
1 using (20) and λ
=
0.10. (b) Vector field when p
(
z
)
=
z
3
-
1 (z
∈
[
-
5.00,5.00
]
×
[
-
5.00,5.00
]
i).
(a)
(b)Figure 5
(a) Basins of attraction forp
(
z
)
=
z
3
-
1 using (26) and λ
=
0.10. (b) Vector field when p
(
z
)
=
z
3
-
1 (z
∈
[
-
3.00,3.00
]
×
[
-
3.00,3.00
]
i).
(a)
(b)We can see in Figure3(a) that the fixed point α
1 is attractive while α
2,3 are repulsive; in Figure 3(b), the fixed point α
1 is repulsive while α
2,3 is attractive. It is clear that this qualitative behavior change is controlled by the sign of the σ parameter.


## 3. Cauchy’s Method as a Dynamical System

A critical point of a holomorphic map is usually a point, where the derivative vanishes. In particular, a critical points ofg
λ
=
i
d
-
λ
p are solutions of g
λ
′
(
z
)
=
1
-
λ
p
′
(
z
)
=
0. Thus if p is degree n, then g
λ admits at the most n
-
1 different critical points.Definition 1 (immediate basins).
Letξ be an attracting fixed point of g
λ. The connected component A
∗
(
ξ
) of the basins of attraction A
(
ξ
) that contains ξ is called its immediate basins.The following theorem is the main result in the study of basins.Theorem 2 (Fatou, [3]).
Ifξ is an attracting fixed point of g
λ, then the immediate basins A
∗
(
ξ
) contain at least one critical point.
We deduce directly from the last theorem that the number of attractive fixed points (attractive roots ofp) of Cauchy’s method is at most equal to the degree of p. Thus the Cauchy’s method cannot find all roots of the complex polynomial p
(
z
). In the subsequent two results we will explain this fact.Theorem 3 (case of discrete Cauchy’s method).
Ifα is a root of p
(
z
) with R
e
(
p
′
(
α
)
)
>
0, then Cauchy’s method converges towards this root for some λ
>
0.Proof.
We have1
-
λ
p
′
(
α
)
2
=
p
′
(
α
)
2
λ
2
-
2
λ
R
e
(
p
′
(
α
)
)
+
1 (where Re
⁡
(
z
) denotes the real part of complex number z) and, for 0
<
λ
<
2
R
e
(
p
′
(
α
)
)
/
p
′
(
α
)
2, condition (2) is obtained.Theorem 4 (case of continuous Cauchy’s method).
Ifz
(
t
) satisfies (6) for all t
>
0 with σ
=
1 and α is the root of p
(
z
) when R
e
(
p
′
(
α
)
)
>
0, then(11)
lim
t
→
∞
⁡
z
t
=
α
, for some z
0 in C.Proof.
Let the monic with degreen
(12)
p
z
=
z
n
+
a
n
z
n
-
1
+
a
n
-
1
z
n
-
2
+
⋯
+
a
1
, with n simple roots α
1
,
α
2
,
…
,
α
n and we have(13)
1
p
z
=
∑
i
=
1
n
1
z
-
α
i
1
∏
j
=
1
,
j
≠
i
n
α
i
-
α
j
=
∑
i
=
1
n
1
z
-
α
i
1
p
′
α
i
,
(14)
∫
z
0
z
d
z
p
z
=
∑
i
=
1
n
1
p
′
α
i
ln
⁡
z
-
α
i
-
ln
⁡
z
0
-
α
i
.Assume that z
(
t
) solves (6). Rearranging terms yields(15)
d
z
p
z
=
-
d
t
,and integrating with respect to t and in accordance with (14)(16)
∑
i
=
1
n
1
p
′
α
i
ln
⁡
z
-
α
i
=
ln
⁡
∏
i
=
1
i
=
n
z
-
α
i
1
/
p
′
α
i
=
-
t
+
ln
⁡
C
. Finally, exponentiation shows that(17)
∏
i
=
1
i
=
n
z
-
α
i
1
/
p
′
α
i
=
C
e
-
t
,
C
∈
C
.


## 4. Computer Experiments with Scaled Cauchy’s Methods

To obtain the condition (2), we used the scaled complex of (1); that is,(18)
z
k
+
1
=
G
λ
z
k
=
z
k
-
λ
ρ
z
k
p
z
k
,
λ
>
0
,
ρ
:
C
⟶
C
.The continuous form is given by(19)
d
z
t
d
t
=
-
ρ
z
t
p
z
t
,
t
≥
0
,
z
0
=
z
0
.Subsequently, we have shown the basins of attraction and vector field according to three different choices of the function ρ
.Case 1 (ρ
(
z
)
=
sign
⁡
Re
⁡
p
′
z).
The functionρ
:
z
→
sign
⁡
(
R
e
(
p
′
(
z
)
)
) is not holomorphic and a similar analysis of (2) of Section 1 is not possible in C; then we consider the dynamics (18) with p
(
z
)
=
z
3
-
1 in R
2. Consider(20)
G
λ
≔
x
k
+
1
=
x
k
-
σ
x
k
,
y
k
x
k
3
-
3
x
k
y
k
2
-
1
,
y
k
+
1
=
y
k
-
σ
x
k
,
y
k
3
x
k
2
y
k
-
y
k
3
,with(21)
σ
x
,
y
=
λ
if
x
2
-
y
2
≥
0
,
-
λ
if
x
2
-
y
2
<
0
. The Jacobian of the transformation G
λ is expressed by(22)
J
G
λ
x
,
y
=
J
11
J
12
J
21
J
22
, with(23)
J
11
=
1
-
σ
x
,
y
3
x
2
-
3
y
2
,
J
12
=
6
σ
x
,
y
x
y
,
J
21
=
1
-
σ
x
,
y
3
x
2
-
3
y
2
,
J
22
=
-
6
σ
x
,
y
x
y
. The eigenvalues of the matrix J
G
λ
(
x
,
y
) are β
1 and β
2 and are given by(24)
β
1
x
,
y
=
1
-
3
σ
x
,
y
x
2
+
3
λ
y
k
2
+
i
6
σ
x
,
y
x
y
,
β
2
x
,
y
=
1
-
3
σ
x
,
y
x
2
+
3
λ
y
k
2
-
i
6
σ
x
,
y
x
y
, and in the singular points α
1, α
2, and α
3, we have (25)
β
1
α
1
=
β
2
α
1
=
1
-
3
λ
,
β
1
α
2
=
β
1
α
3
=
1
-
3
2
λ
1
-
i
3
,
β
2
α
2
=
β
2
α
3
=
1
-
3
2
λ
1
+
i
3
,
β
1
α
1
=
β
2
α
1
<
1
if
λ
∈
0
,
2
3
,
β
1
α
2
=
β
2
α
2
=
β
1
α
3
=
β
2
α
3
<
1
if
λ
∈
0
,
1
3
.Thus the fixed point α
1 is attractive for λ
∈
(
0,2
/
3
), and then α
2
,
α
3 are attractive for λ
∈
(
0,1
/
3
). Figure 4(a) showed the basins of attraction of z
3
-
1 using (20) and λ
=
0.10, and Figure 4(b) represents the vectors field of (19).Case 2 (ρ
(
z
)
=
1
/
Re
⁡
(
p
′
(
z
)
)).
The dynamics (18) with p
(
z
)
=
z
3
-
1 can be formulated in R
2 as(26)
G
λ
≔
x
k
+
1
=
x
k
-
λ
x
k
3
-
3
x
k
y
k
2
-
1
3
x
k
2
-
y
k
2
,
y
k
+
1
=
y
k
-
λ
3
x
k
2
y
k
-
y
3
3
x
k
2
-
y
k
2
.The map G
λ has the following Jacobian(27)
J
G
λ
x
,
y
=
J
11
J
12
J
21
J
22
,with(28)
J
11
=
1
-
λ
3
x
2
-
3
y
2
3
x
2
-
y
2
+
2
λ
x
3
-
3
x
y
2
-
1
3
x
2
-
y
2
2
,
J
12
=
2
λ
x
y
x
2
-
y
2
-
2
λ
x
3
-
3
x
y
2
-
1
y
3
x
2
-
y
2
2
,
J
21
=
-
2
λ
x
y
x
2
-
y
2
+
2
λ
3
x
2
y
-
y
3
x
3
x
2
-
y
2
2
,
J
22
=
1
-
λ
3
x
2
-
3
y
2
3
x
2
-
y
2
-
2
λ
3
x
2
y
-
y
3
y
3
x
2
-
y
2
2
. In a similar way, the eigenvalues of the matrix J
G
λ
(
x
,
y
) are β
1
(
x
,
y
) and β
2
(
x
,
y
) at the singular points (29)
β
1
α
1
=
β
2
α
1
=
1
-
λ
,
β
1
α
2
=
β
1
α
3
=
1
-
λ
1
-
i
3
,
β
2
α
2
=
β
2
α
3
=
1
-
λ
1
+
i
3
,and thus we have(30)
β
1
α
1
=
β
2
α
1
<
1
if
λ
∈
0,2
,
β
1
α
2
=
β
2
α
2
=
β
1
α
3
=
β
2
α
3
<
1
if
λ
∈
0
,
1
2
.Case 3 (ρ
(
z
)
=
p
′
(
z
)
¯).
In this case(31)
G
λ
≔
x
k
=
x
-
3
λ
x
3
-
3
x
y
2
-
1
x
2
-
y
2
-
6
λ
3
x
2
y
-
y
3
x
y
,
y
k
=
y
-
3
λ
3
x
2
y
-
y
3
x
2
-
y
2
+
6
λ
x
3
-
3
x
y
2
-
1
x
y
.The Jacobian of the transformation G
λ is given by(32)
J
G
λ
x
,
y
=
J
11
J
12
J
21
J
22
,with(33)
J
11
=
1
-
3
λ
3
x
2
-
3
y
2
x
2
-
y
2
-
6
λ
x
3
-
3
x
y
2
-
1
x
-
36
λ
x
2
y
2
-
6
λ
3
x
2
y
-
y
3
y
,
J
12
=
18
λ
x
y
x
2
-
y
2
+
6
λ
x
3
-
3
x
y
2
-
1
y
-
6
λ
3
x
2
-
3
y
2
x
y
-
6
λ
3
x
2
y
-
y
3
x
,
J
21
=
-
18
λ
x
y
x
2
-
y
2
-
6
λ
3
x
2
y
-
y
3
x
+
6
λ
3
x
2
-
3
y
2
x
y
+
6
λ
x
3
-
3
x
y
2
-
1
y
,
J
22
=
1
-
3
λ
3
x
2
-
3
y
2
x
2
-
y
2
+
6
λ
3
x
2
y
-
y
3
y
-
36
λ
x
2
y
2
+
6
λ
x
3
-
3
x
y
2
-
1
x
. We notice that the transformation G
λ possesses the following fixed points: (34)
α
1
=
1,0
,
α
2
=
-
1
2
,
1
2
3
,
α
3
=
-
1
2
,
-
1
2
3
,
α
4
=
0,0
.At the pointsα
i, (
i
=
1,2
,
3
) the eigenvalues of J
G
λ
(
α
i
), (
i
=
1,2
,
3
) are equal to 1
-
9
λ; in this case the fixed points α
i
(
i
=
1,2
,
3
) are attractive in the interval (0, 2
/
9) and α
4
=
(
0,0
) is a indifferent fixed point (see Figure 6), since(35)
J
G
λ
α
4
=
1
0
0
1
. In the last case, the method,(36)
z
k
+
1
=
z
k
-
λ
p
z
k
p
′
z
k
¯
,
λ
>
0
,is the minimization process of the function given by(37)
ϕ
z
=
1
2
p
z
2
,called the discrete steepest descent method, since(38)
ϕ
′
z
=
p
z
p
′
z
¯
. Note that ϕ is locally convex and the local convergence of (19) is established (see [4]).Figure 6
(a) Basins of attraction forp
(
z
)
=
z
3
-
1 using (31) and λ
=
0.010. (b) Vector field when p
(
z
)
=
z
3
-
1 (z
∈
[
-
3.00,3.00
]
×
[
-
3.00,3.00
]
i).
(a)
(b)


## 5. The Best Choice ofλ-Parameter for Cauchy’s Method Leads to Newton’s Method

In order to have a condition more strict than (2), we seek holomorphic functions z
→
λ
ρ
(
z
) that yield the functional condition(39)
1
-
λ
ρ
α
p
′
α
=
0
,when p
(
α
)
=
0, and we can take(40)
ρ
z
=
1
p
′
z
,
λ
=
1
.Substituting (40) into (18), we get familiar Newton’s method; that is,(41)
z
k
+
1
=
z
k
-
p
z
k
p
′
z
k
.Numerical investigations into the basins of attraction of (41) and their boundary for the cubic polynomial p
(
z
)
=
z
3
-
1 have been carried out, and pictures of these sets are well known [5–8] (see Figure 7).Figure 7
Basins of attraction forz
3
-
1
=
0 using Newton’s method in the range [
-
2.00,2.00
]
×
[
-
2.00,2.00
].


## 6. Further Motivation

The method (1) is defined for any λ
∈
C. However, we will only be concerned with a small real parameter λ. The study of the λ-parameter plane allows the identification of the singular points other than the fixed points, which are the periodic points.Definition 5.
Letz
∗
∈
C
¯ satisfy g
λ
n
(
z
∗
)
=
z
∗ and g
λ
j
(
z
∗
)
≠
(
z
∗
) for j
=
1
,
…
,
n
-
1. Then z
∗ is a periodic point of period n
. The set,(42)
γ
z
∗
=
z
∗
,
g
λ
z
∗
,
…
,
g
λ
n
-
1
z
∗
, is called a periodic orbit or a cycle (of period n).Contrary to the fixed points ofg
λ which are roots of the polynomial p, the periodic points (and their orbit) are bad starting points for Cauchy’s method. In order to determine the existence of periodic points for (1), Theorem 2 indicates that it is necessary to follow the orbit of a critical point. The critical points of g
λ for λ
≠
0 when p
(
z
)
=
z
3
-
1 are χ
1
=
-
3
/
3
λ and χ
2
=
3
/
3
λ. In Figure 8(a) the global behaviour of the orbit of the critical point χ
1 is pictured. The horizontal and vertical axes correspond to the real and imaginary part of the complex parameter λ in the region [
-
1.2,1.20
]
×
[
-
1.20,1.20
]. The dark area in the picture is the subset of 600
×
600 parameter values at which the orbit is bounded but does not converge to the fixed point of g
λ. Figure 8(b) is an enlargement of the region [
-
1.10,1.30
]
×
[
-
1.20,1.20
] in the previous picture. In these figures, which were generated by examining the parameter values on 600
×
600 grid, the self-similarity (fractal structures) of regions in parameter plan is obvious. In an analogous way to Mandelbrot sets (see [9]) and only for the example p
(
z
)
=
z
3
-
1, the complex structure of the set exhibited in Figures 8-9 requires a more explicit study in forthcoming paper.Figure 8
Theλ-parameter plane of Cauchy’s method for critical point χ
1 = −3
/
3
λ.
(a)
(b)Figure 9
Theλ-parameter plane of Cauchy’s method for critical point χ
2
=
3
/
3
λ.
(a)
(b)



---

*Source: 162818-2015-10-08.xml*