Nech je uvedená tabuľka funkčných hodnôt y iv uzloch x 0 < х 1 < ... < х п . Označiť h i \u003d x i - x i -1 , i= 1, 2, ... , p.

Spline- plynulá krivka prechádzajúca danými bodmi ( x i, y i), i \u003d0, 1, ... , p. Spline interpolácia spočíva v tom, že v každom segmente [ x i -1 , x i] používa polynóm určitého stupňa. Najčastejšie používaný polynóm tretieho stupňa, menej často - druhý alebo štvrtý. V tomto prípade sa na stanovenie koeficientov polynómov použijú podmienky pre kontinuitu derivácií v interpolačných uzloch.

Kubická spline interpoláciaje lokálna interpolácia, keď na každom segmente [ x i -1 , x i], i \u003d1, 2, ... , ppoužíva sa kubická krivka, ktorá spĺňa určité podmienky plynulosti, a to kontinuitu samotnej funkcie a jej prvej a druhej derivácie v uzlových bodoch. Používanie kubickej funkcie je motivované nasledujúcimi úvahami. Ak predpokladáme, že interpolačná krivka zodpovedá elastickému pravítku fixovanému v bodoch ( x i, y i), potom z priebehu odolnosti materiálov je známe, že táto krivka je definovaná ako riešenie diferenciálnej rovnice f (IV) ( x) \u003d 0 v segmente [ x i -1 , x i] (pre jednoduchosť prezentácie neberieme do úvahy problémy spojené s fyzickými dimenziami). Všeobecným riešením takejto rovnice je polynóm tretieho stupňa s ľubovoľnými koeficientmi, ktorý je možné pohodlne napísať vo forme
S i(x) = a i + b i(x - x i -1) + s i(x - x i -1) 2 + d i(x - x i -1) 3 ,
x i -1 £ X £ x i, i \u003d1, 2, ... , p.(4.32)

Funkčné koeficienty S i(x) sú určené z podmienok spojitosti funkcie a jej prvej a druhej derivácie na vnútorných uzloch x i, i= 1, 2,..., p - 1.

Z vzorcov (4.32) s x = x i -1 dostaneme

S i(x i- 1) = y i -1 \u003d a i, i \u003d 1, 2,..., p,(4.33)

a o x = x i

S i(x i) = a i + b i h i + s i h i 2 + d i h i 3 ,(4.34)

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

Podmienky kontinuity interpolačnej funkcie sa zapisujú ako S i(x i) = S i -1 (x i), i= 1, 2, ... , n - 1 a z podmienok (4.33) a (4.34) vyplýva, že sú spokojní.

Nájdite deriváty funkcie S i(x):

S „i(x) = b i +2s i(x - x i -1) + 3di(x – x i -1) 2 ,

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

Kedy x = x i -1, máme S „i(x i -1) = b i, S " (x i -1) = 2s ia o x = x i dostať

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

Podmienky kontinuity derivácií vedú k rovniciam

S „i(x i) = S „i +1 (x i) Þ b i+ 2s i h i+ 3dih i 2 = b i +1 ,

i \u003d 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 ,

i \u003d l, 2, ..., n- 1. (4.36)

Celkovo ich máme 4 n - 2 rovnice na určenie 4 n neznámy. Na získanie ďalších dvoch rovníc sa používajú ďalšie okrajové podmienky, napríklad požiadavka na nulové zakrivenie interpolačnej krivky v koncových bodoch, to znamená rovnosť druhej derivácie s nulou na koncoch segmentu [ a, b] a = x 0 , b= x n:

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

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

Systém rovníc (4.33) - (4.37) možno zjednodušiť a je možné získať opakujúce sa vzorce na výpočet spline koeficientov.

Z podmienky (4.33) získame explicitné vzorce na výpočet koeficientov a i:

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

Vyjadrime sa d inaprieč c is použitím (4,36), (4,37):

; i = 1, 2,...,n; .

Dali sme s n +1 \u003d 0, potom pre d idostaneme jeden vzorec:

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

Náhradné výrazy pre a i a d i do rovnosti (4.34):

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

a vyjadrovať b i, naprieč s i:

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

Z rovníc (4.35) vylučujeme koeficienty b ia d is použitím (4.39) a (4.40):

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

Získame teda sústavu rovníc na určovanie s i:

Systém rovníc (4.41) možno prepísať na

Notácia je tu uvedená

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

Vyriešime sústavu rovníc (4.42) metódou sweep. Z prvej rovnice vyjadrujeme od 2 až od 3:

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

Náhradník (4.43) do druhej rovnice (4.42):

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

a vyjadrovať od 3 až od 4:

od 3 \u003d a 3 od 4 + b 3, (4,44)

Za predpokladu, že s i -1 \u003d a i -1 c i + b i -1 z i-tu rovnicu (4,42), ktorú získame

c i \u003d a ja so i +1 + b i

, i = 3,..., n- 1, a n \u003d 0, (4,45) c n +1 \u003d 0,

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

c 1 = 0.

3. Výpočet koeficientov a i, b i, d i:

a i = y i -1 ,

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

4. Výpočet hodnoty funkcie pomocou spline. Ak to chcete urobiť, nájdite takúto hodnotu iže daná hodnota premennej xpatrí do segmentu [ x i -1 , x i] a vypočítať

S i(x) = a i + b i(x - x i -1) + s i(x - x i -1) 2 + d i(x - x i -1) 3 . (4.50)

Interpolačné vzorce Lagrangeovej, Newtonovej a Stirlingovej atď. Pri použití veľkého počtu interpolačných uzlov v celom segmente [ a, b] často vedú k zlej aproximácii v dôsledku nahromadenia chýb v procese výpočtu. Okrem toho z dôvodu divergencie procesu interpolácie nemusí zvýšenie počtu uzlov nevyhnutne viesť k zvýšeniu presnosti. Aby sa znížili chyby, celý segment [ a, b] je rozdelený na čiastkové segmenty a na každom z nich je funkcia nahradená približným polynómom nízkeho stupňa. To sa nazýva po častiach polynomiálna interpolácia.

Jedným zo spôsobov interpolácie na celom segmente [ a, b] je spline interpolácia.

Spline je po častiach polynomická funkcia definovaná v segmente [ a, b] a má v tomto segmente množstvo kontinuálnych derivátov. Výhodou spline interpolácie oproti konvenčným interpolačným metódam je konvergencia a stabilita výpočtového procesu.

Uvažujme o jednom z najbežnejších prípadov v praxi - interpolácii funkcií kubický spline.
Nechajte na segmente [ a, b] je uvedená nepretržitá funkcia. Poďme predstaviť oblasť segmentu:

a označiť, .

Spline zodpovedajúci danej funkcii a interpolujúcim uzlom (6) je funkcia, ktorá spĺňa tieto podmienky:

1) v každom segmente je funkciou kubický polynóm;

2) funkcia, rovnako ako jej prvý a druhý derivát, sú spojité na segmente [ a, b] ;

Tretia podmienka sa nazýva podmienka interpolácie... Volá sa spline definovaný podmienkami 1) - 3) interpolácia kubický spline.

Zvážte spôsob, ako vytvoriť kubický spline.

Na každom zo segmentov budeme hľadať splajnovú funkciu vo forme polynómu tretieho stupňa:

(7)

kde požadované koeficienty.

Rozlišujte (7) trikrát o x:

odkiaľ nasleduje

Z podmienky interpolácie 3) získame:

Vyplýva to z podmienok spojitosti funkcie.

Ministerstvo školstva a vedy Ruskej federácie

Spolkový štátny rozpočet vzdelávacia inštitúcia vyššie odborné vzdelanie

„Štátna univerzita v Done“

Oddelenie "Softvér pre výpočtovú techniku \u200b\u200ba automatizované systémy„„ POVT a AS “

Špecializácia: Matematická podpora a správa informačných systémov

KURZOVÁ PRÁCA

v disciplíne „Metódy výpočtu“

na tému: „Interpolácia pomocou spline“

Vedúci práce:

Medvedeva Tatiana Alexandrovna

Rostov na Done

ÚLOHA

za seminárnu prácu v disciplíne „Metódy výpočtu“

Študent: Skupina Moiseenko Alexander VBMO21

Téma: "Spline Interpolation"

Termín na odoslanie práce na obhajobu je „__“ _______ 201_.

Počiatočné údaje pre semestrálna práca: prednášky o výpočtových metódach, ru.wikipedia.org, roč. Workshop o vyššej matematike B.V. Sobol

Úseky hlavnej časti: 1 PREHĽAD, 2 FORMULÁR INTERPOLÁCIE, 3 ALGORITMUS KUBICKEJ INTERPOLÁCIE, 4 DIZAJN SOFTVÉRU, 5 VÝSLEDKOV OPERÁCIE SOFTWARU.

Vedúci práce: / Medvedeva T.A. /

ESAY

