Численные методы

Краткое содержание учебной дисциплины, модуля / Brief summary

Введение. Основные задачи и содержание вычислительной математики. Вычислительный эксперимент (А. А. Самарский).

Элементы теории погрешностей. Приближённые числа, значащие и верные цифры. Абсолютная и относительная погрешности. Погрешности арифметических операций. Прямая и обратная задачи теории погрешностей. Погрешность округлений на ЭВМ. Стандарт IEEE 754.

Интерполирование и приближение функций. Алгебраическое интерполирование. Интерполяционный многочлен Лагранжа. Конечные и разделённые разности. Интерполяционные многочлены Ньютона (для равных и неравных узлов). Погрешность интерполирования. Выбор узлов на основе многочленов Чебышева. Интерполирование кубическими сплайнами. Задача аппроксимации. Метод наименьших квадратов для линейных моделей.

Приближённое вычисление интегралов. Квадратурные формулы общего вида. Формулы Ньютона–Котеса: трапеций, Симпсона. Составные формулы, оценка погрешности. Правило Рунге. Квадратурные формулы Гаусса.

Численные методы решения систем линейных алгебраических уравнений (СЛАУ). Нормы векторов и матриц. Число обусловленности. Прямые методы: метод Гаусса с выбором ведущего элемента, LU-разложение, метод прогонки для трёхдиагональных систем. Итерационные методы: Якоби, Зейделя, последовательной верхней релаксации (SOR). Понятие о нестационарных методах (сопряжённых градиентов) и предобуславливании.

Вычисление собственных значений и собственных векторов матриц. Основные свойства. Инвариантность спектра при преобразовании подобия. Степенной метод.

Решение нелинейных уравнений и систем. Отделение корней. Метод дихотомии. Метод простой итерации (условие сходимости). Метод Ньютона и его модификации. Кратные корни.

Численное решение задачи Коши для обыкновенных дифференциальных уравнений (ОДУ). Одношаговые методы: метод Эйлера, методы Рунге–Кутты. Многошаговые методы: метод Адамса. Устойчивость, условие корней. Жёсткие системы ОДУ. А-устойчивость. Метод Гира.

Численное решение краевых задач для ОДУ. Разностный метод для уравнения второго порядка. Интегро-интерполяционный метод. Компактные разностные схемы. Метод Галёркина. Аппроксимация и сходимость. Оценка погрешности. Методы редукции к задачам Коши: метод стрельбы, дифференциальная прогонка.

Построение и исследование разностных схем для задач математической физики. Уравнение теплопроводности (параболическое): явная и неявная схемы. Анализ устойчивости по Фурье. Условие Куранта. Уравнение переноса (гиперболическое): схема «уголок», схема Лакса. Консервативность, монотонность. Уравнение Пуассона (эллиптическое): пятиточечный шаблон. Решение сеточных уравнений методом Зейделя.

Introduction. Main tasks and content of computational mathematics. Computational experiment (A. A. Samarsky).

Elements of error theory. Approximate numbers, significant and correct digits. Absolute and relative errors. Errors of arithmetic operations. Direct and inverse problems of error theory. Rounding error in computer calculations. IEEE 754 standard.

Interpolation and approximation of functions. Algebraic interpolation. Lagrange interpolation polynomial. Finite and divided differences. Newton interpolation polynomials (for equal and unequal nodes). Interpolation error. Choice of nodes based on Chebyshev polynomials. Cubic spline interpolation. Approximation problem. Least squares method for linear models.

Approximate calculation of integrals. General quadrature formulas. Newton–Cotes formulas: trapezoidal, Simpson’s rule. Composite formulas, error estimation. Runge’s rule. Gaussian quadrature.

Numerical methods for solving systems of linear algebraic equations (SLAE). Norms of vectors and matrices. Condition number. Direct methods: Gaussian elimination with pivoting, LU decomposition, Thomas algorithm for tridiagonal systems. Iterative methods: Jacobi, Seidel, successive over-relaxation (SOR). Concept of non-stationary methods (conjugate gradients) and preconditioning.

Computing eigenvalues and eigenvectors of matrices. Basic properties. Spectrum invariance under similarity transformation. Power method.

Solving nonlinear equations and systems. Root separation. Bisection method. Fixed-point iteration (convergence condition). Newton’s method and its modifications. Multiple roots.

Numerical solution of the Cauchy problem for ordinary differential equations (ODEs). One-step methods: Euler’s method, Runge–Kutta methods. Multi-step methods: Adams method. Stability, root condition. Stiff ODE systems. A—stability. Gear’s method.

