Root Finding Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Root Finding Ontology within the Kireth Research Semantic Library. Root finding studies numerical and analytical procedures for locating values at which a function, equation or nonlinear system equals zero. This ontology supports bracketing methods, open methods, fixed-point iteration, scalar and multidimensional roots, convergence rates, residuals, stopping criteria, multiplicity, conditioning, initialisation, safeguards, derivative use, hybrid methods and relationships with numerical analysis, nonlinear equations, optimisation and scientific computing.

FLOW_ALGEBRA_RECORD {

METADATA {
 FLOW_NAME = "Root Finding Ontology"
 FLOW_TYPE = "Mathematical Ontology"
 DOMAIN = "Mathematics"
 SUBDOMAIN = "Applied Mathematics"
 SPECIALISATION = "Numerical Analysis / Root Finding"
 CANONICAL_PAGE = "https://kirethresearch.org/booksai-core/ontologies/mathematical-ontologies/applied-mathematics-ontologies/numerical-analysis/root-finding-ontology.html"
 LANGUAGE = "en-GB"
 VERSION = "1.0"
 STATUS = "active"
}

IDENTITY {
 PRIMARY_ENTITY = RootFinding
 SYMBOLIC_FORMS = [
  "f(x)=0",
  "F(x)=0",
  "x_{n+1}=g(x_n)"
 ]
 ENTITY_CLASS = NonlinearEquationSolutionFramework
 PRIMARY_CONTEXT = NumericalAnalysis
 DEFINITION = "Root finding is the process of locating values at which a scalar function or nonlinear system evaluates to zero."
 SEMANTIC_ROLE = "Provides the machine-readable framework for bracketing, fixed-point, Newton, secant, hybrid and multidimensional nonlinear-equation solution methods."
}

SCOPE {
 INCLUDE = [
  RootFinding,
  Root,
  ZeroOfFunction,
  NonlinearEquation,
  NonlinearSystem,
  ScalarRoot,
  VectorRoot,
  BracketingMethod,
  OpenMethod,
  BisectionMethod,
  RegulaFalsi,
  IllinoisMethod,
  BrentMethod,
  RidderMethod,
  NewtonMethod,
  ModifiedNewtonMethod,
  SecantMethod,
  FixedPointIteration,
  MultidimensionalNewtonMethod,
  Jacobian,
  InitialGuess,
  Bracket,
  SignChange,
  Residual,
  StepError,
  StoppingCriterion,
  AbsoluteTolerance,
  RelativeTolerance,
  IterationLimit,
  Convergence,
  ConvergenceRate,
  LinearConvergence,
  SuperlinearConvergence,
  QuadraticConvergence,
  RootMultiplicity,
  Conditioning,
  SafeguardedMethod,
  HybridMethod
 ]

 EXCLUDE_AS_PRIMARY = [
  GlobalOptimisationWithoutEquationZeroContext,
  PolynomialFactorisationWithoutRootSolutionGoal,
  SymbolicEquationSolvingWithoutNumericalRootContext,
  EigenvalueProblemsUnlessRecastAsRootProblems
 ]

 DISAMBIGUATION_RULE =
  "When the task is to determine x such that f(x)=0 or F(x)=0, interpret it as root finding."
}

CORE_CONCEPTS {

 RootFinding {
  definition = "The process of solving nonlinear equations by locating function zeros."
 }

 Root {
  definition = "A value x_star satisfying f(x_star)=0, or F(x_star)=0 for a nonlinear system."
 }

 Bracket {
  definition = "An interval or region known to contain a root under stated continuity and sign-change conditions."
 }

 BracketingMethod {
  definition = "A root-finding method maintaining an interval containing a root."
 }

 OpenMethod {
  definition = "A root-finding method that does not necessarily maintain a guaranteed bracket."
 }

 BisectionMethod {
  definition = "A bracketing method repeatedly halving an interval with a sign change."
 }

 NewtonMethod {
  definition = "An open method using local linearisation x_{n+1}=x_n-f(x_n)/f'(x_n)."
 }

 SecantMethod {
  definition = "A derivative-free open method approximating the derivative with a secant slope."
 }

 FixedPointIteration {
  definition = "A method rewriting f(x)=0 as x=g(x) and iterating x_{n+1}=g(x_n)."
 }

 BrentMethod {
  definition = "A safeguarded hybrid method combining bracketing with interpolation-based steps."
 }

 RootMultiplicity {
  definition = "The number of times a root is repeated in the local factorisation of a function."
 }

 Conditioning {
  definition = "Sensitivity of a root location to perturbations in the defining function or data."
 }
}

RELATIONS {
 RootFinding --is_branch_of--> NumericalAnalysis
 RootFinding --solves--> NonlinearEquation
 ScalarRoot --is_special_case_of--> Root
 VectorRoot --is_special_case_of--> Root
 BisectionMethod --is_type_of--> BracketingMethod
 RegulaFalsi --is_type_of--> BracketingMethod
 BrentMethod --is_type_of--> HybridMethod
 NewtonMethod --is_type_of--> OpenMethod
 SecantMethod --is_type_of--> OpenMethod
 FixedPointIteration --is_type_of--> OpenMethod
 ModifiedNewtonMethod --handles--> MultipleRoot
 MultidimensionalNewtonMethod --uses--> Jacobian
 Bracket --may_be_defined_by--> SignChange
 Residual --measures--> EquationSatisfaction
 RootMultiplicity --affects--> ConvergenceRate
 Conditioning --affects--> RootSensitivity
 SafeguardedMethod --combines--> RobustnessAndSpeed
}

OPERATORS {
 ROOT_CONDITION(f,x) :=
  f(x)=0

 BISECTION_STEP(a,b,f) :=
  m=(a+b)/2
  choose [a,m] or [m,b] preserving sign_change
  under continuity_and_sign_change assumptions

 NEWTON_STEP(x,f,fprime) :=
  x-f(x)/fprime(x)
  WHEN fprime(x)!=0

 SECANT_STEP(x0,x1,f) :=
  x1-f(x1)*(x1-x0)/(f(x1)-f(x0))
  WHEN f(x1)!=f(x0)

 FIXED_POINT_STEP(x,g) :=
  g(x)

 MULTIVARIATE_NEWTON_STEP(x,F,J) :=
  x - J(x)^(-1)F(x)
  when J(x) is nonsingular
  or solve J(x)*delta=-F(x) and set x_new=x+delta

 RESIDUAL(f,x) :=
  abs(f(x))

 VECTOR_RESIDUAL(F,x) :=
  norm(F(x))

 RELATIVE_STEP(x_new,x_old) :=
  norm(x_new-x_old)/max(1,norm(x_new))

 CHECK_STOP(residual,step,tol_f,tol_x) :=
  residual<=tol_f AND step<=tol_x
  under declared stopping rule

 ROOT_CONDITION_NUMBER(f,x_star) :=
  approximately 1/abs(f'(x_star))
  for simple scalar root under local perturbation model
}

DEFINITIONS {
 D1 = "A root is a point where the function or nonlinear system equals zero."
 D2 = "Bracketing methods trade speed for robustness."
 D3 = "Open methods can converge faster but may fail without suitable initialisation."
 D4 = "Bisection converges linearly."
 D5 = "Newton's method is locally quadratic for simple roots under standard smoothness assumptions."
 D6 = "Secant iteration is typically superlinear for simple roots."
 D7 = "Multiple roots reduce the convergence order of standard Newton iteration."
 D8 = "Fixed-point convergence depends on the local contraction properties of g."
 D9 = "Small residual does not always imply small root error for ill-conditioned roots."
 D10 = "Stopping criteria should consider both residual and step size where appropriate."
}

AXIOMS {
 A1_ROOT:
  x_star is a root iff f(x_star)=0

 A2_BRACKETING:
  For continuous scalar f, a sign change on [a,b] guarantees at least one root in [a,b]

 A3_BISECTION:
  Bisection reduces bracket width by factor 2 each iteration

 A4_NEWTON_LOCAL:
  Newton iteration is locally quadratically convergent to a simple root under suitable differentiability and initialisation assumptions

 A5_SECANT_LOCAL:
  Secant iteration is locally superlinearly convergent to a simple root under suitable assumptions

 A6_FIXED_POINT:
  A contraction mapping has a unique local fixed point and fixed-point iteration converges to it

 A7_MULTIPLICITY:
  Root multiplicity alters local convergence behaviour

 A8_RESIDUAL_CONTEXT:
  Residual-based stopping must be interpreted in light of conditioning
}

REASONING {

 R1_ROOT_PROBLEM_CLASSIFICATION {
  INPUT = equation_or_system
  IDENTIFY = scalar_or_vector
  IDENTIFY = continuity_and_smoothness
  IDENTIFY = derivative_or_Jacobian availability
  IDENTIFY = bracket_or_initial_guess availability
  RETURN = root_problem_class
 }

 R2_METHOD_SELECTION {
  INPUT = root_problem_class
  IF scalar_and_sign_change_bracket_available
   CONSIDER = Bisection_Brent_RegulaFalsi
  IF derivative_available_and_good_initial_guess
   CONSIDER = Newton
  IF derivative_unavailable_but_two_guesses_available
   CONSIDER = Secant
  IF fixed_point_reformulation_is_contracting
   CONSIDER = FixedPointIteration
  IF multidimensional
   CONSIDER = Newton_or_quasiNewton_system method
  RETURN = root_finding_strategy
 }

 R3_BISECTION {
  INPUT = [a,b],f
  VERIFY = continuity_and_sign_change
  REPEAT = interval_halving
  UNTIL = width_or_residual criterion
  RETURN = root_approximation
 }

 R4_NEWTON {
  INPUT = x0,f,fprime
  REPEAT
   CHECK = derivative_not_too_small
   UPDATE = NewtonStep
  UNTIL = stopping criterion
  RETURN = root_approximation
 }

 R5_SECANT {
  INPUT = x0,x1,f
  REPEAT
   CHECK = denominator_not_too_small
   UPDATE = SecantStep
  UNTIL = stopping criterion
  RETURN = root_approximation
 }

 R6_FIXED_POINT {
  INPUT = g,x0
  ASSESS = local_contraction
  ITERATE = x_{n+1}=g(x_n)
  RETURN = fixed_point_or_divergence profile
 }

 R7_MULTIPLE_ROOT {
  INPUT = candidate_root_and_function
  ESTIMATE = multiplicity
  IF multiplicity_known
   APPLY = modified_Newton update
  RETURN = multiplicity_aware_root_solution
 }

 R8_MULTIDIMENSIONAL_NEWTON {
  INPUT = F,J,x0
  REPEAT
   SOLVE = J(x_k)*delta=-F(x_k)
   UPDATE = x_k+delta
   CHECK = residual_step_and_Jacobian conditioning
  RETURN = vector_root
 }

 R9_CONDITIONING_ANALYSIS {
  INPUT = root_and_function
  ANALYSE = derivative_or_Jacobian sensitivity
  RETURN = root_conditioning_profile
 }
}

CONSTRAINTS {
 C1 = "Sign-change bracketing requires continuity for the standard guarantee."
 C2 = "A sign change guarantees at least one root, not necessarily exactly one."
 C3 = "Even-multiplicity roots may not produce a sign change."
 C4 = "Newton's method may diverge or cycle from poor initial guesses."
 C5 = "Newton steps are unsafe when derivatives or Jacobians are singular or nearly singular."
 C6 = "Secant steps fail when successive function values are equal or nearly equal."
 C7 = "Fixed-point iteration requires a suitable reformulation and local contraction."
 C8 = "Small residual does not guarantee small root error for poorly conditioned roots."
 C9 = "Stopping tolerances must reflect problem scaling."
 C10 = "Multidimensional root finding can converge to different roots from different starting points."
}

SEMANTIC_EQUIVALENCE {
 "RootFinding" <=> "ZeroFinding"
 "Root" <=> "ZeroOfFunction"
 "BisectionMethod" <=> "IntervalHalvingRootMethod"
 "NewtonMethod" <=> "NewtonRaphsonMethod"
 "SecantMethod" <=> "DerivativeFreeSecantRootMethod"
 "FixedPointIteration" <=> "SuccessiveSubstitution"
 "HybridMethod" <=> "SafeguardedCombinedRootMethod"
}

VALIDATION {
 V1 = "Equation or nonlinear system is identified."
 V2 = "Scalar versus vector structure is known."
 V3 = "Bracket validity is checked where used."
 V4 = "Derivative or Jacobian assumptions are checked."
 V5 = "Stopping tolerances are explicit."
 V6 = "Residual and step criteria are interpreted together where appropriate."
 V7 = "Multiplicity is considered when convergence degrades."
 V8 = "Conditioning is considered before translating residual into root error."
 V9 = "Iteration limit is present."
 V10 = "Approximate root status is preserved."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 ROOT_FINDING_DEFINITION = 0.99
 METHOD_SELECTION_REASONING = 0.99
 BISECTION_REASONING = 0.99
 NEWTON_REASONING = 0.98
 SECANT_REASONING = 0.98
 FIXED_POINT_REASONING = 0.98
 MULTIDIMENSIONAL_REASONING = 0.97
 CONDITIONING_REASONING = 0.98

 POLICY =
  "Reduce confidence when continuity, smoothness, bracket validity, derivative information, initialisation, multiplicity, conditioning or stopping tolerances are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  RootFindingReasoning,
  NonlinearEquationReasoning,
  BisectionReasoning,
  NewtonReasoning,
  SecantReasoning,
  FixedPointReasoning,
  BrentMethodReasoning,
  HybridMethodReasoning,
  MultidimensionalRootReasoning,
  JacobianReasoning,
  RootConditioningReasoning,
  StoppingCriterionReasoning,
  ConvergenceAnalysis,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "root finding" -> RootFinding
  "root-finding" -> RootFinding
  "zero finding" -> RootFinding
  "zero of a function" -> Root
  "bisection method" -> BisectionMethod
  "Newton-Raphson" -> NewtonMethod
  "Newton's method" -> NewtonMethod
  "secant method" -> SecantMethod
  "fixed-point iteration" -> FixedPointIteration
  "Brent's method" -> BrentMethod
  "nonlinear system" -> NonlinearSystem
 }

 INTERPRETATION_ORDER = [
  detect_root_finding_context,
  identify scalar_or_vector_equation_continuity_smoothness_derivative_information_bracket_and_initial_guesses,
  classify bracketing_open_fixed_point_hybrid_or_multidimensional pathway,
  select numerical_method,
  iterate with safeguards_and_stopping criteria,
  assess residual_step_convergence_multiplicity_and_conditioning,
  verify method assumptions,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("root finding")
  OR asks_to_solve_f_of_x_equals_zero_numerically
  THEN activate(RootFindingOntology)

 E2:
  IF scalar_continuous_function_and_sign_change_interval
  THEN prefer robust_bracketing_or_hybrid method

 E3:
  IF derivative_available_and_initial_guess_is_suitable
  THEN consider NewtonMethod

 E4:
  IF derivative_unavailable_and_two_guesses_available
  THEN consider SecantMethod

 E5:
  IF even_multiplicity_suspected
  THEN do_not rely_on sign_change bracketing

 E6:
  IF derivative_or_Jacobian_nearly_singular
  THEN safeguard_or_switch_method

 E7:
  IF multidimensional_system
  THEN solve linearised_Jacobian system rather_than explicitly invert when practical

 E8:
  IF stopping_based_on_residual
  THEN consider root_conditioning

 E9:
  IF fast_method_loses_safeguard
  THEN prefer hybrid_method when robustness_is important
}

RECURSION {
 ENTRY = RootFinding

 EXPAND(RootFinding) -> [
  Root,
  ZeroOfFunction,
  NonlinearEquation,
  NonlinearSystem,
  ScalarRoot,
  VectorRoot,
  BracketingMethod,
  OpenMethod,
  BisectionMethod,
  RegulaFalsi,
  IllinoisMethod,
  BrentMethod,
  RidderMethod,
  NewtonMethod,
  ModifiedNewtonMethod,
  SecantMethod,
  FixedPointIteration,
  MultidimensionalNewtonMethod,
  Jacobian,
  InitialGuess,
  Bracket,
  SignChange,
  Residual,
  StoppingCriterion,
  Convergence,
  ConvergenceRate,
  RootMultiplicity,
  Conditioning,
  SafeguardedMethod,
  HybridMethod
 ]

 EXPAND(BracketingMethods) -> [
  BisectionMethod,
  RegulaFalsi,
  IllinoisMethod,
  BrentMethod,
  RidderMethod
 ]

 EXPAND(OpenMethods) -> [
  NewtonMethod,
  ModifiedNewtonMethod,
  SecantMethod,
  FixedPointIteration
 ]

 EXPAND(ConvergenceStructure) -> [
  LinearConvergence,
  SuperlinearConvergence,
  QuadraticConvergence,
  RootMultiplicity,
  InitialisationSensitivity
 ]

 STOP_CONDITION =
  "Stop when the equation, root type, selected method, initialisation, bracket or derivative information, stopping criteria, convergence, multiplicity and conditioning are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Numerical Analysis"

 IMMEDIATE_CONTEXTS = [
  "Numerical Analysis Ontology",
  "Numerical Methods Ontology",
  "Nonlinear Equation Ontologies",
  "Scientific Computing Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Numerical Analysis Ontology",
  "Numerical Methods Ontology",
  "Numerical Analysis",
  "Applied Mathematics Ontologies",
  "Algebra Ontologies",
  "Calculus & Analysis Ontologies",
  "Nonlinear Equation Ontologies",
  "Numerical Differentiation Ontology",
  "Linear Algebra Ontologies",
  "Optimisation Ontologies",
  "Scientific Computing Ontologies",
  "Model Verification Ontology"
 ]

 ROUTE_RULES = [
  "Root Finding -> Numerical Analysis Ontology for numerical semantics",
  "Root Finding -> Numerical Methods Ontology for solver selection",
  "Root Finding -> Algebra for equation structure",
  "Root Finding -> Calculus & Analysis for continuity and derivative reasoning",
  "Root Finding -> Numerical Differentiation for derivative approximation",
  "Root Finding -> Linear Algebra for multidimensional Newton systems",
  "Root Finding -> Optimisation for closely related stationary-point methods",
  "Root Finding -> Scientific Computing for implementation and large systems",
  "Root Finding -> Model Verification for residual and convergence checks"
 ]
}

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 zero-of-function semantics.",
  "Preserve bracketing-versus-open distinction.",
  "Preserve continuity-dependent bracketing guarantees.",
  "Preserve initialisation sensitivity.",
  "Preserve multiplicity-aware convergence semantics.",
  "Preserve residual-versus-root-error distinction.",
  "Preserve multidimensional Jacobian semantics.",
  "Preserve machine-readable root-finding semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "Root finding locates scalar or vector values at which a function or nonlinear system evaluates to zero."

 BRACKETING_SUMMARY =
  "Bracketing methods maintain an interval containing a root under suitable continuity and sign-change conditions."

 BISECTION_SUMMARY =
  "Bisection is robust and linearly convergent, reducing the bracket width by half each iteration."

 NEWTON_SUMMARY =
  "Newton's method uses derivative information and is locally quadratically convergent for simple roots under standard assumptions."

 SECANT_SUMMARY =
  "The secant method approximates Newton behaviour without explicit derivatives and is typically superlinearly convergent."

 FIXED_POINT_SUMMARY =
  "Fixed-point iteration converges when the reformulated map is locally contractive."

 MULTIPLICITY_SUMMARY =
  "Repeated roots can reduce standard Newton convergence order and may require modified updates."

 CONDITIONING_SUMMARY =
  "Root sensitivity depends on local derivatives or Jacobian conditioning."

 STOPPING_SUMMARY =
  "Reliable stopping should consider residual, step size, scaling and conditioning."
}

FLOW {
 INPUT
 -> detect_root_finding_context
 -> identify scalar_or_vector_equation_continuity_smoothness_derivative_or_Jacobian_information_bracket_initial_guesses_and_tolerances
 -> classify bracketing_open_fixed_point_hybrid_or_multidimensional problem
 -> select compatible root_finding method
 -> initialise bracket_or_iterates
 -> perform iterations_with_safeguards
 -> compute residual_step_size_and_convergence indicators
 -> assess root_multiplicity_and_conditioning
 -> verify assumptions_and_stopping criteria
 -> route to numerical_analysis_ontology numerical_methods algebra calculus nonlinear_equations numerical_differentiation linear_algebra optimisation scientific_computing_or_model_verification ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Root Finding Ontology defines numerical solution of scalar and multidimensional nonlinear equations. It supports bracketing and open methods, bisection, regula falsi, Brent, Newton, secant, fixed-point and multidimensional Newton methods, initialisation, brackets, residuals, stopping criteria, convergence rates, root multiplicity, conditioning, safeguards and hybrid strategies."
}

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

}

END_FLOW