Аппроксимация и интерполяция

Подставим все данные:

Решая систему, получим: . Воспользуемся подстановкой (2.1.12) и вычислим значения :

Получим следующую интерполяционную систему:

Проверка:

Рис.2.1.2 погрешность сплайн-интерполяции при задании поведения 1й производной

 

2) Т.к. дополнительные условия описывают поведение 2й производной, составим систему вида (2.1.16):

Подставим все  данные:

Решая систему, получим: . Воспользуемся подстановкой (2.1.12) и вычислим значения :

Получим следующую интерполяционную систему:

Проверка:

Рис.2.1.3 погрешность сплайн-интерполяции при задании поведения 2й производной

 

3) Т.к. дополнительные условия описывают естественный кубический сплайн, составим систему вида (2.1.17):

Подставим все данные:

Решая систему, получим: . Воспользуемся подстановкой (2.1.12) и вычислим значения :

Получим следующую интерполяционную систему:

Проверка:

Рис.2.1.3 погрешность сплайн-интерполяции при задании поведения 2й производной

 

2я специальная форма записи сплайнов

В данном случае S_i(x) имеет вид:

Si(x) = ai+bi(x-xi-1) + ci(x-xi-1)2+di(x-xi-1)3   (i= 1, 2,... n)

(2.2.1)

Последний пункт  определения сплайна в сочетании  с формулой (2.2.1) позволяет немедленно найти коэффициенты а_i:

уi-1 = S(х i-1) = Si(x i-1) = ai, или аi = yi-1

(2.2.2)

Условие непрерывности S(x) в каждом узле приводит к равенствам S_i(х_i) = S_i+1(x_i)  (i = 1, ..., n - 1). В развернутом виде с учетом (2.2.1) эти равенства примут вид

аi + bi(хi - хi-1) + сi(хi - хi-1)2 + di(xi - xi-1)3 = ai+1

(2.2.3)

Введем обозначение h_i = x_i - x_i-1. Учитывая (2.2.2), получим:

hibi-hi2ci+hi3di=yi-yi-1

(2.2.4)

Условие непрерывности  первой производной кубического  сплайна, входящее в его определение, сводится к требованию S_i’(x_i) = S_i+1’(x_i) (i = 1, …, n-1). Дифференцируя формулу (2.2.1) и пользуясь введенными выше обозначениями, получим:

bi +2hici + 3hi2di = bi+1  (i = 2, ..., п)

(2.2.5)

Осталось использовать непрерывность второй производной  сплайн-функции, т.е. условие S_i”(х_i) = S_i+1“(x_i). Оно порождает равенства:

ci + 3hidi = ci+1  (i = 2, ..., п)

(2.2.6)

Cистему (2.2.4)-(2.2.6), а предварительно исключают из нее все неизвестные каких-либо двух групп. Начнем с исключения совокупности переменных {d_i}. Для этого выразим d_i из (2.2.6):

(2.2.7)

Подставим (2.2.7) в (2.2.5) и преобразуем:

bi + cihi + ci+1hi = bi+1

(2.2.8)

Выразим b_i из (2.2.4) и подставим (2.2.8):

(2.2.9)

В (2.2.9) увеличим индекс на 1:

(2.2.10)

Подставим (2.2.8) и (2.2.9) в (2.2.5) и преобразуем:

(2.2.11)

Запишем систему  для {c _i} в общем виде:

i = 1  c1h1 + 2c2(h1+h2) + c3h2 = 3(∆2-∆1) i = 2  c2h2 + 2c3(h2+h3) + c4h3 = 3(∆3-∆2) ………………………………………………… i = n-1 cn-1hn-1 + 2cn(hn-1+hn) + cn+1hn = 3(∆n-∆n-1)

(2.2.12)

Система, формируемая  для i = 1..n-1, имеет n-1 уравнений и n+1 неизвестных {c_i}. Чтобы такая система имела единственное решение, составим еще 2 уравнения, используя краевые условия, и выразим коэффициенты c₁ и c_n+1:

1. . Подставим (3.2.9) при i = 1:  
   . Подставим (2.2.7) и (2.2.9) при i = n:               (2.2.13)
2.  
   . Подставим (3.2.7) при i = n:                     (2.2.14)

3. Воспользуемся решениями п. 2 для . Получим .

Преобразуем систему (2.2.12) в соответствии с подстановками (2.2.13) и (2.2.14):

1)  по (2.2.13)
	(2.2.15)
по (2.2.14)	(2.2.16)
3)  по (2.2.14) для естественного кубического сплайна	(2.2.17)

