Dom

Interpolacija funkcija pomoću splinea. Kubični interpolacijski spline. Odabir empirijskih formula

Ministarstvo obrazovanja i znanosti Ruske Federacije

Savezna državna proračunska obrazovna ustanova visokog stručnog obrazovanja

"Donsko državno sveučilište"

Odjel "Računalni softver i automatizirani sustavi" "POVT i AS"

Specijalnost: Administracija softvera i informacijskih sustava

NASTAVNI RAD

u disciplini "Metodika proračuna"

na temu: “Splijn interpolacija”

Šef rada:

Medvedeva Tatjana Aleksandrovna

Rostov na Donu

VJEŽBA

za nastavni rad iz discipline "Metode proračuna"

Student: Moiseenko Alexander Group VBMO21

Tema: “Spline interpolacija”

Rok za predaju obrane rada je “__” _______ 201_.

Početni podaci za rad na kolegiju: bilješke s predavanja o računalnim metodama, ru.wikipedia.org, knjiga. Radionica o višoj matematici Sobol B.V.

Odjeljci glavnog dijela: 1 PREGLED, 2 INTERPOLACIJSKA FORMULA, 3 KUBIČNI INTERPOLACIJSKI ALGORITAM, 4 DIZAJN SOFTVERA, 5 REZULTATI SOFTVERA.

Voditeljica rada: /Medvedeva T.A./

SAŽETAK

Izvješće sadrži: 19 stranica, 3 grafikona, 3 izvora, 1 blok dijagram.

Ključne riječi: INTERPOLACIJA, SPLINE, Mathcad sustav, KUBIČNA INTERPOLACIJA SA SPLINE-OM.

Metoda kubične spline interpolacije detaljno je obrađena. Prikazan je odgovarajući programski modul. Ilustriran je blok dijagram softverskog modula. Razmatra se nekoliko primjera.

UVOD

1. TEORIJSKI OSVRT

2. INTERPOLACIJA

2.1 Interpolacija pomoću kvadratnog splajna

2.2 Interpolacija pomoću kubičnog splajna

2.3 Izjava problema

3. ALGORITAM INTERPOLACIJE KORIŠTENJEM KUBIČNOG SPLINEA

4. DIZAJN SOFTVERA

5. REZULTAT SOFTVERA

5.1 Opis primjera

5.2 Rezultat ispitivanja

5.3 Testni slučaj 1

5.4 Testni slučaj 2

5.5 Testni slučaj 3

ZAKLJUČAK

BIBLIOGRAFIJA

UVOD

Aproksimacija funkcije sastoji se u približnoj zamjeni dane funkcije f(x) nekom funkcijom j( x) tako da je odstupanje funkcije j( x) od f(x) na određenom 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 je metoda u računalnoj matematici za pronalaženje srednjih vrijednosti veličine iz postojećeg diskretnog skupa poznatih vrijednosti. Pri rješavanju problema sa znanstvenim i inženjerskim izračunima često je potrebno raditi sa skupovima vrijednosti dobivenih eksperimentalno ili nasumičnim uzorkovanjem. U pravilu je na temelju tih skupova potrebno konstruirati funkciju u koju bi ostale dobivene vrijednosti mogle pasti s visokom točnošću. Ovaj problem se naziva aproksimacija funkcije. Interpolacija je vrsta aproksimacije funkcije 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 poklapa s određenim 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ćuje 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. Osnovne ideje teorije kubičnih klinova nastale su kao rezultat pokušaja matematičkog opisa fleksibilnih letvica izrađenih od elastičnog materijala (mehanički klinovi), koje su dugo koristili crtači u slučajevima kada je bilo potrebno nacrtati prilično glatku krivulju. kroz zadane točke. Poznato je da traka od elastičnog materijala, fiksirana na određenim točkama iu 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 pomoću kvadratnog splajna

Dakle, na svakom segmentu djelomične interpolacije ćemo konstruirati 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 je broj koeficijenata nepoznat. Jednadžba koja nedostaje može se dobiti iz dodatnih uvjeta nametnutih ponašanju splajna. Na primjer, možete zahtijevati da vrijednost prve derivacije splinea s 1 u točki x 0 bude nula, tj.

Zamjenom ovih izraza dobivamo sljedeće jednadžbe

gdje se uvodi oznaka

Izrazimo koeficijente iz druge jednadžbe c 1 , prethodno zamijenivši vrijednosti koeficijenata u njega a 1 iz prve jednadžbe:

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

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

Nakon izračuna koeficijenata, za izračun samog splinea dovoljno je odrediti broj intervala u kojem se nalazi točka interpolacije i upotrijebiti 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 , koji odgovara ovoj funkciji f(x) i ovi čvorovi x ja, nazvana 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- koeficijenti koji se utvrđuju za sve n elementarni segmenti. Da bi sustav algebarskih jednadžbi imao rješenje, broj jednadžbi mora biti točno jednak broju nepoznanica. Stoga bismo trebali dobiti 4 n jednadžbe

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

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

Ovi se uvjeti mogu napisati kao:

S ja(x ja - 1)= a ja= g 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 interpolacijskim čvorovima, 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 na svakom unutarnjem čvoru x = x ja vrijednosti ovih derivata, 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.

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

Kada su krajevi labavo pričvršćeni, zakrivljenost linije u tim točkama može se postaviti na nulu. Iz uvjeta nulte zakrivljenosti na krajevima slijedi da su druge derivacije u tim točkama jednake nuli:

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 dovesti u 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)

Isključujemo 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 vrijednosti neke funkcije f(x) na ovim točkama

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

Koristeći kubične splineove, konstruirajte interpolacijsku funkciju f(x).

3. ALGORITAM INTERPOLACIJE 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

U tijeku ovog kolegija razvijen je softverski modul koji crta odgovarajuću krivulju kroz postojeće točke. Provedeni su testni slučajevi kako bi se provjerila učinkovitost rada.

5.2 Rezultati ispitivanja

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

5.3 Test slučaj 1

Slika 1.1 - rezultat programa

Test 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 značajnu ulogu ima interpolacija funkcija, tj. Pomoću zadane funkcije konstruirati drugu (obično jednostavniju) funkciju čije se vrijednosti poklapaju 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 rekonstrukcije kontinuirane funkcije iz njezinih tabličnih vrijednosti, primjerice dobivenih tijekom nekog eksperimenta. Za procjenu mnogih funkcija pokazalo se da je učinkovito 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 zadatak dopušta, ovaj se problem može riješiti odabirom mreže s Chebyshevljevim čvorovima. Ako ne možemo slobodno birati čvorove interpolacije ili nam jednostavno treba algoritam koji nije prezahtjevan u izboru čvorova, tada racionalna interpolacija može biti prikladna alternativa polinomskoj interpolaciji.

