Root Finding Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Root Finding Ontology 2 within the Kireth Research Semantic Library. Root finding studies computational methods for determining values x such that f(x)=0. This ontology supports scalar roots, brackets, bisection, false position, secant, Newton and Halley methods, fixed-point iteration, Brent and hybrid methods, multiplicity, convergence order, stopping criteria, conditioning, round-off, verification and robust solver selection.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = RootFinding
 ENTITY_CLASS = ScalarNonlinearZeroFindingFramework
 PRIMARY_CONTEXT = SolvingEquations
 DEFINITION = "Root finding is the numerical or symbolic process of determining values x for which a scalar function satisfies f(x)=0."
 SYMBOLIC_FORMS = [
  "f(x)=0",
  "x_star : f(x_star)=0",
  "x_(k+1)=Phi(x_k)",
  "|f(x_k)|<=tolerance"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for scalar zero finding, bracketing, open and hybrid methods, root multiplicity, convergence, residuals, conditioning, finite precision and verification."
}

SCOPE {
 INCLUDE = [
  RootFinding, RootSolver, ZeroFinding, ZeroOfFunction, Root,
  ScalarEquation, NonlinearEquation, ContinuousFunction,
  DifferentiableFunction, InitialGuess, InitialBracket, RootBracket,
  SignChange, IntermediateValueTheorem, BracketingMethod,
  OpenMethod, HybridMethod, BisectionMethod, RegulaFalsi,
  FalsePositionMethod, IllinoisMethod, PegasusMethod,
  SecantMethod, NewtonMethod, NewtonRaphsonMethod, ModifiedNewtonMethod,
  HalleyMethod, HouseholderMethod, FixedPointIteration,
  SteffensenMethod, BrentMethod, RidderMethod, MullerMethod,
  InverseQuadraticInterpolation, PolynomialRootFinding,
  MultipleRoot, RepeatedRoot, SimpleRoot, RootMultiplicity,
  RootSeparation, BasinOfAttraction, BracketWidth, Residual,
  AbsoluteResidual, RelativeResidual, StepSize, StepNorm,
  FunctionTolerance, StepTolerance, AbsoluteTolerance,
  RelativeTolerance, StoppingCriterion, MaximumIterations,
  MaximumEvaluations, Convergence, ConvergenceRate,
  LinearConvergence, SuperlinearConvergence, QuadraticConvergence,
  CubicConvergence, Divergence, Stagnation, Cycling,
  Derivative, FirstDerivative, SecondDerivative,
  DerivativeFreeMethod, NumericalDerivative, FiniteDifferenceDerivative,
  Conditioning, RootConditionNumber, Sensitivity, FlatRoot,
  SteepRoot, RoundOffError, TruncationError, MachinePrecision,
  FloatingPointArithmetic, Overflow, Underflow, Cancellation,
  Scaling, VariableTransformation, Deflation, PolynomialDeflation,
  Verification, SubstitutionCheck, IntervalVerification,
  ReferenceRoot, Benchmarking, Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  MultivariableNonlinearSystemSolving,
  LinearSystemSolving,
  OptimisationWithoutZeroFindingSemantics,
  DifferentialEquationIntegrationWithoutEventRootContext
 ]
 DISAMBIGUATION_RULE = "When the central task is to determine scalar values x satisfying f(x)=0, interpret the context as root finding."
}

CORE_CONCEPTS {
 RootFinding = "Computation of zeros of scalar functions."
 Root = "Value x_star satisfying f(x_star)=0."
 RootBracket = "Interval known or believed to contain a root."
 BracketingMethod = "Method preserving a bracket around a root under suitable assumptions."
 OpenMethod = "Method using one or more estimates without preserving a bracket."
 NewtonMethod = "Derivative-based local root-finding iteration."
 SecantMethod = "Derivative-free iteration approximating Newton's derivative by a secant slope."
 RootMultiplicity = "Number of times a root is repeated in the local factorisation of a function."
 ConvergenceOrder = "Rate at which root approximations approach the solution asymptotically."
}

