Nechť je uvedena tabulka hodnot funkcí y i v uzlech X 0 < х 1 < ... < х п .Označit h i = x i – x i -1 , i= 1, 2, ... , P.

Spline– plynulá křivka procházející danými body ( x i, y i), i = 0, 1, ... , P. Spline interpolace je to v každém segmentu [ x i -1 , x i]používá se polynom určitého stupně. Nejčastěji se používá polynom třetího stupně, méně často druhý nebo čtvrtý. V tomto případě se pro stanovení koeficientů polynomů používají podmínky spojitosti derivací v interpolačních uzlech.

Interpolace s kubickými splajny představuje lokální interpolaci, kdy na každém segmentu [ x i -1 , x i], i = 1, 2, ... , P používá se kubická křivka, která splňuje určité podmínky hladkosti, jmenovitě spojitost samotné funkce a její první a druhé derivace v uzlových bodech. Použití kubické funkce je způsobeno následujícími úvahami. Pokud předpokládáme, že interpolační křivka odpovídá pružnému pravítku fixovanému v bodech ( x i, y i), pak z kurzu pevnosti materiálů je známo, že tato křivka je definována jako řešení diferenciální rovnice F(IV) ( X) = 0 na intervalu [ x i -1 , x i](pro jednoduchost prezentace nebereme v úvahu problémy spojené s fyzickými rozměry). Obecným řešením takové rovnice je polynom 3. stupně s libovolnými koeficienty, který se pohodlně zapisuje ve tvaru
S i(X) = a já + b i(X - x i -1) +s i(X - x i -1) 2 + d i(X - x i -1) 3 ,
x i-1 £ X £ x i, i = 1, 2, ... , P.(4.32)

Funkční koeficienty S i(X)jsou určeny z podmínek spojitosti funkce a její první a druhé derivace ve vnitřních uzlech x i,i= 1, 2,..., P - 1.

Ze vzorců (4.32) at X = x i-1 dostaneme

S i(xi- 1) = y i -1 = i, i = 1, 2,..., P,(4.33)

a kdy X = x i

S i(x i) = a já + b i h i +s i h i 2 + d i h i 3 ,(4.34)

i= 1, 2,..., n.

Podmínky spojitosti pro interpolační funkci jsou zapsány jako S i(x i) = S i -1 (x i), i= 1, 2, ... , n- 1 a z podmínek (4.33) a (4.34) vyplývá, že jsou splnitelné.

Pojďme najít derivace funkce S i(X):

S" i(X) =b i + 2s i(X - x i -1) + 3di(X – x i -1) 2 ,

S" i(X) = 2c i + 6d i(x - x i -1).

Na X = x i-1, máme S" i(x i -1) = b i, S" (x i -1) = 2s i, a kdy X = x i dostaneme

S" i(x i) = b i+ 2s i h i+ 3dih i 2 , S" (x i) = 2s i + 6d i h i.

Podmínky spojitosti derivací vedou k rovnicím

S" i(x i) =S" i +1 (x i) Þ b i+ 2s i h i+ 3dih i 2 = b i +1 ,

i= l, 2,..., P - 1. (4.35)

S" i (x i) = S" i +1 (x i) Þ 2 s i + 6d i h i= 2c i +1 ,

i= l, 2,..., n- 1. (4.36)

Celkem máme 4 n– 2 rovnice k určení 4 n neznámý. Pro získání dalších dvou rovnic se používají další okrajové podmínky, například požadavek, aby interpolační křivka měla nulové zakřivení v koncových bodech, tj. aby druhá derivace byla na koncích segmentu rovna nule [ A, b]A = X 0 , b= x n:

S" 1 (X 0) = 2C 1 = 0 Þ S 1 = 0,

S'n(x n) = 2s n + 6d n h n = 0 Þ s n + 3d n h n = 0. (4.37)

Systém rovnic (4.33)–(4.37) lze zjednodušit a získat opakující se vzorce pro výpočet spline koeficientů.

Z podmínky (4.33) máme explicitní vzorce pro výpočet koeficientů a i:

a i = y i -1 , i= 1,..., n. (4.38)

Pojďme se vyjádřit d i přes c i pomocí (4.36), (4.37):

; i = 1, 2,...,n; .

Položme s n+1 = 0, pak pro d i dostaneme jeden vzorec:

, i = 1, 2,...,n. (4.39)

Dosadíme výrazy za a já A d i do rovnosti (4.34):

, i= 1, 2,..., n.

a vyjádřit b i, přes s i:

, i= 1, 2,..., n. (4.40)

Vynechme koeficienty z rovnic (4.35) b i A d i pomocí (4.39) a (4.40):

i= 1, 2,..., n -1.

Odtud získáme soustavu rovnic pro určení s i:

Soustavu rovnic (4.41) lze přepsat jako

Zde je uvedena notace

, i =1, 2,..., n- 1.

Řešme soustavu rovnic (4.42) metodou rozmítání. Z první rovnice vyjádříme S 2 přes S 3:

C 2 = a 2 C 3 + b 2 , , . (4,43)

Dosadíme (4.43) do druhé rovnice (4.42):

h 2 (a 2 C 3 + b 2) + 2( h 2 + h 3)C 3 +h 3 C 4 = G 2 ,

a vyjádřit S 3 přes S 4:

S 3 = 3 S 4 + b 3, (4,44)

Za předpokladu, že s i-1 = a i -1 c i+b i-1 z i dostaneme rovnici (4.42).

c i= a já s i+1+b i

, i = 3,..., n– 1, a n= 0, (4,45) c n +1 = 0,

c i= a já s i+1+b i, i= n, n -1,..., 2, (4.48)

C 1 = 0.

3. Výpočet koeficientů a já, b i,d i:

a i = y i -1 ,

i= 1, 2,..., n.

4. Vypočítejte hodnotu funkce pomocí spline. Chcete-li to provést, vyhledejte následující hodnotu i, že daná hodnota proměnné X patří do segmentu [ x i -1 , x i] a vypočítat

S i(X) = a já + b i(X - x i -1) +s i(X - x i -1) 2 + d i(X - x i -1) 3 . (4.50)

Slovo spline (anglické slovo "spline") znamená flexibilní pravítko používané k kreslení hladkých křivek přes dané body v rovině. Tvar tohoto univerzálního vzoru na každém segmentu je popsán kubickou parabolou. Spline jsou široce používány v inženýrských aplikacích, zejména v počítačové grafice. Takže na každém i–tý segment [ x i –1 ,x i], i= 1, 2,…, N, Budeme hledat řešení ve formě polynomu třetího stupně:

S i(X)=a i +b i(x–xi)+c i(X–x i) 2 /2+d i(x–xi) 3 /6

Neznámý kurz a i, b i, c i, d i, i= 1, 2,..., N, najdeme z:

Podmínky interpolace: S i(x i)=f i, i= 1, 2,..., N;S 1 (X 0)=f 0 ,

Kontinuita funkce S i(x i– 1 )=S i– 1 (x i –1), i= 2, 3,..., N,

Spojitosti první a druhé derivace:

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,..., N.

Vzhledem k tomu, pro definici 4 N neznámé dostaneme systém 4 N-2 rovnice:

a i =f i, i= 1, 2,..., N,

b i h i – c i h i 2 /2+ d i h i 3 /6= f i – f i –1 , i= 1, 2,..., N,

b i – b i–1 = c i h i – d i h i 2 /2, i= 2, 3,..., N,

