MINISTARSTVO OBRAZOVANJA I ZNANOSTI RUSKE FEDERACIJE

Savezna državna autonomna obrazovna ustanova

visoko stručno obrazovanje

"Uralsko federalno sveučilište nazvano po prvom predsjedniku Rusije B.N. Jeljcinu"

Institut za radioelektroniku i informacijske tehnologije - RTF

Stolica Automatizacija i informacijska tehnologija

Spline interpolacija

METODIČKE UPUTE za laboratorijski rad IZ DISCIPLINE " Numeričke metode»

Sastavio I.A. Selivanova, viši predavač.

SPLINE INTERPOLACIJA: Upute za praktične vježbe iz discipline "Numeričke metode"

Instrukcije su namijenjene studentima svih oblika obrazovanja smjera 230100 – „Informatika i računarstvo“.

Ó FSAEI HPE "UrFU nazvan po prvom predsjedniku Rusije B.N. Jeljcinu", 2011.

1. INTERPOLACIJA SPLAJNOVIMA. 4

1.1. Kubični splineovi. 4

1.2. Poseban oblik pisanja splajna. 5

1.3. Kvadratni splineovi. 13

1.4. Zadatak za vježbu. 18

1.5. Mogućnosti zadataka. 19

Reference 21

1. Interpolacija splineovima.

U slučajevima kada je interval [ a,b], na kojem je potrebno zamijeniti funkciju f(x) velika, možete primijeniti spline interpolaciju.

1.1. Kubični splineovi.

Interpolacijski splinovi 3 reda su funkcije koje se sastoje od dijelova polinoma 3 th narudžba. Čvorovi konjugacije osiguravaju kontinuitet funkcije, njezine prve i druge derivacije. Aproksimirajuća funkcija je sastavljena od zasebnih polinoma, u pravilu jednako malog stupnja, definiranih svaki na svom dijelu segmenta.

Neka na intervalu [ a, b] realna os x data je mreža u čijim su čvorovima definirane vrijednosti
funkcije f(x). Potrebno je graditi na segmentu [ a, b] kontinuirana spline funkcija S(x), koji zadovoljava sljedeće uvjete:

Da biste konstruirali željeni spline, morate pronaći koeficijente
polinomi
,ja=1,… n, tj. 4 n nepoznati koeficijenti koji zadovoljavaju 4 n-2 jednadžbe (1), (2), (3). Da bi sustav jednadžbi imao rješenje dodaju se još dva dodatna (rubna) uvjeta. Koriste se tri vrste rubnih uvjeta:

Uvjeti (1), (2), (3) i jedan od uvjeta (4), (5), (6) tvore SLAE reda 4 n. Sustav se može riješiti Gaussovom metodom. Međutim, odabirom posebnog oblika pisanja kubnog polinoma može se značajno smanjiti redoslijed sustava jednadžbi koji se rješava.

1.2. Poseban oblik pisanja splajna.

Razmotrite segment
. Uvedimo sljedeće oznake za varijable:

Ovdje
- duljina segmenta
,

,
- pomoćne varijable,

x- međutočka na segmentu
.

Kada x prolazi kroz sve vrijednosti u intervalu
, varijabla mijenja se od 0 do 1, i
mijenja se od 1 do 0.

Neka kubni polinom
na segmentu
izgleda kao:

Varijable I
određuju se u odnosu na određeni segment interpolacije.

Pronađite vrijednost splinea
na krajevima segmenta
. Točka
je inicijal za segment
, Zato =0,
=1 i prema (3.8):
.

Na kraju segmenta
=1,
=0 i
.

Za interval
točka
je konačno, dakle =1,
=0 i iz formule (9) dobivamo:
. Dakle, uvjet kontinuiteta funkcije je zadovoljen S(x) na spojnim točkama kubnih polinoma, bez obzira na izbor brojeva  i .

Za određivanje koeficijenata  i , ja=0,… n diferenciramo (8) dva puta kao složenu funkciju od x. Zatim

Definirajte druge izvodnice splajna
I
:

Za polinom
točka je početak segmenta interpolacije i =0,
=1, dakle

Iz (15) i (16) slijedi da je na intervalu [ a,b]spline funkcija, "slijepljena" od komadića polinoma 3. reda, ima kontinuiranu derivaciju 2. reda.

Da bi se dobila kontinuitet prve derivacije funkcije S(x), zahtijevamo da sljedeći uvjeti budu ispunjeni u unutarnjim čvorovima interpolacije:

Za prirodni kubični spline
, stoga će sustav jednadžbi izgledati ovako:

a sustav jednadžbi (17) izgledat će ovako:

Primjer.

Početni podaci:

Funkcija zamjene
interpolacijski kubični spline, čije se vrijednosti u danim čvornim točkama (vidi tablicu) podudaraju s vrijednostima funkcije u istim točkama. Razmotrite različite rubne uvjete.

Izračunajmo vrijednost funkcije u čvornim točkama. Da bismo to učinili, zamijenimo vrijednosti iz tablice u zadanu funkciju.

Za različite rubne uvjete (4), (5), (6) nalazimo koeficijente kubičnih splajnova.

1. Razmotrimo prve rubne uvjete.

U našem slučaju n=3,
,
,
. Pronaći
koristimo sustav jednadžbi (3.18):

Izračunaj I , koristeći formule (7) i (11):

Dobivene vrijednosti zamjenjujemo u sustav jednadžbi:

.

Sustavno rješenje:

Uzimajući u obzir prve rubne uvjete, koeficijenti splajna:

Razmotrimo definiciju koeficijenata spline-a uzimajući u obzir rubne uvjete (3.5):

Nađimo izvod funkcije
:

Izračunaj
I
:

Zamijenimo u sustav jednadžbi (21) vrijednosti I :

Pomoću formule (20) određujemo  0 i  3:

S obzirom na specifične vrijednosti:

i vektor koeficijenta:

Izračunajmo vrijednosti kubičnog splajna S(x) u središtima interpolacijskih segmenata.

Srednji dijelovi:

Za izračun vrijednosti kubičnog splajna u središtima interpolacijskih segmenata koristimo formule (7) i (9).

3.1.

Nađimo I
:

U formuli (3.9) zamijenimo koeficijente

3.2.

Nađimo I
:

, za rubne uvjete (4), (5), (6):

3.3.

Nađimo I
:

U formuli (9) zamjenjujemo koeficijente
, za rubne uvjete (4), (5), (6):

Napravimo tablicu:

	(1 kr. stanje.)	(2 kr. uvjeti)	(3 kr. uvjeti)

Glavni zadatak interpolacija- pronalaženje vrijednosti tablične funkcije u onim točkama unutar zadanog intervala gdje ona nije navedena. Početni tablični podaci mogu se dobiti i eksperimentalno (u ovom slučaju u osnovi nema međupodataka bez dodatnog rada) i izračunom pomoću složenih ovisnosti (u ovom slučaju pronađite vrijednost pomoću interpolacije složena funkcija lakše je od izravnog izračuna pomoću složene formule)

Pojam interpolacije

Rješenje problema interpolacije i ekstrapolacije daje se konstrukcijom interpolacijske funkcije L(x), otprilike zamjenjujući original f(x), zadane u tablici, a prolaze kroz sve zadane točke - interpolacijski čvorovi. Pomoću ove funkcije možete izračunati željenu vrijednost izvorne funkcije u bilo kojem trenutku.

U vezi s interpolacijom razmatraju se tri glavna problema.

1) izbor funkcije interpolacije L(x);

2) procjena pogreške interpolacije R(x);

3) postavljanje interpolacijskih čvorova kako bi se osigurala najveća moguća točnost obnove funkcije ( x 1 , x 2 ,…,x n).

Posebne metode interpolacije omogućuju određivanje željene vrijednosti funkcije bez izravne konstrukcije interpolacijske funkcije. U načelu, sve metode interpolacije temeljene na korištenju polinoma kao interpolacijske funkcije daju iste rezultate, ali uz različite troškove. To je zato što polinom n stupanj koji sadrži n+1 parametar i prolaz kroz sve zadane n+1 bod, - jedini. Osim toga, polinom se može prikazati kao skraćeni Taylorov niz, u kojem je izvorna diferencijabilna funkcija proširena. Ovo je možda jedna od glavnih prednosti polinoma kao interpolacijske funkcije. Stoga se češće prvi problem interpolacije rješava izborom polinoma kao interpolacijske funkcije, iako se mogu koristiti i druge funkcije (na primjer, trigonometrijski polinomi, druge funkcije odabrane iz neformalnih uvjeta smislenog problema).

Riža. 3.2 Prikaz interpolacije

Odabir vrste interpolacijske funkcije općenito je važan zadatak, osobito ako se sjetite da se kroz zadane točke može povući bilo koji broj funkcija (slika 3.2). Treba napomenuti da postoji očit način konstruiranja interpolacijske funkcije: iz uvjeta da funkcija prolazi kroz sve točke sastavlja se sustav jednadžbi iz čijeg se rješenja nalaze njezini parametri. Međutim, ovaj put je daleko od najučinkovitijeg, pogotovo s velikim brojem bodova.

Uobičajeno je razlikovati lokalnu i globalnu interpolaciju. U slučaju kada je polinom isti za cijelo interpolacijsko područje, kažemo da je interpolacija globalno. U slučajevima kada su polinomi različiti između različitih čvorova, govori se o po komadu ili lokalna interpolacija.

Linearna interpolacija

Najjednostavniji i najčešće korišteni oblik lokalne interpolacije je linearna interpolacija. Sastoji se u tome što zadane točke M(x i, y i) (ja = 0, 1, …,n) povezani su ravnim odsječcima, a funkcija f(x) približava poliliniji s vrhovima u tim točkama (Sl. 3.3) .