Prednosti spline interpolacije uključuju veliku brzinu obrade računskog algoritma, budući da je spline djelomično polinomna funkcija i tijekom interpolacije se istovremeno obrađuju podaci za mali broj mjernih točaka koje pripadaju fragmentu koji se trenutno razmatra. Interpolirana površina opisuje prostornu varijabilnost različitih mjerila i istovremeno je glatka. Posljednja 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 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čnog splajna.

laboratorijski rad, dodan 06.02.2004

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

test, dodan 01.05.2011

Konstruirajte Newtonov interpolacijski polinom. Nacrtajte graf i na njemu označite interpolacijske čvorove. Konstruirajte Lagrangeov interpolacijski polinom. Izvršite interpolaciju pomoću splajnova 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.

kolegij, dodan 04/10/2011

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

kolegij, dodan 14.03.2014

Upoznavanje s poviješću nastanka 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.

kolegij, dodan 09.08.2015

Problemi globalne i lokalne interpolacije prema Lagrangeu i Newtonu; colive ponašanje interpolacijskog polinoma; Runge funkcije. Spline je skupina povezanih kubičnih polinoma s nekontinuiranim prvim i drugim sličnim polinomima, koristeći interpolaciju spline.

prezentacija, dodano 06.02.2014

Metode numeričkog diferenciranja. Izračunavanje derivacije pomoću jednostavnih formula. Numeričko diferenciranje temeljeno na interpolaciji algebarskim polinomima. Aproksimacija Lagrangeovim polinomom. Diferencijacija pomoću interpolacije.

kolegij, dodan 15.02.2016

Opis metoda rješavanja sustava linearnih algebarskih jednadžbi: inverzna matrica, Jacobi, Gauss-Seidel. Postavka 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 kvadratnom interpolacijom i metodom zlatnog reza, njihove usporedne karakteristike, utvrđivanje glavnih prednosti i nedostataka. Broj ponavljanja i procjena točnosti.

Neka je dana tablica vrijednosti funkcije y i u čvorovima x 0 < х 1 < ... < х п .Označiti h i = x i – x i -1 , ja= 1, 2, ... , P.

Spline– glatka krivulja koja prolazi kroz zadane točke ( x i, y i), ja = 0, 1, ... , P. Spline interpolacija je to na svakom segmentu [ x i -1 , x i] koristi se polinom određenog stupnja. Najčešće se koristi polinom trećeg stupnja, rjeđe drugog ili četvrtog stupnja. U ovom slučaju za određivanje koeficijenata polinoma koriste se uvjeti neprekidnosti derivacija u interpolacijskim čvorovima.

Interpolacija kubnim splajnovima predstavlja lokalnu interpolaciju, kada je na svakom segmentu [ x i -1 , x i], ja = 1, 2, ... , P koristi se kubična krivulja koja zadovoljava određene uvjete glatkoće, naime, kontinuitet same funkcije i njezine prve i druge derivacije u čvornim točkama. Upotreba kubne funkcije je posljedica sljedećih razmatranja. Ako pretpostavimo da interpolacijska krivulja odgovara elastičnom ravnalu učvršćenom u točkama ( x i, y i), tada je iz kolegija Čvrstoća materijala poznato da je ova krivulja definirana kao rješenje diferencijalne jednadžbe f(IV) ( x) = 0 na intervalu [ x i -1 , x i](radi jednostavnosti prikaza, ne razmatramo pitanja vezana uz fizičke dimenzije). Opće rješenje takve jednadžbe je polinom 3. stupnja s proizvoljnim koeficijentima, koji se prikladno zapisuje u obliku
S i(x) = i ja + b i(x - x i -1) +sa i(x - x i -1) 2 + d i(x - x i -1) 3 ,
x i-1 £ x £ x i, ja = 1, 2, ... , P.(4.32)

Funkcijski koeficijenti S i(x) određuju se iz uvjeta neprekidnosti funkcije i njezine prve i druge derivacije u unutarnjim čvorovima x i,ja= 1, 2,..., P - 1.

Iz formula (4.32) na x = x i-1 dobivamo

S i(x i- 1) = y i -1 = a i, ja = 1, 2,..., P,(4.33)

i kada x = x i

S i(x i) = i ja + b i h i +sa i h i 2 + d i h i 3 ,(4.34)

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

Uvjeti kontinuiteta za interpolacijsku funkciju zapisani su kao S i(x i) = S i -1 (x i), ja= 1, 2, ... , n- 1 i iz uvjeta (4.33) i (4.34) slijedi da su oni zadovoljivi.

Nađimo derivacije funkcije S i(x):

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

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

Na x = x i-1, imamo S" i(x i -1) = b i, S" (x i -1) = 2sa i, i kada x = x i dobivamo

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

Uvjeti neprekidnosti derivacija dovode do jednadžbi

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

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

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

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

Ukupno imamo 4 n– 2 jednadžbe za određivanje 4 n nepoznato. Da bi se dobile još dvije jednadžbe, koriste se dodatni rubni uvjeti, na primjer, zahtjev da interpolacijska krivulja ima nultu zakrivljenost na krajnjim točkama, tj. da druga derivacija bude jednaka nuli na krajevima segmenta [ A, b]A = x 0 , b= x n:

S" 1 (x 0) = 2c 1 = 0 Þ S 1 = 0,

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

Sustav jednadžbi (4.33)–(4.37) može se pojednostaviti i dobiti rekurentne formule za izračun koeficijenata splinea.

Iz uvjeta (4.33) imamo eksplicitne formule za izračunavanje koeficijenata a ja:

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

Izrazimo se d i kroz c i koristeći (4.36), (4.37):

; ja = 1, 2,...,n; .

Stavimo s n+1 = 0, zatim za d i dobivamo jednu formulu:

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

Zamijenimo izraze za i ja I d i u jednakost (4.34):

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

i izraziti b i, kroz sa i:

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

Isključimo koeficijente iz jednadžbi (4.35) b i I d i koristeći (4.39) i (4.40):

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

Odavde dobivamo sustav jednadžbi za određivanje sa i:

