• ES Español
• EN English

3.5. Numerical and Scientific Analysis (NSA)

This area covers numerical algorithms for computation: error analysis, linear algebra solvers, numerical integration, differential equations, and optimization methods essential for implementing reliable computational systems and scientific software.

Knowledge Area (KA)	CS Core	KA Core
3.5.1 Approximation Theory and Interpolation	Elective
3.5.2 Numerical Integration and Quadrature	Elective
3.5.3 Error Analysis and Floating-Point Arithmetic	Elective
3.5.4 Root-Finding for Nonlinear Equations	Elective
3.5.5 Numerical Linear Algebra	Elective
3.5.6 Numerical Methods for Differential Equations	Elective
3.5.7 Optimization Algorithms	Elective

3.5.1. NSA/Approximation Theory and Interpolation ↑ Back to top

Polynomial and spline interpolation, best approximation, Chebyshev polynomials, and rational approximation.
Topics:
Core

• Polynomial interpolation: Lagrange, Newton divided differences, and Runge's phenomenon
• Spline interpolation: cubic splines, B-splines, and piecewise polynomial methods
• Best approximation in normed spaces: Chebyshev (minimax) and least squares
• Chebyshev polynomials: properties, orthogonality, and spectral convergence
• Trigonometric approximation and the fast Fourier transform (FFT)

Learning Outcomes:
Core:

1. Explain Runge's phenomenon and justify the choice of Chebyshev nodes to mitigate it [Familiarity]
2. Construct cubic spline and Chebyshev interpolants for given data and estimate the interpolation error [Usage]
3. Apply the FFT to efficiently compute trigonometric approximations of a sampled function [Assessment]

3.5.2. NSA/Numerical Integration and Quadrature ↑ Back to top

Quadrature rules, adaptive integration, Gaussian quadrature, and multi-dimensional integration.
Topics:
Core

• Newton-Cotes rules: trapezoidal, Simpson's, and composite rules; error analysis
• Adaptive quadrature and automatic error control
• Gaussian quadrature: optimal nodes and weights, orthogonal polynomial connection
• Numerical treatment of improper and singular integrals
• Monte Carlo integration and quasi-Monte Carlo methods for high-dimensional integrals

Learning Outcomes:
Core:

1. Derive the error formula for composite Simpson's rule and identify its order of accuracy [Familiarity]
2. Select and apply an appropriate quadrature rule (Gaussian, adaptive) based on integrand regularity [Usage]
3. Apply Monte Carlo integration to estimate high-dimensional integrals and quantify the statistical error [Assessment]

3.5.3. NSA/Error Analysis and Floating-Point Arithmetic ↑ Back to top

Sources of numerical error, IEEE 754 floating-point arithmetic, rounding, cancellation, and forward and backward error analysis, critical for reliable software engineering.
Topics:
Core

• IEEE 754 floating-point representation: machine epsilon, overflow, underflow, and rounding modes
• Rounding errors, catastrophic cancellation, and loss of significance
• Forward and backward error analysis; condition number of a problem
• Numerical stability: stable vs. unstable algorithms; Wilkinson's backward error analysis
• Error propagation in arithmetic operations and function evaluation

Learning Outcomes:
Core:

1. Explain the IEEE 754 floating-point standard and identify the sources of rounding and cancellation errors [Familiarity]
2. Estimate the condition number of a problem and predict the accuracy of a numerical result [Usage]
3. Analyze an algorithm for numerical stability using forward and backward error bounds [Assessment]

3.5.4. NSA/Root-Finding for Nonlinear Equations ↑ Back to top

Iterative methods for approximating roots of nonlinear equations and systems of nonlinear equations, the basis of solvers used in optimization and machine learning.
Topics:
Core

• Bisection method: interval bracketing, stopping criteria, and error bound
• Newton-Raphson method: derivation, quadratic convergence, and failure cases
• Secant method as an alternative to Newton's method without an explicit derivative
• Order of convergence and efficiency comparison among iterative methods
• Extension of Newton's method to systems of nonlinear equations via the Jacobian matrix, the basis of solvers used in machine learning

Learning Outcomes:
Core:

1. Compare the convergence guarantees of the bisection, Newton-Raphson, and secant methods [Familiarity]
2. Implement the Newton-Raphson method to approximate roots of a nonlinear function [Usage]
3. Analyze the order of convergence of an iterative method and justify its choice based on computational cost [Assessment]

3.5.5. NSA/Numerical Linear Algebra ↑ Back to top

Algorithms for solving linear systems, least squares, eigenvalue problems, and matrix factorizations, applied in machine learning and scientific computing.
Topics:
Core

• Gaussian elimination with partial pivoting, LU factorization, and complexity analysis
• QR factorization via Householder and Gram-Schmidt; least squares problems
• Eigenvalue algorithms: power iteration, QR algorithm, and the Lanczos method
• Singular value decomposition: computation, truncation, and applications (PCA, pseudoinverse)
• Iterative methods for large sparse systems: CG, GMRES, and preconditioning

Learning Outcomes:
Core:

1. Compare direct and iterative solvers and select the appropriate method for a given matrix structure [Familiarity]
2. Apply QR factorization and SVD to solve least squares problems and compute low-rank approximations [Usage]
3. Analyze the numerical stability and computational cost of eigenvalue algorithms [Assessment]

3.5.6. NSA/Numerical Methods for Differential Equations ↑ Back to top

Finite difference and Runge-Kutta methods for ODEs, stability analysis, and finite difference methods for PDEs, used in scientific simulation and physics-based computing.
Topics:
Core

• Runge-Kutta methods: Euler, RK4, and embedded methods for error control
• Linear multistep methods: Adams-Bashforth, Adams-Moulton, and BDF methods
• Stability analysis: zero-stability, absolute stability regions, and stiff ODEs
• Finite difference methods for parabolic and elliptic PDEs: stability and convergence

Learning Outcomes:
Core:

1. Compare explicit and implicit ODE solvers and explain their relative stability for stiff problems [Familiarity]
2. Implement a Runge-Kutta method with adaptive step control and apply it to a system of ODEs [Usage]
3. Analyze the stability and convergence of a finite difference scheme for a parabolic PDE [Assessment]

3.5.7. NSA/Optimization Algorithms ↑ Back to top

Gradient methods, Newton and quasi-Newton methods, constrained optimization, and convex optimization algorithms foundational for training machine learning models.
Topics:
Core

• Gradient descent and line search methods: Armijo-Wolfe conditions and convergence rates
• Newton's method and quasi-Newton methods (BFGS, L-BFGS)
• Constrained optimization: KKT conditions, penalty methods, and sequential quadratic programming
• Convex optimization algorithms: interior-point methods and ADMM
• Stochastic gradient descent (SGD), variance reduction, and Adam optimizer

Learning Outcomes:
Core:

1. Explain the convergence guarantees of gradient descent for smooth convex functions [Familiarity]
2. Apply Newton and quasi-Newton methods to unconstrained optimization problems [Usage]
3. Formulate a constrained optimization problem as a KKT system and apply an interior-point method [Assessment]