Splines

En type spline, en Bézier-kurve .

I det matematiske underfelt af numerisk analyse er en spline en stykkevis differentierbar kurve defineret af polynomier .

I interpolationsproblemer bruges spline-interpolation ofte, fordi det giver lignende resultater, der kun kræver brug af lavgradspolynomier , og dermed undgås de oscillationer , som er uønskede i de fleste applikationer, som findes ved interpolering med lavgradspolynomier.

Til kurvetilpasning bruges splines til at tilnærme komplicerede former. Enkelheden af repræsentation og beregningslette af splines gør dem populære til kurverepræsentation i datalogi , især inden for computergrafik.

Oprindelse

Den grundlæggende teori om splines blev udviklet i 1940'erne af den rumænskfødte amerikanske matematiker Isaac Jacob Schoenberg (1903-1990).

Introduktion

Udtrykket "spline" refererer til en bred klasse af funktioner, der bruges i applikationer, der kræver datainterpolation eller kurveudjævning. Splines bruges til at arbejde både i én og i flere dimensioner. Funktioner til spline-interpolation bestemmes normalt som ruhedsminimering under en række begrænsninger.

I denne artikel vil vi med udtrykket "spline" referere til dens begrænsede version i én dimension og polynomium, som er den mest almindeligt anvendte.

Lineær Segmental Interpolation

Dette er det enkleste tilfælde. I den skal vi interpolere en funktion f(x), hvorfra vi får et antal N par , som vores polynomiefunktion skal passere igennem . Denne række af vores funktioner vil være lineær, det vil sige med grad 1: af formen . $(x,f(x))$ $P(x)$ $P(x)=ax+b$

Vi vil definere en af disse funktioner for hvert par af tilstødende punkter, op til en total af funktioner, nødvendigvis at sende dem gennem de punkter, der skal bestemme dem, det vil sige, at funktionen vil være det sæt af segmenter, der forbinder på hinanden følgende noder; det er derfor vores funktion vil være kontinuerlig på disse punkter, men ikke differentierbar generelt. $(N-1)$ $P(x)$

Eksempel: Interpoler med splines på de punkter, hvor det er lig med 1, 2 og 4 $f(x)=1/x$ $x$

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

Det første segment skal forbinde de første to koordinatpunkter og . Et lineært system af to ligninger i to ubekendte opstår: $P_{1}(x)=ax+b$ $(1,1)$ $(2,0.5)$

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

Fra (1) får vi:

$a=1-b$ (3)

Ved at erstatte (3) i (2) får vi:

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

senere

$b=1.5$

Ved at erstatte værdien af (b) i (1), får vi:

$a=-0.5$

Derfor følger det, at: Det andet segment skal forbinde det andet punkt med det tredje punkt . Analogt med hvad der blev gjort for , får vi i tilfælde af : $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$
(to) $0.25=4a+b$

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

Senere $P_{2}(x)=-0,125x+0,75$

Kvadratisk segmental interpolation

I dette tilfælde har de polynomier , som vi konstruerer splinen igennem, grad 2. Det betyder, at den vil have formen $P(x)$ $P(x)=ax^{2}+bx+c$

Som i lineær segmental interpolation vil vi have ligninger (hvor er antallet af punkter, over hvilke funktionen er defineret). Den kvadratiske interpolation vil sikre, at den funktion, som vi genererer i stykker med de forskellige, vil være kontinuert, da vi for at beregne koefficienterne, der justerer polynomierne til punkterne, vil bestemme som betingelser: $n-1$ $n$ $P(x)$

Lad delene af den stykvise funktion passere gennem disse punkter. Det vil sige, at de to , der omgiver den , vi ønsker at tilnærme, er lig på hvert af disse punkter. $P(x)$ $P_{n}(x)$ $f(x)$ $f(x)$

At den afledede i et punkt altid stemmer overens for begge "sider" af den stykkevise funktion, der passerer gennem det fælles punkt.

