- •Раздел 6.
- •Раздел 6. Модели и алгоритмы решения задач численными методами с использованием математических пакетов Рекомендации по использованию учебного пособия
- •Тема 6.1. Элементы теории погрешностей
- •6.1.1. Точные и приближенные числа
- •6.1.2. Абсолютная и относительная погрешность
- •Тема 6.2. Методы решения нелинейных уравнений
- •6.2.1. Постановка задачи
- •Отделение корней (локализация корней);
- •Итерационное уточнение корней.
- •6.2.2. Отделение корней
- •6.2.2.1. Графическое отделение корней
- •6.2.2.2. Аналитическое отделение корней
- •6.2.3. Уточнение корней
- •6.2.3.1. Метод половинного деления
- •6.2.3.2. Метод итерации
- •6.2.3.3. Метод Ньютона (метод касательных)
- •6.2.3.4. Метод хорд
- •6.2.3.5. Сравнение методов решения нелинейных уравнений
- •6.2.4. Технология решения нелинейных уравнений средствами MathCad
- •Тема 6.3. Интерполяция функций
- •6.3.1. Постановка задачи
- •6.3.2. Интерполяционная формула Лагранжа
- •6.3.3. Интерполяционные формулы Ньютона
- •6.3.3.1. Конечные разности
- •6.3.3.2. Первая интерполяционная формула Ньютона
- •6.3.3.3. Вторая интерполяционная формула Ньютона
- •6.3.4. Сплайн – интерполяция
- •6.3.5. Сравнение интерполяционных многочленов по применению
- •6.3.6. Технология интерполяции функций в среде математических пакетов
- •Тема 6.4. Численное интегрирование
- •6.4.1. Постановка задачи
- •6.4.2. Метод прямоугольников
- •6.4.3. Формула трапеций
- •6.4.4. Формула Симпсона
- •6.4.5. Оценка погрешности численного интегрирования
- •6.4.6. Технология вычисления интегралов в среде математических пакетов
- •Тема 6.5. Методы решения обыкновенных дифференциальных уравнений
- •6.5.1. Постановка задачи
- •6.5.2. Метод Эйлера
- •6.5.3. Методы Рунге-Кутты
- •6.5.4. Решение оду n-го порядка
- •6.5.5. Сравнение методов решения оду
- •6.5.6. Технология решения обыкновенных дифференциальных уравнений средствами математических пакетов
- •6.6.2. Метод дихотомии
- •6.6.3. Метод золотого сечения
- •6.6.4. Сравнение методов
- •6.6.5. Технология решения задач одномерной оптимизации средствами математических пакетов
- •Тема 6.7. Аппроксимация функций
- •6.7.1. Постановка задачи аппроксимации
- •6.7.2. Метод наименьших квадратов
- •6.7.3. Технология решения задач аппроксимации функций средствами математических пакетов
- •Тема 6.8. Многомерная оптимизация
- •6.8.1. Постановка задачи и основные определения
- •6.8.2. Методы спуска
- •6.8.3. Метод градиентного спуска с дроблением шага
- •6.8.4. Метод наискорейшего спуска
- •6.8.5. Проблема оврагов. Метод покоординатного спуска
- •6.8.6. Технология решения задач многомерной оптимизации средствами математических пакетов
- •Список литературы
- •Тема 6.4. Численное интегрирование................................................71
- •Тема 6.5. Методы решения обыкновенных дифференциальных Уравнений............................................................................. 92
- •Тема 6.6. Одномерная оптимизация................................................ 115
- •Тема 6.7. Аппроксимация функций....................................................132
- •Тема 6.8. Методы многомерной оптимизации............................... 149
- •Список литературы.................................................................... 204
6.3.3. Интерполяционные формулы Ньютона
Рассмотрим случаи, когда интерполируемая функция y=f(x) задается в равноотстоящих узлах так, что = x0 + ih, где h – шаг интерполяции, а i = 0, 1, …, n. В этом случае для нахождения интерполяционного многочлена могут применяться формулы Ньютона, которые используют конечные разности.
6.3.3.1. Конечные разности
Конечной разностью первого порядка называется разность Dyi = yi+1-yi, где yi+1= f(xi+h) и yi = f(xi). Для функции, заданной таблично в (n+1) узлах, i = 0, 1, 2, …, n, конечные разности первого порядка могут быть вычислены в точках 0, 1, 2,…, n-1:
Используя конечные разности первого порядка, можно получить конечные разности второго порядка:
Отметим, что любые конечные разности можно вычислить через значения функции в узлах интерполяции, например:
(6.3.3-1)
Для конечной разности k-го порядка в узле с номером i справедлива формула, позволяющая вычислять конечные разности с помощью таблицы конечных разностей:
.
Следует отметить, что по величине конечных разностей можно сделать вывод о степени интерполяционного полинома, описывающего таблично заданную функцию. Если для таблицы с равноотстоящими узлами конечные разности k-го порядка постоянны или соизмеримы с заданной погрешностью, то функцию можно представить k-й многочленом.
Рассмотрим, например, таблицу конечных разностей для многочлена y=x2- 3x+2.
Таблица 6.3.3-1
-
x
y
Dy
D2y
D3y
1.0
0
-0.16
0.08
0
1.2
-0.16
-0.08
0.08
0
1.4
-0.24
0
0.08
1.6
-0.24
0.08
1.8
-0.16
В данном примере конечные разности третьего порядка равны нулю, а все конечные разности второго порядка равны 0.08. Это говорит о том, что функцию, заданную таблично, можно представить многочленом второй степени.
Введя понятие конечных разностей, рассмотрим еще две формы записей интерполяционных полиномов.
6.3.3.2. Первая интерполяционная формула Ньютона
Пусть функция y = f(x) задана в n+1 равноотстоящих узлах , i = 0, 1, 2, …, n, с шагом h. Требуется найти интерполяционный многочлен Pn(x) степени не выше n, удовлетворяющий условию:
Pn(xi) = yi, i =0, 1, 2, …, n . (6.3.3-2)
Будем искать интерполяционный многочлен вида:
Pn(x) =a0 + a1(x-x0) + a2(x-x0)(x-x1) + …+ an(x-x0)(x-x1)…(x-xn-1), (6.3.3-3)
где аi, i =0,1,2,…,n–неизвестные коэффициенты, не зависящие от узлов интерполяции.
Для нахождения коэффициентов формулы Ньютона аi будем подставлять в (6.3.3-3) значения х, совпадающие с узлами интерполяции, требуя выполнения условия (6.3.3-2).
Пусть х = x0, тогда, согласно (6.3.3-2), Pn(x0) = y0 = a0. Следовательно, a0 = y0.
Пусть х = x1, тогда
Pn(x1) = y1 = a0 + a1(x1-x0) = y0 + a1(x1-x0). (6.3.3-4)
Из равенства (6.3.3-4) следует, что
Теперь пусть х = х2 , тогда:
Выражая неизвестный коэффициент, получим:
Продолжая подстановку, можно получить выражение для любого коэффициента с номером i:
Подставив найденные значения коэффициентов в (6.3.3-4), получим первую интерполяционную формулу Ньютона:
(6.3.3-5)
Воспользуемся этой формулой, как одной из возможных форм записи интерполяционного многочлена второй степени.
(6.3.3-6)
Тогда для вычисления значения функции, заданной табл. 6.3.3-1, при х = 1.45:
Отметим, что при использовании первой интерполяционной формулы Ньютона целесообразно выбирать х0 близко к точке интерполяции (интерполяция вперед). Это обеспечивает более высокую точность при фиксированном числе узлов. Запись интерполяционного многочлена в виде первой формулы Ньютона позволяет учитывать дополнительные узлы в правой части таблицы, уточняя ранее полученный результат, без пересчета остальных слагаемых.
Введя обозначение: и проведя несложные преобразования вида: приведем (6.3.3-5) к виду:
(6.3. 3-7)
Это второй вид записи формулы Ньютона для интерполирования вперед. Она применяется для интерполяции f(x) в окрестностях начального значения х0, где q – достаточно мало по абсолютной величине.
Если n=1, то из (6.3.3-6) получаем формулу линейной интерполяции
Если n=2, то получаем формулу квадратичной (или параболической) интерполяции