Sustav jednadžbi (4.41) može se prepisati kao

Ovdje se uvodi notacija

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

Riješimo sustav jednadžbi (4.42) metodom prelaska. Iz prve jednadžbe izražavamo S 2 kroz S 3:

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

Zamijenimo (4.43) u drugu jednadžbu (4.42):

h 2 (a 2 c 3 + b 2) + 2( h 2 + h 3)c 3 +h 3 c 4 = g 2 ,

i izraziti S 3 kroz S 4:

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

Pod pretpostavkom da sa i-1 = a ja -1 c i+b ja-1 od ja th jednadžbe (4.42) dobivamo

c i= a ja sa ja+1+b ja

, ja = 3,..., n– 1, a n= 0, (4.45) c n +1 = 0,

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

c 1 = 0.

3. Izračun koeficijenata i ja, b i,d i:

a ja = y i -1 ,

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

4. Izračunajte vrijednost funkcije pomoću splinea. Da biste to učinili, pronađite sljedeću vrijednost ja, da je zadana vrijednost varijable x pripada segmentu [ x i -1 , x i] i izračunajte

S i(x) = i ja + b i(x - x i -1) +sa i(x - x i -1) 2 + d i(x - x i -1) 3 . (4.50)

2.2 Interpolacija pomoću kubičnog splajna

Kubični interpolacijski spline koji odgovara danoj funkciji f(x) i danim čvorovima x i je funkcija S(x) koja zadovoljava sljedeće uvjete:

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

2. Funkcija S(x), kao i njezina prva i druga derivacija, kontinuirane su na intervalu,

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

Na svakom od odsječaka , i = 1, 2, ..., N, tražit ćemo funkciju S(x) = S i (x) u obliku polinoma trećeg stupnja:

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

x i - 1 J x J x i ,

gdje su a i, b i, c i, d i koeficijenti koje treba odrediti na svih n elementarnih segmenata. Da bi sustav algebarskih jednadžbi imao rješenje, broj jednadžbi mora biti točno jednak broju nepoznanica. Stoga bismo trebali dobiti 4n jednadžbi.

Prvih 2n jednadžbi dobivamo iz uvjeta da graf funkcije S(x) mora prolaziti kroz zadane točke, tj.

S i (x i - 1) = y i - 1, S i (x i) = y i.

Ovi se uvjeti mogu napisati kao:

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

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

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

Sljedećih 2n - 2 jednadžbi proizlaze iz uvjeta kontinuiteta prve i druge derivacije u čvorovima interpolacije, tj. uvjeta glatkoće krivulje u svim točkama.

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

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

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

Izjednačavajući na svakom unutarnjem čvoru x = x i vrijednosti ovih derivata, izračunatih u intervalima lijevo i desno od čvora, dobivamo (uzimajući u obzir h i = x i - x i - 1):

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

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

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

ako je x = x i

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

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

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

c i = 0 i 2 c n + 6 d n h n = 0.

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

Ovaj sustav se može dovesti u prikladniji oblik. Iz uvjeta možete odmah pronaći sve koeficijente a i.

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

Zamjenom dobivamo:

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

b n = - (h n c n)

Isključujemo koeficijente b i i d i iz jednadžbe. Konačno, samo za koeficijente s i dobivamo sljedeći sustav jednadžbi:

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

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

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

Iz pronađenih koeficijenata s i lako je izračunati d i,b i.

Izračunavanje integrala Monte Carlo metodom

Ovaj softverski proizvod implementira mogućnost postavljanja dodatnih ograničenja na područje integracije pomoću dvije dvodimenzionalne spline površine (za funkciju integranda dimenzije 3)...

Interpolacija funkcije

Neka je dana tablica vrijednosti funkcije f(xi) = yi (), u kojoj su raspoređene uzlaznim redoslijedom vrijednosti argumenata: x0< x1 < … < xn. Чтобы построить кубический сплайн, требуется определить коэффициенты ai0, ai1, ai2, ai3...

Spline interpolacija

Upoznajmo se s algoritmom programa. 1. Izračunajte vrijednosti i 2. Na temelju ovih vrijednosti izračunajte radne koeficijente i o. 3. Na temelju dobivenih podataka izračunavamo koeficijente 4...

Matematičko modeliranje tehničkih objekata

Ugrađene MathCAD funkcije omogućuju interpolaciju za crtanje krivulja različitih stupnjeva složenosti kroz eksperimentalne točke. Linearna interpolacija...

Metode aproksimacije funkcija

Na svakom segmentu interpolacijski polinom jednak je konstanti, odnosno lijevoj ili desnoj vrijednosti funkcije. Za lijevu komadno linearnu interpolaciju F(x)= fi-1, ako je xi-1 ?x

Metode aproksimacije funkcija

Na svakom intervalu funkcija je linearna Fi(x)=kix+li. Vrijednosti koeficijenata se nalaze ispunjavanjem uvjeta interpolacije na krajevima segmenta: Fi(xi-1)=fi-1, Fi(xi-1)=fi. Dobivamo sustav jednadžbi: kixi-1+ li= fi-1, kixi+ li= fi, odakle nalazimo ki=li= fi- kixi...

Metode rješavanja sustava linearnih jednadžbi. Interpolacija

Postavka problema interpolacije. Na intervalu je zadan sustav točaka (interpolacijski čvorovi) xi, i=0,1,…,N; a? x i ? b, te vrijednosti nepoznate funkcije u tim čvorovima fn i=0,1,2,…,N. Mogu se postaviti sljedeći zadaci: 1) Konstruirati funkciju F (x)...

Konstrukcija matematičkog modela koji opisuje proces rješavanja diferencijalne jednadžbe

3.1 Konstrukcija Lagrangeovog interpolacijskog polinoma i kondenzacija vrijednosti Očigledna metoda za rješavanje ovog problema je izračunavanje vrijednosti ѓ(x) pomoću analitičkih vrijednosti funkcije ѓ. U tu svrhu - prema prvim informacijama...

Ako su to potencije (1, x, x2, ..., xn), tada govorimo o algebarskoj interpolaciji, a funkcija se naziva interpolacijski polinom i označava se kao: (4) Ako () (5), tada možemo konstruirajte interpolacijski polinom stupnja n i, štoviše, samo jedan...

Praktična primjena interpolacije glatkih funkcija

