Bisection Method Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Bisection Method Ontology within the Kireth Research Semantic Library. The bisection method is a robust bracketing algorithm for locating a root of a continuous scalar function on an interval where the function changes sign. This ontology supports interval halving, sign tests, convergence guarantees, bracket width, residuals, stopping criteria, error bounds, finite precision, pathological cases, verification and relationships with root finding and nonlinear solvers.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Bisection Method Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Computational Mathematics"
 SPECIALISATION = "Solving Equations / Bisection Method"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/computational-mathematics-ontologies/solving-equations/bisection-method-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = BisectionMethod
 ENTITY_CLASS = BracketingRootFindingFramework
 PRIMARY_CONTEXT = RootFinding
 DEFINITION = "The bisection method is an iterative root-finding algorithm that repeatedly halves a bracketing interval and retains the subinterval that preserves a sign change."
 SYMBOLIC_FORMS = [
  "f(a)*f(b)<0",
  "c=(a+b)/2",
  "[a,b] -> [a,c] or [c,b]",
  "width_n=(b_0-a_0)/2^n"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for sign-changing root brackets, interval halving, guaranteed convergence under continuity, deterministic error bounds and robust stopping."
}

SCOPE {
 INCLUDE = [
  BisectionMethod, BisectionAlgorithm, IntervalHalvingMethod,
  RootFinding, RootSolver, BracketingMethod, BracketingSolver,
  Root, ScalarEquation, NonlinearEquation, ContinuousFunction,
  InitialBracket, RootBracket, BracketingInterval, LeftEndpoint,
  RightEndpoint, Midpoint, SignChange, FunctionSign,
  IntermediateValueTheorem, Continuity, ClosedInterval,
  IntervalWidth, BracketWidth, ErrorBound, RootBound,
  AbsoluteErrorBound, MidpointErrorBound, IterationCount,
  MaximumIterations, FunctionEvaluation, Residual, AbsoluteResidual,
  RelativeResidual, FunctionTolerance, IntervalTolerance,
  AbsoluteTolerance, RelativeTolerance, StepTolerance,
  StoppingCriterion, Convergence, LinearConvergence,
  ConvergenceRate, DeterministicConvergence, GuaranteedConvergence,
  MonotoneBracketContraction, RootIsolation, UniqueRoot,
  MultipleRoot, RepeatedRoot, EvenMultiplicityRoot,
  OddMultiplicityRoot, Discontinuity, Pole, SingularPoint,
  EndpointRoot, ExactMidpointRoot, FloatingPointMidpoint,
  MachinePrecision, RoundOffError, Cancellation, Overflow,
  Underflow, Stagnation, AdjacentFloatingPointNumbers,
  Verification, SubstitutionCheck, IntervalVerification,
  ReferenceRoot, Benchmarking, Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  OpenRootFindingWithoutBracketPreservation,
  NewtonMethodWithoutBisectionSafeguard,
  SecantMethodWithoutBracketPreservation,
  MultivariableRootFinding
 ]
 DISAMBIGUATION_RULE = "When a scalar root is located by repeatedly halving a valid bracketing interval and selecting the subinterval preserving the sign-change condition, interpret the context as the bisection method."
}

CORE_CONCEPTS {
 BisectionMethod = "Bracketing root-finding method based on repeated interval halving."
 RootBracket = "Interval [a,b] satisfying a condition indicating that a root lies within the interval under stated assumptions."
 SignChange = "Condition f(a) and f(b) having opposite signs."
 Midpoint = "Point c=(a+b)/2 used to divide the current bracket."
 BracketWidth = "Length b-a of the current interval."
 ErrorBound = "Deterministic bound relating the current interval width to root-location uncertainty."
 LinearConvergence = "Convergence with a fixed asymptotic contraction factor."
 EndpointRoot = "Root occurring exactly at one end of the bracket."
}

