Скінчені різниці. Інтерполяційні формули Ньютона для рівновіддалених вузлів

Якщо вузли інтерполяції рівновіддалені: х₀, х₁ = х₀ + h, х₂ = х₀ + 2h, …, х_n = х₀ + nh, то інтерполяційна формула Ньютона спрощується, а алгоритми для деяких задач стають ефективнішими. Замість поділених різниць в таких випадках використовують так звані скінчені різниці.

Означення 7. Нехай функція у = f (x) задана в точках х_k = х₀ + kh, де h – дійсна стала, k = 0,1,…,n, y_k = f (х_k). Тоді величину Δу_i = Δ f _i = f (х_i+1) – f (х_i) називають скінченими різницями першого порядку. Скінчені різниці другого порядку Δ²у_i – це різниці перших різниць, тобто Δ²у_i = Δ² f _i = Δ f _{i +1} – Δ f _i = f (х_i+2) – 2 f (х_i+1) + f (х_i). За індукцією різниці Δⁿу_i порядку n – це різниці різниць порядку n – 1: Δⁿу_i = Δⁿ f _i = Δ^{n-1 f} _{i +1} – Δ^{n-1 f} _i.

Зазначимо, що нижні індекси при Δⁿу_i завжди ті ж самі, що у від’ємника Δ^{n-1 f} _i. Можна довести по індукції, що Δⁿу_k = у_k+n – nу_k+n-1 + у_k+n-2 – … + (– 1)ⁿу_k = . Ця формула нагадує розклад за формулою бінома Ньютона: коефіцієнт при у_k+n-m у цій формулі дорівнює коефіцієнту при y^m у розкладі (у – 1)ⁿ за формулою бінома. Скінчені різниці просто зв’язані з поділеними різницями.

Лема 2. Якщо х_k = х₀ + kh, то виконується рівність: f (x_k; x_k+1;…; x_k+n) = .

Доведення проведемо по індукції. При n = 1 маємо f (x_k; x_k+1) = = . Припустимо, що рівність виконується при всіх степенях поділених різниць n = 1, …, l. Звідси маємо

f (x_k; x_k+1;…; x_{k+ l +1}) = = = .

Отже, рівність виконується і при n = l + 1. Лему доведено.

Наслідок. Якщо f = Р_m – многочлен степеня m, то Δⁿу_k = , де с – деяка стала (незалежна від k).

Справді, за теоремою 2 пункт 4, якщо функція f (x) n + 1 раз неперервно диференційовна, то f (x₀; x₁;…; x_n) = , де min{x₀; x₁;…; x_n} ≤ ξ ≤ max{x₀; x₁;…; x_n}. Звідси, якщо у якості f (x) взяти деякий многочлен P_m(x) степеня m ≤ n, то P_m(x_k;…;x_k+n) = , де b – це коефіцієнт многочлена P_m(x) при х^m. Згідно з лемою 2, якщо х_k = х₀ + kh, то P_m(x_k; x_k+1;…; x_k+n) = . Отже, Δⁿу_k = 0, якщо m < n і Δⁿу_k = bhⁿn! незалежно від k, якщо n = m.

Зворотно, якщо для деякого n Δⁿу_k ≈ 0 при всіх k, то f (x_k; x_k+1;…; x_k+n) ≈ 0 і отже ≈ 0. Якщо відстань між всіма вузлами x_k достатньо мала, то ≈ 0 при всіх х на відрізку min{x₀; x₁;…; x_n} ≤ х ≤ max{x₀; x₁;…; x_n}. Отже, з деякою прийнятною похибкою можна вважати, що на цьому відрізку f (x) ≈ P_m(x), де P_m(x) – деякий многочлен степеня m < n і отже за означенням це інтерполяційний многочлен.

Теорема 3. Нехай вузли інтерполяції х_k = х₀ + kh, де h – дійсна стала, k = 0,1,…,n, y_k = f (х_k). Тоді інтерполяційна формула Ньютона набуває вигляду:

f (x) ≈ L_n(x) = y₀ + tΔу₀ + Δ²у₀ + … + Δⁿу₀,

де t = (х – x₀)/h. Якщо функція f (x) n + 1 раз неперервно диференційовна, то залишковий член (абсолютна похибка інтерполяції) R_n(f,x) = f (x) – L_n(x) дорівнює