RELATIONS {
 RootFinding --is_child_of--> NonlinearSolver
 RootFinding --solves--> ScalarEquation
 Root --satisfies--> ZeroEquation
 RootBracket --uses--> SignChange
 BisectionMethod --is_type_of--> BracketingMethod
 RegulaFalsi --is_type_of--> BracketingMethod
 SecantMethod --is_type_of--> OpenMethod
 NewtonMethod --is_type_of--> OpenMethod
 BrentMethod --is_type_of--> HybridMethod
 NewtonMethod --uses--> FirstDerivative
 HalleyMethod --uses--> FirstAndSecondDerivative
 FixedPointIteration --uses--> FixedPointMap
 RootMultiplicity --influences--> ConvergenceRate
 Residual --measures--> RootEquationMismatch
 BracketWidth --measures--> BracketUncertainty
 Conditioning --quantifies--> RootSensitivity
 Verification --checks--> CandidateRoot
}

OPERATORS {
 ROOT_PROBLEM(f) := find_x_such_that_f(x)=0
 BISECTION_STEP(a,b) := c=(a+b)/2
 REGULA_FALSI_STEP(a,b,f) := c=(a*f(b)-b*f(a))/(f(b)-f(a))
 SECANT_STEP(x0,x1,f) := x2=x1-f(x1)*(x1-x0)/(f(x1)-f(x0))
 NEWTON_STEP(x,f) := x_next=x-f(x)/f_prime(x)
 MODIFIED_NEWTON_STEP(x,f,m) := x_next=x-m*f(x)/f_prime(x)
 HALLEY_STEP(x,f) := x_next=x-(2*f*f_prime)/(2*f_prime^2-f*f_second)
 FIXED_POINT_STEP(x,g) := x_next=g(x)
 RESIDUAL(f,x) := r=f(x)
}

AXIOMS {
 A1 = "A root x_star satisfies f(x_star)=0 within exact or declared approximate semantics."
 A2 = "Bracketing and open methods have different convergence and robustness properties."
 A3 = "Bisection provides robust convergence under continuity and sign-change assumptions."
 A4 = "Newton's local quadratic convergence requires sufficient smoothness, a simple root and sufficiently close initialisation."
 A5 = "Repeated roots reduce the convergence order of standard Newton iteration."
 A6 = "Residual magnitude and root-location error are distinct."
 A7 = "Root conditioning depends on local derivative magnitude and problem scaling."
 A8 = "Root-finding results require explicit stopping, verification and reproducibility semantics."
}

REASONING {
 R1_CONTEXT = identify(function,domain,continuity,differentiability,root_expectation,accuracy_goal)
 R2_INITIALISATION = choose(initial_bracket_or_initial_guess)
 R3_METHOD = select(bisection,false_position,secant,Newton,Halley,Brent,fixed_point_or_hybrid_method)
 R4_DERIVATIVES = obtain(required_derivative_information_if_needed)
 R5_ITERATE = generate_next_root_approximation)
 R6_BRACKET = if_bracketing update_interval_while_preserving_root_condition)
 R7_CONVERGENCE = monitor(residual,step_size,bracket_width,rate,stagnation_and_cycling)
 R8_MULTIPLICITY = detect_or_account_for_repeated_root_if_relevant)
 R9_CONDITIONING = assess(local_sensitivity,flatness,scaling_and_finite_precision)
 R10_VERIFY = substitute_candidate_into_original_function_and_check_domain_and_interval_information)
}

CONSTRAINTS {
 C1 = "A sign change does not detect roots of even multiplicity."
 C2 = "Bisection requires continuity and a valid sign-changing bracket for the standard guarantee."
 C3 = "Newton iteration can diverge or move outside the intended domain."
 C4 = "Secant iteration can fail when successive function values produce an unstable denominator."
 C5 = "Repeated roots can cause slow convergence for standard open methods."
 C6 = "Flat roots can be poorly conditioned."
 C7 = "Finite-difference derivatives introduce truncation and round-off tradeoffs."
 C8 = "Stopping on small step size alone can be misleading."
 C9 = "Stopping on small residual alone can be misleading for ill-conditioned roots."
 C10 = "Machine precision imposes a practical lower limit on distinguishable root updates."
}

SEMANTIC_EQUIVALENCE {
 "RootFinding" <=> "ZeroFinding"
 "NewtonRaphsonMethod" <=> "NewtonMethod"
 "FalsePositionMethod" <=> "RegulaFalsi"
 "RootBracket" <=> "BracketingInterval"
 "RepeatedRoot" <=> "MultipleRootInMultiplicityContext"
}

