Page - 188 - in Programming for Computations – Python - A Gentle Introduction to Numerical Simulations with Python 3.6, Volume Second Edition

188 7 SolvingNonlinearAlgebraicEquations 7.3 TheSecantMethod When finding the derivative f ′(x) in Newton’s method is problematic, or when function evaluations take too long; we may adjust the method slightly. Instead of using tangent lines to thegraphwemayusesecants.4 Theapproachis referred toas thesecantmethod, and the idea is illustratedgraphically inFig.7.2 forourexample problemx2−9=0. The idea of the secant method is to think as in Newton’s method, but instead of using f ′(xn), we approximate this derivative by a finite difference or the secant, i.e., the slope of the straight line that goes through the points (xn,f(xn)) and (xn−1,f(xn−1))on the graph,givenby the two most recentapproximationsxn and xn−1. This slope reads f(xn)−f(xn−1) xn−xn−1 . (7.2) Inserting this expression forf ′(xn) in Newton’smethodsimply givesus the secant method: xn+1 =xn− f(xn)f(xn)−f(xn−1) xn−xn−1 , or xn+1 =xn−f(xn) xn−xn−1 f(xn)−f(xn−1) . (7.3) Comparing (7.3) to the graph in Fig.7.2, we see how two chosen starting points (x0 = 1000, x1 = 700, and corresponding function values) are used to compute x2. Once we havex2, we similarly usex1 andx2 to computex3. As with Newton’s method, the procedure is repeated until f(xn) is below some chosen limit value, or some limit on the number of iterations has been reached. We use an iteration counterhere too,based on the same thinkingas in the implementationof Newton’s method. We can store the approximations xn in an array, but as in Newton’s method, we notice that the computation ofxn+1 only needs knowledge ofxn andxn−1, not “older” approximations.Therefore, we can make use of only three variables:x for xn+1,x1 forxn, andx0 forxn−1. Note thatx0 andx1must be given (guessed) for thealgorithmto start. Aprogramsecant_method.pythatsolvesourexampleproblemmaybewritten as: import sys def secant(f, x0, x1, eps): f_x0 = f(x0) f_x1 = f(x1) 4 https://en.wikipedia.org/wiki/Secant_line.