2020/2021
Введение в численные методы
Статус:
Дисциплина общефакультетского пула
Кто читает:
Департамент электронной инженерии
Когда читается:
3 модуль
Преподаватели:
Ихсанов Ренат Шамильевич
Язык:
английский
Кредиты:
3
Контактные часы:
2
Course 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
- Mastering basic knowledge of numerical methods used in modern applied mathematics.
- Acquisition of skills in mathematical packages and libraries of mathematical software.
Expected Learning Outcomes
- Knowledge: mathematical foundations of numerical methods used in modern applied and fundamental research.
- Skills: choose the right numerical method for solving specific mathematical problems.
- Possess: Skills in working with standard math packages.
Course Contents
- Topic 1. Machine arithmetics. Systems of linear algebraic equations.About the University. Introduction. A simple worked example. Machine arithmetics. Representation of real numbers. Machine epsilon. Over- and underflow. A crude estimate of the machine epsilon. Systems of linear equations. Cramer's rule. Gaussian elimination. LU decomposition: the matrix form of the Gaussian elimination. When does the Gaussian elimination work? LU decomposition with pivoting. Permutation matrices.
- Topic 2. Numerical linear algebra.Introduction. Sensitivity of a linear system. Vector norms. Matrix norms. Common matrix norms. Sensitivity of a linear system. Condition number. Cholesky decomposition. Banded matrices. Thomas algorithm. Shermann-Morrison formula. QR decomposition. Constructing the QR decomposition: Householder reflections. Constructing the QR decomposition: Givens rotations.
- Topic 3. Non-linear algebraic equations.Solving non-linear equations. Localization of roots. Bisection. Fixed-point iteration. Aside: convergence rates and related technicalities. Back to the fixed-point iteration. Fine-tuning the fixed-point iteration. Newton's iteration. Multiple roots. Modified Newton's method. Inverse quadratic interpolation. Roots of polynomials. Roots of polynomials: the companion matrix.
- Topic 4. Iterative method for linear systems.Large-scale systems of linear equations. Simple iteration for a linear system. Jacobi iteration. Convergence criteria for simple iteration. Seidel's iteration. Successive over-relaxation. Canonic form of two-step iterative methods for linear systems. Variational approaches: minimum residual method. Copy of Simple iteration for a linear system. Jacobi iteration.
- Topic 5. Interpolation and approximation. Modeling of data.Interpolation and approximation. Modelling of data. Linear least squares problem. Ordinary least squares: the normal equations. Ordinary least squares: QR decomposition of the design matrix. Global polynomial interpolation. Lagrange interpolating polynomial. Quantifying interpolation errors. Runge phenomenon. Chebyshev nodes. Interpolation of the Runge function.
- Topic 6. Numerical calculus: derivatives and integrals.Numerical derivatives. Numerical derivatives: finite differences. Truncation and roundoff errors: an interplay. Higher order schemes. Richardson extrapolation. Integration: numeric quadratures. Convergence rates of simple quadratures. Simple geometric quadratures: Trapezoids, Simpson's rule and all that. Error bounds for quadratures. Romberg extrapolation. Integrals with singularities. A check of convergence. Recap: Newton-Cotes vs Gaussian quadratures. Gaussian quadratures.
- Topic 7. Initial value problem for ordinary differential equations.Initial value problem for an ODE. Discretization. Approximation and convergence. Truncation error or Euler-like schemes. Runge-Kutta methods. Asymptotic stability of ODEs. Stiffness. Linear Multistep methods. Zero-stability of linear multistep methods.
Assessment Elements
- Самостоятельная работа
- Экзамен (тест)If a student misses the exam because of some valid reason, s/he receives «absence» grade. The grade for the course is calculated on the course page on the basis of the student’s number of points that are awarded to the student for answering questions of the proposed tests. Контрольные работы и экзамен по курсу проводятся в письменной форме на платформе Coursera (https://www.coursera.org/learn/intro-to-numerical-analysis). Во время написания контрольных и экзаменационных работ студентам запрещено: общаться с кем-либо, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время контрольной работы или экзамена считается нарушение связи менее часа. Долговременным нарушением связи считается нарушение связи в течение часа и более. При долговременном нарушении связи студент не может продолжить участие в контрольной или экзамене. Процедура пересдачи аналогична процедуре сдачи.
Bibliography
Recommended Core Bibliography
- Вычислительные методы для инженеров : учеб. пособие для вузов, Амосов, А. А., 2003
Recommended Additional Bibliography
- Scott, L. R. (2011). Numerical Analysis. Princeton, New Jersey: Princeton University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1727695
- Введение в численные методы : учеб. пособие для вузов, Самарский, А. А., 1987
- Численные методы : учеб. пособие для вузов, Калиткин, Н. Н., 2011