Repository Public
1import Foundation23/// Outcome of a one-dimensional root search.4public struct RootResult: Sendable, Hashable, Codable {5 public var root: Double6 /// f(root).7 public var residual: Double8 public var iterations: Int9 public var functionEvaluations: Int10 public var converged: Bool11 /// "brent", "secant", "bisection"…12 public var method: String1314 public init(root: Double, residual: Double, iterations: Int, functionEvaluations: Int, converged: Bool, method: String) {15 self.root = root; self.residual = residual; self.iterations = iterations16 self.functionEvaluations = functionEvaluations; self.converged = converged; self.method = method17 }18}1920public enum RootFinder {21 /// Brent's method (inverse quadratic interpolation / secant / bisection) on a bracketing interval:22 /// f(a) and f(b) must have opposite signs. Converges to |b − a| ≤ 2·ε·|x| + xtol, like `scipy.optimize.brentq`.23 public static func brent(_ f: (Double) throws -> Double, lower: Double, upper: Double,24 xtol: Double = 1e-13, maxIterations: Int = 200) throws -> RootResult {25 var a = lower, b = upper26 var fa = try f(a), fb = try f(b)27 var evals = 228 guard fa.isFinite, fb.isFinite else { throw StatError.invalidInput("function is not finite at the bracket ends") }29 if fa == 0 { return RootResult(root: a, residual: 0, iterations: 0, functionEvaluations: evals, converged: true, method: "brent") }30 if fb == 0 { return RootResult(root: b, residual: 0, iterations: 0, functionEvaluations: evals, converged: true, method: "brent") }31 guard (fa < 0) != (fb < 0) else { throw StatError.invalidInput("root is not bracketed: f(a) and f(b) have the same sign") }32 var c = a, fc = fa, d = b - a, e = d33 for iter in 1...max(1, maxIterations) {34 if (fb > 0) == (fc > 0) { c = a; fc = fa; d = b - a; e = d }35 if abs(fc) < abs(fb) { a = b; b = c; c = a; fa = fb; fb = fc; fc = fa }36 let tol1 = 2 * Double.ulpOfOne * abs(b) + 0.5 * xtol37 let xm = 0.5 * (c - b)38 if abs(xm) <= tol1 || fb == 0 {39 return RootResult(root: b, residual: fb, iterations: iter, functionEvaluations: evals, converged: true, method: "brent")40 }41 if abs(e) >= tol1 && abs(fa) > abs(fb) {42 let s = fb / fa43 var p: Double, q: Double44 if a == c {45 p = 2 * xm * s46 q = 1 - s47 } else {48 let qq = fa / fc, r = fb / fc49 p = s * (2 * xm * qq * (qq - r) - (b - a) * (r - 1))50 q = (qq - 1) * (r - 1) * (s - 1)51 }52 if p > 0 { q = -q }53 p = abs(p)54 if 2 * p < min(3 * xm * q - abs(tol1 * q), abs(e * q)) { e = d; d = p / q } else { d = xm; e = d }55 } else {56 d = xm; e = d57 }58 a = b; fa = fb59 b += abs(d) > tol1 ? d : (xm > 0 ? tol1 : -tol1)60 fb = try f(b)61 evals += 162 guard fb.isFinite else { throw StatError.invalidInput("function is not finite inside the bracket") }63 }64 return RootResult(root: b, residual: fb, iterations: maxIterations, functionEvaluations: evals, converged: false, method: "brent")65 }6667 /// Looks for an interval around `guess` on which f changes sign by geometric expansion68 /// (optionally clamped to [min, max]). Returns nil when none is found.69 public static func bracket(_ f: (Double) throws -> Double, guess: Double, step: Double? = nil,70 min lo: Double = -.infinity, max hi: Double = .infinity,71 growth: Double = 1.6, maxExpansions: Int = 60) rethrows -> (lower: Double, upper: Double)? {72 var width = step ?? Swift.max(abs(guess) * 0.1, 0.01)73 var a = Swift.max(lo, guess - width), b = Swift.min(hi, guess + width)74 if a == b { return nil }75 var fa = try f(a), fb = try f(b)76 for _ in 0..<maxExpansions {77 if fa.isFinite, fb.isFinite, fa == 0 || fb == 0 || (fa < 0) != (fb < 0) { return (a, b) }78 width *= growth79 // expand the side that looks closer to a root (smaller |f|), or both when undecidable80 let expandLeft = !fb.isFinite || (fa.isFinite && abs(fa) <= abs(fb))81 let expandRight = !fa.isFinite || (fb.isFinite && abs(fb) <= abs(fa))82 var moved = false83 if expandLeft, a > lo { a = Swift.max(lo, a - width); fa = try f(a); moved = true }84 if expandRight, b < hi { b = Swift.min(hi, b + width); fb = try f(b); moved = true }85 if !moved {86 if a > lo { a = Swift.max(lo, a - width); fa = try f(a) } else if b < hi { b = Swift.min(hi, b + width); fb = try f(b) } else { break }87 }88 }89 if fa.isFinite, fb.isFinite, fa == 0 || fb == 0 || (fa < 0) != (fb < 0) { return (a, b) }90 return nil91 }9293 /// Secant iteration from two starting points (no bracketing needed; may diverge).94 public static func secant(_ f: (Double) throws -> Double, x0: Double, x1: Double,95 xtol: Double = 1e-12, ftol: Double = 0, maxIterations: Int = 100) rethrows -> RootResult {96 var a = x0, b = x197 var fa = try f(a), fb = try f(b)98 var evals = 299 for iter in 1...max(1, maxIterations) {100 if fb == 0 || abs(fb) <= ftol {101 return RootResult(root: b, residual: fb, iterations: iter, functionEvaluations: evals, converged: true, method: "secant")102 }103 let denom = fb - fa104 guard denom != 0, denom.isFinite, fb.isFinite else {105 return RootResult(root: b, residual: fb, iterations: iter, functionEvaluations: evals, converged: false, method: "secant")106 }107 let next = b - fb * (b - a) / denom108 guard next.isFinite else {109 return RootResult(root: b, residual: fb, iterations: iter, functionEvaluations: evals, converged: false, method: "secant")110 }111 a = b; fa = fb112 b = next; fb = try f(b)113 evals += 1114 if abs(b - a) <= xtol * Swift.max(1, abs(b)) {115 return RootResult(root: b, residual: fb, iterations: iter, functionEvaluations: evals, converged: fb.isFinite, method: "secant")116 }117 }118 return RootResult(root: b, residual: fb, iterations: maxIterations, functionEvaluations: evals, converged: false, method: "secant")119 }120}121