Xref: utzoo sci.math:3105 comp.graphics:2029 Path: utzoo!mnetor!uunet!husc6!uwvax!rutgers!columbia!convent!agw From: agw@convent.columbia.edu (Art Werschulz) Newsgroups: sci.math,comp.graphics Subject: Re: Speed of iterative solutions Message-ID: <5443@columbia.edu> Date: 22 Mar 88 16:31:39 GMT References: <1656@thorin.cs.unc.edu> <7662@agate.BERKELEY.EDU> <7741@alice.UUCP> <7735@agate.BERKELEY.EDU> <25618@cca.CCA.COM> Sender: nobody@columbia.edu Reply-To: agw@columbia.edu (Art Werschulz) Followup-To: sci.math Organization: Columbia University Computer Science Dept. Lines: 106 Keywords: Newton's method Summary: Watch your model of computation! In article <25618@cca.CCA.COM> g-rh@CCA.CCA.COM.UUCP (Richard Harter) writes: >The secant method retains the *last* two guesses and estimates the zero >using a linear fit to the last two guesses. >[T]he convergence rate for the secant >method is e_n+1 = Const * e_n ** 1.618... > >The Newton-Raphson iteration convergence rate is quadratic, i.e. >e_n+1 = const * e_n ** 2. However the Newton-Raphson method requires >two evaluations per iteration, whereas the secant method only requires >one. The number of places gained, per evaluation, grows geometrically >with a factor of 1.414 for Newton and 1.618 for secant, so that the >secant method is more efficient. Not quite ... Suppose we wish to find an epsilon-approximation of the solution of a nonlinear equation. That is, given an initial approximation x_0 of the solution alpha of a nonlinear equation f(x) = 0 , we wish to find an approximation y(f) such that |y(f) - alpha| <= |x_0 - alpha| One of the results of iterative complexity theory says that the cost of using an iterative method phi whose order is p(phi) and whose cost per step is c(phi) to find an epsilon-approximation is asymptotically Z(phi) * log log (1/epsilon), where the complexity index Z(phi) is defined by c(phi) Z(phi) = ---------- log p(phi) Then an algorithm phi is better than another algorithm psi iff Z(phi) < Z(psi), since it produces epsilon-approximations more cheaply. [Reference: Traub and Wozniakowski, "A General Theory of Optimal Algorithms", Academic Press, 1980, pg. 236. Note that it really doesn't matter *what* base you use for your logarithms here, as long as you're consistent.] Now suppose we ignore the cost of "memory", i.e., the fact that the secant method must store the old value of f . Suppose that we only count informational cost (as you appear to be doing). That is, we only count evaluations of f and its derivatives,and ignore the combinatory cost (e.g., other arithmetic operations and the like). Then the complexity index of Newton's method is c(f) + c(f') ------------ log 2 while that of the secant method is c(f) --------- log 1.618 where the 1.618 is the solution 1 + sqrt(5) ----------- 2 of the polynomial equation x^2 - x - 1 = 0. It's then easy to see that Z(Newton) > Z(secant) iff c(f') log(2) ----- > ---------- - 1 = 0.4405 (roughly) c(f) log(1.618) Thus secant beats Newton iff the ratio of evaluating the derivative of f to evaluating f is greater than 0.4405. Moral: You have to be a little more careful about your model of computation when saying that one iteration is more efficient than another. >It should also be noted that the common trick of computing the derivative >by taking the difference between two close points is not the Newton method >and does not have the Newton convergence rate. However, a sufficiently-clever choice of the two close points *may* restore quadratic convergence. For example, consider Steffensen's iteration, which generates a new iterate x_{k+1} from an old iterate x_k via the following: z_k := f(x_k) + x_k z_k - x_k x_{k+1} := x_k - --------------- f(x_k) f(z_k) - f(x_k) Steffensen's method is quadratically convergent. Art Werschulz ARPAnet: agw@columbia.edu USEnet: ... seismo!columbia!agw BITnet: agw@columbia.edu CCNET: agw@garfield ATTnet: Columbia University (212) 280-3610 280-2736 Fordham University (212) 841-5323 841-5396