Интерполяционная формула Ньютона с разделенными разностями

Пусть имеется табулированная функция y_i = f(x_i). Введем понятие разделенной разности.

Разделенные разности нулевого порядка совпадают со значениями самой функции.

Разделенные разности первого порядка записываются следующим об-разом:

Разность P_n(x, x₀) – P_n(x₀, x₁) обращается в нуль при x = x₁, поэтому разделенная разность второго порядка

является многочленом степени n – 2. Аналогично, P_n(x, x₀, x₁, x₂) – многочлен степени n – 3 и т.д.

Разделенная разность P_n(x, x₀, x₁, …, x_n-1) порядка n – многочлен нулевой степени.

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

Значение P_n(x, x₀, x₁, …, x_n–1) от x не зависит, поэтому

P_n(x, x₀, x₁,…, x_n-1) = P_n(x₀, x₁, …, x_n).

Из определения разделенных разностей следует

P_n(x) = P_n(x₀) + (x – x₀) P_n(x, x₀),

P_n(x, x₀) = P_n(x₁, x₀) + (x – x₁) P_n(x, x₀, x₁)

и т.д. Отсюда формула для P_n(x) имеет вид

P_n(x) = P_n(x₀) + (x – x₀) P_n(x₀, x₁) + (x – x₀) (x – x₁) P_n(x₀, x₁, x₂) +

+ (x – x₀) (x – x₁) … (x – x_n-1) P_n(x₀, …, x_n). (5.2)

Разделенные разности в соответствии с рекуррентной формулой (5.1) выражаются через значения многочлена в узлах x₀, x₁, …, x_n. Если x₀, x₁, …, x_n узлы интерполяции, y₀, y₁, …, y_n – значения интерполируемой функции в этих узлах, то они однозначно определяют интерполяционный многочлен степени n, значения которого в узлах совпадают с yi. Тогда разделенные разности многочлена Pn(x) совпадают с разделенными разностями функции f(x).

Поэтому интерполяционный многочлен можно записать в форме

Эта форма называется интерполяционным многочленом Ньютона с разделенными разностями.

Многочлен Лагранжа

Пусть задана функция y = f(x). Часто нахождение значений этой функции может оказаться трудоемкой задачей. Например, x – параметр в сложной задаче, после решения которой определяется значение f(x) или f(x) измеряется в дорогостоящем эксперименте. В этих случаях можно получить небольшую таблицу значений функции, но прямое нахождение ее значений при большом количестве значений аргумента нереально. В такой ситуации f(x) заменяется приближенной формулой g(x), которая в определенном смысле близка к функции f(x). Близость обеспечивается введением в функцию g(x) свободных параметров и их соответствующим выбором.

Итак, пусть известны значения функции f(x) в точках x₀, x₁, …, x_n,

y_i= f(x_i), i = 0, …, n, и для некоторой функции g(x, a₀, a₁, …, a_n) выполняются равенства

g(xi, a0, a1, …, an) = yi , i = 0, 1, …, n. (5.4)

Если выражение (5.4) рассматривать как систему уравнений для определения a₀, a₁, …, a_n, то этот способ называется интерполяцией (лагранжвой).

Если g зависит от a_j нелинейно, то говорят о нелинейной интерполяции. В противном случае интерполяция называется линейной. Для линейной интерполяции можно записать

(5.5)

где ϕ_j(x) – система линейно независимых функций.

Подставим выражение (5.5) в равенство (5.4). Относительно aj получаем линейную систему уравнений:

(5.6)

Для однозначной разрешимости системы должно быть m = n.

Для того чтобы задача интерполирования имела единственное решение, система функций ϕ_j(x) должна удовлетворять условию

(5.7)

Система функций, удовлетворяющая условию (5.7), называется

чебышевской. Если ϕ_j(x) задаются в виде

то формула (5.5) называется интерполяционным многочленом Лагранжа.

Многочлены Чебышева

Пусть x∈[–1, 1]. Рассмотрим функцию вида

T_n(x) = cos[n∙arccos(x)]. (5.8)

Очевидно, что T₀(x) = 1, T₁(x) = x. При n = 2 используем тригонометрическое

тождество

T₂(x) = cos(2arccos(x)) = cos²(arccos(x)) − sin²(arcсos(x)) =

= 2cos²(arccos(x)) − 1 = −1 + 2x².

Пусть T_n(x) – многочлен степени n. Получим рекуррентное соотношение, связывающее T_n–1(x), T_n(x) и _Tn+1(x). Как известно,

Сложив почленно эти равенства, будем иметь