Riža. 3.3 Linearna interpolacija

Jednadžbe svakog segmenta izlomljene linije općenito su različite. Budući da postoji n intervali (x i , x i + 1), zatim za svaki od njih kao jednadžba

Interpolacijski polinom koristi jednadžbu pravca koji prolazi kroz dvije točke. Konkretno, za ja - intervalu, možemo napisati jednadžbu pravca koji prolazi kroz točke ( x i, y i) i ( x i + 1 , y i + 1), kao:

(3.2)

Stoga, kada koristite linearnu interpolaciju, prvo morate odrediti interval u koji pada vrijednost argumenta x, a zatim ga zamijenite u formulu (3.2) i pronađite približnu vrijednost funkcija u ovoj točki.

Na slici 3.4 prikazan je primjer korištenja linearne interpolacije u programu MathCAD. Za linearnu interpolaciju koristi se funkcija linterp (x,g,z). Ovdje x, g- početni podaci, z- točka u kojoj se nalazi vrijednost funkcije.

Riža. 3.4. Linearna interpolacija

Kvadratna interpolacija

Kada kvadratna interpolacija kao interpolacijska funkcija na intervalu ( x i — 1 ,x i + 1) uzeti kvadratni trinom. Jednadžba kvadratnog trinoma ima oblik

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

Interpolacija za bilo koju točku x [x 0 , x n] nacrtana je preko tri najbliže točke.

Kubična spline interpolacija

U posljednjih godina intenzivno se razvija nova grana suvremene računalne matematike – teorija klinovi. Splines omogućuju učinkovito rješavanje problema obrade eksperimentalnih ovisnosti između parametara koji imaju prilično složenu strukturu.

Gore razmotrene metode lokalne interpolacije su u biti najjednostavniji spline prvog stupnja (za linearnu interpolaciju) i drugog stupnja (za kvadratnu interpolaciju).

Najširi praktičnu upotrebu, zbog svoje jednostavnosti, pronašli kubične splineove. Glavne ideje teorije kubičnih klinova nastale su kao rezultat pokušaja matematičkog opisa fleksibilnih tračnica izrađenih od elastičnog materijala (mehanički klinovi), koje su dugo koristili crtači u slučajevima kada je postalo potrebno nacrtati dovoljno glatku krivulju kroz zadanih bodova. Poznato je da tračnica izrađena od elastičnog materijala, fiksirana na određenim točkama i nalazeći se u ravnotežnom položaju, poprima oblik u kojem je njezina energija minimalna. Ovo temeljno svojstvo omogućuje učinkovito korištenje splineova u rješavanju praktičnih problema obrade eksperimentalnih informacija.

Općenito, za funkciju y=f(x) potrebno je pronaći aproksimaciju y= j(x) Na način na koji f(x i)= j(x i) u točkama x = x i , a u drugim točkama segmenta [ a, b] vrijednosti

funkcije f(x) I j(x) bili blizu jedan drugoga. S malim brojem eksperimentalnih točaka (npr. 6-8) može se koristiti jedna od metoda za konstruiranje interpolacijskih polinoma za rješavanje problema interpolacije. Međutim, s velikim brojem čvorova interpolacijski polinomi postaju praktički neupotrebljivi. To je zbog činjenice da je stupanj interpolacijskog polinoma samo jedan manji od broja eksperimentalnih vrijednosti funkcija. Moguće je, naravno, segment na kojem je funkcija definirana podijeliti na segmente koji sadrže mali broj eksperimentalnih točaka i za svaki od njih konstruirati interpolacijske polinome. Međutim, u ovom slučaju, aproksimirajuća funkcija će imati točke u kojima derivacija nije kontinuirana, tj. graf funkcije će sadržavati točke "loma".

Kubični splinovi nemaju ovaj nedostatak. Studije teorije greda su pokazale da se fleksibilna tanka greda između dva čvora prilično dobro opisuje kubnim polinomom, a budući da se ne kolabira, aproksimirajuća funkcija mora biti barem kontinuirano diferencijabilna. To znači da funkcije j(x), j'(x), j"(x) mora biti kontinuiran na intervalu [ a, b].

Kubični interpolacijski spline , prikladno za ovu funkciju f(x) i zadane čvorove x i , naziva se funkcija g(x), zadovoljavaju sljedeće uvjete:

1. na svakom segmentu [ x i — 1 , x i], i = 1, 2, ..., n funkcija g(x) je polinom trećeg stupnja,

Funkcija g(x), a također su njegova prva i druga derivacija neprekidne na intervalu [ a,b],

kubni spline je slijepljen od polinoma trećeg stupnja, koji za ja odjeljak napisan je na sljedeći način:

Za cijeli interval, respektivno P kubni polinomi koji se razlikuju po koeficijentima Aja, b i, c i, d i. Najčešće su čvorovi tijekom spline interpolacije ravnomjerno raspoređeni, t.j. xja +1 -Xja = konst = h (iako to nije potrebno).

Potrebno je pronaći četiri koeficijenta pod uvjetom da svaki polinom prolazi kroz dvije točke (x ja,y ja) i (x ja +1 ,y ja +1 ) , što rezultira sljedećim očiglednim jednadžbama:

Prvi uvjet odgovara prolazu polinoma kroz početnu točku, drugi - kroz krajnju točku. Nemoguće je pronaći sve koeficijente iz ovih jednadžbi, budući da ima manje uvjeta od traženih parametara. Stoga su ovi uvjeti dopunjeni uvjetima glatkoće funkcije (tj. kontinuiteta prve derivacije) i glatkoće prve derivacije (tj. kontinuiteta druge derivacije) u čvorovima interpolacije. Matematički, ovi uvjeti su zapisani kao jednakosti prve i druge derivacije na kraju ja th i na početku ( ja+1 )-te parcele.

Od i , To

(g’ (x i +1 ) na kraju ja-th odjeljak je jednak ti(xja +1 ) isprva ( ja+1 )-th),

(na"(xja +1 ) na kraju ja-th odjeljak je jednak y" (xja +1 ) isprva ( ja+1)-th).

Rezultat je sustav linearnih jednadžbi (za sve dijelove) koji sadrži 4n - 2 jednadžbe s 4n nepoznanica (nepoznate a 1 , a 2 ,…, a n , b 1 ,…, d n - koeficijenti splinea). Za rješavanje sustava dodaju se dva rubna uvjeta jedne od sljedećih vrsta (1 se češće koristi):

Zajedničko rješavanje 4n jednadžbi omogućuje pronalaženje svih 4n koeficijenata.

Da bi se vratile derivacije, može se diferencirati odgovarajući kubni polinom na svakom odsječku. Ako je potrebno odrediti derivacije u čvorovima, postoje posebne tehnike koje svode definiciju derivacija na rješavanje jednostavnijeg sustava jednadžbi u odnosu na željene derivacije drugog ili prvog reda. Važna prednost kubične spline interpolacije je dobivanje funkcije koja ima najmanju moguću zakrivljenost. Nedostaci spline interpolacije uključuju potrebu dobivanja relativno velikog broja parametara.

Riješimo problem interpolacije pomoću programa MathCAD. Da bismo to učinili, koristimo ugrađenu funkciju interp(VS,x,y,z) . Varijable x I g postaviti koordinate čvornih točaka, z je argument funkcije, VS definira tip

rubni uvjeti na krajevima intervala.

Definiramo interpolacijske funkcije za tri tipa kubičnog splajna

Ovdje cspline (VX , VY) vraća vektor VS druge derivacije pri približavanju u referentnim točkama kubnom polinomu;

psline(VX, VY) vraća vektor VS druge derivacije pri približavanju referentnim točkama parabolične krivulje;

lspline(VX, VY) vraća vektor VS druge derivacije pri približavanju referentnim točkama pravca;

interp(VS, VX, VY, x) vraća vrijednost g(x) za zadane vektore VS, VX, VY i postavljenu vrijednost x.

Izračunavamo vrijednosti interpolacijskih funkcija u zadanim točkama i uspoređujemo rezultate s točne vrijednosti

Imajte na umu da su rezultati interpolacije različitim vrstama kubičnih splineova praktički isti u unutarnjim točkama intervala i podudaraju se s točnim vrijednostima funkcije. Blizu rubova intervala razlika postaje uočljivija, a kada se ekstrapolira izvan zadanog intervala, različite vrste splajnova daju značajno različite rezultate. Radi veće preglednosti rezultate prikazujemo na grafikonu (Sl. 3.5)

Riža. 3.5 Kubična spline interpolacija

Ako je funkcija specificirana diskretno, tada su matrice podataka specificirane za interpolaciju.

U globalnoj interpolaciji najčešće se koristi polinomska interpolacija n stupnja ili Lagrangeove interpolacije.

Klasični pristup temelji se na zahtjevu striktne usklađenosti vrijednosti f(x) I j(x) u točkama x i(ja = 0, 1, 2, … n).

Tražit ćemo funkciju interpolacije j(x) kao polinom stupnja n.

Ovaj polinom ima n+ 1 koeficijent. Prirodno je pretpostaviti da n+ 1 uvjeti

j(x 0) = g 0 , j(x 1) = g 1 , . . ., j(x n) = y n (3.4)

superponiran na polinom

omogućuju jedinstveno određivanje njegovih koeficijenata. Doista, zahtijevajući j(x) ispunjenje uvjeta (3.4) , dobivamo sustav n+ 1 jednadžbe sa n+ 1 nepoznato:

(3.6)

Rješavanje ovog sustava za nepoznanice a 0 , a 1 , …, an dobivamo analitički izraz za polinom (3.5). Sustav (3.6) uvijek ima jedinstveno rješenje , jer njegova odrednica

