• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
For visually-impairedFor visually-impairedUser profile (HSE staff only)Search
Advanced search
Menu
HSE University
User profile (HSE staff only)Search
Advanced search

Course Syllabus

Bachelor 2020/2021

Numerical Methods

Type: Compulsory course (Applied Mathematics)
Area of studies: Applied Mathematics
Delivered by: School of Applied Mathematics
Where: HSE Tikhonov Moscow Institute of Electronics and Mathematics (MIEM HSE)
When: 3 year, 3, 4 module
Mode of studies: distance learning
Open to: students of one campus
Instructors: Evgeny Burovskiy, Sergey Petropavlovsky, Ksenia Zagvozdina
Language: English
ECTS credits: 4
Contact hours: 70

Course Syllabus

Full Syllabus

Abstract

Numerical computations historically play a crucial role in natural sciences and engineering. These days however, it’s not only traditional «hard sciences»: whether you do digital humanities or biotechnology, whether you design novel materials or build artificial intelligence systems, virtually any quantitative work involves some amount of numerical computing . These days, you hardly ever implement the whole computation yourselves from scratch. We rely on libraries which package tried-and-tested, battle-hardened numerical primitives. It is vanishingly rare however that a library contains a single pre-packaged routine which does all what you need. Numerical computing involves assembling these building blocks into computational pipelines. This kind of work requires a general understanding of basic numerical methods, their strengths and weaknesses, their limitations and their failure modes. And this is exactly what this course is about. It is meant to be an introductory, foundational course in numerical analysis, with the focus on basic ideas. We will review and develop basic characteristics of numerical algorithms (convergence, approximation, stability, computational complexity and so on), and will illustrate them with several classic problems in numerical mathematics. You will also work on implementing abstract mathematical constructions into working prototypes of numerical code. Upon completion of this course, you will have an overview of the main ideas of numerical computing, and will have a solid foundation for reading up on and working with more advanced numerical needs of your specific subject area. As prerequisites for this course, we assume a basic command of college-level mathematics (linear algebra and calculus, mostly), and a basic level of programming proficiency.
Learning Objectives

Learning Objectives

  • Basic command of modern numerical methods of applied maths
  • Basic use of common packages and libraries for numeric and scientific computing
Expected Learning Outcomes

Expected Learning Outcomes

  • Knowledge of mathematical foundations of numerical methods used in contemporary fundamental and applied research and development.
  • Ability to choose an appropriate numerical method for a given problem.
  • Experience working with modern software packages and libraries for numerical and scientific computing.
Course Contents

Course Contents

  • Numerical mathematics.
    Overview of computational problems: set-ups and approaches. Correctness, accuracy, stability, condition numbers. Roundoff errors. Machine arithmetics. Uncertainties.
  • Matrix factorizations
    QR factorization of a matrix. Householder reflections and Givens rotations. SVD factorization. Properties of singular vectors and singular values. Eckhart-Young theorem. Moore-Penrose pseudoinverse. Over- and under-determined systems of linear equations. Solving linear systems in a least-squares sense. Ordinary least squares.
  • Eigenvalue problem.
    The eigenvalue problem. Power iteration, inverse iteration. Shift-invert mode. QR algorithm.
  • Systems of linear equations: direct methods.
    Vector and matrix norms. Condition number of a linear system. Gaussian elimination and LU decomposition of a matrix. Pivoting. Computational complexity. Cholesky decomposition for PSD matrices. Tridiagonal systems, Thomas algorithm.
  • Systems of linear equations: iterative methods.
    Jacobi iteration. Seidel iteration. Convergence properties and convergence theorems. Canonic form of iterative methods. Variational approaches.
  • Nonlinear equations and systems of equations.
    Localization of roots. Bisection, simple iteration and its variations. Modified schemes, Newton's method. Convergence theorems. A priori and a posteriori error estimates. Multiple roots. Inverse quadratic interpolation. Hybrid schemes.
  • Interpolation of functions.
    Interpolation problem. Univariate interpolation. Interpolation polynomial in the Lagrange form. Runge phenomenon. Chebyshev nodes. Piecewise polynomial interpolation, splines. Hermite cubic polynomial. Construction of a spline interpolant. Boundary conditions. Monotone interpolants.
  • Numerical differentiation
    Finite-difference formulas. Optimal differentiation step. Construction of higher-order FD schemes. Richardson extrapolation and Neville algorithm. Algorithmic differentiation.
  • Numerical integration
    Elementary quadrature rules: rectangle formulas, trapezoids, Simpson's rule. Gaussian quadratures.
  • Initial value problem for ODEs
    Ordinary differential equations. Initial value problem. Implicit and explicit finite difference schemes. Euler rule and its modifications. Runge-Kutta methods. Linear multistep methods: convergence, approximation and stability. Zero-stability of LMMs. A-stability, stiff systems. Dahlquist barriers.
  • Fredholm integral equations.
    Fredholm equations of the first and second kinds. Fredholm alternative. Nystrom method of solving FIE of the 2nd kind.
  • Monte Carlo methods.
    Buffon's needle. MC integration in d>1. Pseudo random and quasi-random (low-discrepancy) sequences. Sampling from non-uniform distributions. Markov chain MC.
Assessment Elements

Assessment Elements

  • non-blocking Homework problems A
  • non-blocking In-class activity
  • non-blocking Exam
    The final grade can be set based on the accumulated grade, without taking the exam, provided there is a non-zero grade on at least one problem type B from each problem set.
  • non-blocking Online course
  • non-blocking Homework problems B
Interim Assessment

Interim Assessment

  • Interim assessment (4 module)
    0.2 * Exam + 0.2 * Homework problems A + 0.3 * Homework problems B + 0.1 * In-class activity + 0.2 * Online course
Bibliography

Bibliography

Recommended Core Bibliography

  • Вычислительные методы для инженеров : учеб. пособие для вузов, Амосов, А. А., 2003

Recommended Additional Bibliography

  • William H. Press, Saul A. Teukolsky, William T. Vetterling, & Brian P. Flannery. (1992). Numerical Recipes in C: The Art of Scientific Computing. Second Edition. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.9CFCD6AE
  • Wright, S. J., & Nocedal, J. (2015). Numerical optimization. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.92C9B6B0
  • Численные методы : учеб. пособие для вузов, Калиткин, Н. Н., 2011
  • Численные методы, Самарский, А. А., 1989