Завдання. 1) Побудувати
інтерполяційний многочлен
Ньютона. Накреслити графік і зазначити на ньому вузли
інтерполяції. Обчислити значення в точці х = 1.25.
x i
| 1
| 1.5
| 2
| 2.5
| 3
| 3.5
|
y i
| 0.5
| 2.2
| 2
| 1.8
| 0.5
| 2.25
|
2) Побудувати
інтерполяційний многочлен Лагранжа. Накреслити графік і зазначити на ньому вузли інтерполяції. Обчислити значення в точці х = 1.2.
x i
| 0
| 0.25
| 1.25
| 2.125
| 3.25
|
y i
| 5.0
| 4.6
| 5.7
| 5.017
| 4.333
|
3) Виконати
інтерполяцію сплайнами третього ступеня. Побудувати графік і зазначити на ньому вузли інтерполяції.
Постановка завдання інтерполяція. Нехай відомі значення
функції утворюють наступну таблицю:
x 0
| x 1
| x 2
| ...
| X n-1
| x n
|
y 0
| y 1
| y 2
| ...
| y n-1
| y n
|
При цьому потрібно отримати значення функції f в точці x, що належить
відрізку [x
0 .. x
n] але не збігається ні з одним значенням x
i. Часто при цьому не відомо аналітичне вираз функції f (x), або воно не придатне для обчислень.
У цих випадках використовується прийом побудови наближає функції F (x), яка дуже близька до f (x) і збігається з нею в точках x
0, x
1, x
2, ... x
n. При цьому перебування наближеною функції називається
інтерполяцією, а точки x
0, x
1, x
2, ... x
n - вузлами інтерполяції. Зазвичай
інтерполює шукають у вигляді полінома n ступеня:
P n (x) = a 0 x n + a 1 x n-1 + a 2 x n-2 +...+ a n-1 x + a n Для кожного набору точок є тільки один інтерполяційний многочлен, мірою не більше n. Однозначно певний многочлен може бути представлений в різних видах. Розглянемо інтерполяційний многочлен Ньютона і Лагранжа.
Інтерполяціонная формула Лагранжа. Формула Лагранжа є найбільш загальною, може застосовуватися до таких вузлів інтерполяції, що відстань між сусідніми вузлами не постійна величина.
Побудуємо інтерполяційний поліном L
n (x) ступеня не більше n, і для якого виконуються умови L
n (x
i) = y
i. Запишемо його у вигляді суми:
L
n (x) = l
0 (x) + l
1 (x) + l
2 (x )+...+ l
n (x),
(1)
де
l k (x i) = y
i, якщо i = k, і
l k (x i) = 0, якщо i ≠ k;
Тоді многочлен
l k (x) має наступний вигляд:
(Xx 0) (xx 1 )...( xx i-1) (xx i +1) (xx n) (X i-x 0) (x i-x 1 )...( x i-x i-1) (x i-x i +1) (x i-x n)
|
l k (x) = (2)
Підставимо (2) в (1) і перепишемо
L n (x) у вигляді:
Якщо
функція f (x), що підлягає інтерполяції, диференційовна більше ніж n +1 раз, то похибка інтерполяції оцінюється таким чином:
где0
<θ <1 (3)
Інтерполяціонная формула Ньютона. Побудова інтерполяційного многочлена у формі Ньютона застосовується головним чином коли різниця x
i +1-x i =
h постійна для всіх значень x = 0 .. n-1.
Кінцева різниця k-го порядку:
Δy
i = y
i +1-y i Δ
2 y
i = Δy
i +1 - Δy
i = y
i +2-2y i +1 + y
i ... ... ... ... ... ... ... ... ... ... ... ...
Δ
k y
i = y
i + k-ky i +1- k + k (k-1) / 2! * Y
i + k-2 +...+(- 1)
k y
i Будемо шукати інтерполяційний многочлен у вигляді:
Pn (x) = a
0 + a
1 (xx
0) + a
2 (xx
0) (xx
1 )+...+ a
n (xx
0) (xx
1 )...( xx
n-1) Знайдемо значення коефіцієнтів a
0, a
1, a
2, ..., a
n: Вважаючи x = x
0, знаходимо a
0 = P (x
0) = y
0; Далі підставляючи значення x
1, x
2, ..., x
n отримуємо:
a
1 = Δy
0 / h
a
2 = Δ
2 y
0 / 2! h
2 a
3 = Δ
3 y
0 / 3! h
3 ....................
a
n = Δ
n y
0 / n! h
n Таким чином:
Pn (x) = y
0 + Δy
0 / h * (xx
0) + Δ
2 y
0 / 2! H
2 * (xx
0) (xx
1 )+...+ Δ
n y
0 / n! h
n * (xx
0) (xx
1 )...( xx
n -1) (1)
Практично формула (1) застосовується в дещо іншому вигляді:
Візьмемо: t = (xx
0) / h, тоді x = x
0 + th і формула (1) переписується як:
P n (x) = y 0 + t Δ y 0 + t (t-1) / 2! Δ 2 y 0 +...+ t (t-1 )...( t-n +1) / n! Δ n y 0 (2)
Формула (2) називається
інтерполяційної формулою Ньютона.
Похибка методу Ньютона оцінюється таким чином:
(3)
Інтерполяція сплайнами. При великій кількості вузлів інтерполяції сильно зростає ступінь
інтерполяційних многочленів, що робить їх незручними для проведення обчислень.
Високій многочленів можна уникнути, розбивши відрізок інтерполювання на кілька частин, з побудовою в кожній частині свого інтерполяційного полінома.
Такий метод називається інтерполяцією сплайнами. Найбільш поширеним є побудова на кожному відрізку [x
i, x
i +1], i = 0 .. n-1 кубічної функції. При цьому сплайн - кусково функція, на кожному відрізку задана кубічної
функцією, є кусково-неперервною, разом зі своїми першої та другої похідної.
Будемо шукати кубічний сплайн на кожному з часткових відрізків [x
i, x
i +1] у вигляді:
, Де a
i, b
i, c
i, d
i - невідомі.
З
того що S
i (x
i) = y
i отримаємо:
У силу безперервності зажадаємо збігу значень у вузлах, тобто:
, I = 0 .. n-1; (1)
Також вимагатимемо збігу значень першої та другої похідної:
, I = 0 .. n-2, (2)
, I = 0 .. n-2, (3)
З (1) отримаємо n лінійних рівнянь з 3n невідомими
, I = 0 .. n-1; (1 *)
З (2) та (3) отримаємо 2 (n-1) лінійних рівнянь з тими ж невідомими:
, I = 0 .. n-1; (2 *)
, I = 1 .. n-1; (3 *)
Відсутні два рівняння визначимо наступним чином. Припустимо, що в точках х
0 та х
n похідна дорівнює нулю і отримаємо ще два рівняння. Отримаємо систему з 3 * n лінійних рівнянь з 3 * n невідомими. Вирішимо її будь-яким з методів і побудуємо
інтерполяційну функцію, таку що на відрізку [x
i, x
i +1] вона дорівнює S
i. Метод Лагранжа procedure TForm1.Button1Click (Sender: TObject);
type tip = array of real;
var x, y: tip;
i, j, n: byte;
p, s, xx: real;
begin
n: = edt.Count;
setlength (x, n);
setlength (y, n);
for i: = 0 to n-1 do x [i]: = edt.massiv [i]; edt.Lines.Delete (0);
for i: = 0 to n-1 do y [i]: = edt.massiv [i]; edt.Lines.Delete (0);
xx: = strtofloat (edt.Text);
edt.Lines.Delete (0);
s: = 0;
for i: = 0 to n-1 do
begin
p: = 1;
for j: = 0 to n-1 do if i <> j then p: = p * (xx-x [j]) / (x [i]-x [j]);
p: = p * y [i];
s: = s + p;
end;
edt.writer ('', 1);
edt.writer ('', s, 1);
end;
Сплайн - інтерполяція (програма складає систему лінійних рівнянь, розв'язуючи яку знаходимо коефіцієнти кубічних сплайнів).
procedure TForm1.Button1Click (Sender: TObject);
var b, c, d, x, y: array of real;
urm: array of array of real;
i, j, k, n: byte;
begin
n: = edt.Count;
setlength (x, n); setlength (y, n);
for i: = 0 to n-1 do x [i]: = edt.massiv [i]; edt.Lines.Delete (0);
for i: = 0 to n-1 do y [i]: = edt.massiv [i]; edt.Lines.Delete (0);
setlength (b, n-1); setlength (c, n-1); setlength (d, n-1);
setlength (urm, 3 * (n-1), 3 * (n-1) +1);
for i: = 0 to 3 * (n-1) -1 do
for j: = 0 to 3 * (n-1) do urm [i, j]: = 0;
for i: = 0 to n-1 do edt.writer ('', y [i], 0);
for i: = 0 to n-2 do
begin
urm [i, 3 * i +0]: = x [i +1]-x [i];
urm [i, 3 * i +1]: = (x [i +1]-x [i]) * (x [i +1]-x [i]);
urm [i, 3 * i +2]: = (x [i +1]-x [i]) * (x [i +1]-x [i]) * (x [i +1]-x [ i]);
urm [i, 3 * (n-1)]: = y [i +1]-y [i];
end;
for i: = 0 to n-3 do
begin
urm [i + n-1, 3 * i +0]: = 1;
urm [i + n-1, 3 * i +1]: = 2 * (x [i +1]-x [i]);
urm [i + n-1, 3 * i +2]: = 3 * (x [i +1]-x [i]) * (x [i +1]-x [i]);
urm [i + n-1, 3 * i +3]: =- 1;
end;
for i: = 0 to n-3 do
begin
urm [i +2 * n-3, 3 * i +1]: = 1;
urm [i +2 * n-3, 3 * i +2]: = 3 * (x [i +1]-x [i]);
urm [i +2 * n-3, 3 * i +4]: =- 1;
end;
urm [3 * n-5, 0]: = 1; urm [3 * n-5, 3 * (n-1)]: = 0;
urm [3 * n-4, 3 * (n-1) -3]: = 1; urm [i +2 * n-3, 3 * (n-1) -2]: = 2 * (y [n -1]-y [n-2])]
urm [3 * n-4, 3 * (n-1) -1]: = 3 * (y [n-1]-y [n-2]) * (y [n-1]-y [n- 2]);
urm [i +2 * n-3, 3 * (n-1)]: = 0
for i: = 0 to 3 * (n-1) -1 do
begin
edt.writer ('', 1);
for j: = 0 to 3 * (n-1) do edt.writer ('', urm [i, j], 0);
end;
end;
Виконати інтерполяцію сплайнами третього ступеня. Побудувати графік і зазначити на ньому вузли інтерполяції.
Рішення. Будемо шукати кубічний сплайн на кожному з часткових відрізків [x
i, x
i +1], i = 0 .. 2 у вигляді:
, Де a
i, b
i, c
i, d
i - невідомі.
З того що S
i (x
i) = y
i отримаємо:
Відповідно до теоретичним положеннями викладеними вище, складемо систему лінійних рівнянь, матриця якої матиме вигляд:
При цьому ми зажадали рівності похідної нулю.
Вирішуючи систему рівнянь одержимо вектор рішень [b
1, c
1, d
1, b
2, c
2, d
2]: Підставляючи в рівняння значення b
1, c
1, d
1, отримаємо на відрізку [7 .. 9]:
Якщо вираз спростити то:
Аналогічно підставляючи в рівняння значення b
2, c
2, d
2, отримаємо на відрізку [9 .. 13]:
або
Графік має вигляд:
Метод Ньютона procedure TForm1.Button1Click (Sender: TObject);
type tip = array of real;
var x, y: tip;
i, j, n: byte;
p, s, xx, t, h: real;
kp: array of array of real;
begin
n: = edt.Count;
setlength (x, n);
setlength (y, n);
for i: = 0 to n-1 do x [i]: = edt.massiv [i]; edt.Lines.Delete (0);
for i: = 0 to n-1 do y [i]: = edt.massiv [i]; edt.Lines.Delete (0);
xx: = strtofloat (edt.Text);
edt.Lines.Delete (0);
setlength (kp, n, n);
for i: = 0 to n-1 do for j: = 0 to n-1 do kp [i, j]: = 0;
for i: = 0 to n-1 do kp [0, i]: = y [i];
for i: = 1 to n-1 do
for j: = 0 to ni-1 do
kp [i, j]: = kp [i-1, j +1]-kp [i-1, j];
for i: = 0 to n-1 do
begin
for j: = 0 to n-1 do edt.writer ('', kp [i, j], 0);
edt.writer ('', 1);
end;
edt.writer ('', 1);
h: = 0.5;
t: = (xx-x [0]) / h;
s: = y [0];
for i: = 1 to n-1 do
begin
p: = 1;
for j: = 0 to i-1 do p: = p * (tj) / (j +1);
s: = s + p * kp [i, 0];
end;
edt.writer ('', s, 1);;
end;
Побудувати інтерполяційний многочлен Ньютона. Накреслити графік і зазначити на ньому вузли інтерполяції. Обчислити значення функції в точці х = 1.25.
x i
| 1
| 1.5
| 2
| 2.5
| 3
| 3.5
|
y i
| 0.5
| 2.2
| 2
| 1.8
| 0.5
| 2.25
|
Рішення. Побудуємо таблицю кінцевих різниць у вигляді матриці:
Скористаємося інтерполяційної формулою Ньютона:
P n (x) = y 0 + t Δ y 0 + t (t-1) / 2! Δ 2 y 0 +...+ t (t-1 )...( t-n +1) / n ! Δ n y 0 Підставивши значення отримаємо многочлен п'ятого ступеня, спростивши який отримаємо:
P
5 (x) = 2.2x
5-24x 4 +101.783 x
3-20.2x 2 +211.417 x-80.7
Обчислимо значення функції в точці x = 1.25; P (1.25) = 2.0488;
Графік функції має вигляд:
Побудувати інтерполяційний многочлен Лагранжа. Накреслити графік і зазначити на ньому вузли інтерполяції. Обчислити значення в точці х = 1.2.
x i
| 0
| 0.25
| 1.25
| 2.125
| 3.25
|
y i
| 5.0
| 4.6
| 5.7
| 5.017
| 4.333
|
Рішення. Побудуємо інтерполяційний многочлен Лагранжа
L 4 (x), підставивши значення з
таблиці в формулу:
Напишемо програму і обчислимо значення многочлена в точці х = 1.2:
L 4 (1.2) = 5.657; Отриманий многочлен має
четверту ступінь. Спростимо його і отримаємо:
Побудуємо графік отриманого полінома: