Формула Ньютона с разделенными разностями

 

Первая и вторая формулы Ньютона предполагают, что узлы интерполирования являются равноотстоящими. Однако, в общем случае функция f (x) может быть задана таблицей, в которой узлы находятся на произвольном расстоянии друг от друга , где значения h_i (i = ) являются различными.

При таких условиях первая и вторая интерполяционные формулы Ньютона неприменимы. В данном случае, для решения задачи интерполяции применяются не конечные, а разделенные разности.

Разделенная разность первого порядка определяется:

 

 

Для вычисления разделенных разностей высших порядков используется формула:

 

 

Разделенные разности удобно представлять диагональной таблицей, вид которой для n = 4 соответствует табл. 2.

 

Таблица 2

 

Интерполяционный многочлен Ньютона, использующий разделенные разности, имеет вид:

 

 

где , П_k (x) = 1.

Представленная формула позволяет повышать точность вычислений постепенно, добавляя разделенные разности более высоких порядков. Следует отметить, что при этом все полученные результаты сохраняются, т.е. не вычисляются заново, а только наращиваются. Это следует из соотношения

 

 

Оценка погрешности интерполирования выполняется по формуле

 

 

Интерполяция сплайнами

 

Пусть задана таблица значений функции f (x_i) = y_i (), в которой они расположены по возрастанию значений аргумента: x ₀ < x ₁ < … < x_n. Чтобы построить кубический сплайн, требуется определить коэффициенты a_{i 0}, a_{i 1}, a_{i 2}, a_{i 3}, которые задают интерполяционный кубический многочлен

 

 

на каждом интервале интерполирования [ x_{i -1}, x_i ], .

Таким образом, необходимо определить 4 n коэффициентов a_ij (, ), для чего требуется 4 n уравнений. Необходимые уравнения определяются следующими условиями.

1. Условия непрерывности функции:

 

 

2. Условия непрерывности 1-х и 2-х производных функции:

 

 

3. Граничные условия:

 

 

Часто используются граничные условия вида Получаемый при этом сплайн называется естественным кубическим сплайном.

Задача определения кубического сплайна существенно упрощается при использовании многочлена Эрмита. Кубический многочлен Эрмита на интервале [ x_{i- 1}, x_i ] определяется с помощью значений функции y_{i -1}, y_i и ее производных y ¢ _{i -1}, y ¢ _i. Так как значения производных в общем случае могут быть неизвестны, обозначим их как y ¢ _{i -1} = S_{i -1}; y ¢ _i = S_i. При построении сплайна переменные S_i называются наклонами сплайна в соответствующих точках x_i.

Запишем многочлен Эрмита для интервала [ x_{i- 1}, x_i ], где h_i = x_i - x_{i- 1}:

 

 

При таком выборе кубического многочлена автоматически выполняются условия непрерывности функции и ее первых производных:

 

 

Чтобы определить сплайн, нужно задать условия непрерывности второй производной:

 

 

Для записи этих условий в развернутом виде определим кубический многочлен Эрмита на интервале [ x_i, x_{i +1}], где h_{i +1} = x_{i +1} - x_i:

 

Определим вторые производные многочленов Q_i (x) и Q_{i +1}(x) в точке x = x_i:

 

(4)

(5)

 

Отсюда условие непрерывности вторых производных имеет вид:

 

(6)

 

Это условие порождает систему линейных уравнений относительно наклонов сплайна S_i, которая содержит n - 1 уравнение и n + 1 переменную. Чтобы определить два недостающих уравнения используются граничные условия. Например, для естественного кубического сплайна:

 

 

Указанные граничные условия могут быть получены из уравнения (5) для i = 0 и из уравнения (4) для i = n соответственно. В развернутом виде:

 

(7)

 

Решение системы линейных уравнений, образованной условиями (6) и (7), позволяет вычислить наклоны сплайна S_i (i = ) и определить кубический сплайн путем записи многочлена Эрмита для каждого интервала [ x_{i- 1}, x_i ], i = .

 

Заключение

 

В вычислительной математике существенную роль играет интерполяция функций, т.е. построение по заданной функции другой (как правило, более простой), значения которой совпадают со значениями заданной функции в некотором числе точек. Причем интерполяция имеет как практическое, так и теоретическое значение. На практике часто возникает задача о восстановлении непрерывной функции по ее табличным значениям, например полученным в ходе некоторого эксперимента. Для вычисления многих функций оказывается эффективно приблизить их полиномами или дробно-рациональными функциями. Теория интерполирования используется при построении и исследовании квадратурных формул для численного интегрирования, для получения методов решения дифференциальных и интегральных уравнений.

 

Список литературы

1. В.В. Иванов. Методы вычислений на ЭВМ. Справочное пособие. Изд-во "Наукова думка". Киев. 1986.

2. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Изд-во "Лаборатория базовых знаний". 2003.

3. И.С. Березин, Н.П. Жидков. Методы вычислений. Изд. ФизМатЛит. Москва. 1962.

4. К. Де Бор. Практическое руководство по сплайнам. Изд-во "Радио и связь". Москва. 1985.

5. Дж. Форсайт, М.Мальком, К. Моулер. Машинные методы математических вычислений. Изд-во "Мир". Москва. 1980.