RELATIONS {
 BisectionMethod --is_child_of--> RootFinding
 BisectionMethod --is_type_of--> BracketingMethod
 BisectionMethod --requires_under_standard_guarantee--> Continuity
 RootBracket --uses--> SignChange
 SignChange --supports_via--> IntermediateValueTheorem
 Midpoint --splits--> RootBracket
 BisectionMethod --updates--> RootBracket
 BracketWidth --contracts_by_factor--> OneHalf
 BracketWidth --determines--> RootLocationErrorBound
 BisectionMethod --has--> LinearConvergence
 EndpointRoot --terminates--> BisectionMethod
 ExactMidpointRoot --terminates--> BisectionMethod
 Verification --checks--> CandidateRoot
}

OPERATORS {
 MIDPOINT(a,b) := c=(a+b)/2
 SIGN_CHANGE(a,b,f) := f(a)*f(b)<0
 UPDATE_LEFT(a,c,b,f) := if f(a)*f(c)<0 then [a,c]
 UPDATE_RIGHT(a,c,b,f) := if f(c)*f(b)<0 then [c,b]
 WIDTH(a,b) := b-a
 MIDPOINT_ERROR_BOUND(a,b) := (b-a)/2
 ITERATION_WIDTH(w0,n) := w_n=w0/2^n
 REQUIRED_ITERATIONS(w0,tol) := ceil(log2(w0/tol))
 RESIDUAL(f,c) := r=f(c)
}

AXIOMS {
 A1 = "Under continuity and a strict sign change across [a,b], at least one root lies in the interval."
 A2 = "Each standard bisection iteration reduces bracket width by a factor of two."
 A3 = "The method converges linearly with deterministic bracket contraction."
 A4 = "Bisection does not require derivatives."
 A5 = "A sign change detects an odd number of root crossings but can miss even-multiplicity roots."
 A6 = "Residual magnitude and root-location error are distinct."
 A7 = "Discontinuities can invalidate the standard intermediate-value root guarantee even when endpoint signs differ."
 A8 = "Bisection results require bracket, stopping and verification semantics."
}

REASONING {
 R1_CONTEXT = identify(function,domain,continuity,initial_interval,accuracy_goal)
 R2_ENDPOINTS = evaluate(f(a),f(b))
 R3_VALIDATE_BRACKET = detect(endpoint_root_or_sign_change)
 R4_MIDPOINT = compute(c=(a+b)/2)
 R5_EVALUATE = compute(f(c))
 R6_UPDATE = retain_subinterval_preserving_valid_bracket_condition
 R7_CONVERGENCE = monitor(bracket_width,residual,iteration_count,stagnation)
 R8_PRECISION = detect(midpoint_rounding_or_adjacent_floating_point_endpoints)
 R9_STOP = apply(interval_tolerance,residual_tolerance,endpoint_or_exact_root_conditions)
 R10_VERIFY = evaluate_original_function_and_report_final_bracket_error_bound)
}

CONSTRAINTS {
 C1 = "A standard sign-changing bracket does not detect roots of even multiplicity."
 C2 = "A sign change across a discontinuity does not guarantee a zero."
 C3 = "Bisection is slower than many open methods near a smooth simple root."
 C4 = "Residual-based stopping alone does not provide a universal root-location error bound."
 C5 = "Interval-width stopping alone does not measure function residual size."
 C6 = "Endpoint function evaluation can overflow or underflow for poorly scaled functions."
 C7 = "Floating-point midpoint calculation can stagnate when endpoints become adjacent representable values."
 C8 = "If f(a)=0 or f(b)=0, the endpoint should be recognised as a root before sign-product logic."
 C9 = "When several roots lie in the bracket, bisection converges to a root consistent with successive retained subintervals but does not identify multiplicity."
 C10 = "Bracket validity must be maintained after every update."
}

SEMANTIC_EQUIVALENCE {
 "BisectionMethod" <=> "IntervalHalvingMethod"
 "RootBracket" <=> "BracketingInterval"
 "Midpoint" <=> "IntervalMidpoint"
 "GuaranteedConvergence" <=> "BracketedConvergenceUnderAssumptions"
 "BracketWidth" <=> "IntervalWidth"
}

