5.24. Numerical Methods (Mandatory)

5.24. Numerical Methods (Mandatory)

Figure 5.24: Connection Map. MA202 Numerical Methods

5.24.1. Justification ↑ Back to top

Numerical methods are a fundamental tool shared by computer science and engineering disciplines for approximating solutions to mathematical problems that cannot be solved analytically. This course provides an introduction to the most common numerical methods, including error analysis, solution of nonlinear equations, interpolation, numerical integration, and solution of differential equations, in scientific and engineering contexts.

5.24.2. Generales Goals ↑ Back to top

  1. Understand the importance of numerical methods in solving scientific and engineering problems.
  2. Apply different numerical methods to approximate solutions to mathematical problems.
  3. Analyze the accuracy and efficiency of the numerical methods used.

5.24.3. Contribution to Outcomes ↑ Back to top

AG-C08) Problem Analysis: Identifies, formulates, and analyzes complex computing problems. (Usage)
AG-C11) Use of Tools: Applies modern computing tools in problem solving. (Usage)
AG-C09) Design and Development of Solutions: Designs, implements, and evaluates solutions for complex computing problems. (Usage)

5.24.4. Content ↑ Back to top

5.24.4.1. Error Analysis and Floating-Point Arithmetic (6 hours) [Skills AG-C08,AG-C11] ↑ Back to top

Bibliography: (Chapra and Canale, 2015; Burden and Faires, 2010)

Topics

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

Learning Outcomes

  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]
5.24.4.2. Root-Finding for Nonlinear Equations (10 hours) [Skills AG-C08,AG-C11] ↑ Back to top

Bibliography: (Chapra and Canale, 2015; Burden and Faires, 2010)

Topics

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

Learning Outcomes

  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]
5.24.4.3. Approximation Theory and Interpolation (10 hours) [Skills AG-C08,AG-C11] ↑ Back to top

Bibliography: (Chapra and Canale, 2015; Burden and Faires, 2010)

Topics

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

Learning Outcomes

  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]
5.24.4.4. Numerical Integration and Quadrature (10 hours) [Skills AG-C08,AG-C11] ↑ Back to top

Bibliography: (Chapra and Canale, 2015; Burden and Faires, 2010)

Topics

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

Learning Outcomes

  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]
5.24.4.5. Numerical Methods for Differential Equations (12 hours) [Skills AG-C08,AG-C11] ↑ Back to top

Bibliography: (Chapra and Canale, 2015; Burden and Faires, 2010)

Topics

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

Learning Outcomes

  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]
5.24.4.6. Numerical Linear Algebra (12 hours) [Skills AG-C08,AG-C11] ↑ Back to top

Bibliography: (Burden and Faires, 2010; Trefethen and III, 1997)

Topics

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

Learning Outcomes

  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]
5.24.4.7. Finite Element Method (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Reddy, 2019; Burden and Faires, 2010)

Topics

  1. Weak (variational) formulation of boundary value problems and Sobolev spaces
  2. Galerkin method: finite-dimensional approximation spaces and the stiffness matrix
  3. Triangular and quadrilateral finite element spaces: Lagrange elements and conformity
  4. A priori error estimates: Céa's lemma and interpolation error bounds
  5. A posteriori error estimates and adaptive mesh refinement

Learning Outcomes

  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]
5.24.4.8. Optimization Algorithms (4 hours) [Skills AG-C09,AG-C11] ↑ Back to top

Bibliography: (Nocedal and Wright, 2006)

Topics

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

Learning Outcomes

  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]
5.24.4.9. Parallel and High-Performance Computing (4 hours) [Skills AG-C11] ↑ Back to top

Bibliography: (Pacheco and Malensek, 2022)

Topics

  1. Parallel architectures: shared memory (OpenMP), distributed memory (MPI), and GPU (CUDA)
  2. Performance models: Amdahl's law, roofline model, and communication complexity
  3. Parallel algorithms for dense and sparse linear algebra (ScaLAPACK, PETSc)
  4. Domain decomposition and parallel PDE solvers
  5. Automatic differentiation (forward and reverse mode) and its role in scientific ML

Learning Outcomes

  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]
  3. Apply automatic differentiation to compute gradients of complex scientific functions for optimization [Assessment]
5.24.4.10. Graph Theory (4 hours) [Skills AG-C08] ↑ Back to top

Bibliography: (West, 2001)

Topics

  1. Graphs: definitions, isomorphism, degree sequences, trees, and spanning trees
  2. Connectivity, Menger's theorem, and network flows (max-flow min-cut)
  3. Matchings (Hall's theorem), graph colorings, and the chromatic polynomial
  4. Planar graphs, Euler's formula, Kuratowski's theorem, and the four-color theorem
  5. Adjacency and Laplacian matrices, eigenvalues, and expander graphs

Learning Outcomes

  1. Identify structural properties of graphs (connectivity, planarity, bipartiteness) and apply Euler's formula [Familiarity]
  2. Apply Hall's marriage theorem and network flow algorithms to matching and routing problems [Usage]
  3. Analyze a graph's spectrum to bound its chromatic number and connectivity properties [Assessment]
5.24.4.11. Time Series Analysis (2 hours) [Skills AG-C08,AG-C11] ↑ Back to top

Bibliography: (Shumway and Stoffer, 2017)

Topics

  1. Stationarity, autocovariance function, and the autocorrelation function (ACF)
  2. ARMA models: identification, estimation (Yule-Walker, MLE), and diagnostics
  3. Spectral density, the periodogram, and Wiener-Khinchin theorem
  4. State-space models and the Kalman filter
  5. ARIMA models, seasonal adjustment, and multi-step forecasting

Learning Outcomes

  1. Identify stationarity and determine the order of an ARMA model from ACF and PACF plots [Familiarity]
  2. Fit ARIMA models to time series data, validate residuals, and produce forecasts [Usage]
  3. Apply the Kalman filter to estimate hidden states in a linear Gaussian state-space model [Assessment]

5.24.5. Bibliography ↑ Back to top

Chapra, S. C. and Canale, R. P. (2015). Numerical Methods for Engineers. McGraw-Hill Education.

Burden, R. L. and Faires, J. D. (2010). Numerical Analysis. Cengage Learning.

Trefethen, L. N. and III, D. B. (1997). Numerical Linear Algebra. SIAM.

Reddy, J. N. (2019). An Introduction to the Finite Element Method. McGraw-Hill Education, 4th edition.

Nocedal, J. and Wright, S. J. (2006). Numerical Optimization. Springer, 2nd edition.

Pacheco, P. S. and Malensek, M. (2022). An Introduction to Parallel Programming. Morgan Kaufmann, 2nd edition.

West, D. B. (2001). Introduction to Graph Theory. Prentice Hall, 2nd edition.

Shumway, R. H. and Stoffer, D. S. (2017). Time Series Analysis and Its Applications: With R Examples. Springer, 4th edition.

Spotted a typo, an outdated course, a broken link, or have a suggestion? Let us know.

Scan to open on your phone