Správa obsahuje: 19 strán, 3 grafy, 3 zdroje, -1 blokový diagram.

Kľúčové slová: INTERPOLÁCIA, SPLINE, systém Mathcad, KUBICKÁ INTERPOLÁCIA SPLINE.

Podrobne sa uvažuje o metóde interpolácie kubickými spline. Zobrazí sa zodpovedajúci softvérový modul. Je znázornená bloková schéma softvérového modulu. Zvažuje sa niekoľko príkladov.

ÚVOD

1. TEORETICKÝ PREHĽAD

2. INTERPOLÁCIA

2.1 Interpolácia pomocou kvadratickej spline

2.2 Kocková spline interpolácia

2.3 Vyhlásenie o probléme

3. ALGORITMUS Interpolácie s kubickým spline

4. DIZAJN SOFTVÉRU

5. VÝSLEDKY PREVÁDZKY SOFTVÉRU

5.1 Opis príkladov

5.2 Výsledok skúšky

5.3 Testovací prípad 1

5.4 Testovací prípad 2

5.5 Testovací prípad 3

ZÁVER

BIBLIOGRAFIA

ÚVOD

Aproximácia funkcií spočíva v približnom nahradení danej funkcie f(x) niektorou funkciou j ( x) takže odchýlka funkcie j ( x) z f(x) v danej oblasti bol najmenší. Funkcia j ( x) sa v tomto prípade nazýva približný. Typickým problémom aproximácie funkcií je problém interpolácie. Potreba interpolácie funkcií je spôsobená hlavne dvoma dôvodmi:

1. Funkcia f(x) má komplexný analytický popis, ktorý spôsobuje určité ťažkosti pri jeho používaní (napríklad f(x) je špeciálna funkcia: funkcia gama, eliptická funkcia atď.).

2. Analytický popis funkcie f(x) neznáme, t.j. f(x) je uvedený v tabuľke. V takom prípade je potrebné mať analytický popis, ktorý približne predstavuje f(x) (napríklad na výpočet hodnôt f(x) v ľubovoľných bodoch definície integrálov a derivácií f(x) atď.).

1. TEORETICKÝ PREHĽAD

Interpolácia - vo výpočtovej matematike metóda zisťovania medziľahlých hodnôt veličiny z dostupnej samostatnej množiny známych hodnôt. Pri riešení problémov s vedeckými a technickými výpočtami musíte často pracovať so súbormi hodnôt získaných empiricky alebo náhodným výberom. Spravidla je na základe týchto množín potrebné zostaviť funkciu, ktorá by mohla s vysokou presnosťou prijímať ďalšie získané hodnoty. Tento problém sa nazýva aproximácia funkcií. Interpolácia je druh aproximácie funkcií, pri ktorých krivka vytvorenej funkcie prechádza presne cez dostupné dátové body.

Spline je funkcia, ktorej doména je rozdelená na konečný počet segmentov, na každom z ktorých sa spline zhoduje s niektorým algebraickým polynómom. Maximálny stupeň použitých polynómov sa nazýva stupeň spline. Rozdiel medzi stupňom spline a výslednou hladkosťou sa nazýva defekt spline.

Splajny umožňujú efektívne riešiť problémy spracovania experimentálnych závislostí medzi parametrami, ktoré majú pomerne zložitú štruktúru.

Kubické drážky majú široké praktické využitie. Základné myšlienky teórie kubických drážok sa vytvorili v dôsledku pokusov o matematický popis pružných líšt vyrobených z elastického materiálu (mechanické drážky), ktoré už dávno používali projektanti v prípadoch, keď bolo potrebné nakresliť dostatočne hladký povrch. krivka cez dané body. Je známe, že tyč vyrobená z elastického materiálu, pripevnená v niektorých bodoch a v rovnovážnej polohe, nadobúda tvar, pri ktorom je jej energia minimálna. Táto základná vlastnosť umožňuje efektívne využívať spline pri riešení praktických problémov so spracovaním experimentálnych informácií.

2. INTERPOLÁCIA

2.1 Interpolácia pomocou kvadratickej spline

Takže na každom čiastočnom intervale interpolácie zostrojíme funkciu tvaru:

Budeme hľadať spline koeficienty z nasledujúcich podmienok:

a) Lagrangeove podmienky

b) spojitosť prvej derivácie v uzlových bodoch

Posledné dve podmienky dávajú rovnice, zatiaľ čo počet neznámych koeficientov. Chýbajúcu rovnicu možno získať z ďalších podmienok kladených na správanie spline. Môžete napríklad požadovať, aby hodnota prvej derivácie spline s 1 v bode x 0 bola nulová, t.

Nahradenie týchto výrazov vedie k nasledujúcim rovniciam

kde sa zavádza notácia

Vyjadrme z druhej rovnice koeficienty c 1 , predtým do ktorého boli dosadené hodnoty koeficientov a 1 z prvej rovnice:

Potom dosadením tohto výrazu do rovnice systému získame jednoduchý koeficient rekurencie pre koeficienty

Teraz je algoritmus na určovanie koeficientov splajnov úplne zrejmý. Najskôr pomocou vzorca určíme hodnoty všetkých koeficientov, pričom zohľadníme skutočnosť, že. Potom pomocou vzorca vypočítame koeficienty. Koeficienty sa určujú z prvej rovnice systému. V takom prípade je potrebné postup výpočtu koeficientov splajnov vykonať iba raz.

Po výpočte koeficientov stačí na výpočet samotného splajnu určiť počet intervalov, do ktorých spadá interpolačný bod, a použiť vzorec. Na určenie čísla intervalu použijeme algoritmus podobný algoritmu použitému v predchádzajúcom príklade pre kusovú kvadratickú interpoláciu.

2.2 Interpolácia kubických spline

Kubická interpolačná spline , vhodné pre túto funkciu f(x) a tieto uzly x i, volal funkciu S(x), spĺňa tieto podmienky:

1. V každom segmente [ x ja - 1 , X i], i \u003d1, 2, ..., N funkcia S(x) je polynóm tretieho stupňa,

2. Funkcia S(x), a tiež jeho prvý a druhý derivát sú v danom segmente spojité [ a, b],

3. S(x i) \u003d f(x i), i \u003d0, 1, ..., N.

Na každom zo segmentov [x ja - 1 , X i], i \u003d1, 2, ..., N budeme hľadať funkciu S(x) \u003d S i(x) ako polynóm tretieho stupňa:

S i(x) \u003d a i + b i(x - x ja - 1) + c i(x - x ja - 1) 2 + d i(x - 1) 3 ,

x ja - 1 Ј XЈ X i,

kde a i, b i, c i, d i - koeficienty, ktoré sa určia pre všetkých n elementárne segmenty. Ak má mať systém algebraických rovníc riešenie, musí sa počet rovníc presne rovnať počtu neznámych. Preto musíme dostať 4 n rovnice.

Prvé 2 n získame rovnicu z podmienky, že graf funkcie S(x) musí prechádzať danými bodmi, t.j.

S i(x ja - 1) \u003d r ja - 1 , S i(x i) = r i.

Tieto podmienky možno zapísať ako:

S i(x ja - 1) \u003d a i \u003d r ja - 1 ,

S i(x i) \u003d a i + b ih i + c ih + d ih \u003d r i,

h i \u003d x i - X ja - 1 , i \u003d1, 2, ..., n.

Ďalšie 2 n -Z podmienky spojitosti prvej a druhej derivácie v uzloch interpolácie vyplývajú 2 rovnice, t. J. Podmienka plynulosti krivky vo všetkých bodoch.

S " i + 1 (x i) \u003d S " i(x i), i \u003d1, ..., n -1,

S „“ i + 1 (x i) \u003d S "" i(x i), i \u003d1, ..., n -1,

S " i(x) \u003d b i + 2 c i(x - x ja - 1) + 3 d i(x - x ja - 1),

S " i + 1 (x) \u003d b i + 1 + 2 c i + 1 (x - x i) + 3 d i + 1 (x - x i).

Rovná sa v každom vnútornom uzle x \u003d x i hodnoty týchto derivátov vypočítané v ľavom a pravom intervale od uzla, získame (s prihliadnutím na h i \u003d x i - X ja - 1):

b i + 1 \u003d b i + 2 h ic i + 3h d i, i \u003d1, ..., n -1,

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

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

ak x = x i

c i + 1 \u003d c i + 3 h id i, i \u003d1, 2, ..., n -1.

V tejto fáze máme 4 n neznáme a 4 n - 2 rovnice. Preto je potrebné nájsť ďalšie dve rovnice.

Pri voľnom upevnení koncov možno zakrivenie priamky v týchto bodoch rovnať nule. Z podmienok nulového zakrivenia na koncoch vyplýva, že druhé derivácie sa v týchto bodoch rovnajú nule:

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

c i = 0 a 2 c n + 6 d nh n = 0.