Razmotrimo primjer interpolacije za elemente skupa. Radi jednostavnosti i sažetosti, uzmimo =[-1;1], . Neka se točke razlikuju jedna od druge. Postavimo sljedeći problem: (12) konstruirajte polinom koji zadovoljava ove uvjete...

Primjena numeričkih metoda za rješavanje matematičkih problema

Numeričke metode

Dakle, kao što je gore spomenuto, zadatak interpolacije je pronaći polinom čiji graf prolazi kroz zadane točke. Neka je funkcija y=f(x) određena pomoću tablice (tablica 1)...

Numeričke metode rješavanja matematičkih problema

Osoba može prepoznati svoje sposobnosti samo pokušavajući ih primijeniti. (Seneca)

Interpolacija splajna: primjer konstruiranja splajna u programu STATISTICA

Struktura podataka

Neka su nam zadane vrijednosti nepoznate funkcije na određenom skupu točaka. (Zapravo, varijabla g su vrijednosti funkcije y=sinx u točkama iz segmenta.)

Konstruirajmo krivulju interpolacije iz ovih podataka pomoću programa STATISTICA.

Korak 1 Izaberimo 2M Grafikoni - Scatterplot na jelovniku Grafička umjetnost.

Korak 2 Otvorimo karticu Dodatno, odaberimo kao varijable x I y, kao primjerak - Splines.

Pritisnite tipku OK i na ekranu će se pojaviti konstruirani dijagram raspršenosti na kojem plave oznake označavaju početne vrijednosti između kojih se iscrtava interpolacijska krivulja.

Promijenimo broj bodova.

Sada imamo skup od dvadeset točaka kao početne podatke.

Ponavljajući gore opisane korake, dobivamo:

Pokušajmo također konstruirati spline na skupu od pedeset točaka.

Fragment tablice izvornih podataka:

Proizlaziti:

I konačno, pokušajmo konstruirati spline pomoću točaka nasumično bačenih na segment.

Izvor podataka (fragment tablice):

Grafikon konstruiran na sličan način:

Sada usporedimo dobivene rezultate s izvornom funkcijom y=sinx,čiji grafikon izgleda ovako:

Kao što možete vidjeti, splineovi vrlo točno interpoliraju izvornu funkciju.

Može se primijetiti da ako izvorna funkcija snažno oscilira, tada bi broj točaka trebao biti velik - po redu broja perioda, ali u praksi su takvi slučajevi rijetki.

Primjer iz stvarnog života: Kliničko ispitivanje lijekova

Vratimo se na već na samom početku spomenuti primjer iz stvarnog života korištenja splinova u kliničkim ispitivanjima lijekova.

Vrlo važna karakteristika lijeka je tzv. AUC (Površina ispod krivulje koncentracije lijeka u plazmi) - površina ispod krivulje koncentracija-vrijeme.

Ova krivulja odražava stvarni učinak lijeka na ljudsko tijelo nakon primjene određene doze. Vrijednost AUC se mjeri u mg h/l. Površina ispod krivulje ovisi o brzini eliminacije lijeka iz tijela i primijenjenoj dozi. Ukupna količina lijeka eliminiranog iz tijela može se izračunati zbrajanjem ili integriranjem količine lijeka eliminiranog u bilo kojem trenutku.

Vrijednost AUC izravno je proporcionalna dozi primijenjenog lijeka za lijekove s linearnom farmakokinetikom i obrnuto proporcionalna tzv. pokazatelj klirensa lijeka. Što je veći klirens, lijek ostaje kraće u krvožilnom sustavu i brže se smanjuje njegova koncentracija u plazmi. U tom je slučaju učinak lijeka na tijelo i područje ispod krivulje koncentracija-vrijeme manji.

Tijekom kliničkih studija, vremenski tijek koncentracija lijeka u krvi može se odrediti mjerenjem koncentracija u različitim vremenskim točkama. Zatim se crta grafikon koncentracije i procjenjuje se AUC.

Za procjenu AUC-a često se koristi trapezna metoda: površina ispod grafikona koncentracija-vrijeme podijeljena je na trapeze, a AUC se izračunava zbrajanjem površina tih trapeza (što je u biti ekvivalentno interpolaciji s linearnim funkcijama).

AUC= AUC0-2+AUC2-4+AUC4-6+AUC6-8+AUC8-10+AUC10-12+AUClast-beskonačno

U ovom ćemo članku dati primjer točnije procjene AUC-a dobivene kada se funkcija koncentracije interpolira kubičnim splineovima.

Neka postoje podaci o koncentraciji dobiveni tijekom studije:

Izgradimo dijagram raspršenosti pomoću njih i interpolirajmo vrijednosti koristeći spline u programu STATISTICA.

Kao što se može vidjeti iz grafikona, maksimalna vrijednost koncentracije C pmax = 29,78 mg/l odgovara vremenu t max = 8 sati. Upotrijebimo uređivač podataka grafikona i dobijmo odgovarajuće vrijednosti:

Izračunajmo vrijednost AUC koristeći gore opisanu trapezoidnu metodu. Dobivamo AUC = 716,11 mg h/l.

Bibliografija:

V.P. Borovikov. STATISTICA . Umjetnost analize podataka na računalu: za profesionalce (2. izdanje), St. Petersburg: Peter, 2003. - 688 str.: ilustr.

E.A.Volkov. Numeričke metode. Moskva, "Nauka", Glavna redakcija fizičke i matematičke literature , 1987. (enciklopedijska natuknica).

