SPB Git

Repository Public

RootFinding.swift 6.5 KB 121 lines swift

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
Files main
Menu

Theme