Rovnice tvoria sústavu lineárnych algebraických rovníc na určenie 4 nkoeficienty: a i , b i , c i, d i (i = 1, 2, . . ., n).

Tento systém je možné uviesť do pohodlnejšej formy. Všetky koeficienty možno okamžite zistiť z podmienky a i.

i \u003d1, 2, ..., n -1,

Nahradením dostaneme:

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

b n = - (h nc n)

Z rovnice vylučujeme koeficienty b i a d i. Nakoniec získame nasledujúci systém rovníc iba pre koeficienty od i:

c 1 = 0 a c n + 1 = 0:

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

i \u003d2, 3, ..., n.

Podľa zistených koeficientov od i ľahko vypočítateľný d i, b i.

2.3 Vyhlásenie o probléme

V segmente [ a, b] sú dané n + 1 bodov x i = x 0 , x 1 , . . ., x nktoré sa nazývajú uzly interpolácia , a hodnoty niektorej funkcie f(x) v týchto bodoch

f(x 0) \u003d r 0 , f(x 1) = r 1 , ... ... ., f(x n) \u003d r n.

Vytvorte interpolačnú funkciu pomocou kubických spline f(x).

3. ALGORITMUS Interpolácie s kubickým spline

Poďme sa oboznámiť s algoritmom programu.

1. Vypočítajte hodnoty a

2. Na základe týchto hodnôt vypočítame koeficienty ometenia a o.

3. Na základe získaných údajov vypočítame koeficienty

4. Potom pomocou spline vypočítame hodnotu funkcie.

4. DIZAJN SOFTVÉRU

5. VÝSLEDKY PREVÁDZKY SOFTVÉRU

5.1 Popis testovacích prípadov

V priebehu tejto práce bol vyvinutý softvérový modul, ktorý vykresľuje zodpovedajúcu krivku cez dostupné body. Na overenie efektívnosti práce sa uskutočnili testovacie prípady.

5.2 Výsledky skúšky

Na kontrolu správnosti vykonania testovacích prípadov sa používa funkcia cspline zabudovaná v balíku MATHCAD, ktorá vracia vektor druhých derivácií pri priblížení sa k kubickému polynómu v kontrolných bodoch.

5.3 Testovací prípad 1

Obrázok 1.1 - výsledok programu

Testovací prípad 2

Obrázok 1.2 - výsledok programu

Testovací prípad 3

Obrázok 1.3 - výsledok programu

ZÁVER

spline interpolačná funkcia výpočtová

Interpolácia funkcií hrá významnú úlohu vo výpočtovej matematike, t.j. zostrojenie inej (spravidla jednoduchšej) funkcie podľa danej funkcie, ktorej hodnoty sa zhodujú s hodnotami danej funkcie v určitom počte bodov. Interpolácia má navyše praktický aj teoretický význam. V praxi často nastáva problém s obnovením spojitej funkcie z jej tabuľkových hodnôt, napríklad získaných v priebehu nejakého experimentu. Pri výpočte mnohých funkcií sa ukazuje, že je efektívne ich aproximovať pomocou polynómov alebo zlomkových racionálnych funkcií. Teória interpolácie sa používa pri konštrukcii a štúdiu kvadratúrnych vzorcov pre numerickú integráciu na získanie metód riešenia diferenciálnych a integrálnych rovníc. Hlavnou nevýhodou polynomiálnej interpolácie je to, že je nestabilná na jednej z najpohodlnejších a často používaných mriežok - mriežke s ekvidistantnými uzlami. Ak to problém umožňuje, je možné ho vyriešiť výberom siete s Čebyševovými uzlami. Ak si nemôžeme slobodne zvoliť interpolačné uzly, alebo potrebujeme iba algoritmus, ktorý nie je príliš náročný na výber uzlov, potom môže byť racionálna interpolácia vhodnou alternatívou k polynomiálnej interpolácii.

Medzi výhody spline interpolácie patrí vysoká rýchlosť spracovania výpočtového algoritmu, pretože spline je polynomiálna funkcia po častiach a počas interpolácie sa údaje súčasne spracúvajú na malom počte meracích bodov patriacich k fragmentu, o ktorom sa v súčasnosti uvažuje. Interpolovaný povrch popisuje priestorovú variabilitu rôznych mierok a je zároveň hladký. Posledná uvedená okolnosť umožňuje priamo analyzovať geometriu a topológiu povrchu pomocou analytických postupov.

BIBLIOGRAFIA

1. BV Sobol, B. Ch. Meskhi, I. M. Peshkhoev. Praktická výpočtová matematika. - Rostov na Done: Phoenix, 2008;

2. N.S. Bakhvalov, N.P. Židkov, G.M. Kobelkov. Numerické metódy. Vydavateľstvo „Laboratórium základných znalostí“. 2003

3.www.wikipedia.ru/spline

Podobné dokumenty

Výpočtové metódy lineárnej algebry. Funkčná interpolácia. Newtonov interpolačný polynóm. Interpolačné uzly. Interpolácia Lagrangeov polynóm. Spline interpolácia. Kubické spline koeficienty.

laboratórne práce, doplnené 2. 6. 2004


Interpolácia funkcií hrá vo výpočtovej matematike zásadnú úlohu. Lagrangeov vzorec. Aitkenova interpolácia. Newtonove interpolačné vzorce pre rovnako vzdialené uzly. Newtonov vzorec s oddelenými rozdielmi. Spline interpolácia.

test, pridané 1. 5. 2011


Zostrojte Newtonov interpolačný polynóm. Nakreslite graf a označte na ňom interpolačné uzly. Zostrojte Lagrangeov interpolačný polynóm. Interpolujte s drážkovaním tretieho stupňa.

laboratórne práce, doplnené 2. 6. 2004


Úloha interpolácie funkcií, ktorých hodnoty sa zhodujú s hodnotami danej funkcie v určitom počte bodov. Interpolácia funkcie polynómami, priamo spojité funkcie na intervale a v bode. Definícia pojmu chyba interpolácie.

semestrálna práca, pridané 10. 4. 2011


Spojitá a bodová aproximácia. Interpolačné polynómy Lagrange a Newton. Chyba globálnej interpolácie, kvadratická závislosť. Metóda najmenších štvorcov. Výber empirických vzorcov. Po častiach konštantná a po častiach lineárna interpolácia.

seminárna práca pridaná 14.03.2014


Zoznámenie sa s históriou vzhľadu metódy zlatého rezu. Zohľadnenie základných pojmov a algoritmu na vykonávanie výpočtov. Štúdium metódy Fibonacciho čísel a jej vlastností. Popis príkladov implementácie metódy zlatého rezu v programovaní.

semestrálna práca, pridané 8. 9. 2015


Problémy globálnej a miestnej interpolácie za Lagrangeom a Newtonom; chovanie kolónií interpolačného polynómu; funkcie Runge. Spline je skupina slovných kubických polynómov s nepretržitým prvým a ďalším jednoduchým prechodom spline-interpolácia.

prezentácia pridaná 2. 6. 2014


Metódy numerickej diferenciácie. Výpočet derivácie, najjednoduchšie vzorce. Numerická diferenciácia založená na interpolácii algebraickými polynómami. Aproximácia Lagrangeovým polynómom. Diferenciácia pomocou interpolácie.

semestrálna práca, pridané 15. 2. 2016


Popis metód riešenia sústavy lineárnych algebraických rovníc: inverzná maticaJacobi, Gauss-Seidel. Vyslovenie a riešenie problému interpolácie. Výber polynomiálnej závislosti metódou najmenších štvorcov. Vlastnosti relaxačnej metódy.

laboratórne práce, pridané 06.06.2011


Problém hľadania extrému: podstata a obsah, optimalizácia. Riešenie metódami kvadratickej interpolácie a zlatého rezu, ich komparatívne charakteristiky, stanovenie hlavných výhod a nevýhod. Počet iterácií a odhad presnosti.

2.2 Kocková spline interpolácia

Kubický interpolačný spline zodpovedajúci danej funkcii f (x) a daným uzlom x i je funkcia S (x), ktorá spĺňa nasledujúce podmienky:

1. Na každom segmente, i \u003d 1, 2, ..., N je funkcia S (x) polynómom tretieho stupňa,

2. Funkcia S (x), ako aj jej prvá a druhá derivácia, sú na intervale spojité,

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

Na každom z intervalov i \u003d 1, 2, ..., N budeme hľadať funkciu S (x) \u003d S i (x) vo forme polynómu tretieho stupňa:

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

x i - 1 Ј x Ј x i,

kde a i, b i, c i, d i - koeficienty, ktoré sa určia na všetkých n elementárnych segmentoch. Ak má mať systém algebraických rovníc riešenie, musí sa počet rovníc presne rovnať počtu neznámych. Musíme teda dostať 4n rovnice.

Prvé 2n rovnice získame z podmienky, že graf funkcie S (x) musí prechádzať danými bodmi, t.j.

