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

7.1 BruteForceMethods 177 7.1.1 BruteForceRootFinding Assumethatwe havea set ofpointsalong thecurveofacontinuousfunctionf(x): We want to solvef(x) = 0, i.e., find the pointsx wheref crosses the x axis. A brute force algorithm is to run through all points on the curve and check if one point is below thex axis and if the next point is above thex axis, or the other way around.If this is foundtobe thecase,weknowthat,whenf is continuous, it has to cross thex axis at least once between these twox values. In otherwords,f is zero at least onceon that sub-interval. Note that, in the following algorithm, we refer to “the” root on a sub-interval, even if there may be more than one root in principle. Whether there are more than one root on a sub-interval will of course depend on the function, as well as on the size and location of the sub-interval. For simplicity, we will just assume there is at most one root on a sub-interval (or that it is sufficiently precise to talk about one root, even if therecouldbe more). NumericalAlgorithm Moreprecisely,wehaveaset ofn+1points (xi,yi),yi = f(xi), i = 0,.. .,n, wherex0 < ... < xn. We check ifyi < 0 andyi+1 > 0 (or the other way around). A compact expression for this check is to perform the test yiyi+1 <0. If so, the rootoff(x)=0 is in [xi,xi+1]. Assumingalinearvariationoff betweenxi andxi+1,wehavetheapproximation f(x)≈ f(xi+1)−f(xi) xi+1−xi (x−xi)+f(xi)= yi+1−yi xi+1−xi(x−xi)+yi, which,whenset equal tozero,gives the root x=xi− xi+1−xi yi+1−yiyi .