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

Интерполяционный полином Лагранжа

Согласно условий (1), (2), предъявляемых к функции φ(х), запишем многочлен n-ой степени.

_n

φ(х)≡F_n(x) = ∑ f(x_i) p_i(x) (6)

ⁱ⁼⁰

В узле x_i многочлен (6) на основании (1) должен принимать значение f_i. Значит, сомножитель p_i(x) в точке x_i должен быть равен 1,т.е.

p_i (x_i) = 1.

В то же время другие слагаемые многочлена (6) должны быть равны нулю, т.е.

p_k (x_i) = 0, i ≠ k, i, k = 0, 1, …,n.

Таким образом, мы сформулировали требования к сомножителю p_i(x) , а именно:

p_i (x_i) = 1 , i = 0, 1, …,n (7)

p_k (x_i) = 0, i ≠ k; i, k = 0, 1, …,n. (8)

Сомножитель p_i(x) называют вспомогательным многочленом степени n.

Учитывая свойство (8) и требование, чтобы многочлен p_i(x) имел степень n, запишем:

p_i(x) = c_i (x-x₀) (x-x₁)… (x-x_i-1) (x-x_i+1) (x-x_i+2)… (x-x_n) (9)

где c_i некоторый коэффициент.

При x = x₀, x₁,… x_i-1, x_i+1, … x_n

p_i(x) = 0.

Для определения c_i обратимся к требованию (7). Из него следует:

p_i(x_i) = c_i (x_i-x₀) (x_i-x₁)… (x_i-x_i-1) (x_i-x_i+1) (x_i-x_i+2)… (x_i-x_n) = 1

Тогда

c_i= (10)

Сделав подстановку (10) в (9), получим окончательное выражение для p_i(x):

p_i(x) = (11)

Построенный многочлен (11), например, в точке x₀ принимает значение p₀(x₀) = 1, а в остальных узлах – значения, равные нулю.

Многочлен p₁(x) в точке x₁ будет равен 1, а в остальных узлах обращается в 0, и т.д.

Таким образом, вспомогательный многочлен p_i(x) полностью удовлетворяет требованиям (7), (8), а многочлен n-ой степени

_n

F_n(x) = ∑ f(x_i) p_i(x)

ⁱ⁼⁰

является интерполяционным многочленом Лагранжа.

Замечание: многочлен Лагранжа целесообразнее использовать в задачах восстановления функции f(x) , когда точка интерполяции x расположена ближе к центру сетки.

Тестирование алгоритма

Рассмотрим функцию f(x), заданную таблицей:

Построим многочлен Лагранжа для этой функции.

F₃(x) = 2 + 1 + 2 +3

Если вместо x подставить 1, то F_n(1)= f₁ = 2,

при x = 4 F_n(4)= f₃ = 2 и т.д.

Следовательно, построенный многочлен удовлетворяет главному условию (1).

Таким образом, тестирование алгоритма будет состоять в следующем:

1. задать поочередно в качестве точек интерполяции табличные значения x_i и получить соответствующие значения функции f_i (при правильно работающей программе должно выполняться условие (1)).

2. задать в качестве точек интерполяции несколько значений, не являющихся узлами сетки, и проверить выполнение условия (2).

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

Пусть:

f(x) – F_n(x) = R_n(x),

тогда

f(x) = F_n(x) + R_n(x), (12)

Разность R_n(x) называется остаточным членом формулы Лагранжа. Значение R_n(x) равно погрешности, которая получается при замене значения функции f(x) значением интерполяционного многочлена F_n(x).

Если предположить, что функция f(x) имеет на отрезке [a, b]

(a = min {x_k}; b = max {x_k}) производные до порядка n+1,

^{k k}

то для остаточного члена можно получить формулу

R_n(x) = f⁽ⁿ⁺¹⁾(ξ) (13)

где точка ξ Î [a, b] и зависит от точки х.

Формулу (13) можно записать иначе:

R_n(x) =w_n+1 (x). (14)

Если

max |f⁽ⁿ⁺¹⁾ (x)| £ M_n+1

^{x Î [a; b]}

то получим оценку остаточного члена:

|R_n(x)| £ |w_n+1 (x)|. (15)

Пример. Для функции у= 2^х построим интерполяционный многочлен Лагранжа, выбрав узлами интерполирования точки

x₀ = - 1, x₁ = 0, x₂ = 1, x₃ = 2.

Вычислим соответствующие значения функции:

у₀= ½ , у₁=1, у₂=2, у₃=4;

по формуле Лагранжа найдем:

F₃(x) =x³ + x² +x+1.

Оценим погрешность, которая получается при замене функции у= 2^х многочленом F₃(x). Производная четвертого порядка

F⁽⁴⁾(x) = 2^x(ln 2)⁴.

На отрезке [-1; 2] функция 2^x возрастает, поэтому 0< 2^x <= 4.

M₄ = 4 (ln 2)⁴, ln 2 = 0,693…<, поэтому M₄ < 4× = 1.

w₄ (х) = x (x + 1)(x - 1)(x –2).

По формуле (15) получим:

Многочлен Ньютона

Рассмотренный многочлен Лагранжа, как правило, используется в задачах восстановления функции f(x), когда точка интерполяции х находится ближе к центру сетки.

Если же точка интерполяции х расположена ближе к краям сетки, целесообразнее использовать многочлен Ньютона. Здесь возможны два случая:

1. точка интерполяции х находится вблизи первого узла сетки х₀ (полином Ньютона I);

2. точка интерполяции х находится вблизи последнего узла сетки х_n (полином Ньютона II).

Замечание. Построение многочлена Лагранжа основывается на вспомогательном многочлене p_i(x).

В основе же построения многочлена Ньютона находится понятие конечной разности.

Определим понятие конечной разности.

Пусть функция задана таблицей с постоянным шагом h:

где х_i = х₀ + ih (i = 0, 1, …,n).

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

Dу₀ =у₁ – у₀ = f(x₁) – f(х₀);

Dу₁ =у₂ – у₁ = f(x₂) – f(х₁);

… … …

Dу_n-1 =у_n – у_n-1 = f(x_n) – f(х_n-1).

Приращения разностей первого порядка называются разностями второго порядка:

D²у₀ =Dу₁ – Dу₀ ,

D²у₁ =Dу₂ – Dу_1.

Вообще разности любого порядка k определяются равенствами

D^kу_m =D^{k - 1}у_{m +1} – D^{k - 1}у_m.

Будем считать, что D⁰у_m = у_m.

Последовательно получаемые разности удобно записывать в форме таблицы:

Пример. Построим таблицу конечных разностей для функции

y = cosx на отрезке [0; 0,7] с шагом h = 0,1.

Таблица будет иметь вид: