Seite - 187 - in Programming for Computations – Python - A Gentle Introduction to Numerical Simulations with Python

6.1 BruteForceMethods 187 6.1.1 BruteForceRootFinding Assume thatwehaveasetofpoints along thecurveof a functionf.x/: Wewant to solvef.x/ D 0, i.e., find the pointsxwheref crosses thex 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 thenextpoint is above thex axis, or theotherway around. If this is found to be the case, we know thatf must be zero in between these twox points. Numericalalgorithm Moreprecisely,wehaveasetofnC1points .xi;yi/,yi D f.xi/, i D 0;:: :;n,wherex0 < ::: < xn. Wecheck ifyi < 0 andyiC1 > 0 (or the otherway around). A compact expression for this check is to perform the test yiyiC1 <0. If so, the rootoff.x/D0 is in Œxi;xiC1 . Assuminga linearvariation off betweenxi andxiC1,wehave theapproximation f.x/ f.xiC1/ f.xi/ xiC1 xi .x xi/Cf.xi/D yiC1 yi xiC1 xi .x xi/Cyi; which,whenset equal tozero, gives the root xDxi xiC1 xi yiC1 yiyi : Implementation Given some Python implementation f(x) of ourmathematical function, a straightforward implementationof theabovenumericalalgorithmlooks like