A Note on the Downhill Method

ABSTRACT

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, x0 + iy0, is chosen (at random, if it is desired so), and the corresponding W (x0, y0) is computed. If W (x0, y0) > 0, new values of x and y, x1 = x0 + h1, y1 = y0 + k1, are chosen, the h1 and k1 being subject only to the restriction that W(x1, y1) < W (x0, y0). Therefore, the actual problem consists of determining suitable values of h1 and k1. It is the purpose of this note to indicate a method for the determination of these increments. Let (2) ƒ(z) = c0 + ∑∞j=p cj (z - z)j be analytic in whatever region about z is being considered. It is assumed that c0 ≠ 0, that cp ≠ 0, and the p ≥ 1. The cj 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 cj = &agr;j ei&psgr;j and z - z = rei&thgr;. Then ƒ(z) = &agr;0ei&psgr;0 + ∑∞j=p &agr;j rj ei(j&thgr;+&psgr; j), from which it follows that (3) R(r, &thgr;) = &agr;0 cos &psgr;0 + ∑∞j=p &agr;j rj cos (j&thgr; + &psgr;j), (4) J (r, &thgr;) = &agr;0 sin &psgr;0 + ∑∞j=p &agr;jrj sin (j&thgr; + &psgr;j), and (5) W(r, &thgr;) = | R(r, &thgr;) | + | J (r, &thgr;) |. In particular, W(0, 0) = &agr;0 {| cos &psgr;0 | + | sin &psgr;0 |}. If the angle @@@@ is defined by the equation (6) @@@@ = 1/p (&pgr; + &psgr;0 - &psgr;p), then W (&dgr;, @@@@) ∼ | &agr;0 cos &psgr;0 - &agr;p&dgr;p cos &psgr;0 | + | &agr;0 sin &psgr;0 - &agr;p&dgr;p sin &psgr;0 | = | &agr;0 - &agr;p&dgr;p | {| cos &psgr;0 | + | sin &psgr;0|} < W (0, 0) for &dgr; sufficiently small. To put these results in rectangular form, suitable for computation, let x + iy = z; cj = aj + ibj, with aj and bj 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 (&pgr; + tan-1 b0/a0 - tan -1bp/ap)], and the following theorem has been proved. THEOREM. If c0 ≠ 0, c1 = c2 = … = cp-1 = 0, cp ≠ 0, cp+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 + z4. This polynomial was discussed in [1], and it was pointed out that the usual starting technique failed. Let x0 + iy0 = 0. Then x1 = h1 and y1 = k1, where (8) k1 = h1 tan 1/4 (&pgr; + 0 - 0) = h1. Now, W (x, y) = | x4 - 6x2y2 + y4 + 1 | + | 4xy | · | x2 - y2 |, so that W (0, 0) = 1. Taking h1 = k1 = 1/2 yields W (1/2, 1/2) = 3/4 < 1. Therefore, z1 = x1 + iy1 = 1/2 (1 + i) is permissible. For this example, the roots of f(z) = 0 are ± (√2/2) (1 ± i). Therefore, one could adjust h1 (and k1) in accordance with (8) to obtain one of these roots. However, if we take z1 = 1/2 (1 + i), then f(z) = 3/4 + ∑4j=1 cj (z - z1), where c1 = -1 + i. Using (7) again, k2 = h2 tan (&pgr; + tan-1 0/4 - tan-1 1/-1) = h2. 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 k3 = h3, k4 = h4, …. The only problem remaining is that of choosing the hj 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 c0 and all of the other coefficients in (2) up through the first non-vanishing one. Subroutines for tan &thgr; and tan-1 u must be available.

REFERENCES

• 1: James A. Ward, The Down-Hill Method of Solving f(z) = 0, Journal of the ACM (JACM), v.4 n.2, p.148-150, April 1957 [doi>10.1145/320868.320873]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Performance, Theory