Numerical solution of boundary value problems for ODEs. Finite difference method for second-order equations. Integro-interpolation method. Compact difference schemes. Galerkin method. Approximation and convergence. Error estimation. Reduction to Cauchy problems: shooting method, differential sweeping method.

Construction and analysis of finite difference schemes for problems of mathematical physics. Heat equation (parabolic): explicit and implicit schemes. Fourier stability analysis. Courant condition. Advection equation (hyperbolic): upwind scheme, Lax scheme. Conservativeness, monotonicity. Poisson equation (elliptic): five-point stencil. Solving finite difference equations using the Seidel method.

Формируемые компетенции / The formed competences

Специализированная компетенция:

осуществлять обоснованный выбор рациональной численной методики для решения типовых задач механики, проводить ее реализацию с использованием современных программных средств компьютерных вычислений, оценивать корректность полученных результатов и анализировать возможности альтернативных подходов

Specialized competence:

make a well-founded choice of a rational numerical method for solving typical problems of mechanics, carry out its implementation using modern computer software, evaluate the correctness of the obtained results, and analyze the possibilities of alternative approaches.

Результаты обучения (знать, уметь, владеть) / Learning outcomes (know, can, be able to)

В результате освоения учебной дисциплины студент должен

знать:

— источники и виды погрешностей (неустранимая, вычислительная);

— основные приёмы априорной и апостериорной оценки погрешности;

— понятия устойчивости, сходимости и вычислительной сложности;

— условия корректности задачи по Адамару;

— сравнительные характеристики основных классов методов: интерполяции (полиномиальной), численного интегрирования (Ньютона–Котеса, Гаусса), решения СЛАУ (прямые, итерационные), решения ОДУ (одношаговые, многошаговые, явные/неявные);

— преимущества и недостатки явных и неявных методов решения дифференциальных уравнений;

— современные тенденции в вычислительной математике.

уметь:

— оценить корректность постановки задачи;

— выбрать адекватный метод для численного решения поставленной задачи;

— использовать численные методы для решения математических задач алгебры, анализа и дифференциальных уравнений;

— анализировать достоверность и интерпретировать численные результаты.

владеть:

— навыками работы с современными программными средствами численного решения математических и прикладных задач;

— навыками программирования численных алгоритмов;

— основными приёмами априорной и апостериорной оценки погрешности численного решения задач алгебры и анализа.

As a result of mastering the academic discipline, the student must

know:

— sources and types of errors (inherent, computational);

— basic techniques of a priori and a posteriori error estimation;

— concepts of stability, convergence, and computational complexity;

— Hadamard’s well-posedness conditions;

— comparative characteristics of main method classes: interpolation (polynomial), numerical integration (Newton–Cotes, Gauss), solving SLAE (direct, iterative), solving ODEs (one-step, multi-step, explicit/implicit);

— advantages and disadvantages of explicit and implicit methods for solving differential equations;

— modern trends in computational mathematics;

can:

— assess the well-posedness of a problem statement;

— select an adequate method for numerical solution of the given problem;

— use numerical methods to solve mathematical problems in algebra, analysis, and differential equations;

— analyze reliability and interpret numerical results;

be able to:

— work with modern software for numerical solution of mathematical and applied problems;

— program numerical algorithms;

— apply basic techniques of a priori and a posteriori error estimation for numerical solutions of algebra and analysis problems.

Семестр изучения учебной дисциплины, модуля / Semester of study

6

6

Пререквизиты / Prerequisites

— Алгебра и теория чисел;

— Математический анализ; 

— Функциональный анализ;

— Дифференциальные уравнения;

— Уравнения математической физики.

— Algebra and number theory;

— Mathematical analysis;

— Functional analysis;

— Differential equations;

— Equations of mathematical physics.

Трудоемкость в зачетных единицах (кредитах) / Credit units

3 зачетные единицы.

3 credit units.

Количество аудиторных часов и часов самостоятельной работы / Academic hour of students’ class work, 

hours of self-directed learning

Всего 90 часов, из них 52 аудиторных часа и 38 часов самостоятельной работы.

A total of 90 hours, of which 52 academic hours of students’ class work and 38 hours of self-directed learning.

Требования и формы текущей и промежуточной аттестации / Requirements and forms of current and interim certification

Формы текущей аттестации: опрос, письменный отчёт с устной защитой по лабораторным работам, контрольная работа.

Форма промежуточной аттестации: экзамен.

Forms of ongoing assessment: oral questioning, written report with oral defense for laboratory works, test.

Form of interim assessment: exam.