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

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

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

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

Интерполирование и приближение функций. Системы Функций Чебышева. Интерполирование обобщенными многочленами. Алгебраическое интерполирование. Построение интерполяционного многочлена в форме Лагранжа. Конечные разности. Разделенные и разности, их свойства. Интерполяционный многочлен Ньютона. Представление погрешности интерполирования. Минимизация погрешности интерполирования дискретно заданных функций. Многочлены Чебышева. Минимизация погрешности интерполирования для функций, заданных на отрезке. Интерполирование по равноотстоящим узлам. Интерполирование сплайнами. Интерполяционная задача Эрмита. Тригонометрическое интерполирование. Дискретное и быстрое преобразование Фурье. Численное дифференцирование и оценка его погрешности. Задача аппроксимации. Метод наименьших квадратов.

Приближенное вычисление интегралов. Квадратурные формулы общего вида. Квадратурные формулы, основанные на алгебраическом интерполировании. Простейшие квадратурные правила Ньютона-Котеса. Погрешность интегрирования. Составные квадратурные формулы Ньютона-Котеса. Погрешность интегрирования. Правила Рунге и Эйткена практической оценки погрешности квадратурных формул. Квадратурные формулы типа Гаусса. Оптимизация распределения узлов квадратурной формулы. Частные случаи квадратур гауссова типа. Вычисление интегралов от функций специального вида.

Численные методы решения систем ЛАУ. Нормы векторов и матриц. Оценка погрешности решения систем ЛАУ. Число обусловленности. Прямые методы. Метод Гаусса. Выбор ведущего элемента. LU факторизация. Разложение Холецкого. Метод прогонки и ортогонализации. Итерационные методы решения систем ЛАУ. Метод простой итерации. Сходимость итерационных методов. Оценка числа итераций. Выбор оптимального параметра. Неявные итерационные методы. Понятие о переобуславливателе. Методы Якоби, Зейделя, Последовательной верхней релаксации. Методы наискорейшего спуска и сопряженных градиентов.

Вычисление собственных значений и собственных векторов матриц. Свойства собственных векторов и собственных значений матриц. Преобразование подобия. Каноническая форма Фробениуса. Метод Данилевского. Степенной метод нахождения максимальных по модулю собственных значений. Метод вращений. Понятие о QR алгоритме.

Решение нелинейных уравнений и систем. Отделение корней. Метод дихотомии. Кратные корни. Корни полиномов. Метод простой итерации. Условие сходимости и скорость сходимости. Метод Ньютона. Квадратичная сходимость. Модификации метода Ньютона. Понятие о методах нелинейной оптимизации. Градиентные методы.

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

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

Численное решение интегральных уравнений Фредгольма. Основные подходы к решению интегральных уравнений. Метод Фурье для численного решения интегральных уравнений типа свертки.

Построение и исследование разностных схем для задач математической физики. Разностные схемы для уравнения теплопроводности. Канонический вид и условие устойчивости двухслойных разностных схем. Устойчивость, аппроксимация и сходимость. Разностные схемы для уравнения переноса. Спектральный критерий устойчивости. Разностные схемы для эллиптических уравнений. Принцип максимума. Обзорные занятия по теме «Методы численного решения дифференциальных уравнений». Реализация разностных схем. Метод переменных направлений и метод дробных шагов.

Introduction. On the main tasks and content of computational mathematics. The content and purpose of the computational experiment as interpreted by A.A. Samarsky.

Elements of error theory. Significant and correct digits in writing approximate numbers. Absolute and relative errors. Errors in arithmetic operations. Direct and inverse problems of error theory. Examples of unstable algorithms. Error in computer calculations. Rounding error and computer recording of numbers.

Interpolation and approximation of functions. Systems of Chebyshev Functions. Interpolation by generalized polynomials. Algebraic interpolation. Construction of an interpolation polynomial in Lagrange form. Finite differences. Separated and differences, their properties. Newton’s interpolation polynomial. Interpolation error representation. Minimizing the interpolation error of discretely specified functions. Chebyshev polynomials. Minimization of interpolation error for functions specified on a segment. Interpolation by equally spaced nodes. Spline interpolation. Hermite interpolation problem. Trigonometric interpolation. Discrete and fast Fourier transform. Numerical differentiation and estimation of its error. Approximation problem. Least square method.

Approximate calculation of integrals. General quadrature formulas. Quadrature formulas based on algebraic interpolation. The simplest Newton-Cotes quadrature rules. Integration error. Composite Newton-Cotes quadrature formulas. Integration error. Runge and Aitken’s rules for practical estimation of the error of quadrature formulas. Quadrature formulas of Gauss type. Optimization of the distribution of nodes of the quadrature formula. Special cases of Gaussian-type quadratures. Calculation of integrals of functions of a special form.

