- •Вычислительные методы и компьютерная алгебра
- •Общие сведения Сведения об эумк
- •Методические рекомендации по изучению дисциплины
- •Рабочая учебная программа для специальности
- •Пояснительная записка
- •Содержание дисциплины
- •1. Название тем лекционных занятий, их содержание, объем в часах
- •2. Перечень тем лабораторных занятий, их наименование и объем в часах
- •3. Литература
- •3.1. Основная
- •3.2. Дополнительная
- •4. Перечень компьютерных программ, наглядных и других пособий, методических указаний и материалов к техническим средствам обучения
- •Протокол согласования учЕбной программы по изучаемой учебной дисциплине с другими дисциплинами специальности
- •Дополнения и изменения к учебной программе
- •Предисловие ко второму изданию
- •1 Математические модели. Численные методы. Погрешности вычислений
- •1.1 Математические модели и моделирование
- •1.2 Этапы численного решения задач на эвм
- •1.3 Виды погрешностей решения задач
- •1.4 Погрешности арифметических операций
- •1.5 Графы арифметических операций
- •1.6 Распространение погрешностей в вычислениях
- •2 Решение систем линейных алгебраических уравнений
- •2.1 Постановка задачи. Методы решения
- •2.2 Метод Гаусса
- •2.2.1 Описание метода Гаусса
- •2.2.2 Расчетные формулы метода Гаусса
- •2.2.3 Погрешность метода Гаусса. Метод Гаусса с выбором главного элемента
- •2.3 Вычислительная сложность метода Гаусса
- •2.4 Обращение матрицы
- •2.5 Метод lu-разложения
- •2.6 Метод квадратного корня решения симметричных слау
- •2.7 Метод Гаусса–Зейделя
- •2.7.1 Расчетные формулы метода Гаусса–Зейделя
- •2.7.2 Сходимость метода Гаусса–Зейделя
- •2.7.3 Графическая иллюстрация метода Гаусса–Зейделя
- •3 Аппроксимация функций
- •3.1 Понятие аппроксимации функций
- •3.2 Постановка задачи интерполирования функций
- •3.3 Интерполяционный полином Лагранжа
- •3.4 Вычисление значений полиномов
- •3.5 Вычислительная сложность задачи интерполирования
- •3.6 Конечные и разделенные разности функции
- •3.7 Интерполяционный полином Ньютона
- •3.8 Погрешность интерполирования
- •3.9 Полиномы Чебышева 1-го рода
- •3.10 Наилучший выбор узлов интерполирования
- •4 Численное интегрирование
- •4.1 Постановка задачи численного интегрирования
- •4.2 Метод прямоугольников
- •4.3 Погрешность метода прямоугольников
- •4.4 Метод трапеций
- •4.5 Погрешность метода трапеций
- •4.6 Метод Симпсона
- •4.7 Погрешность метода Симпсона
- •4.8 Интерполяционные квадратурные формулы
- •4.9 Интерполяционные квадратурные формулы наивысшей алгебраической степени точности (квадратурные формулы Гаусса)
- •4.9.1 Квадратурная формула Гаусса–Лежандра
- •4.9.2 Квадратурная формула Гаусса–Лагерра
- •4.9.3 Квадратурная формула Гаусса–Эрмита
- •5 Решение нелинейных уравнений
- •5.1 Постановка задачи численного решения нелинейных уравнений
- •5.2 Метод деления отрезка пополам
- •5.3 Метод хорд
- •5.4 Метод простой итерации
- •5.5 Метод Ньютона
- •5.6 Метод секущих
- •6 Решение обыкновенных дифференциальных уравнений
- •6.1 Постановка задачи
- •6.2 Метод рядов Тейлора
- •6.3 Метод Эйлера
- •6.4 Метод Рунге–Кутта 2-го порядка
- •6.5 Метод Рунге–Кутта 4-го порядка
- •7 Решение систем обыкновенных дифференциальных уравнений
- •7.1 Постановка задачи
- •7.2 Приведение дифференциального уравнения -го порядка к системе дифференциальных уравнений 1-го порядка
- •7.3 Метод Эйлера
- •8.2 Выполнение символьных операций в Matlab
- •8.3 Создание символьных переменных
- •8.4 Создание группы символьных переменных
- •8.5 Создание списка символьных переменных
- •8.6 Вывод символьного выражения
- •8.7 Упрощение выражений
- •8.8 Вычисление производных
- •8.9 Вычисление интегралов
- •8.10 Вычисление сумм рядов
- •8.11 Вычисление пределов
- •8.12 Разложение функции в ряд Тейлора
- •8.13 Вычисление определителя матрицы, обращение матрицы
- •9 Дополнение
- •9.1 Вычисление корней полиномов
- •9.2 Решение систем нелинейных уравнений. Метод Ньютона
- •9.3 Решение систем линейных алгебраических уравнений с трехдиагональной матрицей (метод прогонки)
- •9.4 Интерполирование функций сплайнами
- •Практический раздел Указания к выбору варианта
- •Лабораторная работа № 1. Работа в системе Matlab
- •1.1. Цель работы
- •1.2. Порядок выполнения работы
- •Лабораторная работа № 2. Решение систем линейных алгебраических уравнений
- •2.1. Цель работы
- •2.2. Теоретические положения
- •2.3. Порядок выполнения работы
- •Лабораторная работа № 3. Аппроксимация функций
- •3.1. Цель работы
- •3.2. Теоретические положения
- •3.3. Порядок выполнения работы
- •Лабораторная работа № 4. Численное интегрирование
- •4.1. Цель работы
- •4.2. Теоретические положения
- •4.3. Порядок выполнения работы
- •Лабораторная работа № 5. Решение нелинейных уравнений
- •5.1. Цель работы
- •5.2. Теоретические положения
- •5.3. Порядок выполнения работы
- •Лабораторная работа № 6. Решение обыкновенных дифференциальных уравнений
- •6.1. Цель работы
- •6.2. Теоретические положения
- •6.3. Порядок выполнения работы
- •Лабораторная работа № 7. Решение систем обыкновенных дифференциальных уравнений
- •7.1. Цель работы
- •7.2. Теоретические положения
- •7.3. Порядок выполнения работы
- •Лабораторная работа № 8. Выполнение символьных операций
- •8.1. Цель работы
- •8.2. Теоретические сведения
- •8.3. Порядок выполнения работы
- •Литература
- •Литература
3.5 Вычислительная сложность задачи интерполирования
Как следует из изложенного ранее, возможны две схемы решения задачи интерполирования функции. Первая схема состоит в решении системы линейных алгебраических уравнений (3.3) относительно коэффициентов полинома и последующем вычислении значения полинома. Вторая схема состоит в расчете значения полинома по формуле Лагранжа (3.4). Будем называть ее схемой Лагранжа. Какая из этих схем более экономична по затратам машинного времени? Для ответа на этот вопрос найдем число операций расчета для каждой схемы и сравним эти числа между собой.
Для первой схемы будем считать, что при решении СЛАУ используется метод Гаусса без выбора главного элемента, а при расчете значения полинома используется схема Горнера. Назовем эту схему схемой Гаусса–Горнера. Учитывая, что для интерполяционного полинома -й степени решается СЛАУ изуравнений, получим, что для определения коэффициентов полинома затрачивается
(3.15)
операций (см. формулу (2.11)). Для расчета значения полинома степени в одной точке по схеме Горнера затрачивается операций (см. формулу (3.14)), а значений в точках – операций. В итоге по схеме Гаусса–Горнера затрачивается
(3.16)
операций.
При расчетах по схеме Лагранжа на расчет интерполяционного полинома степени в точках затрачивается
операций (см. формулу (3.8)). Так как в формуле для при стоит коэффициент ,а в формуле для при стоит коэффициент , то ясно, что при большомполучим. Это значит, что при необходимости рассчитать интерполяционный полином в достаточно большом числе точек более выгодной является схема Гаусса–Горнера.
На рисунке 3.3 представлены графики функций (3.15) и (3.16) в зависимости от при . Видно, что схема Лагранжа более выгодна при расчете значения полинома 10-й степени не более чем в двух точках.
Рисунок 3.3 – Зависимости числа операций от числа точек расчета интерполяционного полинома по схемам Гаусса–Горнера и Лагранжа
3.6 Конечные и разделенные разности функции
Пусть – точки действительной прямой и,, – значения функциив этих точках. Назовем значенияконечными разностями нулевого порядка функции. Конечными разностями первого порядка функцииназываются приращения
, .
Конечные разности второго порядка определяются как конечные разности от конечных разностей первого порядка:
, .
Конечные разности третьего порядка определяются как конечные разности от конечных разностей второго порядка:
, .
Вообще, конечные разности -го порядка определяются с помощью следующего рекуррентного соотношения:
, .
Если функция есть полином -й степени
,
то можно показать, что его конечная разность -го порядка есть величина постоянная (), а конечная разность -го порядка равна нулю ().
Введем теперь понятие разделенных разностей функции . Назовем значенияв точках,, разделенными разностями нулевого порядка функции. Разделенными разностями первого порядка функцииназываются отношения
, .
Разделенными разностями второго порядка функции называются отношения
.
Вообще, разделенные разности -го порядка определяются через разделенные разности-го порядка с помощью рекуррентного соотношения
, ,.
Разделенные разности являются симметричными функциями своих аргументов, т.е. не меняются при их перестановке. Например,
.
Если – полином степени, то можно показать, что его разделенная разность-го порядка тождественно равна нулю,
,
для любой системы попарно различных точек .
В случае равноотстоящих на величину точекразделенные разности можно выразить через конечные разности. Действительно, легко заметить, что
, ,
, .
В общем случае справедлива формула
, ,
которая при приобретает вид
. (3.17)
Из приведенного изложения очевидно, что конечные и разделенные разности являются прообразами производных. Действительно, производная -го порядка получается при равномерном шагеиз конечной разности-го порядка путем предельного перехода
.