u algebri poznat kao determinanta Vandermonde, različit od nule . iz čega slijedi , što je interpolacijski polinom j(x) za funkciju f(x) dan u tablici postoji i jedinstven je.

Rezultirajuća jednadžba krivulje prolazi točno kroz zadane točke. Izvan interpolacijskih čvorova matematički model može imati značajnu pogrešku

Lagrangeova interpolacijska formula

Neka su poznate vrijednosti neke funkcije f(X) V n+ 1 različite proizvoljne točke y i = f(x i) , ja = 0,…, P. Interpolirati (vratiti) funkciju u nekom trenutku X, koji pripada segmentu [ x 0 ,x str], potrebno je konstruirati interpolacijski polinom n-tog reda koji se u Lagrangeovoj metodi predstavlja na sljedeći način:

I to je lako vidjeti Qj(x i) = 0, Ako ja¹ j, I Qj(x i) =1, Ako ja= j. Proširimo li umnožak svih zagrada u brojniku (u nazivniku su sve zagrade brojevi), tada dobivamo polinom n-tog reda iz X, budući da brojnik sadrži n faktora prvog reda. Stoga Lagrangeov interpolacijski polinom nije ništa više od običnog polinoma n-tog reda, unatoč specifičnoj notaciji.

Procijenite grešku interpolacije u točki x od [ x 0 ,xn] (tj. riješiti drugo

problem interpolacije) može se dati formulom

U formuli - najveća vrijednost (n+1)-te derivacije izvorne funkcije f(X) na segmentu [ x 0 ,xn]. Dakle, da bi se procijenila pogreška interpolacije, potrebne su neke dodatne informacije o izvornoj funkciji (ovo bi trebalo biti jasno, jer kroz zadane početne točke može proći beskonačno mnogo različitih funkcija za koje će pogreška biti različita). Takva informacija je derivacija n + 1 reda, koju nije lako pronaći. U nastavku će biti prikazano kako izaći iz ove situacije. Također napominjemo da je primjena formule pogreške moguća samo ako je funkcija diferencijabilna n + 1 puta.

Za gradnju Lagrangeova interpolacijska formula u MathCAD-u je zgodno koristiti funkciju ako.

ako (uvjet, x, y)

Vraća vrijednost x ako cond nije 0 (true). Vraća y ako je cond 0 (false) (slika 3.6).

Interpolacijske formule Lagrangea, Newtona i Stirlinga itd. kada se koristi veliki broj interpolacijskih čvorova na cijelom segmentu [ a, b] često dovode do loše aproksimacije zbog gomilanja pogrešaka u procesu izračuna. Osim toga, zbog divergentnosti procesa interpolacije, povećanje broja čvorova ne dovodi nužno do povećanja točnosti. Kako bi se smanjile pogreške, cijeli segment [ a, b] podijeljen je na parcijalne segmente i na svakom od njih je funkcija zamijenjena aproksimacijskim polinomom niskog stupnja. To se zove piecewise polinomska interpolacija.

Jedna od metoda interpolacije na cijelom segmentu [ a, b] je spline interpolacija.

Spline naziva se komadno polinomska funkcija definirana na segmentu [ a, b] i ima određeni broj kontinuiranih izvodnica na ovom intervalu. Prednosti spline interpolacije u odnosu na konvencionalne metode interpolacije su u konvergenciji i stabilnosti računskog procesa.

Razmotrimo jedan od najčešćih slučajeva u praksi - interpolaciju funkcije kubni spline.
Neka na intervalu [ a, b] je kontinuirana funkcija. Uvedimo particiju segmenta:

i označavaju, .

Spline koji odgovara zadanoj funkciji i interpolacijskim čvorovima (6) je funkcija koja zadovoljava sljedeće uvjete:

1) na svakom segmentu funkcija je kubni polinom;

2) funkcija , kao i njena prva i druga derivacija su neprekidne na intervalu [ a, b] ;

Treći uvjet je tzv uvjet interpolacije. Poziva se spline definiran uvjetima 1) - 3). interpolirajući kubni splajn.

Razmotrite metodu za konstruiranje kubičnog splina.

Na svakom od segmenata, tražit ćemo spline funkciju u obliku polinoma trećeg stupnja:

(7)

Gdje željene koeficijente.

Razlikujemo (7) tri puta s obzirom na x:

odakle slijedi

Iz uvjeta interpolacije 3) dobivamo:

To proizlazi iz uvjeta kontinuiteta funkcije.

Ministarstvo obrazovanja i znanosti Ruske Federacije

savezni državni proračun obrazovna ustanova visoko stručno obrazovanje

"Donsko državno sveučilište"

Zavod za "Softver za računalno inženjerstvo i automatizirane sustave" "POVT i AS"

Specijalnost: Matematička podrška i administracija informacijskih sustava

NASTAVNI RAD

u disciplini "Metodika proračuna"

na temu: "Interpolacija splajnovima"

Voditelj rada:

Medvedeva Tatjana Aleksandrovna

Rostov na Donu

VJEŽBA

za seminarski rad iz discipline "Metode računanja"

Student: Alexander Moiseenko VBMO21 Group

Tema: "Interpolacija splineovima"

Rok za predaju radova za obranu “__” _______ 201_.

Početni podaci za seminarski rad: bilješke s predavanja o metodama izračuna, ru.wikipedia.org, knj. Radionica o višoj matematici Sobol B.V.

Odjeljci glavnog dijela: 1 PREGLED, 2 INTERPOLACIJSKA FORMULA, 3 CUBE INTERPOLACIJSKI ALGORITAM, 4 DIZAJN SOFTVERA, 5 REZULTATI RADA SOFTVERA.

Voditeljica rada: /Medvedeva T.A./

SAŽETAK

Izvješće sadrži: stranice-19, grafikone-3, izvore-3, blok dijagram-1.

Ključne riječi: INTERPOLACIJA, SPLINE, Mathcad sustav, CUBIC INTERPOLATION BY SPLINE.

Detaljno je razmotrena metoda interpolacije kubičnim splajnovima. Prikazan je odgovarajući programski modul. Ilustriran je blok dijagram programskog modula. Razmotreno je nekoliko primjera.

UVOD

1. TEORIJSKI OSVRT

2. INTERPOLACIJA

2.1 Interpolacija s kvadratnim splineom

2.2 Interpolacija pomoću kubičnog splajna

2.3 Izjava problema

3. INTERPOLACIJSKI ALGORITAM KORIŠTENJEM KUBIČNOG SPLINEA

4. DIZAJN SOFTVERA

5. REZULTATI RADA SOFTVERA

5.1 Opis primjera

5.2 Rezultat ispitivanja

5.3 Test slučaj 1

5.4 Testni slučaj 2

5.5 Test slučaj 3

ZAKLJUČAK

BIBLIOGRAFIJA

UVOD

Aproksimacija funkcija sastoji se u približnoj zamjeni zadane funkcije f(x) nekom funkcijom j( x) tako da je odstupanje funkcije j( x) od f(x) na danom području bio je najmanji. Funkcija j( x) naziva se aproksimacija. Tipičan problem aproksimacije funkcije je problem interpolacije. Potreba za interpolacijom funkcije je uglavnom zbog dva razloga:

1. Funkcija f(x) ima složen analitički opis, što uzrokuje određene poteškoće u njegovoj uporabi (npr. f(x) je posebna funkcija: gama funkcija, eliptična funkcija itd.).

2. Analitički opis funkcije f(x) nepoznato, tj. f(x) dat je u tablici. U tom slučaju potrebno je imati analitički opis koji približno predstavlja f(x) (na primjer, za izračunavanje vrijednosti f(x) u proizvoljnim točkama, definicije integrala i derivacija f(x) i tako dalje.).

1. TEORIJSKI OSVRT

Interpolacija - u računalnoj matematici, način da se pronađu međuvrijednosti veličine iz postojećeg diskretnog skupa poznate vrijednosti. Pri rješavanju problema sa znanstvenim i inženjerskim izračunima često je potrebno operirati sa skupovima vrijednosti dobivenih empirijski ili metodom nasumični uzorak. U pravilu, na temelju tih skupova potrebno je konstruirati funkciju na koju bi druge dobivene vrijednosti mogle pasti s visokom točnošću. Taj se problem naziva aproksimacija funkcija. Interpolacija je vrsta aproksimacije funkcija u kojoj krivulja konstruirane funkcije prolazi točno kroz dostupne podatkovne točke.

Spline je funkcija čija je domena definicije podijeljena na konačan broj segmenata, na svakom od kojih se spline podudara s nekim algebarskim polinomom. Maksimalni stupanj korištenih polinoma naziva se stupanj splajna. Razlika između stupnja splinea i rezultirajuće glatkoće naziva se spline defekt.

Splines omogućuju učinkovito rješavanje problema obrade eksperimentalnih ovisnosti između parametara koji imaju prilično složenu strukturu.

Kubični splinovi našli su široku praktičnu primjenu. Glavne ideje teorije kubičnih klinova nastale su kao rezultat pokušaja matematičkog opisa fleksibilnih tračnica izrađenih od elastičnog materijala (mehanički klinovi), koje su dugo koristili crtači u slučajevima kada je postalo potrebno nacrtati dovoljno glatku krivulju kroz zadanih bodova. Poznato je da tračnica izrađena od elastičnog materijala, fiksirana na određenim točkama i nalazeći se u ravnotežnom položaju, poprima oblik u kojem je njezina energija minimalna. Ovo temeljno svojstvo omogućuje učinkovito korištenje splineova u rješavanju praktičnih problema obrade eksperimentalnih informacija.

