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

Пусть имеется табулированная функция 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, a 0, a 1, …, 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 + 2 x ².

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

 

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