Thumbnail
Access Restriction
Subscribed

Author Caldwell, George C.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1959
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract In [1] Ward described the “downhill” method for determining roots of $\textit{f}(\textit{z})$ = 0, whqere $\textit{f}(\textit{z})$ is analytic. He denoted by $\textit{R}(\textit{x,$ y) and $\textit{J}(\textit{x,$ y) the real and imaginary parts, respectively, of $\textit{f}(\textit{z})$ and defined the surface $\textit{W}$ by (1) $\textit{W}(\textit{x,$ y) = | $\textit{R}(\textit{x,$ y) | + | $\textit{J}$ (x, y) |. He proved that $\textit{W}$ (x, y) is a minimum if and only if $\textit{x}$ + $\textit{iy}$ is a zero of $ƒ(\textit{z}),$ i.e., $\textit{W}$ is a minimum if and only if $\textit{W}$ = 0. The application of this method to the solution of $\textit{f}(\textit{z})$ = 0 is conceptually simple in view of the results in [1]. A starting value, $\textit{x}0$ + $\textit{iy}0,$ is chosen (at random, if it is desired so), and the corresponding $\textit{W}$ $(\textit{x}0,$ $\textit{y}0)$ is computed. If $\textit{W}$ $(\textit{x}0,$ $\textit{y}0)$ > 0, new values of $\textit{x}$ and $\textit{y},$ $\textit{x}1$ = $\textit{x}0$ + $\textit{h}1,$ $\textit{y}1$ = $\textit{y}0$ + $\textit{k}1,$ are chosen, the $\textit{h}1$ and $\textit{k}1$ being subject only to the restriction that $\textit{W}(\textit{x}1,$ $\textit{y}1)$ < $\textit{W}$ $(\textit{x}0,$ $\textit{y}0).$ Therefore, the actual problem consists of determining suitable values of $\textit{h}1$ and $\textit{k}1.$ It is the purpose of this note to indicate a method for the determination of these increments. Let (2) $ƒ(\textit{z})$ = $\textit{c}0$ + $∑∞\textit{j}=\textit{p}$ $\textit{cj}$ $(\textit{z}$ - $\textit{z})\textit{j}$ be analytic in whatever region about $\textit{z}$ is being considered. It is assumed that $\textit{c}0$ ≠ 0, that $\textit{cp}$ ≠ 0, and the $\textit{p}$ ≥ 1. The $\textit{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 $\textit{cj}$ = $\textit{α}\textit{j$ $ei}&psgr;\textit{j}$ and $\textit{z}$ - $\textit{z}$ = $\textit{re}\textit{i}&thgr;.$ Then $ƒ(\textit{z})$ = $\textit{α}0\textit{e}\textit{i}&psgr;0$ + $∑∞\textit{j}=\textit{p}$ $\textit{α}\textit{j}$ $\textit{rj}$ $\textit{ei}(\textit{j}&thgr;+&psgr;$ $\textit{j}),$ from which it follows that (3) $\textit{R}(\textit{r},$ &thgr;) = $\textit{α}0$ cos &psgr;0 + $∑∞\textit{j}=\textit{p}$ $\textit{α}\textit{j}$ $\textit{rj}$ cos $(\textit{j&thgr;}$ + $\textit{&psgr;j}),$ (4) $\textit{J}$ (r, &thgr;) = $\textit{α}0$ sin &psgr;0 + $∑∞\textit{j}=\textit{p}$ $\textit{α}\textit{j}\textit{rj}$ sin $(\textit{j&thgr;}$ + $&psgr;\textit{j}),$ and (5) $\textit{W}(\textit{r,$ &thgr;) = | $\textit{R}(\textit{r,$ &thgr;) | + | $\textit{J}$ (r, &thgr;) |. In particular, $\textit{W}(0,$ 0) = $\textit{α}0$ {| cos &psgr;0 | + | sin &psgr;0 |}. If the angle @@@@ is defined by the equation (6) @@@@ = $1/\textit{p}$ (π + &psgr;0 - $&psgr;\textit{p}),$ then $\textit{W}$ (δ, @@@@) ∼ | $\textit{α}0$ cos &psgr;0 - $\textit{α}\textit{p}δ\textit{p}$ cos &psgr;0 | + | $\textit{α}0$ sin &psgr;0 - $\textit{α}\textit{p}δ\textit{p}$ sin &psgr;0 | = | $\textit{α}0$ - $\textit{α}\textit{p}δ\textit{p}$ | {| cos &psgr;0 | + | sin &psgr;0|} < $\textit{W}$ (0, 0) for δ sufficiently small. To put these results in rectangular form, suitable for computation, let $\textit{x}$ + $\textit{i}\textit{y}$ = $\textit{z};$ $\textit{cj}$ = $\textit{aj}$ + $\textit{ibj},$ with $\textit{aj}$ and $\textit{bj}$ real; and $\textit{h}$ and $\textit{k}$ denote the increments in $\textit{x}$ and $\textit{y},$ respectively. It follows from equation (6) that (7) $\textit{k}/\textit{h}$ = tan $[1/\textit{p}$ (π + tan-1 $\textit{b}0/\textit{a}0$ - tan $-1\textit{bp}/\textit{ap})],$ and the following theorem has been proved.THEOREM. If $\textit{c}0$ ≠ 0, $\textit{c}1$ = $\textit{c}2$ = … = $\textit{cp}-1$ = 0, $\textit{cp}$ ≠ 0, $\textit{c}\textit{p}+1,$ … are complex coefficients in (1), then $\textit{W}$ $(\textit{x}$ + $\textit{h},$ $\textit{y}$ + $\textit{k})$ < $\textit{W}$ (x, y, for $\textit{h}$ and $\textit{k}$ sufficiently small, if $\textit{h}$ and $\textit{k}$ satisfy (7). As an example of the application of the theorem, consider the polynomial $\textit{f}(\textit{z})$ = 1 + $\textit{z}4.$ This polynomial was discussed in [1], and it was pointed out that the usual starting technique failed. Let $\textit{x}0$ + $\textit{iy}0$ = 0. Then $\textit{x}1$ = $\textit{h}1$ and $\textit{y}1$ = $\textit{k}1,$ where (8) $\textit{k}1$ = $\textit{h}1$ tan 1/4 (π + 0 - 0) = $\textit{h}1.$ Now, $\textit{W}$ (x, y) = | $\textit{x}4$ - $6x2\textit{y}2$ + $\textit{y}4$ + 1 | + | $4\textit{xy}$ | · | $\textit{x}2$ - $\textit{y}2$ |, so that $\textit{W}$ (0, 0) = 1. Taking $\textit{h}1$ = $\textit{k}1$ = 1/2 yields $\textit{W}$ (1/2, 1/2) = 3/4 < 1. Therefore, $\textit{z}1$ = $\textit{x}1$ + $\textit{iy}1$ = 1/2 (1 + $\textit{i})$ is permissible. For this example, the roots of $\textit{f}(\textit{z})$ = 0 are ± (√2/2) (1 ± $\textit{i}).$ Therefore, one could adjust $\textit{h}1$ (and $\textit{k}1)$ in accordance with (8) to obtain one of these roots. However, if we take $\textit{z}1$ = 1/2 (1 + $\textit{i}),$ then $\textit{f}(\textit{z})$ = 3/4 + $∑4\textit{j}=1$ $\textit{cj}$ $(\textit{z}$ - $\textit{z}1),$ where $\textit{c}1$ = -1 + $\textit{i}.$ Using (7) again, $\textit{k}2$ = $\textit{h}2$ tan (π + tan-1 0/4 - tan-1 1/-1) = $\textit{h}2.$ This procedure is followed step by step until $\textit{W}$ (x, y) differs from zero by no more than an initially prescribed amount. In this example, it can be seen easily that $\textit{k}3$ = $\textit{h}3,$ $\textit{k}4$ = $\textit{h}4,$ …. The only problem remaining is that of choosing the $\textit{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 $\textit{c}0$ and all of the other coefficients in (2) up through the first non-vanishing one. Subroutines for tan $\textit{&thgr;}$ and tan-1 $\textit{u}$ must be available.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1959-04-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 6
Issue Number 2
Page Count 3
Starting Page 223
Ending Page 225


Open content in new tab

   Open content in new tab
Source: ACM Digital Library