"""ch11_multiple_roots.py Find several distinct roots by scanning an interval and using bisection on each subinterval with a sign change. Origin: Python version of ch11_multiple_roots.f90 by Alexander Godunov. Based on the default scan plus bisection method in BForce.f90. Example: f(x) = exp(x) - x*sin(pi*x/2) on [-10.5, 2]. The chapter example has six distinct roots in this interval. The tolerance applies to the final width of each root bracket. A sign-change scan can miss even-multiplicity roots, pairs of roots within one subinterval, and roots near a discontinuity. Inspect a plot and repeat with more subintervals when counting roots matters. """ import math def main(): """Set up the example and print the detected roots and residuals.""" # Search interval, number of scan subintervals, and bracket-width tolerance x1 = -10.5 x2 = 2.0 n = 1000 eps = 1.0e-7 print("Roots of f(x) by interval scanning and bisection") print(f"interval = [{x1:.3f}, {x2:.3f}]") print(f"scan subintervals = {n}") print(f"bracket-width tol. = {eps:.5e}") roots, nfail = multiple_roots(f, x1, x2, n, eps) if not roots: print("no roots detected by the scan") else: print("number root f(root)") for i, root in enumerate(roots, start=1): print(f"{i:5d} {root:18.10f} {f(root):16.8e}") if nfail > 0: print(f"brackets not refined to the requested width: {nfail}") def multiple_roots(fun, x1, x2, n, eps): """Scan [x1, x2] and bisect subintervals with opposite endpoint signs. Input: fun - function continuous on the search interval x1,x2 - endpoints of the search interval, with x1 < x2 n - number of equal scan subintervals (positive) eps - maximum final bracket width (positive) Output: roots - detected roots, in increasing order nfail - number of sign-change brackets that reached the limit Notes: A zero at a grid point is recorded once, including at x2. A sign change only certifies a root when fun is continuous there. The scan does not certify that all roots have been found. """ roots = [] nfail = 0 if n <= 0 or x1 >= x2 or eps <= 0.0: return roots, nfail dx = (x2 - x1) / n a = x1 fa = fun(a) # Each grid point is checked once; a sign change brackets another root. for j in range(1, n + 1): b = x1 + j * dx fb = fun(b) if fa == 0.0: roots.append(a) elif fa * fb < 0.0: root, flag = bisect_bracket(fun, a, b, eps) if flag > 0: roots.append(root) else: nfail += 1 a = b fa = fb # The rightmost grid point is not a left endpoint in the loop. if fa == 0.0: roots.append(a) return roots, nfail def bisect_bracket(fun, x1, x2, eps): """Refine one sign-change bracket by bisection. Input: fun - function continuous on [x1, x2] x1,x2 - endpoints with opposite signs of fun eps - requested maximum final bracket width Output: root - midpoint of the final bracket flag - positive iteration count on convergence; -200 on limit Notes: The stopping rule is bracket width, as in ch11_bisection.py. """ max_iterations = 200 a = x1 b = x2 fa = fun(a) flag = -max_iterations for i in range(1, max_iterations + 1): c = a + (b - a) / 2.0 fc = fun(c) if fa * fc <= 0.0: b = c else: a = c fa = fc if abs(b - a) <= eps: flag = i break root = a + (b - a) / 2.0 return root, flag def f(x): """Example from Chapter 11. Replace this expression for another problem.""" # Choose a scan interval on which the new function is continuous. pi = 3.141592653589793 return math.exp(x) - x * math.sin(pi * x / 2.0) if __name__ == "__main__": main()