Krivulje i površine koje se susreću u praktičnim problemima često imaju prilično složen oblik, što ne dopušta univerzalni analitički zadatak u cjelini korištenjem 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 budu slične prirode, na primjer, trebaju biti polinomi istog stupnja. A kako bi rezultirajuća krivulja ili površina bila dovoljno glatka, morate biti posebno pažljivi gdje se odgovarajući fragmenti spajaju. Stupanj polinoma bira se iz jednostavnih geometrijskih razmatranja i u pravilu je mali. Za glatku promjenu tangente duž cijele složene krivulje dovoljno je spojene 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 konstrukciji fragmenata kompozitnih ploha. I ovdje se bikubični splineovi pojavljuju sasvim prirodno, opisani pomoću polinoma trećeg stupnja u svakoj od dvije varijable. Rad s takvim splajnovima zahtijeva znatno veću količinu izračuna. Ali pravilno organiziran proces omogućit će da se u najvećoj mjeri uzmu u obzir stalno rastuće mogućnosti računalne tehnologije. Spline funkcije Neka na segmentu, tj. Napomena. Na to ukazuje indeks (t) brojeva a^. da je skup koeficijenata koji određuje funkciju 5(x) na svakom parcijalnom segmentu D različit. 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. To znači da je za potpuno određivanje spline-a potrebno pronaći (p + 1) zatim brojeve. Uvjet) označava neprekidnost funkcije 5(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 potpuno definiranje splinea nema dovoljno uvjeta (jednadžbi), izbor dodatnih uvjeta određen je prirodom problema koji se razmatra, a ponekad jednostavno željom korisnika. TEORIJA SPLINEA primjeri rješenja Problemi interpolacije i izglađivanja najčešće se razmatraju kada je potrebno konstruirati jedan ili drugi spline iz zadanog niza točaka na ravnini. Problemi interpolacije zahtijevaju da spline graf prolazi kroz točke, što nameće m + 1 dodatnih uvjete (jednadžbe) na njegove koeficijente. Preostali p - 1 uvjeti (jednadžbe) za jedinstvenu konstrukciju splinea najčešće su navedeni u obliku vrijednosti nižih derivacija splinea na krajevima segmenta koji se razmatra [a, 6] - granica ( rub) uvjeti. Mogućnost odabira različitih rubnih uvjeta omogućuje vam da konstruirate splineove s različitim svojstvima. U problemima izglađivanja, spline se konstruira tako da njegov graf prolazi blizu točaka (i""Y"), * = 0, 1,..., t, a ne kroz njih. Mjera te blizine može se definirati na različite načine, što rezultira značajnom raznolikošću izglađujućih splajnova. Opisane mogućnosti izbora pri konstrukciji splajn funkcija ne iscrpljuju svu njihovu raznolikost. A ako su se u početku razmatrale samo djelomično polinomne spline funkcije, onda kako se širio opseg njihove primjene, spline su se počeli pojavljivati, "zalijepljeni" od drugih elementarnih funkcija. Interpolacijski kubični splinovi Izjava problema interpolacije Neka je mreža w dana na segmentu [a, 6) Razmotrimo skup brojeva Problem. Konstruirajte glatku funkciju na segmentu (a, 6] koja uzima određene vrijednosti u čvorovima mreže o", to jest Napomena: Formulirani problem interpolacije sastoji se od vraćanja glatke funkcije navedene u tablici (slika 2). Jasno je da takav problem ima mnogo različitih rješenja. Nametanjem dodatnih uvjeta na konstruiranu funkciju moguće je postići potrebnu jedinstvenost.U primjenama često postoji potreba za aproksimacijom analitički definirane funkcije pomoću funkcije s propisanom dovoljno dobrom Na primjer, u slučajevima kada je izračun vrijednosti zadane funkcije /(x) na segmentu točaka [a, 6] povezan sa značajnim poteškoćama i/ili zadana funkcija /(x) nema potrebna glatkoća, zgodno je koristiti drugu funkciju koja bi prilično dobro aproksimirala danu funkciju i bila lišena njezinih navedenih nedostataka. Problem interpolacije funkcije. Konstruirajte na segmentu [a, 6] glatku funkciju a(x), koja koincidira na čvorovi mreže w sa zadanom funkcijom f(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 tom segmentu s četiri koeficijenta . Ukupan broj segmenata je m. To znači da je za potpuno definiranje spline-a potrebno pronaći 4m brojeva. Uvjet znači neprekidnost funkcije S(x) i njenih 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 (rubni) uvjeti Dva nedostajuća uvjeta navedena su u obliku ograničenja vrijednosti splinea i/ili njegovih izvodnica na krajevima intervala [a, 6]. Pri konstruiranju interpolirajućeg kubičnog splajna najčešće se koriste sljedeće četiri vrste rubnih uvjeta. A. Rubni uvjeti 1. vrste. - na krajevima intervala [a, b] navedene su vrijednosti prve derivacije željene funkcije. B. Rubni uvjeti 2. vrste. - na krajevima intervala (a, 6) navedene su 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), općenito govoreći, je diskontinuirana. Međutim, broj diskontinuiteta treće derivacije može se smanjiti korištenjem 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. Ovdje su TEORIJA SPLINE primjeri rješenja i brojevi rješenja sustava linearnih algebarskih jednadžbi, čiji oblik ovisi o vrsti rubnih uvjeta. Za rubne uvjete tipa 1 i 2 ovaj sustav ima sljedeći oblik gdje 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 zapisuje se na sljedeći način: Broj nepoznanica u posljednjem sustavu jednak je mn, jer je iz uvjeta periodičnosti slijedi po = nm. Za rubne uvjete 4. vrste sustav za određivanje brojeva ima oblik gdje se Na temelju pronađenog rješenja sustava brojevi po i n mogu odrediti pomoću formula.Važna napomena. Matrice sva tri linearna algebarska sustava su dijagonalno dominantne matrice. Matrice nisu singularne, pa stoga svaki od ovih sustava ima jedinstveno rješenje. Teorema. Interpolacijski kubični spline koji zadovoljava uvjete (2) i rubni uvjet jednog od četiri gore navedena tipa postoji i jedinstven je. Dakle, konstruirati interpolacijski 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 izračune prikladniji je sljedeći algoritam za pronalaženje vrijednosti 5(g). Neka je x 6 [x", Prvo se vrijednosti A i B izračunaju pomoću formula, a zatim se pronađe vrijednost 5(x): Korištenje ovog algoritma značajno smanjuje računske troškove određivanja vrijednosti. Savjeti za korisnik Izbor graničnih (rubnih) uvjeta i interpolacijskih čvorova omogućuje vam da u određenoj mjeri kontrolirate svojstva interpolacijskih splajnova. A. Izbor rubnih (rubnih) uvjeta. Izbor rubnih uvjeta jedan je od središnjih problema u interpolaciji funkcija. To postaje posebno važno 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 utjecaj brzo slabi kako se čovjek udaljava od njih. Odabir rubnih uvjeta često je određen dostupnošću dodatnih informacija o ponašanju aproksimirane funkcije f(x). Ako su vrijednosti prve derivacije f"(x) poznate na krajevima segmenta (a, 6), tada je prirodno koristiti rubne uvjete 1. tipa. Ako su vrijednosti druge derivacije f"(x) su poznati na krajevima segmenta [a, 6], onda su to rubni uvjeti prirodne uporabe tipa 2. Ako postoji izbor između rubnih uvjeta tipa 1 i 2, prednost treba dati uvjetima tipa 1. Ako je f(x) periodična funkcija, tada bismo se trebali zaustaviti na rubnim uvjetima tipa 3. Ako nema dodatnih informacija o ponašanju aproksimirane funkcije, č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 izvodnica, već s njihovim razlika aproksimacija.Točnost ovog pristupa je niska.Praktično iskustvo u proračunima pokazuje da su u razmatranoj situaciji najprikladniji izbor rubni uvjeti 4. tipa. B. Izbor interpolacijskih čvorova. Ako treća derivacija f""(x) funkcije ima diskontinuitet u nekim točkama segmenta [a, b], tada za poboljšanje kvalitete aproksimacije te točke treba uključiti u broj interpolacijskih čvorova. Ako je druga derivacija /"(x) diskontinuirana, tada je potrebno poduzeti posebne mjere da bi se izbjeglo osciliranje splinea u blizini točaka diskontinuiteta. Tipično se interpolacijski čvorovi biraju tako 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 se prva derivacija f" (x) je diskontinuiran. Kao jedan od najjednostavnijih, možemo predložiti ovo: podijelite segment aproksimacije na intervale gdje je derivacija kontinuirana, i konstruirajte spline na svakom od tih intervala. Odabir funkcije interpolacije (za i protiv) Pristup 1. Lagrangeov interpolacijski polinom Za dani niz TEORIJA SPLINE primjera rješenja (slika 3), Lagrangeov interpolacijski polinom određen je formulom. Preporučljivo je razmotriti svojstva Lagrangeovog interpolacijskog polinoma s dvije suprotne pozicije, raspravljajući o glavnim prednostima odvojeno od nedostatke. Glavne prednosti 1. pristupa: 1) graf Lagrangeovog interpolacijskog polinoma prolazi kroz svaku točku niza, 2) konstruirana funkcija se lako opisuje (broj koeficijenata Lagrangeovog interpolacijskog polinoma na mreži koji treba odrediti je jednako m + 1), 3) konstruirana funkcija ima kontinuirane derivacije bilo kojeg reda, 4) interpolacijski polinom jednoznačno je određen 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 također 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 Lagrangeova interpolacijskog polinoma s neograničenim usklađivanjem mreže općenito zahtijeva posebnu pozornost. Komentari A. O aproksimaciji 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 intervalu [a, 6]. Tada za bilo koji e > 0 postoji polinom R„(x) takav da će za bilo koji x iz intervala [a, 6] nejednakost biti zadovoljena (slika 4). Primijetite da polinomi čak i istog stupnja koji aproksimiraju funkciju f(x) sa specificiranom točnošću ima beskonačno mnogo. Konstruirajmo mrežu w na segmentu [a, 6]. 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 danu mrežu, polinom Pn(x) nije interpolacija. Kada se kontinuirana funkcija aproksimira Jla-graczovim interpolacijskim polinomom, njezin graf ne samo da ne mora biti blizu grafa funkcije f(x) u svakoj točki segmenta [a, b), nego može odstupati od ovu funkciju onoliko koliko želite. Navedimo dva primjera. Primjer 1 (Rung, 1901). S neograničenim povećanjem broja čvorova za funkciju na intervalu [-1, 1] granična jednakost je zadovoljena (slika 6) Primjer 2 (Beristein, 1912). Niz Lagrangeovih interpolacijskih polinoma konstruiranih na uniformnim mrežama za kontinuiranu funkciju /(x) = |x| na segmentu s rastućim brojem čvorova m ne teži funkciji /(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 primjetno promijeniti prema prvome. Konstruirajmo komadno linearnu funkciju uzastopnim povezivanjem točaka (xit y) s ravnim segmentima (slika 8). Glavne prednosti 2. pristupa: 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 zadanim nizom jedinstveno, 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čunavanje četiri broja (koeficijenti dviju ravnih veza koje izlaze iz nove točke), 6) dodavanje dodavanje dodatne točke nizu zahtijeva izračunavanje četiri koeficijenta. Djelomično linearna funkcija također se prilično dobro ponaša pri pročišćavanju mreže. Glavni nedostatak 2. pristupa: aproksimirajuća podjelno linearna 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 istovremeno smanjenje broja nedostataka. To se može učiniti konstruiranjem glatke interpolacijske 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) jednaka je 3) konstruirana funkcija je jedinstveno definirana zadanim nizom, 4) polinom stupnja ne ovisi o broju čvorova mreže i stoga se ne mijenja kako raste, 5) konstruirana funkcija ima kontinuiranu derivacije do reda p - 1 uključivo, 6) konstruirana funkcija ima dobra svojstva aproksimacije. Kratke informacije. Predloženi naziv - spline - nije slučajan - glatke komadno polinomske funkcije koje smo uveli i crtanje splineova usko su povezani. Razmotrimo 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 gdje je S(x) savijanje, M(x) moment savijanja koji linearno varira od oslonca do oslonca, E1 je krutost ravnala . Funkcija S(x), koja opisuje crte formula, je polinom trećeg stupnja između svake i dvije susjedne točke niza (nosača) i dva puta je kontinuirano diferencijabilna na cijelom intervalu (a, 6). Komentar. 06 interpoliranje kontinuirane funkcije Za razliku od Lagrangeovih interpolacijskih polinoma, slijed interpolirajućih kubičnih splineova na uniformnoj mreži uvijek konvergira interpolirajućoj kontinuiranoj funkciji, a kako se diferencijalna svojstva ove funkcije poboljšavaju, brzina 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 J). Svojstva interpolacijskog kubičnog splajna A. Alproksimativna svojstva kubičnog splajna. Svojstva aproksimacije interpolacijskog splajna ovise o glatkoći funkcije f(x) - što je veća glatkoća interpolirane funkcije, to je viši red aproksimacije i, kod pročišćavanja mreže, veća je brzina 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 O 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 i druga derivacija aproksimira funkciju B. Ekstremno svojstvo kubičnog splina. Interpolacijski kubični spline ima još jedno korisno svojstvo. Razmotrite sljedeći primjer. primjer. Konstruirajte funkciju /(x) koja minimizira funkcional na klasi funkcija iz prostora C2, čiji grafovi prolaze kroz točke niza. Između svih funkcija koje prolaze kroz referentne točke (x;, /(x, )) i pripada navedenom prostoru, to je kubni spline 5( x), koji zadovoljava rubne uvjete, daje ekstrem (minimum) funkcionalu. Napomena 1. Često se ovo ekstremno svojstvo uzima kao definicija interpolirajućeg kubika spline. Opaska 2. Zanimljivo je uočiti da interpolacijski kubični spline ima svojstvo ekstremnosti opisano gore na vrlo širokoj klasi funkcija, naime na klasi |o, 5]. 1.2. Izglađivanje kubičnih splineova O formulaciji problema izglađivanja Neka su zadani mreža i skup brojeva Komentar početnih podataka U praksi se često moramo suočiti sa slučajem kada su vrijednosti y u nizu navedene s nekim greška. Zapravo, to znači da je za svaki određen interval i 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, budući da ć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 u rezultatu 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, osim toga, imala prilično 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 ove vrste također nastaje kada je za zadani (točno) niz potrebno konstruirati funkciju koja ne prolazi kroz zadane točke, već blizu njih i, štoviše, mijenja se sasvim glatko. Drugim riječima, činilo se da tražena funkcija izglađuje dani niz, umjesto da ga interpolira. 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 u čvorovima mreže u razlikuju od brojeva y za zadane vrijednosti. Formulirani problem zaglađivanja je obnova glatka funkcija navedena u tablici. Jasno je da takav problem ima mnogo različitih rješenja. Postavljanjem dodatnih uvjeta na konstruiranu funkciju može se postići potrebna jednoznačnost. Definicija izglađujućeg kubičnog splajna Izglađujući kubični splajn S(x) na rešetki 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 u obliku ograničenja vrijednosti splinea i njegovih izvodnica na graničnim čvorovima mreže w. A. Rubni uvjeti tipa 1. - na krajevima intervala [a, b) navedene su vrijednosti prve derivacije željene funkcije. Rubni uvjeti tipa 2. - druge derivacije željene funkcije na krajevima intervala (a, b] jednake su nuli. B. Rubni uvjeti 3. tipa nazivaju se periodičkim. Teorem. Kubni spline S(x), minimizirajući funkcional (4) i zadovoljava rubne uvjete jednog od gornja tri tipa, jedinstveno je definiran. Definicija. Kubični splajn koji minimizira funkcional J(f) i zadovoljava rubne uvjete i-gotipa naziva se izglađujući splajn i-gotipa . Napomena: Na svakom izo-segmentu (, spline 5(x) je mio-interval trećeg stupnja i definiran je na ovom segmentu s četiri koeficijenta. Ukupan broj segmenata je m. To znači da u cilju potpunog određivanja spline, potrebno je pronaći 4m brojeva. Uvjet znači kontinuitet funkcije 5(ag) i svih njezinih izvoda na svim unutarnjim čvorovima mreže o. " Broj takvih čvorova je m - 1 Dakle, za izračunavanje koeficijenata svih polinoma dobivaju se 3(m - 1) uvjeta (jednadžbe).Konstrukcija izglađujućeg kubičnog splajna Opisat ćemo metodu za izračunavanje koeficijenata kubičnog splajna, u kojoj je broj veličina koje treba odrediti. jednak je 2m + 2. Na svakom od intervala, spline za izglađivanje funkcija se traži u sljedećem obliku. Ovdje su brojevi i rješenje sustava linearnih algebarskih jednadžbi, čiji oblik ovisi o vrsti rubnih uvjeta. Najprije opišimo kako se pronalaze vrijednosti n*. Za rubne uvjete 1. i 2. tipa 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: a svi koeficijenti se izračunavaju prema formulama (5) (vrijednosti s indeksima k i m + k smatraju se jednakima: Važna* napomena. Matrice sustava nisu degenerirane i stoga svaki od tih sustava ima jedinstveno rješenje. Ako su brojevi n, - pronađeni, tada se veličine lako određuju formulama gdje U slučaju periodičkih rubnih uvjeta, izbor njegovih koeficijenata Izbor težinskih koeficijenata p, - uključenih u funkcional (4), omogućuje kontrolu svojstava izglađujućih linija do određene mjere. Ako sve i izglađujući spline ispadne interpolacija. To posebno znači da što su točnije navedene vrijednosti, očekuje se da će odgovarajući težinski koeficijenti biti manji. Ako je potrebno da spline prolazi kroz točku (x^, Vk), onda težinski faktor p\ koji mu odgovara treba postaviti jednak nuli. U praktičnim proračunima najvažniji je izbor vrijednosti pi- Neka D, - pogreška u mjerenju 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 specificirati, na primjer, u obliku - gdje je c neka dovoljno mala konstanta. Međutim, ovaj izbor težine p ne dopušta korištenje "hodnika" zbog pogrešaka u vrijednostima y, -. Racionalniji, ali i radno intenzivniji algoritam za određivanje p vrijednosti može izgledati ovako. Ako su vrijednosti pronađene u fc-toj iteraciji, tada se pretpostavlja da 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 "koridora" (6) i, u konačnici, do glatko mijenjajućeg splajna. Malo teorije A. Obrazloženje formula za izračunavanje koeficijenata interpolacijskog kubičnog splajna. Uvedimo oznaku gdje su m trenutno nepoznate veličine. Njihov broj je jednak m + 1. Spline zapisan u obliku gdje zadovoljava uvjete interpolacije i kontinuiran je na cijelom intervalu [a, b\: stavljajući ga u formulu dobivamo redom. Osim toga, ima kontinuirana prva derivacija na intervalu [a, 6]: Diferenciranjem relacije (7) i njezinim stavljanjem 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čunajmo drugu derivaciju spline-a na intervalu: U točki x, - 0 (pri t = 1) imamo Izračunajmo drugu derivaciju spline-a na intervalu U točki imamo Iz uvjeta neprekidnosti spline-a. druga derivacija u unutarnjim čvorovima mreže a; dobivamo m - 1 relaciju gdje Dodavanjem ovih m - 1 jednadžbi još dvije, koje slijede 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 rsh u slučaju rubnih uvjeta 1. i 2. tipa ima oblik gdje je (rubni uvjeti 1. tipa), (rubni uvjeti 2. tipa). Za periodične rubne uvjete (rubni uvjeti tipa 3), mreža o; proširiti za još jedan čvor i pretpostaviti Tada će sustav za određivanje vrijednosti σ* imati kontinuitet oblika u drugom i (th - !)-tom čvoru mreže. Imamo Iz posljednje dvije relacije dobivamo nedostajuće dvije jednadžbe koje odgovaraju rubnim uvjetima 4. tipa: Isključivanjem nepoznatog goo iz jednadžbi, te nepoznatog pc iz jednadžbi, kao rezultat dobivamo sustav jednadžbi. Imajte na umu da je broj nepoznanica u ovom sustavu th - I. 6. Obrazloženje formula za izračun učinkovitosti izglađujućeg podšahovskog splajna. Uvedimo oznaku gdje su Zi i nj trenutno nepoznate veličine. Njihov broj je 2m + 2. Spline funkcija zapisana u obliku je kontinuirana na cijelom intervalu 8), imala je kontinuiranu prvu derivaciju na intervalu [a, 6]. Izračunajmo prvu derivaciju spline S(x) na intervalu: U točki x^ - 0 (pri t = 1) imamo Izračunajmo prvu derivaciju splajna 5(x) na intervalu: U točki imamo Iz uvjeta neprekidnosti prve derivacije splinea na unutarnjim čvorovima mreže i --> dobivamo relaciju m - 1. Ovaj odnos je prikladno zapisati u matričnom obliku. Koristi se sljedeća oznaka. Dodatno, spline na intervalu [a, 6) ima kontinuiranu drugu derivaciju: diferenciranjem relacije (8) i njezinim stavljanjem dobivamo redom Štoviše, matričnu relaciju dobivamo iz uvjeta minimuma funkcionala (4). Posljednje dvije matrične jednakosti mogu se smatrati linearnim sustavom od 2m + 2 linearne algebarske jednadžbe za 2m + 2 nepoznanice. Zamjenom stupca r u prvoj jednakosti s njegovim izrazom dobivenim iz relacije (9) dolazimo do matrične jednadžbe SPLINE TEORIJA primjeri rješenja za određivanje stupca M. Ova jednadžba ima jedinstveno rješenje zbog činjenice da je matrica A + 6HRH7 uvijek nedegeneriran. Nakon što smo ga pronašli, lako možemo identificirati grad Eamsshine. Elementi nitmagolnih matrica A i H određeni su samo parametrima mreže i (s koracima hi) i ne ovise o vrijednostima y^. Linearni prostor kubičnih spline funkcija Skup kubičnih splineova konstruiranih na segmentu [a, 6) duž mreže wcra+l čvor je linearni prostor dimenzije m + 3: 1) zbroj dvaju kubičnih splineova konstruiranih na mreži u >, i umnožak kubičnog splajna , konstruiranog na rešetki i>, s proizvoljnim brojem tajnije, su kubični splajnovi konstruirani na ovoj mreži, 2) svaki kubični splajn konstruiran na mreži i iz čvora potpuno je određen m + 1 vrijednost vrijednosti y" u tim čvorovima i dva rubna uvjeta - samo + 3 parametra. Odabirom baze u tom prostoru 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. Ova vrsta dodjele spline raširena je u računalnoj praksi. Osobito je prikladna baza podataka koja se sastoji od takozvanih kubičnih B-splajnova (osnovnih ili fundamentalnih splinova). Korištenje D-splineova može značajno smanjiti zahtjeve za memorijom računala. L-splineovi. B-splin nultog stupnja, konstruiran na brojevnom pravcu duž rešetke w, naziva se funkcija vile. B-splin stupnja k ^ I, konstruiran na brojevnom pravcu duž mreže u, određen je pomoću rekurentne funkcije. formula Grafovi B-splina prvog B, -1 "(g) i drugog in\7\x) stupnja 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).Prikladnije je numerirati kubične B-splineove tako da je spline B, -3* (π) različit od nule na segmentu r,-+2]. Predstavljamo formulu za kubični spline trećeg stupnja za slučaj uniformne mreže (s korakom A). U drugim slučajevima imamo. Tipični graf kubičnog B-splinea prikazan je na slici 13. Po posuđuje*, funkcija a) dvaput je kontinuirano diferencijabilna na intervalu, odnosno pripada klasi C2[a, "), k b) različita je od nule samo na četiri uzastopna intervala (Dopunimo mrežu w pomoćnim čvorovima uzeti potpuno proizvoljno. Pomoću proširene mreže w*, možemo konstruirati obitelj od m + 3 kubičnih B-splineova: Ova obitelj čini bazu u prostoru kubičnih splinova na segmentu (a, b]. Dakle, proizvoljni kubični spline S(z), konstruiran na segmentu |b, 6] mreže o; izm+1 čvora, mogu se na ovom segmentu prikazati u obliku linearne kombinacije.Uvjetima problema koeficijenti ft ove ekspanzije određeni su jednoznačno. ... U slučaju kada su zadane vrijednosti y* funkcije u čvorovima mreže te vrijednosti y o i Ym prve derivacije funkcije na krajevima mreže (problem interpolacije s granicom uvjeti prve vrste), ti se koeficijenti izračunavaju iz sustava sljedećeg oblika. Nakon eliminacije vrijednosti b- i i &m+i dobiva se linearni sustav s nepoznanicama 5q, ..., bm i tri -dimenzionalna matrica. Uvjet osigurava dijagonalnu dominaciju i, prema tome, mogućnost korištenja metode sweep za njegovo rješavanje. 3MMCMY 1. Linearni sustavi sličnog tipa nastaju kada se razmatraju drugi problemi interpolacije Zmmchnm* 2. U usporedbi s algoritmima opisanim u odjeljku 1.1, uporaba R-splinea u * problemima interpolacije omogućuje nam smanjenje * količine pohranjenih informacija, odnosno značajno smanjenje zahtjeva za memorijom računala, iako dovodi do povećanja broj operacija. Konstrukcija spline krivulja korištenjem spline funkcija Gore smo razmatrali nizove čije su točke bile numerirane tako da njihove apscise tvore 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 kako izbor klase aproksimirajućih krivulja (prometnih funkcija), tako i način 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 zadatak konstruiranja interpolacijske krivulje, možemo smatrati dani niz neplanarnim, odnosno jasno je da je za rješavanje ovog općeg problema potrebno značajno proširiti klasu dopuštenih krivulja, uključujući zatvorene krivulje, krivulje sa samosjecištima i prostorne krivulje. Pogodno je takve krivulje opisati pomoću parametarskih jednadžbi.Zahtijevamo. osim toga, funkcije moraju imati 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 segmentu)