Fixed Point Iteration Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Fixed-Point Iteration Ontology within the Kireth Research Semantic Library. Fixed-point iteration solves equations by reformulating them as x=g(x) and repeatedly applying the fixed-point map. This ontology supports contraction mappings, convergence conditions, local and global behaviour, relaxation, acceleration, residuals, stopping criteria, stability, finite precision, multiple fixed points, basins of attraction and verification.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = FixedPointIteration
 ENTITY_CLASS = IterativeFixedPointSolutionFramework
 PRIMARY_CONTEXT = RootFinding
 DEFINITION = "Fixed-point iteration is an iterative method that seeks a value x satisfying x=g(x) by repeatedly applying the map x_(k+1)=g(x_k)."
 SYMBOLIC_FORMS = [
  "x=g(x)",
  "x_(k+1)=g(x_k)",
  "r_k=g(x_k)-x_k",
  "|g'(x_star)|<1"
 ]
 SEMANTIC_ROLE = "Provides machine-readable semantics for fixed-point reformulation, iteration maps, contraction conditions, convergence, relaxation, acceleration, residuals, finite precision and verification."
}

SCOPE {
 INCLUDE = [
  FixedPointIteration, FixedPointMethod, PicardIteration,
  SuccessiveSubstitution, FixedPointEquation, FixedPoint,
  FixedPointMap, IterationFunction, IterationOperator,
  ScalarFixedPointIteration, VectorFixedPointIteration,
  NonlinearEquation, NonlinearSystem, RootFinding,
  InitialGuess, CurrentIterate, NextIterate, IterationSequence,
  Orbit, BasinOfAttraction, AttractingFixedPoint, RepellingFixedPoint,
  NeutralFixedPoint, StableFixedPoint, UnstableFixedPoint,
  ContractionMapping, ContractionConstant, BanachFixedPointTheorem,
  LipschitzConstant, LipschitzContinuity, CompleteMetricSpace,
  LocalConvergence, GlobalConvergence, LinearConvergence,
  SuperlinearConvergence, ConvergenceRate, SpectralRadius,
  Jacobian, Derivative, FixedPointJacobian, IterationMatrix,
  Relaxation, UnderRelaxation, OverRelaxation, Damping,
  WeightedFixedPointIteration, RelaxationParameter,
  AitkenAcceleration, DeltaSquaredMethod, SteffensenMethod,
  AndersonAcceleration, Extrapolation, Residual, FixedPointResidual,
  ResidualNorm, StepNorm, AbsoluteTolerance, RelativeTolerance,
  ResidualTolerance, StepTolerance, StoppingCriterion,
  MaximumIterations, MaximumEvaluations, Divergence,
  Stagnation, Oscillation, Cycling, PeriodicOrbit, Chaos,
  MultipleFixedPoints, UniqueFixedPoint, Conditioning,
  Sensitivity, Scaling, VariableScaling, NumericalStability,
  FloatingPointArithmetic, MachinePrecision, RoundOffError,
  Cancellation, Overflow, Underflow, SolverStatus,
  Success, Failure, Warning, Verification, SubstitutionCheck,
  ReferenceSolution, Benchmarking, Reproducibility
 ]
 EXCLUDE_AS_PRIMARY = [
  NewtonMethodWithoutFixedPointInterpretation,
  SecantMethodWithoutFixedPointMap,
  DirectEquationSolvingWithoutIterationMap,
  DynamicalSystemsAnalysisWithoutEquationSolvingContext
 ]
 DISAMBIGUATION_RULE = "When an equation is solved by reformulating it as x=g(x) and repeatedly applying g, interpret the context as fixed-point iteration."
}

CORE_CONCEPTS {
 FixedPointIteration = "Iteration x_(k+1)=g(x_k) intended to converge to x_star=g(x_star)."
 FixedPoint = "Value unchanged by the iteration map."
 ContractionMapping = "Map that reduces distances by a factor strictly below one under an appropriate metric."
 BanachFixedPointTheorem = "Theorem guaranteeing existence, uniqueness and convergence for contractions on complete metric spaces."
 AttractingFixedPoint = "Fixed point toward which nearby iterates converge."
 RepellingFixedPoint = "Fixed point from which nearby iterates move away."
 Relaxation = "Modification blending the current iterate with the mapped iterate."
 AndersonAcceleration = "Multistep acceleration technique for fixed-point iterations."
}