Системы (2.2.15) и (2.2.16) содержат лишь неизвестные {c_i} и являются системами линейных алгебраических уравнений с трехдиагональной матрицей, которые удобно решать методом прогонки. После решения системы надо вычислить коэффициенты {c₁} и {c_n+1} по формулам (2.2.13) и (2.2.14). Найдя все неизвестные {с_i} , по формулам (2.2.7) и (2.2.9) определим неизвестные {d_i} и {b_i}. На этом построение кубического сплайна завершится.

Пример. Построить кубический сплайн для функции y=f(x), заданной таблицей

x	-1	0	1	3	1)
f(x)	½	1	2	8	2)
h		1	1	2	3)
∆		½	1	3

1) Т.к. дополнительные условия описывают поведение 1й производной, составим систему вида (2.2.15):

Решая систему, получим: . Воспользуемся подстановкой (2.1.12) и вычислим значения :

Далее находим  по формуле (2.2.7) значение коэффициентов d_i:

Теперь по формуле (2.2.9) находим коэффициенты b_i:

Теперь по формуле (2.2.2) находим коэффициенты a_i:

Получим следующую интерполяционную систему:

Проверка:	Рис.2.2.1 погрешность сплайн-интерполяции при задании поведения 1й производной

 

 

2) Т.к. дополнительные условия описывают поведение 2й производной, составим систему вида (2.2.16):

Решая систему, получим: . Воспользуемся подстановкой (2.1.12) и вычислим значения :

Далее находим  по формуле (2.2.7) значение коэффициентов d_i:

Теперь по формуле (2.2.9) находим коэффициенты b_i:

Теперь по формуле (2.2.2) находим коэффициенты a_i:

Получим следующую интерполяционную систему:

Проверка:	Рис.2.2.2 погрешность сплайн-интерполяции при задании поведения 2й производной

 

 

3) Т.к. дополнительные условия описывают естественный кубический сплайн, составим систему вида (2.1.17):

Решая систему, получим: . Воспользуемся подстановкой (2.1.12) и вычислим значения :

Далее находим по формуле (2.2.7) значение коэффициентов d_i:

Теперь по формуле (2.2.9) находим коэффициенты b_i:

Теперь по формуле (2.2.2) находим коэффициенты a_i:

Получим следующую интерполяционную систему:

Проверка:	Рис.2.2.2 погрешность сплайн-интерполяции при задании поведения 2й производной

 

 

Выводы

 

Заметим, что решения задачи интерполяции с применением разных специальных форм одинаковы при одинаковых краевых условиях. Однако интерполяция с использованием разных краевых условий дает разную степень погрешности. Наиболее точно функцию можно интерполировать с заданием краевых условий через 1ю производную: в этом случае погрешность интерполяции составляет примерно 0,05 на отрезке интерполяции длиной 2. На этом же отрезке погрешность интерполяции естественным кубическим сплайном составляет примерно 0,57. Погрешность интерполяции с заданием краевых условий через 1ю производную принимает промежуточные значения.

Интерполяция  сплайнами сопряжена с немалым объемом вычислительной работы. Весьма необычна и форма окончательного результата, т.к. сплайн имеет различные представления на различных частичных отрезках интерполяции. Это осложняет доступ к значениям сплайна в каждой конкретной точке, так как предполагает прежде всего поиск параметров, определяющих соответствующую формулу сплайна. Эти трудности легко предотвратимы при использовании компьютера, так как упорядоченное хранение всех необходимых параметров организовать нетрудно, а выполнение однотипных процедур по вычислению параметров сплайна и его значений может быть обеспеченно специальными процедурами.

В данной работе описаны наиболее распространенные способы интерполяции функций: многочленами и сплайнами, а также рассмотрены 2 спецформы записи сплайнов. Данная работа может быть использована в качестве методического пособия по теме интерполяция.

В ходе выполнения работы потребовалось изучить дополнительную литературу, провести большое количество расчетов.

 

Библиографический список

 

1. М.П.Лапчик Численные методы / М.П.Лапчик, М.И.Рагулина, Е.К.Хеннер. М.: Академия, 2004. 383с.
2. Л.И.Турчак Основы численных методов. М.: Наука, 1987. 320с.
3. В.М.Вержбицкий Численные методы. М.: Высшая школа, 2001. 374с.

 

Приложение

Текст пограммы

main.cpp

#include <conio.h>

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#include <alloc.h>

#include "func.h"

void main()

{

  int res, ch;

  struct slau g;

  struct slv s;

  atexit(myexit);

  randomize(); //инициализация генератора случайных чисел

  menu(&ch); //вызов функции меню

  switch(ch) //определение выбора пользователя

  {

case 1: manualinput(&g, &s); break;

case 2: fileinput(&g, &s); break;

case 3: autoinput(&g, &s); break;

case 0: exit(1);

default: {

  textcolor(LIGHTRED);

  printf("\nWRONG INPUT!!!");

  exit(1); }

  }

  clrscr();

  printm(&g); //вывод системы на экран