Odoslanie dobrej práce do databázy znalostí je jednoduché. Použite nižšie uvedený formulár
Študenti, postgraduálni študenti, mladí vedci, ktorí pri štúdiu a práci využívajú vedomostnú základňu, vám budú veľmi vďační.
Uverejnené dňa http://www.allbest.ru/
Moskovská štátna univerzita prístrojového inžinierstva a informatiky Pobočka Sergieva Posada
Abstrakt na tému:
Newtonove interpolačné vzorce
Doplnil: Brevchik Taisiya Yurievna
Študent 2. ročníka skupiny EF-2
1. Úvod
2. Newtonov prvý interpolačný vzorec
3. Newtonov druhý interpolačný vzorec
Záver
Bibliografia
Úvod
Interpolácia, interpolácia - vo výpočtovej matematike metóda hľadania medziľahlých hodnôt množstva z existujúcej diskrétnej množiny známych hodnôt.
Mnohí z tých, ktorí sa zaoberajú vedeckými a inžinierskymi výpočtami, musia často pracovať so súbormi hodnôt získaných empiricky alebo náhodným výberom vzoriek. Na základe týchto množín je spravidla potrebné zostrojiť funkciu, do ktorej by mohli s vysokou presnosťou spadať ďalšie získané hodnoty. Tento problém sa nazýva aproximácia. Interpolácia je typ aproximácie, pri ktorej krivka zostrojenej funkcie prechádza presne cez dostupné dátové body.
Interpolácii je blízka aj úloha, ktorá spočíva v aproximácii komplexnej funkcie inou, jednoduchšou funkciou. Ak je určitá funkcia príliš zložitá na produktívne výpočty, môžete skúsiť vypočítať jej hodnotu vo viacerých bodoch a z nich zostaviť, teda interpolovať, jednoduchšiu funkciu.
Samozrejme, že použitie zjednodušenej funkcie neprinesie také presné výsledky ako pôvodná funkcia. Ale v niektorých triedach problémov môže dosiahnutý zisk v jednoduchosti a rýchlosti výpočtov prevážiť výslednú chybu vo výsledkoch.
Za zmienku stojí aj úplne iný typ matematickej interpolácie známy ako operátorová interpolácia.
Klasické práce o interpolácii operátorov zahŕňajú Riesz-Thorinov teorém a Marcinkiewiczov teorém, ktoré sú základom pre mnohé ďalšie práce.
Uvažujme systém nezhodných bodov () z určitého regiónu. Nech sú funkčné hodnoty známe iba v týchto bodoch:
Problémom interpolácie je nájsť funkciu z danej triedy funkcií takú, že
Body sa nazývajú interpolačné uzly a ich súbor sa nazýva interpolačná mriežka.
Páry sa nazývajú dátové body alebo základné body.
Rozdiel medzi „susednými“ hodnotami je krok interpolačnej mriežky. Môže byť variabilný alebo konštantný.
Funkcia je interpolačná funkcia alebo interpolant.
1. Newtonov prvý interpolačný vzorec
1. Popis úlohy. Nech funkcia dostane hodnoty pre rovnomerne rozložené hodnoty nezávislej premennej: , kde - interpolačný krok. Je potrebné zvoliť polynóm stupňa nie vyššieho, pričom v bodoch berieme hodnoty
Podmienky (1) sú ekvivalentné podmienkam v.
Newtonov interpolačný polynóm má tvar:
Je ľahké vidieť, že polynóm (2) plne spĺňa požiadavky problému. Po prvé, stupeň polynómu nie je vyšší a po druhé,
Všimnite si, že keď sa vzorec (2) zmení na Taylorov rad pre funkciu:
Pre praktické použitie sa Newtonov interpolačný vzorec (2) zvyčajne píše v mierne transformovanej forme. Na tento účel zavedieme novú premennú pomocou vzorca; potom dostaneme:
kde predstavuje počet krokov, potrebné na dosiahnutie bodu, začínajúc od bodu. Toto je konečný vzhľad Newtonov interpolačný vzorec.
Na interpoláciu funkcie je výhodné použiť vzorec (3). v blízkosti počiatočnej hodnoty , kde je malá v absolútnej hodnote.
Ak je uvedená neobmedzená tabuľka funkčných hodnôt, potom číslo v interpolačnom vzorci (3) môže byť ľubovoľné. V praxi sa v tomto prípade číslo volí tak, aby bol rozdiel s daným stupňom presnosti konštantný. Ako počiatočnú hodnotu možno považovať akúkoľvek tabuľkovú hodnotu argumentu.
Ak je tabuľka funkčných hodnôt konečná, potom je počet obmedzený, a to: nemôže byť viac ako počet funkčných hodnôt znížených o jednu.
Všimnite si, že pri použití prvého Newtonovho interpolačného vzorca je vhodné použiť horizontálnu tabuľku rozdielov, pretože potom sú požadované hodnoty rozdielov funkcie v zodpovedajúcom horizontálnom riadku tabuľky.
2. Príklad. V tomto kroku zostrojte Newtonov interpolačný polynóm pre funkciu danú tabuľkou
Výsledný polynóm umožňuje predpovedať. Dostatočnú presnosť získame pri riešení interpolačnej úlohy, napr., presnosť klesá pri riešení extrapolačnej úlohy, napr.
2. Newtonov druhý interpolačný vzorec
Newtonov prvý interpolačný vzorec je prakticky nepohodlný na interpoláciu funkcie v blízkosti uzlov tabuľky. V tomto prípade sa zvyčajne používa .
Popis úlohy . Majme postupnosť funkčných hodnôt
pre ekvidistantné hodnoty argumentov, kde je interpolačný krok. Zostavme polynóm nasledujúceho tvaru:
alebo pomocou zovšeobecnenej sily dostaneme:
Potom, ak platí rovnosť, dostaneme
Nahraďte tieto hodnoty do vzorca (1). Potom, konečne, Newtonov druhý interpolačný vzorec má tvar:
Uveďme si pohodlnejší zápis pre vzorec (2). Nech je to potom
Nahradením týchto hodnôt do vzorca (2) dostaneme:
Toto je bežný pohľad Newtonov druhý interpolačný vzorec. Na približný výpočet funkčných hodnôt predpokladajme:
Newtonov prvý aj druhý interpolačný vzorec možno použiť na extrapoláciu funkcie, to znamená na nájdenie funkčných hodnôt pre hodnoty argumentov mimo tabuľky.
Ak je blízko, potom je výhodné použiť prvý Newtonov interpolačný vzorec a potom. Ak je to blízko, potom je navyše pohodlnejšie použiť druhý Newtonov interpolačný vzorec.
Preto sa zvyčajne používa prvý Newtonov interpolačný vzorec dopredná interpolácia A extrapolácia dozadu, a Newtonov druhý interpolačný vzorec, naopak, pre interpolácia dozadu A dopredná extrapolácia.
Všimnite si, že operácia extrapolácie je vo všeobecnosti menej presná ako operácia interpolácie v užšom zmysle slova.
Príklad. V tomto kroku zostrojte Newtonov interpolačný polynóm pre funkciu danú tabuľkou
Záver
interpolácia newton extrapolačný vzorec
Vo výpočtovej matematike hrá významnú úlohu interpolácia funkcií, t.j. Pomocou danej funkcie zostrojenie inej (zvyčajne jednoduchšej) funkcie, ktorej hodnoty sa zhodujú s hodnotami danej funkcie v určitom počte bodov. Okrem toho má interpolácia praktický aj teoretický význam. V praxi často vzniká problém rekonštruovať spojitú funkciu z jej tabuľkových hodnôt, získaných napríklad počas nejakého experimentu. Na vyhodnotenie mnohých funkcií 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 na riešenie diferenciálnych a integrálnych rovníc.
Bibliografia
1. V.V. Ivanov. Počítačové metódy výpočtu. Referenčný manuál. Vydavateľstvo "Naukova Dumka". Kyjev. 1986.
2. N.S. Bakhvalov, N.P. Zhidkov, G.M. Kobelkov. Numerické metódy. Vydavateľstvo "Laboratórium základných vedomostí". 2003.
3. I.S. Berezin, N.P. Židkov. Metódy výpočtu. Ed. PhysMatLit. Moskva. 1962.
4. K. De Bor. Praktický sprievodca drážkami. Vydavateľstvo "Rádio a komunikácie". Moskva. 1985.
5. J. Forsyth, M. Malcolm, K. Mowler. Strojové metódy matematických výpočtov. Vydavateľstvo "Mir". Moskva. 1980.
Uverejnené na Allbest.ru
...Podobné dokumenty
Aplikácia Newtonovho prvého a druhého interpolačného vzorca. Hľadanie funkčných hodnôt v bodoch, ktoré nie sú tabuľkové. Použitie Newtonovho vzorca pre nerovnaké body. Nájdenie hodnoty funkcie pomocou Aitkenovej interpolačnej schémy.
laboratórne práce, doplnené 14.10.2013
Johann Carl Friedrich Gauss je najväčší matematik všetkých čias. Gaussove interpolačné vzorce, ktoré dávajú približné vyjadrenie funkcie y=f(x) pomocou interpolácie. Oblasti použitia Gaussových vzorcov. Hlavné nevýhody Newtonových interpolačných vzorcov.
test, pridaný 12.06.2014
Interpolácia funkcie v bode ležiacom v blízkosti stredu intervalu. Gaussove interpolačné vzorce. Stirlingov vzorec ako aritmetický priemer Gaussových interpolačných vzorcov. Kubický spline funguje ako matematický model tenkej tyče.
prezentácia, pridané 18.04.2013
Priebežná a bodová aproximácia. Lagrangeove a Newtonove interpolačné polynómy. Globálna interpolačná chyba, kvadratická závislosť. Metóda najmenších štvorcov. Výber empirických vzorcov. Po častiach konštantná a po častiach lineárna interpolácia.
kurzová práca, pridané 14.03.2014
Metódy akordov a iterácií, Newtonovo pravidlo. Interpolačné vzorce Lagrangea, Newtona a Hermita. Bodová kvadratická aproximácia funkcie. Numerická diferenciácia a integrácia. Numerické riešenie obyčajných diferenciálnych rovníc.
priebeh prednášok, pridané 2.11.2012
Interpolácia pomocou Newtonovho polynómu. Spresnenie hodnoty odmocniny na danom intervale v troch iteráciách a nájdenie chyby výpočtu. Aplikácia Newtonových, Sampsonových a Eulerových metód pri riešení problémov. Výpočet derivácie funkcie.
test, pridané 06.02.2011
Vo výpočtovej matematike hrá významnú úlohu interpolácia funkcií. Lagrangeov vzorec. Interpolácia podľa Aitkenovej schémy. Newtonove interpolačné vzorce pre ekvidistantné uzly. Newtonov vzorec s delenými rozdielmi. Spline interpolácia.
test, pridané 01.05.2011
Výpočet derivácie podľa jej definície, s použitím konečných rozdielov a na základe prvého Newtonovho interpolačného vzorca. Lagrangeove interpolačné polynómy a ich aplikácia pri numerickej diferenciácii. Metóda Runge-Kutta (štvrtého rádu).
abstrakt, pridaný 03.06.2011
Konce rôznych objednávok. Vzťah medzi terminálovými rozdielmi a funkciami. Diskrétna a kontinuálna analýza. Pochopenie rozdelenia. Newtonov interpolačný vzorec. Aktualizácia Lagrangeových a Newtonových vzorcov. Interpolácia pre rovnako vzdialené uzly.
test, pridané 02.06.2014
Nájdenie Lagrangeových a Newtonových interpolačných polynómov prechádzajúcich štyrmi bodmi danej funkcie, porovnanie ich mocninových reprezentácií. Riešenie nelineárnej diferenciálnej rovnice pomocou Eulerovej metódy. Riešenie sústav algebraických rovníc.
Prednáška 4
1. Konečné rozdiely2. Prvý interpolačný vzorec
Newton
3. Druhý interpolačný vzorec
Newton
4. Interpolačné chyby
Konečné rozdiely 1. rádu
Ak je interpolovaná funkcia y = f(x) daná vrovnako vzdialené uzly, takže xi = x0 + i∙h, kde h je krok tabuľky a
i = 0, 1, … n, potom sa vzorce môžu použiť na interpoláciu
Newton pomocou konečných rozdielov.
Konečný rozdiel prvého rádu je rozdiel yi
= yi+1 - yi, kde
yi+1= f(xi+h) a yi = f(xi). Pre danú funkciu
tabuľkové v (n+1) uzloch, i = 0, 1, 2, …, n, konečné rozdiely
prvé poradie možno vypočítať v bodoch 0, 1, 2,…, n - 1:
r 0 y1 r 0 ,
y1 y 2 y1,
.......................
yn 1 yn yn 1.
Konečné rozdiely vyšších rádov
Pomocou konečných rozdielov prvého rádu je to možnézískajte konečné rozdiely druhého rádu 2yi = yi+1 - yi:
2 y 0 y1 y 0;
2y1y2y1;
..........................
2 r n 2 r n 1 r n 2.
Konečné rozdiely k-tého rádu pri čísle uzla môžem
vypočíta sa prostredníctvom rozdielov (k-1) rádu:
k yi k 1yi 1 k 1yi
Akékoľvek konečné rozdiely možno vypočítať prostredníctvom hodnôt
funkcie v interpolačných uzloch, napríklad:
2 y 0 y1 y 0 (y 2 y1) (y1 y 0) y 2 2 y1 y 0 .
Tabuľka konečných rozdielov
Xr
Δy
Δ2y
Δ3y
x0
y0 Δy0 = y1 – y0 Δ2y0 = Δy1 – Δy0 Δ3y0 = Δ2y1 – Δ2y0
x1 = x0 + h
y1 Δy1 = y2 – y1 Δ2y1 = Δy2 – Δy1
x2 = x0 + 2h
y2 Δy2 = y3 – y2
x3 = x0 + 3h
y3
Na základe veľkosti konečných rozdielov možno
robiť
záver
O
stupňa
interpolácia
polynóm,
popisujúce
tabuľkový
daný
funkciu.
Ak
Pre
tabuľky
s
v rovnakej vzdialenosti
uzly
Konečný
rozdiely k-tého rádu sú konštantné resp
sú úmerné danej chybe
funkcia môže byť reprezentovaná ako polynóm
k-tý stupeň.
Konečné rozdiely a stupeň polynómu
Zoberme si napríklad tabuľku konečných rozdielov prepolynóm y = x2 – 3x + 2.
0
r
-0.16
2r
0.08
3r
0
1.2
-0.16
-0.08
0.08
0
1.4
-0.24
0
0.08
1.6
-0.24
0.08
1.8
-0.16
X
r
1.0
Konečné rozdiely tretieho rádu sa rovnajú nule a všetky
konečné rozdiely druhého rádu sú rovnaké a rovnajú sa 0,08. Toto
hovorí, že funkcia uvedená v tabuľke môže byť
reprezentovať to ako polynóm 2. stupňa (očakávaný výsledok,
vzhľadom na spôsob získania tabuľky).
Nech je funkcia y = f(x) špecifikovaná v n+1 rovnako vzdialených uzloch xi , i = 0, 1,
2,…n s krokom h. Potrebujeme nájsť interpolačný polynóm Pn(x)
stupeň n, spĺňajúci podmienku:
Pn(xi) = yi, i = 0, 1, 2, ..., n .
Budeme hľadať interpolačný polynóm v tvare:
Pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + ... + an(x-x0)(x-x1)...(x-xn-1),
kde аi, i = 0, 1, 2,…n – neznáme koeficienty nezávislé od uzlov
interpolácia. Nájdite tieto koeficienty z interpolačných podmienok.
Nech x = x0, potom Pn(x0) = y0 = a0. Preto a0 = y0.
Nech x = x1, potom Pn(x1) = y1 = a0 + a1(x1 - x0) = y0 + a1(x1 - x0), odkiaľ
a1
y1 y0 y0
.
x1 x 0
h
Teraz nech x = x2, potom:
Pn (x 2) y 2 a0 a1 (x 2 - x 0) a2 (x 2 - x 0) (x 2 - x 1) y 0
y 0
2h a2 2h2.
h
Vyjadrením a2 z tohto výrazu dostaneme:
r 2 2 r. r. 2 2 (r. 1 r. 0) r. r. 2 2 r. 1 r. 0 2 r. 0
a2
.
2h2
2h2
2h2
2h2
Newtonov prvý interpolačný vzorec
Pokračujúc v substitúciách môžeme získať výraz pre ľubovoľnékoeficient s číslom i:
ja y 0
ai
,
ja! Ahoj
i 0,1,...,n.
Nahradením nájdených hodnôt koeficientov do pôvodného výrazu,
dostaneme prvý Newtonov interpolačný vzorec:
y0
2 roky0
n y 0
Pn(x)y0
(x x 0)
(x x 0) (x x1) ...
(x x 0)... (x x n 1).
1! h
2!h2
n!hn
Vzorec ukazuje, že používa horný riadok tabuľky
konečné rozdiely (snímka 4). Zvláštnosťou vzorca je tiež
postupné zvyšovanie stupňa polynómu pri jeho pridávaní
ďalšie termíny. To vám umožní spresniť výsledok získaný bez
prepočet už zohľadnených termínov.
Newtonov prvý interpolačný vzorec
Je možné zapísať prvý Newtonov interpolačný vzorecv kompaktnejšej a pohodlnejšej forme na implementáciu softvéru.
Po určení
q
x x 0
,
h
x x 0 qh
a vykonávanie jednoduchých transformácií formulára:
x x 1 x x 0 h
q 1;
h
h
x xn
x x2
qn 1,
q 2;......;
h
h
dostaneme prvý Newtonov interpolačný vzorec, vyjadrený
relatívne k neznámemu q:
n y 0
2 roky0
q(q 1)...(q n 1).
q(q 1) ...
Pn (x) Pn (x0 hq) y0 y0q
n!
2!
10. Newtonov prvý interpolačný vzorec
Vo vzorci sa používajú konečné rozdiely vyšších rádovNewton, zvyčajne majú veľkú chybu spojenú s chybami
zaokrúhľovanie pri odčítaní blízkych hodnôt. Preto zodpovedajúce
výrazy vzorca majú tiež veľkú chybu. Na zníženie
ich príspevok k sume, teda ku konečnému výsledku, musí byť splnený
podmienka |q|< 1. Это обеспечивается, если точка интерполяции x находится
medzi prvými dvoma uzlami tabuľky: x0< x < x1. По этой причине
sa nazýva interpolácia pomocou prvého Newtonovho vzorca
interpolácia na začiatku tabuľky alebo dopredná interpolácia.
interpolácia Prvý Newtonov interpolačný vzorec trvá
nasledujúci formulár:
P1(x) y0 y0q.
P2 (x) y 0 y 0 q 2 y 0
q(q 1)
.
2
11. Príklad použitia prvého Newtonovho interpolačného vzorca
ako v príklade na snímke 6. Musíte nájsť približnú hodnotu
hodnota funkcie v bode x = 1,1 podľa kvadrat
interpolácia pomocou prvého Newtonovho vzorca.
X
1.0
1.2
1.4
1.6
1.8
r
0
-0.16
-0.24
-0.24
-0.16
r
-0.16
-0.08
0
0.08
2r 3r
0.08 0
0.08 0
0.08
Tabuľkový krok h = 0,2
q = (x – x0)/h = 0,5
q(q 1)
2
0.5(0.5 1)
0 (0.16) 0.5 0.08
0.09
2
P2 (x) y 0 Δy 0 q Δ 2 y 0
Výsledok zodpovedá
hodnotu polynómu
y = x2 – 3x + 2, z čoho
tabuľka prijatá
12. Schéma výpočtového algoritmu s použitím prvého Newtonovho interpolačného vzorca
13. Newtonov druhý interpolačný vzorec
Podobné vlastnosti má aj druhý Newtonov vzorecvzhľadom na pravú stranu stola. Na jej vybudovanie použite
polynóm v tvare:
Pn(x) = a0 + a1(x-xn) + a2(x-xn)(x-xn-1) + … + an(x-xn)(x-xn-1)…(x-x1),
kde аi, i = 0, 1, 2, … n sú koeficienty, ktoré nezávisia od interpolačných uzlov.
Na určenie koeficientov ai použijeme tento výraz jeden po druhom
náhradné interpolačné uzly. Preto pre x = xn Pn(xn) = yn,
a0 = yn.
Pre x = xn-1 máme Pn(xn-1) = yn-1 = a0 + a1 (xn-1-xn) = yn + a1 (xn-1-xn),
kde
a1
yn 1 yn yn 1. yn 1
.
xn 1 xn xn xn 1
h
14. Newtonov druhý interpolačný vzorec
Pokračujúc v substitúciách získame výrazy pre všetky koeficientypolynóm a Newtonov druhý interpolačný vzorec:
n y 0
yn 1
2yn 2
Pn(x)yn
(x xn)
(x xn) (x xn 1)
(x xn)...(x x1).
2
n
1! h
2! h
n!h
Vzorec ukazuje, že používa spodnú uhlopriečku tabuľky
konečné rozdiely (snímka 4). Ako v prvom Newtonovom vzorci, pridávanie
po sebe idúce obdobia vedie k konzistentnému zvyšovaniu stupňa
polynóm, ktorý umožňuje objasniť výsledok bez prepočítavania
zohľadnené podmienky.
Zadaním notového zápisu: q
x xn
,
h
x xn hq
a po vykonaní jednoduchých transformácií získame druhú interpoláciu
Newtonov vzorec vyjadrený vzhľadom na substitučnú premennú q:
n y 0
2yn 2
Pn (x) yn yn 1q
q(q 1) ...
q(q 1)...(q n 1).
2!
n!
15. Newtonov druhý interpolačný vzorec
Z rovnakých úvah ako v prípade prvého Newtonovho vzorca, preNa zníženie výpočtovej chyby je potrebné, aby bola splnená podmienka
|q|< 1. Это обеспечивается, если точка интерполяции x находится между
posledné dva uzly tabuľky: xn-1< x < xn. По этой причине
sa nazýva interpolácia pomocou druhého Newtonovho vzorca
interpolácia od konca tabuľky alebo spätná interpolácia.
Pre špeciálne prípady lineárneho (n=1) a kvadratického (n=2)
interpolácia Druhý Newtonov interpolačný vzorec trvá
nasledujúci formulár:
P1 (x) y n y n 1q
2 roky n 2
P2 (x) y n y n 1 q
q(q 1)
2!
16. Príklad použitia Newtonovho druhého interpolačného vzorca
Nech je interpolovaná funkcia f(x) daná tou istou tabuľkou,ako v príklade na snímke 11. Musíte nájsť približnú hodnotu
hodnota funkcie v bode x = 1,7 podľa kvadrat
interpolácia pomocou druhého Newtonovho vzorca.
X
1.0
1.2
1.4
1.6
1.8
r
0
-0.16
-0.24
-0.24
-0.16
r
-0.16
-0.08
0
0.08
2r 3r
0.08 0
0.08 0
0.08
Tabuľkový krok h = 0,2
q = (x – xn)/h = -0,5
Výsledok zodpovedá
hodnotu polynómu
y = x2 – 3x + 2, od
ktorý bol prijatý
tabuľky
q(q 1)
2
0.5(0.5 1)
0.16 0.08 (0.5) 0.08
0.21
2
P2 (x) y n Δy n 1 q Δ 2 y n 2
17. Schéma výpočtového algoritmu s použitím Newtonovho druhého interpolačného vzorca
18. Interpolačné chyby
Interpolačná funkcia v bodoch medziinterpolačné uzly nahrádzajú interpoláciu
funkcia približne:
f(x) = F(x) + R(x), kde R(x) je chyba
interpolácia.
Na odhadnutie chyby je potrebné mať
je potrebné mať určité informácie o
interpolovaná funkcia f(x). Predstierajme to
f(x) je definovaný na segmente, ktorý obsahuje všetky
uzly xi a pre x patriace do , má všetky
deriváty f"(x), f""(x), … f(n+1)(x) až (n+1)
vrátane objednávky.
19. Interpolačné chyby
Potom20. Výber interpolačných uzlov pomocou Lagrangeovho vzorca
Pre pevný stupeň polynómu:X*
x0
x1
x2
x3
x4
x5
X
S postupným zvyšovaním stupňa
polynóm
X*
x4
x2
x0
x1
x3
x5
X
21. Praktické posúdenie chyby interpolácie pomocou Lagrangeovho vzorca
V praxi sa odhaduje maximálna hodnota derivácie (n+1)-tejrád Mn+1 je pri použití Lagrangeovho vzorca zriedka možný,
a preto použite približný odhad chyby
Rn (x) f(x) Ln (x) Ln 1 (x) Ln (x),
kde n je počet použitých uzlov.
Z vyššie uvedeného vzorca vyplýva, že na odhad chyby
je potrebná interpolácia s Lagrangeovým polynómom n-tého stupňa
dodatočne vypočítajte hodnotu polynómu (n+1) stupňa. Ak
je daná prípustná chyba interpolácie, potom je potrebné pripočítať všetky
nové uzly, zvýšte stupeň polynómu až po modul
rozdiel medzi poslednými dvoma hodnotami polynómu |Ln+1(x)-Ln(x)| nie
bude nižšia ako špecifikovaná hodnota.
22. Schéma interpolačného algoritmu s použitím Lagrangeovho vzorca s danou presnosťou
23. Odhad chýb Newtonových interpolačných vzorcov
Pre interpoláciuprijať nasledujúci formulár.
Newtonov prvý vzorec:
Rn(x)h
n 1
vzorce
Newton
hodnotenia
q(q 1) (q n) (n 1)
f
(n 1)!
R n (x) h n 1
q(q 1) (q n)
M n 1
(n 1)!
Newtonov 2. vzorec:
Rn(x)h
n 1
q(q 1) (q n) (n 1)
f
(n 1)!
R n (x) h n 1
q(q 1) (q n)
M n 1
(n 1)!
chyby
24. Praktické hodnotenie chýb v Newtonových interpolačných vzorcoch
Pri použití Newtonových interpolačných vzorcov hodnotaf(n+1)(ξ) možno približne odhadnúť z hodnôt konečných rozdielov:
f
(n 1)
n 1
Δy0
() n 1
h
a v tomto prípade majú vzorce na odhad chyby nasledujúce
vyhliadka:
Newtonov prvý vzorec:
Rn(x)
q(q 1) (q n) n 1
Δy0
(n 1)!
Newtonov 2. vzorec:
Rn(x)
q(q 1) (q n) n 1
Δy0
(n 1)!
25. Interpolácia pomocou Newtonových vzorcov s danou presnosťou
Porovnanie týchto vzorcov so vzorcamiNewton, dá sa to odhadnúť
chyby pri interpolácii s polynómom
n-tý stupeň musíte vziať ďalší uzol
a vypočítajte člen (n+1)-tého stupňa.
Ak je uvedená povolená chyba
interpoláciu ε, potom je potrebné sekvenčne
pridať nové uzly a podľa toho
nové pojmy, zvýšenie stupňa
interpolačný polynóm až
kým ďalší člen nebude menší ako ε.
anotácia
Vysvetlivka k predmetovej práci „Interpolácia funkcie jednej premennej Newtonovou metódou“ obsahuje úvod, rozbor úlohy s popisom vstupných a výstupných údajov, prehľad literárnych zdrojov, popis matematického modelu a metód. výpočtovej matematiky, vysvetlenie algoritmu, text programu a inštrukcie. Pri štúdiu odboru "Informatika" boli na napísanie seminárnej práce použité rôzne literárne zdroje, ktoré sú uvedené v tomto dokumente. Táto práca v kurze poskytuje program, ktorý sa používa na interpoláciu funkcie špecifikovanej v tabuľke pomocou Newtonovej metódy. Použila metódu štruktúrovaného programovania na uľahčenie písania a ladenia programu, ako aj na zlepšenie jeho prehľadnosti a čitateľnosti. Účelom písania tejto práce bolo získať a upevniť praktické zručnosti pri vývoji algoritmov pomocou rôznych metód. Prezentovaný program je implementovaný v programovacom jazyku Pascal. Vysvetlivka obsahuje 25 listov, ktoré obsahujú dva výkresy, text programu a popis programu a algoritmu.
Úvod
Analýza práce
Matematický model problému
Programovanie funkcie Newtonovho vzorca
Prehľad literárnych zdrojov
Vývoj programu podľa schémy algoritmu
Pokyny na používanie programu
Text programu
Počiatočné údaje a výsledok riešenia testovacieho prípadu
Záver
Zoznam použitých zdrojov
Úvod
Moderný rozvoj fyziky a techniky úzko súvisí s využívaním elektronických počítačov (počítačov). V súčasnosti sa počítače stali bežnou výbavou mnohých ústavov a dizajnérskych kancelárií. To nám umožnilo prejsť od najjednoduchších výpočtov a hodnotení rôznych štruktúr či procesov k novej etape práce – podrobnému matematickému modelovaniu (výpočtovému experimentu), ktoré výrazne znižuje potrebu experimentov v plnom rozsahu a v niektorých prípadoch ich môže nahradiť.
Komplexné výpočtové problémy, ktoré vznikajú pri štúdiu fyzikálnych a technických problémov, možno rozdeliť na množstvo elementárnych, ako napríklad výpočet integrálu, riešenie diferenciálnej rovnice atď. Mnohé elementárne problémy sú jednoduché a dobre preštudované. Pre tieto problémy už boli vyvinuté metódy numerického riešenia a na ich riešenie často existujú štandardné počítačové programy. Existujú aj pomerne zložité elementárne úlohy; Metódy na riešenie takýchto problémov sa v súčasnosti intenzívne vyvíjajú.
V tomto ohľade musí mať moderný odborník s vyšším vzdelaním nielen vysokú úroveň odbornej prípravy v profile svojej špecializácie, ale musí mať aj dobré znalosti matematických metód na riešenie inžinierskych problémov, musí byť orientovaný na používanie výpočtovej techniky, a prakticky ovládať princípy práce na počítači.
Analýza práce
Ako vstupné údaje boli použité:
1. Počet uzlov.
2. Tabuľkové hodnoty funkcie.
Výstupné údaje, t.j. Výsledkom programu je:
1. Hodnoty funkcie špecifikovanej v tabuľke v medzihodnotách.
2. Polynomický graf.
Matematický model problému
Pri práci v kurze bol zvolený nasledujúci matematický model:
Interpolácia a aproximácia funkcií.
1. Vyjadrenie problému.
Jedným z hlavných problémov numerickej analýzy je problém interpolácie funkcií. Často je potrebné obnoviť funkciu
pre všetky hodnoty v intervale, ak sú jeho hodnoty známe v určitom konečnom počte bodov v tomto intervale. Tieto hodnoty možno nájsť ako výsledok pozorovaní (meraní) v nejakom prirodzenom experimente alebo ako výsledok výpočtov. Okrem toho sa môže ukázať, že funkcia je daná vzorcom a výpočet jej hodnôt pomocou tohto vzorca je veľmi náročný na prácu, preto je žiaduce mať pre funkciu jednoduchší (na výpočet menej náročný na prácu) vzorec. , čo by umožnilo nájsť približnú hodnotu príslušnej funkcie s požadovanou presnosťou v akomkoľvek bode segmentu. V dôsledku toho vzniká nasledujúci matematický problém.Let a“ segment
mriežka sa hodnoty funkcií sú špecifikované v jeho uzloch
, rovný .Je potrebné zostrojiť interpolant – funkciu
, ktorá sa zhoduje s funkciou v uzloch mriežky: .Hlavným účelom interpolácie je získať rýchly (ekonomický) algoritmus na výpočet hodnôt
pre hodnoty, ktoré nie sú obsiahnuté v tabuľke údajov.2. Newtonova interpolácia
Zadaná tabuľková funkcia:
| i | ||
| 0 | ||
| 1 | ||
| 2 | ||
| .. | .. | .. |
| n |
Body so súradnicami
sa nazývajú uzlové body alebo uzly.Počet uzlov v tabuľkovej funkcii je N=n+1.
Je potrebné nájsť hodnotu tejto funkcie v medziľahlom bode, napr.
a . Na vyriešenie problému sa používa interpolačný polynóm.Interpolačný polynóm podľa Newtonovho vzorca má tvar:
kde n je stupeň polynómu,
Newtonov interpolačný vzorec umožňuje vyjadriť interpolačný polynóm
cez hodnotu na jednom z uzlov a cez delené rozdiely funkcie postavenej nad uzlami.Najprv poskytneme potrebné informácie o oddelených rozdieloch.
Vpustite uzly
,funkčné hodnoty sú známe
. Predpokladajme, že medzi bodmi , , nie sú žiadne zhodné. Delené rozdiely prvého rádu sa nazývajú vzťahy , , .Budeme uvažovať rozdelené rozdiely tvorené susednými uzlami, t. j. výrazmi
Pomerne bežnou interpolačnou metódou je Newtonova metóda. Interpolačný polynóm pre túto metódu má tvar:
Pn (x) = a 0 + a 1 (x-x 0) + a 2 (x-x 0) (x-x 1) + ... + a n (x-x 0) (x-x 1)...(x-x n-1).
Úlohou je nájsť koeficienty a i polynómu P n (x). Koeficienty sa získajú z rovnice:
Pn(xi) = yi, i = 0, 1, ..., n,
čo vám umožní napísať systém:
ao + ai (x 1 - x 0) = yi;
a0 + ai (x 2 - x 0) + a 2 (x 2 - x 0) (x 2 - x 1) = y2;
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
a 0 +... + a n (x n - x 0) (x n - x 1) ... (x n - x n-1) = y n;
Používame metódu konečných rozdielov. Ak sú uzly x i dané v rovnakých intervaloch h, t.j.
x i+1 - x i = h,
potom vo všeobecnom prípade x i = x 0 + i×h, kde i = 1, 2, ..., n. Posledný výraz nám umožňuje zredukovať riešenú rovnicu do tvaru
yi = ao + a1 xh;
y2 = ao + ai (2h) + a2 (2h)h;
- - - - - - - - - - - - - - - - - - -
y i = a 0 + a 1 ×i×h + a 2 ×i×h[(i-1)h] + ... + a i ×i!×h i ,
odkiaľ dostaneme koeficienty
kde Dу 0 je prvý konečný rozdiel.
Pokračujúc vo výpočtoch dostaneme:
kde D 2 y 0 je druhý konečný rozdiel, ktorý je rozdielom rozdielov. Koeficient ai môže byť reprezentovaný ako:
Vložením nájdených hodnôt koeficientov a i do hodnôt pre P n (x) dostaneme Newtonov interpolačný polynóm:
Transformujme vzorec, pre ktorý zavedieme novú premennú, kde q je počet krokov potrebných na dosiahnutie bodu x, pohybujúcich sa z bodu x 0. Po transformáciách dostaneme:
Výsledný vzorec je známy ako Newtonov prvý interpolačný vzorec alebo Newtonov vzorec pre doprednú interpoláciu. Je výhodné ho použiť na interpoláciu funkcie y = f(x) v blízkosti počiatočnej hodnoty x – x 0, kde q je v absolútnej hodnote malé.
Ak zapíšeme interpolačný polynóm v tvare:
potom je možné podobným spôsobom získať druhý Newtonov interpolačný vzorec alebo Newtonov vzorec pre interpoláciu „spätne“:
Zvyčajne sa používa na interpoláciu funkcie blízko konca tabuľky.
Pri štúdiu tejto témy je potrebné pamätať na to, že interpolačné polynómy sa v uzloch interpolácie zhodujú s danou funkciou f(x) a v ostatných bodoch sa vo všeobecnom prípade budú líšiť. Táto chyba nám dáva chybu metódy. Chyba interpolačnej metódy je určená zvyškovým členom, ktorý je rovnaký pre Lagrangeov a Newtonov vzorec a ktorý nám umožňuje získať nasledujúci odhad absolútnej chyby:
| |
Ak sa v tom istom kroku vykoná interpolácia, vzorec pre zvyšok sa upraví. Najmä pri interpolácii „dopredu“ a „dozadu“ pomocou Newtonovho vzorca sa výrazy pre R(x) navzájom mierne líšia.
Z analýzy výsledného vzorca je zrejmé, že chyba R(x) je až do konštanty súčinom dvoch faktorov, z ktorých jeden, f (n+1) (x), kde x leží vo vnútri , závisí od vlastnosti funkcie f(x) a nedajú sa regulovať, ale veľkosť inej,
je určený výlučne výberom interpolačných uzlov.
Ak je umiestnenie týchto uzlov neúspešné, horná hranica modulu |R(x)| môže byť dosť veľký. Preto vzniká problém čo najracionálnejšieho výberu interpolačných uzlov x i (pre daný počet uzlov n) tak, aby polynóm П n+1 (x) mal najmenšiu hodnotu.
2. Newtonova interpolácia
Zadaná tabuľková funkcia:
| i | ||
| 0 | ||
| 1 | ||
| 2 | ||
| .. | .. | .. |
| n |
Body so súradnicami sa nazývajú uzlové body alebo uzly.
Počet uzlov v tabuľkovej funkcii je N=n+1.
Je potrebné nájsť hodnotu tejto funkcie v medziľahlom bode, napríklad , a . Na vyriešenie problému sa používa interpolačný polynóm.
Interpolačný polynóm podľa Newtonovho vzorca má tvar:
kde n je stupeň polynómu,
Newtonov interpolačný vzorec umožňuje vyjadriť interpolačný polynóm z hľadiska hodnoty v jednom z uzlov a z hľadiska delených rozdielov funkcie zostrojenej v uzloch.
Najprv poskytneme potrebné informácie o oddelených rozdieloch.
Vpustite uzly
hodnoty funkcie sú známe. Predpokladajme, že medzi bodmi , , nie sú žiadne zhodné. Delené rozdiely prvého rádu sa nazývajú vzťahy
, ,.
Budeme uvažovať rozdelené rozdiely tvorené susednými uzlami, t. j. výrazmi
Z týchto oddelených rozdielov prvého rádu môžeme zostaviť oddelené rozdiely druhého rádu:
,
,
Takto oddelený rozdiel tého rádu na sekcii možno určiť prostredníctvom oddelených rozdielov tého rádu pomocou opakujúceho sa vzorca:
kde , , je stupeň polynómu.
Maximálna hodnota je . Potom sa delený rozdiel n-tého rádu na úseku rovná
tie. sa rovná rozdielu delených rozdielov tého rádu delené dĺžkou úseku.
Rozdelené rozdiely
sú dobre definované čísla, preto výraz (1) je skutočne algebraický polynóm tého stupňa. Navyše v polynóme (1) sú všetky delené rozdiely definované pre sekcie , .
Pri výpočte delených rozdielov je zvykom zapisovať ich vo forme tabuľky
| ■ | |||||
|
| |||||
Delený rozdiel -tého rádu je vyjadrený z hľadiska funkčných hodnôt v uzloch takto:
. (1)
Tento vzorec sa dá dokázať indukciou. Budeme potrebovať špeciálny prípad vzorca (1):
Newtonov interpolačný polynóm sa nazýva polynóm
Uvažovaná forma Newtonovho polynómu sa nazýva Newtonov prvý interpolačný vzorec a zvyčajne sa používa pri interpolácii na začiatku tabuľky.
Všimnite si, že riešenie Newtonovho interpolačného problému má určité výhody v porovnaní s riešením Lagrangeovho interpolačného problému. Každý člen Lagrangeovho interpolačného polynómu závisí od všetkých hodnôt tabuľkovej funkcie y i , i=0,1,…n. Preto, keď sa zmení počet uzlových bodov N a stupeň polynómu n (n=N-1), je potrebné Lagrangeov interpolačný polynóm zostrojiť nanovo. V Newtonovom polynóme pri zmene počtu uzlových bodov N a stupňa polynómu n stačí pridať alebo zahodiť zodpovedajúci počet štandardných členov v Newtonovom vzorci (2). To je v praxi výhodné a urýchľuje to proces výpočtu.
Programovanie funkcie Newtonovho vzorca
Na zostrojenie Newtonovho polynómu pomocou vzorca (1) organizujeme cyklický výpočtový proces podľa . V tomto prípade pri každom kroku vyhľadávania nájdeme oddelené rozdiely k-tého rádu. Rozdelené rozdiely v každom kroku umiestnime do poľa Y.
Potom bude opakujúci sa vzorec (3) vyzerať takto:
Newtonov vzorec (2) používa oddelené rozdiely t. rádu, vypočítané len pre úseky, t.j. oddelené rozdiely rádu pre . Označme tieto oddelené rozdiely k-tého rádu ako . A delené rozdiely vypočítané pre , sa používajú na výpočet delených rozdielov vyššieho rádu.
Pomocou (4) zbalíme vzorec (2). V dôsledku toho dostaneme
(5)
– hodnota tabuľkovej funkcie (1) pre .
– delený rozdiel t. rádu pre úsek .
Podobné články