RELATIONS {
 FixedPointIteration --is_child_of--> RootFinding
 FixedPointIteration --solves--> FixedPointEquation
 FixedPointEquation --is_equivalent_to--> RootEquationUnderReformulation
 FixedPointIteration --uses--> FixedPointMap
 FixedPointMap --generates--> IterationSequence
 ContractionMapping --supports--> UniqueFixedPointConvergence
 BanachFixedPointTheorem --guarantees_under_assumptions--> FixedPointConvergence
 DerivativeMagnitudeBelowOne --supports_locally--> AttractingFixedPoint
 DerivativeMagnitudeAboveOne --supports_locally--> RepellingFixedPoint
 Relaxation --modifies--> FixedPointMap
 AitkenAcceleration --accelerates--> LinearlyConvergentSequence
 SteffensenMethod --uses--> AitkenAcceleration
 AndersonAcceleration --accelerates--> VectorFixedPointIteration
 Residual --measures--> FixedPointMismatch
 Verification --checks--> CandidateFixedPoint
}

OPERATORS {
 FIXED_POINT_STEP(x,g) := x_next=g(x)
 FIXED_POINT_RESIDUAL(x,g) := r=g(x)-x
 RELAXED_STEP(x,g,omega) := x_next=(1-omega)*x+omega*g(x)
 CONTRACTION_TEST(g,L) := L<1
 LOCAL_SCALAR_TEST(g,x_star) := |g_prime(x_star)|<1
 VECTOR_LOCAL_TEST(Jg) := spectral_radius(Jg)<1
 AITKEN(x0,x1,x2) := x_hat=x0-(x1-x0)^2/(x2-2*x1+x0)
}

AXIOMS {
 A1 = "A fixed point satisfies x_star=g(x_star)."
 A2 = "A contraction mapping on a complete metric space has a unique fixed point and converges from any starting point in the invariant domain."
 A3 = "For scalar differentiable maps, |g'(x_star)|<1 supports local attraction."
 A4 = "If |g'(x_star)|>1, the fixed point is locally repelling."
 A5 = "Residual and fixed-point location error are distinct."
 A6 = "Different algebraic rearrangements of the same equation can produce fixed-point maps with different convergence behaviour."
 A7 = "Relaxation can improve or degrade convergence depending on the map and parameter."
 A8 = "Fixed-point results require explicit map, initialisation, stopping and verification semantics."
}

REASONING {
 R1_CONTEXT = identify(original_equation,fixed_point_map,domain,dimension,accuracy_goal)
 R2_MAP_ANALYSIS = assess(invariance,Lipschitz_constant,derivative_or_Jacobian,spectral_radius)
 R3_INITIALISE = choose(initial_guess_and_scaling)
 R4_VARIANT = choose(plain,relaxed,Aitken,Steffensen,Anderson_or_other_accelerated_iteration)
 R5_ITERATE = compute_next_iterate_from_selected_map)
 R6_RESIDUAL = compute_fixed_point_residual_and_step_norm)
 R7_CONVERGENCE = monitor(rate,stagnation,oscillation,cycling_and_divergence)
 R8_ACCELERATION = if_slow_and_safe apply(relaxation_or_acceleration)
 R9_PRECISION = assess(roundoff,cancellation,and_machine_precision_limits)
 R10_VERIFY = check_candidate_against_fixed_point_map_and_original_equation)
}

CONSTRAINTS {
 C1 = "A fixed-point reformulation can diverge even when the original equation has a solution."
 C2 = "Convergence depends on the chosen map g, not only on the original equation."
 C3 = "A derivative magnitude near one can produce very slow convergence."
 C4 = "A derivative magnitude greater than one near the fixed point generally indicates local divergence."
 C5 = "Multiple fixed points can produce multiple basins of attraction."
 C6 = "Relaxation parameters outside a suitable range can destabilise the iteration."
 C7 = "Acceleration methods can amplify noise or instability when the base iteration is poorly behaved."
 C8 = "A small step does not necessarily imply a small residual."
 C9 = "Finite precision can cause stagnation or artificial cycles."
 C10 = "Verification must check both x=g(x) and the original equation when a reformulation was used."
}

SEMANTIC_EQUIVALENCE {
 "FixedPointIteration" <=> "FixedPointMethod"
 "PicardIteration" <=> "FixedPointIteration"
 "SuccessiveSubstitution" <=> "FixedPointIteration"
 "DeltaSquaredMethod" <=> "AitkenAcceleration"
 "UnderRelaxation" <=> "DampedFixedPointIteration"
}

