Newton-Raphson Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Newton-Raphson Ontology within the Kireth Research Semantic Library. Newton-Raphson is a derivative-based iterative method for solving scalar nonlinear equations and, through Jacobian linearisation, nonlinear systems. This ontology supports tangent-based iteration, local convergence, quadratic convergence at simple roots, multiple-root behaviour, damping and safeguarding, derivative and Jacobian computation, Newton steps, inexact Newton variants, conditioning, residuals, finite precision, stopping criteria, failure modes and verification.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = NewtonRaphsonMethod
 ENTITY_CLASS = DerivativeBasedNonlinearRootIterationFramework
 PRIMARY_CONTEXT = RootFinding
 DEFINITION = "Newton-Raphson is an iterative method that updates an approximation using a local first-order linearisation of a nonlinear equation or nonlinear system."
 SYMBOLIC_FORMS = [
  "x_(k+1)=x_k-f(x_k)/f'(x_k)",
  "J(x_k)*delta_k=-F(x_k)",
  "x_(k+1)=x_k+delta_k",
  "x_(k+1)=x_k-alpha_k*f(x_k)/f'(x_k)"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for Newton iteration, tangent linearisation, Jacobian-based system solving, local convergence, damping, safeguarding, inexact solves, conditioning, finite precision and verification."
}

SCOPE {
 INCLUDE = [
  NewtonRaphsonMethod, NewtonMethod, ScalarNewtonMethod,
  MultivariableNewtonMethod, NewtonSystemMethod, NewtonIteration,
  NewtonStep, TangentMethod, Linearisation, LocalLinearModel,
  NonlinearEquation, NonlinearSystem, Root, SimpleRoot, MultipleRoot,
  RepeatedRoot, RootMultiplicity, InitialGuess, CurrentIterate,
  NextIterate, FunctionValue, Residual, ResidualNorm,
  FirstDerivative, Derivative, Jacobian, JacobianMatrix,
  ExactDerivative, NumericalDerivative, FiniteDifferenceDerivative,
  AutomaticDifferentiation, SymbolicDerivative, SecantApproximation,
  ModifiedNewtonMethod, MultiplicityCorrectedNewton,
  DampedNewtonMethod, SafeguardedNewtonMethod, GlobalisedNewtonMethod,
  LineSearchNewton, TrustRegionNewton, InexactNewtonMethod,
  NewtonKrylovMethod, JacobianFreeNewtonKrylov, JFNK,
  QuasiNewtonMethod, BroydenMethod, NewtonCorrection,
  SearchDirection, StepLength, DampingFactor, MeritFunction,
  LineSearch, TrustRegion, StepAcceptance, ForcingTerm,
  InnerLinearSolver, LinearSystem, Preconditioner,
  BacktrackingLineSearch, ArmijoCondition, WolfeCondition,
  Convergence, LocalConvergence, QuadraticConvergence,
  SuperlinearConvergence, LinearConvergence, ConvergenceRate,
  BasinOfAttraction, Divergence, Oscillation, Cycling, Stagnation,
  Breakdown, ZeroDerivative, SmallDerivative, SingularJacobian,
  NearlySingularJacobian, IllConditionedJacobian,
  ConditionNumber, Conditioning, RootConditioning,
  Sensitivity, Scaling, VariableScaling, EquationScaling,
  ForwardError, BackwardError, ResidualError,
  RoundOffError, TruncationError, FloatingPointArithmetic,
  MachinePrecision, Cancellation, Overflow, Underflow,
  AbsoluteTolerance, RelativeTolerance, ResidualTolerance,
  StepTolerance, StoppingCriterion, MaximumIterations,
  MaximumEvaluations, SolverStatus, Success, Failure, Warning,
  Verification, SubstitutionCheck, ReferenceRoot,
  Benchmarking, Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  SecantMethodWithoutDerivativeNewtonSemantics,
  BisectionMethodWithoutNewtonStep,
  LinearSolverWithoutNonlinearLinearisationContext,
  OptimisationNewtonMethodWhenNoEquationRootIsBeingSolved
 ]
 DISAMBIGUATION_RULE = "When a nonlinear equation is solved by repeated local linearisation using a derivative or Jacobian, interpret the context as Newton-Raphson."
}

