g-rh@cca.CCA.COM (Richard Harter) (03/17/88)
In article <7735@agate.BERKELEY.EDU> greg@skippy.UUCP (Greg) writes: > >The whole point of the algorithm is that the root is bracketed in such a way >that Newton's method will work beautifully. As a general rule, Newton's >method either crashes, stumbles in the dark, or converges much more quickly >than an uninspired method such as regula falsi. In this case, there are >no inflection points to interfere. There may be two roots, which would >make regula falsi choke, but Newton steps from the two endpoints will >get you both roots. If there is one root, you pick the starting endpoint >based on concavity and again Newton's method can't fail. A point that should be mentioned is that there are two algorithms which look very similar, but which have quite difference performance. These are the regula-falsi and the secant algorithms. The regula falsi algorithm maintains two bracket points, interpolates between them linearly to get a new estimate and moves on of the bracket points in. The secant method retains the *last* two guesses and estimates the zero using a linear fit to the last two guesses. The similarity resides in the fact that both algorithms keep two guesses. However regula-falsi has geometric convergence, whereas the 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. The secant method and the Newton method both are subject to failure of convergence, and both can be tamed by combining them with a bracketing strategy. The secant method is tricky to code correctly because it is subject to numerical instability. 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. If one is creating a routine ad-hoc to iteratively solve an equation the Newton method is simplest to code and implement. If one is creating an iterative zero finder as a library routine, the secant method is superior. -- In the fields of Hell where the grass grows high Are the graves of dreams allowed to die. Richard Harter, SMDS Inc.
agw@convent.columbia.edu (Art Werschulz) (03/23/88)
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