2.4 Secant method#

One drawback of Newton’s method is that we need to know \(f'(x)\) explicitly to evaluate \(f'(p_{n-1})\) in

\[\begin{equation*} p_{n}=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})},n\geq1. \end{equation*}\]

If we do not know \(f'(x)\) explicitly, or if its computation is expensive, we might approximate \(f'(p_{n-1})\) by the finite difference

(13)#\[\frac{f(p_{n-1}+h)-f(p_{n-1})}{h}\]

for some small \(h.\) We then need to compute two values of \(f\) at each iteration to approximate \(f'\). Determining \(h\) in this formula brings some difficulty, but there is a way to get around this. We will use the iterates themselves to rewrite the finite difference (13) as

\[\begin{equation*} \frac{f(p_{n-1})-f(p_{n-2})}{p_{n-1}-p_{n-2}}. \end{equation*}\]

Then, the recursion for \(p_n\) simplifies as

(14)#\[p_{n}=p_{n-1}-\frac{f(p_{n-1})}{\frac{f(p_{n-1})-f(p_{n-2})}{p_{n-1}-p_{n-2}}}=p_{n-1}-f(p_{n-1})\frac{p_{n-1}-p_{n-2}}{f(p_{n-1})-f(p_{n-2})},n\geq2.\]

This is called the secant method. Observe that

  • No additional function evaluations are needed,

  • The recursion requires two initial guesses \(p_{0},p_{1}.\)

Geometric interpretation: The slope of the secant line through the points \((p_{n-1},f(p_{n-1}))\) and \((p_{n-2},f(p_{n-2}))\) is \(\frac{f(p_{n-1})-f(p_{n-2})}{p_{n-1}-p_{n-2}}\). The \(x\)-intercept of the secant line, which is set to \(p_{n}\), is

\[\begin{equation*} \frac{0-f(p_{n-1})}{p_{n}-p_{n-1}}=\frac{f(p_{n-1})-f(p_{n-2})}{p_{n-1}-p_{n-2}}\Rightarrow p_{n}=p_{n-1}-f(p_{n-1})\frac{p_{n-1}-p_{n-2}}{f(p_{n-1})-f(p_{n-2})} \end{equation*}\]

which is the recursion of the secant method.

The following theorem shows that if the initial guesses are “good”, the secant method has superlinear convergence. A proof can be found in Atkinson [1989].

Theorem 8

Let \(f\in C^{2}[a,b]\) and assume \(f(p)=0,f'(p)\neq0,\) for \(p\in(a,b).\) If the initial guesses \(p_{0},p_{1}\) are sufficiently close to \(p,\) then the iterates of the secant method converge to \(p\) with

\[\begin{equation*} \lim_{n\rightarrow\infty}\frac{|p-p_{n+1}|}{|p-p_{n}|^{r_{0}}}=\left|\frac{f''(p)}{2f'(p)}\right|^{r_{1}} \end{equation*}\]

where \(r_{0}=\frac{\sqrt{5}+1}{2}\approx1.62,r_{1}=\frac{\sqrt{5}-1}{2}\approx0.62\).

Python code for the secant method#

The following code is based on Equation (14); the recursion for the secant method. The initial guesses are called pzero and pone in the code. The same stopping criterion as in Newton’s method is used. Notice that once a new iterate \(p\) is computed, pone is updated as \(p\), and pzero is updated as pone.

import numpy as np
def secant(f, pzero, pone, eps, N):
    n = 1
    p = 0. # to ensre the value of p carries out of the while loop
    while n <= N:
        p = pone - f(pone)*(pone-pzero) / (f(pone)-f(pzero))
        if np.isclose(f(p), 0) or np.abs(p-pone)<eps:
            print('p is ', p, ' and the iteration number is ', n)
            return
        pzero = pone
        pone = p
        n += 1
    y = f(p)
    print('Method did not converge. The last iteration gives ', 
          p, ' with function value ', y)

Let’s find the root of \(f(x)=\cos x - x\) using the secant method, using 0.5 and 1 as the initial guesses.

secant(lambda x: np.cos(x)-x, 0.5, 1, 1e-4, 20)

p is  0.739085132900112  and the iteration number is  4

Exercise 2.4-1

Use the Python codes for the secant and Newton’s methods to find solutions for the equation \(\sin x-e^{-x}=0\) on \(0\leq x\leq1\). Set tolerance to \(10^{-4}\), and take \(p_{0}=0\) in Newton, and \(p_{0}=0,p_{1}=1\) in secant method. Do a visual inspection of the estimates and comment on the convergence rates of the methods.

Exercise 2.4-2

a. The function \(y=\log x\) has a root at \(x=1\). Run the Python code for Newton’s method with \(p_0=2, \epsilon=10^{-4},N=20\), and then try \(p_0=3\). Does Newton’s method find the root in each case? If Python gives an error message, explain what the error is.

b. One can combine the bisection method and Newton’s method to develop a hybrid method that converges for a wider range of starting values \(p_0\), and has better convergence rate than the bisection method.

Write a Python code for a bisection-Newton hybrid method, as described below. (You can use the Python codes for the bisection and Newton’s methods from the lecture notes.) Your code will input \(f,f',a,b,\epsilon, N\) where \(f,f'\) are the function and its derivative, \((a,b)\) is an interval that contains the root (i.e., \(f(a)f(b)<0\)), and \(\epsilon, N\) are the tolerance and the maximum number of iterations. The code will use the same stopping criterion used in Newton’s method.

The method will start with computing the midpoint of \((a,b)\), call it \(p_0\), and use Newton’s method with initial guess \(p_0\) to obtain \(p_1\). It will then check whether \(p_1\in (a,b)\). If \(p_1\in (a,b)\), then the code will continue using Newton’s method to compute the next iteration \(p_2\). If \(p_1\notin (a,b)\), then we will not accept \(p_1\) as the next iteration: instead the code will switch to the bisection method, determine which subinterval among \((a,p_0),(p_0,b)\) contains the root, updates the interval \((a,b)\) as the subinterval that contains the root, and sets \(p_1\) to the midpoint of this interval. Once \(p_1\) is obtained, the code will check if the stopping criterion is satisfied. If it is satisfied, the code will return \(p_1\) and the iteration number, and terminate. If it is not satisfied, the code will use Newton’s method, with \(p_1\) as the initial guess, to compute \(p_2\). Then it will check whether \(p_2\in (a,b)\), and continue in this way. If the code does not terminate after \(N\) iterations, output an error message similar to Newton’s method.

Apply the hybrid method to:

  • a polynomial with a known root, and check if the method finds the correct root;

  • \(y=\log x\) with \((a,b)=(0,6)\), for which Newton’s method failed in part (a).

c. Do you think in general the hybrid method converges to the root, provided the initial interval \((a,b)\) contains the root, for any starting value \(p_0\)? Explain.

Atk89

K.E. Atkinson. An Introduction to Numerical Analysis. John Wiley & Sons, 2nd edition, 1989.