CORE_CONCEPTS {
 NewtonRaphsonMethod = "Derivative-based iteration using a local linear approximation to compute a correction toward a root."
 NewtonStep = "Correction obtained by solving the scalar derivative equation or Jacobian linear system."
 SimpleRoot = "Root with nonzero first derivative in the scalar case."
 MultipleRoot = "Root with multiplicity greater than one, often reducing standard Newton convergence."
 DampedNewtonMethod = "Newton method using a step factor smaller than one or otherwise controlled."
 InexactNewtonMethod = "Newton method in which the linearised system is solved only approximately."
 BasinOfAttraction = "Set of starting values converging to a particular root under Newton iteration."
 SingularJacobian = "Jacobian lacking local invertibility and potentially preventing a standard Newton step."
}

RELATIONS {
 NewtonRaphsonMethod --is_child_of--> RootFinding
 NewtonRaphsonMethod --is_type_of--> NonlinearSolver
 NewtonRaphsonMethod --uses--> FirstDerivative
 MultivariableNewtonMethod --uses--> Jacobian
 NewtonRaphsonMethod --produces--> NewtonStep
 NewtonStep --comes_from--> LocalLinearisation
 NewtonStep --updates--> CurrentIterate
 SimpleRoot --supports_under_conditions--> QuadraticConvergence
 MultipleRoot --reduces--> StandardNewtonConvergenceRate
 MultiplicityCorrectedNewton --improves--> MultipleRootConvergence
 DampedNewtonMethod --uses--> DampingFactor
 LineSearchNewton --uses--> LineSearch
 TrustRegionNewton --uses--> TrustRegion
 InexactNewtonMethod --uses--> InnerLinearSolver
 NewtonKrylovMethod --uses--> KrylovMethod
 JacobianFreeNewtonKrylov --avoids_explicit--> JacobianAssembly
 SingularJacobian --can_cause--> NewtonBreakdown
 RootConditioning --influences--> SolutionSensitivity
 Verification --checks--> NewtonCandidateRoot
}

OPERATORS {
 NEWTON_SCALAR(x,f) := x_next=x-f(x)/f_prime(x)
 NEWTON_CORRECTION_SCALAR(x,f) := delta=-f(x)/f_prime(x)
 NEWTON_SYSTEM(x,F,J) := solve(J(x)*delta=-F(x)); x_next=x+delta
 DAMPED_NEWTON(x,delta,alpha) := x_next=x+alpha*delta
 MULTIPLICITY_NEWTON(x,f,m) := x_next=x-m*f(x)/f_prime(x)
 RESIDUAL(f,x) := r=f(x)
 SYSTEM_RESIDUAL(F,x) := r=F(x)
 RELATIVE_RESIDUAL(F,x,scale) := ||F(x)||/scale
}

AXIOMS {
 A1 = "Newton-Raphson is based on first-order local linearisation."
 A2 = "At a sufficiently close initial guess and a simple root, standard Newton iteration is locally quadratic under suitable smoothness."
 A3 = "A zero or very small derivative can make a scalar Newton step undefined or unstable."
 A4 = "A singular or ill-conditioned Jacobian can make a system Newton step unreliable."
 A5 = "Standard Newton iteration can converge to different roots from different initial guesses."
 A6 = "Multiple roots generally reduce standard Newton convergence below quadratic."
 A7 = "Residual and root-location error are distinct."
 A8 = "Newton-Raphson results require explicit initialisation, stopping, termination and verification semantics."
}

