Наближення функцій.

Постановка задачі. Нехай відомі значення функції y = f(x) у декількох точках x_i, i = 0, 1, …, n; a < x_i < b. Задача полягає у відновленні виду функції f(x) та/або її значень у інших точках з деякою точністю.

Термінологія. Точки x_i, i = 0, 1, …, n - вузли інтерполяції, y_i - вузлові значення.

Інтерполяція - апроксимація. У такому порівнянні інтерполюванням називається задача відшукання функції f(x) такої, що точно вдовольняє вузловим значенням: f(x_i ) = y_i , i = 0, …, n.

Апроксимацією називається функція f(x), близька до y лише у тому сенсі. що сумарна помилка S = || f - y || є мінімальною.

Інтерполяція - екстраполяція. У такому протиставленні інтерполяцією називають обчислення значень функції всередині інтервалу [a; b]; екстраполяцією - поза цим інтервалом.

Інтерполяційні поліноми. Поліном P_n(x) степеня n, що точно вдовольняє вузловим значенням, існує та є єдиним. Для його відшукання треба розв’язати систему

відносно коефіцієнтів a_n, …, a₀. Для спрощення задачі існують певні форми запису цього поліному.

Нехай

f(x)	- функція;	(0)
	- поділена різниця;	(1)
	- друга поділена різниця;	(2)

f(x) = f(x₀) + (x - x₀) f(x, x₀);

f(x, x₀) = f(x₀, x₁) + (x - x₁) f(x, x₀, x₁);

Аналогічно:

f(x) = f(x₀) + (x - x₀) f(x₀, x₁) + (x - x₀) (x - x₁) f(x₀, x₁, x₂) + (x - x₀) (x - x₁) (x - x₂) f(x₀, x₁, x₂, x₃) + … + (x - x₀) (x - x₁)… (x - x_n-1) f(x₀, x₁,…, x_n) + (x - x₀) (x - x₁)… (x - x_n) f(x, x₀,…, x_n) ,(3)

причому підкреслена частина є деяким поліномом n-го порядку:

f(x₀) + (x - x₀) f(x₀, x₁) + (x - x₀) (x - x₁) f(x₀, x₁, x₂) + (x - x₀) (x - x₁) (x - x₂) f(x₀, x₁, x₂, x₃) + (x - x₀) (x - x₁)… (x - x_n-1) f(x₀, x₁,…, x_n) = P_n(x).

Якщо x = x₀, x₁, …, x_n, то f(x_i) = P_n(x_i) = y_i, тому що (x - x₀) … (x - x_n) f(x, x₀, …, x_n) = 0!

Права частина виразу (3) і є інтерполяційним поліномом Ньютона.

Якщо x₀ < x₁ < … < x_n, то це – формула інтерполяції вперед, якщо навпаки –назад.

- інтеполяційний поліном "назад".

Нехай

та

де

При s = x_i, i = 0, 1, …, n, w(x_i) = 0. Тому g(x_i) = 0, бо f(x_i) = P_n(x_i). Виберемо деяку точку x № x_i, i = 0, 1, …, n, та виберемо k так, щоби g(x) = 0. Тоді

Враховуючи, що w⁽ⁿ⁺¹⁾(s) = (n+1)!, та те, що g(s) має n+2 нулі на [a;b], то g'(s) має n+1 нуль, g''(s) має n нулів, … g⁽ⁿ⁺¹⁾(s) має принаймні один нуль. Нехай це має місце при s = x. Тоді

Розгляньмо функцію W_i (x) = (x - x₀) (x - x₁) … (x - x_i-1) (x - x_i) (x - x_i+1) … (x - x_n).

У ній відсутній член (x - x_i), тому при x = x_i вона приймає ненульове значення. Якщо її пронормувати значенням W_i (x_i), то одержуємо т.зв. фундаментальний поліном Лагранжа

причому

Тоді

Поліном Лагранжа повністю збігається з інтерполяційним поліномом Н’ютона - це дві форми запису того самого єдиного поліному.

У вузлах може бути задано значення функції f та похідні - f', f'', …, f^(Ni-1) - усього N_i штук.

Тоді всього буде N₀ + N₁ + … + N_n умов.

Шукається поліном степеня

у якому N_i - кратність вузла і.

Поліном існує та єдиний. Кількість рівнянь дорівнює кількості коефіцієнтів. Розгляньмо поліном степеня m, похідні якого H_m^(j)(x_i) = 0, j = 0, 1, …, N_i . Це означає. що x_i - корінь кратності N_i .

Тоді на [a; b] існує N₀ + N₁ + … + N_n = m+1 коренів. але степінь його m, тому при всіх x H_m(x) = 0.

Будемо шукати H_m(x) у вигляді

де

L_n(x_i) = y_i, w_n(x_i) = 0, i = 0, 1, …, n.

Похідна:

причому

У тих точках. де задано f'(x_i), знайдемо

Далі шукають другу похідну

причому

Звідки виражають H'_m-n(x_i), тому що інші величини є відомими, і т. ін..

Нехай задано значення функції та її похідних у точках x₀ = 0; x₁ = 1; x₂ = 2:

f(0) = 1; f '(0) = 1; N₀ = 2;

Таким чином, m = (2 + 1 + 3) - 1 = 5. Поліном Ерміта шукаємо у вигляді H₅(x) = L₂(x) + w₃(x) H₂(x):

,

Розглянемо послідовність сіток w_n:

При max (x_n - x_n-1)  0 для заданої f(x) (рівномірна збіжність).

Теорема Фабера. Для будь-якої послідовності сіток w_n знайдеться така, що збіжність відсутня.

Теорема Марцинкевича. Для знайдеться послідовність сіток

Поліноміальним сплайном порядку m та дефекту k називається функція S_m,k(x) на сітці

1. на кожному проміжку

2. k - дефект сплайну, 0 < k < m.

   Розгляньмо сплайн дефекту 1. S_m,1 = S_m.

   Інтерполяційним сплайном називається S_m(x):

3. S_m(x_i) = y_i, i = 0, 1, …, N.

Усього вільних коефіцієнтів: N(m+1).

Умов неперервності: (N-1)m (похідні від f ⁽⁰⁾ = f до f ^(m-1)).

Умов інтерполяції: N+1 типу 3).

Усього N(m+1)-(N-1)m-N-1=N+m-N-1=m-1.

Систему недовизначено. Можна задати додатково крайові умови у точці х = а та х = b.

Розглянути приклад: m = 0 – кусочно-постійна функція; m = 1 - кусочно-лінійна; m = 3 - кубічні сплайни.

Доведено збіжність при на рівонмірній сітці (Гулін, Самарский).

F - фундаментальні сплайни:

Сплайни F є незручними; їхній вигляд є заскладним; щоб їх визначити, слід розв'язати таку ж задачу.

Зручніше – B-сплайни:

B_m,i(t) - сплайн порядку m дефекту 1.

B_m,i^(j)(t_i) = B_m,i^(j)(t_i+m+1) = 0 та за межами [t_i, t_i+m+1]; j=0, 1, …, m-1.

. (5)

При цьому виявляється, що, B(x) > 0 при хЦе сплайн з фінітним носієм мінімальної довжини.

- 2m умов на кінцях;

- m*m умов неперервності f, f ', f '', …, f^(m-1) в m серединних вузлах; усього m² + 2m;

- коефіцієнтів (m + 1)² = m² + 2m + 1.

де B_m = B_m,0.

На сітці a = x₀ < x₁ < … < x_n-1 < x_n = b для інтерполяції слід використовувати сплайни { B_m,i }, i = -m, …, N-1, усього N + m = (N + 1) + (m - 1), тобто дефект визначеності той самий. Вони утворюють базис у просторі S-сплайнів на цій сітці.

Наприклад, B_3,i на сітці x₀, …, x_n використовуються від B_3,-3 до B_3,N-1 - всього N + 3 на (N + 1) точках.

Нерівномірний B_3,0 - сплайн.

1. x на [0;x₁]; B(x) = a₀x³; B(x₁) = a₀x₁³.

2. x на [x₁ ; x₂]; B(x) = a₁x³ + b₁x² + c₁x + d₁;

   B(x₁) = a₁x₁³ + b₁x₁² + c₁x₁ + d₁ = a₀x₁³.

   B'(x₁) = 3a₁x₁² + 2b₁x₁ + c₁ = 3a₀x₁²;

   B''(x₁) = 6a₁x₁ + 2b₁ = 6a₀x₁;

3. x на [x₂ ; x₃]; B(x) = a₂x³ + b₂x² + c₂x + d₂;

   B(x₂) = a₁x₂³ + b₁x₂² + c₁x₂ + d₁ = a₂x₂³ + b₂x₂² + c₂x₂ + d₂.

   B'(x₂) = 3a₁x₂² + 2b₁x₂ + c₁ = 3a₂x₂² + 2b₂x₂ + c₂;

   B''(x₂) = 6a₁x₂ + 2b₁ = 6a₂x₂ + 2b₂;

4. x на [x₃ ; x₄]; B(x) =a₃(x₄ - x)³;