МИНИСТЕРСТВО НА ОБРАЗОВАНИЕТО И НАУКАТА НА РУСКАТА ФЕДЕРАЦИЯ

Федерална държавна автономна образователна институция

висше професионално образование

"Уралски федерален университет на името на първия президент на Русия Б. Н. Елцин"

Институт по радиоелектроника и информационни технологии – РТФ

отдел Автоматизация и информационни технологии

Сплайн интерполация

МЕТОДОЛОГИЧЕСКИ УКАЗАНИЯ за лабораторна работа ПО ДИСЦИПЛИНАТА " Числени методи»

Съставител: I.A. Селиванова, старши преподавател.

СПЛАЙН ИНТЕРПОЛАЦИЯ:Указания за практически упражнения по дисциплината "Числени методи"

Указанията са предназначени за студенти от всички форми на обучение в направление 230100 - "Информатика и компютърна техника".

Ó FSAEI HPE "UrFU на името на първия президент на Русия Б. Н. Елцин", 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] непрекъсната сплайн функция С(х), който отговаря на следните условия:

За да конструирате желания сплайн, трябва да намерите коефициентите
полиноми
,аз=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) намираме коефициентите на кубичните сплайни.

1. Разгледайте първите гранични условия.

В нашия случай н=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):

Нека направим таблица:

	(1 кр. състояние.)	(2 кр. условия)	(3 кр. условия)

Основната задача интерполация- намиране на стойността на таблична функция в тези точки в даден интервал, където тя не е посочена. Първоначалните таблични данни могат да бъдат получени както експериментално (в този случай по същество няма междинни данни без допълнителна работа), така и чрез изчисление с помощта на сложни зависимости (в този случай намерете стойността чрез интерполация сложна функцияе по-лесно от директното изчисление с помощта на сложна формула)

Понятие за интерполация

Решаването на проблемите с интерполацията и екстраполацията се осигурява от конструкцията на интерполационната функция Л(х), приблизително замествайки оригинала f(х), дадено в таблица и преминаващо през всички дадени точки - интерполационни възли.Използвайки тази функция, можете да изчислите желаната стойност на оригиналната функция във всяка точка.

Във връзка с интерполацията се разглеждат три основни проблема.

1) избор на интерполационна функция Л(х);

2) оценка на интерполационната грешка Р(х);

3) поставяне на интерполационни възли, за да се осигури възможно най-висока точност на възстановяването на функцията ( х 1 , х 2 ,…,x n).

Специалните методи за интерполация ви позволяват да определите желаната стойност на функцията без директно конструиране на интерполационната функция. По принцип всички методи на интерполация, базирани на използването на полиноми като интерполационна функция, дават едни и същи резултати, но с различни разходи. Това е така, защото полиномът нта степен, съдържаща н+1 параметър и преминаване през всички дадени н+1 точки, - единственият. В допълнение, полиномът може да бъде представен като пресечена серия на Тейлър, в която оригиналната диференцируема функция е разширена. Това е може би едно от основните предимства на полинома като интерполационна функция. Следователно по-често първият проблем на интерполацията се решава чрез избор на полином като интерполационна функция, въпреки че могат да се използват и други функции (например тригонометрични полиноми, други функции, избрани от неформалните условия на смислен проблем).

Ориз. 3.2 Илюстрация на интерполация

Изборът на типа на интерполационната функция обикновено е важна задача, особено ако помните, че произволен брой функции могат да бъдат начертани през дадени точки (фиг. 3.2). Трябва да се отбележи, че има очевиден начин за конструиране на интерполационна функция: от условието, че функцията преминава през всички точки, се съставя система от уравнения, от чието решение се намират нейните параметри. Този път обаче далеч не е най-ефективният, особено при голям брой точки.

Прието е да се прави разлика между локална и глобална интерполация. В случай, че полиномът е един и същ за цялата интерполационна област, казваме, че интерполацията глобален. В случаите, когато полиномите са различни между различните възли, се говори за на части или локална интерполация.

Линейна интерполация

Най-простата и най-често използвана форма на локална интерполация е линейна интерполация.Състои се в това, че дадените точки М(x i, y i) (аз = 0, 1, …,н) са свързани с прави сегменти и функцията f(х) се доближава до полилиния с върхове в тези точки (фиг. 3.3) .

Ориз. 3.3 Линейна интерполация

Уравненията на всеки сегмент от прекъсната линия обикновено са различни. Тъй като има нинтервали (x i , x i + 1), след това за всяко от тях като уравнение

Интерполационният полином използва уравнението на права линия, минаваща през две точки. По-специално, за аз -интервал, можем да напишем уравнението на права линия, минаваща през точките ( x i, y i) И ( x i + 1 , y i + 1), като:

(3.2)

Следователно, когато използвате линейна интерполация, първо трябва да определите интервала, в който попада стойността на аргумента х, и след това го заместете във формула (3.2) и намерете приблизителната стойност на функциите в тази точка.

Фигура 3.4 показва пример за използване на линейна интерполация в програмата MathCAD. За линейна интерполация се използва функцията linterp (х,г,z). Тук х, г- първоначални данни, z- точката, в която се намира стойността на функцията.

Ориз. 3.4. Линейна интерполация

Квадратична интерполация

Кога квадратична интерполациякато интерполационна функция върху сегмента ( x i — 1 ,x i + 1) вземете квадратен тричлен. Уравнението на квадратен трином има формата

y = a i x 2 + b i x + c i , x i — 1 х x i + 1 , (3.3)

Интерполация за всяка точка х [х 0 , x n] се начертава върху трите най-близки точки.

Кубична сплайн интерполация

IN последните годиниинтензивно се развива нов клон на съвременната изчислителна математика – теорията шлици.Сплайновете позволяват ефективно решаване на проблемите с обработката на експериментални зависимости между параметри, които имат доста сложна структура.

Методите за локална интерполация, обсъдени по-горе, са по същество най-простият сплайн от първа степен (за линейна интерполация) и втора степен (за квадратична интерполация).

Най-широкият практическа употреба, поради тяхната простота, откриха кубични сплайни. Основните идеи на теорията на кубичните сплайни се формират в резултат на опитите за математическо описание на гъвкави релси, изработени от еластичен материал (механични сплайни), които отдавна се използват от чертожниците в случаите, когато е необходимо да се начертае достатъчно гладка крива през дадени точки. Известно е, че релса, изработена от еластичен материал, фиксирана в определени точки и намираща се в равновесно положение, приема форма, при която нейната енергия е минимална. Това фундаментално свойство прави възможно ефективното използване на сплайни при решаване на практически проблеми за обработка на експериментална информация.

Общо взето за функция y=f(х) се изисква да се намери приближение y=j(х) По начина, по който f(x i)= j(x i) в точки х = х i, a в други точки на отсечката [ а, б] стойности

