Spline

In sovelletun matematiikan ja numeerinen analyysi , joka on ura- on paloittain funktio määritellään polynomeja .

Spline on englanninkielinen termi, jota ranskaksi käytettäessä lausutaan yleensä [splin] , à la française. Se osoittaa joustavan puuviivaajan , jota kutsutaan ranskan kielellä cerce . Sovelletun matematiikan käytössä englanninkielinen termi spline on kuitenkin yleistetty ja ranskan sana cerce jätetty huomiotta.

In interpolointi ongelmia , vaarnan menetelmä on hyvin usein edullista polynomi-interpolointi . Splinejä käytetään myös kokeellisten tietojen tai tilastojen tasoittamiseen liittyvissä ongelmissa .

Splinejä käytetään numeerisesti edustamaan monimutkaisia muotoja. Niiden toteuttaminen on yksinkertaista. Niitä käytetään usein piirustus- tai graafisen suunnittelun ohjelmistoissa; Niiden käyttö yleistynyt siellä Pierre bézier kanssa B-kiilat .

Historiallinen

Rihlojen historiallinen alkuperä löytyy teollisesta muotoilusta.

Aiemmin, ennen digitaalisten työkalujen olemassaoloa, teollinen muotoilu perustui geometriaan ja piirustuksiin. Esimerkiksi koneosan suunnittelijat määrittivät graafisesti muutaman pisteen tai solmun , joiden läpi osan ääriviivan on välttämättä kuljettava ( tekninen piirustus ). Teollisuussuunnittelijan työ koostui näiden solmujen yhdistämisestä mahdollisimman sujuvilla kaarilla epäjatkuvuuksien, mekaanisten heikkouksien ja repeämien välttämiseksi. Näiden käyrien oli oltava "silmälle miellyttäviä": subjektiivisen "ilon" käsitteen ja funktion säännöllisyysluokan , toisin sanoen sen ominaisuuksien, jatkuvuuden ja johdannaisen, matemaattisen käsityksen välillä on suora suhde .

Graafisen ääriviivat ääriviivat, käytimme elastinen puinen hallitsija, nimeltään urainen Englanti ja vanne ranskaksi. Viivain vietiin solmien avulla solmujen läpi ja hallitsijan ottama käyrä jäljitettiin niiden välillä. Puuliuskan mekaaniset ominaisuudet ovat sellaiset, että se muodonmuutoksessa muodon, jolla on jatkuvia johdannaisia korkeassa järjestyksessä (ensimmäinen johdannainen on jatkuva, myös toinen johdannainen jne.)

Tietoja spline- termistä

Ääntäminen

Spline on englanninkielinen sana, joka tällä kielellä lausutaan [splaɪn] , mikä erottaa sen " pernasta " [spli: n] . Ranskassa ääntämme sanan sen kirjoitettuna : [splin] .

Etymologia

Pierre Bézier kirjoittaa:

” Valitettavasti englanninkielinen sana spline on vallinnut, kun taas se käännetään ranskaksi substantiiveilla latte tai baguette . "

Oxfordin englanninkielisessä sanakirjassa 1989 määritellään sana spline seuraavasti :

" Pitkä kapea ja suhteellisen ohut pala tai nauha puusta, metallista jne. säleikkö. Joustava puu- tai kovakuminauha, jota luonnokset käyttävät laajan lakaisukäyrän asettamiseen etenkin rautatieliikenteessä. "

”Pitkä, kapea ja suhteellisen ohut puu-, metalli- jne. Pala. Joustava puu- tai kovakuminauha, jota teollisuussuunnittelijat käyttävät leveiden kaarien piirtämiseen, erityisesti rautatieliikenteessä. "

Joiners, puusepän ja liukuportaat kutsutaan tämän työkalun vanne , joustava puinen säleen hyvä viljaa käytetään tehdä "mitään" käyrät (harmoninen käyrät läpi tietyn määrän pisteitä, ja joita ei voida tehdä käyttämällä kompassi).

Rihmojen matemaattinen lähentäminen

Puuliuskan ottaman muodon kuvaus elastisuuslakien perusteella on matemaattisesti monimutkainen. Käytännön käyttötarkoituksiin saadaan kuitenkin hyväksyttävä likiarvo edustamalla säännön muotoa uralla , toisin sanoen funktiona, jonka palat määrittelee polynomi kullakin solmujen välisellä välillä.

Nämä polynomit voidaan laskea asettamalla jatkuvuusolosuhteet: ne kulkevat solmujen läpi, muodon kaltevuus on jatkuva, ts. Että solmun oikealla ja vasemmalla puolella olevilla polynomeilla on jopa ensimmäinen johdannainen; samalla tavalla kussakin solmussa kaarevuus on jatkuva, toisin sanoen oikealla ja vasemmalla olevilla polynomeilla on sama johdannaissekunti. Ratkaisu annetaan paloina kolmannen asteen polynomeja. Se on polynomien vähimmäisaste niin, että funktio, sen kaltevuus ja kaarevuus ovat jatkuvia jokaisessa solmussa. Tätä paloittain käyrää kutsutaan uraksi .

Kuutiopaloja käytetään käytännössä eniten. Niitä on helpompi käyttää kuin polynominterpolointia, eikä niillä yleensä ole poikkeavaa käyttäytymistä. Joissakin erityistapauksissa voidaan johtaa neljännen asteen polynomien käyttöön; tämä käyttö johtuu kuitenkin analyytikoiden käytännöstä, mutta ei teoreettisista näkökohdista.

Tietojen lähentämisen puitteissa on myös kehitetty muita spline-toimintoperheitä (jotka on saatu minimoimalla energiafunktionaalisuus).

Määritelmä

Antaa olla sarja datapisteitä tai solmuja koordinaatteja $( X i , Y i )$ . Kutsumme interpolointi Spline paloittain toiminta koostuu polynomin kunkin aikavälin solmujen välillä.

Spline-asteen määrittelee käytetyn korkeimman asteen polynomi: jos yhdistämme yksinkertaisesti solmut suorilla viivoilla, toisin sanoen jos spline koostuu ensimmäisen asteen polynomeista, spline on astetta 1 jne. Jos kaikilla polynomeilla on sama aste, puhumme yhtenäisestä urasta . Jos kaikki polynomit ovat kolmannen asteen, puhumme kuutiomaisesta urasta .

Esimerkkejä

Tässä on esimerkki toisaalta asteen 1 ja toisaalta asteen 3 interpolaatioviivoista, jotka perustuvat samoihin neljään solmuun (punaiset pisteet alla olevissa kaavioissa.

Vasemmalla asteen 1 spline yhdistää neljä solmua asteen 1 polynomeilla, toisin sanoen suorilla viivoilla. Spline on jatkuva, mutta kaltevuus ei ole jatkuva (se siirtyy yhtäkkiä arvosta toiseen). Polynomit, lineaariset funktiot, sallivat lineaariset interpolaatiot solmujen välillä.

Oikealla kuutiomainen spline, jossa solmut on kytketty polynomeilla 3 e astetta, johon se on asettanut edellytykset jatkuvan uran tekemiseksi ensimmäisen asteen (rinteet vaihtelevat jatkuvasti) ja toisen asteen (uran kaarevuus, tarkemmin sanottuna sen toinen johdannainen, vaihtelee jatkuvasti).

Esimerkkejä urista

Esimerkki asteen 1 urasta neljälle solmulle.

Esimerkki asteen 3 urasta neljälle solmulle.

Spline-jatkuvuus

Koska polynomit ovat jatkuvia, rajattomasti erilaistuvia ja niiden peräkkäiset johdannaiset ovat jatkuvia, uran jatkuvuus riippuu jokaiselle solmulle asetetuista jatkuvuusolosuhteista. Jatkuvuus määrittää kunkin intervallin välisen risteyksen ominaisuudet. Tämä vastaa kahden peräkkäisen polynomin vastaavuustasoa risteyskohdissa.

$C 0$ on pienin jatkuvuus: peräkkäiset polynomit kulkevat risteyskohtien läpi;
$C 1$ on tangenttien jatkuvuus: peräkkäisillä polynomeilla on ensimmäiset johdannaiset (toisin sanoen kaltevuudet), jotka ovat yhtä suuret kuin risteyspisteet;
$C 2$ on jatkuvuus kaarevuuden: peräkkäisten polynomit myös toinen johdannaiset (kaarevuudet) yhtä kuin solmukohdissa;

Soveltamisen ehtojen

C 0

C 1

C- 2

johtaa kuutiosplinimenetelmät.

Interpolointiraja

Kun olemme määrittäneet uran elementit, toisin sanoen polynomien parametrit, jotka liittävät kuhunkin annettuun pisteeseen ( solmut ), voimme laskea kahden solmun välissä olevan pisteen ordinaatin: c 'on vastaavan abskissan polynomi. Spline mahdollistaa sen vuoksi solmujen välisten arvojen interpoloinnin.

Rihmojen haitat

Vaikka ne ovat vakaampia kuin muut interpolointimenetelmät, splineillä on silti joitain haittoja:

uran parametrien arviointi voi olla erilainen, jos kahden solmun välinen kaltevuus vaihtelee suuresti intervallista toiseen;
spline riippuu koordinaatistojärjestelmän valinnasta, sillä ei siten ole mitään geometrista invarianssiominaisuutta (esimerkiksi pyörimisen tapaus); se on kuitenkin edelleen epäherkkä yhden akselin homotyypille ;
emme voi käyttää interpolaatiota splineina, jos esitettävä käyrä ei ole funktio, toisin sanoen jos tietylle absissille on enemmän kuin yksi arvo (käyrät, jotka "palaavat" kuten ellipsit, ympyrät jne.) Tässä Tässä tapauksessa käytämme splainien yleistyksiä ( B-splines , NURBS ).

Kuutiomaisen uran alkioiden laskeminen

Tarkastellaan n koordinaattien solmua $( X 1 , Y 1 ), ..., ( X n , Y n )$ . Aikaväliä on n -1. Siksi haluamme määrittää kolmannen asteen n -1 polynomien, $S 1 , ..., S n -1,$ parametrit .

Jokaisella polynomilla $S$ on muodon yhtälö:

{\ displaystyle S = a_ {0} x ^ {3} + a_ {1} x ^ {2} + a_ {2} x + a_ {3}}

Siksi meidän on määritettävä neljä kerrointa polynomia kohti tai yhteensä 4 n- 4 tuntematonta, joille meidän on asetettava niin monta ehtoa.

Edellytykset $C 0$ , $C 1$ ja $C- 2$ ilmaistaan seuraavasti:

$C 0$ : kukin n- 1-polynomista kulkee kahden solmun eli 2 n- 2-olosuhteen läpi;
$C 1$ : polynomien on sama ensimmäinen johdannaisen n -2 liitoksen solmua, eli N -2 olosuhteissa;
$C 2$ : ja näillä polynomeilla on jopa toinen johdannainen n -2 risteyssolmussa, ts. N -2 olosuhteissa.

Yhteensä meillä on siis 4 n -6 ehtoa. Kaksi ehtoa puuttuu siis 4 n- 4 tuntemattoman määrittämiseksi. Lisätään kaksi lisäehtoa asettamalla toisen johdannaisen arvo kullekin ääripäälle. Jos määräämme, että toiset johdannaiset ovat nollat kummassakin päässä, saadaan luonnollinen kuutio-ura . Saattaa kuitenkin olla saatavilla lisätietoja, joiden avulla toinen johdannainen voidaan kiinnittää tarkemmin päihin.

Näin saadaan 4 n- 4 lineaarisen yhtälön järjestelmä, jossa on 4 n -4 tuntematonta.

Laskenta-algoritmi

Alla on algoritmi interpolointikuutiouurteen laskemiseksi, luonnollinen tai ei. Tämä algoritmi on esitetty luonnollisella ja matemaattisella kielellä, viittaamatta mihinkään ohjelmointikieleen. Se voidaan toteuttaa yksinkertaisella laskentataulukolla.

Algoritmi interpolointiradan laskemiseksi Olkoon

X i

Y i

n

solmun paiseet ja ordinaatit , paiseet luokitellaan nousevaan järjestykseen.1. Laske pylväsmatriisi

h

solmujen välisten

n -1

välin leveydestä :

{\ displaystyle \ mathbf {h} _ {i} = X_ {i + 1} -X_ {i}}

i: lle

välillä 1 -

n -1

.2. Laske sarakkeen matriisi

F

n- -2

johdannainen sekuntia solmut:2.1. Solmuille 2 -

n -1

{\ displaystyle \ mathbf {F} _ {i} = {\ frac {Y_ {i + 1} -Y_ {i}} {\ mathbf {h} _ {i}}} - {\ frac {Y_ {i} -Y_ {i-1}} {\ mathbf {h} _ {i-1}}}}

i: lle

välillä 2 -

n -1

.2.2. On myös tarpeen arvo toisen johdannaiset päissä,

F 1

F n

. Jos asetamme

F 1 = 0

F n = 0

, saamme luonnollisen uran; jos meillä on tietoja päistä, annamme

F 1: lle

ja / tai

F n:

lle ad hoc -arvon . 3. Muodosta neliömatriisi

R i , j

, joiden mitat ovat

n x n

, siten, että

i

tarkoittaa indeksi rivit ja

j

että sarakkeet: 3.1 Aseta kaikki matriisin

R

elementit arvoon 0. 3.2 Ensimmäisellä rivillä vain ensimmäinen elementti ei ole nolla:

R 1,1 = 1

. 3.3 Viimeisellä rivillä vain viimeinen elementti ei ole nolla:

R n , n = 1

. 3.4 Mitan

(

n

-2) \times

n

R

n

alamatriisi

ilman ensimmäistä ja viimeistä riviä on kolmiaksiaalinen. Kaikki sen elementit ovat nollia, paitsi:

Alamatriisin keskiväli on:

{\ displaystyle \ mathbf {R} _ {i, i} = {\ frac {h_ {i-1} + h_ {i}} {3}}}

kun

i = 2, ..., n -1

Ylempi lävistäjä on:

{\ displaystyle \ mathbf {R} _ {i, {i + 1}} = {\ frac {h_ {i}} {6}}}

kun

i = 2, ..., n -1

Alemman lävistäjän arvo on:

{\ displaystyle \ mathbf {R} _ {i, {i-1}} = {\ frac {h_ {i-1}} {6}}}

kun

i = 2, ..., n -1

.4. Laske mitan

n

pylväsmatriisi

M

siten, että:

{\ displaystyle \ mathbf {M} = \ mathbf {R} ^ {- 1} \ kertaa \ mathbf {F}}

.5. Laske sarakematriisit

C

C '

, mitat

n -1

, jotka sisältävät vastaavasti

n - 1-

polynomien järjestysluvut 1 ja 2 :For

i

n -1

{\ displaystyle \ mathbf {C} _ {i} = {\ frac {Y_ {i + 1} -Y_ {i}} {\ mathbf {h} _ {i}}} - {\ frac {\ mathbf {h } _ {i}} {6}} (\ mathbf {M} _ {i + 1} - \ mathbf {M} _ {i})}

{\ displaystyle \ mathbf {C '} _ {i} = Y_ {i} - \ mathrm {M} _ {i} {\ frac {\ mathbf {h} _ {i} ^ {2}} {6}} }

6. Interpolointiarvon laskeminen abskissa

x: lle, joka

sijaitsee välissä

k

, absissin

X

k ja

X k +1

solmujen välillä (

k

: n ollessa 1 -

n - 1

{\ displaystyle {\ begin {array} {lcl} y & = & \ mathbf {M} _ {k} {\ frac {(X_ {k + 1} -x) ^ {3}} {6 \ mathbf {h } _ {k}}} \\ & + & \ mathbf {M} _ {k + 1} {\ frac {(x-X_ {k}) ^ {3}} {6 \ mathbf {h} _ {k }}} \\ & + & \ mathbf {C} _ {k} (x-X_ {k}) \\ & + & \ mathbf {C '} _ {k} \ end {array}}}

Esimerkki

Tässä esimerkissä esitetään käyrän likiarvo $y = sin x$ luonnollisella kuutio-uralla, jolle annamme seuraavat viisi funktion arvoa (5 solmua):

n = 5

{\ displaystyle {\ begin {array} {rrr} i & X_ {i} & Y_ {i} \\ 1 & 0 {,} 0 ja 0 {,} 0000 \\ 2 & 0 {,} 5 ja 0 { ,} 4794 \\ 3 & 1 {,} 0 & 0 {,} 8415 \\ 4 & 1 {,} 5 & 0 {,} 9975 \\ 5 & 2 {,} 0 & 0 {,} 9093 \\ \ end {array}}}

{\ displaystyle \ mathbf {h} = {\ begin {bmatrix} 0 {,} 5 \\ 0 {,} 5 \\ 0 {,} 5 \\ 0 {,} 5 \\\ end {bmatrix}} { \ text {; }}}

{\ displaystyle \ mathbf {F} = \ vasen [{\ begin {array} {r} 0 {,} 0000 \\ - 0 {,} 2348 \\ - 0 {,} 4120 \\ - 0 {,} 4884 \\ 0 {,} 0000 \\\ end {array}} \ right] {\ text {; }}}

{\ displaystyle \ mathbf {R} = \ vasemmalle [{\ begin {array} {rrrrr} 1 {,} 0000 & 0 & 0 & 0 & 0 \\ 0 {,} 0833 & 0 {,} 3333 & 0 { ,} 0833 & 0 & 0 \\ 0 & 0 {,} 0833 & 0 {,} 3333 & 0 {,} 0833 & 0 \\ 0 & 0 & 0 {,} 0833 & 0 {,} 3333 & 0 { ,} 0833 \\ 0 & 0 & 0 & 0 & 1 {,} 0000 \\\ end {array}} \ right] {\ text {; }}}

{\ displaystyle \ mathbf {M} = \ vasen [{\ begin {array} {r} 0 {,} 0000 \\ - 0 {,} 5061 \\ - 0 {,} 7928 \\ - 1 {,} 2671 \\ 0 {,} 0000 \\\ end {array}} \ right] {\ text {; }}}

{\ displaystyle \ mathbf {C} = \ vasen [{\ begin {array} {r} 1 {,} 0010 \\ 0 {,} 7480 \\ 0 {,} 3516 \\ - 0 {,} 2820 \\ \ end {array}} \ right] {\ text {; }}}

{\ displaystyle \ mathbf {C '} = \ vasen [{\ begin {array} {r} 0 {,} 0000 \\ 0 {,} 5005 \\ 0 {,} 8745 \\ 1 {,} 0503 \\ \ end {array}} \ right]}

Kommentti esimerkkiä : Funktiota kuvaa hyvin sen likiarvo luonnollisella uralla kaavion vasemmalla puolella, koska toisen johdannainen on todellakin nolla , kuten luonnollisen uran laskeminen edellyttää. Toisaalta kaavion oikealla puolella likiarvo luonnollisella uralla on vähemmän tarkka, koska arvon toinen johdannainen ei ole nolla (se on arvoinen ), arvo, joka poikkeaa nollahypoteesista, joka esitetään luonnollinen spline. ${\ displaystyle sin (i)}$ ${\ displaystyle sin (i)}$ $i = 0$ ${\ displaystyle sin (i)}$ ${\ displaystyle X_ {5} = 2 {,} 0}$ ${\ displaystyle -0 {,} 035}$

Selkeä muoto kuutio-ura

Funktion , jonka arvot solmut ovat tunnettuja , yleinen lauseke kuutio spline luokan C 2 pisteessä on on seuraava: $f ()$ $X_ {i}$ $x$ ${\ displaystyle [X_ {i-1}, X_ {i}]}$

{\ displaystyle S_ {i} (x) = {\ frac {z_ {i} (x-X_ {i-1}) ^ {3}} {6h_ {i}}} + {\ frac {z_ {i- 1} (X_ {i} -x) ^ {3}} {6h_ {i}}} + \ vasen [{\ frac {f (X_ {i})} {h_ {i}}} - {\ frac { z_ {i} h_ {i}} {6}} \ oikea] (x-X_ {i-1}) + \ vasen [{\ frac {f (X_ {i-1})} {h_ {i}} } - {\ frac {z_ {i-1} h_ {i}} {6}} \ oikea] (X_ {i} -x)}

tai

${\ displaystyle f (X_ {i} ^ {})}$ on solmun i arvo , $f ()$
${\ displaystyle h_ {i} ^ {} = X_ {i} \; {\ text {-}} \; X_ {i-1}}$ ,
${\ displaystyle z_ {i} = f ^ {\ prime \ prime} (X_ {i})}$ on solmun i toinen johdannainen . $f ()$

On helppo tarkistaa, että ja . ${\ displaystyle S_ {i} (X_ {i-1}) = f (X_ {i-1})}$ ${\ displaystyle S_ {i} (X_ {i}) = f (X_ {i})}$

Toteutus ohjelmistoissa

Splines integroidaan usein piirto-ohjelmistoihin, olivatpa ne sitten yleiskäyttöisiä ohjelmistoja, kuten toimisto-ohjelmistopakettien ( Microsoft Office , LibreOffice jne.), Piirustus- ja kuvankäsittelyohjelmistojen ( Inkscape , GIMP …) tai tietokoneavusteisen piirustuksen tai suunnittelun piirustustoimintoja. ohjelmisto. Nämä ohjelmistot käyttävät useimmiten B-uria .

Tasoittaa juovaa

Rihmojen käyttö tasoitukseen

Mittaustiedot yleensä vaikuttavat vaarat joko fysiikan tai humanististen tieteiden (talous, väestönkehitys, sosiologia jne) empiirisesti lähestyä tuntematon toiminto, jonka mittaukset häiriintyvät vaarat, harjoittelemme usein tasoituksen . Heuristisen taustalla olevan ajatuksen mukaan fyysisiä ilmiöitä edustavat toiminnot tai humanistiset tieteet ovat yleensä hyvin jatkuvia: tasoituksen tarkoituksena on siis korvata jatkuvat arvot vaarojen vuoksi hajautetuille mittausarvoille. Tämä ongelma syntyy erityisesti ajan mittaan muuttuvan määrän mittauksissa ( kronologiset sarjat ).

On olemassa monia empiirisiä tasoitusmenetelmiä, kuten liikkuvat keskiarvot , yhden tai kahden eksponentiaalinen tasoitus jne. Rihmojen tasoittaminen on yksi tällainen nyrkkisääntö.

Tarkastellaanpa mittaustietoja, joiden paiseet kasvavat tiukasti (nämä ovat usein kronologisia tietoja).

Rihmojen tasoittamiseen johtava ajatus perustuu saman joustavan viivaimen käyttöön kuin mitä interpolointiradat ovat alkaneet (katso yllä oleva teollinen muotoilu ). Sen sijaan, että nauha pakotettaisiin kulkemaan solmujen (mittausarvojen) läpi, oletetaan, että ne on kytketty vanteen kanssa jousilla. Sitten liukusäädin kuvaa hyvin jatkuvaa toimintoa, joka minimoi jousien ja liukusäätimen kokonais deformaatioenergian.

Tasoitustoiminnon tasausmuoto

Olkoon $n$ tunnettua arvoa (solmua), jonka paiseet kasvavat tiukasti, ja jonka haluat tasoittaa. Nämä $n$ solmua on yhdistetty joustavaan jäykkyysliuskaan $r$ jousilla, joilla kaikilla on sama jäykkyys $k$ . Tasapainon muoto on se, joka minimoi jousien pidennyksen ja nauhan kaarevuuden kokonaisenergian.

Kevään venymäenergia

Jokainen jousi $i$ ulottuu pituudella $e i$ . Joustavan jousen venymäenergia on verrannollinen venymän neliöön; jousen n o $i venymäenergia on$ arvoinen:

{\ displaystyle w_ {i} = ke_ {i} ^ {2}}

missä

k

on jousen jäykkyys.

Jousen kokonaisvenymäenergia on $n$ jousen venymäenergian summa :

{\ displaystyle W_ {R} = \ summa w_ {i} = \ summa ke_ {i} ^ {2}}

(olettaen, että kaikkien jousien jäykkyys on sama ja yhtä suuri kuin

k

). Nauhan muodonmuutosenergia

Joustavan vanteen kaarevuusvoima on verrannollinen missä tahansa pisteessä olevan kaarevuuden neliöön. Lähennämme kaarevuutta funktion $s ( x )$ toisella johdannaisella, joka edustaa nauhan muotoa. Tämä likiarvo on sallittu käytännössä, jos toiminnon kaltevuus ei ole liian suuri (>> 1). Sitten kaarevuusenergian arvo $x: n$ ja $x + dx: n välillä on$ :

{\ displaystyle dW_ {C} = rs '' (x) ^ {2} dx}

missä

r

on renkaan elastinen kaarevuusjäykkyys.

Koko nauhan venytysenergia on arvoltaan:

{\ displaystyle W_ {C} = \ int rs '' (x) ^ {2} \, \ mathrm {d} x}

jos oletetaan, että sillä on vakio jäykkyys koko pituudeltaan. Ehto nauhan ottamassa muodossa

Nauhan ottama muoto on se, joka minimoi muodonmuutosenergian, toisin sanoen jousien jatkeenergian ja nauhan kaarevuusenergian. Tämä on funktio, joka minimoi lausekkeen:

{\ displaystyle W (s, \ lambda) = \ summa e_ {i} ^ {2} + \ lambda \ int s '' (x) ^ {2} dx}

jossa

λ

on nauhan jäykkyyden

r

ja jousien jäykkyyden

k

suhde .

Tasoittava kuutiomainen spline

Löytää toiminto $s$ , joka minimoi $W ( s , λ )$ varten tietyn $λ$ on helpompaa, jos oletetaan, että tämä toiminto on kuutio spline: paloittain käyrä muodostuu kolmannen asteen polynomi. Jos joudumme tasoittamaan $n$ arvoa (tai solmua), on $n -1$ väliä ja siten $n -1$ kolmannen asteen polynomia, joista kukin määritetään neljällä parametrilla, eli yhteensä $4 n -4$ määritettävää parametria.

Näille polynomitoiminnoille asetetaan jatkuvuus jokaisessa risteyksessä, kaltevuus (ensimmäinen johdannainen) ja jatkuva toinen johdannainen, nimittäin:

$C 0$ : kukin $n - 1-$ polynomista on vierekkäinen seuraavien, toisin sanoen $n - 2$ olosuhteiden kanssa;
$C 1$ : polynomeilla on jopa ensimmäinen johdannainen $n -2$ solmussa, ts. $N -2$ olosuhteessa;
$C 2$ : ja näillä polynomeilla on jopa toinen johdannainen $n -2$ solmussa, eli $n -2$ olosuhteessa.

Olkoon $3 n -6$ ehtoa.

$W: n ( s , λ )$ minimointi , jossa $λ$ on kiinteä, vastaa $n$ ehtoa. Olkoon siis yhteensä $4 n -6$ ehtoa. Kaksi ehtoa puuttuu $4 n -4$ tuntemattoman määrittämiseksi. On säädetty, että toisten johdannaisten päissä on nolla. Näiden ehtojen joukko johtaa $4 n -4$ lineaariseen yhtälöön, joissa on $4 n -4$ tuntematonta. (Jos loppupisteiden kaarevuuksista on lisätietoja, näitä tunnettuja arvoja voidaan käyttää arvon 0 sijasta.)

Laskenta-algoritmi

Alla on algoritmi kuutiomaisen tasoitusviivan laskemiseksi. Tämä algoritmi on esitetty luonnollisella ja matemaattisella kielellä, viittaamatta mihinkään ohjelmointikieleen. Se voidaan toteuttaa yksinkertaisella laskentataulukolla.

Algoritmi kuutiomaisen tasoitusviivan laskemiseksi

Algoritmi kuutiomaisen tasoitusviivan laskemiseksi .

Olkoon

X i

Y i

n

solmun paiseet ja ordinaatit , paiseet luokitellaan nousevaan järjestykseen

( n > 2)

.1. Laske kolonnimatriisi

h

solmujen välisten

n -1

välin leveydestä :

{\ displaystyle \ mathbf {h} _ {i} = X_ {i + 1} -X_ {i}}

i: lle

välillä 1 -

n -1

.2. Rakenna tridiagonaalimatriisi

Q

(

n \times ( n -2)

) siten, että kaikki matriisin arvot ovat nollia, paitsi:

Keski-diagonaali:

{\ displaystyle \ mathbf {Q} _ {i, {i-1}} = {\ frac {1} {h_ {i-1}}} + {\ frac {1} {h_ {i}}}}

, kun

i = 2

n - 1

;

Ylempi lävistäjä:

{\ displaystyle \ mathbf {Q} _ {i, i} = - {\ frac {1} {h_ {i}}}}

, kun

i = 1

n - 2

;

Alempi lävistäjä:

{\ displaystyle \ mathbf {Q} _ {i, {i-2}} = - {\ frac {1} {h_ {i-1}}}}

, kun

i = 3

n

;3. Rakenna kolmidiagonaalinen neliömatriisi

R

(

( n -2) \times ( n -2)

) siten, että kaikki matriisin arvot ovat nollia, paitsi:

Tärkein lävistäjä:

{\ displaystyle \ mathbf {R} _ {i, i} = {\ frac {h_ {i} + h_ {i + 1}} {3}}}

, kun

i = 1

n - 2

;

Ylempi lävistäjä:

{\ displaystyle \ mathbf {R} {i, {i + 1}} = - {\ frac {h_ {i}} {6}}}

kun

i = 1

n -3

;

Alempi lävistäjä:

{\ displaystyle \ mathbf {R} {i, {i-1}} = - {\ frac {h_ {i-1}} {6}}}

kun

i = 2

n - 2

;4. Laske neliömatriisi

K

(

n \times n

{\ displaystyle \ mathbf {K} = \ mathbf {Q} \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ {t}}

;5. Olkoon yhtenäinen matriisi

n

\times

n

ja tasoitusparametri.

\ mathbf {I}

\ lambda

Saamme tasoitusviivan ordinaatit

s

jokaisesta abscissan

X

n

solmusta ja ordinaatit

Y

tasoitusparametrin arvoksi seuraavasti:

\ lambda

{\ displaystyle \ mathbf {s} = (\ mathbf {I} + \ lambda \ mathbf {K}) ^ {- 1} \ mathbf {Y}}

.6. Voimme interpoloida minkä tahansa abstsissan tasoitusviivan arvon äärimmäisten solmujen

X 1

X n

välillä soveltamalla spline-interpoloinnin algoritmia abscissa

X:

n pisteisiin ja ordinaattien

s kanssa

Esimerkki :

Tämä esimerkki osoittaa tasoituksen neljä koordinoida solmujen $( X i , Y i )$ , joka on esitetty punaisella kaavio edellä, luonnollinen kuutio Spline tasoitusfunktion parametri $λ = 1,5$ .

{\ displaystyle {\ begin {array} {rrr} i & X_ {i} & Y_ {i} \\ 1 & 0 {,} 0 ja 0 {,} 0 \\ 2 ja 1 {,} 0 ja 6 { ,} 0 \\ 3 & 3 {,} 0 & 5 {,} 0 \\ 4 & 5 {,} 0 ja 1 {,} 0 \ end {array}}}

;

{\ displaystyle \ mathbf {h} = {\ begin {bmatrix} 1 {,} 0 \\ 2 {,} 0 \\ 2 {,} 0 \\\ end {bmatrix}} {\ text {; }}}

{\ displaystyle \ mathbf {Q} = {\ begin {bmatrix} {\ begin {array} {rr} -1 {,} 0000 & 0 {,} 0000 \\ 1 {,} 5000 & -0 {,} 5000 \\ - 0 {,} 5000 & 1 {,} 0000 \\ 0 {,} 0000 & -0 {,} 5000 \\\ end {array}} \ end {bmatrix}} {\ text {; }}}

{\ displaystyle \ mathbf {R} = {\ begin {bmatrix} {\ begin {array} {rr} 1 {,} 0000 & -0 {,} 1667 \\ - 0 {,} 1667 & 1 {,} 3333 \\\ end {array}} \ end {bmatrix}}}

;

{\ displaystyle \ mathbf {K} = \ mathbf {Q} \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ {t} = {\ begin {bmatrix} {\ begin {array} {rrrr} 1 {,} 0213 ja -1 {,} 4681 ja 0 {,} 3830 ja 0 {,} 0638 \\ - 1 {,} 4681 ja 2 {,} 2979 & -0 {,} 9255 ja 0 {,} 0957 \\ 0 {,} 3830 & -0 {,} 9255 & 0 {,} 8936 & -0 {,} 3511 \\ 0 {,} 0638 & 0 {,} 0957 & -0 {,} 3511 & 0 { ,} 1915 \\\ end {array}} \ end {bmatrix}}}

;

Olen

yksikkömatriisi

n \times n

ja parametrilla

λ

laskemme:

{\ displaystyle (\ mathbf {I} + \ lambda \ mathbf {K}) = {\ begin {bmatrix} {\ begin {array} {rrrr} 2.53191 & -2.20213 & 0.57447 ​​& 0.09574 \\ - 2.20213 & 4.44681 & -1.38830 & 0.14362 \\ 0.57447 ​​& -1.38830 & 2.34043 & -0.52660 \\ 0.09574 & 0.14362 & -0.52660 & 1.28723 \\\ end {array}} \ end {bmatrix}} {\ text {, et:} }}

{\ displaystyle (\ mathbf {I} + \ lambda \ mathbf {K}) ^ {- 1} = {\ begin {bmatrix} {\ begin {array} {rrrr} 0.7051 & 0.3583 & 0.0206 & -0.0840 \\ 0.3583 & 0.4599 & 0.1843 & -0.0026 \\ 0.0206 & 0.1843 & 0.5800 & 0.2152 \ - 0.0840 & -0.0026 & 0.2152 & 0.8714 \\ end {array}} \ end {bmatrix}}}

. mistä laskemme

{\ displaystyle \ mathbf {s} = (\ mathbf {I} + \ lambda \ mathbf {K}) ^ {- 1} \ mathbf {Y}}

Tasoitusparametri

Yleisesti oletetaan, että jousilla, jotka vetävät vanteen, on kaikilla sama jäykkyys $k$ . Erilaisten jäykkyyksien antaminen merkitsee solmujen painottamista ottamalla huomioon, että jotkut ovat enemmän tai vähemmän tärkeitä tai enemmän tai vähemmän "houkuttelevia" kuin toiset. Analyytikoiden kokemus antaa nämä painot määrittää.

Jos kaikilla jousilla on sama jäykkyyskerroin $k$ , tasoitusparametri, usein merkitty $X$ , ilmaisee nauhan elastisen jäykkyyden ja jousien välisen suhteen. $λ$ voi vaihdella välillä 0 ja $+ \infty$ :

jos $λ = 0$ , jouset ovat "äärettömän" kovia renkaaseen verrattuna. Tässä tapauksessa spline kulkee solmujen läpi ja saamme luonnollisen uran ;
jos $λ$ pyrkii kohti $+ \infty$ , tämä tarkoittaa oletusta, että vanteesta tulee "äärettömän" jäykkä jousiin nähden. Tällöin tasoitusviiva pyrkii solmujen regressioviivaan .

Esimerkkejä kuutiosta tasoittavista urista

Neljän solmun tasoitus kuutiomaisella tasoitusviivalla parametrilla λ = 0,3.

Neljän solmun tasoitus kuutiomaisella tasoitusviivalla parametrilla λ = 1,5.

Tasoituksen voimakkuuden paremmin arvioimiseksi $käytetään$ usein parametria $p$ , kuten:

{\ displaystyle p = {\ frac {1} {\ lambda +1}}}

, tarkoittaen :

{\ displaystyle \ lambda = {\ frac {1-p} {p}}}

, jossa

p

vaihtelee välillä 0 (pois lukien) ja 1.

p = 1

vastaa

λ = 0

: saamme solmujen läpi kulkevan luonnollisen uran;

p \to 0 +

vastaa

λ \to + \infty

: saatu ura pyrkii regressioviivaan.

Tasoitusparametrin optimointi

Kun tarkastellaan paljon meluisia mittaustietoja, tasoituksen tavoitteena on tuottaa äänetön arvio mittauksesta. Jos voimme arvioida melun varianssin, raakadatan ja tasoitetun datan erojen varianssi melun varianssiin verrattuna voi ohjata tasoitusparametrin valintaa.

Tätä prosessia sovelletaan järjestelmällisemmin seuraavasti:

Annettavan tasoitusparametrin avulla poistetaan solmu n o $i$ mittaussarjasta ja määritetään parametrin $λ$ tasoitusviiva siten, että tämä solmu jätetään laskennan ulkopuolelle. Poikkeama $ε i$ solmun n o $i$ välillä raaka-arvon ja arvon tasoituksen Spline mittaa ennustevirhe tämän solmun. Toistetaan tämä operaatio, jossa sama parametri $λ$ , että $n$ solmujen:

ilmaisin

{\ displaystyle \ summa {\ frac {\ epsilon _ {i} ^ {2}} {n}}}

on likiarvo ennusteen tasoitusviivan varianssista parametrin $λ$ ehdossa . Tätä indikaattoria kutsutaan ristivalidointipisteeksi $CV ( λ )$ .

Toistamalla tämä menettely useille $λ-$ arvoille voimme löytää tasoitusparametrin arvon, joka minimoi tämän ristivalidointipisteen. Ei voida taata, että $ansioluettelossa ei$ ole paikallisia vähimmäisvaatimuksia. Vaaditut laskelmat voivat siis olla mittavia ja tutkimus työlästä. Onneksi meillä on algoritmi, joka mahdollistaa $CV: n ( λ )$ määrittämisen suorittamatta kuutiomaisen tasoitusviivan laskemista.

Kätevä spline-laskenta

Olipa kyseessä interpolointi tai tasoitus, laskenta tuo peliin, jos solmuja on lukuisia, erittäin suuria matriiseja, jotka voivat aiheuttaa ongelmia laskennan toteutuksen aikana. Käytetyt matriisit ovat hyvin harvinaisia , toisin sanoen kaikki niiden elementit, lukuun ottamatta kolmen pääasiallisen lävistäjän, ovat nollia. On olemassa ohjelmisto, joka toteuttaa tehokkaita harvinaisia matriisivarastointimenetelmiä. Laskelmat voivat kuitenkin olla pitkiä.

Reinsch (de) antaa algoritmin, joka käyttää Choleskyn kertointa laskelmien koon pienentämiseen.

Huomautuksia ja viitteitä

Pierre Bézier, " Käyrät ja pinnat CFAO: lle ", Techniques of the engineer Applications of Mathics , voi. TIB102DUO, n o A1440,1992( luettu verkossa , kuultu 25. joulukuuta 2017 ).
E. Moulines, "Ei- parametrinen regressiotapaustutkimus " [PDF] .

Katso myös

Aiheeseen liittyvät artikkelit

Bibliografia (urat, B-urat, Dm-urat ...)

De Casteljaun ja Bézierin alkuteosten lisäksi viiteteoksia ovat Pierre Jean Laurent ( Approximation et optimization, Hermann, Pariisi, 1972 ), Carl de Boor ( A Practical Guide to Splines, Springer Verlag, Berlin-Heidelberg, 1978 ).
DG Schweikert, Interpolaatiokäyrä, jossa käytetään spline-jännitettä, J. Math. ja Phys., osa 45, s. 312-317, 1966.
LL Schumaker, Pintojen sovittaminen hajautettuihin tietoihin, Approximation Theory II, GG Lorentz, CK Chui ja LL Schumaker (toim.), Academic Press, 203-269 (1976).
M. Atteia, "Spline" -toiminnot määritelty kuperalle joukolle, Numerot. Math., 12, 192 - 210, 1968.
R. Arcangéli, Jotkut erillisten D ^ {m} -linjojen sovellukset, matemaattiset menetelmät tietokoneavusteisessa geometrisessa suunnittelussa, T. Lyche ja LL Schumaker (toimittajat), Academic Press, 35-44, 1989.
R. Arcangéli, MC López-de-Silanes ja JJ Torrens, moniulotteiset minimoivat urat. Teoria ja sovellukset, Grenoble Sciences, s.1-4020, 2004.
J. Duchon, Splines Minimizing Rotation- Invariant Semi-Norms in Sobolev Spaces, Lecture Notes in Math., 571, 85-100, Springer, 1977.
Gout, Z. Lambert ja D. Apprato, Tietojen lähentäminen: matemaattinen mallinnus ja numeeriset simulaatiot, ( ISBN 978-2-7598-2367-3 ) , EDP Sciences, 2019.
G. Demengel ja JP Pouget , Bézier malleja, B-rihlat ja NURBS , Ellipses ,1998, 286 Sivumäärä ( ISBN 978-2-7298-9806-9 )
Michelle Schatzman, Numeerinen analyysi :: Matemaattinen lähestymistapa , Pariisi, Dunod , coll. "Sup Sciences",Heinäkuu 2004, 480 Sivumäärä ( ISBN 978-2-10-048732-5 ).

Ulkoiset linkit

(en) Richard Bartels John C. Beatty, Brian A. Barsky, Johdatus käyttö Splines tietokonegrafiikan , TR CS-83-09, Johdatus sen käyttö Splines Computer Graphics , University of Waterloo , Kanada;
(en) Christian H. Reinsch, ” Smoothing by Spline Functions ” , Numerische Mathematik , voi. 10,1967, s. 177-183 ( luettu verkossa , tutustunut 14. tammikuuta 2018 ) ;
JP Croisille, " INTERPOLATION SPLINE " [PDF] , matematiikan maisteri M1, vuosi 2008-2009 , http://www.iecl.univ-lorraine.fr/ , Institut Élie Cartan de Lorraine,2008(käytetty 14. tammikuuta 2018 ) ;
Frédéric PLANCHET, " Tasoitus- ja säätömenetelmät " [PDF] , DURATION MODELS - Kurssimateriaali 2017-2018 , osoitteessa http://www.ressources-actuarielles.net/ , finanssitieteiden ja vakuutusten instituuttielokuu 2017(käytetty 14. tammikuuta 2018 ) ,s. 4.