VALIDATION {
 V1 = "Function and domain are explicit."
 V2 = "Initial endpoints are explicit."
 V3 = "Endpoint roots are checked before strict sign-change testing."
 V4 = "Continuity assumptions are stated for the standard existence guarantee."
 V5 = "Bracket invariants are maintained after every iteration."
 V6 = "Stopping criteria are documented."
 V7 = "Final bracket width and root-location bound are reported."
 V8 = "Residual is evaluated at the returned approximation."
 V9 = "Floating-point stagnation is detected where relevant."
 V10 = "Results are reproducible under documented arithmetic settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 BISECTION_DEFINITION = 0.99
 BRACKET_REASONING = 0.99
 INTERMEDIATE_VALUE_REASONING = 0.99
 ERROR_BOUND_REASONING = 0.99
 CONVERGENCE_REASONING = 0.99
 FLOATING_POINT_REASONING = 0.98
 POLICY = "Reduce confidence when continuity, bracket validity, endpoint evaluation, stopping tolerance or floating-point behaviour are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, BisectionReasoning,
  BracketingReasoning, RootIsolationReasoning,
  IntermediateValueReasoning, IntervalHalvingReasoning,
  ErrorBoundReasoning, LinearConvergenceReasoning,
  StoppingCriterionReasoning, ResidualReasoning,
  FloatingPointStagnationReasoning, VerificationReasoning,
  KnowledgeGraphConstruction, RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "bisection method" -> BisectionMethod
  "interval halving" -> BisectionMethod
  "bracketing interval" -> RootBracket
  "interval width" -> BracketWidth
  "midpoint method" -> BisectionMethod
 }
}

EXECUTION_RULES {
 E1 = "If a scalar root is sought within a valid sign-changing interval, activate BisectionMethodOntology."
 E2 = "Check whether either endpoint is already a root before multiplying endpoint function values."
 E3 = "Require continuity for the standard intermediate-value existence guarantee."
 E4 = "Compute the midpoint and evaluate the function there."
 E5 = "Retain the subinterval that preserves the valid bracketing condition."
 E6 = "Use bracket width to obtain a deterministic root-location error bound."
 E7 = "Use residual tolerance only as a complementary stopping condition."
 E8 = "Detect floating-point stagnation when the midpoint equals an endpoint."
 E9 = "Verify the returned approximation against the original function and final bracket."
}