функции f(х) И й(х) бяха близо един до друг. С малък брой експериментални точки (например 6-8) един от методите за конструиране на интерполационни полиноми може да се използва за решаване на проблема с интерполацията. Въпреки това, с голям брой възли, интерполационните полиноми стават практически неизползваеми. Това се дължи на факта, че степента на интерполационния полином е само една по-малка от броя на експерименталните стойности на функциите. Възможно е, разбира се, да се раздели сегментът, на който е дефинирана функцията, на сегменти, съдържащи малък брой експериментални точки, и за всяка от тях да се конструират интерполационни полиноми. В този случай обаче апроксимиращата функция ще има точки, в които производната не е непрекъсната, т.е. графиката на функцията ще съдържа точки на „прекъсване“.

Кубичните сплайни нямат този недостатък. Изследванията на теорията на лъча показват, че гъвкав тънък лъч между два възела се описва доста добре от кубичен полином и тъй като той не се свива, апроксимиращата функция трябва да бъде поне непрекъснато диференцируема. Това означава, че функциите й(х), j'(х), j"(х) трябва да бъде непрекъснат на интервала [ а, б].

Кубичен интерполационен сплайн , подходящи за тази функция f(х) и дадени възли x i ,наречена функция г(х), отговарящи на следните условия:

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 )-та),

(при"(хаз +1 ) накрая аз-та секция е равна на y" (xаз +1 ) първо ( аз+1)-та).

Резултатът е система от линейни уравнения (за всички секции), съдържаща 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 , …, анполучаваме аналитичен израз за полинома (3.5). Система (3.6) винаги има уникално решение , защото неговата детерминанта

известен в алгебрата като детерминант Вандермонд,различен от нула . това предполага , какво е интерполационният полином й(х) за функцията f(х), дадено в таблица, съществува и е уникално.

Полученото уравнение на кривата минава точно през дадените точки. Извън възлите на интерполация математическият модел може да има значителна грешка

Интерполационна формула на Лагранж

Нека стойностите на някаква функция са известни f(Х) V n+ 1 различни произволни точки y i = f(x i) , аз = 0,…, П.За интерполиране (възстановяване) на функция в даден момент Х,принадлежащ на сегмента [ x 0, x p], необходимо е да се построи интерполационен полином от 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).

Интерполационни формулиЛагранж, Нютон и Стърлинг и др. при използване на голям брой интерполационни възли на целия сегмент [ а, b] често водят до лошо приближение поради натрупването на грешки в процеса на изчисление. Освен това, поради разминаването на процеса на интерполация, увеличаването на броя на възлите не води непременно до повишаване на точността. За да намалите грешките, целият сегмент [ а, b] се разделя на частични сегменти и на всеки от тях функцията се замества с приближен полином от ниска степен. Нарича се частична полиномна интерполация.

Един от методите за интерполация върху целия сегмент [ а, b] е сплайн интерполация.

Сплайнсе нарича частична полиномиална функция, дефинирана на сегмента [ а, b] и имащ определен брой непрекъснати производни на този сегмент. Предимствата на сплайн интерполацията пред конвенционалните методи за интерполация са в конвергенцията и стабилността на изчислителния процес.

Помислете за един от най-често срещаните случаи в практиката - интерполация на функцията кубичен сплайн.
Нека върху сегмента [ а, b] е непрекъсната функция. Нека въведем разделяне на сегмента:

и обозначават, .

Сплайн, съответстващ на дадена функция и интерполационни възли (6), е функция, която отговаря на следните условия:

1) на всеки сегмент функцията е кубичен полином;

2) функцията , както и нейните първа и втора производни са непрекъснати на сегмента [ а, b] ;

Третото условие се нарича условие за интерполация. Извиква се сплайн, определен от условия 1) - 3). интерполиращ кубичен сплайн.

Помислете за метод за конструиране на кубичен сплайн.

На всеки от сегментите, ще търсим сплайн функция под формата на полином от трета степен:

(7)

Където желани коефициенти.

Диференцираме (7) три пъти по отношение на х:

откъдето следва

От условието за интерполация 3) получаваме:

Това следва от условията за непрекъснатост на функцията.

Министерство на образованието и науката на Руската федерация

федерален държавен бюджет образователна институциявисше професионално образование

"Донски държавен университет"

Катедра "Софтуер за компютърна техника и автоматизирани системи" "ПОВТ и АС"

Специалност: Математическо осигуряване и администриране на информационни системи

КУРСОВА РАБОТА

по дисциплина "Методи на изчисление"

по темата: "Интерполация чрез сплайни"

Работен ръководител:

Медведева Татяна Александровна

Ростов на Дон

УПРАЖНЕНИЕ

за курсова работа по дисциплина "Методи на изчисленията"

Студент: Александър Моисеенко VBMO21 Group

Тема: "Интерполация чрез сплайни"

Краен срок за предаване на работа за защита “__” _______ 201_ г.

Първоначални данни за срочна писмена работа: бележки за лекции по методи за изчисление, ru.wikipedia.org, книга. Семинар по висша математика Sobol B.V.

Раздели на основната част: 1 ПРЕГЛЕД, 2 ИНТЕРПОЛАЦИОННА ФОРМУЛА, 3 КУБ ИНТЕРПОЛАЦИОНЕН АЛГОРИТЪМ, 4 СОФТУЕРЕН ДИЗАЙН, 5 СОФТУЕРНИ РЕЗУЛТАТИ.

Ръководител: /Медведева Т.А./

РЕЗЮМЕ

Докладът съдържа: страници-19, графики-3, източници-3, блокова схема-1.

Ключови думи: ИНТЕРПОЛАЦИЯ, СПЛАЙН, система Mathcad, КУБИЧНА ИНТЕРПОЛАЦИЯ ПО СПЛАЙН.

Подробно е разгледан методът на интерполация чрез кубични сплайни. Представен е съответният софтуерен модул. Илюстрирана е блоковата схема на програмния модул. Бяха разгледани няколко примера.

ВЪВЕДЕНИЕ

1. ТЕОРЕТИЧЕН ПРЕГЛЕД

2. ИНТЕРПОЛАЦИЯ

2.1 Интерполация с квадратен сплайн

2.2 Интерполация с помощта на кубичен сплайн

2.3 Постановка на проблема

3. ИНТЕРПОЛАЦИОНЕН АЛГОРИТЪМ С ИЗПОЛЗВАНЕ НА КУБИЧНИЯ СПЛАЙН

4. СОФТУЕРЕН ДИЗАЙН

5. РЕЗУЛТАТИ ОТ РАБОТА НА СОФТУЕРА

5.1 Описание на примерите

5.2 Резултат от теста

5.3 Тестов случай 1

5.4 Тестов случай 2

5.5 Тестов случай 3

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЯ

ВЪВЕДЕНИЕ

