Splajny

V matematickém podoblasti numerické analýzy je spline po částech diferencovatelná křivka definovaná polynomy .

V interpolačních problémech se často používá spline interpolace, protože poskytuje podobné výsledky vyžadující pouze použití nízkostupňových polynomů , čímž se vyhne oscilacím , nežádoucím ve většině aplikací, které se vyskytují při interpolaci nízkostupňovými polynomy.

Pro aproximaci křivek se křivky používají k aproximaci komplikovaných tvarů. Jednoduchost reprezentace a výpočetní snadnost splajnů je činí populárními pro reprezentaci křivek v informatice , zejména v oblasti počítačové grafiky.

Původ

Základní teorii splajnů vyvinul ve 40. letech 20. století americký matematik rumunského původu Isaac Jacob Schoenberg (1903-1990).

Úvod

Termín "spline" se týká široké třídy funkcí, které se používají v aplikacích, které vyžadují interpolaci dat nebo vyhlazování křivek. Spline se používají k práci jak v jednom, tak v několika rozměrech. Funkce pro interpolaci spline jsou normálně určeny jako minimalizátory drsnosti podléhající řadě omezení.

V tomto článku budeme termínem „spline“ odkazovat na jeho omezenou verzi v jednom rozměru a polynomu, která se nejčastěji používá.

Lineární segmentová interpolace

Toto je nejjednodušší případ. V něm budeme interpolovat funkci f(x), ze které dostaneme počet N dvojic , kterými bude muset naše polynomiální funkce projít . Tato naše řada funkcí bude lineární, tedy se stupněm 1: tvaru . $(x,f(x))$ $P(x)$ $P(x)=ax+b$

Jednu z těchto funkcí definujeme pro každou dvojici sousedních bodů, až do celkového počtu funkcí, přičemž je nutně projdeme body, které je budou určovat, to znamená, že funkcí bude množina segmentů, které spojují po sobě jdoucí uzly; proto bude naše funkce v těchto bodech spojitá, ale nebude obecně diferencovatelná. $(N-1)$ $P(x)$

Příklad: Interpolujte pomocí splajnů v bodech, kde se rovná 1, 2 a 4 $f(x)=1/x$ $X$

$f(1)=1$
$f(2)=0,5$
$f(4)=0,25$

První segment musí spojit první dva body souřadnic a . Vzniká lineární systém dvou rovnic o dvou neznámých: $P_{1}(x)=ax+b$ $(1,1)$ $(2,0,5)$

(1) $1=a+b$
(dva) $0.5=2a+b$

Z (1) dostáváme:

$a=1-b$ (3)

Nahrazením (3) za (2) dostaneme:

$0.5=2(1-b)+b$

později

$b=1.5$

Nahrazením hodnoty (b) za (1) získáme:

$a=-0,5$

Z toho tedy vyplývá, že: Druhý segment musí spojit druhý bod s třetím bodem . Analogicky k tomu, co bylo provedeno pro , v případě získáme: $P_{1}(x)=-0,5x+1,5$ $P_{2}(x)=ax+b$ $(2,0,5)$ $(4,0,25)$ $P_{1}(x)$ $P_{2}(x)$

(1) $0.5=2a+b$
(dva) $0,25=4a+b$

$a=-0,125,b=0,75$

Později $P_{2}(x)=-0,125x+0,75$

Kvadratická segmentová interpolace

V tomto případě mají polynomy, pomocí kterých sestrojíme spline, stupeň 2. To znamená, že bude mít tvar $P(x)$ $P(x)=ax^{2}+bx+c$

Stejně jako v lineární segmentální interpolaci budeme mít rovnice (kde je počet bodů, nad kterými je funkce definována). Kvadratická interpolace zajistí, že funkce, kterou vygenerujeme po částech s různými, bude spojitá, protože pro výpočet koeficientů, které přizpůsobují polynomy bodům, určíme jako podmínky: $n-1$ $n$ $P(x)$

Nechte části funkce po částech procházet těmito body. To znamená, že dva , které obklopují ten, který chceme aproximovat, se rovnají v každém z těchto bodů. $P(x)$ $P_{n}(x)$ $f(x)$ $f(x)$

Že derivace v bodě vždy souhlasí pro obě "strany" po částech procházející tímto společným bodem.

