Page - 192 - in Programming for Computations – Python - A Gentle Introduction to Numerical Simulations with Python

192 6 SolvingNonlinearAlgebraicEquations 1. theslopeequals tof 0.x0/ 2. the tangent touches thef.x/curveatx0 So, ifwewrite the tangent functionas Qf.x/DaxCb,wemust require Qf 0.x0/D f 0.x0/and Qf.x0/Df.x0/, resulting in Qf.x/Df.x0/Cf 0.x0/.x x0/: Thekeystep inNewton’smethod is tofindwhere the tangentcrosses thex axis, whichmeanssolving Qf.x/D0: Qf.x/D0 ) xDx0 f.x0/ f 0.x0/ : This isournewcandidatepoint,whichwecallx1: x1 Dx0 f.x0/ f 0.x0/ : With x0 D 1000, we get x1 500, which is in accordance with the graph in Fig.6.1.Repeating theprocess,weget x2 Dx1 f.x1/ f 0.x1/ 250: Thegeneral schemeofNewton’smethodmaybewrittenas xnC1 Dxn f.xn/ f 0.xn/ ; nD0;1;2;:: : (6.1) The computation in (6.1) is repeated until f .xn/ is close enough to zero. More precisely,we test if jf.xn/j< ,with beingasmall number. We moved from 1000 to 250 in two iterations, so it is exciting to see how fast we can approach the solution x D 3. A computer program can automate the calculations. Our first try at implementingNewton’smethod is in a function naive_Newton: def naive_Newton(f, dfdx, x, eps): while abs(f(x)) > eps: x = x - float(f(x))/dfdx(x) return x Theargumentx is the startingvalue, calledx0 inourpreviousmathematicalde- scription.Weusefloat(f(x)) to ensure that an integerdivisiondoesnothappen byaccident iff(x)anddfdx(x)bothare integers for somex. Tosolve theproblemx2 D9wealsoneed to implement def f(x): return x**2 - 9 def dfdx(x): return 2*x print naive_Newton(f, dfdx, 1000, 0.001)