Примерно решение за интерполация чрез кубични сплайни. Сплайн теория примери за решения. Специална форма на сплайн запис
![Примерно решение за интерполация чрез кубични сплайни. Сплайн теория примери за решения. Специална форма на сплайн запис](https://i0.wp.com/studfiles.net/html/2706/35/html_I26m00Ebfk.LHeR/img-VToFZP.png)
МИНИСТЕРСТВО НА ОБРАЗОВАНИЕТО И НАУКАТА НА РУСКАТА ФЕДЕРАЦИЯ
Федерална държавна автономна образователна институция
висше професионално образование
"Уралски федерален университет на името на първия президент на Русия Б. Н. Елцин"
Институт по радиоелектроника и информационни технологии – РТФ
Отдел Автоматизация и информационни технологии
Сплайн интерполация
МЕТОДИЧЕСКИ УКАЗАНИЯ ЗА ЛАБОРАТОРНА РАБОТА ПО ДИСЦИПЛИНАТА „Числени методи”
Съставител: I.A.Selivanova, старши учител.
ИНТЕРПОЛАЦИЯ СЪС СПЛАЙН:Указания за практически занятия по дисциплината „Числени методи”
Указанията са предназначени за студенти от всички форми на обучение в направление 230100 – „Информатика и компютърни науки”.
Ó Федерална държавна автономна образователна институция за висше професионално образование "Уралски федерален университет на името на първия президент на Русия Б. Н. Елцин", 2011 г.
1. ИНТЕРПОЛАЦИЯ СЪС СПЛАЙН. 4
1.1. Кубични сплайни. 4
1.2. Специална форма на писане на сплайн. 5
1.3. Квадратни сплайни. 13
1.4. Практическа задача. 18
1.5. Опции за задачи. 19
Препратки 21
1. Сплайн интерполация.
В случаите, когато интервалът [ а,b], на който искате да замените функцията f(х) е голям, може да се приложи сплайн интерполация.
1.1. Кубични сплайни.
Интерполационни сплайни 3-торед - това са функции, състоящи се от части от полиноми 3 thпоръчка. В интерфейсните възли се осигурява непрекъснатостта на функцията и нейните първи и втори производни. Апроксимиращата функция е съставена от отделни полиноми, обикновено с еднакво малка степен, всеки дефиниран в своята част от сегмента.
Нека върху сегмента [ а,
b] реална ос х
е зададена мрежа, в чиито възли се определят стойностите функции f(х).
Необходимо е да се построи върху отсечката [ а,
b] непрекъсната сплайн функция С(х),
който отговаря на следните условия:
![](https://i2.wp.com/studfiles.net/html/2706/35/html_I26m00Ebfk.LHeR/img-R5Fw_M.png)
![](https://i0.wp.com/studfiles.net/html/2706/35/html_I26m00Ebfk.LHeR/img-ROZKsS.png)
|
![](https://i1.wp.com/studfiles.net/html/2706/35/html_I26m00Ebfk.LHeR/img-zGJyDn.png)
|
За да конструирате желания сплайн, трябва да намерите коефициентите полиноми
,аз=1,…
н, т.е. 4
н
неизвестни коефициенти, които удовлетворяват 4
н-2
уравнения (1), (2), (3). За да има решение системата от уравнения, се добавят две допълнителни (гранични) условия. Използват се три вида гранични условия:
|
Условия (1), (2), (3) и едно от условията (4), (5), (6) образуват SLAE на поръчката 4 н. Системата може да бъде решена с помощта на метода на Гаус. Въпреки това, като изберете специална форма на писане на кубичния полином, можете значително да намалите реда на системата от уравнения, която се решава.
1.2. Специална форма на писане на сплайн.
Помислете за сегмента . Нека въведем следните обозначения на променливите:
|
Тук - дължина на сегмента
,
,
- спомагателни променливи,
х– междинна точка на сегмента .
Кога х
минава през всички стойности в интервала , променлива
варира от 0 до 1 и
варира от 1 до 0.
Нека кубичният полином на сегмента
има формата:
Променливи И
се определят по отношение на конкретен интерполационен сегмент.
Нека намерим стойността на сплайна в краищата на сегмента
. Точка
е началната точка за сегмента
, Ето защо
=0,
=1 и в съответствие с (3.8):
.
В края на сегмента =1,
=0 и
.
За интервал точка
е ограничен, така че
=1,
=0 и от формула (9) получаваме:
. По този начин условието за непрекъснатост на функцията е изпълнено С(х)
в точките на свързване на кубични полиноми, независимо от избора на числа i.
За определяне на коефициентите i, аз=0,… н Нека диференцираме (8) два пъти като сложна функция на х. Тогава
Нека дефинираме вторите производни на сплайна И
:
|
За полином точка
е началото на интерполационния сегмент и
=0,
=1, следователно
От (15) и (16) следва, че на интервала [ а,b]сплайн функция, „слепена заедно“ от части от полиноми от 3-ти ред, има непрекъсната производна от 2-ри ред.
За получаване на непрекъснатост на първата производна на функция С(х), Нека изискаме следните условия да бъдат изпълнени във вътрешните интерполационни възли:
За естествен кубичен сплайн , следователно системата от уравнения ще изглежда така:
и системата от уравнения (17) ще изглежда така:
|
Пример.
Първоначални данни:
|
Замяна на функция интерполиращ кубичен сплайн, чиито стойности в дадени възлови точки (виж таблицата) съвпадат със стойностите на функцията в същите точки. Разгледайте различни гранични условия.
Нека изчислим стойността на функцията в възловите точки. За да направите това, заменете стойностите от таблицата в дадената функция.
Нека разгледаме първите гранични условия.
За различни гранични условия (4), (5), (6) намираме коефициентите на кубичните сплайни.
|
В нашия случай н=3,
,
,
. Да намеря
използваме системата от уравнения (3.18):
|
Нека изчислим И
, използвайки формули (7) и (11):
Нека заместим получените стойности в системата от уравнения:
.
Системно решение:
Като се вземат предвид първите гранични условия, коефициентите на сплайн са:
Нека разгледаме дефиницията на сплайн коефициентите, като вземем предвид граничните условия (3.5):
Нека намерим производната на функцията :
Нека изчислим И
:
Нека заместим в системата от уравнения (21) стойностите И
:
Използвайки формула (20), определяме 0 и 3:
Като се вземат предвид конкретни стойности:
|
и вектор на коефициентите:
Нека изчислим стойностите на кубичния сплайн S(x) в средните точки на интерполационните сегменти.
Средни точки на сегменти:
За да изчислим стойността на кубичния сплайн в средата на интерполационните сегменти, използваме формули (7) и (9).
3.1.
Ще намерим И
:
Във формула (3.9) заместваме коефициентите
3.2.
Ще намерим И
:
, за гранични условия (4), (5), (6):
3.3.
Ще намерим И
:
Във формула (9) заместваме коефициентите , за гранични условия (4), (5), (6):
Нека направим таблица:
|
|
| ||
| ||||
| ||||
|
Думата сплайн (английската дума "spline") означава гъвкава линийка, използвана за изчертаване на гладки криви през дадени точки на равнина. Формата на този универсален модел на всеки сегмент е описана от кубична парабола. Сплайновете се използват широко в инженерните приложения, особено в компютърната графика. И така, на всеки аз–ти сегмент [ x i –1 ,x i], i= 1, 2,…, Н,Ще търсим решение под формата на полином от трета степен:
S i(х)=a i +b i(x–x i)+c i(х–x i) 2 /2+d i(x–x i) 3 /6
Неизвестни коефициенти a i, b i, c i, d i, i= 1, 2,..., Н,намираме от:
Условия на интерполация: S i(x i)=f i , i= 1, 2,..., н;С 1 (х 0)=f 0 ,
Непрекъснатост на функцията S i(x i– 1 )=S i– 1 (x i –1), i= 2, 3,..., Н,
Непрекъсваемост на първата и втората производна:
S/i(x i– 1)=S/i– 1 (x i –1), S//i(x i –1)=S //i –1 (x i –1), i= 2, 3,..., н.
Като се има предвид, че за дефиниция 4 ннеизвестни получаваме система 4 н–2 уравнения:
a i =f i , i= 1, 2,..., Н,
b i h i – c i h i 2 /2+ d i h i 3 /6=f i – f i –1 , i= 1, 2,..., Н,
b i – b i–1 = c i h i – d i h i 2 /2, i= 2, 3,..., Н,
d i h i = c i – c i– 1 , i= 2, 3,..., Н.
Където h i =x i – x i– 1. Липсващите две уравнения са получени от допълнителни условия: С //(а)=S //(b)=0. Може да се покаже, че в този случай. Неизвестните могат да бъдат изключени от системата b i, d i,след получаване на системата N+ 1 линейни уравнения (SLAE) за определяне на коеф c i:
° С 0 = 0, c N = 0,
h i c i –1 +
2(h i +h i +1)c i +h i +1 c i +1 =
6 , i= 1, 2,…, н–1. (1)
След това се изчисляват коефициентите b i, d i:
, i= 1, 2,..., Н. (2)
В случай на постоянна мрежа h i = hТази система от уравнения е опростена.
Тази SLAE има тридиагонална матрица и се решава чрез метода на почистване.
Коефициентите се определят по формулите:
За изчисляване на стойността С(х) в произволна точка от сегмента z∈[а, б] е необходимо да се реши системата от уравнения за коефициентите c i , i= 1,2,…, н–1, след това намерете всички коефициенти b i, d i.След това трябва да определите за какъв интервал [ x i 0, x i 0–1 ] тази точка удря и, знаейки числото аз 0,изчисляване на стойността на сплайна и неговите производни в точка z
С(z)=a i 0 +b i 0 (z–xi 0)+c i 0 (z–xi 0) 2 /2+d i 0 (z–xi 0) 3 /6
С/(z)=b i 0 +c i 0 (z–xi 0)+d i 0 (z–xi 0) 2 /2, С //(z)=c i 0 +d i 0 (z–xi 0).
Необходимо е да се изчислят стойностите на функцията в точки 0,25 и 0,8, като се използва сплайн интерполация.
В нашия случай: h i =1/4, .
Нека напишем система от уравнения, за да определим:
Решавайки тази система от линейни уравнения, получаваме: .
Нека разгледаме точката 0,25, която принадлежи на първия сегмент, т.е. . Следователно получаваме,
Нека разгледаме точка 0.8, която принадлежи към четвъртия сегмент, т.е. .
следователно
Глобална интерполация
Кога глобална интерполациянамира се един полином в целия интервал [ а, б], т.е. конструира се полином, който се използва за интерполиране на функцията f(x) върху целия интервал на изменение на аргумента x. Ще търсим интерполираща функция под формата на полином (полином) м-та степен следобед(х)=а 0 +a 1 x+a 2 х 2 +a 3 х 3 +...+a m x m.Каква трябва да бъде степента на полинома, за да бъдат изпълнени всички условия за интерполация? Да приемем, че са дадени две точки: ( х 0 , е 0) и ( х 1 , е 1), т.е. N=1. През тези точки може да се прекара една права линия, т.е. интерполиращата функция ще бъде полином от първа степен П 1 (х)=а 0 +a 1 х.Чрез три точки (N=2) можете да начертаете парабола П 2 (х)=а 0 +a 1 x+a 2 х 2 и т.н. Разсъждавайки по този начин, можем да приемем, че желаният полином трябва да има степен н .
За да докажем това, написваме система от уравнения за коефициентите. Системните уравнения представляват условията на интерполация за всяко x=x i:
Тази система е линейна по отношение на необходимите коефициенти а 0 , а 1 , а 2 , …,един Н.Известно е, че SLAE има решение, ако неговият детерминант е различен от нула. Детерминанта на тази система
носи името Детерминант Вандермонд. От курса на математическия анализ е известно, че е различно от нула ако x k≠x m(т.е. всички интерполационни възли са различни). Така се доказва, че системата има решение.
Показахме, че за намиране на коефициентите
а 0 , а 1 , а 2 ,
…,един Ннеобходимо е да се реши SLAE, което е трудна задача. Но има и друг начин за конструиране на полином н-та степен, която не изисква решаване на такава система.
Полином на Лагранж
Търсим решение във формата , Където аз(z) –
базисни полиноми н-та степен, за която е изпълнено условието:
. Нека се уверим, че ако такива полиноми са конструирани, тогава L N (x)ще отговаря на условията за интерполация:
Как да конструираме базисни полиноми? Да дефинираме
, i= 0, 1,..., Н.
Лесно е да се разбере това
функция аз(z) е полином н-та степен от zи за него са изпълнени условията за „основност“:
0, i≠k;, т.е. k=1,…,i-1 или k=i+1,…,N.
Така успяхме да решим проблема с конструирането на интерполиращ полином Н-степен, като за това не е необходимо да решавате SLAE. Полиномът на Лагранж може да бъде написан като компактна формула: .
Грешката на тази формула може да бъде оценена, ако оригиналната функция ж(х) има производни до N+ 1-ва поръчка:
От тази формула следва, че грешката на метода зависи от свойствата на функцията ж(х), както и местоположението на интерполационните възли и точки z.Както показват изчислителните експерименти, Полиномът на Лагранж има малка грешка за малки стойности н<20 . При по-големи нгрешката започва да нараства, което показва, че методът на Лагранж не се сближава (т.е. грешката му не намалява с нарастване н).
Нека разгледаме специални случаи. Нека N=1, т.е. Стойностите на функцията са посочени само в две точки. Тогава основните полиноми имат формата:
, т.е. получаваме формули за частично линейна интерполация.
Нека N=2. Тогава:
В резултат получихме формулите на т.нар квадратична или параболична интерполация.
Пример:Дадени са стойностите на определена функция:
х | 3.5 | |||
f | -1 | 0.2 | 0.5 | 0.8 |
Изисква се да се намери стойността на функцията, когато z= 1, използвайки интерполационния полином на Lgrange. ad hoc н=3, т.е. Полиномът на Лагранж е от трети ред. Нека изчислим стойностите на базовите полиноми при z=1:
Избор на емпирични формули
При интерполиране на функции използвахме условието за равенство на стойностите на интерполационния полином и дадената функция в интерполационните възли. Ако първоначалните данни са получени в резултат на експериментални измервания, тогава изискването за точно съвпадение не е необходимо, тъй като данните не са получени точно. В тези случаи можете да изисквате само приблизително изпълнение на условията за интерполация. Това условие означава, че интерполиращата функция F(x)минава не точно през дадените точки, а в някаква тяхна близост, например, както е показано на фиг.
След това говорят за избор на емпирични формули. Изграждането на емпирична формула се състои от два етапа6 на избор на типа на тази формула, съдържаща неизвестни параметри, и определяне на най-добрия в известен смисъл от тези параметри. Формата на формулата понякога е известна от физически съображения (за еластична среда, връзката между напрежението и деформацията) или е избрана от геометрични съображения: експерименталните точки се нанасят върху графика и общата форма на връзката се отгатва приблизително чрез сравняване получената крива с графики на тегловни функции. Успехът тук до голяма степен се определя от опита и интуицията на изследователя.
За практиката е важен случаят на апроксимация на функция с полиноми, т.е. .
След като е избран типът на емпиричната зависимост, степента на близост до емпиричните данни се определя с помощта на минимална сума на квадратите на отклоненията на изчислените и експериментални данни.
Метод на най-малките квадрати
Нека за първоначалните данни x i, f i, i= 1,…,N (по-добре е номерирането да започне от едно),Избраният тип емпирична зависимост е: с неизвестни коефициенти. Нека запишем сумата от квадратите на отклоненията между изчислените по емпиричната формула и дадените експериментални данни:
Параметрите ще намерим от условието за минимум на функцията . Това е метод на най-малките квадрати (LSM).
Известно е, че в минималната точка всички частни производни на са равни на нула:
(1)
Нека разгледаме използването на най-малките квадрати за специален случай, който се използва широко в практиката. Като емпирична функция, разгледайте полинома
Формула (1) за определяне на сумата от квадратите на отклоненията ще приеме формата:
Нека изчислим производните:
Приравнявайки тези изрази на нула и събирайки коефициентите за неизвестните, получаваме следната система от линейни уравнения.
Интерполационни формули на Лагранж, Нютон и Стърлинг и др. при използване на голям брой интерполационни възли на целия сегмент [ а, b] често водят до лошо приближение поради натрупването на грешки по време на процеса на изчисление. В допълнение, поради разминаването на процеса на интерполация, увеличаването на броя на възлите не води непременно до повишена точност. За да намалите грешките, целият сегмент [ а, b] се разделя на частични сегменти и на всеки от тях функцията се замества приблизително с полином от ниска степен. Нарича се частична полиномна интерполация.
Един от методите за интерполация върху целия сегмент [ а, b] е сплайн интерполация.
Сплайне частична полиномна функция, дефинирана на интервала [ а, b] и имащ определен брой непрекъснати производни на този сегмент. Предимствата на сплайн интерполацията в сравнение с конвенционалните методи за интерполация са конвергенцията и стабилността на изчислителния процес.
Нека разгледаме един от най-често срещаните случаи в практиката - интерполация на функция кубичен сплайн.
Нека върху сегмента [ а, b] е зададена непрекъсната функция. Нека въведем разделяне на сегмента:
и обозначават, .
Сплайн, съответстващ на дадена функция и интерполационни възли (6), е функция, която отговаря на следните условия:
1) на всеки сегмент функцията е кубичен полином;
2) функцията, както и нейните първа и втора производни, са непрекъснати на интервала [ а, b] ;
Третото условие се нарича условие за интерполация. Извиква се сплайн, определен от условия 1) – 3). интерполиращ кубичен сплайн.
Нека разгледаме метод за конструиране на кубичен сплайн.
На всеки от сегментите, Ще търсим сплайн функция под формата на полином от трета степен:
(7)
Където необходимите коефициенти.
Нека диференцираме (7) три пъти по отношение на х:
откъде следва
От условие за интерполация 3) получаваме:
Това следва от условията за непрекъснатост на функцията.
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407838983_screenshot_2.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839059_screenshot_3.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839010_screenshot_4.png)
![](https://i2.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839076_screenshot_5.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839019_screenshot_6.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839026_screenshot_7.png)
![](https://i2.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839029_screenshot_8.png)
![](https://i2.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839019_screenshot_9.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839045_screenshot_10.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839000_screenshot_11.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839065_screenshot_12.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839030_screenshot_13.png)
![](https://i2.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839075_screenshot_14.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839009_screenshot_15.png)
![](https://i2.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839044_screenshot_16.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839057_screenshot_17.png)
![](https://i2.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839006_screenshot_18.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839029_screenshot_19.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839013_screenshot_20.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839015_screenshot_21.png)
![](https://i2.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839023_screenshot_22.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839018_screenshot_23.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839049_screenshot_24.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839070_screenshot_25.png)
![](https://i1.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839022_screenshot_26.png)
![](https://i0.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839041_screenshot_27.png)
![](https://i2.wp.com/natalibrilenova.ru/uploads/posts/2014-08/1407839058_screenshot_28.png)
Кривите и повърхнините, които се срещат в практическите задачи, често имат доста сложна форма, което не позволява универсална аналитична задача като цяло, използвайки елементарни функции. Следователно те се сглобяват от сравнително прости гладки фрагменти - сегменти (криви) или разфасовки (повърхности), всеки от които може да бъде доста задоволително описан с помощта на елементарни функции на една или две променливи. В този случай е съвсем естествено да се изисква гладките функции, които се използват за конструиране на частични криви или повърхнини, да бъдат от подобно естество, например да бъдат полиноми от еднаква степен. И за да бъде получената извивка или повърхност достатъчно гладка, трябва да сте особено внимателни къде се съединяват съответните фрагменти. Степента на полиномите се избира от прости геометрични съображения и като правило е малка. За плавна промяна на допирателната по цялата съставна крива е достатъчно да се опишат свързаните криви с полиноми от трета степен, кубични полиноми. Коефициентите на такива полиноми винаги могат да бъдат избрани така, че кривината на съответната съставна крива да е непрекъсната. Кубичните сплайни, които възникват при решаването на едномерни проблеми, могат да бъдат адаптирани към изграждането на фрагменти от композитни повърхности. И тук бикубичните сплайнове се появяват съвсем естествено, описани с полиноми от трета степен във всяка от двете променливи. Работата с такива сплайнове изисква значително по-голям обем изчисления. Но правилно организираният процес ще позволи да се вземат предвид непрекъснато нарастващите възможности на компютърните технологии в максимална степен. Сплайн функции Нека върху сегмента, т.е. Забележка. Индексът (t) на числата a^ показва това. че наборът от коефициенти, който определя функцията 5(x) на всеки частичен сегмент D е различен. На всяка от отсечките D1 сплайнът 5(x) е полином от степен p и се определя на тази отсечка от p + 1 коефициент. Общо частични сегменти - тогава. Това означава, че за да се определи напълно сплайнът, е необходимо да се намери (p + 1), тогава числата означават непрекъснатостта на функцията 5(x) и нейните производни във всички вътрешни възли на мрежата w. Броят на тези възли е m - 1. По този начин, за да се намерят коефициентите на всички полиноми, се получават p(m - 1) условия (уравнения). За да се дефинира напълно сплайн, няма достатъчно условия (уравнения), които се определят от естеството на разглеждания проблем, а понякога просто от желанието на потребителя. ТЕОРИЯ НА СПЛАЙНИТЕ примери за решения Проблемите с интерполация и изглаждане най-често се разглеждат, когато е необходимо да се конструира един или друг сплайн от даден масив от точки на равнина. Интерполационните задачи изискват графиката на сплайн да преминава през точки, което налага m + 1 допълнителни условия (уравнения) върху неговите коефициенти. Останалите p - 1 условия (уравнения) за уникалната конструкция на сплайн най-често се определят под формата на стойности на долните производни на сплайн в краищата на разглеждания сегмент [a, 6] - граница ( край) условия. Възможността да избирате различни гранични условия ви позволява да конструирате сплайни с различни свойства. При задачи за изглаждане, сплайнът се конструира така, че неговата графика да минава близо до точките (i""Y"), * = 0, 1,..., t, а не през тях. Мярката за тази близост може да се дефинира по различни начини, което води до значително разнообразие от изглаждащи сплайни. Описаните възможности за избор при конструиране на сплайн функции не изчерпват цялото им многообразие. И ако първоначално се разглеждаха само частични полиномиални сплайн функции, тогава с разширяването на обхвата на техните приложения започнаха да се появяват сплайни, „залепени заедно“ от други елементарни функции. Интерполационни кубични сплайни Постановка на проблема с интерполацията Нека на сегмента [a, 6) е дадена решетка w. Конструирайте гладка функция на сегмента (a, 6], която приема определени стойности във възлите на мрежата o", т.е. Забележка: Формулираният проблем за интерполация се състои от възстановяване на гладка функция, посочена в таблица (фиг. 2). Ясно е, че такъв проблем има много различни решения. Чрез налагане на допълнителни условия на конструираната функция е възможно да се постигне необходимата уникалност свойства, например в случаите, когато стойностите на дадена функция /(x) се изчисляват в точки [a, 6] е свързано със значителни трудности и/или дадената функция /(x) не притежава необходима гладкост, е удобно да се използва друга функция, която ще апроксимира доста добре дадената функция и ще бъде лишена от нейните недостатъци във възлите на мрежата w с дадената функция f(x). Дефиниция на интерполиращ кубичен сплайн Интерполиращ кубичен сплайн S(x) върху мрежа w е функция, която 1) във всеки от сегментите е полином от трета степен, 2) е два пъти непрекъснато диференцируема в сегмента [a, b ], т.е. принадлежи към клас C2[ a, 6], и 3) удовлетворява условията На всеки от сегментите сплайнът S(x) е полином от трета степен и се определя на този сегмент от четири коефициента. . Общият брой сегменти е m. Това означава, че за да се дефинира напълно сплайнът, е необходимо да се намерят 4m числа. Условието означава непрекъснатост на функцията S(x) и нейните производни S"(x) и 5". (x) във всички вътрешни възли на мрежата w. Броят на тези възли е m - 1. По този начин, за да се намерят коефициентите на всички полиноми, се получават още 3 (m - 1) условия (уравнения). Заедно с условията (2) се получават условия (уравнения). Гранични (крайни) условия Две липсващи условия са посочени под формата на ограничения върху стойностите на сплайн и/или неговите производни в краищата на интервала [a, 6]. При конструирането на интерполиращ кубичен сплайн най-често се използват следните четири вида гранични условия. А. Гранични състояния от 1-ви тип. - в краищата на интервала [a, b] се посочват стойностите на първата производна на желаната функция. Б. Гранични условия от 2-ри тип. - в краищата на интервала (a, 6) се посочват стойностите на втората производна на желаната функция. Б. Гранични състояния от 3-ти тип. се наричат периодични. Естествено е да се изисква изпълнението на тези условия в случаите, когато интерполираната функция е периодична с период T = b-a. D. Гранични състояния от 4-ти тип. изискват специален коментар. Коментар. Във вътрешните сепси възли третата производна на функцията S(x), най-общо казано, е прекъсната. Въпреки това, броят на прекъсванията на третата производна може да бъде намален с помощта на условия от 4-ти тип. В този случай построеният сплайн ще бъде непрекъснато диференцируем три пъти на интервали. Построяване на интерполиращ кубичен сплайн. Нека опишем метод за изчисляване на коефициентите на кубичен сплайн, при който броят на величините, които трябва да се определят, е равен. На всеки от интервалите се търси интерполационната сплайн функция в следната форма. Тук примерите на СПЛАЙНОВА ТЕОРИЯ за решения и числа са решението на система от линейни алгебрични уравнения, чиято форма зависи от вида на граничните условия. За гранични условия от типове 1 и 2 тази система има следната форма, където коефициентите зависят от избора на гранични условия. Гранични условия от 1-ви тип: Гранични условия от 2-ри тип: При гранични условия от 3-ти тип системата за определяне на числата се записва по следния начин: Броят на неизвестните в последната система е равен на mn, тъй като тя от условията за периодичност следва, че po = nm. За гранични условия от 4-ти тип системата за определяне на числата има формата където Въз основа на намереното решение на системата числата po и n могат да бъдат определени с помощта на формули. Матриците и на трите линейни алгебрични системи са диагонално доминиращи матрици. Матриците не са единични и следователно всяка от тези системи има уникално решение. Теорема. Интерполиращ кубичен сплайн, който отговаря на условия (2) и гранично условие от един от четирите типа, изброени по-горе, съществува и е уникален. По този начин, да се конструира интерполиращ кубичен сплайн означава да се намерят неговите коефициенти. Когато се намерят коефициентите на сплайн, стойността на сплайн S(x) в произволна точка от сегмента [a, b] може да се намери с помощта на формула (3). . За практически изчисления обаче следният алгоритъм за намиране на стойността 5(g) е по-подходящ. Нека x 6 [x", Първо, стойностите на A и B се изчисляват с помощта на формулите и след това се намира стойността 5(x): Използването на този алгоритъм значително намалява изчислителните разходи за определяне на стойността. Съвети за потребителят Изборът на гранични (крайни) условия и интерполационни възли ви позволява да контролирате до известна степен свойствата на интерполационните сплайнове. A. Избор на гранични (крайни) условия. Изборът на гранични условия е един от централните проблеми при интерполирането на функции. Това става особено важно в случай, че е необходимо да се осигури висока точност на апроксимация на функцията f (x) чрез сплайн 5 (g) близо до краищата на сегмента [a, 6). Граничните стойности имат забележим ефект върху поведението на сплайн 5(g) близо до точки a и b и това влияние бързо отслабва, когато човек се отдалечи от тях. Изборът на гранични условия често се определя от наличието на допълнителна информация за поведението на апроксимираната функция f(x). Ако стойностите на първата производна f"(x) са известни в краищата на сегмента (a, 6), тогава е естествено да се използват гранични условия от 1-ви тип. Ако стойностите на втората производна f"(x) са известни в краищата на сегмента [a, 6], тогава това са естествени гранични условия на използване от тип 2. Ако има избор между гранични условия от тип 1 и 2, тогава трябва да се даде предпочитание на условия от тип 1. Ако f(x) е периодична функция, тогава трябва да спрем на гранични условия от тип 3. Ако няма допълнителна информация за поведението на апроксимираната функция, често се използват така наречените естествени гранични условия, но трябва да се има предвид, че при такъв избор на гранични условия точността на апроксимация на функцията f(. x) от сплайн S(x) близо до краищата на сегмента (a, ft] рязко намалява. Понякога се използват гранични условия от 1-ви или 2-ри тип, но не с точните стойности на съответните производни, а с техните разликата в апроксимациите е ниска. Практическият опит в изчисленията показва, че в разглежданата ситуация най-подходящ е граничните условия от 4-ти тип. Б. Избор на интерполационни възли. Ако третата производна f""(x) на функцията има прекъсване в някои точки от сегмента [a, b], тогава за подобряване на качеството на апроксимацията тези точки трябва да бъдат включени в броя на интерполационните възли. Ако втората производна /"(x) е прекъсната, тогава, за да се избегне колебание на сплайн близо до точките на прекъсване, е необходимо да се вземат специални мерки. Обикновено възлите на интерполация се избират така, че точките на прекъсване на втората производна да падат вътре в интервала \xif), така че стойността a може да бъде избрана чрез числен експеримент (често е достатъчно да се зададе a = 0,01). (x) е прекъснат. Като един от най-простите можем да предложим следното: разделете апроксимационния сегмент на интервали, където производната е непрекъсната, и конструирайте сплайн на всеки от тези интервали. Избор на функция за интерполация (за и против) Подход 1. Интерполационен полином на Лагранж За дадена матрица SPLINE THEORY примери за решения (фиг. 3), интерполационният полином на Лагранж се определя от формулата Препоръчително е свойствата на интерполационния полином на Лагранж да се разглеждат от две противоположни позиции, като се обсъждат основните предимства отделно от недостатъците. Основните предимства на първия подход: 1) графиката на интерполационния полином на Лагранж преминава през всяка точка от масива, 2) построената функция се описва лесно (броят на коефициентите на интерполационния полином на Лагранж върху мрежата, който трябва да се определи, е равно на m + 1), 3) конструираната функция има непрекъснати производни от всякакъв ред, 4) интерполационният полином се определя еднозначно от дадения масив. Основните недостатъци на първия подход: 1) степента на интерполационния полином на Лагранж зависи от броя на възлите на мрежата и колкото по-голям е този брой, толкова по-висока е степента на интерполационния полином и следователно, колкото повече изчисления са необходими, 2) промяната на поне една точка в масива изисква пълно преизчисляване на коефициентите на интерполационния полином на Лагранж, 3) добавянето на нова точка към масива увеличава степента на интерполационния полином на Лагранж с единица и също така води до пълно преизчисляване на неговите коефициенти , 4) с неограничено усъвършенстване на мрежата, степента на интерполационния полином на Лагранж нараства неограничено. Поведението на интерполационния полином на Лагранж с неограничено уточняване на мрежата обикновено изисква специално внимание. Коментари А. За апроксимацията на непрекъсната функция с полином. Известно е (Weierstrass, 1885), че всяка непрекъсната (и още повече гладка) функция на интервал може да бъде апроксимирана, както и желано, на този интервал чрез полином. Нека опишем този факт на езика на формулите. Нека f(x) е функция, непрекъсната в интервала [a, 6]. Тогава за всяко e > 0 има полином Р(x) такъв, че за всяко x от интервала [a, 6] неравенството ще бъде изпълнено (Фиг. 4) Забележете, че полиноми от същата степен, които апроксимират функцията f(x) с определената точност, има безкрайно много. Нека построим решетка w на отсечката [a, 6]. Ясно е, че неговите възли, най-общо казано, не съвпадат с пресечните точки на графиките на полинома Pn(x) и функцията f(x) (фиг. 5). Следователно за дадената мрежа полиномът Pn(x) не е интерполация. Когато една непрекъсната функция се апроксимира чрез интерполиращ полином на Jla-gracz, нейната графика не само не трябва да е близо до графиката на функцията f(x) във всяка точка от сегмента [a, b), но може да се отклонява от тази функция колкото желаете. Нека дадем два примера. Пример 1 (Rung, 1901). При неограничено нарастване на броя на възлите за функцията на интервала [-1, 1], граничното равенство е изпълнено (фиг. 6) Пример 2 (Beristein, 1912). Последователност от интерполационни полиноми на Лагранж, конструирани върху равномерни мрежи за непрекъснатата функция /(x) = |x| на сегмент с нарастващ брой възли m не клони към функцията /(x) (фиг. 7). Подход 2. Частично линейна интерполация Ако гладкостта на интерполираната функция бъде изоставена, съотношението между броя на предимствата и броя на недостатъците може да бъде значително променено към първото. Нека да построим линейна линейна функция чрез последователно свързване на точки (xit y) с прави сегменти (фиг. 8). Основните предимства на втория подход: 1) графиката на частично линейна функция преминава през всяка точка от масива, 2) построената функция се описва лесно (броят на коефициентите на съответните линейни функции, които трябва да се определят за мрежата ( 1) е 2m), 3) конструираната функция е дефинирана от дадения масив уникално, 4) степента на полиномите, използвани за описание на интерполационната функция, не зависи от броя на възлите на мрежата (равен на 1), 5) промяна една точка в масива изисква изчисляване на четири числа (коефициенти на две прави връзки, произтичащи от новата точка), 6) добавянето добавяне на допълнителна точка към масива изисква изчисляване на четири коефициента. Частично линейната функция също се държи доста добре при прецизиране на мрежата. Основният недостатък на втория подход: апроксимиращата частично линейна функция не е гладка: първите производни страдат от прекъсване във възлите на мрежата (интерполационни уши). Подход 3. Сплайн интерполация Предложените подходи могат да се комбинират така, че броят на изброените предимства на двата подхода да се запази, като същевременно се намали броят на недостатъците. Това може да се направи чрез конструиране на гладка интерполационна сплайн функция със степен p. Основните предимства на третия подход: 1) графиката на построената функция минава през всяка точка от масива, 2) построената функция е сравнително лесна за описване (броят на коефициентите на съответните полиноми, които трябва да бъдат определени за мрежата ( 1) е равно на 3) конструираната функция е уникално дефинирана от дадения масив, 4) полиномите на степента не зависят от броя на възлите на мрежата и следователно не се променят с нарастването си, 5) конструираната функция има непрекъсната производни до ред p - 1 включително, 6) построената функция има добри апроксимационни свойства. Кратка информация. Предложеното наименование - сплайн - не е случайно - въведените от нас гладки късови полиномиални функции и чертането на сплайнове са тясно свързани. Нека разгледаме гъвкава идеално тънка линийка, минаваща през референтните точки на масива, разположени в равнината (x, y). Съгласно закона на Бернули-Ойлер, линеаризираното уравнение на извита линийка има формата, където S(x) е огъването, M(x) е огъващият момент, който варира линейно от опора до опора, E1 е твърдостта на линийката . Функцията S(x), която описва формулните линии, е полином от трета степен между всяка и две съседни точки от масива (опори) и е два пъти непрекъснато диференцируема по целия интервал (a, 6). Коментар. 06 интерполиране на непрекъсната функция За разлика от интерполиращите полиноми на Лагранж, последователност от интерполиращи кубични сплайнове върху равномерна мрежа винаги се сближава с интерполиращата непрекъсната функция и с подобряването на диференциалните свойства на тази функция скоростта на сближаване се увеличава. Пример. За функция, кубичен сплайн върху решетка с брой възли m = 6 дава грешка на приближаване от същия порядък като интерполационния полином Ls(z), а върху решетка с брой възли m = 21 тази грешка е толкова малък, че в мащаба на обикновена рисунка на книга просто не може да бъде показан (фиг. 10) (интерполационният полином 1>2o(r) дава в този случай грешка от около 10 000 J). Свойства на интерполационен кубичен сплайн A. Алпроксимационни свойства на кубичен сплайн. Апроксимационните свойства на интерполационния сплайн зависят от гладкостта на функцията f(x) - колкото по-висока е гладкостта на интерполираната функция, толкова по-висок е редът на апроксимация и, при прецизиране на мрежата, толкова по-висока е скоростта на конвергенция. Ако интерполираната функция f(x) е непрекъсната в интервала. Ако интерполираната функция f(x) има непрекъсната първа производна в интервала [a, 6], т.е. интерполационен сплайн, който удовлетворява граничните условия на 1-ви или 3-ти тип, тогава за h O имаме В този случай не само сплайнът се сближава към интерполираната функция, но и производната на сплайна се сближава с производната на тази функция. Ако сплайнът S(x) апроксимира функцията f(x) на отсечката [a, b], а нейните първа и втора производна съответно апроксимират функция B. Екстремално свойство на кубичен сплайн. Интерполиращият кубичен сплайн има още едно полезно свойство. Помислете за следния пример. пример. Конструирайте функция /(x), която минимизира функционала върху клас функции от пространството C2, чиито графики минават през точките на масива сред всички функции, минаващи през референтните точки (x;, /(x,. )) и принадлежащ към определеното пространство, това е кубичният сплайн 5( x), удовлетворяващ граничните условия, предоставя екстремум (минимум) на функционала. Забележка 1. Често това екстремално свойство се приема като дефиниция на интерполираща кубика сплайн. Забележка 2. Интересно е да се отбележи, че интерполиращият кубичен сплайн притежава екстремното свойство, описано по-горе, върху много широк клас функции, а именно класа |o, 5]. 1.2. Изглаждане на кубични сплайни За формулирането на проблема за изглаждане Нека са дадени решетка и набор от числа Коментар на първоначалните данни На практика често се налага да се справяте със случая, когато стойностите на y в масива са определени с някои грешка. Всъщност това означава, че за всеки е определен интервал и всяко число от този интервал може да бъде взето като стойност на y, . Удобно е да се интерпретират стойностите на y, например, като резултати от измервания на някаква функция y(x) за дадени стойности на променливата x, съдържаща случайна грешка. Когато решавате проблема с възстановяването на функция от такива „експериментални“ стойности, едва ли е препоръчително да използвате интерполация, тъй като интерполационната функция послушно ще възпроизведе странни колебания, причинени от случаен компонент в масива (y,). По-естественият подход се основава на процедура за изглаждане, предназначена да намали по някакъв начин елемента на случайност в резултатите от измерването. Обикновено при такива задачи се изисква да се намери функция, чиито стойности за x = x, * = 0, 1,... m биха попаднали в подходящите интервали и които освен това биха имали доста добри свойства. Например, той ще има непрекъснати първа и втора производни или графиката му няма да е твърде силно извита, тоест няма да има силни колебания. Проблем от този вид възниква и когато по даден (точно) масив е необходимо да се конструира функция, която не минава през дадени точки, а близо до тях и освен това се променя доста плавно. С други думи, изискваната функция изглежда изглажда дадения масив, вместо да го интерполира. Нека са дадени решетка w и два набора от числа ТЕОРИЯ НА СПЛАЙНОВЕ Примери за решение на задачата. Конструирайте гладка функция на сегмента [a, A], чиито стойности във възлите на мрежата u се различават от числата y с дадените стойности. Формулираният проблем за изглаждане ереставрация гладка функция, посочена в таблица. Ясно е, че такъв проблем има много различни решения. Чрез налагането на допълнителни условия върху конструираната функция може да се постигне необходимата еднозначност. Дефиниция на изглаждащ кубичен сплайн Изглаждащ кубичен сплайн S(x) върху решетка w е функция, която 1) на всеки от сегментите е полином от трета степен, 2) е два пъти непрекъснато диференцируема на сегмента [a, 6 ], тоест принадлежи към клас C2 [a , b], 3) доставя минимум на функционала, където са дадените числа, 4) удовлетворява граничните условия на един от трите вида, посочени по-долу. Гранични (крайни) условия Граничните условия са посочени под формата на ограничения върху стойностите на сплайн и неговите производни в граничните възли на мрежата w. А. Тип 1 гранични условия. - в краищата на интервала [a, b) са посочени стойностите на първата производна на желаната функция. Тип 2 гранични условия. - вторите производни на търсената функция в краищата на интервала (a, b] са равни на нула. B. Граничните условия от 3-ти тип се наричат периодични. Теорема. Кубичен сплайн S(x), минимизиращ функционал (4) и отговарящ на граничните условия на един от горните три типа, е уникално дефиниран. Кубичен сплайн, който минимизира функционала J(f) и удовлетворява граничните условия на i-типа, се нарича изглаждащ сплайн на i-типа. Забележка. Общият брой на отсечките е m производни във всички вътрешни възли на мрежата o ". Броят на такива възли е m - 1. Така, за да изчислим коефициентите на всички полиноми, получаваме 3 (m - 1) условия (уравнения). функцията се търси в Тук числата и са решението на система от линейни алгебрични уравнения, чиято форма зависи от вида на граничните условия. Нека първо опишем как се намират стойностите n*. За гранични условия от 1-ви и 2-ри тип системата от линейни уравнения за определяне на стойностите на Hi е написана в следната форма, където са известни числа). Коефициентите зависят от избора на гранични условия. Гранични условия от 1-ви тип: Гранични условия от 2-ри тип: В случай на гранични условия от 3-ти тип, системата за определяне на числата се записва, както следва: и всички коефициенти се изчисляват по формули (5) (стойности с индекси k и m + k се считат за равни: Важна* забележка. Матриците на системите не са изродени и следователно всяка от тези системи има уникално решение. Ако числата n, - са намерени, тогава количествата се определят лесно по формулите, където В случай на периодични гранични условия, изборът на неговите коефициенти Изборът на коефициентите на тегло p, - включени във функционала (4), ви позволява да контролирате свойствата на изглаждащите сплайнове до известна степен. Ако всичко и изглаждащият сплайн се окаже интерполация. Това по-специално означава, че колкото по-точно са посочени стойностите, толкова по-малки се очаква да бъдат съответните тегловни коефициенти. Ако е необходимо сплайнът да премине през точката (x^, Vk), тогава съответстващият му тегловен коефициент p\ трябва да бъде равен на нула. При практическите изчисления най-важното е изборът на стойности pi-Нека D, - грешката при измерване на стойността y,. Тогава е естествено да се изисква изглаждащият сплайн да отговаря на условието или, което е същото, в най-простия случай тегловните коефициенти pi могат да бъдат зададени, например, във формата - където c е някаква достатъчно малка константа. Въпреки това, този избор на тегла p не позволява използването на „коридор“ поради грешки в стойностите y, -. По-рационален, но и по-трудоемък алгоритъм за определяне на стойностите на p може да изглежда така. Ако стойностите са намерени на fc-тата итерация, тогава се приема, че където e е малко число, което е избрано експериментално, като се вземат предвид битовата мрежа на компютъра, стойностите на D и точността на решаване на система от линейни алгебрични уравнения. Ако при fc-тата итерация в точка i условието (6) е нарушено, тогава последната формула ще осигури намаляване на съответния коефициент на тежест p,. Ако след това при следващата итерация, увеличаването на p води до по-пълно използване на „коридора“ (6) и в крайна сметка до по-плавно променящ се сплайн. Малко теория А. Обосновка на формули за изчисляване на коефициентите на интерполационен кубичен сплайн. Нека въведем обозначението, където m са неизвестни в момента количества. Техният брой е равен на m + 1. Сплайн, записан във формата където, удовлетворява условията за интерполация и е непрекъснат на целия интервал [a, b\: като го поставим във формулата, получаваме освен това, че има a непрекъсната първа производна на интервала [a, 6]: Чрез диференциране на връзката (7) и поставянето й получаваме съответния всъщност. Нека покажем, че числата m могат да бъдат избрани така, че сплайн функцията (7) да има непрекъсната втора производна на интервала [a, 6]. Нека изчислим втората производна на сплайна на интервала: В точката x, - 0 (при t = 1) имаме. Нека изчислим втората производна на сплайна на интервала В точката имаме От условието за непрекъснатост на втора производна във вътрешните възли на мрежата a; получаваме m - 1 връзка, където Добавяйки към тези m - 1 уравнения още две, които следват от граничните условия, получаваме система от m + 1 линейни алгебрични уравнения с m + I неизвестно miy i = 0, 1. ... , м. Системата от уравнения за изчисляване на стойностите на rsh в случай на гранични условия от 1-ви и 2-ри тип има формата където (гранични условия от 1-ви тип), (гранични условия от 2-ри тип). За периодични гранични условия (гранични условия от тип 3), мрежата o; разширете с още един възел и приемете, че тогава системата за определяне на стойностите на σ* ще има формата непрекъснатост във втория и (th - !)-ия възел на мрежата. Имаме. От последните две отношения получаваме липсващите две уравнения, които съответстват на граничните условия от 4-ти тип: Елиминирайки неизвестното goo от уравненията и неизвестното pc от уравненията, в резултат получаваме система от уравнения. Обърнете внимание, че броят на неизвестните в тази система е th - I. 6. Обосновка на формулите за изчисляване на ефективността на изглаждащ субшахматен сплайн. Нека въведем обозначението, където Zi и nj са неизвестни величини в момента. Техният брой е 2m + 2. Сплайн функцията, записана във формата, е непрекъсната през целия интервал 8), има непрекъсната първа производна на интервала [a, 6]. Нека изчислим първата производна на сплайна S(x) на интервала: В точката x^ - 0 (при t = 1) имаме Нека изчислим първата производна на сплайна 5(x) на интервала: В точката имаме От условието за непрекъснатост на първата производна на сплайн във вътрешните възли на мрежата и --> получаваме връзката m - 1, която е удобно записана в матрична форма. В допълнение се използва следната нотация на интервала. има непрекъсната втора производна: диференцирайки връзката (8) и поставяйки я, получаваме, съответно, матричната връзка се получава от условието за минимум на функционала (4). Имаме Последните две матрични равенства могат да се разглеждат като линейна система от 2m + 2 линейни алгебрични уравнения за 2m + 2 неизвестни. Заменяйки колона r в първото равенство с нейния израз, получен от съотношението (9), стигаме до матричното уравнение СПЛАЙНОВА ТЕОРИЯ примери за решения за определяне на колона М. Това уравнение има уникално решение поради факта, че матрицата A + 6HRH7 е винаги неизродени. След като го намерихме, можем лесно да идентифицираме град Eamsshine. Елементите на нишковидните матрици A и H се определят само от параметрите на мрежата и (със стъпки hi) и не зависят от стойностите на y^. Линейно пространство на кубични сплайн функции Множеството от кубични сплайнове, конструирани върху сегмента [a, 6) по дължината на мрежата wcra+l възел е линейно пространство с размерност m + 3: 1) сумата от два кубични сплайна, конструирани върху мрежата u > и произведението на кубичен сплайн, конструиран върху решетка и>, с произволен брой по-тайно, са кубични сплайни, конструирани върху тази решетка, 2) всеки кубичен сплайн, конструиран върху решетка и от възел, се определя напълно от m + 1 стойност на стойностите y" в тези възли и две гранични условия - само + 3 параметъра. Като изберем база в това пространство, състояща се от m + 3 линейно независими сплайна, можем да напишем произволен кубичен сплайн a(x) като линейна комбинация от тях по уникален начин. Коментирайте. Този тип присвояване на сплайн е широко разпространен в компютърната практика. Особено удобна е база данни, състояща се от така наречените кубични B-сплайнове (основни или фундаментални сплайнове). Използването на D-сплайнове може значително да намали изискванията за компютърна памет. L-сплайнове. B-сплайн от нулева степен, конструиран върху числовата права по протежение на мрежата w, се нарича B-сплайн със степен k ^ I, конструиран върху числовата права по протежение на мрежата u, се определя с помощта на рекурента. формула Графиките на B-сплайнове от първата B, -1 "(g) и втората в\7\x) степени са представени съответно на Фиг. 11 и 12. B-сплайн с произволна степен k може да бъде различен от нула само на определен сегмент (дефиниран от k + 2 възли) По-удобно е да се номерират кубични B-сплайнове, така че сплайнът B, -3* (π) да е различен от нула на сегмента r, -+2]. Представяме формулата за кубичен сплайн от трета степен за случай на равномерна мрежа (със стъпка A). В други случаи имаме типична графика на кубичен B-сплайн заемайки*, функцията a) е два пъти непрекъснато диференцируема на интервала, т.е. принадлежи към клас C2 [a, "), k b) е различна от нула само на четири последователни интервала (Нека допълним мрежата w с помощни възли взето напълно произволно чрез разширена мрежа w*, можем да конструираме семейство от m + 3 кубични B-сплайна: Това семейство формира основа в пространството на кубичните сплайнове на сегмента (a, b]. По този начин, произволен кубичен сплайн S(z), конструиран върху сегмента |b, 6] мрежа o; izm+1 възел, могат да бъдат представени на този сегмент под формата на линейна комбинация. По условията на задачата коефициентите ft на това разширение се определят еднозначно. ... В случая, когато са дадени стойностите y* на функцията в възлите на мрежата и стойностите y o и Ym на първата производна на функцията в краищата на мрежата (проблемът с интерполацията с граница условия от първи вид), тези коефициенти се изчисляват от системата от следния вид След елиминиране на стойностите b- i и &m+i се получава линейна система с неизвестните 5q, ..., bm и три -дименсионална матрица осигурява диагонална доминация и, следователно, възможността за използване на метода на почистване 3MMCMY 1. Линейни системи от подобен тип възникват при разглеждане на други проблеми на интерполацията. В сравнение с алгоритмите, описани в раздел 1.1, използването на R-сплайн в * интерполационни проблеми ни позволява да намалим * количеството съхранена информация, т.е. значително да намалим изискванията за компютърна памет, въпреки че води до увеличаване на броя на операциите. Конструиране на сплайнови криви с помощта на сплайнови функции По-горе разгледахме масиви, чиито точки бяха номерирани така, че техните абциси образуват строго нарастваща последователност. Например случаят, показан на фиг. 14, когато различни точки от масива имат една и съща абциса, не се допуска. Това обстоятелство определи както избора на клас апроксимиращи криви (трафик функции), така и метода на тяхното конструиране. Предложеният по-горе метод обаче позволява доста успешно да се изгради интерполационна крива в по-общия случай, когато номерирането на точките на масива и тяхното местоположение в равнината по правило не са свързани (фиг. 15). Освен това, когато поставяме задачата за изграждане на интерполационна крива, можем да считаме дадения масив за неравнинен, т.е. ясно е, че за решаването на този общ проблем е необходимо значително да се разшири класът на допустимите криви, включително затворени криви, криви със самопресечни точки и пространствени криви. Удобно е да се опишат такива криви с помощта на параметрични уравнения. освен това функциите трябва да имат достатъчна гладкост, например те принадлежат към класа C1 [a, /0] или класа. За да намерите параметричните уравнения на крива, която последователно преминава през всички точки на масива, процедирайте по следния начин. 1-ва стъпка. На произволно взет сегмент се извършва по трите най-близки точки.
Кубична сплайн интерполация
През последните години интензивно се развива нов клон на съвременната изчислителна математика - теорията шлици.Сплайновете позволяват ефективно решаване на проблеми с обработката на експериментални зависимости между параметри, които имат доста сложна структура.
Методите за локална интерполация, обсъдени по-горе, са по същество най-простият сплайн от първа степен (за линейна интерполация) и втора степен (за квадратична интерполация).
Поради своята простота, кубичните сплайни са намерили най-широко практическо приложение. Основните идеи на теорията на кубичните сплайни се формират в резултат на опитите за математическо описание на гъвкави ламели, изработени от еластичен материал (механични сплайни), които отдавна се използват от чертожниците в случаите, когато е необходимо да се начертае доста гладка крива през дадени точки. Известно е, че лента от еластичен материал, фиксирана в определени точки и в равновесно положение, приема форма, при която нейната енергия е минимална. Това фундаментално свойство прави възможно ефективното използване на сплайни при решаване на практически проблеми за обработка на експериментална информация.
Като цяло за функцията y = f(х) се изисква да се намери приближение y=j(х) По начина, по който f(x i)= j(x i) в точки х = х i, a в други точки на отсечката [ а, б] стойности
функции f(х) И й(х) бяха близо един до друг. При малък брой експериментални точки (например 6-8) един от методите за конструиране на интерполационни полиноми може да се използва за решаване на проблема с интерполацията. Въпреки това, с голям брой възли, интерполационните полиноми стават практически неизползваеми. Това се дължи на факта, че степента на интерполационния полином е само една по-малка от броя на експерименталните стойности на функциите. Възможно е, разбира се, да се раздели сегментът, на който е дефинирана функцията, на секции, съдържащи малък брой експериментални точки, и за всяка от тях да се конструират интерполационни полиноми. В този случай обаче апроксимиращата функция ще има точки, в които производната не е непрекъсната, т.е. графиката на функцията ще съдържа точки на „прекъсване“.
Кубичните сплайни нямат този недостатък. Изследванията на теорията на лъча показват, че гъвкав тънък лъч между два възела е сравнително добре описан от кубичен полином и тъй като той не се свива, апроксимиращата функция трябва да бъде поне непрекъснато диференцируема. Това означава, че функциите й(х), j'(х), j"(х) трябва да бъде непрекъснат на сегмента [ а, б].
Кубичен интерполационен сплайн , съответстваща на тази функция f(х) и тези възли xi,наречена функция г(х), отговарящи на следните условия:
1. на всеки сегмент [ x i — 1 ,x i], i = 1, 2, ..., нфункция г(х) е полином от трета степен,
функция г(х), и също нейните първа и втора производни са непрекъснати на интервала [ а,б],
Кубичен сплайнсе слепва от полиноми от трета степен, които за аз- раздел са написани, както следва:
За целия интервал ще бъде съответно Пкубични полиноми, различни по коефициенти Ааз, b i, c i, d i. Най-често възлите по време на сплайн интерполация се поставят равномерно, т.е. хаз +1 -Хаз = конст = ч (въпреки че това не е необходимо).
Необходимо е да се намерят четири коефициента, при условие че всеки полином минава през две точки (x аз, г аз) и (x аз +1 , г аз +1 ) , което води до следните очевидни уравнения:
Първото условие съответства на преминаването на полинома през началната точка, второто - през крайната точка. Невъзможно е да се намерят всички коефициенти от тези уравнения, тъй като има по-малко условия от необходимите параметри. Следователно тези условия се допълват с условията за гладкост на функцията (т.е. непрекъснатост на първата производна) и гладкост на първата производна (т.е. непрекъснатост на втората производна) в интерполационните възли. Математически тези условия се записват като равенства съответно на първата и втората производни в края азта и в началото ( аз+1 )-ти парцели.
От , Че
(г’ (x i +1 ) накрая аз-парцел е равен на ти(хаз +1 ) първо ( аз+1 )-та),
(y"(хаз +1 ) накрая аз-парцел е равен на y" (xаз +1 ) първо ( аз+1)th).
Резултатът е система от линейни уравнения (за всички секции), съдържаща 4n - 2 уравнения с 4n неизвестни (неизвестни a 1, a 2,..., a n, b 1,..., d n - коефициенти на сплайн). За да разрешите системата, добавете две гранични условия от един от следните типове (най-често се използва 1):
Съвместното решение на 4n уравнения ви позволява да намерите всичките 4n коефициенти.
За да възстановите производните, можете да диференцирате съответния кубичен полином във всяка секция. Ако е необходимо да се определят производни във възли, има специални техники, които намаляват определянето на производни до решаване на по-проста система от уравнения за желаните производни от втори или първи ред. Важни предимства на кубичната сплайн интерполация включват получаване на функция, която има минималната възможна кривина. Недостатъците на сплайн интерполацията включват необходимостта от получаване на относително голям брой параметри.
Нека решим проблема с интерполацията с помощта на програмата MathCAD. За целта ще използваме вградената функция интерп(VS,x,y,z) . Променливи х И г задайте координатите на възловите точки, z е аргумент на функция, СРЕЩУ определя типа
гранични условия в краищата на интервала.
Нека дефинираме интерполационните функции за три типа кубичен сплайн
Тук cspline (VX , VY) връща вектор СРЕЩУвтори производни при приближаване на кубичен полином в референтни точки;
pspline(VX, VY) връща вектор СРЕЩУвтори производни при приближаване на референтни точки към параболична крива;
lspline(VX, VY) връща вектор СРЕЩУвтори производни при приближаване до референтните точки на линията;
интерп(СРЕЩУ, VX, VY, х) връща стойност г(х) за дадени вектори СРЕЩУ, VX, VYи зададена стойност х.
Ние изчисляваме стойностите на интерполационните функции в дадени точки и сравняваме резултатите с точните стойности
Моля, имайте предвид, че резултатите от интерполацията от различни видове кубични сплайни са практически еднакви във вътрешните точки на интервала и съвпадат с точните стойности на функцията. Близо до краищата на интервала разликата става по-забележима и когато се екстраполира отвъд даден интервал, различните видове сплайнове дават значително различни резултати. За по-голяма яснота нека представим резултатите на графика (фиг. 3.5)
Ориз. 3.5 Кубична сплайн интерполация
Ако функцията е посочена дискретно, тогава за интерполация се посочват матрици с данни.
При глобалната интерполация най-често се използва полиномна интерполация. н-та степен или интерполация на Лагранж.
Класическият подход се основава на изискването за строго съответствие на стойностите f(х) И й(х) в точки x i(аз = 0, 1, 2, … н).
Ще търсим интерполационната функция й(х) под формата на полином от степен н.
Този полином има n+ 1 коефициент. Естествено е да се предположи, че n+ 1 условия
й(х 0) = г 0 , й(х 1) = г 1 , . . ., й(x n) = y n (3.4)
насложен върху полинома
дават възможност за недвусмислено определяне на неговите коефициенти. Наистина взискателни за й(х) изпълнение на условията (3.4) , получаваме система n+ 1 уравнения с n+ 1 неизвестен:
(3.6)
Решаване на тази система за неизвестни а 0 , а 1 , …, a nполучаваме аналитичен израз за полинома (3.5). Система (3.6) винаги има уникално решение , защото неговата детерминанта
известен в алгебрата като Детерминант Вандермондненулев . това предполага , че интерполационният полином й(х) за функция f(х), дадено в таблица, съществува и е уникално.
Полученото уравнение на кривата минава точно през дадените точки. Извън възлите на интерполация математическият модел може да има значителна грешка
Интерполационна формула на Лагранж
Нека стойностите на някаква функция са известни f(Х) V n+ 1 различни произволни точки y i = f(x i) , аз = 0,…, П.За интерполиране (възстановяване) на функция във всяка точка Х,принадлежащ на сегмента [ x 0, x n], необходимо е да се конструира интерполационен полином от n-ти ред, който в метода на Лагранж се представя по следния начин:
Освен това е лесно да се забележи това Qj(x i) = 0, Ако аз¹ й, И Qj(x i) =1, Ако аз= й. Ако разширим произведението на всички скоби в числителя (в знаменателя всички скоби са числа), получаваме полином от n-ти ред в Х,тъй като числителят съдържа n фактора от първи ред. Следователно, интерполационният полином на Лагранж не е нищо повече от обикновен полином от n-ти ред, въпреки специфичната форма на нотация.
Оценете интерполационната грешка в точка хот [ х 0, хн] (т.е. решете второто
интерполационен проблем) може да се направи с помощта на формулата
Във формулата - максимална стойност на (n+1)-та производна на оригиналната функция f(Х)на сегмента [ х 0, хн].
Следователно, за да се оцени грешката на интерполацията, е необходима допълнителна информация за оригиналната функция (това трябва да е разбираемо, тъй като безкраен брой различни функции могат да преминат през дадени начални точки, за които грешката ще бъде различна). Такава информация е производната от порядък n+1, която не е толкова лесна за намиране. По-долу ще покажем как да излезем от тази ситуация. Отбележете също, че прилагането на формулата за грешка е възможно само ако функцията е диференцируема n +1 пъти.
За изграждане Интерполационна формула на Лагранжв MathCAD е удобно да се използва функцията ако.
ако (условие, x, y)
Връща стойността на x, ако cond не е 0 (true). Връща стойността на y, ако cond е 0 (false) (Фигура 3.6).