REASONING {
 R1_CONTEXT = identify(scalar_or_system_problem,function_or_residual,domain,derivative_availability,accuracy_goal)
 R2_INITIALISE = choose(initial_guess_and_scaling)
 R3_DERIVATIVE = obtain(exact_symbolic_AD_finite_difference_or_approximate_derivative_or_Jacobian)
 R4_LINEARISE = construct_local_first_order_model_at_current_iterate
 R5_STEP = compute_Newton_correction)
 R6_GLOBALISE = if_needed apply(damping,line_search,trust_region_or_safeguard)
 R7_UPDATE = form_next_iterate)
 R8_CONVERGENCE = monitor(residual,step_norm,rate,stagnation,oscillation_and_breakdown)
 R9_CONDITIONING = assess(derivative_or_Jacobian_conditioning,root_multiplicity,scaling_and_roundoff)
 R10_VERIFY = substitute_candidate_into_original_equation_and_check_domain_constraints_and_reproducibility)
}

CONSTRAINTS {
 C1 = "Newton-Raphson can diverge from a poor initial guess."
 C2 = "A derivative equal or close to zero can produce an unbounded or unstable Newton step."
 C3 = "Finite-difference derivatives introduce truncation-roundoff tradeoffs."
 C4 = "Repeated roots can reduce convergence to linear in the standard scalar method."
 C5 = "A full Newton step can overshoot or leave the intended domain."
 C6 = "Damping and line search improve robustness but can reduce local speed."
 C7 = "A small residual does not guarantee a small forward error for ill-conditioned roots."
 C8 = "Inexact Newton methods require inner linear-solve accuracy compatible with outer convergence."
 C9 = "Jacobian-free methods still depend on accurate directional residual differences."
 C10 = "Stopping tolerances below attainable finite precision can cause stagnation."
}

SEMANTIC_EQUIVALENCE {
 "NewtonRaphsonMethod" <=> "NewtonMethod"
 "DampedNewtonMethod" <=> "UnderrelaxedNewtonMethod"
 "JacobianFreeNewtonKrylov" <=> "JFNK"
 "MultiplicityCorrectedNewton" <=> "ModifiedNewtonForKnownMultiplicity"
 "NewtonCorrection" <=> "NewtonStep"
}

VALIDATION {
 V1 = "Original nonlinear equation or system is explicit."
 V2 = "Initial guess is documented."
 V3 = "Derivative or Jacobian source is documented."
 V4 = "Residual and step stopping criteria are documented."
 V5 = "Damping, line-search or trust-region settings are documented where used."
 V6 = "Derivative zeros or Jacobian singularity are monitored."
 V7 = "Root multiplicity is considered when convergence order is abnormal."
 V8 = "Conditioning and scaling are assessed where relevant."
 V9 = "Candidate roots satisfy the original equation, domain and constraints."
 V10 = "Results are reproducible under documented arithmetic and solver settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 NEWTON_RAPHSON_DEFINITION = 0.99
 SCALAR_NEWTON_REASONING = 0.99
 SYSTEM_NEWTON_REASONING = 0.99
 QUADRATIC_CONVERGENCE_REASONING = 0.99
 MULTIPLE_ROOT_REASONING = 0.98
 GLOBALISATION_REASONING = 0.99
 INEXACT_NEWTON_REASONING = 0.98
 CONDITIONING_REASONING = 0.98
 POLICY = "Reduce confidence when initial guess, derivative quality, Jacobian conditioning, multiplicity, globalisation, stopping criteria or arithmetic precision are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, NewtonRaphsonReasoning,
  NewtonStepReasoning, ScalarNewtonReasoning, SystemNewtonReasoning,
  JacobianReasoning, QuadraticConvergenceReasoning,
  MultipleRootReasoning, DampedNewtonReasoning,
  LineSearchNewtonReasoning, TrustRegionNewtonReasoning,
  InexactNewtonReasoning, NewtonKrylovReasoning, JFNKReasoning,
  BasinOfAttractionReasoning, SingularJacobianReasoning,
  ConditioningReasoning, NumericalStabilityReasoning,
  VerificationReasoning, KnowledgeGraphConstruction,
  RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "Newton-Raphson" -> NewtonRaphsonMethod
  "Newton method" -> NewtonRaphsonMethod
  "Newton iteration" -> NewtonRaphsonMethod
  "JFNK" -> JacobianFreeNewtonKrylov
  "Newton correction" -> NewtonStep
 }
}