d i h i = c i – c i– 1 , i= 2, 3,..., N.

Kde h i =x i – x i– 1. Chybějící dvě rovnice jsou odvozeny z dalších podmínek: S //(A)=S //(b)=0. Lze ukázat, že v tomto případě . Neznámé mohou být ze systému vyloučeny b i, d i, po obdržení systému N+ 1 lineární rovnice (SLAE) pro stanovení koeficientů c i:

C 0 = 0cN= 0,

h i c i –1 + 2(h i + h i +1)c i + h i +1 c i +1 = 6 , i= 1, 2,…, N–1. (1)

Poté se vypočtou koeficienty b i, d i:

, i= 1, 2,..., N. (2)

V případě konstantní mřížky h i = h Tento systém rovnic je zjednodušený.

Tento SLAE má tridiagonální matici a je řešen metodou rozmítání.

Koeficienty se určují ze vzorců:

Pro výpočet hodnoty S(X) v libovolném bodě segmentu z∈[a, b] je nutné vyřešit soustavu rovnic pro koeficienty c i, i= 1,2,…, N–1, pak najděte všechny koeficienty b i, d i. Dále musíte určit, pro jaký interval [ x i 0, x i 0–1 ] tento bod zasáhne, a při znalosti čísla já 0, vypočítat hodnotu splajnu a jeho derivací v bodě z

S(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

S/(z)=b i 0 +c i 0 (z–xi 0)+d i 0 (z–xi 0) 2 /2, S //(z)=c i 0 +d i 0 (z–xi 0).

Je nutné vypočítat funkční hodnoty v bodech 0,25 a 0,8 pomocí spline interpolace.

V našem případě: h i =1/4, .

Napišme soustavu rovnic, abychom určili:

Řešením této soustavy lineárních rovnic získáme: .

Uvažujme bod 0,25, který patří do prvního segmentu, tzn. . Proto dostáváme,

Uvažujme bod 0.8, který patří do čtvrtého segmentu, tzn. .

Proto,

Globální interpolace

Když globální interpolace v celém intervalu je nalezen jediný polynom [ a, b], tj. je sestrojen polynom, který slouží k interpolaci funkce f(x) přes celý interval variace argumentu x. Budeme hledat interpolační funkci ve tvaru polynomu (polynomu) m-tý stupeň Odpoledne(X)=a 0 +a 1 x+a 2 X 2 +a 3 X 3 +…+a m x m . Jaký musí být stupeň polynomu, aby byly splněny všechny podmínky interpolace? Předpokládejme, že jsou dány dva body: ( X 0 ,F 0) a ( X 1 ,F 1), tzn. N=1. Těmito body lze vést jedinou přímku, tzn. interpolační funkce bude polynom prvního stupně P 1 (X)=a 0 +a 1 X. Prostřednictvím tří bodů (N=2) můžete nakreslit parabolu P 2 (X)=a 0 +a 1 x+a 2 X 2 atd. Uvažováním tímto způsobem můžeme předpokládat, že požadovaný polynom musí mít stupeň N .

Abychom to dokázali, sepíšeme soustavu rovnic pro koeficienty. Systémové rovnice představují interpolační podmínky pro každou z nich x=xi:

Tento systém je lineární s ohledem na požadované koeficienty A 0 ,A 1 ,A 2 , …,N. Je známo, že SLAE má řešení, pokud je jeho determinant odlišný od nuly. Determinant tohoto systému

nese jméno Vandermondův determinant. Z průběhu matematické analýzy je známo, že se liší od nuly, jestliže x k≠x m(tj. všechny interpolační uzly jsou různé). Je tedy dokázáno, že systém má řešení.

Ukázali jsme to, abychom našli koeficienty
A 0 ,A 1 ,A 2 , …,N je nutné vyřešit SLAE, což je obtížný úkol. Existuje však další způsob, jak sestrojit polynom N-tý stupeň, který nevyžaduje řešení takového systému.

Lagrangeův polynom

Hledáme řešení ve formuláři , Kde l i(z) – bázové polynomy N- stupeň, pro který je podmínka splněna: . Ujistíme se, že pokud jsou takové polynomy sestrojeny, pak L N (x) bude splňovat podmínky interpolace:

Jak konstruovat základní polynomy? Pojďme definovat

, i= 0, 1,..., N.

Je snadné to pochopit

Funkce l i(z) je polynom N-tý stupeň od z a pro něj jsou splněny podmínky „základnosti“:

0, i≠k;, tzn. k=1,…,i-1 nebo k=i+1,…,N.

Tak jsme byli schopni vyřešit problém sestrojení interpolačního polynomu N– stupně, a k tomu nemusíte řešit SLAE. Lagrangeův polynom lze zapsat jako kompaktní vzorec: . Chybu tohoto vzorce lze odhadnout, pokud původní funkce G(X) má deriváty až N+ 1. objednávka:

Z tohoto vzorce vyplývá, že chyba metody závisí na vlastnostech funkce G(X), stejně jako umístění interpolačních uzlů a bodů z. Jak ukazují výpočetní experimenty, Lagrangeův polynom má pro malé hodnoty malou chybu N<20 . Při větším N chyba začíná narůstat, což naznačuje, že Lagrangeova metoda nekonverguje (tj. její chyba se s rostoucím N).

Podívejme se na zvláštní případy. Nechť N=1, tzn. Hodnoty funkcí jsou specifikovány pouze ve dvou bodech. Pak mají základní polynomy tvar:

, tj. získáme vzorce pro po částech lineární interpolaci.

Nechť N=2. Pak:

V důsledku toho jsme získali vzorce tzv kvadratická nebo parabolická interpolace.

Příklad: Hodnoty určité funkce jsou dány:

Je nutné zjistit hodnotu funkce kdy z= 1 pomocí Lgrangeova interpolačního polynomu. Ad hoc N=3, tzn. Lagrangeův polynom je třetího řádu. Vypočítejme hodnoty základních polynomů at z=1:

Výběr empirických vzorců

Při interpolaci funkcí jsme použili podmínku rovnosti hodnot interpolačního polynomu a dané funkce v uzlech interpolace. Pokud byla počáteční data získána jako výsledek experimentálních měření, pak požadavek na přesnou shodu není nutný, protože data nebyla získána přesně. V těchto případech můžete požadovat pouze přibližné splnění podmínek interpolace. Tato podmínka znamená, že interpolační funkce F(x) prochází ne přesně danými body, ale v nějakém jejich sousedství, např. jak je znázorněno na Obr.

Pak o tom mluví výběr empirických vzorců. Konstrukce empirického vzorce se skládá ze dvou fází6 výběru typu tohoto vzorce obsahujícího neznámé parametry a určení nejlepšího z těchto parametrů v určitém smyslu. Forma vzorce je někdy známa z fyzikálních úvah (pro elastické médium vztah mezi napětím a deformací) nebo je vybrána z geometrických úvah: experimentální body jsou vyneseny do grafu a obecný tvar vztahu je přibližně uhodnut porovnáním výsledná křivka s grafy váhových funkcí. O úspěchu zde do značné míry rozhoduje zkušenost a intuice výzkumníka.

Pro praxi je důležitý případ aproximace funkce polynomy, tzn. .

Poté, co byl vybrán typ empirické závislosti, je míra blízkosti empirických dat určena pomocí minimální součet čtverců odchylek vypočtených a experimentálních dat.

Metoda nejmenších čtverců

Pojďme k počátečním údajům x i, f i, i= 1,…,N (je lepší začít číslovat od jedné), Typ zvolené empirické závislosti je: s neznámými koeficienty. Zapišme součet čtverců odchylek mezi odchylkami vypočtenými pomocí empirického vzorce a uvedenými experimentálními daty:

Najdeme parametry z podmínky pro minimum funkce . Tohle je metoda nejmenších čtverců (LSM).

Je známo, že v minimálním bodě jsou všechny parciální derivace rovny nule:

(1)

Zvažme použití nejmenších čtverců pro speciální případ, který je v praxi široce používán. Jako empirickou funkci uvažujme polynom

Vzorec (1) pro určení součtu čtverců odchylek bude mít tvar:

Spočítejme si derivace:

Přirovnáním těchto výrazů k nule a sběrem koeficientů pro neznámé dostaneme následující systém lineárních rovnic.

Interpolační vzorce Lagrangeova, Newtona a Stirlinga atd. při použití velkého počtu interpolačních uzlů na celém segmentu [ A, b] často vedou ke špatné aproximaci kvůli hromadění chyb během procesu výpočtu. Navíc kvůli divergenci procesu interpolace nemusí zvýšení počtu uzlů nutně vést ke zvýšení přesnosti. Aby se snížily chyby, celý segment [ A, b] je rozdělena na dílčí segmenty a na každém z nich je funkce nahrazena přibližně polynomem nízkého stupně. To se nazývá po částech polynomiální interpolace.

Jedna z metod interpolace přes celý segment [ A, b] je spline interpolace.

Spline je po částech polynomiální funkce definovaná na intervalu [ A, b] a mající na tomto segmentu určitý počet spojitých derivací. Výhody spline interpolace ve srovnání s konvenčními interpolačními metodami jsou konvergence a stabilita výpočetního procesu.

Uvažujme jeden z nejběžnějších případů v praxi – interpolaci funkce kubický spline.
Nechte na segmentu [ A, b] je zadána spojitá funkce. Uveďme rozdělení segmentu:

a označovat, .

Spline odpovídající dané funkci a interpolačním uzlům (6) je funkce, která splňuje následující podmínky:

1) na každém segmentu je funkcí kubický polynom;