VALIDATION {
 V1 = "Original function and domain are explicit."
 V2 = "Initial bracket or initial guess is documented."
 V3 = "Method and derivative requirements are documented."
 V4 = "Stopping criteria are explicit."
 V5 = "Residual is evaluated using the original function."
 V6 = "Bracket validity is checked for bracketing methods."
 V7 = "Root multiplicity is considered when convergence is anomalous."
 V8 = "Conditioning and scaling are assessed where relevant."
 V9 = "Candidate root satisfies domain restrictions."
 V10 = "Results are reproducible under documented arithmetic and method settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 ROOT_FINDING_DEFINITION = 0.99
 BISECTION_REASONING = 0.99
 SECANT_REASONING = 0.99
 NEWTON_REASONING = 0.99
 BRENT_REASONING = 0.99
 MULTIPLICITY_REASONING = 0.98
 CONDITIONING_REASONING = 0.98
 POLICY = "Reduce confidence when continuity, differentiability, bracket validity, initial guess, root multiplicity, stopping criteria or arithmetic precision are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, RootFindingReasoning,
  BracketingReasoning, BisectionReasoning, RegulaFalsiReasoning,
  SecantReasoning, NewtonMethodReasoning, HalleyReasoning,
  BrentReasoning, FixedPointReasoning, RootMultiplicityReasoning,
  ConvergenceOrderReasoning, ResidualReasoning,
  RootConditioningReasoning, FinitePrecisionReasoning,
  VerificationReasoning, KnowledgeGraphConstruction,
  RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "root finding" -> RootFinding
  "zero finding" -> RootFinding
  "Newton-Raphson" -> NewtonMethod
  "false position" -> RegulaFalsi
  "root bracket" -> RootBracket
 }
}

EXECUTION_RULES {
 E1 = "If the task is to determine x such that f(x)=0, activate RootFindingOntology."
 E2 = "If a valid sign-changing bracket is available and robustness is prioritised, consider bisection or a hybrid bracketing method."
 E3 = "If derivative information and a good initial guess are available, consider Newton's method."
 E4 = "If derivatives are unavailable, consider secant, Brent or other derivative-free methods."
 E5 = "If the root is repeated, use multiplicity-aware reasoning or a modified method."
 E6 = "For bracketing methods, preserve interval invariants."
 E7 = "For open methods, monitor domain violations and divergence."
 E8 = "Use residual, step size and bracket width together when appropriate."
 E9 = "Verify the returned root against the original function and domain."
}

