Secant Method

While the Newton-Raphson method has many positive features, it does require the evaluation of two different functions on each iteration, f(x) and $f^{\prime}(x)$. When f(x) is reasonably simple, it easy to compute $f^{\prime}(x)$, but when f(x) is a complicated function, the computation of the derivative can be tedious at best. Thus it is useful to have another method which does not require evaluation of $f^{\prime}(x)$. Such a method is the secant method which closely resembles the regula falsi method in using a linear approximation to f(x) at each iteration, but with the bracketing aspect dropped.

Figure 6.6: The secant method for a simple function. We observe that, unlike the regula falsi method, the initial points do not enclose a point where we necessarily know a zero of f(x) exists.

In figure 6.6 the secant method is illustrated and we can see that the function f(x) is being approximated by a straight line which is an extrapolation based on the two points x₀ and x₁. The line passing through the points (x₀,f(x₀)) and (x₁,f(x₁)) can be seen to be given by:

$$y - f_1 = (x - x_1) \frac{f_1 - f_0}{x_1 - x_0}$$ (6.18)

so that solving for the value of x for which y = 0 for this line, we have the two-point iteration formula:

$$x_{k+1} = x_k - f(x_k) \frac{x_k - x_{k-1}}{f(x_k) - f(x_{k-1})}\,.$$ (6.19)

The secant method is closely related to the Newton-Raphson method, and this relationship is clearly related to the fact that the quantity

$$\frac{\Delta f}{\Delta x} = \frac{f(x_k) - f(x_{k-1})}{x_k - x_{k-1}}$$ (6.20)

becomes $f^{\prime}(x)$ in the limit that $\vert x_k - x_{k-1}\vert \rightarrow 0$. In fact, from the Mean Value Theorem of calculus, we know that as long as f(x) is continuous in the interval [x_k,x_k-1], there is a point x = c in that interval for which

$$\frac{\Delta f}{\Delta x} = f^{\prime}(c)\,.$$ (6.21)

#!/usr/bin/env python
'''
    This uses the secant method to find the zero of a function starting
    from two values of x, which do not necessarily enclose the zero.
'''

import sys

def secant_solve(f,x1,x2,ftol,xtol):
  f1 = f(x1)
  if abs(f1) <= ftol : return x1        # already effectively zero
  f2 = f(x2)
  if abs(f2) <= ftol : return x2        # already effectively zero
  while abs(x2 - x1) > xtol :
    slope = (f2 - f1)/(x2 - x1)
    if slope == 0 :
      sys.stderr.write("Division by 0 due to vanishing slope - exit!\n")
      sys.exit(1)
    x3 = x2 - f2/slope               # the new approximate zero
    f3 = f(x3)                       # and its function value
    if abs(f3) <= ftol : break
    x1,f1 = x2,f2                    # copy x2,f2 to x1,f1
    x2,f2 = x3,f3                    # copy x3,f3 to x2,f2
  return x3

def quad(x):                  # a simple test function with known zeroes
  return  (x-5)*(x-2) 

root = secant_solve(quad,1.0,3.0,0.000001,0.000001)
print "ROOT = %g" % root
root = secant_solve(quad,3.0,10.0,0.000001,0.000001)
print "ROOT = %g" % root
root = secant_solve(quad,9.99,10.0,0.000001,0.000001)
print "ROOT = %g" % root

The secant method does not require the evaluation of any formal derivative as the Newton-Raphson does, and requires only one evaluation of f(x) per iteration. In many cases the absence of any requirement to compute a derivative is a significant advantage, not only because there is no need to perform the formal differentiation, but because frequently the derivative of a function is a significantly more complicated function than the original function. The rate of convergence for the Newton-Raphson for a simple zero x = a is said to be of order 2, meaning that the error |a - x_k+1| at iteration k+1 is related to the error |a - x_k| at iteration k by the relation:

$$\vert a - x_{k+1}\vert \approx A \vert a - x_k\vert^R$$ (6.22)

where A is some constant factor, and R = 2. Thus if the error $\vert a - x_k\vert \approx 10^{-3}$, then the error in the next iteration will be $\vert a - x_{k+1}\vert \approx A \times 10^{-6}$. The constant A is normally near 1, but its value is not particularly important here, for the exponent R has the dominant effect. While R = 2 for the Newton-Raphson method, the value for the secant method is about 1.618 (actually it can be shown to be $(1 + \sqrt{5})/2$) for simple zeroes. For many practical purposes, the difference between convergence of order 2 and order 1.618 is of less impact than the difficulties already mentioned for the Newton-Raphson method.

While both the regula falsi and secant methods use the idea of a linear approximation to the function based on its values at two points, the regula falsi method depends on the fact that those two points enclose a zero, with the consequent sign change for f(x), while the secant method simply extrapolates using these two points to find the next approximation to the zero. The regula falsi method is sure to find the zero, since it keeps it bracketed, while the secant method can sometimes fail to find a zero that does exist. The secant method has the advantage that we do not need to have prior knowledge of the interval in x in which each zero of f(x) lies.

We have tried to follow the dominant trend in the naming of these methods, but there does exist some variance in many books in this regard. Most variance arises with the distinction between the regula falsi method and the secant method. In fact both these methods use the straight line joining two points on a curve, which is called a secant or a chord. The distinction is in how the two methods use that secant to find the next approximation to the zero. It is probably best to think of the regula falsi method as an interpolator method for a zero in a known interval, and the secant method as an extrapolator method since it uses two known values to determine the next approximation for the zero, but without the restriction that the next approximation must lie in any particular interval. Of course, the secant method will function as an interpolator when the next approximation happens to lie between the two initial values of x.

<