S i (x i - 1) \u003d y i - 1, S i (x i) \u003d y i.

Tieto podmienky možno zapísať ako:

S i (x i - 1) \u003d a i \u003d y i - 1,

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

h i \u003d x i - x i - 1, i \u003d 1, 2, ..., n.

Nasledujúce 2n - 2 rovnice vyplývajú z podmienky spojitosti prvej a druhej derivácie v interpolačných uzloch, to znamená z podmienky plynulosti krivky vo všetkých bodoch.

S i + 1 (x i) \u003d S i (x i), i \u003d 1, ..., n - 1,

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

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

Rovnicou v každom vnútornom uzle x \u003d x i hodnoty týchto derivátov vypočítané v ľavom a pravom intervale od uzla získame (s prihliadnutím na h i \u003d x i - x i - 1):

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

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

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

ak x \u003d x i

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

V tejto fáze máme 4n neznáme a 4n - 2 rovnice. Preto je potrebné nájsť ďalšie dve rovnice.

Pri voľnom upevnení koncov možno zakrivenie priamky v týchto bodoch rovnať nule. Z podmienok nulového zakrivenia na koncoch vyplýva, že druhé derivácie sa v týchto bodoch rovnajú nule:

S 1 (x 0) \u003d 0 a S n (x n) \u003d 0,

c i \u003d 0 a 2 c n + 6 d n h n \u003d 0.

Rovnice tvoria sústavu lineárnych algebraických rovníc na určovanie 4n koeficientov: a i, b i, c i, d i (i \u003d 1, 2, ..., N).

Tento systém je možné uviesť do pohodlnejšej formy. Všetky koeficienty a i možno nájsť z podmienky naraz.

i \u003d 1, 2, ..., n - 1,

Nahradením dostaneme:

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

b n \u003d - (h n c n)

Z rovnice vylučujeme koeficienty b i a d i. Nakoniec dostaneme nasledujúcu sústavu rovníc iba pre koeficienty s i:

c 1 \u003d 0 a c n + 1 \u003d 0:

h i - 1 c i - 1 + 2 (h i - 1 + h i) c i + h i c i + 1 \u003d 3,

i \u003d 2, 3, ..., n.

Z nájdených koeficientov s i je ľahké vypočítať d i, b i.

Výpočet integrálov metódou Monte Carlo

Tento softvérový produkt implementuje schopnosť nastavovať ďalšie obmedzenia v integračnej oblasti pomocou dvoch dvojrozmerných spline povrchov (pre celé číslo dimenzie 3) ...

Funkčná interpolácia

Nech je uvedená tabuľka hodnôt funkcie f (xi) \u003d yi (), v ktorej sú umiestnené vo vzostupnom poradí od hodnôt argumentu: x0< x1 < … < xn. Чтобы построить кубический сплайн, требуется определить коэффициенты ai0, ai1, ai2, ai3...

Spline interpolácia

Spline interpolácia

Spline interpolácia

Poďme sa oboznámiť s algoritmom programu. 1. Vypočítame hodnoty a 2. Na základe týchto hodnôt vypočítame rozmetávacie koeficienty a o. 3. Na základe získaných údajov vypočítame koeficienty 4 ...

Matematické modelovanie technické objekty

Zabudované funkcie MathCADu umožňujú kresliť krivky rôznej zložitosti cez experimentálne body počas interpolácie. Lineárna interpolácia ...

Metódy aproximácie funkcií

V každom segmente sa interpolačný polynóm rovná konštante, menovite ľavej alebo pravej hodnote funkcie. Pre ľavú po častiach lineárnu interpoláciu F (x) \u003d fi-1, ak xi-1? X

Metódy aproximácie funkcií

V každom intervale je funkcia lineárna Fi (x) \u003d kix + li. Hodnoty koeficientov sa zistia zo splnenia interpolačných podmienok na koncoch segmentu: Fi (xi-1) \u003d fi-1, Fi (xi-1) \u003d fi. Dostaneme sústavu rovníc: kixi-1 + li \u003d fi-1, kixi + li \u003d fi, odkiaľ nájdeme ki \u003d li \u003d fii- kixi ...

Metódy riešenia sústavy lineárnych rovníc. Interpolácia

Vyhlásenie o probléme interpolácie. Na intervale je uvedená sústava bodov (interpolačné uzly) xi, i \u003d 0,1, ..., N; a? x ja? b a hodnoty neznámej funkcie v týchto uzloch fn i \u003d 0,1,2,…, N. Nastaviť sa dajú tieto úlohy: 1) Zostrojte funkciu F (x) ...

Konštrukcia matematického modelu popisujúceho postup riešenia diferenciálnej rovnice

3.1 Konštrukcia Lagrangeovho interpolačného polynómu a kondenzácia hodnôt Zrejmým spôsobom riešenia tohto problému je výpočet hodnôt ѓ (x) pomocou analytických hodnôt funkcie ѓ. K tomu - podľa prvotných informácií ...

Ak sú to stupne (1, x, x2, ..., xn), hovoríme o algebraickej interpolácii a funkcia sa nazýva interpolačný polynóm a označuje sa ako: (4) If () (5), potom môžeme zostrojte interpolačný polynóm stupňa n a navyše iba jeden ...

Praktické použitie interpolácie plynulými funkciami

Uvažujme o príklade interpolácie pre prvky množiny. Pre jednoduchosť a stručnosť vezmeme \u003d [- 1; 1] ,. Nechajte body a buďte medzi sebou iní. Predstavme si tento problém: (12) zostrojme polynóm vyhovujúci týmto podmienkam ...

Aplikácia numerických metód na riešenie matematických úloh

Numerické metódy

Ako už bolo spomenuté vyššie, úlohou interpolácie je nájsť taký polynóm, ktorého graf prechádza danými bodmi. Nech je funkcia y \u003d f (x) daná pomocou tabuľky (tabuľka 1) ...

Numerické metódy riešenia matematických úloh