2) funkce, stejně jako její první a druhá derivace, jsou spojité na intervalu [ A, b] ;

Třetí podmínka se nazývá interpolační podmínka. Zavolá se splajn definovaný podmínkami 1) – 3). interpolační kubický spline.

Uvažujme metodu pro konstrukci kubické spline.

Na každém ze segmentů, Budeme hledat spline funkci ve tvaru polynomu třetího stupně:

(7)

Kde požadované koeficienty.

Rozlišujme (7) třikrát vzhledem k X:

odkud následuje

Z interpolační podmínky 3) získáme:

Vyplývá to z podmínek návaznosti funkce.

2.2 Interpolace pomocí kubické spline

Kubický interpolační spline odpovídající dané funkci f(x) a daným uzlům x i je funkcí S(x), která splňuje následující podmínky:

1. Na každém segmentu i = 1, 2, ..., N je funkce S(x) polynom třetího stupně,

2. Funkce S(x), stejně jako její první a druhá derivace, jsou spojité na intervalu,

3. S(xi) = f(xi), i = 0, 1, ..., N.

Na každém ze segmentů , i = 1, 2, ..., N, budeme hledat funkci S(x) = S i (x) ve tvaru polynomu třetího stupně:

S i (x) = a i + b i (x - x i - 1) + c i (x - x i - 1) 2 + d i (x - 1) 3,

x i – 1 Ј x Ј x i ,

kde a i, b i, c i, d i jsou koeficienty, které se mají určit na všech n elementárních segmentech. Aby systém algebraických rovnic měl řešení, musí být počet rovnic přesně roven počtu neznámých. Měli bychom tedy dostat 4n rovnic.

Prvních 2n rovnic získáme z podmínky, že graf funkce S(x) musí procházet danými body, tzn.

Si (xi-1) = yi-1, Si (xi) = yi.

Tyto podmínky lze zapsat jako:

Si (x i - 1) = a i = y i - 1,

S i (x i) = a i + b i h i + c i h + d i h = y i,

h i = x i - x i - 1, i = 1, 2, ..., n.

Následující rovnice 2n - 2 vyplývají z podmínky spojitosti první a druhé derivace v uzlech interpolace, tj. podmínky hladkosti křivky ve všech bodech.

Si + 1 (x i) = Si (x i), i = 1, ..., n - 1,

S i (x) = b i + 2 c i (x - x i - 1) + 3 d i (x - x i - 1),

Si + 1 (x) = b i + 1 + 2 c i + 1 (x - x i) + 3 d i + 1 (x - x i).

Když u každého vnitřního uzlu x = x i vyrovnáme hodnoty těchto derivací, vypočítané v intervalech nalevo a napravo od uzlu, získáme (s přihlédnutím k h i = x i - x i - 1):

b i + 1 = b i + 2 h i c i + 3h d i , i = 1, ..., n - 1,

S i (x) = 2 c i + 6 d i (x - x i - 1),

Si + 1 (x) = 2 c i + 1 + 6 d i + 1 (x - x i),

pokud x = x i

c i + 1 = c i + 3 h i d i, i = 1,2, ..., n - 1.

V této fázi máme 4n neznámých a 4n - 2 rovnice. Proto je třeba najít další dvě rovnice.

Když jsou konce volně zajištěny, lze zakřivení čáry v těchto bodech nastavit na nulu. Z podmínek nulového zakřivení na koncích vyplývá, že druhé derivace v těchto bodech jsou rovny nule:

S1 (x 0) = 0 a Sn (x n) = 0,

cj = 0 a 2 cn + 6 dnhn = 0.

Rovnice tvoří soustavu lineárních algebraických rovnic pro určení 4n koeficientů: a i, b i, c i, d i (i = 1, 2, ..., n).

Tento systém lze převést do pohodlnější podoby. Z podmínky můžete okamžitě najít všechny koeficienty a i.

i = 1, 2, ..., n - 1,

Nahrazením dostaneme:

b i = - (c i + 1 + 2c i), i = 1,2, ..., n - 1,

b n = - (h n c n)

Koeficienty b i a d i z rovnice vyloučíme. Nakonec získáme následující soustavu rovnic pouze pro koeficienty s i:

c 1 = 0 a c n + 1 = 0:

h i - 1 c i - 1 + 2 (hi - 1 + h i) c i + h i c i + 1 = 3,

i = 2, 3, ..., n.

Ze zjištěných koeficientů s i lze snadno vypočítat d i,b i.

Výpočet integrálů metodou Monte Carlo

Tento softwarový produkt implementuje možnost nastavit další omezení v oblasti integrace pomocí dvou dvourozměrných spline ploch (pro integrandovou funkci dimenze 3)...

Interpolace funkcí

Nechť je dána tabulka hodnot funkcí f(xi) = yi (), ve které jsou uspořádány vzestupně podle hodnot argumentů: x0< x1 < … < xn. Чтобы построить кубический сплайн, требуется определить коэффициенты ai0, ai1, ai2, ai3...

Spline interpolace

Spline interpolace

Spline interpolace

Pojďme se seznámit s algoritmem programu. 1. Vypočítejte hodnoty a 2. Na základě těchto hodnot vypočítejte průběžné koeficienty a o. 3. Na základě získaných údajů vypočítáme koeficienty 4...

