Iterative Methods Ontology

AI INTERPRETATION NOTE
This Flow Algebra defines the Iterative Methods Ontology within the Kireth Research Semantic Library. Iterative methods are numerical procedures that generate successive approximations to a target solution and terminate when a convergence or stopping criterion is satisfied. This ontology supports fixed-point iteration, stationary and nonstationary linear solvers, Krylov subspace methods, nonlinear iterations, relaxation, preconditioning, residual monitoring, convergence rates, stopping criteria, divergence detection, acceleration, conditioning, stability and relationships with numerical analysis, root finding, numerical linear algebra, optimisation and scientific computing.

FLOW_ALGEBRA_RECORD {

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

IDENTITY {
 PRIMARY_ENTITY = IterativeMethod
 SYMBOLIC_FORMS = [
  "x_{k+1}=G(x_k)",
  "r_k=b-Ax_k",
  "||r_k|| -> 0"
 ]
 ENTITY_CLASS = SuccessiveApproximationFramework
 PRIMARY_CONTEXT = NumericalAnalysis
 DEFINITION = "An iterative method is a numerical algorithm that generates a sequence of approximations intended to converge to a mathematical solution."
 SEMANTIC_ROLE = "Provides the machine-readable framework for successive approximation, iteration operators, residuals, stopping criteria, convergence rates, relaxation, preconditioning, acceleration and divergence detection."
}

SCOPE {
 INCLUDE = [
  IterativeMethod,
  Iteration,
  Iterate,
  InitialGuess,
  UpdateRule,
  FixedPointIteration,
  StationaryIteration,
  NonstationaryIteration,
  JacobiMethod,
  GaussSeidelMethod,
  SuccessiveOverRelaxation,
  RichardsonIteration,
  GradientIteration,
  ConjugateGradientMethod,
  GMRES,
  MINRES,
  BiCGSTAB,
  KrylovSubspaceMethod,
  NewtonIteration,
  QuasiNewtonIteration,
  PicardIteration,
  NonlinearIteration,
  Residual,
  Error,
  Convergence,
  Divergence,
  ConvergenceRate,
  LinearConvergence,
  SuperlinearConvergence,
  QuadraticConvergence,
  SpectralRadius,
  Preconditioner,
  RelaxationParameter,
  StoppingCriterion,
  AbsoluteTolerance,
  RelativeTolerance,
  IterationLimit,
  ResidualNorm,
  StepNorm,
  AccelerationMethod,
  AndersonAcceleration
 ]

 EXCLUDE_AS_PRIMARY = [
  DirectMethodWithoutIteration,
  GenericLoopsWithoutNumericalConvergenceGoal,
  MonteCarloSamplingWithoutSuccessiveApproximationStructure,
  TimeSteppingUnlessUsedAsSolverIterationContext
 ]

 DISAMBIGUATION_RULE =
  "When a numerical algorithm repeatedly updates an approximation until a residual, error, step or convergence condition is met, interpret it as an iterative method."
}

CORE_CONCEPTS {

 IterativeMethod {
  definition = "A numerical method producing successive approximations to a target solution."
 }

 Iterate {
  definition = "The current approximation generated at an iteration step."
 }

 InitialGuess {
  definition = "The starting approximation from which iteration begins."
 }

 UpdateRule {
  definition = "The map or procedure generating the next iterate from current information."
 }

 FixedPointIteration {
  definition = "An iteration of the form x_{k+1}=g(x_k)."
 }

 StationaryIteration {
  definition = "An iterative method whose update operator does not change with iteration count."
 }

 KrylovSubspaceMethod {
  definition = "A method generating approximations from nested Krylov subspaces associated with a matrix and residual."
 }

 Residual {
  definition = "The mismatch between a current iterate and the governing discrete equations."
 }

 ConvergenceRate {
  definition = "The asymptotic speed at which approximation error decreases."
 }

 Preconditioner {
  definition = "A transformation intended to improve the spectral or conditioning properties of an iterative problem."
 }

 StoppingCriterion {
  definition = "A rule determining when iteration is terminated."
 }

 Divergence {
  definition = "Failure of the iterate sequence to approach the desired solution."
 }
}

RELATIONS {
 IterativeMethod --is_type_of--> NumericalMethod
 IterativeMethod --produces--> Iterate
 IterativeMethod --starts_from--> InitialGuess
 IterativeMethod --uses--> UpdateRule
 IterativeMethod --uses--> StoppingCriterion
 FixedPointIteration --is_type_of--> IterativeMethod
 StationaryIteration --is_type_of--> IterativeMethod
 KrylovSubspaceMethod --is_type_of--> IterativeMethod
 NewtonIteration --is_type_of--> NonlinearIteration
 Residual --measures--> EquationMismatch
 ConvergenceRate --describes--> IterativeMethod
 SpectralRadius --influences--> StationaryIterationConvergence
 Preconditioner --modifies--> IterativeLinearSystem
 RelaxationParameter --controls--> RelaxedIteration
 AccelerationMethod --improves--> ConvergenceBehaviour
 Divergence --contrasts_with--> Convergence
}

OPERATORS {
 GENERIC_ITERATION(x_k,G) :=
  G(x_k)

 LINEAR_STATIONARY_ITERATION(x_k,M,N,b) :=
  M^{-1}*(N*x_k+b)
  WHEN A=M-N

 RESIDUAL(A,x,b) :=
  b-A*x

 RELATIVE_RESIDUAL(r,b) :=
  norm(r)/max(norm(b),epsilon_scale)

 STEP_NORM(x_new,x_old) :=
  norm(x_new-x_old)

 CHECK_STOP(residual,step,tol_r,tol_x,k,kmax) :=
  residual<=tol_r
  OR step<=tol_x
  OR k>=kmax

 SPECTRAL_RADIUS(T) :=
  max_abs_eigenvalue(T)

 RELAXED_UPDATE(x_old,x_raw,omega) :=
  (1-omega)*x_old + omega*x_raw

 PRECONDITIONED_SYSTEM(A,b,P) :=
  solve P^{-1}A x = P^{-1}b
  or equivalent right/split form

 KRYLOV_SUBSPACE(A,r0,m) :=
  span{r0,A*r0,...,A^{m-1}*r0}

 CONVERGENCE_FACTOR(errors) :=
  asymptotic_ratio ||e_{k+1}||/||e_k||
}

DEFINITIONS {
 D1 = "Iterative methods generate successive approximations."
 D2 = "The initial guess can materially affect nonlinear convergence."
 D3 = "Stopping criteria should reflect both accuracy and computational cost."
 D4 = "Residual convergence and true error convergence are related but not identical."
 D5 = "Stationary linear iterations are governed by their iteration matrix."
 D6 = "A stationary iteration converges for all initial guesses when the spectral radius of its iteration matrix is less than one."
 D7 = "Krylov methods generate approximations in nested matrix-generated subspaces."
 D8 = "Preconditioning improves iterative convergence by altering the effective problem."
 D9 = "Relaxation changes the update amplitude."
 D10 = "Acceleration methods combine iteration history to improve convergence."
}

AXIOMS {
 A1_SUCCESSIVE_APPROXIMATION:
  IterativeMethod defines a sequence x_0,x_1,x_2,...

 A2_UPDATE:
  Each iterate is generated by a declared update rule

 A3_STOPPING:
  Practical iteration requires a stopping criterion or iteration limit

 A4_CONVERGENCE:
  Convergence claims require that iterates approach the intended solution under stated assumptions

 A5_RESIDUAL_CONTEXT:
  Residual reduction alone does not guarantee small forward error for ill-conditioned problems

 A6_STATIONARY_LINEAR:
  For x_{k+1}=T x_k+c, convergence for every x_0 requires spectral_radius(T)<1

 A7_PRECONDITIONING:
  Valid preconditioning preserves the original solution under the chosen transformed system

 A8_DIVERGENCE_DETECTION:
  Iteration should terminate or switch strategy when divergence or stagnation is detected
}

REASONING {

 R1_ITERATION_CLASSIFICATION {
  INPUT = iterative_algorithm
  IDENTIFY = linear_or_nonlinear
  IDENTIFY = stationary_or_nonstationary
  IDENTIFY = fixed_point_Newton_Krylov_relaxation_or_other
  RETURN = iteration_class
 }

 R2_INITIALISATION {
  INPUT = problem_and_method
  SELECT = initial_guess
  INITIALISE = residual_and_iteration_counter
  RETURN = iteration_state
 }

 R3_STATIONARY_LINEAR_ANALYSIS {
  INPUT = iteration_matrix_T
  COMPUTE = spectral_radius
  IF rho(T)<1
   RETURN = convergence_expected_for_all_initial_guesses
  ELSE
   RETURN = no_general_convergence_guarantee
 }

 R4_FIXED_POINT_ANALYSIS {
  INPUT = g_and_initial_region
  TEST = local_contraction
  IF contraction
   RETURN = local_convergence_expected
  ELSE
   RETURN = uncertain_or_divergent
 }

 R5_KRYLOV_REASONING {
  INPUT = A_b_initial_guess
  COMPUTE = r0
  BUILD = Krylov_subspace
  APPLY = method_specific orthogonalisation_or_minimisation
  RETURN = improved_iterate
 }

 R6_PRECONDITIONING {
  INPUT = A_and_solver
  SELECT = P_approximating_A_or_relevant structure
  FORM = preconditioned_problem
  RETURN = modified_iteration_with_same_target_solution
 }

 R7_STOPPING_REASONING {
  INPUT = residual_step_error_estimate_and_iteration_count
  NORMALISE = residual_and_step
  COMPARE = absolute_relative_tolerances
  CHECK = iteration_limit
  RETURN = continue_stop_or_fail
 }

 R8_DIVERGENCE_STAGNATION {
  INPUT = iteration_history
  TEST = increasing_residual
  TEST = negligible_progress
  TEST = oscillation_or_breakdown
  RETURN = converging_stagnating_diverging_or_breakdown
 }

 R9_ACCELERATION {
  INPUT = iteration_history
  SELECT = relaxation_extrapolation_Anderson_or_Krylov acceleration
  APPLY = accelerated update
  RETURN = accelerated_iterate
 }

 R10_CONVERGENCE_RATE {
  INPUT = error_or_residual_history
  ESTIMATE = linear_superlinear_quadratic_or_empirical rate
  RETURN = convergence_profile
 }
}

CONSTRAINTS {
 C1 = "Iterative methods require finite stopping logic."
 C2 = "Residual norms must be scaled appropriately."
 C3 = "Small residual does not guarantee small forward error in ill-conditioned problems."
 C4 = "Convergence theory can depend on the chosen norm."
 C5 = "Nonlinear methods can converge to different solutions from different initial guesses."
 C6 = "Stationary linear iteration convergence depends on the iteration matrix."
 C7 = "Relaxation parameters outside suitable ranges can cause divergence."
 C8 = "Preconditioners must remain computationally cheaper than solving the original problem directly to be useful."
 C9 = "Krylov methods may suffer breakdown, loss of orthogonality or stagnation."
 C10 = "Iteration counts alone are not comparable across methods without cost and accuracy context."
}

SEMANTIC_EQUIVALENCE {
 "IterativeMethod" <=> "SuccessiveApproximationMethod"
 "Iterate" <=> "CurrentApproximateSolution"
 "FixedPointIteration" <=> "SuccessiveSubstitution"
 "Preconditioner" <=> "ConvergenceImprovingProblemTransformation"
 "StoppingCriterion" <=> "IterationTerminationRule"
 "Stagnation" <=> "FailureToMakeMeaningfulProgress"
}

VALIDATION {
 V1 = "Initial guess is defined."
 V2 = "Update rule is explicit."
 V3 = "Residual or error monitor is defined."
 V4 = "Stopping tolerances are explicit."
 V5 = "Iteration limit exists."
 V6 = "Convergence assumptions are identified."
 V7 = "Preconditioning preserves solution equivalence."
 V8 = "Divergence and stagnation are monitored."
 V9 = "Convergence-rate claims use sufficient history."
 V10 = "Approximate-versus-converged status is explicit."
}

CONFIDENCE {
 BASE_CONFIDENCE = 0.99
 ITERATIVE_METHOD_DEFINITION = 0.99
 CLASSIFICATION_REASONING = 0.99
 STATIONARY_ITERATION_REASONING = 0.99
 FIXED_POINT_REASONING = 0.98
 KRYLOV_REASONING = 0.98
 PRECONDITIONING_REASONING = 0.98
 STOPPING_REASONING = 0.99
 CONVERGENCE_RATE_REASONING = 0.98

 POLICY =
  "Reduce confidence when initialisation, norm, tolerance, conditioning, spectral information, preconditioner quality, iteration history or nonlinear basin of attraction are underspecified."
}

AI_CONSUMPTION {
 PURPOSES = [
  SemanticSearch,
  OntologyGrounding,
  IterativeMethodReasoning,
  FixedPointReasoning,
  StationaryIterationReasoning,
  KrylovSubspaceReasoning,
  PreconditioningReasoning,
  RelaxationReasoning,
  StoppingCriterionReasoning,
  ResidualMonitoring,
  ConvergenceAnalysis,
  DivergenceDetection,
  StagnationDetection,
  AccelerationReasoning,
  KnowledgeGraphConstruction,
  RetrievalAugmentation,
  RecursiveInference
 ]

 NORMALISE {
  "iterative methods" -> IterativeMethod
  "iterative method" -> IterativeMethod
  "iteration" -> Iteration WHEN numerical_context
  "fixed-point iteration" -> FixedPointIteration
  "Jacobi method" -> JacobiMethod
  "Gauss-Seidel method" -> GaussSeidelMethod
  "successive over-relaxation" -> SuccessiveOverRelaxation
  "conjugate gradient" -> ConjugateGradientMethod
  "GMRES" -> GMRES
  "preconditioner" -> Preconditioner
  "stopping criterion" -> StoppingCriterion
 }

 INTERPRETATION_ORDER = [
  detect_iterative_method_context,
  identify problem_type_initial_guess_update_rule_norm_tolerances_conditioning_and_iteration_limit,
  classify fixed_point_stationary_Krylov_Newton_relaxation_or_other pathway,
  initialise iteration,
  perform successive updates,
  monitor residual_step_error_and_breakdown indicators,
  apply preconditioning_relaxation_or_acceleration when appropriate,
  assess convergence_rate_stagnation_or_divergence,
  return semantic output
 ]
}

EXECUTION_RULES {
 E1:
  IF query_mentions("iterative method")
  OR repeated_numerical_updates_until_convergence context
  THEN activate(IterativeMethodsOntology)

 E2:
  IF stationary_linear_iteration
  THEN analyse iteration_matrix_and_spectral_radius

 E3:
  IF fixed_point_iteration
  THEN assess contraction_or_local_derivative condition

 E4:
  IF large_sparse_linear_system
  THEN consider Krylov_method_and_preconditioning

 E5:
  IF residual_decreases_but_solution_unreliable
  THEN inspect conditioning_and_forward error

 E6:
  IF stagnation_detected
  THEN consider preconditioning_acceleration_rescaling_or_method change

 E7:
  IF divergence_detected
  THEN terminate_or_safeguard rather_than continue blindly

 E8:
  IF stopping_criterion_uses_only_iteration_count
  THEN recommend residual_or_step based criterion when possible

 E9:
  IF comparing_iterative_methods
  THEN compare work_per_iteration_total_iterations_memory_and_accuracy
}

RECURSION {
 ENTRY = IterativeMethod

 EXPAND(IterativeMethod) -> [
  Iteration,
  Iterate,
  InitialGuess,
  UpdateRule,
  FixedPointIteration,
  StationaryIteration,
  NonstationaryIteration,
  JacobiMethod,
  GaussSeidelMethod,
  SuccessiveOverRelaxation,
  RichardsonIteration,
  GradientIteration,
  ConjugateGradientMethod,
  GMRES,
  MINRES,
  BiCGSTAB,
  KrylovSubspaceMethod,
  NewtonIteration,
  QuasiNewtonIteration,
  PicardIteration,
  Residual,
  Convergence,
  Divergence,
  ConvergenceRate,
  SpectralRadius,
  Preconditioner,
  RelaxationParameter,
  StoppingCriterion,
  AccelerationMethod
 ]

 EXPAND(StationaryIteration) -> [
  IterationMatrix,
  SpectralRadius,
  JacobiMethod,
  GaussSeidelMethod,
  SuccessiveOverRelaxation,
  RichardsonIteration
 ]

 EXPAND(KrylovSubspaceMethod) -> [
  ConjugateGradientMethod,
  GMRES,
  MINRES,
  BiCGSTAB,
  ArnoldiProcess,
  LanczosProcess,
  Preconditioner
 ]

 EXPAND(ConvergenceMonitoring) -> [
  ResidualNorm,
  RelativeResidual,
  StepNorm,
  ErrorEstimate,
  Stagnation,
  Divergence,
  IterationLimit
 ]

 STOP_CONDITION =
  "Stop when the initialisation, update rule, residual, stopping criterion, convergence behaviour, conditioning, preconditioning, acceleration and final iteration status are sufficiently resolved."
}

ROUTING {
 PARENT_ONTOLOGY = "Numerical Analysis"

 IMMEDIATE_CONTEXTS = [
  "Numerical Analysis Ontology",
  "Numerical Methods Ontology",
  "Root Finding Ontology",
  "Linear Algebra Ontologies"
 ]

 RELATED_ONTOLOGIES = [
  "Numerical Analysis Ontology",
  "Numerical Methods Ontology",
  "Root Finding Ontology",
  "Numerical Analysis",
  "Applied Mathematics Ontologies",
  "Linear Algebra Ontologies",
  "Matrix Ontologies",
  "Optimisation Ontologies",
  "Differential Equations Ontologies",
  "Computational Model Ontology",
  "Scientific Computing Ontologies",
  "Model Verification Ontology"
 ]

 ROUTE_RULES = [
  "Iterative Methods -> Numerical Analysis Ontology for convergence and error semantics",
  "Iterative Methods -> Numerical Methods Ontology for algorithm families",
  "Iterative Methods -> Root Finding for nonlinear fixed-point and Newton iterations",
  "Iterative Methods -> Linear Algebra for matrix iterations and Krylov methods",
  "Iterative Methods -> Optimisation for gradient and quasi-Newton iterations",
  "Iterative Methods -> Differential Equations for nonlinear solver iterations within discretised systems",
  "Iterative Methods -> Computational Model for executable solver implementation",
  "Iterative Methods -> Scientific Computing for large-scale sparse computation",
  "Iterative Methods -> Model Verification for residual and convergence evidence"
 ]
}

UPDATE_MODEL {
 MODE = "append-compatible semantic versioning"

 MAJOR = "ontology-breaking conceptual change"
 MINOR = "new compatible iterative algorithms, acceleration techniques or reasoning pathways"
 PATCH = "clarification, metadata or formatting correction"

 RULES = [
  "Preserve successive-approximation semantics.",
  "Preserve initial-guess semantics.",
  "Preserve update-rule semantics.",
  "Preserve residual-versus-error distinction.",
  "Preserve stopping-criterion semantics.",
  "Preserve stationary-iteration spectral-radius semantics.",
  "Preserve preconditioning solution equivalence.",
  "Preserve machine-readable iterative-method semantics."
 ]
}

OUTPUT {
 CANONICAL_DEFINITION =
  "An iterative method generates successive approximations to a mathematical solution until a convergence or stopping condition is met."

 INITIALISATION_SUMMARY =
  "Iteration begins from an initial guess and declared update rule."

 RESIDUAL_SUMMARY =
  "Residuals measure equation mismatch and are commonly used to monitor progress."

 CONVERGENCE_SUMMARY =
  "Convergence describes whether iterates approach the intended solution."

 STATIONARY_SUMMARY =
  "A stationary linear iteration converges for every initial guess when the spectral radius of its iteration matrix is less than one."

 KRYLOV_SUMMARY =
  "Krylov methods construct approximations from nested subspaces generated by repeated matrix action on the initial residual."

 PRECONDITIONING_SUMMARY =
  "Preconditioning transforms the numerical problem to improve iterative convergence while preserving the target solution."

 STOPPING_SUMMARY =
  "Stopping criteria should combine tolerances, scaling, residual or step information and an iteration limit."

 ACCELERATION_SUMMARY =
  "Relaxation, extrapolation and history-based methods can accelerate convergence when applied appropriately."
}

FLOW {
 INPUT
 -> detect_iterative_method_context
 -> identify mathematical_problem_initial_guess_update_rule_norm_tolerances_iteration_limit_conditioning_and_preconditioner
 -> classify stationary_nonstationary_fixed_point_Krylov_Newton_relaxation_or_accelerated method
 -> initialise iterate_and_residual
 -> apply update_rule
 -> monitor residual_step_error_estimate_and_breakdown indicators
 -> apply preconditioning_relaxation_or_acceleration when appropriate
 -> assess convergence_rate_stagnation_divergence_and_conditioning
 -> apply stopping criterion
 -> route to numerical_analysis_ontology numerical_methods root_finding linear_algebra optimisation differential_equations computational_model scientific_computing_or_model_verification ontology
 -> recursively_expand_required_dependencies
 -> verify_result
 -> assign_confidence
 -> produce_semantic_output
 -> END
}

SEMANTIC_SUMMARY {
 "The Iterative Methods Ontology defines numerical algorithms based on successive approximation. It supports fixed-point, stationary, Krylov, Newton and relaxation methods; initial guesses, update rules, residuals, stopping criteria, convergence rates, spectral-radius analysis, preconditioning, acceleration, stagnation and divergence detection, and large-scale solver reasoning."
}

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

}

END_FLOW