To však nestačí a potřebujeme ještě jednu podmínku. Proč?. Pro každého máme 3 neznámé . V jednoduchém případě s definováním ve třech bodech a dvěma rovnicemi pro jeho aproximaci budeme mít celkem šest neznámých. Abychom to vyřešili, potřebovali bychom šest rovnic, ale budeme mít pouze pět: čtyři, které se rovnají hodnotě v každém bodě (dvě pro každý interval), a pátou rovnici derivace v bodě společném těmto dvěma . $P(x)$ $f(x)$ $P(x)$ $P(x)$ $f(x)$ $P(x)$

Je potřeba šestá rovnice, odkud pochází? To se obvykle provádí s hodnotou derivátu v určitém bodě, ke kterému je jeden z . $P(x)$

Kubická segmentová interpolace

V tomto případě má každý polynom , jehož prostřednictvím sestrojujeme splajny , stupeň 3. To znamená, že bude mít tvar $P(x)$ $[m,n]$ $P(x)=ax^{3}+bx^{2}+cx+d$

V tomto případě budeme mít čtyři neznámé pro každý interval a novou podmínku pro každý bod společný pro dva intervaly s ohledem na druhou derivaci: $(a,b,c,d)$

Nechte části funkce po částech procházet tímto bodem. To znamená, že dva , které obklopují ten, který chceme aproximovat, se rovnají v každém z těchto bodů. $P(x)$ $P_{n}(x)$ $f(x)$ $f(x)$

Že derivace v bodě vždy souhlasí pro obě "strany" po částech procházející tímto společným bodem.

Že druhá derivace v bodě vždy souhlasí pro obě „strany“ po částech procházející tímto společným bodem.

Jak lze odvodit při srovnání s případem kvadratických splajnů, nyní nám nebude chybět jedna, ale dvě rovnice (podmínky) pro počet neznámých, které máme.

Jak to opravit, určuje charakter kubických splajnů. Můžeme tedy použít:

Přirozené kubické splajny : Nejtypičtější forma. Druhá derivace se stane 0 pro první a poslední bod, na kterém je definována množina křivek, tedy body a v intervalu . $P$ $m$ $n$ $[m,n]$

Uveďte hodnoty druhé derivace y "ručně", v sadě splajnů definované v intervalu . $m$ $n$ $[m,n]$

Srovnejte hodnoty druhé derivace m a n v sadě spline definovaných na intervalu $[m,n]$

Předmět kubické splajny : První derivace P musí mít stejnou hodnotu jako první derivace funkce pro první a poslední bod, na kterém je definována množina splajnů, to znamená pro body ma n v intervalu [m, n].

Reference

Ferguson, James C, Multi-variable curve interpolation, J. ACM, sv. 11, č. 2, str. 221-228, duben 1964.
Ahlberg, Nielson a Walsh, The Theory of Splines and their Applications, 1967.
Birkhoff, Dynamika tekutin, výpočty reaktorů a reprezentace povrchu, v: Steve Nash (ed.), A History of Scientific Computation , 1990.
Bartels, Beatty a Barsky, Úvod do splajnů pro použití v počítačové grafice a geometrickém modelování, 1987.
Birkhoff a de Boor, Kusová polynomiální interpolace a aproximace, v: HL Garabedian (ed.), Proc. Symposium General Motors z roku 1964, str. 164–190. Elsevier, New York a Amsterdam, 1965.
Davis, B-splines and Geometric design , SIAM News, sv. 29, č. 5, 1997.
Epperson, History of Splines , NA Digest, sv. 98, č.p. 26, 1998.
Stoer & Bulirsch, Úvod do numerické analýzy. Springer-Verlag . p. 93-106. ISBN 0387904204
Schoenberg, Příspěvky k problému aproximace ekvidistantních dat analytickými funkcemi, Quart. Aplikace. Math., sv. 4, str. 45–99 a 112–141, 1946.
Young, Garrett Birkhoff a aplikovaná matematika, Notices of the AMS, sv. 44, č. 11, str. 1446–1449, 1997.
Chapra, Canale, "Numerické metody pro inženýry" 5. vydání.

Externí odkazy

Wikimedia Commons má kategorii médií pro Splines .