7.25. Numerical Methods (Mandatory)

7.25. Numerical Methods (Mandatory)

Figure 7.25: Connection Map. MA202 Numerical Methods

7.25.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.

7.25.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.

7.25.3. Contribution to Outcomes ↑ Back to top

ABET-1) An ability to identify, formulate, and solve complex engineering problems by applying principles of engineering, science, and mathematics. (Usage)
ABET-6) An ability to develop and conduct appropriate experimentation, analyze and interpret data, and use engineering judgment to draw conclusions. (Usage)
ABET-2) An ability to apply engineering design to produce solutions that meet specified needs with consideration of public health, safety, and welfare, as well as global, cultural, social, environmental, and economic factors. (Usage)

7.25.4. Content ↑ Back to top

7.25.4.1. Error Analysis and Floating Point Arithmetic (6 hours) [Skills ABET-1,ABET-6] ↑ Back to top

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

Topics

  1. Floating point representation and round-off errors in engineering software
  2. Conditioning of engineering problems and stability of numerical algorithms
  3. Truncation error in series approximations and finite difference stencils
  4. Error propagation through chains of computations in engineering simulations

Learning Outcomes

  1. Explain the sources and consequences of round-off and truncation errors in engineering computations [Familiarity]
  2. Calculate the condition number of a linear system and interpret its effect on solution accuracy [Assessment]
  3. Estimate the propagation of measurement uncertainties through an engineering calculation chain [Usage]
  4. Select numerical methods with appropriate stability properties for engineering simulation requirements [Assessment]
7.25.4.2. Numerical Solution of Nonlinear Equations (10 hours) [Skills ABET-1,ABET-6] ↑ Back to top

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

Topics

  1. Bracketing methods: bisection and false position
  2. Newton-Raphson method and the secant method
  3. Order of convergence and stopping criteria in iterative methods

Learning Outcomes

  1. Explain the basis and convergence guarantees of the bisection and false position methods [Familiarity]
  2. Apply the Newton-Raphson and secant methods to approximate roots of engineering equations [Usage]
  3. Compare the convergence order of different iterative methods and select the most appropriate one for a given problem [Assessment]
7.25.4.3. Approximation Theory and Interpolation (10 hours) [Skills ABET-1,ABET-6] ↑ Back to top

Bibliography: (Chapra and Canale, 2015a; 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]
7.25.4.4. Numerical Integration and Quadrature (10 hours) [Skills ABET-1,ABET-6] ↑ Back to top

Bibliography: (Chapra and Canale, 2015a; 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]
7.25.4.5. Numerical Methods for ODEs and PDEs (12 hours) [Skills ABET-1,ABET-6] ↑ Back to top

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

Topics

  1. Runge-Kutta methods and adaptive time-stepping for engineering ODE problems
  2. Stability analysis and stiffness in engineering ODE integrators
  3. Finite difference discretization of engineering PDEs (heat equation, Laplace equation)
  4. Finite element and shooting methods for engineering boundary value problems

Learning Outcomes

  1. Implement a fourth-order Runge-Kutta integrator for a mechanical vibration problem [Usage]
  2. Determine the region of absolute stability for an explicit time-stepping scheme [Assessment]
  3. Discretize the 2D heat equation using finite differences and set up the resulting linear system [Usage]
  4. Compare finite difference and finite element approaches for solving an engineering PDE [Assessment]
7.25.4.6. Numerical Linear Algebra (12 hours) [Skills ABET-1,ABET-6] ↑ Back to top

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

Topics

  1. LU and QR decompositions for solving engineering linear systems
  2. Iterative solvers: Jacobi, Gauss-Seidel, and Conjugate Gradient for large sparse systems
  3. Singular Value Decomposition (SVD) for data fitting and model reduction
  4. Sparse matrix storage formats and efficient solvers for large engineering FEM/FVM systems

Learning Outcomes

  1. Solve engineering linear systems using LU decomposition with partial pivoting [Usage]
  2. Analyze the convergence rate of iterative solvers applied to engineering stiffness matrices [Assessment]
  3. Implement a Conjugate Gradient solver for a large symmetric positive-definite engineering system [Usage]
  4. Apply SVD to compress a structural mode shape dataset and assess the approximation quality [Assessment]
7.25.4.7. Finite Element Method (8 hours) [Skills ABET-1,ABET-2] ↑ Back to top

Bibliography: (Reddy, 2019a; 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]
7.25.4.8. Optimization Algorithms (4 hours) [Skills ABET-2,ABET-6] ↑ 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 the alternating direction method of multipliers (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]
7.25.4.9. Parallel and High-Performance Computing (4 hours) [Skills ABET-6] ↑ 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]
7.25.4.10. Graph Theory (4 hours) [Skills ABET-1] ↑ 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]
7.25.4.11. Time Series Analysis (2 hours) [Skills ABET-1,ABET-6] ↑ 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]

7.25.5. Bibliography ↑ Back to top

Chapra, S. C. and Canale, R. P. (2015a). 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. (2019a). 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