Сплайн интерполяция. Отчёт по домашней работе №3

Сплайн интерполяция
Назаров Максим Вячеславович
Найти приближение функции заданной в равноотстоящих точках, т.е. функции, заданной в виде последовательности чисел, с помощью сплайна третьей степени.
Произвести анализ результатов. Предусмотреть возможность выбора размера последовательности преобразования без перекомпиляции программы. Размер последовательности N, где N = 5, 6, 7, … . Оценить вычислительную сложность.

Теория
Сплайн – функция, которая вместе с несколькими производными непрерывна на всем заданном отрезке [a, b], а на каждом частичном отрезке [??, ??+1] в отдельности является некоторым алгебраическим многочленом.
Степенью сплайна называется максимальная по всем частичным отрезкам степень многочленов, а дефектом сплайна - разность между степенью сплайна и порядком наивысшей непрерывной на [a, b] производной. Например, непрерывная ломанная является сплайном степени 1 с дефектом 1 (так как сама функция – непрерывна, а первая производная уже разрывна).
Назаров Максим Вячеславович

Теория
На практике наиболее часто используются кубические сплайны ?3(?) - сплайны третьей степени с непрерывной, по крайней мере, первой производной. При этом величина ?? = ?'3(??), называется наклоном сплайна в точке ??.
Разобьём отрезок [a, b] на N равных отрезков [??, ??+1], где ?? = ? + ?ℎ, i=0, 1, …, N-1, ?? = ?, ℎ = (? − ?)/?.
Назаров Максим Вячеславович

Теория
Назаров Максим Вячеславович

Теория
Таким образом, для того, чтобы задать кубический сплайн на отрезке, необходимо задать значения ??, ?? i=0,1…, N в N+1 в узле ??.
Кубический сплайн, принимающий в узлах те же значения ?? , что и некоторая функция, называется интерполяционным и служит для аппроксимации функции f на отрезке [a, b] вместе с несколькими производными.
Назаров Максим Вячеславович

Программа
#include
#include
#include
#include
using namespace std;
typedef array
polynome;
int main() {
double a, b;
int n;
vector
m = {};
vector
x = {};
vector
f = {};
printf("Введите границы: ");
scanf("%lf %lf",&a,&b);
printf("Введите N: ");
scanf("%d",&n);
double h = (b-a)/n;
for (int i = 0; i <= n; i++) {
x.push_back(a+i*h);
printf("f(%lf): ",x[i]);
double tmp;
scanf("%lf",&tmp);
f.push_back(tmp);
}
Назаров Максим Вячеславович

Программа
m.push_back((4*f[1]-f[2]-3*f[0])/(2*h));
for (int i = 1; i < n; i++)
m.push_back((f[i+1]-f[i-1])/(2*h));
m.push_back((3*f[n]-f[n-2]-3*f[n-1])/(2*h));
for (int i = 0; i < n; i++) {
polynome s = {
(-2*x[i]*pow(x[i+1],2)+h*pow(x[i+1],2))/pow(h,3)*f[i]+
(2*x[i+1]*pow(x[i],2)+h*pow(x[i],2))/pow(h,3)*f[i+1]+
(x[i]*pow(x[i+1],2))/pow(h,2)*m[i]+
(x[i+1]*pow(x[i],2))/pow(h,2)*m[i+1],
(2*pow(x[i+1],2)+4*x[i]*x[i+1]-2*x[i+1]*h)/pow(h,3)*f[i]+
(-4*x[i]*x[i+1]-2*x[i]*h-2*pow(x[i],2))/pow(h,3)*f[i+1]+
(pow(x[i+1],2)+2*x[i]*x[i+1])/pow(h,2)*m[i]+
(2*x[i]*x[i+1]+pow(x[i],2))/pow(h,2)*m[i+1],
(-4*x[i+1]-2*x[i]+h)/pow(h,3)*f[i]+
(4*x[i]+2*x[i+1]+h)/pow(h,3)*f[i+1]+
(-2*x[i+1]-x[i])/pow(h,2)*m[i]+
(-2*x[i]-x[i+1])/pow(h,2)*m[i+1],
2/pow(h,3)*f[i]-
2/pow(h,3)*f[i+1]+
1/pow(h,2)*m[i]+
1/pow(h,2)*m[i+1],
};
double check = (s[3]*(pow(x[i],3)+pow(x[i+1],3))+
s[2]*(pow(x[i],2)+pow(x[i+1],2))+
s[1]*(x[i]+x[i+1]))/2+s[0];
s[0] -= (check-(f[i]+f[i+1])/2);
printf("x ∈ [%lf, %lf], S3(x) = (%lf)x^3 + (%lf)x^2 + (%lf)x +(%lf)\n",
x[i],x[i+1], s[3],s[2],s[1],s[0]
);
}
}
Назаров Максим Вячеславович

Пример вывода
Введите границы: 0 10
Введите N: 3
f(0.000000): 1
f(3.333333): 2
f(6.666667): 5
f(10.000000): 6
x ∈ [0.000000, 3.333333], S3(x) = (0.000000)x^3 + (0.090000)x^2 + (0.000000)x + (1.000000)
x ∈ [3.333333, 6.666667], S3(x) = (-0.054000)x^3 + (0.810000)x^2 + (-3.000000)x +
(5.000000)
x ∈ [6.666667, 10.000000], S3(x) = (0.013500)x^3 + (-0.405000)x^2 + (4.200000)x + (-
9.000000)
Назаров Максим Вячеславович

Трудоемкость
Назаров Максим Вячеславович

Выводы
В ходе выполнения домашнего задания я написал программу на языке С++; для нахождения приближения функции с помощью сплайна третьей степени; произвел анализ результатов. В отчете предоставил текст задачи, код программы, а также вычислил трудоемкость алгоритма.
Назаров Максим Вячеславович

Источники
Назаров Максим Вячеславович