Інтерполяція формули Ньютона

Інтерполяція застосовується в багатьох задачах, пов'язаних з обчисленнями. Вкажемо деякі з цих завдань. Обробка фізичного експерименту — побудова наближених формул за даними обчислювального експерименту. Тут виникають нестандартні задачі інтерполяції, так як зазвичай пишуться формули, можливо, більш простої структури.

Інтерполяційні формули використовуються також при обчисленні інтегралів, при написанні різницевих апроксимацій для диференціальних рівнянь, на основі інтегральних тотожностей.
Часто потрібно відновити функцію f(x) на відрізку a ≤ x ≤ b, якщо відомі її значення в деякому кінцевому числі точок цього відрізка.



На практиці найчастіше застосовують інтерполяцію многочленами. Це пов'язано, насамперед, з тим, що многочлени легко обчислювати, легко аналітично знаходити їх похідні і безліч багаточленів щільно в просторі неперервних функцій. Ми розглянемо більш докладно метод Ньютона.

В таблиці 1 наведено дані часової складності алгоритмів.

Таблиця 1


Вхідні дані:
x — координата, в якій необхідно обчислити.
n — Кількість вузлів.
Step — крок інтерполяції
Безліч MasX Значення x.
Безліч MasY Значення f(x).

Вихідні дані:
res — значення полінома в точці x.

Алгоритмічна модель методу Ньютона:
Безліч mas потужністю |n + 2, n + 1|;
Для всіх i від 0..2:
Для всіх j від 0..n+1:
Якщо i = 0:
masi,j = MasXj;
інакше, Якщо i = 1:
masi,j = MasYj;
m = n;
Для всіх i від 2..n+2:
Для всіх j від 0..m:
masi,j = mas(i-1),(j+1) - mas(i-1),j;
m = m-1;

Безліч dy0 потужністю |n + 1|;

Для всіх i від 0..n+1:
dy0i = mas(i + 1),0;

res = dy00;
Безліч xn потужністю |n|;
xn0 = x - mas0,0;

Для всіх i від 1..n:
ans = xni - 1 * (x - mas0, i);
xni = ans;
ans = 0;

m1 = n + 1;
fact = 1;
Для всіх i від 1..m1:
fact = fact * i;
res = res + (dy0i * xni - 1) / (fact * stepi);


На малюнку 1 зображена схема методу інтерполяції Ньютона.


Малюнок 1 — інтерполяційного методу Ньютона

// x - координата, в якій необхідно обчислити значення полінома Ньютона; n - кількість вузлів; MasX - масив x; MasY - масив значень x; step - крок
public double Newton(double x, int n, double[] MasX, double[] MasY, double step)
{
double[,] mas = new double[n + 2, n + 1];
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < n + 1; j++)
{
if (i == 0)
mas[i, j] = MasX[j];
else if (i == 1)
mas[i, j] = MasY[j];
}
}
int m = n;
for (int i = 2; i < n + 2; i++)
{
for (int j = 0; j < m; j++)
{
mas[i, j] = mas[i - 1, j + 1] - mas[i - 1, j];
}
m--;
}

double[] dy0 = new double[n + 1];

for (int i = 0; i < n + 1; i++)
{
dy0[i] = mas[i + 1, 0];
}

double res = dy0[0];
double[] xn = new double[n];
xn[0] = x - mas[0, 0];

for (int i = 1; i < n; i++)
{
double ans = xn[i - 1] * (x - mas[0, i]);
xn[i] = ans;
ans = 0;
}

int m1 = n + 1;
int fact = 1;
for (int i = 1; i < m1; i++)
{
fact = fact * i;
res = res + (dy0[i] * xn[i - 1]) / (fact * Math.Pow(step, i));
}

return res;
}


Складемо таблицю значень для f(x) = x^3.


Знайдемо полімер в точці 2.1: f(2.1) = 2.1^3=9,261

За допомогою програмної функції ми отримали такий результат (Малюнок 2).

Малюнок 2 — застосування функції

Нами були розглянуті основні методу інтерполяції многочленами. На практиці найчастіше застосовують інтерполяцію многочленами. Це пов'язано, насамперед, з тим, що многочлени легко обчислювати, легко аналітично знаходити їх похідні і безліч багаточленів щільно в просторі неперервних функцій. Ми розглянули більш детально метод Ньютона.

Ми побудували математичний опис методів, після чого приступили до розробки схеми програми.

Розробили програму реалізує інтерполяцію методу Ньютона, на мові C#, Visual Studio 2012.

Протестували програму, всі тести на основі заданих нами даних були успішно пройдені.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.