VALIDATION {
 V1 = "Original equation and fixed-point map are explicit."
 V2 = "Domain and invariant-region assumptions are documented."
 V3 = "Initial guess is documented."
 V4 = "Derivative, Jacobian or contraction information is documented where used."
 V5 = "Residual and step stopping criteria are documented."
 V6 = "Relaxation or acceleration parameters are documented."
 V7 = "Oscillation, cycling and stagnation are monitored."
 V8 = "Candidate fixed point satisfies x=g(x)."
 V9 = "Candidate solution satisfies the original equation."
 V10 = "Results are reproducible under documented arithmetic and iteration settings."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 FIXED_POINT_DEFINITION = 0.99
 CONTRACTION_REASONING = 0.99
 LOCAL_CONVERGENCE_REASONING = 0.99
 RELAXATION_REASONING = 0.98
 AITKEN_REASONING = 0.98
 ANDERSON_REASONING = 0.98
 FINITE_PRECISION_REASONING = 0.98
 POLICY = "Reduce confidence when fixed-point map, invariant domain, derivative or Jacobian behaviour, initial guess, relaxation, acceleration or stopping criteria are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch, OntologyGrounding, FixedPointIterationReasoning,
  FixedPointMapReasoning, ContractionMappingReasoning,
  BanachFixedPointReasoning, LocalConvergenceReasoning,
  BasinOfAttractionReasoning, RelaxationReasoning,
  AitkenAccelerationReasoning, SteffensenReasoning,
  AndersonAccelerationReasoning, ResidualReasoning,
  SpectralRadiusReasoning, NumericalStabilityReasoning,
  VerificationReasoning, KnowledgeGraphConstruction,
  RetrievalAugmentation, RecursiveInference
 ]
 NORMALISE {
  "fixed-point iteration" -> FixedPointIteration
  "fixed point iteration" -> FixedPointIteration
  "Picard iteration" -> FixedPointIteration
  "successive substitution" -> FixedPointIteration
  "Aitken delta-squared" -> AitkenAcceleration
  "Anderson mixing" -> AndersonAcceleration
 }
}

EXECUTION_RULES {
 E1 = "If an equation is solved through repeated application of x_(k+1)=g(x_k), activate FixedPointIterationOntology."
 E2 = "Make the chosen fixed-point map explicit."
 E3 = "Assess contraction, derivative or Jacobian conditions before assuming convergence."
 E4 = "Choose and document the initial guess."
 E5 = "If convergence is slow, consider relaxation or acceleration only after checking stability."
 E6 = "If oscillation or divergence occurs, revise the map, relaxation or solver choice."
 E7 = "For vector problems, use Jacobian spectral-radius reasoning where appropriate."
 E8 = "Monitor both residual and step norm."
 E9 = "Verify the final result against both the fixed-point map and the original equation."
}

RECURSION {
 ENTRY = FixedPointIteration
 EXPAND(FixedPointIteration) -> [
  FixedPointMethod,PicardIteration,SuccessiveSubstitution,
  FixedPointEquation,FixedPoint,FixedPointMap,IterationFunction,
  IterationOperator,ScalarFixedPointIteration,VectorFixedPointIteration,
  InitialGuess,CurrentIterate,NextIterate,IterationSequence,Orbit,
  BasinOfAttraction,AttractingFixedPoint,RepellingFixedPoint,
  NeutralFixedPoint,StableFixedPoint,UnstableFixedPoint,
  ContractionMapping,ContractionConstant,BanachFixedPointTheorem,
  LipschitzConstant,LipschitzContinuity,LocalConvergence,
  GlobalConvergence,LinearConvergence,ConvergenceRate,SpectralRadius,
  Jacobian,Derivative,FixedPointJacobian,IterationMatrix,Relaxation,
  UnderRelaxation,OverRelaxation,Damping,WeightedFixedPointIteration,
  RelaxationParameter,AitkenAcceleration,SteffensenMethod,
  AndersonAcceleration,Extrapolation,Residual,FixedPointResidual,
  ResidualNorm,StepNorm,AbsoluteTolerance,RelativeTolerance,
  ResidualTolerance,StepTolerance,StoppingCriterion,MaximumIterations,
  Divergence,Stagnation,Oscillation,Cycling,PeriodicOrbit,
  MultipleFixedPoints,UniqueFixedPoint,Conditioning,Sensitivity,
  Scaling,NumericalStability,FloatingPointArithmetic,MachinePrecision,
  RoundOffError,Cancellation,SolverStatus,Verification,
  Benchmarking,Reproducibility
 ]
 EXPAND(FixedPointFamilies) -> [
  ScalarFixedPointIteration,
  VectorFixedPointIteration,
  ContractionMappings,
  RelaxedFixedPointIteration,
  AitkenAndSteffensenAcceleration,
  AndersonAcceleration,
  FixedPointVerification
 ]
 STOP_CONDITION = "Stop when fixed-point map, domain, initialisation, convergence conditions, relaxation or acceleration, 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",
  "Secant Method Ontology",
  "Numerical Methods",
  "Numerical Analysis Ontology 2",
  "Numerical Error Ontology",
  "Numerical Stability Ontology 2",
  "Numerical Convergence Ontology",
  "Floating Point Arithmetic Ontology"
 ]
 ROUTE_RULES = [
  "Fixed-Point Iteration -> Root Finding for parent zero-finding semantics",
  "Fixed-Point Iteration -> Nonlinear Solver for nonlinear iteration and status",
  "Fixed-Point Iteration -> Newton-Raphson for derivative-based fixed-point reinterpretation",
  "Fixed-Point Iteration -> Secant Method for open-method comparison",
  "Fixed-Point Iteration -> Numerical Analysis for contraction and convergence theory",
  "Fixed-Point Iteration -> Numerical Error for residual and iterate error",
  "Fixed-Point Iteration -> Numerical Stability for finite-precision behaviour",
  "Fixed-Point Iteration -> Numerical Convergence for asymptotic rate and stopping",
  "Fixed-Point Iteration -> Floating Point Arithmetic for stagnation and cancellation"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"
 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible fixed-point maps, acceleration methods or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"
 RULES = [
  "Preserve equation-versus-fixed-point-map distinction.",
  "Preserve attracting-versus-repelling fixed-point distinction.",
  "Preserve contraction-guarantee-versus-local-derivative-test distinction.",
  "Preserve raw-iteration-versus-relaxed-or-accelerated distinction.",
  "Preserve residual-versus-step-error distinction.",
  "Preserve scalar-versus-vector fixed-point distinction.",
  "Preserve original-equation-versus-reformulated-map distinction.",
  "Preserve machine-readable fixed-point iteration semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION = "Fixed-point iteration solves equations by repeatedly applying a map x_(k+1)=g(x_k) until x approximately equals g(x)."
 CONTRACTION_SUMMARY = "Contraction mappings provide strong existence, uniqueness and convergence guarantees under the Banach fixed-point theorem."
 LOCAL_SUMMARY = "For scalar differentiable maps, derivative magnitude below one near the fixed point supports local attraction."
 RELAXATION_SUMMARY = "Under-relaxation and over-relaxation alter the effective iteration map and can improve or destabilise convergence."
 ACCELERATION_SUMMARY = "Aitken, Steffensen and Anderson techniques can accelerate suitable slowly convergent fixed-point sequences."
 FAILURE_SUMMARY = "Repelling maps, poor reformulations, oscillations, multiple basins and finite-precision stagnation can prevent convergence."
 VALIDATION_SUMMARY = "Fixed-point results should be checked against the iteration map, the original equation, residuals, convergence conditions and reproducibility."
}

FLOW {
 INPUT
 -> detect_fixed_point_iteration_context
 -> identify_original_equation_fixed_point_map_domain_dimension_and_accuracy_goal
 -> assess_invariance_Lipschitz_derivative_or_Jacobian_and_spectral_radius
 -> choose_initial_guess_and_scaling
 -> select_plain_relaxed_Aitken_Steffensen_Anderson_or_other_fixed_point_iteration
 -> compute_next_iterate
 -> evaluate_fixed_point_residual_and_step_norm
 -> monitor_convergence_rate_stagnation_oscillation_cycling_and_divergence
 -> if_needed_adjust_relaxation_acceleration_or_solver_choice
 -> assess_conditioning_roundoff_cancellation_and_machine_precision
 -> verify_candidate_against_fixed_point_map_and_original_equation
 -> route_to_related_root_finding_nonlinear_solver_analysis_error_stability_convergence_and_floating_point_ontologies
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Fixed-Point Iteration Ontology defines equation solving through repeated application of x_(k+1)=g(x_k). It supports scalar and vector fixed-point problems, Picard iteration and successive substitution, attracting, repelling and neutral fixed points, contraction mappings, the Banach fixed-point theorem, Lipschitz constants, local and global convergence, derivative and Jacobian tests, spectral-radius reasoning, relaxation and damping, Aitken delta-squared, Steffensen and Anderson acceleration, residual and step tolerances, basins of attraction, multiple fixed points, oscillation, cycling and stagnation, conditioning, finite precision, solver status, verification, benchmarking and reproducibility."
}

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

}

END_FLOW