Программирование формулы Ньютона

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

Тогда рекуррентная формула (11.8) будет иметь вид:

(11.9)

В формуле Ньютона (11.7) используются разделенные разности k-го порядка, подсчитанные только для участков [x₀, x_0+k], т.е. разделенные разности k-го порядка для i=0. Обозначим эти разделенные разности k-го порядка как у₀. А разделенные разности, подсчитанные для I > 0, используются для расчетов разделенных разностей более высоких порядков.

Используя (11.9), свернем формулу (11.7). В результате получим

(11.10)

где

у₀ - значение табличной функции (11.1) для x=x₀.

- разделенная разность k-го порядка для участка [x₀, x_0+k].

Для вычисления Р удобно использовать рекуррентную формулу P = P(x - x_k-1) внутри цикла по k.

Схема алгоритма интерполяции по Ньютону представлена на рис.11.4.

Рис. 11.4. Схема алгоритма интерполяции по Ньютону

Пример интерполяции по Ньютону

Дана табличная функция:

i	xi	yi
0	2	0,693147
1	3	1,098613
2	4	1, 986295
3	5	1,609438

Вычислить разделенные разности 1-го, 2-го, 3-го порядков (n=3) и занести их в диагональную таблицу.

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

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

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

Таблица 11.1. Диагональная таблица разделенных разностей
i	xi	Разделенная разность
		0-го пор.	1-го пор.	2-го пор.	3-го пор.
0	2	0,693147
			0,405466
1	3	1,098613		-0,058892
			0,287682		0,00887416
2	4	1,386295		-0,0322695
			0,223143
3	5	1,60943

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

Далее полученный интерполяционный многочлен Ньютона можно привести к нормальному виду

и использовать его для решения задач интерполирования или прогноза.

Сплайн-интерполяция

Сплайны стали широко использоваться в вычислительной математике сравнительно недавно. В машиностроительном черчении они применяются уже давно, так как сплайны - это лекала или гибкие линейки, деформация которых позволяет провести кривую через заданные точки (x_i, у_i).

Используя теорию изгиба бруса при малых деформациях, можно показать, что сплайн - это группа кубических многочленов, в местах сопряжения которых первая и вторая производные непрерывны. Такие функции называются кубическими сплайнами. Для их построения необходимо задать коэффициенты, которые единственным образом определяют многочлен в промежутке между данными точками.

Например, для некоторых функций (рис.11.5) необходимо задать все кубические функции q₁(x), q₂(x),:q_n(x).

В наиболее общем случае эти многочлены имеют вид:

где k_ij - коэффициенты, определяемые описанными ранее условиями, количество которых равно 4n. Для определения коэффициентов k_ij необходимо построить и решить систему порядка 4n.

Рис. 11.5.

Первые 2п условий требуют, чтобы сплайны соприкасались в заданных точках:

Следующие (2п-2) условий требуют, чтобы в местах соприкосновения сплайнов были равны первые и вторые производные:

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

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

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