Matematické modelování technických objektů

Vestavěné funkce MathCAD umožňují interpolaci pro kreslení křivek různého stupně složitosti prostřednictvím experimentálních bodů. Lineární interpolace...

Metody aproximace funkcí

Na každém segmentu je interpolační polynom roven konstantě, konkrétně levé nebo pravé hodnotě funkce. Pro levou po částech lineární interpolaci F(x)= fi-1, pokud xi-1 ?x

Metody aproximace funkcí

Na každém intervalu je funkce lineární Fi(x)=kix+li. Hodnoty koeficientů se zjistí splněním interpolačních podmínek na koncích segmentu: Fi(xi-1)=fi-1, Fi(xi-1)=fi. Dostaneme soustavu rovnic: kixi-1+ li= fi-1, kixi+ li= fi, odkud najdeme ki=li= fi- kixi...

Metody řešení soustavy lineárních rovnic. Interpolace

Vyjádření problému interpolace. Na intervalu je uvedena soustava bodů (uzlů interpolace) xi, i=0,1,…,N; A? x já? b, a hodnoty neznámé funkce v těchto uzlech fn i=0,1,2,…,N. Lze nastavit následující úlohy: 1) Sestrojte funkci F (x)...

Konstrukce matematického modelu popisujícího proces řešení diferenciální rovnice

3.1 Konstrukce Lagrangeova interpolačního polynomu a kondenzace hodnot Samozřejmou metodou řešení tohoto problému je výpočet hodnot ѓ(x) pomocí analytických hodnot funkce ѓ. Za tímto účelem - dle prvotních informací...

Pokud jsou to mocniny (1, x, x2, ..., xn), pak mluvíme o algebraické interpolaci a funkce se nazývá interpolační polynom a značí se: (4) Pokud () (5), pak můžeme sestrojte interpolační polynom stupně n a navíc pouze jeden...

Praktická aplikace interpolace hladkých funkcí

Uvažujme příklad interpolace pro prvky množiny. Pro jednoduchost a stručnost vezměme =[-1;1], . Nechť se body od sebe liší. Položme si následující problém: (12) sestrojte polynom, který splňuje tyto podmínky...

Aplikace numerických metod při řešení matematických problémů

Numerické metody

Takže, jak bylo uvedeno výše, úkolem interpolace je najít polynom, jehož graf prochází danými body. Nechť je funkce y=f(x) specifikována pomocí tabulky (Tabulka 1)...

Numerické metody řešení matematických úloh