R_n(f,x) = hⁿ⁺¹t(t –1)(t – 2)…(t – n) ≈ t(t – 1)(t – 2)…(t – n) (х₀ ≤ ξ ≤ х_n).

Доведення. Згідно з теоремою 2 пункт 3

L_n(x) = f (x₀) + f (x₀; x₁)(х – х₀) + … + f (x₀; x₁;…; x_n)(х – x₀)(х – x₁) … (х – х_n-1).

Згідно з лемою 2 для вузлів х_k = х₀ + kh виконується рівність: f (x₀; x₁;…; x_k) = . Нарешті очевидно, що х – x_k = x – х₀ – kh = h( – k) = h(t – k), звідки (х – x₀)(х – x₁) … (х – х_k-1) = h^kt(t – 1)(t – 2)…(t – k + 1). Отже, f (x₀; x₁;…; x_k)(х – x₀)(х – x₁) … (х – х_k-1) = Δ^kу₀, що і доводить інтерполяційну формулу. Якщо функція f (x) n + 1 раз неперервно диференційовна, то згідно з теоремою 1 R_n(f,x) = (х – x₀)(х – x₁) … (х – х_n) = hⁿ⁺¹t(t –1)(t – 2)…(t – n), де х₀ ≤ ξ ≤ х_n. Згідно з теоремою 2 пункт 4 = f (х; x₀; x₁;…; x_n). Звідси, якщо величини │x_i – х│ достатньо малі, то f (х; x₀; x₁; …; x_n) = ≈ f (x₀; x₁;…; x_n+1) = . Отже, R_n(f,x) = (х – x₀) ∙ (х – x₁) … (х – х_n) ≈ t(t – 1)(t – 2)…(t – n). Теорему доведено.

Означення 8. Інтерполяційну формулу

f (x) ≈ L_n(x) = y₀ + tΔу₀ + Δ²у₀ + … + Δⁿу₀, (3)

де t = (х – x₀)/h, називають першою інтерполяційною формулою Ньютона.

Зокрема при n = 1 маємо формулу лінійної інтерполяції f (x) ≈ f (x₀) + (x – x₀), яка була використана у розділі 2. Тут R₁(f,x) ≈ t(t – 1). При n = 2 маємо формулу квадратичної інтерполяції f (x) ≈ у₀ + (х – x₀) + (х – x₀)(х – x₁), R₂(f,x) ≈ t(t – 1)(t – 2).

Згідно з формулою для абсолютної похибки інтерполяції │R_n(f,x)│ набуває найменше можливе значення за умови, що найменші можливі значення мають відстані │x_i – х│ від

х до вузлів інтерполяції x_i. Для цього необхідно, щоби вони були занумеровані в порядку зростання │x_i – х│ (як і в схемі Ейткіна). Насправді в умовах теореми 3 це буде виконано, якщо х міститься на початку таблиці, тобто х є [x₀; x₁]. Якщо х є [x₁; x₂], то користуватись безпосередньо формулою (3) недоцільно, бо t буде більшим за 1. У цьому разі за перший вузол треба взяти x₁ і в інтерполяційному многочлені використовувати скінчені різниці Δу₁, Δ²у₁, …, Δⁿу₁. Тому першу інтерполяційну формулу Ньютона називають також формулою Ньютона для інтерполювання вперед. Якщо значення х лежить ближче до кінця відрізкаінтерполювання, то вузли треба занумерувати у зворотному порядку: x_n, x_n-1, …, x₁, x₀. Звідси так само, як у теоремі 3, отримаємо L_n(x) = f (x_n) + f (x_n; x_n-1) ∙ (х – х_n) + … + f (x_n; x_n-1;…; x₀)(х – х_n-1) … (х – x₁)(х – x₀) = y_n + tΔу_n-1 + Δ²у_n-2 + … + Δⁿу₀.

Означення 9. Інтерполяційну формулу

f (x) ≈ L_n(x) = y_n + tΔу_n-1 + Δ²у_n-2 + … + Δⁿу₀, (4)

де t = (х – х_n)/h, називають другою інтерполяційною формулою Ньютона або формулою Ньютона для інтерполювання назад.

При такій нумерації відповідна формула залишкового члена має вигляд

R_n(f, x) = hⁿ⁺¹t(t +1)(t + 2)…(t + n) ≈ t(t +1)(t + 2)…(t + n) (х₀ ≤ ξ ≤ х_n).