2. INTERPOLACIJA

2.1 Interpolacija s kvadratnim splineom

Dakle, na svakom parcijalnom segmentu interpolacije izgradit ćemo funkciju oblika:

Tražit ćemo koeficijente spline-a prema sljedećim uvjetima:

a) Lagrangeovi uvjeti

b) neprekidnost prve derivacije u čvornim točkama

Zadnja dva uvjeta daju jednadžbe, dok broj nepoznatih koeficijenata. Jednadžba koja nedostaje može se dobiti iz dodatnih uvjeta nametnutih ponašanju splajna. Na primjer, možete zahtijevati da vrijednost prve derivacije splajna s 1 u točki x 0 bude nula, tj.

Zamjenom ovih izraza dolazimo do sljedećih jednadžbi

gdje notacija

Izrazimo koeficijente iz druge jednadžbe c 1 , nakon što u njega zamijenite vrijednosti koeficijenata a 1 iz prve jednadžbe:

Zatim, zamjenom ovog izraza u jednadžbu sustava, dobivamo jednostavnu rekurzivnu relaciju za koeficijente

Sada algoritam za određivanje koeficijenata splineova postaje sasvim očit. Prvo, koristeći formulu, određujemo vrijednosti svih koeficijenata, uzimajući u obzir činjenicu da. Zatim, prema formuli, izračunavamo koeficijente. Koeficijenti se određuju iz prve jednadžbe sustava. U tom slučaju, postupak za izračunavanje koeficijenata splineova potrebno je provesti samo jednom.

Nakon što su koeficijenti izračunati, za izračun samog splinea dovoljno je odrediti broj intervala u koji spada točka interpolacije, te koristiti formulu. Za određivanje broja intervala koristit ćemo se algoritmom sličnim onom korištenom u prethodnom primjeru za komadno kvadratnu interpolaciju.

2.2 Interpolacija pomoću kubičnog splajna

Kubični interpolacijski spline , prikladno za ovu funkciju f(x) i zadane čvorove x ja, naziva se funkcija S(x), zadovoljavaju sljedeće uvjete:

1. Na svakom segmentu [ x ja- 1 , x ja], i = 1, 2, ..., N funkcija S(x) je polinom trećeg stupnja,

2. Funkcija S(x), a također su njegova prva i druga derivacija neprekidne na intervalu [ a, b],

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

Na svakom od segmenata [x ja- 1 , x ja], i = 1, 2, ..., N tražit ćemo funkciju S(x)= S ja(x) u obliku polinoma trećeg stupnja:

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

x ja- 1 Ј xЈ x ja,

Gdje a ja,b ja, c ja, d ja- koeficijente koji se uopće određuju n elementarni segmenti. Da bi sustav algebarskih jednadžbi imao rješenje, broj jednadžbi mora biti točno jednak broju nepoznanica. Dakle, trebali bismo dobiti 4 n jednadžbe.

Prvo 2 n jednadžbe dobivamo iz uvjeta da graf funkcije S(x) mora proći kroz zadane točke, tj.

S ja(x ja- 1)=y ja- 1 , S ja(x ja) = g ja.

Ovi se uvjeti mogu napisati kao:

S ja(x ja- 1)= a ja=y ja- 1 ,

S ja(x ja)= a ja+b jah ja+c jah + d jah = y ja,

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

Sljedeće 2 n- 2 jednadžbe proizlaze iz uvjeta neprekidnosti prve i druge derivacije u čvorovima interpolacije, odnosno uvjeta glatkoće krivulje u svim točkama.

S" ja + 1 (x ja)=S" ja(x ja), ja = 1, ..., n - 1,

S"" ja + 1 (x ja)=S"" ja(x ja), i = 1, ..., n - 1,

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

S" ja + 1 (x)= b ja + 1 + 2 c ja + 1 (x-x ja) + 3 d ja + 1 (x-x ja).

Izjednačavanje u svakom unutarnjem čvoru x = x ja vrijednosti ovih izvedenica, izračunate u intervalima lijevo i desno od čvora, dobivamo (uzimajući u obzir h ja= x ja-x ja- 1):

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

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

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

Ako x = x ja

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

Na ovoj fazi imamo 4 n nepoznato i 4 n- 2 jednadžbe. Stoga je potrebno pronaći još dvije jednadžbe.

Uz slobodno fiksiranje krajeva, zakrivljenost linije u tim točkama može se izjednačiti s nulom. Iz uvjeta nulte zakrivljenosti na krajevima slijedi da su druge derivacije jednake nuli u ovim točkama:

S 1" " (x 0) = 0 i S n" "(x n) = 0,

c ja = 0 I 2 c n + 6 d nh n = 0.

Jednadžbe čine sustav linearnih algebarskih jednadžbi za određivanje 4 n koeficijenti: a ja,b ja, c ja, d ja (ja = 1, 2, . . ., n).

Ovaj sustav se može svesti na prikladniji oblik. Iz uvjeta možete odmah pronaći sve koeficijente a ja

ja = 1, 2, ..., n- 1,

Zamjenom dobivamo:

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

b n = - (h nc n)

Eliminirajte koeficijente iz jednadžbe b ja I d ja. Konačno, dobivamo sljedeći sustav jednadžbi samo za koeficijente S ja:

c 1 = 0 i c n+ 1 = 0:

h ja- 1 c ja- 1 + 2 (h ja- 1 + h ja) c ja+ h jac ja + 1 = 3 ,

ja = 2, 3, ..., n.

Prema pronađenim koeficijentima S ja lako izračunati d ja,b ja.

2.3 Izjava problema

Na segmentu [ a, b] dani su n + 1 bodova x ja = x 0 , x 1 , . . ., x n, koji se nazivaju čvorovi interpolacija , i vrijednost neke funkcije f(x) na ovim točkama

f(x 0)=y 0 , f(x 1) = g 1 , . . ., f(x n)=y n.

Korištenje kubičnih splineova za izgradnju interpolacijske funkcije f(x).

3. INTERPOLACIJSKI ALGORITAM KORIŠTENJEM KUBIČNOG SPLINEA

Upoznajmo se s algoritmom programa.

1. Izračunajte vrijednosti i

2. Na temelju ovih vrijednosti izračunavamo koeficijente zamaha i o.

3. Na temelju dobivenih podataka izračunavamo koeficijente

4. Zatim računamo vrijednost funkcije koristeći spline.

4. DIZAJN SOFTVERA

5. REZULTATI SOFTVERA

5.1 Opis testnih slučajeva

Tijekom ovog kolegija razvijen je softverski modul koji kroz dostupne točke iscrtava krivulju koja im odgovara. Provedeni su testni slučajevi kako bi se provjerila učinkovitost rada.

5.2 Rezultati ispitivanja

Za provjeru ispravnog izvođenja testnih slučajeva koristi se funkcija cspline ugrađena u paket MATHCAD, koja vraća vektor druge derivacije pri približavanju kubnom polinomu u referentnim točkama.

5.3 Test slučaj 1

Slika 1.1 - rezultat programa

Testni slučaj 2

Slika 1.2 - rezultat programa

Testni slučaj 3

Slika 1.3 - rezultat programa

ZAKLJUČAK

spline funkcija interpolacije computational

U računalnoj matematici interpolacija funkcija igra bitnu ulogu, tj. konstrukcija zadane funkcije druge (obično jednostavnije), čije se vrijednosti podudaraju s vrijednostima zadane funkcije u određenom broju točaka. Štoviše, interpolacija ima i praktično i teoretsko značenje. U praksi se često javlja problem obnavljanja kontinuirane funkcije iz njezinih tabličnih vrijednosti, primjerice onih dobivenih tijekom nekog eksperimenta. Za izračun mnogih funkcija pokazalo se učinkovitim aproksimirati ih polinomima ili frakcijskim racionalnim funkcijama. Teorija interpolacije koristi se u konstrukciji i proučavanju kvadraturnih formula za numeričku integraciju, kako bi se dobile metode za rješavanje diferencijalnih i integralnih jednadžbi. Glavni nedostatak polinomske interpolacije je da je nestabilna na jednoj od najprikladnijih i najčešće korištenih mreža - mreži s ekvidistantnim čvorovima. Ako problem dopušta, ovaj se problem može riješiti odabirom mreže s Chebyshevljevim čvorovima. Međutim, ako ne možemo slobodno birati interpolacijske čvorove ili samo trebamo algoritam koji nije previše zahtjevan za izbor čvorova, tada racionalna interpolacija može biti prikladna alternativa polinomskoj interpolaciji.

Prednosti spline interpolacije uključuju veliku brzinu obrade računalnog algoritma, budući da je spline funkcija polinoma po komadu i tijekom interpolacije se podaci istovremeno obrađuju za mali broj mjernih točaka koje pripadaju fragmentu koji se razmatra u ovaj trenutak. Interpolirana površina opisuje prostornu varijabilnost različitih mjerila i istovremeno je glatka. Potonja okolnost omogućuje izravnu analizu geometrije i topologije površine pomoću analitičkih postupaka.

BIBLIOGRAFIJA

1. B. V. Sobol, B. Ch. Meskhi, I. M. Peshkhoev. Radionica iz računalne matematike. - Rostov na Donu: Phoenix, 2008.;

2. N.S. Bahvalov, N.P. Židkov, G.M. Kobelkov. Numeričke metode. Izdavačka kuća "Laboratorij temeljnih znanja". 2003. godine

3. www.wikipedia.ru/spline

Slični dokumenti

Računalne metode linearne algebre. Interpolacija funkcije. Newtonov interpolacijski polinom. interpolacijski čvorovi. Lagrangeov interpolacijski polinom. Spline interpolacija. Koeficijenti kubičnih splineova.

laboratorijski rad, dodan 06.02.2004


U računalnoj matematici interpolacija funkcija igra bitnu ulogu. Lagrangeova formula. Interpolacija prema Aitkenovoj shemi. Newtonove interpolacijske formule za ekvidistantne čvorove. Newtonova formula s podijeljenim razlikama. Spline interpolacija.

kontrolni rad, dodano 05.01.2011


Konstruirajte Newtonov interpolacijski polinom. Nacrtajte graf i na njemu označite interpolacijske čvorove. Konstruirajte Lagrangeov interpolacijski polinom. Izvršite spline interpolaciju trećeg stupnja.

laboratorijski rad, dodan 06.02.2004


Uloga interpolacije funkcija, čije se vrijednosti podudaraju s vrijednostima dane funkcije u određenom broju točaka. Interpolacija funkcija polinomima, izravno kontinuirane funkcije na segmentu iu točki. Definicija pojma greške interpolacije.

seminarski rad, dodan 10.04.2011


Kontinuirana i točkasta aproksimacija. Interpolacijski polinomi Lagrangea i Newtona. Globalna pogreška interpolacije, kvadratna ovisnost. Metoda najmanjeg kvadrata. Odabir empirijskih formula. Dijelno konstantna i komadno linearna interpolacija.

seminarski rad, dodan 14.03.2014


Upoznavanje s poviješću pojave metode zlatnog reza. Razmatranje osnovnih pojmova i algoritama za izvođenje izračuna. Proučavanje metode Fibonaccijevih brojeva i njezinih značajki. Opis primjera primjene metode zlatnog reza u programiranju.

seminarski rad, dodan 09.08.2015


Problemi globalne i lokalne interpolacije Lagrangea i Newtona; colive ponašanje interpolacijskog polinoma; Runge funkcije. Spline je skupina polinoma koji se nazivaju kubični polinomi s nepropusnim prvim i drugim sličnim, prednosti interpolacije splajnom.

prezentacija, dodano 06.02.2014


Metode numeričkog diferenciranja. Izračunavanje derivacije, najjednostavnije formule. Numeričko diferenciranje temeljeno na interpolaciji algebarskim polinomima. Aproksimacija Lagrangeovim polinomom. Diferencijacija, korištenjem interpolacije.

seminarski rad, dodan 15.02.2016


Opis metoda za rješavanje sustava linearnih algebarskih jednadžbi: inverzna matrica, Jacobi, Gauss-Seidel. Formulacija i rješenje problema interpolacije. Izbor polinomske ovisnosti metodom najmanjih kvadrata. Značajke metode opuštanja.

laboratorijski rad, dodano 06.12.2011


Problem nalaženja ekstrema: bit i sadržaj, optimizacija. Rješenje metodama kvadratne interpolacije i zlatnog reza, njihove usporedne karakteristike, utvrđivanje glavnih prednosti i nedostataka. Broj ponavljanja i procjena točnosti.