Křivky a plochy, se kterými se setkáváme v praktických úlohách, mají často dosti složitý tvar, který neumožňuje univerzální analytickou úlohu jako celek využívající elementární funkce. Proto jsou sestaveny z relativně jednoduchých hladkých fragmentů - segmentů (křivek) nebo řezů (plochy), z nichž každý lze celkem uspokojivě popsat pomocí elementárních funkcí jedné nebo dvou proměnných. V tomto případě je zcela přirozené vyžadovat, aby hladké funkce, které se používají ke konstrukci dílčích křivek nebo ploch, měly podobný charakter, například by to měly být polynomy stejného stupně. A aby byla výsledná křivka či plocha dostatečně hladká, je třeba dávat pozor především na to, kde se odpovídající fragmenty spojují. Stupeň polynomů se volí z jednoduchých geometrických úvah a je zpravidla malý. Pro plynulou změnu tečny podél celé složené křivky stačí popsat spojené křivky pomocí polynomů třetího stupně, kubických polynomů. Koeficienty takových polynomů lze vždy volit tak, aby zakřivení příslušné složené křivky bylo spojité. Kubické splajny, které vznikají při řešení jednorozměrných problémů, lze přizpůsobit konstrukci fragmentů kompozitních ploch. A zde se bikubické splajny objevují zcela přirozeně, popsané pomocí polynomů třetího stupně v každé ze dvou proměnných. Práce s takovými splajny vyžaduje podstatně větší množství výpočtů. Správně organizovaný proces však umožní v maximální míře zohlednit neustále se zvyšující možnosti výpočetní techniky. Spline funkce Nechte na segmentu, tedy Remark. Udává to index (t) čísel a^. že množina koeficientů, která určuje funkci 5(x) na každém dílčím segmentu D je různá. Na každém ze segmentů D1 je spline 5(x) polynom stupně p a je na tomto segmentu určen koeficientem p + 1. Celkové dílčí segmenty - pak. To znamená, že ke kompletnímu určení splajnu je nutné najít (p + 1)pak podmínka) znamená spojitost funkce 5(x) a jejích derivací ve všech vnitřních uzlech sítě w. Počet takových uzlů je m - 1. Pro nalezení koeficientů všech polynomů jsou tedy získány podmínky (rovnice) p(m - 1). Pro úplnou definici splajnu není dostatek podmínek (rovnic) Výběr dalších podmínek je určen povahou uvažovaného problému a někdy jednoduše přáním uživatele. TEORIE SPLINEU příklady řešení Interpolační a vyhlazovací problémy se nejčastěji zvažují, když je nutné sestrojit jeden nebo druhý spline z daného pole bodů v rovině Interpolační problémy vyžadují, aby spline graf procházel body, což vyžaduje m + 1 navíc podmínky (rovnice) na jeho koeficientech. Zbývající podmínky (rovnice) p - 1 pro jednoznačnou konstrukci spline jsou nejčastěji specifikovány ve formě hodnot dolních derivací spline na koncích uvažovaného segmentu [a, 6] - hranice ( okrajové) podmínky. Schopnost vybrat různé okrajové podmínky vám umožňuje konstruovat splajny s různými vlastnostmi. V úlohách vyhlazování je spline konstruován tak, že jeho graf prochází v blízkosti bodů (i""Y"), * = 0, 1,..., t, a nikoli skrz ně. Míru této blízkosti lze definovat různými způsoby, což vede k významné rozmanitosti vyhlazovacích splajnů. Popsané možnosti výběru při konstrukci spline funkcí nevyčerpávají veškerou jejich rozmanitost. A pokud byly zpočátku uvažovány pouze po částech polynomiální spline funkce, pak jak se rozsah jejich aplikací rozšiřoval, začaly se objevovat spline, „slepené“ z jiných elementárních funkcí. Interpolační kubické splajny Výrok interpolačního problému Nechť je dána mřížka w na segmentu [a, 6). Sestrojte hladkou funkci na segmentu (a, 6], který nabývá zadaných hodnot v uzlech mřížky o), tj. Poznámka: Formulovaný interpolační problém spočívá v obnovení hladké funkce specifikované v tabulce (obr. 2). Je zřejmé, že takový problém má mnoho různých řešení Vložením dalších podmínek na konstruovanou funkci je možné dosáhnout potřebné jedinečnosti V aplikacích je často potřeba aproximovat funkci definovanou analyticky pomocí funkce s předepsanou dostatečně dobrou vlastnosti, například v případech, kdy jsou hodnoty dané funkce /(x) počítány v bodech segment [a, 6] je spojen se značnými obtížemi a/nebo daná funkce /(x) nemá požadovanou hladkost, je vhodné použít jinou funkci, která by danou funkci docela dobře aproximovala a byla by zbavena svých nevýhod Problém interpolace funkce na segmentu [a, 6] hladká funkce a(x), koincidující v uzlech mřížky w s danou funkcí /(x). Definice interpolačního kubického splajnu Interpolační kubický splajn S(x) na síti w je funkce, která 1) na každém ze segmentů je polynom třetího stupně, 2) je dvakrát spojitě diferencovatelný na segmentu [a, b ], tedy patří do třídy C2[ a, 6], a 3) splňuje podmínky Na každém ze segmentů je spline S(x) polynom třetího stupně a je na tomto segmentu určen čtyřmi koeficienty. . Celkový počet segmentů je m To znamená, že pro úplné definování splajnu je potřeba najít 4m čísel. Podmínka znamená spojitost funkce S(x) a jejích derivací S"(x) a 5". (x) ve všech vnitřních uzlech sítě w. Počet takových uzlů je m - 1. Pro nalezení koeficientů všech polynomů jsou tedy získány další 3 (m - 1) podmínky (rovnice). Společně s podmínkami (2) se získají podmínky (rovnice). Okrajové (hranové) podmínky Dvě chybějící podmínky jsou specifikovány ve formě omezení hodnot splajnu a/nebo jeho derivací na koncích intervalu [a, 6]. Při konstrukci interpolačního kubického splajnu se nejčastěji používají následující čtyři typy okrajových podmínek. A. Okrajové podmínky 1. typu. - na koncích intervalu [a, b] jsou uvedeny hodnoty první derivace požadované funkce. B. Okrajové podmínky 2. typu. - na koncích intervalu (a, 6) jsou uvedeny hodnoty druhé derivace požadované funkce. B. Okrajové podmínky 3. typu. se nazývají periodické. Splnění těchto podmínek je přirozené vyžadovat v případech, kdy je interpolovaná funkce periodická s periodou T = b-a. D. Okrajové podmínky 4. typu. vyžadují zvláštní komentář. Komentář. U vnitřních sepsích uzlů je třetí derivace funkce S(x), obecně řečeno, nespojitá. Počet nespojitostí třetí derivace však může být snížen pomocí podmínek typu 4. V tomto případě bude sestrojený splajn spojitě diferencovatelný třikrát na intervalech Konstrukce interpolačního kubického splajnu Popišme si metodu výpočtu koeficientů kubického splajnu, ve kterém je počet určovaných veličin roven. Na každém z intervalů se hledá interpolační spline funkce v následujícím tvaru Zde TEORIE SPLINEU příklady řešení a čísel jsou řešením soustavy lineárních algebraických rovnic, jejichž tvar závisí na typu okrajových podmínek. Pro okrajové podmínky typu 1 a 2 má tento systém následující podobu, kde koeficienty závisí na volbě okrajových podmínek. Okrajové podmínky 1. typu: Okrajové podmínky 2. typu: V případě okrajových podmínek 3. typu se systém určování čísel píše takto: Počet neznámých v poslední soustavě je roven mn, jelikož z podmínek periodicity vyplývá, že po = nm. Pro okrajové podmínky 4. typu má soustava pro určování čísel tvar kde Na základě nalezeného řešení soustavy lze pomocí vzorců určit čísla po a n Důležitá poznámka. Matice všech tří lineárních algebraických systémů jsou diagonálně dominantní matice. Matice nejsou singulární, a proto má každý z těchto systémů jedinečné řešení. Teorém. Interpolační kubický splajn, který splňuje podmínky (2) a okrajovou podmínku jednoho ze čtyř výše uvedených typů, existuje a je jedinečný. Konstruovat interpolační kubický splajn tedy znamená najít jeho koeficienty Když jsou spline koeficienty nalezeny, lze hodnotu splajnu S(x) v libovolném bodě segmentu [a, b] najít pomocí vzorce (3). . Pro praktické výpočty je však vhodnější následující algoritmus pro zjištění hodnoty 5(g). Nechť x 6 [x", Nejprve se pomocí vzorců vypočítají hodnoty A a B a pak se zjistí hodnota 5(x): Použití tohoto algoritmu výrazně snižuje výpočetní náklady na určení hodnoty. Tipy pro uživatel Volba okrajových (hranových) podmínek a interpolačních uzlů umožňuje do určité míry ovládat vlastnosti interpolačních splajnů. A. Výběr okrajových (okrajových) podmínek. Volba okrajových podmínek je jedním z ústředních problémů interpolačních funkcí. Zvláště důležité je to v případě, kdy je potřeba zajistit vysokou přesnost aproximace funkce f(x) pomocí spline 5(g) poblíž konců segmentu [a, 6). Hraniční hodnoty mají znatelný vliv na chování spline 5(g) v blízkosti bodů a a b a tento vliv rychle slábne, jak se od nich vzdalujeme. Volba okrajových podmínek je často určena dostupností dalších informací o chování aproximované funkce f(x). Pokud jsou na koncích segmentu (a, 6) známy hodnoty první derivace f"(x), pak je přirozené použít okrajové podmínky 1. typu. Pokud jsou hodnoty druhé derivace f"(x) jsou známy na koncích segmentu [a, 6], pak je přirozené použití okrajových podmínek typu 2. Pokud existuje volba mezi okrajovými podmínkami typu 1 a 2, pak by měla být dána přednost podmínkám typu 1. Pokud je f(x) periodická funkce, měli bychom se zastavit u okrajových podmínek typu 3. Pokud nejsou k dispozici další informace o chování aproximované funkce, často se používají tzv. přirozené okrajové podmínky Je však třeba mít na paměti, že při takové volbě okrajových podmínek je přesnost aproximace funkce f(. x) splinem S(x) v blízkosti konců segmentu (a, ft] prudce klesá. Někdy se používají okrajové podmínky 1. nebo 2. typu, ale ne s přesnými hodnotami odpovídajících derivací, ale s jejich rozdílové aproximace Přesnost tohoto přístupu je nízká Praktické zkušenosti výpočtů ukazují, že v uvažované situaci je to nejvhodnější volba 4. typu. B. Výběr interpolačních uzlů. Pokud má třetí derivace f""(x) funkce diskontinuitu v některých bodech segmentu [a, b], pak by pro zlepšení kvality aproximace měly být tyto body zahrnuty do počtu interpolačních uzlů. Pokud je druhá derivace /"(x) nespojitá, pak aby se zabránilo oscilaci splajnu v blízkosti bodů nespojitosti, je nutné provést speciální opatření. Typicky se interpolační uzly volí tak, aby body nespojitosti druhé derivace padaly uvnitř intervalu \xif), tak, že hodnotu a lze zvolit pomocí numerického experimentu (často stačí nastavit a = 0,01). (x) je nespojitý. Jako jeden z nejjednodušších můžeme navrhnout toto: rozdělte aproximační segment na intervaly, kde je derivace spojitá, a na každém z těchto intervalů sestrojte spline. Výběr interpolační funkce (pro a proti) Přístup 1. Lagrangeův interpolační polynom Pro dané pole SPLINE THEORY příklady řešení (obr. 3) je Lagrangeův interpolační polynom určen vzorcem Je vhodné zvážit vlastnosti Lagrangeova interpolačního polynomu ze dvou protilehlých pozic, přičemž hlavní výhody probereme odděleně od nevýhody. Hlavní výhody 1. přístupu: 1) graf Lagrangeova interpolačního polynomu prochází každým bodem pole, 2) sestrojená funkce je snadno popsána (počet koeficientů Lagrangeova interpolačního polynomu na mřížce, který se má určit, je rovná se m + 1), 3) sestrojená funkce má spojité derivace libovolného řádu, 4) interpolační polynom je jednoznačně určen daným polem. Hlavní nevýhody 1. přístupu: 1) stupeň Lagrangeova interpolačního polynomu závisí na počtu uzlů mřížky a čím větší je toto číslo, tím vyšší je stupeň interpolačního polynomu a tím více výpočtů, 2) změna alespoň jednoho bodu v poli vyžaduje kompletní přepočet koeficientů Lagrangeova interpolačního polynomu, 3) přidání nového bodu do pole zvýší stupeň Lagrangeova interpolačního polynomu o jednu a také vede k úplnému přepočtu jeho koeficientů. , 4) s neomezeným zjemňováním sítě se stupeň Lagrangeova interpolačního polynomu neomezeně zvyšuje. Chování Lagrangeova interpolačního polynomu s neomezeným zjemňováním sítě obecně vyžaduje zvláštní pozornost. Komentář A. O aproximaci spojité funkce polynomem. Je známo (Weierstrass, 1885), že libovolnou spojitou (a ještě více hladkou) funkci na intervalu lze na tomto intervalu aproximovat podle potřeby pomocí polynomu. Popišme tuto skutečnost jazykem vzorců. Nechť f(x) je funkce spojitá na intervalu [a, 6]. Pak pro libovolné e > 0 existuje polynom Є(x) takový, že pro libovolné x z intervalu [a, 6] bude nerovnost splněna (obr. 4) Všimněte si, že polynomy dokonce stejného stupně, které aproximují funkci f(x) se zadanou přesností je jich nekonečně mnoho. Sestrojme mřížku w na úsečce [a, 6]. Je zřejmé, že jeho uzly se obecně neshodují s průsečíky grafů polynomu Pn(x) a funkce f(x) (obr. 5). Proto pro danou síť není polynom Pn(x) interpolací. Když je spojitá funkce aproximována Jla-graczovým interpolačním polynomem, její graf nejenže nemusí být blízko grafu funkce f(x) v každém bodě segmentu [a, b), ale může se odchýlit od tuto funkci podle potřeby. Uveďme dva příklady. Příklad 1 (Rung, 1901). Při neomezeném nárůstu počtu uzlů pro funkci na intervalu [-1, 1] je splněna limitní rovnost (obr. 6) Příklad 2 (Beristein, 1912). Posloupnost Lagrangeových interpolačních polynomů konstruovaných na jednotných mřížkách pro spojitou funkci /(x) = |x| na segmentu s rostoucím počtem uzlů m neinklinuje k funkci /(x) (obr. 7). Přístup 2. Po částech lineární interpolace Pokud se opustí hladkost interpolované funkce, poměr mezi počtem výhod a počtem nevýhod se může výrazně změnit směrem k první. Sestrojme po částech lineární funkci postupným spojováním bodů (xit y) úsečkami (obr. 8). Hlavní výhody 2. přístupu: 1) graf po částech lineární funkce prochází každým bodem pole, 2) sestrojená funkce je snadno popsána (počet koeficientů odpovídajících lineárních funkcí, které mají být určeny pro mřížku ( 1) je 2 m), 3) konstruovaná funkce je definována daným polem jednoznačně, 4) stupeň polynomů použitých k popisu interpolační funkce nezávisí na počtu uzlů mřížky (rovná se 1), 5) mění se jeden bod v poli vyžaduje výpočet čtyř čísel (koeficienty dvou přímých spojnic vycházejících z nového bodu), 6) přidání dalšího bodu do pole vyžaduje výpočet čtyř koeficientů. Po částech lineární funkce se také chová docela dobře při zjemňování sítě. Hlavní nevýhoda 2. přístupu: aproximace po částech lineární funkce není hladká: první derivace trpí nespojitostí v uzlech mřížky (interpolační uši). Přístup 3. Spline interpolace Navržené přístupy lze kombinovat tak, aby byl zachován počet vyjmenovaných výhod obou přístupů při současném snížení počtu nevýhod. Toho lze dosáhnout vytvořením hladké interpolační spline funkce stupně p. Hlavní výhody 3. přístupu: 1) graf sestrojené funkce prochází každým bodem pole, 2) sestrojená funkce se dá poměrně snadno popsat (počet koeficientů odpovídajících polynomů, které se mají pro mřížku určit ( 1) se rovná 3) sestrojená funkce je jednoznačně definována daným polem, 4) polynomy stupňů nezávisí na počtu uzlů mřížky, a proto se při zvětšování nemění, 5) sestrojená funkce má spojitou derivace do řádu p - 1 včetně, 6) sestrojená funkce má dobré aproximační vlastnosti. Stručné informace. Navrhovaný název – splajn – není náhodný – hladké po částech polynomické funkce, které jsme zavedli, a kreslení splajnů spolu úzce souvisí. Uvažujme flexibilní ideálně tenké pravítko procházející referenčními body pole v rovině (x, y). Podle Bernoulli-Eulerova zákona má linearizovaná rovnice zakřiveného pravítka tvar, kde S(x) je ohyb, M(x) je ohybový moment, který se lineárně mění od podpory k podpoře, E1 je tuhost pravítka . Funkce S(x), která popisuje řádky vzorců, je polynomem třetího stupně mezi každým a dvěma sousedními body pole (podporami) a je dvakrát spojitě diferencovatelná v celém intervalu (a, 6). Komentář. 06 interpolace spojité funkce Na rozdíl od Lagrangeových interpolačních polynomů posloupnost interpolačních kubických splajnů na jednotné síti vždy konverguje k interpolační spojité funkci a jak se diferenciální vlastnosti této funkce zlepšují, zvyšuje se rychlost konvergence. Příklad. Pro funkci dává kubický spline na mřížce s počtem uzlů m = 6 aproximační chybu stejného řádu jako interpolační polynom Ls(z) a na mřížce s počtem uzlů m = 21 je tato chyba tak malý, že v měřítku běžné knižní kresby to prostě nejde zobrazit (obr. 10) (interpolační polynom 1>2o(r) dává v tomto případě chybu asi 10 000 J). Vlastnosti interpolačního kubického splajnu A. Alproximační vlastnosti kubického splajnu. Aproximační vlastnosti interpolačního splajnu závisí na hladkosti funkce f(x) - čím vyšší je hladkost interpolované funkce, tím vyšší je řád aproximace a při zpřesňování sítě tím vyšší rychlost konvergence. Pokud je interpolovaná funkce f(x) spojitá na intervalu Pokud má interpolovaná funkce f(x) spojitou první derivaci na intervalu [a, 6], tedy interpolační splajn, který splňuje okrajové podmínky 1. nebo 3. typu, pak pro h O máme V tomto případě nejen, že splajn konverguje k interpolované funkci, ale také derivace splajnu k derivaci této funkce. Pokud splajn S(x) aproximuje funkci f(x) na segmentu [a, b] a jeho první a druhá derivace aproximují funkci B, resp. Interpolační kubický splajn má další užitečnou vlastnost. Zvažte následující příklad. příklad. Sestrojte funkci /(x), která minimalizuje funkcionál na třídě funkcí z prostoru C2, jehož grafy procházejí body pole Mezi všemi funkcemi procházejícími referenčními body (x;, /(x,. )) a patřící do zadaného prostoru, je to kubický splajn 5(x), splňující okrajové podmínky, dodává extrému (minimum) funkcionálu Poznámka 1. Často je tato extrémní vlastnost brána jako definice interpolační kubiky spline. Poznámka 2. Je zajímavé poznamenat, že interpolační kubický splajn má výše popsanou extrémní vlastnost pro velmi širokou třídu funkcí, konkrétně pro třídu |o, 5]. 1.2. Vyhlazování kubických splajnů O formulaci vyhlazovacího problému Nechť je uvedena mřížka a množina čísel Komentář k počátečním datům V praxi se často musíme vypořádat s případem, kdy jsou hodnoty y v poli specifikovány s nějakým chyba. Ve skutečnosti to znamená, že pro každý je specifikován interval a libovolné číslo z tohoto intervalu lze vzít jako hodnotu y, . Hodnoty y je vhodné interpretovat například jako výsledky měření nějaké funkce y(x) pro dané hodnoty proměnné x, obsahující náhodnou chybu. Při řešení problému obnovy funkce z takto „experimentálních“ hodnot je stěží vhodné použít interpolaci, protože interpolační funkce bude poslušně reprodukovat bizarní oscilace způsobené náhodnou složkou v poli (y,). Přirozenější přístup je založen na vyhlazovací proceduře navržené tak, aby nějakým způsobem redukovala prvek náhodnosti ve výsledku měření. Obvykle je v takových úlohách potřeba najít funkci, jejíž hodnoty pro x = x, * = 0, 1,.... m by spadali do příslušných intervalů a která by navíc měla docela dobré vlastnosti. Například by měl spojitou první a druhou derivaci nebo by jeho graf nebyl příliš silně zakřivený, to znamená, že by neměl silné oscilace. Problém tohoto druhu také nastává, když je za daného (přesného) pole nutné sestrojit funkci, která neprochází danými body, ale v jejich blízkosti a navíc se celkem plynule mění. Jinými slovy, zdálo se, že požadovaná funkce dané pole spíše vyhlazuje, než aby jej interpolovala. Nechť je dána mřížka w a dvě sady čísel příklady řešení úlohy. Sestrojte hladkou funkci na segmentu [a, A], jehož hodnoty v uzlech mřížky u se liší od čísel y o dané hodnoty. Formulovaný problém vyhlazování je obnovení hladká funkce specifikovaná v tabulce. Je jasné, že takový problém má mnoho různých řešení. Kladením dalších podmínek na konstruovanou funkci lze dosáhnout potřebné jednoznačnosti. Definice vyhlazovacího kubického splajnu Vyhlazovací kubický splajn S(x) na mřížce w je funkcí, která 1) na každém ze segmentů je polynom třetího stupně, 2) je na segmentu dvakrát spojitě diferencovatelný [a, 6 ], tedy patří do třídy C2 [a , b], 3) dodává minimum do funkcionálu, kde jsou daná čísla, 4) splňuje okrajové podmínky jednoho ze tří níže uvedených typů. Okrajové (okrajové) podmínky Okrajové podmínky jsou specifikovány ve formě omezení hodnot splajnu a jeho derivací na hraničních uzlech sítě w. A. Okrajové podmínky typu 1. - na koncích intervalu [a, b) jsou uvedeny hodnoty první derivace požadované funkce. Okrajové podmínky typu 2. - druhé derivace požadované funkce na koncích intervalu (a, b] jsou rovny nule. B. Okrajové podmínky 3. typu nazýváme periodické. Věta. Kubický spline S(x), minimalizující funkcionál (4) a splňující okrajové podmínky jednoho z výše uvedených tří typů, je jednoznačně definován Definice Kubický splajn, který minimalizuje funkcionál J(f) a splňuje okrajové podmínky typu i, se nazývá vyhlazovací spline typu i. Poznamenejte tento segment čtyřmi koeficienty. To znamená, že pro úplné určení spline je potřeba najít 4m čísla derivací ve všech vnitřních uzlech mřížky o ". Počet takových uzlů je m - 1. Pro výpočet koeficientů všech polynomů tedy získáme 3(m - 1) podmínky (rovnice). Funkce se hledá v následující tvar zde a čísla a jsou řešením soustavy lineárních algebraických rovnic, jejichž tvar závisí na typu okrajových podmínek. Nejprve si popišme, jak se nacházejí hodnoty n*. Pro okrajové podmínky 1. a 2. typu je soustava lineárních rovnic pro určení hodnot Hi zapsána v následujícím tvaru, kde jsou známá čísla). Koeficienty závisí na volbě okrajových podmínek. Okrajové podmínky 1. typu: Okrajové podmínky 2. typu: V případě okrajových podmínek 3. typu je systém pro určování čísel napsán následovně: a všechny koeficienty se počítají podle vzorců (5) (hodnoty s indexy k a m ​​+ k jsou považovány za stejné: Důležitá* poznámka. Matice systémů nejsou degenerované a proto má každý z těchto systémů jedinečné řešení. Jsou-li nalezena čísla n, -, pak se veličiny snadno určují pomocí vzorců, kde V případě periodických okrajových podmínek je volba jeho koeficientů p, - obsažena ve funkcionálu (4). umožňuje do určité míry ovládat vlastnosti vyhlazovacích splajnů. Pokud se vše a vyhlazovací spline ukáže jako interpolace. To zejména znamená, že čím přesněji jsou hodnoty specifikovány, tím menší se očekává, že budou odpovídající váhové koeficienty. Pokud je nutné, aby splajn procházel bodem (x^, Vk), pak jemu odpovídající váhový faktor p\ by měl být nastaven na nulu. V praktických výpočtech je nejdůležitější volba hodnot pi-Let D, - chyba měření hodnoty y,. Pak je přirozené vyžadovat, aby vyhlazovací splajn splňoval podmínku nebo, což je stejné V nejjednodušším případě lze váhové koeficienty pi zadat například ve tvaru - kde c je nějaká dostatečně malá konstanta. Tato volba vah p však neumožňuje použití „koridoru“ kvůli chybám v hodnotách y, -. Racionálnější, ale také pracnější algoritmus pro určování hodnot p může vypadat takto. Pokud jsou hodnoty nalezeny v fc-té iteraci, pak se předpokládá, že kde e je malé číslo, které je vybráno experimentálně s ohledem na bitovou mřížku počítače, hodnoty D a přesnost řešení soustavy lineárních algebraických rovnic. Pokud je při fc-té iteraci v bodě i porušena podmínka (6), pak poslední vzorec zajistí snížení odpovídajícího váhového koeficientu p,. Pokud pak při další iteraci zvýšení p povede k úplnějšímu využití „koridoru“ (6) a nakonec k hladšímu se měnícímu spline. Trocha teorie A. Zdůvodnění vzorců pro výpočet koeficientů interpolačního kubického splajnu. Zaveďme označení, kde m, jsou v současnosti neznámé veličiny. Jejich počet je roven m + 1. Spline zapsaný ve tvaru kde splňuje podmínky interpolace a je spojitý na celém intervalu [a, b\: uvedením do vzorce dostaneme, resp spojitá první derivace na intervalu [a, 6]: Diferencováním vztahu (7) a jeho uvedením získáme odpovídající vlastně. Ukažme, že čísla m lze zvolit tak, aby splajnová funkce (7) měla spojitou druhou derivaci na intervalu [a, 6]. Vypočítejme druhou derivaci splajnu na intervalu: V bodě x, - 0 (v t = 1) máme Vypočítejme druhou derivaci splajnu na intervalu V bodě máme Z podmínky spojitosti křivky druhá derivace ve vnitřních uzlech mřížky a; získáme vztah m - 1 kde Připočteme-li k těmto m - 1 rovnicím další dvě, které vyplývají z okrajových podmínek, získáme soustavu m + 1 lineárních algebraických rovnic s m + I neznámými miy i = 0, 1. ... , m. Systém rovnic pro výpočet hodnot rsh v případě okrajových podmínek 1. a 2. typu má tvar kde (okrajové podmínky 1. typu), (okrajové podmínky 2. typu). Pro periodické okrajové podmínky (okrajové podmínky typu 3) je síť o; rozšířit o další uzel a předpokládat Pak bude mít systém pro určování hodnot σ* tvarovou spojitost na druhém a (tém - !)-tém uzlu mřížky. Máme Z posledních dvou vztahů získáme chybějící dvě rovnice, které odpovídají okrajovým podmínkám 4. typu: Vyloučením neznámého goo z rovnic a neznámého pc z rovnic získáme soustavu rovnic. Všimněte si, že počet neznámých v tomto systému je th - I. 6. Zdůvodnění vzorců pro výpočet účinnosti vyhlazovacího subichess spline. Uveďme si zápis, kde Zi a nj jsou aktuálně neznámé veličiny. Jejich počet je 2m + 2. Spline funkce zapsaná ve tvaru je spojitá přes celý interval 8), měla spojitou první derivaci na intervalu [a, 6] Vypočítejme první derivaci spline S(x). na intervalu: V bodě x^ - 0 (v t = 1) máme Vypočítejme první derivaci splajnu 5(x) na intervalu: V bodě máme Z podmínky spojitosti první derivace spline u vnitřních uzlů sítě a --> získáme vztah m - 1 Tento vztah je vhodně zapsán v maticovém tvaru Kromě toho se používá spline na intervalu [a, 6). má spojitou druhou derivaci: derivováním vztahu (8) a jeho uvedením získáme, resp., maticový vztah získáme z podmínky pro minimum funkcionálu (4). Máme Poslední dvě maticové rovnosti lze považovat za lineární systém 2m + 2 lineárních algebraických rovnic pro 2m + 2 neznámé. Nahradíme-li sloupec r v první rovnosti jeho výrazem získaným ze vztahu (9), dostaneme se k maticové rovnici SPLINE THEORY příklady řešení pro určení sloupce M. Tato rovnice má jedinečné řešení díky tomu, že matice A + 6HRH7 je vždy nezdegenerované. Po jeho nalezení můžeme snadno identifikovat město Eamshine. Prvky závitových magolových matic A a H jsou určeny pouze parametry mřížky a (s kroky hi) a nezávisí na hodnotách y^. Lineární prostor kubických splajnů Množina kubických splajnů sestrojená na segmentu [a, 6) podél uzlu sítě wcra+l je lineární prostor o rozměru m + 3: 1) součet dvou kubických splajnů sestrojených na síti u >, a součinem kubické splajny , sestrojené na mřížce a> libovolným číslem tajněji, jsou kubické splajny sestrojené na této mřížce, 2) jakákoli kubická splajna sestrojená na mřížce a z uzlu je zcela určena m + 1 hodnota hodnot y" v těchto uzlech a dvě okrajové podmínky - jen + 3 parametry. Volbou báze v tomto prostoru sestávajícím z m + 3 lineárně nezávislých splajnů můžeme jedinečným způsobem zapsat libovolný kubický splajn a(x) jako jejich lineární kombinaci. Komentář. Tento typ přiřazení spline je ve výpočetní praxi velmi rozšířen. Obzvláště výhodná je databáze skládající se z tzv. kubických B-splines (základní neboli základní spline). Použití D-splines může výrazně snížit požadavky na paměť počítače. L-drážky. B-spline nulového stupně, sestrojený na číselné ose podél mřížky w, se nazývá vidlová funkce B-spline stupně k ^ I, sestrojený na číselné ose podél mřížky u, je určen pomocí rekurentu. vzorec Grafy B-spline prvního stupně B, -1"(g) a druhého v\7\x) jsou uvedeny na obr. 11 a 12. B-spline libovolného stupně k se může lišit od nuly pouze na určitém segmentu (definovaném k + 2 uzly B, -3* (i) bylo odlišné od nuly na segmentu z,-+2]. Uvádíme vzorec pro kubický splajn třetího stupně pro případ jednotné sítě (s krokem A) V ostatních případech je typický graf kubické B-spline znázorněn na obr. 13. Výpůjčkou* je funkce a) dvakrát spojitě derivovatelná na intervalu, tedy patří do třídy C2[a, "), a b) se liší od nuly pouze ve čtyřech po sobě jdoucích intervalech (Doplňme mřížku w pomocnými uzly branými zcela libovolně. Rozšířenou sítí w* můžeme sestrojit rodina m + 3 kubických B-spline: Tato rodina tvoří základ v prostoru kubických splajnů na segmentu (a, b]. Tedy libovolný kubický splajn S(z), sestrojený na segmentu |b, 6] mřížce o; izm+1 uzel, lze na tomto segmentu reprezentovat ve formě lineární kombinace. Podle podmínek úlohy jsou koeficienty ft tohoto rozšíření určeny jednoznačně. ... V případě, že jsou uvedeny hodnoty y* funkce na uzlech mřížky a hodnoty y o a Ym první derivace funkce na koncích mřížky (problém interpolace s hranicí podmínky prvního druhu), tyto koeficienty se vypočítají ze soustavy následujícího tvaru Po eliminaci hodnot b- i a &m+i získáme lineární soustavu s neznámými 5q, ..., bm a a tři -dimenzionální matice zajišťuje diagonální dominanci a tedy možnost použití metody sweep k jejímu vyřešení. Ve srovnání s algoritmy popsanými v části 1.1 nám použití R-spline v * problémech s interpolací umožňuje snížit * množství uložených informací, to znamená výrazně snížit požadavky na paměť počítače, i když to vede ke zvýšení počet operací. Konstrukce spline křivek pomocí spline funkcí Výše ​​jsme uvažovali o polích, jejichž body byly očíslovány tak, aby jejich úsečky tvořily přísně rostoucí sekvenci. Například případ znázorněný na Obr. 14, kdy různé body pole mají stejnou úsečku, nebylo povoleno. Tato okolnost předurčila jak volbu třídy aproximačních křivek (dopravních funkcí), tak způsob jejich konstrukce. Výše navržená metoda však umožňuje poměrně úspěšně sestrojit interpolační křivku v obecnějším případě, kdy spolu číslování bodů pole a jejich umístění v rovině zpravidla nesouvisí (obr. 15). Navíc při zadání úkolu sestrojit interpolační křivku můžeme dané pole považovat za nerovinné, to znamená, že je jasné, že k vyřešení tohoto obecného problému je nutné výrazně rozšířit třídu přípustných křivek, včetně uzavřených křivky, křivky s vlastními průsečíky a prostorové křivky. Takové křivky je vhodné popsat pomocí parametrických rovnic, které požadujeme. funkce navíc musí mít dostatečnou hladkost, patří například do třídy C1 [a, /0] nebo třídy Pro nalezení parametrických rovnic křivky, která postupně prochází všemi body pole, postupujte následovně. 1. krok. V libovolném segmentu)