RECURSION {
 ENTRY = RootFinding
 EXPAND(RootFinding) -> [
  RootSolver,ZeroFinding,ZeroOfFunction,Root,ScalarEquation,
  NonlinearEquation,ContinuousFunction,DifferentiableFunction,
  InitialGuess,InitialBracket,RootBracket,SignChange,
  IntermediateValueTheorem,BracketingMethod,OpenMethod,HybridMethod,
  BisectionMethod,RegulaFalsi,IllinoisMethod,PegasusMethod,
  SecantMethod,NewtonMethod,ModifiedNewtonMethod,HalleyMethod,
  HouseholderMethod,FixedPointIteration,SteffensenMethod,BrentMethod,
  RidderMethod,MullerMethod,InverseQuadraticInterpolation,
  PolynomialRootFinding,MultipleRoot,RepeatedRoot,SimpleRoot,
  RootMultiplicity,RootSeparation,BasinOfAttraction,BracketWidth,
  Residual,AbsoluteResidual,RelativeResidual,StepSize,
  FunctionTolerance,StepTolerance,AbsoluteTolerance,RelativeTolerance,
  StoppingCriterion,MaximumIterations,Convergence,ConvergenceRate,
  LinearConvergence,SuperlinearConvergence,QuadraticConvergence,
  CubicConvergence,Divergence,Stagnation,Cycling,Derivative,
  FirstDerivative,SecondDerivative,DerivativeFreeMethod,
  NumericalDerivative,Conditioning,RootConditionNumber,Sensitivity,
  FlatRoot,SteepRoot,RoundOffError,TruncationError,MachinePrecision,
  FloatingPointArithmetic,Scaling,VariableTransformation,Deflation,
  Verification,IntervalVerification,ReferenceRoot,Benchmarking,
  Reproducibility
 ]
 EXPAND(RootFindingFamilies) -> [
  BracketingMethods,
  OpenMethods,
  NewtonFamilyMethods,
  DerivativeFreeMethods,
  HybridRootMethods,
  MultipleRootMethods,
  RootVerification
 ]
 STOP_CONDITION = "Stop when root problem, initialisation, method, convergence, multiplicity, conditioning and verification are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Nonlinear Solver Ontology"
 RELATED_ONTOLOGIES = [
  "Nonlinear Solver Ontology",
  "Equation Solver Ontology",
  "Solving Equations",
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Error Ontology",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology",
  "Floating Point Arithmetic Ontology",
  "Machine Precision Ontology"
 ]
 ROUTE_RULES = [
  "Root Finding -> Nonlinear Solver for parent nonlinear-solver semantics",
  "Root Finding -> Equation Solver for generic solver configuration and status",
  "Root Finding -> Numerical Methods for root algorithms",
  "Root Finding -> Numerical Analysis for convergence and conditioning",
  "Root Finding -> Numerical Error for residual and root-location error",
  "Root Finding -> Numerical Stability for finite-precision behaviour",
  "Root Finding -> Numerical Convergence for convergence order and stopping",
  "Root Finding -> Floating Point Arithmetic for round-off limitations"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible root-finding methods, safeguards or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve bracketing-versus-open-method distinction.",
  "Preserve simple-root-versus-multiple-root distinction.",
  "Preserve residual-versus-root-error distinction.",
  "Preserve derivative-based-versus-derivative-free distinction.",
  "Preserve local-convergence-versus-global-robustness distinction.",
  "Preserve exact-root-versus-approximate-root distinction.",
  "Preserve original-function-versus-transformed-function distinction.",
  "Preserve machine-readable root-finding semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Root finding computes scalar values x for which f(x)=0."
 BRACKETING_SUMMARY = "Bisection and false-position methods preserve intervals containing roots under suitable assumptions."
 OPEN_SUMMARY = "Secant, Newton, Halley and related methods use local information for faster convergence without necessarily preserving a bracket."
 HYBRID_SUMMARY = "Brent and related methods combine robust bracketing with interpolation-based acceleration."
 MULTIPLICITY_SUMMARY = "Repeated roots alter local convergence and may require modified iterations."
 CONDITIONING_SUMMARY = "Root sensitivity depends strongly on local derivative magnitude and scaling."
 VALIDATION_SUMMARY = "Root-finding results should be checked using residuals, stopping criteria, bracket or step information, conditioning and reproducibility."
}

FLOW {
 INPUT
 -> detect_root_finding_context
 -> identify_function_domain_continuity_differentiability_root_expectation_and_accuracy_goal
 -> choose_initial_bracket_or_initial_guess
 -> select_bisection_regula_falsi_secant_Newton_Halley_Brent_fixed_point_or_hybrid_method
 -> obtain_derivatives_if_required
 -> generate_next_root_approximation
 -> if_bracketing_update_interval_and_preserve_invariant
 -> monitor_residual_step_size_bracket_width_convergence_rate_stagnation_and_cycling
 -> detect_or_account_for_root_multiplicity_if_needed
 -> assess_conditioning_scaling_roundoff_and_machine_precision
 -> verify_candidate_against_original_function_domain_and_interval_information
 -> route_to_related_nonlinear_solver_equation_solver_and_numerical_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Root Finding Ontology 2 defines computational methods for locating zeros of scalar functions. It supports roots and zero finding, initial guesses and brackets, sign changes and the intermediate value theorem, bisection, regula falsi, Illinois and Pegasus variants, secant, Newton, modified Newton, Halley and Householder methods, fixed-point and Steffensen iteration, Brent, Ridder, Muller and inverse quadratic interpolation, polynomial roots, simple and multiple roots, basins of attraction, residual and bracket metrics, stopping tolerances, convergence order, derivative and derivative-free methods, root conditioning, flat and steep roots, truncation and round-off effects, machine precision, scaling, deflation, verification, benchmarking and reproducibility."
}

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

}

END_FLOW