Krivulje i plohe koje se susreću u praktičnim problemima često imaju prilično složen oblik, koji ne dopušta univerzalnu analitičku specifikaciju cjeline uz pomoć elementarnih funkcija. Stoga se sastavljaju od relativno jednostavnih glatkih fragmenata - segmenata (krivulja) ili rezova (ploha), od kojih se svaki može sasvim zadovoljavajuće opisati pomoću elementarnih funkcija jedne ili dvije varijable. U ovom slučaju sasvim je prirodno zahtijevati da glatke funkcije koje se koriste za konstruiranje parcijalnih krivulja ili površina imaju sličnu prirodu, na primjer, budu polinomi istog stupnja. A kako bi rezultirajuća krivulja ili površina bila dovoljno glatka, potrebno je biti posebno pažljiv na spojevima odgovarajućih fragmenata. Stupanj polinoma bira se iz jednostavnih geometrijskih razmatranja i u pravilu je mali. Za glatku promjenu tangente duž cijele složene krivulje dovoljno je spojne krivulje opisati polinomima trećeg stupnja, kubnim polinomima. Koeficijenti takvih polinoma uvijek se mogu odabrati tako da je zakrivljenost odgovarajuće složene krivulje kontinuirana. Kubični splinovi koji nastaju pri rješavanju jednodimenzionalnih problema mogu se prilagoditi oblikovanju fragmenata složenih ploha. I tu se, sasvim prirodno, pojavljuju bikubični splineovi, opisani polinomima trećeg stupnja u svakoj od dviju varijabli. Rad s takvim klinovima zahtijeva mnogo više izračuna. Ali pravilno organiziran proces omogućit će maksimalno uzimanje u obzir stalno rastućih mogućnosti računalne tehnologije. Spline funkcije Neka na segmentu , tj. Napomena. Indeks (t) brojeva a^ pokazuje da. da je skup koeficijenata kojima je određena funkcija S(x) na svakom parcijalnom segmentu D vlastiti. Na svakom segmentu D1, spline 5(x) je polinom stupnja p i određen je na tom segmentu p + 1 koeficijentom. Ukupni parcijalni segmenti - zatim. Dakle, da bi se potpuno odredio spline potrebno je pronaći (p + 1) zatim brojeve. Uvjet) označava neprekidnost funkcije S(x) i njezinih izvodnica u svim unutarnjim čvorovima mreže w. Broj takvih čvorova je m - 1. Dakle, da bi se pronašli koeficijenti svih polinoma, dobiva se p(m - 1) uvjeta (jednadžbi). Za potpunu definiciju splajna nema dovoljno (uvjeta (jednadžbi). Izbor dodatnih uvjeta određen je prirodom problema koji se razmatra, a ponekad jednostavno željom korisnika. TEORIJA SPLINE Primjeri rješenja Najčešće se razmatraju problemi interpolacije i izglađivanja, kada je potrebno izgraditi jedan ili drugi spline iz zadanog niza točaka na ravnini. U problemima interpolacije, potrebno je da spline graf prolazi kroz točke, koje nameće m + 1 dodatnih uvjeta (jednadžbi) na svoje koeficijente. Preostali p - 1 uvjeti (jednadžbe) za jedinstvenu konstrukciju splinea najčešće se postavljaju u obliku vrijednosti donjih izvodnica splinea na krajevima segmenta koji se razmatra [a, 6] - granica ( rubni) uvjeti. Sposobnost odabira različitih rubnih uvjeta omogućuje vam da izgradite splineove s različitim svojstvima. U problemima izglađivanja, spline se gradi tako da njegov graf prolazi blizu točaka (i "" Y "), * = 0, 1, ..., m, a ne kroz njih. Mjera ove blizine može se definirati na različite načine, što dovodi do značajne raznolikosti izglađujućih splajnova. Opisane mogućnosti izbora pri konstruiranju splajn funkcija ni izdaleka ne iscrpljuju njihovu raznolikost. I ako su se u početku razmatrale samo komadno-polinomne spline funkcije, kako se proširio opseg njihove primjene, spline su se počeli pojavljivati ​​"zalijepljeni" i od drugih elementarnih funkcija. Interpolacijski kubični splinovi Izjava problema interpolacije Neka je rešetka w dana na intervalu [a, 6) Razmotrimo skup brojeva Problem. Konstruirajte funkciju koja je glatka na segmentu (a, 6] i poprima zadane vrijednosti u čvorovima mreže o, tj. "Nametanjem dodatnih uvjeta na funkciju koja se konstruira, može se postići potrebna jedinstvenost. U primjene, često postaje potrebno aproksimirati analitički zadanu funkciju pomoću funkcije s propisanim dovoljno dobrim svojstvima. Na primjer, u slučajevima kada se računanje vrijednosti zadane funkcije f(x) na segmentu točaka [a, 6] povezana sa značajnim poteškoćama i/ili zadana funkcija f(x) nema traženu glatkoću, zgodno je koristiti drugu funkciju koja bi dovoljno dobro aproksimirala zadanu funkciju i bila lišena njezinih nedostataka [a, 6] glatka funkcija a(x) koja se podudara u čvorovima mreže w s danom funkcijom /(X). Definicija interpolirajućeg kubičnog splajna Interpolirajući kubični splajn S(x) na mreži w je funkcija koja je 1) na svakom od segmenata polinom trećeg stupnja, 2) dvaput je kontinuirano diferencijabilna na segmentu [a, b ], odnosno pripada klasi C2[ a, 6], i 3) zadovoljava uvjete Na svakom od segmenata, spline S(x) je polinom trećeg stupnja i određen je na ovom segmentu s četiri koeficijenta. Ukupan broj segmenata je m. To znači da je za potpuno određivanje spline potrebno pronaći 4m brojeva. Uvjet znači neprekidnost funkcije S (x) i njezinih izvodnica S "(x) i 5" (x) na svim unutarnjim čvorovima mreže w. Broj takvih čvorova je m - 1. Dakle, da bi se pronašli koeficijenti svih polinoma, dobiju se još 3 (m - 1) uvjeta (jednadžbi). Zajedno s uvjetima (2) dobivaju se uvjeti (jednadžbe). Rubni (granični) uvjeti Dva nedostajuća uvjeta navedena su kao ograničenja vrijednosti splajna i/ili njegovih izvoda na krajevima intervala [a, 6]. Pri konstruiranju interpolirajućeg kubičnog splajna najčešće se koriste rubni uvjeti sljedeća četiri tipa. A. Rubni uvjeti 1. vrste. - na kraju intervala [a, b] daju se vrijednosti prve derivacije željene funkcije. B. Rubni uvjeti 2. vrste. - na kraju intervala (a, 6) postavljaju se vrijednosti druge derivacije željene funkcije. B. Rubni uvjeti 3. vrste. nazivaju se periodičnim. Prirodno je zahtijevati ispunjenje ovih uvjeta u slučajevima kada je interpolirana funkcija periodična s periodom T = b-a. D. Rubni uvjeti 4. vrste. zahtijevaju poseban komentar. Komentar. U unutarnjim sepsi čvorovima treća derivacija funkcije S(x) je, općenito govoreći, diskontinuirana. Međutim, broj diskontinuiteta treće derivacije može se smanjiti primjenom uvjeta 4. tipa. U tom slučaju konstruirani spline bit će kontinuirano diferencijabilan tri puta na intervalima.. Konstrukcija interpolirajućeg kubičnog splinea Opišimo metodu za izračunavanje koeficijenata kubičnog splinea, u kojoj je broj veličina koje treba odrediti jednak. Na svakom od intervala traži se interpolacijska spline funkcija u sljedećem obliku Za rubne uvjete 1. i 2. vrste ovaj sustav ima sljedeći oblik gdje koeficijenti ovise o izboru rubnih uvjeta. Rubni uvjeti 1. vrste: Rubni uvjeti 2. vrste: Kod rubnih uvjeta 3. vrste sustav za određivanje brojeva zapisuje se na sljedeći način. Za rubne uvjete 4. vrste sustav za određivanje brojeva ima oblik Matrice sva tri linearna algebarska sustava su matrice s dijagonalnom dominacijom. Ove matrice nisu degenerirane, pa stoga svaki od ovih sustava ima jedinstveno rješenje. Teorema. Interpolacijski kubni splajn koji zadovoljava uvjete (2) i rubni uvjet jednog od četiri navedena tipa postoji i jedinstven je. Dakle, konstruirati interpolirajući kubični spline znači pronaći njegove koeficijente. Kada se pronađu koeficijenti splinea, vrijednost splinea S(x) u proizvoljnoj točki segmenta [a, b] može se pronaći pomoću formule ( 3). Međutim, za praktične proračune prikladniji je sljedeći algoritam za pronalaženje veličine S(x). Neka je x 6 [x", Prvo se vrijednosti A i B izračunaju prema formulama, a zatim se pronađe vrijednost 5(x): Korištenje ovog algoritma značajno smanjuje računalne troškove za određivanje vrijednosti Savjeti za korisnik Izbor rubnih (rubnih) uvjeta i interpolacijskih čvorova omogućuje do određene mjere kontrolu svojstava interpolacijskih splajnova. A. Izbor rubnih (rubnih) uvjeta. Izbor rubnih uvjeta jedan je od središnjih problema u interpolaciji funkcija. Posebnu važnost dobiva u slučaju kada je potrebno osigurati visoku točnost aproksimacije funkcije f(x) splajnom 5(g) u blizini krajeva segmenta [a, 6]. Granične vrijednosti imaju primjetan učinak na ponašanje splajna 5(g) u blizini točaka a i b, a taj učinak brzo slabi kako se od njih udaljavamo. Izbor rubnih uvjeta često je određen prisutnošću dodatne informacije o ponašanju funkcije f(x) koja se aproksimira. Ako su vrijednosti prve derivacije f "(x) poznate na krajevima segmenta (a, 6), tada je prirodno koristiti rubne uvjete 1. tipa. Ako su vrijednosti drugog izvedenice f"(x) poznate na krajevima segmenta [a, 6], onda je to prirodna uporaba rubnih uvjeta 2. vrste. Ako je moguće birati između rubnih uvjeta 1. i 2. tipa, tada prednost treba dati uvjetima 1. tipa. Ako je f(x) periodična funkcija, tada se trebamo zaustaviti na rubnim uvjetima 3. vrste. Ako nema dodatnih informacija o ponašanju funkcije koja se aproksimira, često se koriste tzv. prirodni rubni uvjeti.Međutim, treba imati na umu da pri takvom izboru rubnih uvjeta točnost aproksimacije funkcije f (x) splineom S (x) blizu krajeva segmenta (a, ft] naglo se smanjuje. Ponekad se koriste rubni uvjeti 1. ili 2. tipa, ali ne s točnim vrijednostima odgovarajućih derivacija, ali s njihovim razlikama aproksimacija. Točnost ovog pristupa je niska. Praktično iskustvo proračuna pokazuje da su u razmatranoj situaciji najprikladniji izbor rubni uvjeti tipa 4. B. Izbor interpolacijskih čvorova. Ako je treća derivacija f " " (x) funkcije je diskontinuirana u nekim točkama segmenta [a, b], tada za poboljšanje kvalitete aproksimacije te točke treba uključiti u broj interpolacijskih čvorova. druga derivacija / "(x), tada se moraju poduzeti posebne mjere kako bi se izbjeglo osciliranje splinea u blizini točaka diskontinuiteta. čvorovi interpolacije biraju se na takav način da točke diskontinuiteta druge derivacije padaju unutar intervala \xif), tako da. Vrijednost a može se odabrati numeričkim eksperimentom (često je dovoljno postaviti a = 0,01). Postoji niz recepata za prevladavanje poteškoća koje se javljaju kada je prva derivacija f "(x) diskontinuirana. Kao jedan od najjednostavnijih, možemo predložiti ovaj: podijeliti segment aproksimacije u intervale gdje je derivacija kontinuirana, i izgraditi spline na svakom od ovih intervala Odabir interpolacijske funkcije (za i protiv) Pristup 1. Lagrangeov interpolacijski polinom Za dani niz TEORIJA SPLINE primjeri rješenja (slika 3) Lagrangeov interpolacijski polinom određen je formulom Preporučljivo je razmotriti svojstva Lagrangeovog interpolacijskog polinoma iz dva suprotna položaja, raspravljajući o glavnim prednostima odvojeno od nedostataka --ti pristup: 1) graf Lagrangeovog interpolacijskog polinoma prolazi kroz svaku točku niza, 2) konstruirana funkcija lako se opisuje ( broj koeficijenata Lagrangeovog interpolacijskog polinoma na rešetki u koji treba odrediti jednak je m + 1), 3) konstruirana funkcija ima kontinuirane derivacije bilo koje pore 4) interpolacijski polinom je jedinstveno definiran zadanim nizom. Glavni nedostaci 1. pristupa: 1) stupanj Lagrangeovog interpolacijskog polinoma ovisi o broju čvorova mreže, a što je taj broj veći, to je veći stupanj interpolacijskog polinoma i, prema tome, potrebno je više izračuna, 2 ) promjena barem jedne točke u nizu zahtijeva potpuni ponovni izračun koeficijenata Lagrangeovog interpolacijskog polinoma, 3) dodavanje nove točke u niz povećava stupanj Lagrangeova interpolacijskog polinoma za jedan i čak dovodi do potpunog ponovnog izračuna njegovih koeficijenata , 4) s neograničenim usklađivanjem mreže, stupanj Lagrangeova interpolacijskog polinoma raste neograničeno. Ponašanje Lagrangeovog interpolacijskog polinoma pod neograničenim usklađivanjem mreže općenito zahtijeva posebnu pozornost. Komentari A. Aproksimacija kontinuirane funkcije polinomom. Poznato je (Weierstrass, 1885) da se bilo koja kontinuirana (a još više glatka) funkcija na intervalu može aproksimirati kao i željeti na tom intervalu polinomom. Opišimo tu činjenicu jezikom formula. Neka je f(x) funkcija kontinuirana na segmentu [a, 6]. Tada za bilo koji e > 0 postoji polinom Rn(x) takav da će za bilo koji x iz intervala [a, 6] nejednakost biti zadovoljena (slika 4), ima ih beskonačno mnogo. Na segmentu [a, 6] konstruiramo mrežu w. Jasno je da se njegovi čvorovi, općenito govoreći, ne poklapaju sa sjecištima grafova polinoma Pn(x) i funkcije f(x) (slika 5). Stoga za preuzetu mrežu polinom Pn(x) nije interpolacijski polinom. Kada se kontinuirana funkcija aproksimira interpolacijskim polinomom Jla-grajj, njezin graf ne samo da ne mora biti blizu grafa funkcije f(x) u svakoj točki intervala [a, b), nego može odstupati od ovu funkciju onoliko koliko želite. Navedimo dva primjera. Primjer 1 (Rung, 1901). S neograničenim porastom broja čvorova za funkciju na intervalu [-1, 1] granična jednakost je ispunjena (slika 6) Primjer 2 (Berichtein, 1912). Niz Lagrangeovih interpolacijskih polinoma konstruiranih na uniformnim mrežama nm za kontinuiranu funkciju /(x) = |x| na segmentu s povećanjem broja čvorova m ne teži funkciji f(x) (slika 7). Pristup 2. Komadno linearna interpolacija Ako se odustane od glatkoće interpolirane funkcije, omjer između broja prednosti i broja nedostataka može se zamjetno promijeniti u smjeru prvog. Konstruirajmo komadno linearnu funkciju uzastopnim povezivanjem točaka (xit y,) s ravnim segmentima (slika 8). Glavne prednosti 2. pristupa su: 1) graf komadno-linearne funkcije prolazi kroz svaku točku niza, 2) konstruirana funkcija se lako opisuje (broj koeficijenata odgovarajućih linearnih funkcija treba odrediti za mrežu (1) je 2m), 3) konstruirana funkcija definirana je danim nizom nedvosmisleno, 4) stupanj polinoma korištenih za opisivanje funkcije interpolacije ne ovisi o broju čvorova mreže (jednak 1), 5) mijenjanje jedna točka u nizu zahtijeva izračun četiri broja (koeficijenti dviju pravocrtnih veza koje izlaze iz nove točke), 6) dodavanje dodatne točke u niz zahtijeva izračun četiri koeficijenta. Djelomično linearna funkcija ponaša se prilično dobro kada sužava rešetku. i Glavni nedostatak 2. pristupa je da aproksimirajuća linearna po komadu funkcija nije glatka: prve derivacije trpe diskontinuitet u čvorovima mreže (uši interpolacije). Pristup 3. Spline interpolacija Predloženi pristupi mogu se kombinirati tako da se očuva niz navedenih prednosti oba pristupa uz smanjenje broja nedostataka. To se može učiniti konstruiranjem glatke interpolirajuće spline funkcije stupnja p. Glavne prednosti 3. pristupa: 1) graf konstruirane funkcije prolazi kroz svaku točku niza, 2) konstruiranu funkciju je relativno lako opisati (broj koeficijenata odgovarajućih polinoma treba odrediti za mrežu ( 1) je 3) konstruirana funkcija je jednoznačno određena zadanim nizom, 4) polinom stupnja ne ovisi o broju čvorova mreže i stoga se ne mijenja s njegovim povećanjem, 5) konstruirana funkcija ima kontinuirane derivacije prema gore reda p - 1 uključivo, 6) konstruirana funkcija ima dobra svojstva aproksimacije. Kratka referenca. Predloženi naziv - spline - nije slučajan - glatke po komadu polinomske funkcije koje smo uveli i crtanje splineova usko su povezane. Razmotrite fleksibilno, idealno tanko ravnalo koje prolazi kroz referentne točke niza smještene na (x, y) ravnini. Prema Bernoulli-Eulerovom zakonu, linearizirana jednadžba zakrivljenog ravnala ima oblik Funkcija S(x), koja opisuje ravnala, polinom je trećeg stupnja između svake i dviju susjednih točaka niza (nosača) i dvaput je kontinuirano diferencijabilna na cijelom intervalu (a, 6). Komentar. 06 Interpolacija kontinuirane funkcije Za razliku od Lagrangeovih interpolacijskih polinoma, niz interpolacijskih kubičnih splajnova na uniformnoj mreži uvijek konvergira u interpoliranu kontinuiranu funkciju, a s poboljšanjem diferencijalnih svojstava ove funkcije, stopa konvergencije raste. Primjer. Za funkciju, kubični spline na mreži s brojem čvorova m = 6 daje pogrešku aproksimacije istog reda kao interpolacijski polinom Ls(z), a na mreži s brojem čvorova m = 21 ta je pogreška jednaka toliko mali da se u mjerilu običnog crteža knjige jednostavno ne može prikazati (slika 10) (interpolacijski polinom 1>2o(r) daje u ovom slučaju pogrešku od oko 10 000 W). Svojstva interpoliranog kubičnog splajna A. Aproksimativna svojstva kubičnog splajna. Svojstva aproksimacije interpolirajućeg splajna ovise o glatkoći funkcije f(x) - što je veća glatkoća interpolirane funkcije, to je viši red aproksimacije, a kada je mreža pročišćena, to je veća stopa konvergencije. Ako je interpolirana funkcija f(x) kontinuirana na intervalu Ako interpolirana funkcija f(x) ima kontinuiranu prvu derivaciju na intervalu [a, 6], odnosno interpolacijski spline koji zadovoljava rubne uvjete 1. ili 3. tipa, tada za h imamo U ovom slučaju, ne samo da spline konvergira interpoliranoj funkciji, nego i derivacija splinea konvergira derivaciji te funkcije. Ako spline S(x) aproksimira funkciju f(x) na segmentu [a, b], a njegova prva odnosno druga derivacija aproksimira funkciju B. Ekstremno svojstvo kubičnog splina. Interpolacijski kubni spline ima još jedan korisno svojstvo . Razmotrite sljedeći primjer. primjer. Konstruirajte funkciju /(x) minimizirajući funkcional na klasi funkcija iz prostora C2 čiji grafovi prolaze kroz točke niza x) koja zadovoljava rubne uvjete daje ekstrem (minimum) funkcionalu. Opaska 2. Zanimljivo je uočiti da interpolacijski kubični spline ima svojstvo ekstremnosti opisano gore na vrlo širokoj klasi funkcija, naime na klasi |0, 5]. 1.2. Izglađivanje kubičnih splinova O formulaciji problema izglađivanja Neka su zadani mreža i skup brojeva. Zapravo, to znači da je za svaki određen interval, a bilo koji broj iz tog intervala može se uzeti kao vrijednost y, . Prikladno je tumačiti vrijednosti y, na primjer, kao rezultate mjerenja neke funkcije y(x) za zadane vrijednosti varijable x, koja sadrži slučajnu pogrešku. Prilikom rješavanja problema vraćanja funkcije iz takvih "eksperimentalnih" vrijednosti, teško da je preporučljivo koristiti interpolaciju, jer će interpolacijska funkcija poslušno reproducirati bizarne oscilacije uzrokovane slučajnom komponentom u nizu (y,). Prirodniji pristup temelji se na postupku izglađivanja koji je dizajniran da nekako smanji element slučajnosti kao rezultat mjerenja. Obično se u takvim problemima traži pronaći funkciju čije bi vrijednosti za x = x, * = 0, 1, .... m, spadale u odgovarajuće intervale i koja bi, uz to, imala dovoljno dobra svojstva. Na primjer, imao bi kontinuiranu prvu i drugu derivaciju ili mu graf ne bi bio previše zakrivljen, odnosno ne bi imao jake oscilacije. Problem te vrste također nastaje kada se prema zadanom (točno) nizu traži konstruirati funkcija koja bi prolazila kroz nezadane točke, ali blizu njih i, štoviše, mijenjala se prilično glatko. Drugim riječima, željena funkcija je izgladila dani niz, takoreći, a nije ga interpolirala. Neka je dana mreža w i dva skupa brojeva TEORIJA SPLINE primjeri rješenja Problem. Konstruirajte glatku funkciju na segmentu [a, A] čije se vrijednosti nalaze u čvorovima mreže i razlikuju se od brojeva y za zadane vrijednosti. Formulirani problem zaglađivanja je oporavak glatka funkcija data u tablici. Jasno je da takav problem ima mnogo različitih rješenja. Postavljanjem dodatnih uvjeta na konstruiranu funkciju možemo postići potrebnu jedinstvenost. Definicija izglađujućeg kubičnog splajna Izglađujući kubični splajn S(x) na mreži w je funkcija koja je 1) na svakom od segmenata polinom trećeg stupnja, 2) dvaput je kontinuirano diferencijabilna na segmentu [a, 6 ], odnosno pripada klasi C2 [a , b], 3) daje minimum funkcionalu gdje su zadani brojevi, 4) zadovoljava rubne uvjete jednog od tri dolje navedena tipa. Rubni (rubni) uvjeti Rubni uvjeti navedeni su kao ograničenja vrijednosti splinea i njegovih izvedenica na graničnim čvorovima mreže w. A. Rubni uvjeti 1. vrste. - na kraju intervala [a, b) dane su vrijednosti prve derivacije željene funkcije. Rubni uvjeti 2. vrste. - druge derivacije željene funkcije na krajevima intervala (a, b] jednake su nuli. B. Rubni uvjeti 3. tipa nazivaju se periodičkim. Teorem. Kubični spline S (x), minimizirajući funkcional (4 ) i zadovoljavanje rubnih uvjeta jednog od tri naznačena tipa je jedinstveno definirano. Definicija. Kubični splajn koji minimizira funkcional J(f) i zadovoljava rubne uvjete i-tipa naziva se izglađujući splajn i-tipa .ovaj segment s četiri koeficijenta.Ukupni segmenti - m.Dakle, da bi se u potpunosti definirao spline potrebno je pronaći 4m brojeva.Uvjet znači kontinuitet funkcije 5(ar) i svih derivacija u svim unutarnjim čvorovima funkcije 5(ar). grid o. "Broj takvih čvorova je m - 1 Dakle, za pronalaženje koeficijenata svih polinoma dobivaju se 3(m - 1) uvjeta (jednadžbi). za koji je broj veličina koje treba odrediti 2m + 2. Na svakom od intervala traži se izglađujuća splajn funkcija u sljedećem obliku Opišimo najprije kako se nalaze količine n*. Za rubne uvjete 1. i 2. vrste, sustav linearnih jednadžbi za određivanje vrijednosti Hi zapisan je u sljedećem obliku gdje su poznati brojevi). Koeficijenti ovise o izboru rubnih uvjeta. Rubni uvjeti 1. vrste: Rubni uvjeti 2. vrste: U slučaju rubnih uvjeta 3. vrste, sustav za određivanje brojeva zapisan je na sljedeći način: štoviše, svi koeficijenti izračunavaju se formulama (5) (veličine s indeksi k i m + k smatraju se jednakima: Važna* napomena. Matrice sustava nisu degenerirane, pa stoga svaki od tih sustava ima jedinstveno rješenje. Ako su brojevi n, - pronađeni, tada se veličine lako određuju formulama Ako sve i spline za izglađivanje ispadne interpolacijski. To posebno znači da što su vrijednosti preciznije dane, to je manja vrijednost predskale odgovarajućih težinskih koeficijenata. Ako je, s druge strane, potrebno da spline prolazi kroz točku (x^, yk), tada se težinski faktor p\ koji tome odgovara mora postaviti jednak nuli. U praktičnim proračunima najvažniji je izbor vrijednosti pi- Neka D, - pogreška mjerenja vrijednosti y,. Tada je prirodno zahtijevati da izglađujući spline zadovoljava uvjet ili, što je isto.U najjednostavnijem slučaju težinski koeficijenti pi mogu se dati npr. u obliku - gdje je c neka dovoljno mala konstanta. Međutim, takav izbor težina p, ne dopušta korištenje "koridora" zbog pogrešaka u vrijednostima y, -. Racionalniji, ali i dugotrajniji algoritam za određivanje vrijednosti p, - može izgledati kako slijedi. Ako su vrijednosti pronađene u fc-toj iteraciji, tada se pretpostavlja gdje je e mali broj, koji je odabran eksperimentalno uzimajući u obzir bitnu mrežu računala, vrijednosti D i točnost rješavanje sustava linearnih algebarskih jednadžbi. Ako se u fc-toj iteraciji u točki i prekrši uvjet (6), tada će zadnja formula osigurati smanjenje odgovarajućeg težinskog koeficijenta p,. Ako zatim, u sljedećoj iteraciji, povećanje p, dovodi do potpunijeg korištenja "hodnika" (6) i, u konačnici, glatkije promjenjivog splajna. Malo teorije A. Obrazloženje formula za izračun koeficijenata interpolacijskog kubičnog splajna. Uvodimo oznaku gdje su m, nepoznate veličine. Njihov broj je jednak m + 1. Spline, napisan u obliku gdje zadovoljava uvjete interpolacije i kontinuiran je na cijelom intervalu [a, b\: uvrštavanjem formule dobivamo redom. Osim toga, ima kontinuirana prva derivacija na intervalu [a, 6]: diferenciranjem relacije (7) i postavljanjem dobivamo odgovarajuću. zapravo. Pokažimo da se brojevi m mogu odabrati tako da spline funkcija (7) ima kontinuiranu drugu derivaciju na intervalu [a, 6]. Izračunajte drugu derivaciju splajna na intervalu: U točki x, - 0 (pri t = 1) imamo Izračunajte drugu derivaciju splajna na intervalu U točki imamo Iz uvjeta neprekidnosti druge derivacije na unutarnjim čvorovima mreže a; dobivamo m - 1 relaciju gdje Dodavanjem ovih m - 1 jednadžbi još dvije, koje proizlaze iz i iz rubnih uvjeta, dobivamo sustav od m + 1 linearnih algebarskih jednadžbi s m + I nepoznatim miy i = 0, 1. ... , m. Sustav jednadžbi za izračunavanje vrijednosti gw u slučaju rubnih uvjeta 1. i 2. tipa ima oblik gdje je (rubni uvjeti 1. tipa), (rubni uvjeti 2. tipa). Za periodičke rubne uvjete (rubni uvjeti 3. tipa), mreža o; produljiti za još jedan čvor i pretpostaviti Tada će sustav za određivanje vrijednosti r* imati kontinuitet oblika na drugom i (th - !)th čvoru mreže. Imamo. Iz zadnje dvije relacije dobivamo dvije nedostajuće jednadžbe koje odgovaraju rubnim uvjetima 4. tipa: Isključivanjem nepoznate r0 iz jednadžbi i nepoznate pc iz jednadžbi, kao rezultat dobivamo sustav jednadžbi Imajte na umu da je broj nepoznanica u ovom sustavu jednak r - I. 6. Obrazloženje formula za izračun učinkovitosti izglađujućeg subičkog splajna. Uvodimo oznaku gdje su Zi i nj još nepoznate veličine. Njihov broj je jednak 2m + 2. Spline funkcija zapisana u obliku kontinuirana je na cijelom intervalu (a, 6]: stavljanjem ove formule dobivamo redom. Pokažimo da brojevi z i n mogu biti izabran tako da spline napisan u obliku ( 8), ima kontinuiranu prvu derivaciju na intervalu [a, 6] Izračunajte prvu derivaciju splinea S(x) na intervalu: U točki, imamo Iz uvjet kontinuiteta prve derivacije splajna u unutarnjim čvorovima mreže i --> dobivamo relaciju m - 1. Pogodno je ovu relaciju napisati u matričnom obliku. relacija (8) i postavkom dobivamo, odnos matrice Yeshe olyu dobiva se iz uvjeta minimuma funkcionala (4). Posljednje dvije matrične jednakosti mogu se smatrati linearnim sustavom od 2m + 2 linearne algebarske jednadžbe u 2m + 2 nepoznanice. Zamjenom stupca r u prvoj jednakosti s njegovim izrazom dobivenim iz relacije (9) dolazimo do matrične jednadžbe TEORIJA SPLINE primjeri rješenja za određivanje stupca M. Ova jednadžba ima jedinstveno rješenje zbog činjenice da matrica A + 6HRH7 je uvijek nedegeneriran. Pronašavši ga, lako ćemo identificirati gospodina Eamshinea. Elementi trokutamagolnih matrica A i H određuju n samo parametrima mreže u (s koracima hi) i ne ovise o vrijednostima yj. Linearni prostor kubičnih splajn funkcija Skup kubičnih splajnova konstruiranih na segmentu [a, 6) pomoću čvora wcra + l je linearni prostor dimenzije m + 3: 1) zbroj dvaju kubičnih splajnova konstruiranih pomoću mreže u> i umnožak kubičnog splina , izgrađenog na rešetki u>, proizvoljan broj tajniji su kubični spline izgrađeni na ovoj mreži, 2) bilo koji kubični spline izgrađen na mreži i iz čvora potpuno je određen s m + 1 pomoću vrijednost vrijednosti \u200b\u200of y "na ovim čvorovima i dva rubna uvjeta - samo + 3 parametra. Odabirom u tom prostoru baze koja se sastoji od m + 3 linearno neovisna splajna, proizvoljan kubični splajn a(x) možemo napisati kao njihovu linearnu kombinaciju na jedinstven način. Komentar. Takva specifikacija splinea široko se koristi u računskoj praksi. Osobito je prikladna baza koja se sastoji od takozvanih kubičnih B-splineova (osnovnih ili temeljnih klinova). Korištenje D-splineova može značajno smanjiti zahtjeve za memorijom računala. L-splineovi. B -spline nultog stupnja, izgrađen na brojevnom pravcu duž rešetke w, funkcija je vilice B -splin stupnja k ^ I, izgrađen na brojevnom pravcu duž mreže u, određen je rekurzivnom formulom koja je druga u \7\x) stupnjevi prikazani su na sl. 11 odnosno 12. B-splin proizvoljnog stupnja k može biti različit od nule samo na određenom segmentu (definiranom s k + 2 čvora). Pogodnije je numerirati kubične B -splines tako da je spline B,-3* (n) bio različit od nule na segmentu ir,-+2]. Dajmo formulu za kubični spline trećeg stupnja za slučaj uniformne mreže (s korak A). ​​Imamo u drugim slučajevima. Tipičan dijagram kubičnog B-splajna prikazan je na slici 13. Funkcija a) je dva puta kontinuirano diferencijabilna na segmentu, odnosno pripada klasi C2 [a, "), c) je različit od nule samo na četiri uzastopna segmenta proširene mreže w * mo Potrebno je konstruirati familiju od m + 3 kubičnih B-splajnova: Ova familija čini bazu u prostoru kubičnih splajnova na segmentu (a, b]. Dakle, proizvoljni kubični spline S(z) konstruiran na segmentu |s, 6] mreže o; od +1 čvorova, može se prikazati na ovom segmentu kao linearna kombinacija.Koeficijenti ft ove ekspanzije jednoznačno su određeni uvjetima problema. ... U slučaju kada su vrijednosti funkcije u čvorovima mreže i vrijednosti prve derivacije funkcije na krajevima mreže "(problem interpolacije s granicom uvjeti prve vrste), ti se koeficijenti izračunavaju iz sustava sljedećeg oblika vrijednosti b-i i &m+i, dobivamo linearni sustav s nepoznanicama 5q, ... , bm i trodijajunalnom matricom. Uvjet osigurava dijagonalnu dominaciju, a samim time i mogućnost primjene metode sweep za njegovo rješavanje. 3MMCHMYU 1. Linearni sustavi sličnog oblika nastaju i pri razmatranju drugih problema interpolacije. Zmmchm* 2. U usporedbi s algoritmima opisanim u odjeljku 1.1, uporaba R-splinea u * problemima interpolacije omogućuje * smanjenje količine pohranjenih informacija, odnosno značajno smanjenje zahtjeva za memorijom računala, iako dovodi do povećanje broja operacija. Konstrukcija spline krivulja pomoću spline funkcija Gore su razmatrani nizovi čije su točke bile numerirane tako da su njihove apscise tvorile strogo rastući niz. Na primjer, slučaj prikazan na Sl. 14, kada različite točke niza imaju istu apscisu, nije bilo dopušteno. Ta je okolnost odredila i izbor klase aproksimirajućih krivulja (promet funkcija) i metodu njihove konstrukcije. Međutim, gore predložena metoda omogućuje prilično uspješnu konstrukciju interpolacijske krivulje u općenitijem slučaju, kada numeriranje točaka niza i njihov položaj na ravnini, u pravilu, nisu povezani (slika 15). Štoviše, kada postavljamo problem konstruiranja interpolacijske krivulje, zadani niz možemo smatrati neplanarnim, odnosno jasno je da je za rješavanje ovog općeg problema potrebno značajno proširiti klasu dopustivih krivulja, uključujući i zatvorene krivulje, i krivulje sa samosjecištima, i prostorne krivulje. Pogodno je opisati takve krivulje pomoću parametarskih jednadžbi. Zahtijevamo. dodatno, tako da funkcije imaju dovoljnu glatkoću, na primjer, pripadaju klasi C1 [a, /0] ili klasi Da biste pronašli parametarske jednadžbe krivulje koja uzastopno prolazi kroz sve točke niza, postupite na sljedeći način. 1. korak. na proizvoljnom intervalu)