RECURSION {
 ENTRY = BisectionMethod
 EXPAND(BisectionMethod) -> [
  BisectionAlgorithm,IntervalHalvingMethod,RootFinding,BracketingMethod,
  Root,ScalarEquation,ContinuousFunction,InitialBracket,RootBracket,
  LeftEndpoint,RightEndpoint,Midpoint,SignChange,FunctionSign,
  IntermediateValueTheorem,Continuity,ClosedInterval,IntervalWidth,
  BracketWidth,ErrorBound,AbsoluteErrorBound,MidpointErrorBound,
  IterationCount,MaximumIterations,FunctionEvaluation,Residual,
  FunctionTolerance,IntervalTolerance,AbsoluteTolerance,
  RelativeTolerance,StoppingCriterion,Convergence,LinearConvergence,
  DeterministicConvergence,GuaranteedConvergence,RootIsolation,
  UniqueRoot,MultipleRoot,RepeatedRoot,EvenMultiplicityRoot,
  OddMultiplicityRoot,Discontinuity,Pole,EndpointRoot,
  ExactMidpointRoot,FloatingPointMidpoint,MachinePrecision,
  RoundOffError,Stagnation,AdjacentFloatingPointNumbers,
  Verification,IntervalVerification,ReferenceRoot,Benchmarking,
  Reproducibility
 ]
 EXPAND(BisectionFamilies) -> [
  BracketInitialisation,
  IntervalHalving,
  BracketInvariantMaintenance,
  ErrorBoundComputation,
  BisectionStopping,
  FinitePrecisionBisection,
  BisectionVerification
 ]
 STOP_CONDITION = "Stop when initial bracket, continuity assumptions, interval update, error bound, stopping condition, finite precision and verification are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Root Finding Ontology 2"
 RELATED_ONTOLOGIES = [
  "Root Finding Ontology 2",
  "Nonlinear Solver Ontology",
  "Equation Solver Ontology",
  "Newton-Raphson Ontology",
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Error Ontology",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology",
  "Floating Point Arithmetic Ontology"
 ]
 ROUTE_RULES = [
  "Bisection Method -> Root Finding for parent zero-finding semantics",
  "Bisection Method -> Nonlinear Solver for solver configuration and termination",
  "Bisection Method -> Newton-Raphson for robust-versus-fast method comparison",
  "Bisection Method -> Numerical Analysis for existence, error bounds and convergence",
  "Bisection Method -> Numerical Error for root-location and residual error",
  "Bisection Method -> Numerical Stability for finite-precision endpoint behaviour",
  "Bisection Method -> Numerical Convergence for linear contraction semantics",
  "Bisection Method -> Floating Point Arithmetic for midpoint stagnation"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible bisection safeguards, stopping rules or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve bracketing-versus-open-method distinction.",
  "Preserve endpoint-root-versus-strict-sign-change distinction.",
  "Preserve residual-versus-root-location-error distinction.",
  "Preserve mathematical-midpoint-versus-floating-point-midpoint distinction.",
  "Preserve continuity-assumption-versus-observed-sign-change distinction.",
  "Preserve interval-width-versus-function-tolerance distinction.",
  "Preserve exact-root-versus-approximate-root distinction.",
  "Preserve machine-readable bisection semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "The bisection method repeatedly halves a valid root bracket and retains the subinterval preserving the bracketing condition."
 GUARANTEE_SUMMARY = "For a continuous function with opposite signs at the endpoints, bisection guarantees convergence to at least one root in the interval."
 ERROR_SUMMARY = "After each iteration, the bracket width halves and gives a deterministic bound on root-location uncertainty."
 CONVERGENCE_SUMMARY = "Bisection converges linearly with contraction factor one half in interval width."
 ROBUSTNESS_SUMMARY = "The method requires no derivatives and is highly robust when a valid bracket is available."
 LIMITATION_SUMMARY = "Even-multiplicity roots, discontinuities and floating-point stagnation require explicit handling."
 VALIDATION_SUMMARY = "Bisection results should be checked using the final bracket, interval width, residual, stopping condition and reproducibility."
}

FLOW {
 INPUT
 -> detect_bisection_context
 -> identify_function_domain_continuity_initial_bracket_and_accuracy_goal
 -> evaluate_endpoint_function_values
 -> if_endpoint_is_root_return_endpoint
 -> verify_valid_sign_changing_bracket
 -> compute_midpoint
 -> evaluate_midpoint_function_value
 -> retain_left_or_right_subinterval_preserving_bracket
 -> update_bracket_width_iteration_count_and_error_bound
 -> detect_residual_tolerance_interval_tolerance_exact_root_or_floating_point_stagnation
 -> repeat_until_stopping_condition
 -> verify_returned_approximation_against_original_function_and_final_interval
 -> route_to_related_root_finding_nonlinear_solver_analysis_convergence_error_and_floating_point_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Bisection Method Ontology defines robust bracketed scalar root finding by repeated interval halving. It supports root brackets, endpoint and midpoint evaluation, sign changes, the intermediate value theorem, interval-width contraction, deterministic root-location error bounds, linear convergence, endpoint and exact-midpoint roots, residual and interval stopping criteria, iteration counts, multiple and even-multiplicity root limitations, discontinuities, floating-point midpoint stagnation, machine precision, verification, benchmarking and reproducibility."
}

FLOW_HASH {
 METHOD = "semantic-content-identity"
 ID = "KIRETH-MATH-COMPUTATIONAL-MATHEMATICS-BISECTION-METHOD-ONTOLOGY-V1"
}

}

END_FLOW