A Note on the Downhill Method
Authors: Caldwell George C. 
Published: July 2002

In [1] Ward described the “downhill” method for determining roots of
f
(
z
) = 0, whqere
f
(
z
) is analytic. He denoted by
R
(
x, y
) and
J
(
x, y
) the real and imaginary parts, respectively, of
f
(
z
) and defined the surface
W
by (1)
W
(
x, y
) = |
R
(
x, y
) | + |
J
(
x, y
) |. He proved that
W
(
x, y
) is a minimum if and only if
x
+
iy
is a zero of ƒ(
z
), i.e.,
W
is a minimum if and only if
W
= 0.

The application of this method to the solution of
f
(
z
) = 0 is conceptually simple in view of the results in [1]. A starting value,
x
0
+
iy
0
, is chosen (at random, if it is desired so), and the corresponding
W
(
x
0
,
y
0
) is computed. If
W
(
x
0
,
y
0
) > 0, new values of
x
and
y
,
x
1
=
x
0
+
h
1
,
y
1
=
y
0
+
k
1
, are chosen, the
h
1
and
k
1
being subject only to the restriction that
W
(
x
1
,
y
1
) <
W
(
x
0
,
y
0
). Therefore, the actual problem consists of determining suitable values of
h
1
and
k
1
. It is the purpose of this note to indicate a method for the determination of these increments.

Let (2) ƒ(
z
) =
c
0
+ Σ
∞

j
=
p

c
j

(
z
-
z
)

j

be analytic in whatever region about
z
is being considered. It is assumed that
c
0
≠ 0, that

c
p

≠ 0, and the
p
≥ 1. The

c
j

are complex numbers. Although the final result will be given in rectangular coordinates, it is easier to work here with the polar form.

Accordingly, let

c
j

=
α

j

e
i
ψ
j
and
z
-
z
=
re

i
θ

. Then ƒ(
z
) =
α
0
e

i
ψ0

+ Σ
∞

j
=
p

α

j

r
j

e
i(jθ+ψ j)

, from which it follows that (3)
R
(
r
, θ) =
α
0
cos ψ
0
+ Σ
∞

j
=
p

α

j

r
j

cos (
jθ
+

ψ
j

), (4)
J
(
r, θ
) =
α
0
sin ψ
0
+ Σ
∞

j
=
p

α

j

r
j

sin (
jθ
+ ψ

j

), and (5)
W
(
r, θ
) = |
R
(
r, θ
) | + |
J
(
r, θ
) |. In particular,
W
(0, 0) =
α
0
{| cos ψ
0
| + | sin ψ
0
|}.

If the angle φ is defined by the equation (6) φ = 1/
p
(π + ψ
0
- ψ

p

), then
W
(δ, φ) ~ |
α
0
cos ψ
0
-
α

p

δ

p

cos ψ
0
| + |
α
0
sin ψ
0
-
α

p

δ

p

sin ψ
0
| = |
α
0
-
α

p

δ

p

| {| cos ψ
0
| + | sin ψ
0
|} <
W
(0, 0) for δ sufficiently small.

To put these results in rectangular form, suitable for computation, let
x
+
i
y
=
z
;

c
j

=

a
j

+

ib
j

, with

a
j

and

b
j

real; and
h
and
k
denote the increments in
x
and
y
, respectively. It follows from equation (6) that (7)
k
/
h
= tan [1/
p
(π + tan
-1
b
0
/
a
0
- tan
-1

b
p

/

a
p

)], and the following theorem has been proved.

THEOREM. If
c
0
≠ 0,
c
1
=
c
2
= … =

c
p-1

= 0,

c
p

≠ 0,
c

p
+1

, … are complex coefficients in (1), then
W
(
x
+
h
,
y
+
k
) <
W
(
x, y
, for
h
and
k
sufficiently small, if
h
and
k
satisfy (7).

As an example of the application of the theorem, consider the polynomial
f
(
z
) = 1 +
z
4
. This polynomial was discussed in [1], and it was pointed out that the usual starting technique failed. Let
x
0
+
iy
0
= 0. Then
x
1
=
h
1
and
y
1
=
k
1
, where (8)
k
1
=
h
1
tan 1/4 (π + 0 - 0) =
h
1
. Now,
W
(
x, y
) = |
x
4
- 6x
2
y
2
+
y
4
+ 1 | + | 4
xy
| · |
x
2
-
y
2
|, so that
W
(0, 0) = 1. Taking
h
1
=
k
1
= 1/2 yields
W
(1/2, 1/2) = 3/4 < 1. Therefore,
z
1
=
x
1
+
iy
1
= 1/2 (1 +
i
) is permissible.

For this example, the roots of
f
(
z
) = 0 are ± (√2/2) (1 ±
i
). Therefore, one could adjust
h
1
(and
k
1
) in accordance with (8) to obtain one of these roots. However, if we take
z
1
= 1/2 (1 +
i
), then
f
(
z
) = 3/4 + Σ
4

j
=1

c
j

(
z
-
z
1
), where
c
1
= -1 +
i
. Using (7) again,
k
2
=
h
2
tan (π + tan
-1
0/4 - tan
-1
1/-1) =
h
2
. This procedure is followed step by step until
W
(
x, y
) differs from zero by no more than an initially prescribed amount. In this example, it can be seen easily that
k
3
=
h
3
,
k
4
=
h
4
, …. The only problem remaining is that of choosing the

h
j

properly, and this is done readily with simple tests.

The downhill method has the following principal advantages for use on an automatic digital computer:

The method always converges (theoretically).

The method is definitive, i.e., it can be programmed for use in the general case.

On the other hand, there are some apparent disadvantages:

In order to utilize effectively the result of the theorem, it is necessary at each step to compute
c
0
and all of the other coefficients in (2) up through the first non-vanishing one.

Subroutines for tan
θ
and tan
-1
u
must be available.