Апроксимацията на функциите се състои в приближената замяна на дадена функция f(х) чрез някаква функция j( х), така че отклонението на функцията j( х) от f(х) в дадения район е най-малък. Функция j( х) се нарича апроксимиращ. Типичен проблем с апроксимацията на функцията е проблемът с интерполацията. Необходимостта от интерполация на функция се дължи главно на две причини:

1. Функция f(х) има сложно аналитично описание, което създава определени трудности при използването му (напр. f(х) е специална функция: гама функция, елиптична функция и др.).

2. Аналитично описание на функцията f(х) неизвестен, т.е. f(х) е даден в таблица. В този случай е необходимо да има аналитично описание, което приблизително представлява f(х) (например за изчисляване на стойностите f(х) в произволни точки, дефиниции на интеграли и производни на f(х) и така нататък.).

1. ТЕОРЕТИЧЕН ПРЕГЛЕД

Интерполация - в изчислителната математика, начин за намиране на междинни стойности на количество от съществуващ дискретен набор известни стойности. При решаване на проблеми с научни и инженерни изчисления често е необходимо да се работи с набори от стойности, получени емпирично или по метода произволна извадка. Като правило, въз основа на тези набори, се изисква да се конструира функция, върху която други получени стойности биха могли да паднат с висока точност. Този проблем се нарича апроксимация на функции. Интерполацията е вид апроксимация на функции, при която кривата на построената функция минава точно през наличните точки от данни.

Сплайн е функция, чиято област на дефиниране е разделена на краен брой сегменти, на всеки от които сплайнът съвпада с някакъв алгебричен полином. Максималната степен на използваните полиноми се нарича степен на сплайн. Разликата между степента на сплайн и получената гладкост се нарича сплайн дефект.

Сплайновете позволяват ефективно решаване на проблемите с обработката на експериментални зависимости между параметри, които имат доста сложна структура.

Кубичните сплайни намериха широко практическо приложение. Основните идеи на теорията на кубичните сплайни се формират в резултат на опитите за математическо описание на гъвкави релси, изработени от еластичен материал (механични сплайни), които отдавна се използват от чертожниците в случаите, когато е необходимо да се начертае достатъчно гладка крива през дадени точки. Известно е, че релса, изработена от еластичен материал, фиксирана в определени точки и намираща се в равновесно положение, приема форма, при която нейната енергия е минимална. Това фундаментално свойство прави възможно ефективното използване на сплайни при решаване на практически проблеми за обработка на експериментална информация.

2. ИНТЕРПОЛАЦИЯ

2.1 Интерполация с квадратен сплайн

И така, върху всеки частичен сегмент от интерполация ще изградим функция от формата:

Ще търсим сплайн коефициенти от следните условия:

а) условия на Лагранж

б) непрекъснатост на първата производна във възловите точки

Последните две условия дават уравнения, докато броят на неизвестните коефициенти. Липсващото уравнение може да се получи от допълнителни условия, наложени върху поведението на сплайн. Например, можете да изисквате стойността на първата производна на сплайн s 1 в точката x 0 да бъде нула, т.е.

Заместването на тези изрази води до следните уравнения

където нотацията

Нека изразим коефициентите от второто уравнение ° С 1 , след заместване в него на стойностите на коефициентите а 1 от първото уравнение:

След това, замествайки този израз в уравнението на системата, получаваме проста рекурсивна връзка за коефициентите

Сега алгоритъмът за определяне на коефициентите на сплайновете става съвсем очевиден. Първо, използвайки формулата, ние определяме стойностите на всички коефициенти, като вземем предвид факта, че. След това, според формулата, изчисляваме коефициентите. Коефициентите се определят от първото уравнение на системата. В този случай процедурата за изчисляване на коефициентите на сплайновете трябва да се извърши само веднъж.

След като се изчислят коефициентите, за да се изчисли самият сплайн, е достатъчно да се определи номерът на интервала, в който попада точката на интерполация, и да се използва формулата. За да определим номера на интервала, ще използваме алгоритъм, подобен на този, използван в предишния пример за частична квадратична интерполация.

2.2 Интерполация с помощта на кубичен сплайн

Кубичен интерполационен сплайн , подходящи за тази функция f(х) и дадени възли х аз, наречена функция С(х), отговарящи на следните условия:

1. На всеки сегмент [ х аз- 1 , х аз], i = 1, 2, ..., Нфункция С(х) е полином от трета степен,

2. Функция С(х), и също нейните първа и втора производни са непрекъснати на интервала [ а, б],

3. С(х аз)= f(х аз), i = 0, 1, ..., Н.

На всеки от сегментите [х аз- 1 , х аз], i = 1, 2, ..., Нще търсим функция С(х)= S аз(х) под формата на полином от трета степен:

С аз(х)= а аз+б аз(х-х аз- 1)+c аз(х-х аз- 1) 2 +г аз(х- 1) 3 ,

х аз- 1 Ј хЈ х аз,

Където а аз,б аз, ° С аз, д аз- коефициенти, които изобщо да се определят нелементарни сегменти. За да има решение система от алгебрични уравнения, броят на уравненията трябва да е точно равен на броя на неизвестните. Така че трябва да получим 4 нуравнения.

Първо 2 нполучаваме уравненията от условието, че графиката на функцията С(х) трябва да премине през дадените точки, т.е.

С аз(х аз- 1)=г аз- 1 , С аз(х аз) = г аз.

Тези условия могат да бъдат записани като:

С аз(х аз- 1)= а аз=г аз- 1 ,

С аз(х аз)= а аз+б азч аз+c азh + d азh = y аз,

ч аз= х аз-х аз- 1 , i = 1, 2, ..., н.

Следваща 2 н- 2 уравнения следват от условието за непрекъснатост на първата и втората производни във възлите на интерполация, т.е. условието за гладкост на кривата във всички точки.

С" аз + 1 (х аз)=S" аз(х аз), аз = 1, ..., н - 1,

С"" аз + 1 (х аз)=S"" аз(х аз), i = 1, ..., н - 1,

С" аз(х)= б аз + 2 ° С аз(х-х аз- 1) + 3 д аз(х-х аз- 1),

С" аз + 1 (х)= б аз + 1 + 2 ° С аз + 1 (х-х аз) + 3 д аз + 1 (х-х аз).

Приравняване на всеки вътрешен възел х = х азстойностите на тези производни, изчислени в интервалите отляво и отдясно на възела, получаваме (като вземем предвид ч аз= х аз-х аз- 1):

b аз + 1 = б аз + 2 ч аз° С аз + 3ч д аз, i = 1, ..., н - 1,

С"" аз(х) = 2 ° С аз + 6 д аз(х-х аз- 1),

С"" аз + 1 (х) = 2 ° С аз + 1 + 6 д аз + 1 (х-х аз),