Krivky a povrchy vyskytujúce sa v praktických problémoch majú často pomerne zložitý tvar, ktorý neumožňuje univerzálnu analytickú úlohu ako celok pomocou elementárnych funkcií. Preto sú zostavené z pomerne jednoduchých hladkých fragmentov - segmentov (kriviek) alebo výrezov (povrchov), z ktorých každý je možné celkom uspokojivo opísať pomocou elementárnych funkcií jednej alebo dvoch premenných. V tomto prípade je celkom prirodzené vyžadovať, aby hladké funkcie, ktoré sa používajú na zostrojenie čiastkových kriviek alebo plôch, mali podobnú povahu, napríklad by išlo o polynómy rovnakého stupňa. A aby bola výsledná krivka alebo povrch dostatočne hladký, musíte byť obzvlášť opatrní pri spojoch zodpovedajúcich fragmentov. Stupeň polynómov sa volí z jednoduchých geometrických hľadísk a spravidla nie je veľký. Na plynulú zmenu dotyčnice pozdĺž celej zloženej krivky stačí opísať priliehajúce krivky pomocou polynómov tretieho stupňa, kubických polynómov. Koeficienty takýchto polynómov je možné zvoliť vždy tak, aby zakrivenie zodpovedajúcej zloženej krivky bolo spojité. Kubické drážky, ktoré vznikajú pri riešení jednorozmerných problémov, je možné prispôsobiť konštrukcii fragmentov paplónov. A tu sa celkom prirodzene objavujú bikubické spline, ktoré sú popísané polynómami tretieho stupňa v každej z týchto dvoch premenných. Práca s takýmito spline už vyžaduje oveľa viac výpočtov. Správne organizovaný proces však umožní v maximálnej miere neustále sa rozvíjajúce výpočtové schopnosti. Funkcie Spline Pustite na segment, to znamená na Poznámka. Index (t) čísel a ^ to naznačuje. že množina koeficientov, ktoré definujú funkciu S (x), na každom čiastočnom segmente D, je iná. Na každom zo segmentov Dl je spline 5 (x) polynómom stupňa p a je na tomto segmente určená koeficientom p + 1. Celkové čiastkové segmenty - to. Preto, aby sme úplne určili spline, je potrebné nájsť (p + 1), potom čísla Podmienka) znamená spojitosť funkcie 5 (x) a jej derivátov na všetkých vnútorných uzloch mriežky w. Počet takýchto uzlov je m - 1. Teda pre nájdenie koeficientov všetkých polynómov sa získajú podmienky (rovnice) p (m - 1). Pre úplnú definíciu spline (chýbajú (podmienky (rovnice)). Výber ďalších podmienok je daný povahou uvažovaného problému a niekedy jednoducho túžbou používateľa.) Príklady riešení SPLINE THEORY Najčastejšie sa problémy s interpoláciou a vyhladzovaním zvažujú, keď sa vyžaduje zostrojenie jedného alebo druhého spline z daného radu bodov v rovine. Pri interpolačných problémoch sa vyžaduje, aby spline graf prechádzal cez body, čo ukladá m + 1 ďalšia podmienka (rovnice) pre jej koeficienty. Zvyšné podmienky p - 1 (rovnice) pre jednoznačnú konštrukciu spline sú najčastejšie špecifikované vo forme hodnôt najnižších derivácií spline na koncoch uvažovaného segmentu [a, 6] - hranica (hraničné) podmienky. Schopnosť zvoliť rôzne okrajové podmienky vám umožňuje vytvárať spline s rôznymi vlastnosťami. Pri vyhladzovaní úloh je spline zostrojené tak, aby jej graf prechádzal v blízkosti bodov (z „„ Y “), * \u003d 0, 1, ..., t, a nie cez ne. Mieru tejto blízkosti je možné definovať rôznymi spôsobmi, čo vedie k významnej škále vyhladzovacích drážok. Popísané možnosti voľby pri konštrukcii funkcií spline v žiadnom prípade nevyčerpávajú celú ich rozmanitosť. A ak sa spočiatku uvažovalo iba po častiach s polynomiálnymi spline funkciami, potom ako sa rozširoval rozsah ich aplikácií, začali sa objavovať splajny, „zlepené“ od iných elementárnych funkcií. Interpolácia kubických splajnov Výrok interpolačného problému Nech je na segmente zadaná sieť ω [a, 6) Zvážte množinu čísel Problém. Zostrojte funkciu, ktorá je plynulá na intervale (a, 6], ktorá nadobúda dané hodnoty v uzloch mriežky o », to znamená, že: Formulovaný problém s interpoláciou spočíva v obnovení hladkej funkcie danej z tabuľky. (Obr. 2) Je zrejmé, že takýto problém má svoju množinu rôzne riešenia ... Uložením ďalších podmienok na konštruovanú funkciu je možné dosiahnuť potrebnú jednoznačnosť. V aplikáciách je často potrebné aproximovať funkciu danú analyticky pomocou funkcie s predpísanými dostatočne dobrými vlastnosťami. Napríklad v prípadoch, keď je výpočet hodnôt danej funkcie f (x) v bodoch segmentu [a, 6] spojený so značnými ťažkosťami a / alebo daná funkcia f (x) nemá požadovanú plynulosť, je vhodné použiť inú funkciu, ktorá sa bude aproximovať danou funkciou a nebude mať uvedené nevýhody. Problém interpolácie funkcií. Zostrojte na segmente [a, 6] hladkú funkciu a (x), ktorá sa zhoduje v uzloch mriežky w s danou funkciou f (x). Definícia interpolácie kubický spline Interpolácia kubický spline S (x) na sieti w je funkcia, ktorá 1) na každom zo segmentov je polynóm tretieho stupňa, 2) je dvakrát spojito diferencovateľná na segmente [a, b ], to znamená, že patrí do triedy C2 [a, 6] a 3) spĺňa podmienky Na každom zo segmentov je spline S (x) polynómom tretieho stupňa a je na tomto segmente určená štyrmi koeficientmi. . Celkové segmenty - m. Preto, aby sme úplne určili spline, je potrebné nájsť čísla 4 m. Podmienkou sa rozumie spojitosť funkcie S (x) a jej derivátov S "(x) a 5" (x) na všetky vnútorné uzly mriežky w. Počet takýchto uzlov je m - 1. Teda na zistenie koeficientov všetkých polynómov sa získajú 3 (m - 1) podmienky (rovnice). Spolu s podmienkami (2) sa získajú podmienky (rovnice). Hraničné (hraničné) podmienky Dve chýbajúce podmienky sú špecifikované vo forme obmedzení hodnôt spline a / alebo jeho derivátov na konci intervalu [a, 6]. Pri konštrukcii interpolačného kubického spline sa najčastejšie používajú okrajové podmienky nasledujúcich štyroch typov. A. Okrajové podmienky 1. typu. - na koncoch intervalu [a, b] sa nastavia hodnoty prvej derivácie požadovanej funkcie. B. Okrajové podmienky 2. typu. - na koncoch intervalu (a, 6) sa nastavia hodnoty druhej derivácie požadovanej funkcie. B. Okrajové podmienky 3. typu. sa nazývajú periodické. Je prirodzené vyžadovať splnenie týchto podmienok v prípadoch, keď je interpolovaná funkcia periodická s periódou T \u003d b-a. D. Okrajové podmienky 4. typu. vyžadovať osobitný komentár. Komentovať. Vo vnútorných uzloch sepsy je tretia derivácia funkcie S (x) všeobecne nespojitá. Počet diskontinuít tretieho derivátu sa však dá znížiť použitím podmienok štvrtého typu. V takom prípade bude zostrojený spline kontinuálne trikrát diferencovateľný v intervaloch. Konštrukcia interpolačného kubického spline. Popíšeme si metódu výpočtu koeficientov kubického spline, pre ktoré sa počet veličín, ktoré sa majú určiť, rovná. V každom z intervalov sa interpolačná spline funkcia hľadá v nasledujúcom tvare. TADY SPLINE TEORIE sú príkladmi riešení a čísla sú riešením systému lineárnych algebraických rovníc, ktorých forma závisí od typu okrajových podmienok. Pre okrajové podmienky 1. a 2. typu má tento systém nasledujúcu formu, kde koeficienty závisia od výberu okrajových podmienok. Okrajové podmienky 1. typu: Okrajové podmienky 2. typu: V prípade okrajových podmienok 3. typu je systém na určovanie čísel zapísaný nasledovne Počet neznámych v poslednom systéme sa rovná mn, keďže od z podmienky periodicity vyplýva, že n \u003d nt. Pre okrajové podmienky 4. typu má systém na určovanie čísel tvar kde. Podľa nájdeného riešenia systému možno čísla on a nm určiť pomocou vzorcov Dôležitá poznámka. Matice všetkých troch lineárnych algebraických systémov sú matice s diagonálnymi dominantami. Tamie matice nie sú zdegenerované, a preto má každý z týchto systémov jedinečné riešenie. Veta. Interpolačný kubický spline vyhovujúci podmienkam (2) a okrajová podmienka jedného zo štyroch typov uvedených vyššie existuje a je jedinečný. Konštruovať interpoláciu kubického spline teda znamená nájsť jeho koeficienty. Keď sa nájdu spline koeficienty, hodnota spline S (x) v ľubovoľnom bode segmentu [a, b] sa dá nájsť podľa vzorca (3 ). Pre praktické výpočty je však vhodnejší nasledujúci algoritmus na zistenie hodnoty 5 (g). Nech x 6 [x ", Najprv sa hodnoty A a B vypočítajú podľa vzorcov a potom sa nájde hodnota 5 (g): Aplikácia tohto algoritmu významne znižuje výpočtové náklady na stanovenie hodnoty Poradenstvo pre používateľa výber hraničných (hraničných) podmienok a interpolačných uzlov umožňuje do istej miery vlastnosti interpolačných spline. A. Voľba okrajových (okrajových) podmienok. Voľba okrajových podmienok je jedným z ústredných problémov vo funkčnej interpolácii. Osobitný význam nadobúda v prípade, keď je potrebné zabezpečiť vysokú presnosť aproximácie funkcie f (x) spline 5 (g) v blízkosti koncov segmentu [a, 6]. Hraničné hodnoty majú znateľný vplyv na správanie splajnu 5 (g) v blízkosti bodov a a b a tento efekt s ich vzdialenosťou rýchlo slabne. Voľba okrajových podmienok je často daná dostupnosťou ďalších informácií o správaní aproximovanej funkcie f (x). Ak sú hodnoty prvej derivácie f "(x) známe na koncoch segmentu (a, 6], potom je prirodzené použiť okrajové podmienky typu 1. Ak sú hodnoty druhej derivácie f „(x) sú známe na koncoch segmentu [a, 6), potom prirodzene používajú okrajové podmienky 2. typu. Ak existuje voľba medzi okrajovými podmienkami 1. a 2. typu, mali by sa uprednostniť podmienky 1. typu. Ak je f (x) periodická funkcia, mali by sme sa zastaviť na okrajových podmienkach 3. typu. Ak nie sú k dispozícii ďalšie informácie o správaní sa funkcie, ktorá sa aproximuje, často sa používajú takzvané prirodzené okrajové podmienky. Je však potrebné mať na pamäti, že pri tomto výbere okrajových podmienok je presnosť aproximácie funkcie f ( x) spline S (x) blízko koncov segmentu (a, ft] prudko klesá. Niekedy sa používajú okrajové podmienky 1. alebo 2. typu, ale nie s presnými hodnotami zodpovedajúcich derivácií, ale s ich rozdielové aproximácie. Presnosť tohto prístupu nie je vysoká. Praktické skúsenosti s výpočtami ukazujú, že v posudzovanej situácii je najvhodnejšou voľbou okrajové podmienky typu 4. B. Výber interpolačných uzlov Ak tretia derivácia f "" (x ) funkcie má diskontinuitu v niektorých bodoch segmentu [a, b], aby sa zlepšila kvalita aproximácie, mali by sa tieto body zahrnúť do počtu interpolačných uzlov. druhá derivácia f "(x), potom v aby sa zabránilo oscilácii spline v blízkosti bodov zlomu, musia sa prijať špeciálne opatrenia. interpolačné uzly sú vybrané tak, aby body diskontinuity druhej derivácie spadali do intervalu \\ xif) také, že. Hodnotu a je možné zvoliť numerickým experimentom (často stačí nastaviť a \u003d 0,01). Existuje súbor receptov na prekonanie ťažkostí, ktoré vznikajú, keď je prvá derivácia f "(x) nespojitá. Jeden z najjednoduchších je nasledujúci: rozdeliť aproximačný segment na intervaly, kde je derivácia spojitá, a vytvoriť spline na každom z týchto intervalov.Výber interpolačnej funkcie (plusy a mínusy) Prístup 1. Lagrangeov interpolačný polynóm Pre dané pole Príklady riešení SPLINE THEORY (obr. 3) Lagrangeov interpolačný polynóm je určený vzorcom Lagrangeove interpolačné polynomické vlastnosti treba brať do úvahy od dve protichodné polohy, ktoré pojednávajú o hlavných výhodách oddelene od nevýhod. Hlavné výhody 1. prístup: 1) graf Lagrangeovho interpolačného polynómu prechádza každým bodom poľa, 2) konštruovaná funkcia je ľahko opísateľná (počet koeficienty Lagrangeovho interpolačného polynómu na mriežke u\u003e sa rovná m + 1), 3) skonštruovaná funkcia má spojité derivácie ľubovoľného póru yadka, 4) dané pole interpolačného polynómu je jednoznačne určené. Hlavné nevýhody prvého prístupu: 1) stupeň Lagrangeovho interpolačného polynómu závisí od počtu uzlov mriežky a čím väčšie je toto číslo, tým vyšší je stupeň interpolačného polynómu, a preto je potrebných viac výpočtov, 2 ) zmena aspoň jedného bodu v poli vyžaduje úplný prepočet koeficientov Lagrangeovho interpolačného polynómu, 3) pridanie nový bod do poľa zvyšuje stupeň Lagrangeovho interpolačného polynómu o jeden a vedie tiež k úplnému prepočtu jeho koeficientov, 4) s neobmedzeným spresnením ôk, stupeň Lagrangeovho interpolačného polynómu sa zvyšuje na neurčito. Správanie Lagrangeovho interpolačného polynómu pri neobmedzenom zdokonalení ôk si všeobecne vyžaduje osobitnú pozornosť. Poznámky A. K aproximácii spojitej funkcie pomocou polynómu. Je známe (Weierstrass, 1885), že každú spojitú (a ešte hladšiu) funkciu na segmente je možné aproximovať aj polynómom na tomto segmente. Popíšme túto skutočnosť z hľadiska vzorcov. Nech f (x) je spojitá funkcia na intervale [a, 6]. Potom pre každé ε\u003e 0 existuje polynóm Pn (x) taký, že pre ľubovoľné x v intervale [a, 6] bude platiť nerovnosť (obr. 4). Všimnite si, že polynómy rovnakého stupňa aproximujúce funkciu f ( x) so stanovenou presnosťou je ich nekonečne veľa. Zostrojme mriežku w v segmente [a, 6]. Je zrejmé, že jeho uzly sa vo všeobecnosti nezhodujú s priesečníkmi grafov polynómu Pn (x) a funkcie f (x) (obr. 5). Preto pre danú mriežku polynóm Pn (x) nie je interpolácia. Keď sa spojitá funkcia aproximuje interpolačným polynómom Jla-grack, jej graf sa nielenže nemusí nachádzať v blízkosti grafu funkcie f (x) v každom bode segmentu [a, b), ale môže sa odchýliť z tejto funkcie toľko, koľko chcete. Zoberme si dva príklady. Príklad 1 (Rung, 1901). S neobmedzeným nárastom počtu uzlov pre funkciu na segmente [-1, 1] je limitná rovnosť splnená (obr. 6), príklad 2 (Berishtein, 1912). Postupnosť Lagrangeových interpolačných polynómov skonštruovaných na jednotných mriežkach pc pre spojitú funkciu f (x) \u003d | x | na intervale so zvyšujúcim sa počtom uzlov m nemá tendenciu k funkcii f (x) (obr. 7). Prístup 2. Kusovo-lineárna interpolácia Ak sa upustí od plynulosti interpolovanej funkcie, pomer medzi počtom výhod a počtom nevýhod sa dá zreteľne zmeniť smerom k predchádzajúcej. Konštruujeme po častiach lineárnu funkciu postupným spájaním bodov (xit y,) segmentmi priamky (obr. 8). Hlavné výhody druhého prístupu: 1) graf lineárnej funkcie po častiach prechádza každým bodom poľa, 2) konštruovaná funkcia je ľahko opísateľná (počet koeficientov zodpovedajúcich lineárnych funkcií pre mriežku (1) je potrebné určiť je 2m), 3) zostrojená funkcia je definovaná daným poľom jednoznačne, 4) stupeň polynómov použitých na popis interpolačnej funkcie nezávisí od počtu uzlov mriežky (rovný 1), 5) zmena jedného bodu v poli vyžaduje výpočet štyroch čísel (koeficienty dvoch lineárnych odkazov pochádzajúcich z nového bodu), 6) pridanie ďalšieho bodu do poľa vyžaduje výpočet štyroch koeficientov. Kusová lineárna funkcia sa tiež správa veľmi dobre pri zjemňovaní siete. • Hlavná nevýhoda prístupu 2-g: aproximačná po častiach lineárna funkcia nie je plynulá: prvé derivácie sú diskontinuálne v uzloch mriežky (interpolačné uši). Prístup 3. Spline interpolácia Navrhované prístupy možno kombinovať tak, aby sa zachoval počet uvedených výhod oboch prístupov a znížil sa počet nevýhod. To je možné dosiahnuť zostrojením funkcie hladkej interpolácie spline stupňa p. Hlavné výhody 3. prístupu: 1) graf zostrojenej funkcie prechádza každým bodom poľa, 2) zostrojená funkcia sa dá pomerne ľahko opísať (počet koeficientov zodpovedajúcich polynómov pre mriežku (1) až byť určený je 3) zostrojená funkcia je jednoznačne určená daným poľom, 4) stupeň polynómov nezávisí od počtu uzlov mriežky, a preto sa nemení, keď sa zväčšuje, 5) zostrojená funkcia má spojité derivácie do poriadku p - 1 vrátane, 6) zostrojená funkcia má dobré aproximačné vlastnosti. Krátka pomoc. Navrhovaný názov - spline - nie je náhodný - nami zavedené plynulé po častiach polynomické funkcie a kreslenie spline úzko súvisia. Zvážte flexibilné, ideálne tenké pravítko prechádzajúce cez podporné body poľa nachádzajúce sa v rovine (x, y). Podľa Bernoulliho-Eulerovho zákona má linearizovaná rovnica zakriveného pravítka tvar, kde S (x) je ohyb, M (x) je ohybový moment, ktorý sa lineárne líši od podpory k podpore, E1 je tuhosť pravítka . Funkcia S (x), popisujúca vzorce priamok, je polynómom tretieho stupňa medzi každým a dvoma susednými bodmi poľa (podpory) a je dvakrát kontinuálne diferencovateľná v celom intervale (a, 6). Komentovať. 06 interpolácia spojitej funkcie Na rozdiel od interpolácie Lagrangeových polynómov sekvencia interpolácie kubických spline na jednotnej mriežke vždy konverguje k interpolovanej spojitej funkcii a so zlepšením diferenciálnych vlastností tejto funkcie sa rýchlosť konvergencie zvyšuje. Príklad. Pre funkciu poskytuje kubický spline na sieti s m \u003d 6 uzlov chybu aproximácie v rovnakom poradí ako interpolačný polynóm Ls (z) a na sieti s uzlami m \u003d 21 je táto chyba taká malá, že na stupnici bežného knižného výkresu to jednoducho nie je možné zobraziť (obr. 10) (interpolačný polynóm 1\u003e 2® (d) dáva v tomto prípade chybu asi 10 000 W). Vlastnosti interpolácie kubický spline A. Vlastnosti aproximácie kubického spline. Aproximačné vlastnosti interpolačného spline závisia od plynulosti funkcie f (x) - čím vyššia je plynulosť interpolovanej funkcie, tým vyšší je aproximačný poriadok a keď je sieť rafinovaná, tým vyššia je miera konvergencie. Ak je interpolovaná funkcia f (x) spojitá na segmente Ak má interpolovaná funkcia f (x) spojitú prvú deriváciu na segmente [a, 6], to znamená interpolačnú spline spĺňajúcu okrajové podmienky 1. alebo 3. hranice typu, potom pre h О máme V tomto prípade nielen spline konverguje k interpolovanej funkcii, ale aj derivácia spline konverguje k derivácii tejto funkcie. Ak spline S (x) aproximuje funkciu f (x) na intervale [a, b] a jej prvá a druhá derivácia sa približujú funkcii B. Extrémna vlastnosť kubického spline. Interpolujúci kubický spline má ďalšiu užitočnú vlastnosť. Uvažujme o nasledujúcom príklade. príklad. Zostrojte funkciu f (x), ktorá minimalizuje funkčnosť na triede funkcií z priestoru C2, ktorého grafy prechádzajú bodmi poľa Medzi všetkými funkciami prechádzajúcimi podpornými bodmi (x;, / (x,)) a príslušnosťou do označeného priestoru, je to kubický spline 5 (x) vyhovujúci okrajovým podmienkam dáva extrém (minimálny) funkčnej poznámke 1. Za definíciu interpolácie kubického spline sa často považuje táto extrémna vlastnosť. Poznámka 2. Je zaujímavé poznamenať, že interpolačná kubická spline má extremálnu vlastnosť popísanú vyššie pri veľmi širokej triede funkcií, konkrétne pri triede | o, 5]. 1.2. Vyhlazovanie kubických splajnov O formulácii problému vyhladenia Nechajte uviesť mriežku a množinu čísel Komentáre k pôvodným údajom V praxi sa často musíme zaoberať prípadom, keď sú hodnoty y v poli dané s nejaká chyba. V skutočnosti to znamená, že pre každý interval je uvedený interval a akékoľvek číslo z tohto intervalu je možné považovať za hodnotu y ,. Hodnoty y je vhodné interpretovať napríklad ako výsledky meraní určitej funkcie y (x) pre dané hodnoty premennej x, ktoré obsahujú náhodnú chybu. Pri riešení problému obnovy funkcie z jej „experimentálnych“ hodnôt je ťažko vhodné použiť interpoláciu, pretože interpolačná funkcia poslušne reprodukuje bizarné oscilácie spôsobené náhodnou zložkou v poli (y,). Prirodzenejší prístup je založený na vyhladzovacom postupe, ktorý je navrhnutý tak, aby v dôsledku meraní nejako zmenšil prvok náhodnosti. Zvyčajne je pri takýchto problémoch potrebné nájsť funkciu, ktorej hodnoty pre x \u003d x, * \u003d 0, 1, .... m by spadali do zodpovedajúcich intervalov a ktorá by navyše mala dostatočne dobré vlastnosti. Napríklad by mal spojitú prvú a druhú deriváciu alebo by jeho graf nebol príliš zakrivený, to znamená, že by nemal silné oscilácie. Problém tohto druhu nastáva aj vtedy, keď sa na základe daného (presne) poľa vyžaduje zostrojenie funkcie, ktorá by prechádzala nešpecifikovanými bodmi a navyše by sa v ich blízkosti celkom plynulo menila. Inými slovami, hľadanou funkciou je skôr vyhladenie daného poľa ako jeho interpolácia. Nechajme uviesť mriežku a dve množiny čísel. TEÓRIA SPLINE. Príklady riešení. Problém. Zostrojte plynulú funkciu na segmente [a, A], ktorého hodnoty sa v uzloch mriežky „líšia od čísel y o dané hodnoty -3shochtio. Formulovaný problém vyhladenia jeprestavba plynulá funkcia uvedená v tabuľke. Je zrejmé, že tento problém má veľa rôznych riešení. Uložením ďalších podmienok na konštruovanú funkciu je možné dosiahnuť potrebnú jednoznačnosť. Definícia vyhladzovacieho kubického spline Vyhladzovací kubický spline S (x) na sieti w je funkcia, ktorá 1) na každom zo segmentov predstavuje polynóm tretieho stupňa, 2) je na segmente dvakrát spojito diferencovateľná [a, 6 ], to znamená, že patrí do triedy C2 [a, B], 3) poskytuje minimum funkcionálu, kde sú dané čísla, 4) spĺňa okrajové podmienky jedného z troch typov uvedených nižšie. Hraničné (hraničné) podmienky Hraničné podmienky sú špecifikované vo forme obmedzení hodnôt spline a jeho derivácií v hraničných uzloch siete w. A. Okrajové podmienky 1. typu. - na koncoch intervalu [a, b) sa nastavia hodnoty prvej derivácie požadovanej funkcie. Okrajové podmienky 2. typu. - druhé derivácie požadovanej funkcie na koncoch intervalu (a, b] sa rovnajú nule. B. Okrajové podmienky tretieho typu sa nazývajú periodické Veta: Kubický spline S (x), ktorý minimalizuje funkčné (4) a spĺňa okrajové podmienky jednej z troch definícií. Kubický spline, ktorý minimalizuje funkčné J (f) a spĺňa hraničné podmienky i-gotypu, sa nazýva vyhladzovací spline i-gotypu. Tento segment má štyri koeficienty. Celkom segmenty - m. Preto, aby sme úplne určili spline, je potrebné nájsť 4m čísla. Podmienkou sa rozumie spojitosť funkcie 5 (a) a všetkých derivácií na všetkých vnútorných uzloch mriežky o ". Počet takýchto uzly sú m - 1. Aby sme teda našli koeficienty všetkých polynómov, získame 3 (m - 1) podmienok (rovníc). Konštrukcia vyhladzovacieho kubického splajna Popíšeme si metódu výpočtu koeficientov kubického spline, pri ktorom je počet veličín, ktoré sa majú určiť, 2m + 2. V každom z intervalov sa hľadá vyhladzovacia spline funkcia v nasledujúcom tvare. Tu sú čísla a sú riešením sústavy lineárnych algebraických rovníc, ktorej forma závisí od typu okrajových podmienok. Najprv popíšme, ako sa nachádzajú množstvá n *. Pre okrajové podmienky 1. a 2. typu je systém lineárnych rovníc na určovanie hodnôt Hi napísaný v nasledujúcom tvare, kde sú známe čísla). Koeficienty závisia od voľby okrajových podmienok. Okrajové podmienky 1. typu: Okrajové podmienky 2. typu: V prípade okrajových podmienok 3. typu je systém stanovenia čísel zapísaný takto: navyše všetky koeficienty sa počítajú podľa vzorcov (5) (veličín s indexmi k a m \u200b\u200b+ k sa považujú za rovnaké: Dôležité * poznámka. Matice systémov nie sú zdegenerované, a preto má každý z týchto systémov jedinečné riešenie. Ak sa nájdu čísla n, -, potom sa hodnoty dajú ľahko určiť pomocou vzorcov, kde V prípade periodických okrajových podmienok Výber jeho koeficientov Výber hmotnostných koeficientov p, - zahrnutých do funkčného (4), umožníte určitú stupňa na kontrolu vlastností vyhladzovacích drážok. Ak sa všetko a vyhladzovacie spline ukážu ako interpolácia. To znamená najmä to, že čím presnejšie sú uvedené hodnoty, tým menšie musia byť zodpovedajúce váhové faktory. Ak je nevyhnutné, aby spline prechádzala bodom (x ^, Vk), potom by sa váhový faktor p1 zodpovedajúci y mal rozdeliť na nulu. Pri praktických výpočtoch je najdôležitejšia voľba hodnôt pi-Let D, je chyba merania hodnoty y,. Potom je prirodzené vyžadovať, aby vyhladzovacie spline vyhovovalo podmienke alebo ekvivalentne. V najjednoduchšom prípade možno uviesť váhové koeficienty pi, napríklad tvar, kde c je nejaká dostatočne malá konštanta. Takáto voľba váh p však neumožňuje použitie „chodby“ z dôvodu chýb v hodnotách y, -. Racionálnejší, ale aj časovo náročnejší algoritmus na určovanie hodnôt p môže vyzerať nasledovne. Ak sa hodnoty nájdu na f-tej iterácii, potom sa predpokladá, že kde e je malé číslo, ktoré sa vyberie experimentálne s prihliadnutím na mriežku počítača, hodnoty D a presnosť riešenia sústava lineárnych algebraických rovníc. Ak je podmienka (6) porušená pri f-tej iterácii v bode i, potom posledný vzorec zabezpečí zníženie zodpovedajúceho hmotnostného koeficientu p,. Ak potom, pri nasledujúcej iterácii, zvýšenie p vedie k úplnejšiemu využitiu „koridoru“ (6) a v konečnom dôsledku k plynulejšie sa meniacemu spline. Niektorá teória A. Zdôvodnenie vzorcov na výpočet koeficientov interpolačnej kubickej spline. Uveďme zápis, kde m sú stále neznáme veličiny. Ich počet sa rovná m + 1. Splajn, napísaný vo forme, kde spĺňa interpolačné podmienky a je spojitý v celom intervale [a, b \\: uvedenie do vzorca, dostaneme podľa toho. Navyše má spojitá prvá derivácia na intervale [a, 6]: Diferenciačný vzťah (7) a nastavenie, získame zodpovedajúci. prirodzene. Ukážme, že čísla m je možné zvoliť tak, aby spline funkcia (7) mala na segmente [a, 6] spojitú druhú deriváciu. Vypočítajme druhú deriváciu spline na intervale: V bode х, - 0 (pri t \u003d 1) máme Vypočítajte druhú deriváciu spline v bode Máme z podmienky spojitosti druhej derivácie na vnútorné uzly mriežky a; získame vzťah m - 1, kde Pridaním ďalších dvoch rovníc k týmto rovniciam m - 1, ktoré vyplývajú z okrajových podmienok, získame sústavu m + 1 lineárnych algebraických rovníc s m + I neznámy miy i \u003d 0, 1. ..., m. Sústava rovníc na výpočet hodnôt rn v prípade okrajových podmienok 1. a 2. typu má tvar kde (okrajové podmienky 1. typu), (okrajové podmienky 2. typu). Pre periodické okrajové podmienky (okrajové podmienky 3. typu) je mriežka o; predĺžiť o ďalší uzol a predpokladať, že potom bude mať systém na určovanie veličín go * tvar. Aby sme získali sústavu rovníc na určovanie počtu go, v prípade okrajových podmienok typu 4 nájdeme na segmente [the tretia derivácia spline (7) a vyžaduje sa jej spojitosť v druhom a (th -!) - tom uzle mriežky. Máme Z posledných dvoch vzťahov dostaneme chýbajúce dve rovnice zodpovedajúce okrajovým podmienkam 4. typu: Eliminácia neznámeho r0 z rovníc a neznámeho np z rovníc, vďaka čomu získame sústavu rovníc. Všimnite si, že počet neznámych v tomto systéme sa rovná i - I. 6. Zdôvodnenie vzorcov dm na výpočet ueffiye, ktorý „vyhladzuje spicitu subicess. Uveďme zápis, kde Zi a nj sú stále neznáme veličiny. Ich počet sa rovná 2m + 2. Funkcia spline napísaná vo forme je spojitá po celý interval (a, 6]: vložením do tohto vzorca získame respektíve. Ukážeme, že je možné zvoliť čísla z a n aby spline napísaná vo forme (8) mala spojitú prvú deriváciu na intervale [a, 6] Vypočítajte prvú deriváciu spline S (x) na intervale: V bode x ^ - 0 (pre t \u003d 1) máme Vypočítajte prvú deriváciu spline 5 (x) na intervale: V bode máme Z podmienky spojitosti prvej derivácie spline na vnútorných uzloch mriežky a -\u003e získame m - 1 vzťah Je vhodné tento vzťah zapisovať do maticového tvaru Tu sa používa nasledujúca notácia. Splajn na intervale [a, 6) má navyše spojitú druhú deriváciu: diferenciačný vzťah (8) a nastavenie, získame , respektíve Echool, vzťah matice sa získa z podmienky minimálnej funkčnosti (4). Máme Posledné dve maticové ekvity môžeme považovať za lineárny systém 2m + 2 lineárnych algebraických rovníc pre 2m + 2 neznáme. Nahradením stĺpca r v prvej rovnosti jeho výrazom získaným z vzťahu (9) sa dostaneme k maticovej rovnici SPLINE TEORY Príklady riešení pre určenie stĺpca M. Táto rovnica má jedinečné riešenie vďaka tomu, že matica A + 6HRH7 je vždy nedegenerovaný. Nájdite to, pána Eamshine ľahko identifikujeme. Prvky trillmagallovej matice A a H, ktoré určujú i iba parametrami mriežky a (c s krokmi hi) a nezávisia od hodnôt y ^. Lineárny priestor kubických spline funkcií Množina kubických splajnov vytvorených na segmente [a, 6) pozdĺž siete wcra + l uzlom je lineárny priestor dimenzie m + 3: 1) súčet dvoch kubických splajnov vytvorených na mesh u\u003e a produkt kubického spline, postavený na mriežke u\u003e, sú tajne kubické splajny postavené na tejto mriežke ľubovoľným počtom, 2) akýkoľvek kubický spline postavený na mriežke a z uzla je úplne určený znakom m + 1 hodnota y v týchto uzloch a dve okrajové podmienky - iba + 3 parametre. Ak v tomto priestore vyberieme základňu pozostávajúcu z m + 3 lineárne nezávislých spline, môžeme jedinečným spôsobom napísať ľubovoľný kubický spline a (x) vo forme ich lineárnej kombinácie. Komentovať. Táto spline špecifikácia je rozšírená vo výpočtovej praxi. Obzvlášť výhodná je základná čiara pozostávajúca z takzvaných kubických B-čiar (základná alebo základná, spline). Použitie D-splines môže významne znížiť požiadavky na množstvo pamäte počítača. L-drážky. V -spline nulového stupňa, postavenej na číselnej čiare pozdĺž mriežky w, sa nazýva funkcia B-spline stupňa k ^ I, postavenej na číselnej čiare na mriežke u, je určená rekurzívnym vzorcom grafy B-spline prvého B, -1 "(x) a druhého v \\ 7 \\ x) stupňoch sú zobrazené na obr. 11 a 12. B-spline ľubovoľného stupňa k môže byť nenulová iba na nejaký segment (definovaný k + 2 uzlami). Je pohodlnejšie očíslovať kubické B-splajny tak, aby spline B, -3 * (z) bola na segmente m, - + 2 nenulová. Dávame vzorec pre kubický spline tretieho stupňa pre prípad rovnomernej siete (s krokom A). Máme to v iných prípadoch. Typický graf kubického B-spline je uvedený na obr. 13. Pri výpožičkách *. a) je dvakrát spojito diferencovateľné na intervale, to znamená, že patrí do triedy C2 [a, "), a b) je nenulové iba na štyroch po sebe nasledujúcich segmentoch (mriežku w dopĺňame pomocnými uzlami branými celkom ľubovoľne. rozšírená sieť sh * mo Je potrebné skonštruovať rodinu m + 3 kubických B-plôch: Táto rodina tvorí základ v priestore kubických spline na segmente (a, b]. Teda ľubovoľný kubický spline S (z) zostrojený na segmente | в, 6] návštevník o; uzla m + 1, možno na tomto segmente znázorniť ako lineárnu kombináciu. Podľa podmienok problému sú koeficienty ft tejto expanzie jednoznačne určené. ... V prípade, že sú uvedené hodnoty funkcie y * v uzloch mriežky a hodnoty yo a Yt prvej derivácie funkcie na koncoch mriežky (problém interpolácie s hranicou podmienky prvého druhu), tieto koeficienty sa počítajú zo systému nasledujúceho tvaru Po eliminácii množstvá b-i a & m + i sa získa lineárny systém s neznámymi 5q, ..., bm a tri-diajunálnou maticou. Podmienka poskytuje diagonálnu dominanciu, a teda možnosť použiť metódu rozmetania na jej vyriešenie. 3ММЧМЮ 1. Lineárne systémy podobnej formy vznikajú pri uvažovaní o ďalších interpolačných problémoch. Zmmchnm * 2. V porovnaní s algoritmami opísanými v časti 1.1 môže použitie R-spline v * interpolačných problémoch znížiť * množstvo uložených informácií, to znamená podstatne znížiť požiadavky na množstvo pamäte počítača, hoci vedie k zvýšeniu počtu operácií. Konštrukcia spline kriviek pomocou funkcií spline Vyššie uvedené polia, ktorých body boli očíslované tak, aby ich úsečky tvorili striktne rastúcu postupnosť. Napríklad prípad znázornený na obr. 14, keď rôzne body poľa majú rovnaké úsečky, nebol povolený. Táto okolnosť určovala jednak výber triedy aproximačných kriviek (prenos funkcií), jednak spôsob ich konštrukcie. Vyššie navrhnutá metóda však umožňuje celkom úspešne zostrojiť interpolačnú krivku vo všeobecnejších prípadoch, keď číslovanie bodov poľa a ich umiestnenie v rovine spravidla nie sú spojené (obr. 15). Navyše, s nastavením problému zostrojenia interpolačnej krivky možno dané pole považovať za nerovinné m, to znamená, že je zrejmé, že na vyriešenie tohto všeobecného problému je potrebné výrazne rozšíriť triedu prípustných kriviek vrátane uzavretých kriviek, a krivky so samočinnými priesečníkmi a priestorové krivky. Takéto krivky je vhodné opísať pomocou parametrických rovníc. navyše, aby mali funkcie dostatočnú plynulosť, aby napríklad patrili do triedy C1 [a, / 0] alebo do triedy. Ak chcete nájsť parametrické rovnice krivky postupne prechádzajúcej všetkými bodmi poľa, postupujte takto . 1. krok. V ľubovoľnom segmente)