EXECUTION_RULES {
 E1 = "If a nonlinear equation is solved by derivative- or Jacobian-based local linearisation, activate NewtonRaphsonOntology."
 E2 = "Choose and document the initial guess before iteration."
 E3 = "If the scalar derivative is zero or tiny, reject or safeguard the raw Newton step."
 E4 = "If a system Jacobian is singular or poorly conditioned, use safeguarding, regularisation, alternative steps or another method."
 E5 = "If full Newton steps are unreliable, use damping, line search or trust-region globalisation."
 E6 = "If the system is large, consider inexact Newton, Newton-Krylov or JFNK methods."
 E7 = "If a repeated root is known or suspected, consider multiplicity-corrected Newton semantics."
 E8 = "Monitor residual, step norm, convergence rate, stagnation and breakdown."
 E9 = "Verify the returned root against the original equation or system and domain."
}

RECURSION {
 ENTRY = NewtonRaphsonMethod
 EXPAND(NewtonRaphsonMethod) -> [
  NewtonMethod, ScalarNewtonMethod, MultivariableNewtonMethod,
  NewtonSystemMethod, NewtonIteration, NewtonStep, TangentMethod,
  Linearisation, LocalLinearModel, NonlinearEquation, NonlinearSystem,
  Root, SimpleRoot, MultipleRoot, RepeatedRoot, RootMultiplicity,
  InitialGuess, CurrentIterate, NextIterate, FunctionValue, Residual,
  FirstDerivative, Jacobian, ExactDerivative, NumericalDerivative,
  FiniteDifferenceDerivative, AutomaticDifferentiation,
  SymbolicDerivative, ModifiedNewtonMethod, MultiplicityCorrectedNewton,
  DampedNewtonMethod, SafeguardedNewtonMethod, GlobalisedNewtonMethod,
  LineSearchNewton, TrustRegionNewton, InexactNewtonMethod,
  NewtonKrylovMethod, JacobianFreeNewtonKrylov, QuasiNewtonMethod,
  BroydenMethod, NewtonCorrection, SearchDirection, StepLength,
  DampingFactor, MeritFunction, LineSearch, TrustRegion,
  BacktrackingLineSearch, ArmijoCondition, InnerLinearSolver,
  Preconditioner, Convergence, LocalConvergence, QuadraticConvergence,
  SuperlinearConvergence, BasinOfAttraction, Divergence, Oscillation,
  Stagnation, Breakdown, ZeroDerivative, SmallDerivative,
  SingularJacobian, NearlySingularJacobian, IllConditionedJacobian,
  ConditionNumber, Conditioning, RootConditioning, Sensitivity,
  Scaling, ForwardError, BackwardError, RoundOffError,
  TruncationError, FloatingPointArithmetic, MachinePrecision,
  AbsoluteTolerance, RelativeTolerance, ResidualTolerance,
  StepTolerance, StoppingCriterion, MaximumIterations,
  SolverStatus, Verification, Benchmarking, Reproducibility
 ]
 EXPAND(NewtonFamilies) -> [
  ScalarNewtonMethods,
  SystemNewtonMethods,
  ModifiedAndMultiplicityCorrectedNewton,
  GlobalisedNewtonMethods,
  InexactNewtonMethods,
  NewtonKrylovAndJFNKMethods,
  NewtonVerification
 ]
 STOP_CONDITION = "Stop when initialisation, derivative model, Newton step, globalisation, convergence, conditioning and verification are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Root Finding Ontology 2"
 RELATED_ONTOLOGIES = [
  "Root Finding Ontology 2",
  "Nonlinear Solver Ontology",
  "Equation Solver Ontology",
  "Linear Solver Ontology",
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Error Ontology",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology",
  "Floating Point Arithmetic Ontology"
 ]
 ROUTE_RULES = [
  "Newton-Raphson -> Root Finding for scalar zero-finding parent semantics",
  "Newton-Raphson -> Nonlinear Solver for system and globalisation semantics",
  "Newton-Raphson -> Equation Solver for generic solver configuration and status",
  "Newton-Raphson -> Linear Solver for Jacobian-system Newton steps",
  "Newton-Raphson -> Numerical Analysis for local convergence and conditioning",
  "Newton-Raphson -> Numerical Error for residual and root-error semantics",
  "Newton-Raphson -> Numerical Stability for finite-precision behaviour",
  "Newton-Raphson -> Numerical Convergence for local order and stopping"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible Newton variants, globalisation mechanisms or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve scalar-versus-system Newton distinction.",
  "Preserve full-step-versus-damped Newton distinction.",
  "Preserve exact-versus-inexact Newton distinction.",
  "Preserve simple-root-versus-multiple-root distinction.",
  "Preserve residual-versus-root-error distinction.",
  "Preserve local-convergence-versus-globalisation distinction.",
  "Preserve explicit-Jacobian-versus-Jacobian-free distinction.",
  "Preserve machine-readable Newton-Raphson semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Newton-Raphson is a derivative-based iterative method that solves nonlinear equations by repeated local linearisation."
 SCALAR_SUMMARY = "For scalar equations, the Newton update is x_(k+1)=x_k-f(x_k)/f'(x_k)."
 SYSTEM_SUMMARY = "For systems, each Newton step solves J(x_k) delta_k=-F(x_k) and updates x_(k+1)=x_k+delta_k."
 CONVERGENCE_SUMMARY = "Near a sufficiently smooth simple root, standard Newton iteration is locally quadratic."
 MULTIPLICITY_SUMMARY = "Repeated roots reduce the convergence rate unless multiplicity-aware corrections are used."
 GLOBALISATION_SUMMARY = "Damping, line search and trust-region strategies improve robustness outside the local convergence region."
 LARGE_SCALE_SUMMARY = "Inexact Newton, Newton-Krylov and JFNK methods reduce the cost of large nonlinear systems."
 VALIDATION_SUMMARY = "Newton results should be checked for residuals, step size, derivative or Jacobian quality, convergence, conditioning and reproducibility."
}

FLOW {
 INPUT
 -> detect_Newton_Raphson_context
 -> identify_scalar_or_system_problem_function_domain_derivative_availability_and_accuracy_goal
 -> choose_initial_guess_and_scaling
 -> obtain_exact_symbolic_AD_finite_difference_or_approximate_derivative_or_Jacobian
 -> construct_local_linear_model
 -> compute_Newton_correction
 -> if_needed_apply_damping_line_search_trust_region_or_safeguard
 -> update_iterate
 -> monitor_residual_step_norm_convergence_rate_stagnation_oscillation_and_breakdown
 -> assess_derivative_or_Jacobian_conditioning_root_multiplicity_scaling_and_roundoff
 -> classify_solver_status
 -> verify_candidate_against_original_equation_or_system_and_domain
 -> route_to_related_root_finding_nonlinear_solver_linear_solver_and_numerical_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Newton-Raphson Ontology defines derivative-based nonlinear root iteration. It supports scalar and multivariable Newton methods, tangent linearisation, Newton corrections, derivatives and Jacobians from symbolic, automatic-differentiation and finite-difference sources, simple and repeated roots, modified and multiplicity-corrected Newton methods, damping and safeguarding, line-search and trust-region Newton, inexact Newton, Newton-Krylov and Jacobian-free Newton-Krylov methods, quasi-Newton relationships, residuals and step norms, local and quadratic convergence, basins of attraction, zero derivatives and singular Jacobians, conditioning, scaling, round-off and truncation effects, stopping criteria, solver status, verification, benchmarking and reproducibility."
}

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

}

END_FLOW