Ако х = х аз

° С аз + 1 = c аз + 3 ч азд аз, i = 1, 2, ..., н- 1.

На този етапимаме 4 ннеизвестен и 4 н- 2 уравнения. Следователно трябва да се намерят още две уравнения.

При свободно фиксиране на краищата, кривината на линията в тези точки може да бъде приравнена на нула. От условията на нулева кривина в краищата следва, че вторите производни са равни на нула в тези точки:

С 1" " (х 0) = 0 и С н" "(х н) = 0,

° С аз = 0 И 2 ° С н + 6 д нч н = 0.

Уравненията представляват система от линейни алгебрични уравнения за определяне на 4 нкоефициенти: а аз,б аз, ° С аз, д аз (аз = 1, 2, . . ., н).

Тази система може да бъде намалена до по-удобна форма. От условието можете веднага да намерите всички коефициенти ааз

аз = 1, 2, ..., н- 1,

Замествайки, получаваме:

b аз = - (° С аз + 1 + 2° С аз), i = 1, 2, ..., н- 1,

b н = - (ч н° С н)

Елиминирайте коефициентите от уравнението b азИ д аз. Накрая получаваме следната система от уравнения само за коефициентите с аз:

° С 1 = 0 и ° С n+ 1 = 0:

ч аз- 1 ° С аз- 1 + 2 (ч аз- 1 + ч аз) ° С аз+ ч аз° С аз + 1 = 3 ,

аз = 2, 3, ..., н.

Според намерените коеф с аз лесен за изчисляване д аз,б аз.

2.3 Постановка на проблема

На сегмента [ а, б] са дадени н + 1 точки х аз = х 0 , х 1 , . . ., х н, които се наричат ​​възли интерполация , и стойността на някаква функция f(х) в тези точки

f(х 0)=г 0 , е(х 1) = г 1 , . . ., е(х н)=г н.

Използване на кубични сплайни за изграждане на интерполационна функция f(х).

3. ИНТЕРПОЛАЦИОНЕН АЛГОРИТЪМ С ИЗПОЛЗВАНЕ НА КУБИЧНИЯ СПЛАЙН

Нека се запознаем с алгоритъма на програмата.

1. Изчислете стойностите и

2. Въз основа на тези стойности, ние изчисляваме коефициентите на почистване и o.

3. Въз основа на получените данни изчисляваме коефициентите

4. След това изчисляваме стойността на функцията с помощта на сплайн.

4. СОФТУЕРЕН ДИЗАЙН

5. РЕЗУЛТАТИ ОТ СОФТУЕРА

5.1 Описание на тестовите случаи

В хода на тази курсова работа е разработен софтуерен модул, който чертае съответстваща им крива през наличните точки. Проведени са тестови случаи, за да се провери ефективността на работата.

5.2 Резултати от теста

За проверка на правилното изпълнение на тестовите случаи се използва функцията cspline, вградена в пакета MATHCAD, която връща вектора на вторите производни при приближаване до кубичен полином в референтните точки.

5.3 Тестов случай 1

Фигура 1.1 - резултатът от програмата

Тестов случай 2

Фигура 1.2 - резултатът от програмата

Тестов случай 3

Фигура 1.3 - резултатът от програмата

ЗАКЛЮЧЕНИЕ

сплайн интерполационна функция изчисление

В изчислителната математика интерполацията на функции играе съществена роля, т.е. изграждане на дадена функция на друга (обикновено по-проста), чиито стойности съвпадат със стойностите на дадена функция в определен брой точки. Освен това интерполацията има както практическо, така и теоретично значение. На практика често възниква проблемът с възстановяването на непрекъсната функция от нейните таблични стойности, например тези, получени в хода на някакъв експеримент. За да се изчислят много функции, се оказва ефективно да се апроксимират чрез полиноми или дробни рационални функции. Теорията на интерполацията се използва при конструирането и изследването на квадратурни формули за числено интегриране, за получаване на методи за решаване на диференциални и интегрални уравнения. Основният недостатък на полиномната интерполация е, че тя е нестабилна върху една от най-удобните и често използвани мрежи - мрежа с равноотдалечени възли. Ако проблемът позволява, този проблем може да бъде решен чрез избор на мрежа с възли на Чебишев. Ако обаче не можем свободно да избираме възлите за интерполация или просто се нуждаем от алгоритъм, който не е твърде взискателен към избора на възли, тогава рационалната интерполация може да бъде подходяща алтернатива на полиномната интерполация.

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

БИБЛИОГРАФИЯ

1. Б. В. Собол, Б. Ч. Месхи, И. М. Пешхоев. Семинар по изчислителна математика. - Ростов на Дон: Феникс, 2008;

2. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобелков. Числени методи. Издателство "Лаборатория за фундаментални знания". 2003 г

3. www.wikipedia.ru/spline

Подобни документи

Изчислителни методи на линейната алгебра. Интерполация на функция. Интерполационен полином на Нютон. интерполационни възли. Интерполационен полином на Лагранж. Сплайн интерполация. Коефициенти на кубични сплайни.

лабораторна работа, добавена на 02/06/2004


В изчислителната математика интерполацията на функциите играе съществена роля. Формула на Лагранж. Интерполация по схемата на Aitken. Интерполационни формули на Нютон за равноотдалечени възли. Формула на Нютон с разделени разлики. Сплайн интерполация.

контролна работа, добавена на 05.01.2011 г


Конструирайте интерполационния полином на Нютон. Начертайте графика и маркирайте интерполационни възли върху нея. Конструирайте интерполационния полином на Лагранж. Извършете сплайн интерполация от трета степен.

лабораторна работа, добавена на 02/06/2004


Ролята на интерполацията на функции, чиито стойности съвпадат със стойностите на дадена функция в определен брой точки. Интерполация на функции от полиноми, директно непрекъснати функции върху отсечка и в точка. Определение на понятието интерполационна грешка.

курсова работа, добавена на 04/10/2011


Непрекъсната и точкова апроксимация. Интерполационни полиноми на Лагранж и Нютон. Глобална интерполационна грешка, квадратична зависимост. Метод на най-малките квадрати. Избор на емпирични формули. Частично постоянна и частично линейна интерполация.

курсова работа, добавена на 14.03.2014 г


Запознаване с историята на появата на метода на златното сечение. Разглеждане на основните понятия и алгоритъм за извършване на изчисления. Изучаване на метода на числата на Фибоначи и неговите характеристики. Описание на примери за прилагане на метода на златното сечение в програмирането.

курсова работа, добавена на 08/09/2015


Проблеми на глобалната и локална интерполация на Лагранж и Нютон; colive поведение на интерполационния полином; Рунге функции. Сплайнът е група от полиноми, наречени кубични полиноми с непреходен първи и друг подобен, предимствата на сплайн интерполацията.

презентация, добавена на 02/06/2014


