• 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	1	1
3.5.2 Numerical Integration and Quadrature	1	1
3.5.3 Error Analysis and Floating-Point Arithmetic	1	1
3.5.4 Root-Finding for Nonlinear Equations	1	1
3.5.5 Numerical Linear Algebra	1	1
3.5.6 Numerical Methods for Differential Equations	1	1
3.5.7 Optimization Algorithms	1	1
3.5.8 Finite Element Method	1	1
3.5.9 Parallel and High-Performance Computing	1	1

3.5.1. NSA/Approximation Theory and Interpolation  (CS Core: 1 hr, KA Core: 1 hr) ↑ 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  (CS Core: 1 hr, KA Core: 1 hr) ↑ 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  (CS Core: 1 hr, KA Core: 1 hr) ↑ 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  (CS Core: 1 hr, KA Core: 1 hr) ↑ 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  (CS Core: 1 hr, KA Core: 1 hr) ↑ 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  (CS Core: 1 hr, KA Core: 1 hr) ↑ 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  (CS Core: 1 hr, KA Core: 1 hr) ↑ 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]

3.5.8. NSA/Finite Element Method  (CS Core: 1 hr, KA Core: 1 hr) ↑ Back to top

Variational formulation, Galerkin methods, finite element spaces, error estimates, and applications to elliptic PDEs.
Topics:
Core

• Weak (variational) formulation of boundary value problems and Sobolev spaces
• Galerkin method: finite-dimensional approximation spaces and the stiffness matrix
• Triangular and quadrilateral finite element spaces: Lagrange elements and conformity
• A priori error estimates: Céa's lemma and interpolation error bounds

Non Core

• A posteriori error estimates and adaptive mesh refinement

Learning Outcomes:
Core:

1. Derive the weak formulation of an elliptic BVP and show its equivalence to the strong form [Familiarity]
2. Assemble the global stiffness matrix and load vector for a linear finite element discretization [Usage]
3. Estimate the \(H^1\) error of a finite element solution using Céa's lemma and interpolation theory [Assessment]

3.5.9. NSA/Parallel and High-Performance Computing  (CS Core: 1 hr, KA Core: 1 hr) ↑ Back to top

Parallel architectures, performance models, parallel algorithms for linear algebra, and GPU computing.
Topics:
Core

• Parallel architectures: shared memory (OpenMP), distributed memory (MPI), and GPU (CUDA)
• Performance models: Amdahl's law, roofline model, and communication complexity
• Parallel algorithms for dense and sparse linear algebra (ScaLAPACK, PETSc)
• Domain decomposition and parallel PDE solvers

Non Core

• Automatic differentiation (forward and reverse mode) and its role in scientific ML

Learning Outcomes:
Core:

1. Explain Amdahl's law and identify the bottlenecks limiting parallel speedup in a given algorithm [Familiarity]
2. Implement a parallel linear algebra routine using MPI or OpenMP and measure parallel efficiency [Usage]

NonCore:

1. Apply automatic differentiation to compute gradients of complex scientific functions for optimization [Assessment]