For our first spelunking expedition, I skimmed volume 1 of the Communications of the ACM.
The first thing that I noticed about the earliest issues is that numerical algorithms dominate: numeric integration, minimizing errors, etc. If you dig around, though, you'll find a smattering of topics such as binary search in tables, as well.
The one that caught my eye this morning is Accelerating Convergence of Iterative Processes, by J. H. Wegstein of the U.S. National Bureau of Standards. (ACM began as an American organization; I don't know when the first articles from abroad appeared in CACM, nor when it began to really view itself as an international organization.)
The first thing you notice, of course, is the layout and typesetting. It's almost a newsletter format, single column, not a lot of boilerplate or fanciness. That said, the typesetting is pretty solid, even if it now looks kind of dated. (One big problem is the intermediate quality of the scans, but given the volume of material that needs to be brought online, I'm forgiving on this.)
The paper contains an acknowledgment that another researcher contributed Section 4 of the paper, so I wonder why he wasn't listed as an author. The main body of the text also includes a comment by the editor (Alan J. Perlis?) on a method for reducing the computational cost. The paper contains no references.
Okay, on to the content...
Iterative methods for finding roots of equations have been known for a long time; one famous one is Newton's method. They always depend on some assumptions about the nature of the function. In this paper, we are looking at roots of $F(x) = 0$. If the equation can be written as $x = f(x)$, then you're looking for a constant point (a kind of eigenvector or steady state solution?), and it can be found by iterating $x_{n+1} = f(x_n)$. If that form doesn't work, then you apply some factor $\Gamma$ by way of $x_{n+1} = x_n + \Gamma F(x_n)$.
The author examines several cases, where iteration causes values:
- to oscillate and converge;
- to oscillate and diverge;
- to converge monotonically; or, finally,
- to diverge monotonically.
No comments:
Post a Comment