Методи за числено диференциране. Изчисляване на производната, най-прости формули. Числено диференциране на базата на интерполация с алгебрични полиноми. Апроксимация с полинома на Лагранж. Диференциране, използване на интерполация.

курсова работа, добавена на 15.02.2016 г


Описание на методите за решаване на система от линейни алгебрични уравнения: обратна матрица, Якоби, Гаус-Зайдел. Постановка и решение на интерполационната задача. Избор на полиномна зависимост по метода на най-малките квадрати. Характеристики на метода на релаксация.

лабораторна работа, добавена на 12/06/2011


Проблемът за намиране на екстремум: същност и съдържание, оптимизация. Решение чрез методите на квадратичната интерполация и златното сечение, техните сравнителни характеристики, определяне на основните предимства и недостатъци. Брой итерации и оценка на точността.

Кривите и повърхнините, които се срещат в практическите задачи, често имат доста сложна форма, която не позволява универсална аналитична спецификация като цяло с помощта на елементарни функции. Следователно те се сглобяват от сравнително прости гладки фрагменти - сегменти (криви) или разрези (повърхности), всеки от които може да бъде доста задоволително описан с помощта на елементарни функции на една или две променливи. В този случай е съвсем естествено да се изисква гладките функции, които се използват за конструиране на частични криви или повърхности, да имат подобна природа, например да бъдат полиноми от същата степен. И за да бъде получената крива или повърхност достатъчно гладка, е необходимо да бъдете особено внимателни на кръстовищата на съответните фрагменти. Степента на полиномите се избира от прости геометрични съображения и като правило е малка. За плавна промяна на допирателната по цялата съставна крива е достатъчно свързващите криви да се опишат с помощта на полиноми от трета степен, кубични полиноми. Коефициентите на такива полиноми винаги могат да бъдат избрани така, че кривината на съответната съставна крива да е непрекъсната. Кубичните сплайни, които възникват при решаването на едномерни проблеми, могат да бъдат адаптирани към оформянето на фрагменти от съставни повърхности. И тук съвсем естествено се появяват бикубични сплайни, описани с полиноми от трета степен по всяка от двете променливи. Работата с такива сплайнове изисква много повече изчисления. Но правилно организираният процес ще позволи да се вземат предвид непрекъснато нарастващите възможности на компютърните технологии в максимална степен. Сплайн функции Нека върху сегмента , т.е. Забележка. Индексът (t) на числата a^ показва, че. че наборът от коефициенти, чрез които функцията S(x) се определя на всеки частичен сегмент D, е собствен. На всяка от отсечките D1 сплайнът 5(x) е полином от степен p и се определя на тази отсечка от p + 1 коефициент. Общо частични сегменти - тогава. Следователно, за да се определи напълно сплайнът, е необходимо да се намерят (p + 1), след това числа. Условие) означава непрекъснатостта на функцията S(x) и нейните производни във всички вътрешни възли на мрежата w. Броят на тези възли е m - 1. По този начин, за да се намерят коефициентите на всички полиноми, се получават p(m - 1) условия (уравнения). За пълна дефиниция на сплайна няма достатъчно (условия (уравнения). Изборът на допълнителни условия се определя от естеството на разглеждания проблем, а понякога просто от желанието на потребителя. ТЕОРИЯ НА СПЛАЙНОВЕ Примери за решения Най-често се разглеждат проблемите на интерполацията и изглаждането, когато се изисква да се построи един или друг сплайн от даден масив от точки на равнина. При интерполационните задачи се изисква графиката на сплайн да преминава през точки, които налага m + 1 допълнителни условия (уравнения) върху своите коефициенти. Останалите p - 1 условия (уравнения) за уникалната конструкция на сплайн най-често се задават под формата на стойности на долните производни на сплайн в краищата на разглеждания сегмент [a, 6] - граница ( гранични условия. Възможността да избирате различни гранични условия ви позволява да изграждате сплайнове с различни свойства. При проблеми с изглаждане сплайнът се изгражда така, че неговата графика да минава близо до точките (i "" Y "), * = 0, 1, ..., m, а не през тях. Мярката за тази близост може да бъде определена по различни начини, което води до значително разнообразие от изглаждащи сплайнове. Описаните възможности за избор при конструиране на сплайн функции далеч не изчерпват разнообразието им. И ако първоначално се разглеждаха само частични полиномиални сплайн функции, то с разширяването на обхвата на техните приложения започнаха да се появяват сплайнове, „слепени“ и от други елементарни функции. Интерполационни кубични сплайни Постановка на проблема с интерполацията Нека мрежата w е дадена на интервала [a, 6) Разгледайте набор от числа Проблем. Конструирайте функция, която е гладка на сегмента (a, 6] и приема дадените стойности във възлите на мрежата o, т.е. „Чрез налагане на допълнителни условия върху конструираната функция може да се постигне необходимата уникалност. В приложения, често става необходимо да се приближи функция, дадена аналитично с помощта на функция с предписани достатъчно добри свойства.Например, в случаите, когато изчисляването на стойностите на дадена функция f(x) в точки сегмент [a, 6] е свързано със значителни затруднения и/или дадената функция f(x) няма необходимата гладкост, е удобно да се използва друга функция, която би апроксимирала достатъчно добре дадената функция и би била лишена от нейните недостатъци [a, 6] гладка функция a(x), съвпадаща във възлите на мрежата w с дадената функция /(Х). Дефиниция на интерполиращ кубичен сплайн Интерполиращ кубичен сплайн 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-ти тип системата за определяне на числата се записва по следния начин. За гранични условия от 4-ти тип системата за определяне на числата има формата Матриците и на трите линейни алгебрични системи са матрици с диагонална доминантност. Тези матрици не са изродени и следователно всяка от тези системи има уникално решение. Теорема. Интерполационен кубичен сплайн, който отговаря на условия (2) и гранично условие от един от изброените четири типа, съществува и е уникален. По този начин, да се конструира интерполиращ кубичен сплайн означава да се намерят коефициентите му.Когато коефициентите на сплайна бъдат намерени, стойността на сплайн S(x) в произволна точка от сегмента [a, b] може да бъде намерена с помощта на формулата ( 3). За практически изчисления обаче следният алгоритъм за намиране на величината S(x) е по-подходящ. Нека x 6 [x", Първо, стойностите A и B се изчисляват съгласно формулите и след това се намира стойността 5(x): Използването на този алгоритъм значително намалява изчислителните разходи за определяне на стойността. Съвети към потребител Изборът на гранични (гранични) условия и интерполационни възли позволява до известна степен да се контролират свойствата на интерполационните сплайнове. А. Избор на гранични (гранични) условия. Изборът на гранични условия е един от централните проблеми при интерполацията на функции. Той придобива особено значение в случаите, когато е необходимо да се осигури висока точност на апроксимацията на функцията 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. B. Избор на интерполационни възли. Ако третата производна f " " (x) на функцията е прекъсната в някои точки на сегмента [a, b], тогава за подобряване на качеството на приближението, тези точки трябва да бъдат включени в броя на интерполационните възли. второ производно / "(x), тогава, за да се избегне трептене на сплайн близо до точките на прекъсване, трябва да се вземат специални мерки. интерполационните възли са избрани по такъв начин, че точките на прекъсване на втората производна да попадат в интервала \xif), така че. Стойността на a може да бъде избрана чрез числен експеримент (често е достатъчно да се зададе a = 0,01). Има набор от рецепти за преодоляване на трудностите, които възникват, когато първата производна f "(x) е прекъсната. Като една от най-простите, можем да предложим това: разделете апроксимационния сегмент на интервали, където производната е непрекъсната, и изградете a сплайн на всеки от тези интервали. свойствата на интерполационния полином на Лагранж от две противоположни позиции, като се обсъждат основните предимства отделно от недостатъците -тият подход: 1) графиката на интерполационния полином на Лагранж минава през всяка точка от масива, 2) конструираната функция се описва лесно ( броят на коефициентите на интерполационния полином на Лагранж върху мрежата u, който трябва да се определи, е равен на m + 1), 3) конструираната функция има непрекъснати производни на всяка пора 4) интерполационният полином е еднозначно определен от даден масив. Основните недостатъци на първия подход: 1) степента на интерполационния полином на Лагранж зависи от броя на възлите на мрежата и колкото по-голям е този брой, толкова по-висока е степента на интерполационния полином и следователно, толкова повече изчисления са необходими, 2 ) промяната на поне една точка в масива изисква пълно преизчисляване на коефициентите на интерполационния полином на Лагранж, 3) добавянето на нова точка към масива увеличава степента на интерполационния полином на Лагранж с единица и дори води до пълно преизчисляване на неговите коефициенти , 4) с неограничено усъвършенстване на мрежата, степента на интерполационния полином на Лагранж нараства неограничено. Поведението на интерполационния полином на Лагранж при неограничено прецизиране на мрежата обикновено изисква специално внимание. Коментари A. Апроксимация на непрекъсната функция с полином. Известно е (Weierstrass, 1885), че всяка непрекъсната (и още повече гладка) функция на интервал може да бъде апроксимирана, както и желано, на този интервал чрез полином. Нека опишем този факт на езика на формулите. Нека f(x) е функция, непрекъсната на отсечката [a, 6]. Тогава за всяко e > 0 съществува полином Рn(x) такъв, че за всяко x от интервала [a, 6] неравенството ще бъде изпълнено (фиг. 4) , безкрайно много са. На отсечката [a, 6] построяваме мрежа w. Ясно е, че неговите възли, най-общо казано, не съвпадат с пресечните точки на графиките на полинома Pn(x) и функцията f(x) (фиг. 5). Следователно, за взетата мрежа, полиномът Pn(x) не е интерполационен полином. Когато една непрекъсната функция се апроксимира чрез интерполационен полином на Jla-grajj, нейната графика не само не трябва да е близо до графиката на функцията f(x) във всяка точка от интервала [a, b), но може да се отклонява от тази функция колкото желаете. Нека дадем два примера. Пример 1 (Rung, 1901). При неограничено нарастване на броя на възлите за функция на интервала [-1, 1] се изпълнява граничното равенство (фиг. 6) Пример 2 (Berichtein, 1912). Последователност от интерполационни полиноми на Лагранж, конструирани върху равномерни мрежи nm за непрекъсната функция /(x) = |x| на сегмента с увеличаване на броя на възлите m не се стреми към функцията f(x) (фиг. 7). Подход 2-ри. Частично линейна интерполация Ако гладкостта на интерполираната функция бъде изоставена, съотношението между броя на предимствата и броя на недостатъците може да се промени значително в посока на първото. Нека построим линейна линейна функция чрез последователно свързване на точки (xit y,) с прави сегменти (фиг. 8). Основните предимства на втория подход са: 1) графиката на частично линейна функция минава през всяка точка от масива, 2) построената функция се описва лесно (броят на коефициентите на съответните линейни функции трябва да се определи за мрежата (1) е 2m), 3) конструираната функция е дефинирана от даден масив недвусмислено, 4) степента на полиномите, използвани за описание на интерполационната функция, не зависи от броя на възлите на мрежата (равен на 1), 5) промяна една точка в масива изисква изчисляване на четири числа (коефициентите на две праволинейни връзки, произтичащи от новата точка), 6) добавянето на допълнителна точка към масива изисква изчисляване на четири коефициента. Частично линейната функция се държи доста добре при прецизиране на мрежата. i Основният недостатък на втория подход е, че апроксимиращата частично линейна функция не е гладка: първите производни страдат от прекъсване във възлите на мрежата (интерполационни уши). Подход 3-ти. Сплайн интерполация Предложените подходи могат да се комбинират, така че броят на изброените предимства на двата подхода да се запази, като същевременно се намали броят на недостатъците. Това може да се направи чрез конструиране на гладка интерполираща сплайн функция със степен p. Основните предимства на третия подход: 1) графиката на построената функция минава през всяка точка от масива, 2) построената функция е сравнително лесна за описание (броят на коефициентите на съответните полиноми, които трябва да бъдат определени за мрежата ( 1) е 3) построената функция е уникално определена от даден масив, 4) полиномите на степента не зависят от броя на възлите на мрежата и следователно не се променят с увеличаването му, 5) построената функция има непрекъснати производни нагоре до ред p - 1 включително, 6) построената функция има добри апроксимационни свойства. Кратка справка. Предложеното наименование - сплайн - не е случайно - въведените от нас гладки частично-полиномиални функции и чертането на сплайнове са тясно свързани. Помислете за гъвкава, идеално тънка линийка, минаваща през референтните точки на масива, разположени в равнината (x, y). Според закона на Бернули-Ойлер линеаризираното уравнение на крива линийка има формата Функцията S(x), която описва линеалите, е полином от трета степен между всяка и две съседни точки от масива (опори) и е два пъти непрекъснато диференцируема на целия интервал (a, 6). Коментар. 06 Интерполация на непрекъсната функция За разлика от интерполационните полиноми на Лагранж, последователност от интерполационни кубични сплайнове върху равномерна решетка винаги се сближава към интерполирана непрекъсната функция и с подобряването на диференциалните свойства на тази функция скоростта на сходимост се увеличава. Пример. За функция кубичен сплайн върху решетка с брой възли m = 6 дава апроксимационна грешка от същия ред като интерполационния полином Ls(z), а върху решетка с брой възли m = 21 тази грешка е толкова малък, че в мащаба на обикновена книжна рисунка просто не може да бъде показан (фиг. 10) (интерполационният полином 1>2o(r) дава в този случай грешка от около 10 000 W). Свойства на интерполиран кубичен сплайн A. Апроксимационни свойства на кубичен сплайн. Апроксимационните свойства на интерполиращия сплайн зависят от гладкостта на функцията f(x) - колкото по-висока е гладкостта на интерполираната функция, толкова по-висок е редът на апроксимация, а когато мрежата е прецизирана, толкова по-висока е скоростта на конвергенция. Ако интерполираната функция f(x) е непрекъсната в интервала. Ако интерполираната функция f(x) има непрекъсната първа производна в интервала [a, 6], т.е. интерполационен сплайн, който удовлетворява граничните условия на 1-ви или 3-ти тип, тогава за h имаме В този случай не само сплайнът се сближава към интерполираната функция, но и производната на сплайна се сближава с производната на тази функция. Ако сплайнът S(x) апроксимира функцията f(x) на отсечката [a, b], а първата и втората му производна апроксимират съответно функцията B. Екстремално свойство на кубичен сплайн. Интерполационният кубичен сплайн има още един полезно свойство . Помислете за следния пример. пример. Конструирайте функция /(x), минимизираща функционала върху класа функции от пространството C2, чиито графики минават през точките на масива x), който удовлетворява граничните условия, доставя екстремум (минимум) на функционала. Забележка 2. Интересно е да се отбележи, че интерполиращият кубичен сплайн има екстремното свойство, описано по-горе, върху много широк клас функции, а именно, върху класа |0, 5]. 1.2. Изглаждане на кубични сплайни Относно формулирането на задачата за изглаждане Нека са дадени мрежа и набор от числа. Всъщност това означава, че за всеки е определен интервал и всяко число от този интервал може да се приеме като стойност на y, . Удобно е да се интерпретират стойностите на y, например, като резултати от измервания на някаква функция y(x) за дадени стойности на променливата x, съдържаща случайна грешка. Когато решавате проблема с възстановяването на функция от такива "експериментални" стойности, едва ли е препоръчително да използвате интерполация, тъй като интерполационната функция послушно ще възпроизведе странни колебания, причинени от случаен компонент в масива (y,). По-естественият подход се основава на процедура за изглаждане, предназначена да намали по някакъв начин елемента на произволност в резултат на измерванията. Обикновено при такива задачи се изисква да се намери функция, чиито стойности за x = x, * = 0, 1, .... m, биха попаднали в съответните интервали и които освен това биха имали достатъчно добри свойства. Например, той ще има непрекъснати първа и втора производни или графиката му няма да е твърде силно извита, тоест няма да има силни колебания. Проблем от този вид възниква и когато по даден (точно) масив се изисква да се конструира функция, която да минава през недадени точки, но близо до тях и освен това да се променя доста плавно. С други думи, желаната функция изглади дадения масив, така да се каже, и не го интерполира. Нека са дадени решетка w и два набора от числа.СПЛАЙНОВА ТЕОРИЯ примери за решения Проблем. Конструирайте гладка функция на сегмента [a, A], чиито стойности във възлите на мрежата и се различават от числата 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.Така че, за да дефинирате напълно сплайна, трябва да намерите 4m числа.Условието означава непрекъснатост на функцията 5(ar) и всички производни във всички вътрешни възли на grid o. „Броят на такива възли е m - 1 По този начин, за да се намерят коефициентите на всички полиноми, се получават 3 (m - 1) условия (уравнения). за които броят на величините, които трябва да се определят, е 2m + 2. На всеки от интервалите се търси изглаждащата сплайн функция в следната форма Нека първо опишем как се намират количествата n*. За гранични условия от 1-ви и 2-ри тип системата от линейни уравнения за определяне на стойностите на Hi е написана в следната форма, където са известните числа). Коефициентите зависят от избора на гранични условия. Гранични условия от 1-ви тип: Гранични условия от 2-ри тип: В случай на гранични условия от 3-ти тип системата за определяне на числата е записана по следния начин: освен това всички коефициенти се изчисляват по формули (5) (количествата с индексите k и m + k се считат за равни на: Важна* забележка. Матриците на системите не са изродени и следователно всяка от тези системи има уникално решение. Ако числата n, - са намерени, тогава количествата се определят лесно по формулите Ако всичко и изглаждащият сплайн се окаже интерполационен. Това означава, по-специално, че колкото по-точно са дадени стойностите, толкова по-малка е предварителната стойност на съответните тегловни коефициенти. Ако, от друга страна, е необходимо сплайнът да минава през точката (x^, yk), тогава коефициентът на тежест p\, съответстващ на него, трябва да бъде зададен равен на нула. При практическите изчисления най-важен е изборът на стойности pi-Нека D, - грешката на измерване на стойността y,. Тогава е естествено да се изисква изглаждащият сплайн да отговаря на условието или, което е същото.В най-простия случай тегловните коефициенти pi могат да бъдат дадени например във формата - където c е някаква достатъчно малка константа. Въпреки това, такъв избор на тегла p, не позволява използването на "коридора" поради грешки в стойностите на y, -. По-рационален, но и по-отнемащ време алгоритъм за определяне на стойностите на p, - може да изглежда по следния начин. Ако стойностите са намерени на fc-тата итерация, тогава се приема, че e е малко число, което се избира експериментално, като се вземат предвид битовата мрежа на компютъра, стойностите на D и точността на решаване на система от линейни алгебрични уравнения. Ако при fc-тата итерация в точка i условието (6) е нарушено, тогава последната формула ще осигури намаляване на съответния коефициент на тежест p,. Ако след това, при следващата итерация, увеличаването на p води до по-пълно използване на "коридора" (6) и в крайна сметка до по-плавно променящ се сплайн. Малко теория А. Обосноваване на формули за изчисляване на коефициентите на интерполационния кубичен сплайн. Въвеждаме обозначението, където m са неизвестни величини. Техният брой е равен на m + 1. Сплайнът, записан във вида, в който отговаря на условията за интерполация и е непрекъснат на целия интервал [a, b\: въвеждайки формулата, получаваме респ. Освен това има непрекъсната първа производна на интервала [a, 6]: диференцираща връзка (7) и настройка, получаваме съответния. всъщност. Нека покажем, че числата m могат да бъдат избрани така, че сплайн функцията (7) да има непрекъсната втора производна на интервала [a, 6]. Изчислете втората производна на сплайна на интервала: В точката x, - 0 (при t = 1) имаме Изчислете втората производна на сплайна на интервала В точката имаме От условието за непрекъснатост на втората производна във вътрешните възли на мрежата a; получаваме връзката m - 1, където Добавяйки към тези m - 1 уравнения още две, произтичащи от и от граничните условия, получаваме система от m + 1 линейни алгебрични уравнения с m + I неизвестно miy i = 0, 1. ... , м. Системата от уравнения за изчисляване на стойностите на gw в случай на гранични условия от 1-ви и 2-ри тип има формата където (гранични условия от 1-ви тип), (гранични условия от 2-ри тип). За периодични гранични условия (гранични условия от 3-ти тип), мрежата o; удължете с още един възел и приемете, че тогава системата за определяне на стойностите на r* ще има формата непрекъснатост във втория и (th - !) th възли на мрежата. Имаме От последните две отношения получаваме липсващите две уравнения, които съответстват на граничните условия от 4-ти тип: Изключвайки неизвестното r0 от уравненията и неизвестното pc от уравненията, в резултат получаваме система от уравнения Обърнете внимание, че броят на неизвестните в тази система е равен на r - I. 6. Обосновка на формулите за изчисляване на ефективността на изглаждащ субичен сплайн. Въвеждаме обозначението, където Zi и nj са все още неизвестни величини. Техният брой е равен на 2m + 2. Сплайн функцията, записана във формата, е непрекъсната на целия интервал (a, 6]: поставяйки тази формула, получаваме съответно. Нека покажем, че числата z и n могат да бъде избран така, че сплайнът, записан във формата (8), да има непрекъсната първа производна на интервала [a, 6] Изчислете първата производна на сплайна S(x) на интервала: В дадена точка имаме От условие за непрекъснатост на първата производна на сплайна във вътрешните възли на мрежата и --> получаваме връзка m - 1. Удобно е да напишем тази връзка в матрична форма. връзка (8) и настройка, получаваме, съответно матричното отношение Йеше олю се получава от условието за минимум на функционала (4). Имаме Последните две матрични равенства могат да се разглеждат като линейна система от 2m + 2 линейни алгебрични уравнения в 2m + 2 неизвестни. Заменяйки колоната r в първото равенство с нейния израз, получен от съотношението (9), стигаме до матричното уравнение СПЛАЙНОВА ТЕОРИЯ примери за решения за определяне на колона М. Това уравнение има уникално решение поради факта, че матрицата A + 6HRH7 винаги е неизроден. Намирайки го, ние лесно идентифицираме г-н Имшайн. Елементите на триъгълните маголални матрици A и H определят n само от параметрите на мрежата u (със стъпки hi) и не зависят от стойностите yj. Линейно пространство на кубични сплайн функции Наборът от кубични сплайнове, конструирани върху сегмента [a, 6) от възела wcra + l, е линейно пространство с размерност m + 3: 1) сумата от два кубични сплайна, конструирани от мрежата u> и произведението на кубичен сплайн , изграден върху мрежата u>, произволен брой по-секретни са кубичните сплайни, изградени върху тази мрежа, 2) всеки кубичен сплайн, изграден върху мрежата и от възела, е напълно определен от m + 1 от стойност на стойностите на y "в тези възли и две гранични условия - само + 3 параметъра. Избирайки в това пространство основа, състояща се от m + 3 линейно независими сплайна, можем да запишем произволен кубичен сплайн a(x) като линейна комбинация от тях по уникален начин. Коментирайте. Такава спецификация на сплайн се използва широко в изчислителната практика. Особено удобна е основата, състояща се от така наречените кубични B-сплайнове (основни или фундаментални сплайнове). Използването на D-сплайнове може значително да намали изискванията за компютърна памет. L-сплайнове. B -сплайн от нулева степен, изграден върху числова права по мрежата w, е функцията на вилицата B -сплайн от степен k ^ I, построен върху числова права по мрежата u, се определя от рекурсивната формула, втора в \7\x) степени са показани съответно на фиг. 11 и 12. B-сплайн с произволна степен k може да бъде различен от нула само на определен сегмент (дефиниран от k + 2 възли). По-удобно е да се номерират кубични B -сплайни, така че сплайнът B,-3* (n) да е различен от нула на сегмента ir,-+2]. Нека дадем формула за кубичен сплайн от трета степен за случая на равномерна мрежа (с стъпка A). ​​Имаме в други случаи. Типична графика на кубичен B-сплайн е представена на фиг. 13. Функцията a) е два пъти непрекъснато диференцируема на сегмент, тоест принадлежи към класа C2 [a, "), c) е различно от нула само на четири последователни сегмента разширена мрежа w * mo Необходимо е да се конструира семейство от m + 3 кубични B-сплайна: Това семейство формира основа в пространството на кубичните сплайнове на сегмента (a, b]. По този начин, произволен кубичен сплайн S(z), конструиран върху сегмента |s, 6] на мрежата o; от +1 възли, могат да бъдат представени на този сегмент като линейна комбинация.Коефициентите ft на това разширение се определят еднозначно от условията на проблема. ... В случая, когато стойностите на функцията във възлите на мрежата и стойностите на първата производна на функцията в краищата на мрежата "(интерполационен проблем с граница условия от първи вид), тези коефициенти се изчисляват от системата от следния вид стойности b-iи &m+i, получаваме линейна система с неизвестни 5q, ... , bm и тридиюнална матрица. Условието осигурява диагонално господство и следователно възможността за прилагане на метода на почистване за разрешаването му. 3MMCHMYU 1. Линейни системи с подобна форма възникват и при разглеждане на други проблеми на интерполацията. Zmmchm* 2. В сравнение с алгоритмите, описани в раздел 1.1, използването на R-сплайн в * интерполационни проблеми позволява * да се намали количеството на съхранената информация, т.е. значително да се намалят изискванията за компютърна памет, въпреки че води до увеличаване на броя на операциите. Конструиране на сплайнови криви с помощта на сплайнови функции По-горе бяха разгледани масиви, чиито точки бяха номерирани така, че техните абсцисни форми образуваха строго нарастваща последователност. Например случаят, изобразен на фиг. 14, когато различни точки от масива имат една и съща абциса, не се допуска. Това обстоятелство определя както избора на клас апроксимиращи криви (трафик на функции), така и метода за тяхното конструиране. Предложеният по-горе метод обаче дава възможност за доста успешно конструиране на интерполационна крива в по-общ случай, когато номерирането на точките на масива и тяхното местоположение в равнината, като правило, не са свързани (фиг. 15). Освен това, когато поставяме задачата за изграждане на интерполационна крива, можем да считаме дадения масив за непланарен, т.е. ясно е, че за да се реши този общ проблем, е необходимо значително да се разшири класът на допустимите криви, в т.ч. както затворени криви, така и криви със самопресечни точки и пространствени криви. Удобно е да се опишат такива криви с помощта на параметрични уравнения. Нека изискаме. освен това, така че функциите да имат достатъчна гладкост, например, те принадлежат към класа C1 [a, /0] или към класа За да намерите параметричните уравнения на крива, минаваща последователно през всички точки на масива, процедирайте по следния начин. 1-ва стъпка. на произволен интервал)