Numerical methods for solving systems of linear algebraic equations. Norms of vectors and matrices. Estimation of the error in solving systems of linear algebraic equations. Condition number. Direct methods. Gauss method. Selecting a leading element. LU factorization. Cholesky decomposition. Method of sweeping and orthogonalization. Iterative methods for solving systems of linear algebraic equations. Simple iteration method. Convergence of iterative methods. Estimation of the number of iterations. Selecting the optimal parameter. Implicit iterative methods. The concept of a preconditioner. Jacobi, Seidel, Sequential upper relaxation methods. Methods of steepest descent and conjugate gradients.

Вычисление собственных значений и собственных векторов матриц. Свойства собственных векторов и собственных значений матриц. Преобразование подобия. Каноническая форма Фробениуса. Метод Данилевского. Степенной метод нахождения максимальных по модулю собственных значений. Метод вращений. Понятие о QR алгоритме.

Решение нелинейных уравнений и систем. Отделение корней. Метод дихотомии. Кратные корни. Корни полиномов. Метод простой итерации. Условие сходимости и скорость сходимости. Метод Ньютона. Квадратичная сходимость. Модификации метода Ньютона. Понятие о методах нелинейной оптимизации. Градиентные методы.

Numerical solution of the Cauchy problem for ordinary differential equations. One-step methods. Euler’s method. Estimation of the speed of convergence. Runge-Kutta methods. Multi-step methods. Stability, root conditions. Adams method. The concept of rigid systems of ordinary differential equations. A-sustainability. Geer’s method.

Numerical solution of boundary value problems for ordinary differential equations. Difference method for solving a boundary value problem for a second order equation. Methods for constructing difference schemes. Integro-interpolation method. The concept of compact difference schemes. Galerkin method. Approximation and convergence. Error estimation of linear difference schemes. Difference methods for solving boundary value problems for nonlinear ordinary differential equations. Methods for reducing boundary value problems to Cauchy problems. Differential sweep methods and shooting method.

Numerical solution of Fredholm integral equations. Basic approaches to solving integral equations. Fourier method for numerical solution of integral equations of convolution type.

Construction and study of difference schemes for problems of mathematical physics. Difference schemes for the heat equation. Canonical form and stability condition for two-layer difference schemes. Stability, approximation and convergence. Difference schemes for the transport equation. Spectral stability criterion. Difference schemes for elliptic equations. Maximum principle. Review lessons on the topic “Methods for numerical solution of differential equations.” Implementation of difference schemes. Alternating Direction Method and Fractional Step 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 results obtained and analyze the possibilities of alternative approaches.

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

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

знать:

источники погрешности численных результатов;

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

требования корректности постановки задачи;

основные приемы оценки погрешности численных методов;

 назначение и вычислительные качества наиболее популярных численных методов интерполирования (формулы Лагранжа и Ньютона, метод наилучшего приближения в среднеквадратичной норме), приближенного интегрирования (формулы трапеций и Симпсона, методы типа Гаусса наивысшей алгебраической степени точности), для задач алгебры, дифференциальных уравнений (метод Гаусса, LU-факторизация, итерационные методы Ричардсона, Якоби, Зейделя, последовательной верхней релаксации, минимальных невязок, сопряженных градиентов, методы Рунге-Кутты и Адамса, метод стрельбы, быстрое дискретное преобразование Фурье);    

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

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

уметь: 

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

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

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

 анализировать достоверность и трактовать численные результаты;

владеть:

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

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

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

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

know:

– sources of error in numerical results;

– concepts of stability, convergence and computational complexity of numerical algorithms;

– requirements for the correctness of the problem statement;

– basic techniques for assessing the error of numerical methods;

– the purpose and computational qualities of the most popular numerical interpolation methods (Lagrange and Newton formulas, the method of best approximation in the root mean square norm), approximate integration (Trapezoidal and Simpson formulas, Gauss-type methods of the highest algebraic degree of accuracy), for algebra problems, differential equations (Gauss method , LU factorization, iterative methods of Richardson, Jacobi, Seidel, sequential upper relaxation, minimal residuals, conjugate gradients, Runge-Kutta and Adams methods, shooting method, fast discrete Fourier transform);

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

– modern trends in the development of methods for numerical solution of mathematical and applied problems;

can:

– evaluate the correctness of the problem statement;

– choose an adequate method for numerical solution of the problem;

– use numerical methods to solve mathematical problems of algebra, analysis and differential equations;

– analyze the reliability and interpret numerical results;

be able to:

– skills of working with modern software for numerical solution of mathematical and applied problems;

– skills in programming numerical algorithms;

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

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

7

7

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

– Компьютерная математика,

– Алгебра и теория чисел,

– Математический анализ,

– Функциональный анализ,

– Дифференциальные уравнения,

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

– Computer mathematics,

– Algebra and number theory,

– Mathematical analysis,

– Functional analysis,

– Differential equations,

– Equations of mathematical physics.

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

0 зачетных единиц.

0 credit units.

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

hours of self-directed learning

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

A total of 108 hours, of which 72 academic hours of students’ class work and 36 hours of self-directed learning/

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

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

Зачет.

Survey, written report with oral defense on laboratory work, written report with oral defense on homework, written report with oral defense on solving problems and exercises, verification work.

End-of-term tests.