Dette er dog ikke nok, og vi har brug for endnu en betingelse. Hvorfor?. Vi har 3 ubekendte for hver . I et simpelt tilfælde med defineret ved tre punkter og to ligninger for at tilnærme det, vil vi have seks ukendte i alt. For at løse dette ville vi have brug for seks ligninger, men vi vil kun have fem: fire, der sætter lighedstegn mellem værdien af ved hvert punkt (to for hvert interval), og den femte ved at sætte lighedstegn mellem den afledte i det punkt, der er fælles for de to. . $P(x)$ $f(x)$ $P(x)$ $P(x)$ $f(x)$ $P(x)$

En sjette ligning er nødvendig, hvor kommer den fra? Dette gøres normalt med værdien af den afledte på et tidspunkt, hvortil en af . $P(x)$

Cubic Segmental Interpolation

I dette tilfælde har hvert polynomium , som vi konstruerer Splines i , grad 3. Det betyder, at det vil have formen $P(x)$ $[m,n]$ $P(x)=ax^{3}+bx^{2}+cx+d$

I dette tilfælde vil vi have fire ubekendte for hvert interval , og en ny betingelse for hvert punkt, der er fælles for to intervaller, med hensyn til den anden afledede: $(a,b,c,d)$

Lad delene af den stykvise funktion passere gennem det punkt. Det vil sige, at de to , der omgiver den , vi ønsker at tilnærme, er lig på hvert af disse punkter. $P(x)$ $P_{n}(x)$ $f(x)$ $f(x)$

At den afledede i et punkt altid stemmer overens for begge "sider" af den stykkevise funktion, der passerer gennem det fælles punkt.

At den anden afledede i et punkt altid stemmer overens for begge "sider" af den stykkevise funktion, der passerer gennem det fælles punkt.

Som det kan udledes, når man sammenligner det med tilfældet med kvadratiske splines, kommer vi nu ikke til at mangle en men to ligninger (betingelser) for antallet af ukendte, vi har.

Hvordan man løser dette, bestemmer karakteren af de kubiske splines. Således kan vi bruge:

Naturlige kubiske splines : Den mest typiske form. Den anden afledede af bliver 0 for det første og sidste punkt, hvorpå sættet af Splines er defineret, det vil sige punkterne og i intervallet . $P$ $m$ $n$ $[m,n]$

Angiv værdierne af den anden afledede af y "manuelt", i sættet af splines defineret i intervallet . $m$ $n$ $[m,n]$

Gør værdierne lig med den anden afledede af m og n i sættet af splines defineret på intervallet $[m,n]$

Subjekt kubiske splines : Den første afledede af P skal have samme værdi som den første afledede af funktionen for det første og sidste punkt, hvorpå sættet af Splines er defineret, det vil sige punkterne m og n i intervallet [m, n].

Referencer

Ferguson, James C, Multi-variabel kurveinterpolation, J. ACM, vol. 11, nr. 2, s. 221-228, april 1964.
Ahlberg, Nielson og Walsh, The Theory of Splines and Their Applications, 1967.
Birkhoff, Fluid dynamics, reactor computations, and surface repræsentation, i: Steve Nash (red.), A History of Scientific Computation , 1990.
Bartels, Beatty og Barsky, En introduktion til splines til brug i computergrafik og geometrisk modellering, 1987.
Birkhoff og de Boor, Stykkevis polynomisk interpolation og tilnærmelse, i: HL Garabedian (red.), Proc. General Motors Symposium fra 1964, s. 164-190. Elsevier, New York og Amsterdam, 1965.
Davis, B-splines og geometrisk design , SIAM News, vol. 29, nr. 5, 1997.
Epperson, History of Splines , NA Digest, vol. 98, nr. 26, 1998.
Stoer & Bulirsch, Introduktion til numerisk analyse. Springer-Verlag . s. 93-106. ISBN 0387904204
Schoenberg, Bidrag til problemet med tilnærmelse af ækvidistante data ved analytiske funktioner, Quart. App. Math., bind. 4, s. 45–99 og 112–141, 1946.
Young, Garrett Birkhoff og anvendt matematik, Notices of the AMS, vol. 44, nr. 11, s. 1446-1449, 1997.
Chapra, Canale, "Numerical Methods for Engineers" 5. udgave.

Eksterne links

Wikimedia Commons har en mediekategori for Splines .