Newtons interpolationsformel. Newtons interpolationspolynom Newtons första interpolationsformel

Skicka ditt goda arbete i kunskapsbasen är enkelt. Använd formuläret nedan

Studenter, doktorander, unga forskare som använder kunskapsbasen i sina studier och arbete kommer att vara er mycket tacksamma.

Postat på http://www.allbest.ru/

Moscow State University of Instrument Engineering and Informatics Sergiev Posad Branch

Sammanfattning om ämnet:

Newtons interpolationsformler

Kompletterad av: Brevchik Taisiya Yurievna

2:a årsstudent i grupp EF-2

1. Introduktion

2. Newtons första interpolationsformel

3. Newtons andra interpolationsformel

Slutsats

Bibliografi

Introduktion

Interpolation, interpolation - i beräkningsmatematik, en metod för att hitta mellanliggande värden av en kvantitet från en befintlig diskret uppsättning kända värden.

Många av dem som sysslar med vetenskapliga och tekniska beräkningar måste ofta arbeta med uppsättningar värden som erhållits empiriskt eller genom slumpmässigt urval. Som regel, baserat på dessa uppsättningar, är det nödvändigt att konstruera en funktion i vilken andra erhållna värden kan falla med hög noggrannhet. Detta problem kallas approximation. Interpolation är en typ av approximation där kurvan för den konstruerade funktionen passerar exakt genom de tillgängliga datapunkterna.

Det finns också en uppgift nära interpolation, som består i att approximera en komplex funktion med en annan, enklare funktion. Om en viss funktion är för komplex för produktiva beräkningar kan du försöka beräkna dess värde vid flera punkter, och utifrån dem konstruera, det vill säga interpolera, en enklare funktion.

Att använda en förenklad funktion ger naturligtvis inte resultat lika exakta som den ursprungliga funktionen. Men i vissa klasser av problem kan den uppnådda vinsten i enkelhet och hastighet av beräkningar uppväga det resulterande felet i resultaten.

Värt att nämna är också en helt annan typ av matematisk interpolation som kallas operatorinterpolation.

Klassiska verk om operatorinterpolation inkluderar Riesz-Thorin-satsen och Marcinkiewicz-satsen, som ligger till grund för många andra verk.

Låt oss betrakta ett system med icke-sammanfallande punkter () från en viss region. Låt funktionsvärdena vara kända endast vid dessa punkter:

Interpolationsproblemet är att hitta en funktion från en given klass av funktioner så att

Punkterna kallas interpolationsnoder, och deras samling kallas interpolationsrutnät.

Paren kallas datapunkter eller baspunkter.

Skillnaden mellan "angränsande" värden är interpolationsrutnätssteget. Den kan vara antingen variabel eller konstant.

En funktion är en interpolerande funktion eller en interpolant.

1. Newtons första interpolationsformel

1. Beskrivning av uppgiften. Låt funktionen ges värden för lika fördelade värden av den oberoende variabeln: , där - interpolationssteg. Det krävs att man väljer ett polynom av grad som inte är högre, och tar vid punkter värdena

Villkor (1) är likvärdiga med det vid.

Newtons interpolationspolynom har formen:

Det är lätt att se att polynom (2) helt uppfyller kraven för problemet. För det första är graden av polynomet inte högre, och för det andra,

Observera att när formel (2) förvandlas till en Taylor-serie för funktionen:

För praktiskt bruk skrivs Newtons interpolationsformel (2) vanligtvis i en lätt transformerad form. För att göra detta introducerar vi en ny variabel med hjälp av formeln; då får vi:

där representerar antal steg, krävs för att nå punkten, med början från punkten. Detta är den sista looken Newtons interpolationsformel.

Det är fördelaktigt att använda formel (3) för att interpolera funktionen i närheten av utgångsvärdet , där är liten i absolut värde.

Om en obegränsad tabell med funktionsvärden ges, kan numret i interpolationsformeln (3) vara vilket som helst. I praktiken, i detta fall, väljs numret så att skillnaden är konstant med en given grad av noggrannhet. Alla tabellvärden för argumentet kan tas som initialvärde.

Om tabellen med funktionsvärden är ändlig, är antalet begränsat, nämligen: det kan inte finnas mer än antalet funktionsvärden reducerat med ett.

Observera att när du tillämpar Newtons första interpolationsformel är det bekvämt att använda en horisontell tabell med skillnader, eftersom de erforderliga värdena för skillnaderna i funktionen är i den motsvarande horisontella raden i tabellen.

2. Exempel. Ta steget och konstruera Newton-interpolationspolynomet för funktionen som ges av tabellen

Det resulterande polynomet gör det möjligt att förutsäga. Vi får tillräcklig noggrannhet när vi löser ett interpolationsproblem, till exempel, Noggrannheten sjunker när vi löser ett extrapolationsproblem, till exempel .

2. Newtons andra interpolationsformel

Newtons första interpolationsformel är praktiskt taget obekväm för att interpolera en funktion nära tabellnoder. I det här fallet används det vanligtvis .

Beskrivning av uppgiften . Låt oss ha en sekvens av funktionsvärden

för ekvidistanta argumentvärden, var är interpolationssteget. Låt oss konstruera ett polynom av följande form:

eller, med den generaliserade kraften, får vi:

Sedan, om jämställdheten håller, får vi

Låt oss ersätta dessa värden i formel (1). Då, äntligen, Newtons andra interpolationsformel har formen:

Låt oss introducera en mer bekväm notation för formel (2). Låt det vara då

Genom att ersätta dessa värden i formel (2) får vi:

Detta är den vanliga synen Newtons andra interpolationsformel. För att approximera beräkningen av funktionsvärdena, anta:

Både Newtons första och andra interpolationsformler kan användas för att extrapolera en funktion, det vill säga för att hitta funktionsvärden för argumentvärden utanför tabellen.

Om det är nära, är det fördelaktigt att tillämpa Newtons första interpolationsformel, och sedan. Om det är nära, är det dessutom bekvämare att använda Newtons andra interpolationsformel.

Alltså brukar Newtons första interpolationsformel användas för framåt interpolation Och extrapolera bakåt, och Newtons andra interpolationsformel, tvärtom, för interpolerar bakåt Och framåtextrapolering.

Notera att extrapoleringsoperationen, generellt sett, är mindre exakt än interpolationsoperationen i ordets snäva betydelse.

Exempel. Ta steget och konstruera Newton-interpolationspolynomet för funktionen som ges av tabellen

Slutsats

interpolation newton extrapolation formel

Inom beräkningsmatematiken spelar interpolering av funktioner en betydande roll, d.v.s. Använda en given funktion, konstruera en annan (vanligtvis enklare) funktion vars värden sammanfaller med värdena för den givna funktionen vid ett visst antal punkter. Dessutom har interpolation både praktisk och teoretisk betydelse. I praktiken uppstår ofta problemet med att rekonstruera en kontinuerlig funktion från dess tabellerade värden, till exempel erhållna under något experiment. För att utvärdera många funktioner är det effektivt att approximera dem med hjälp av polynom eller rationella bråkfunktioner. Interpolationsteori används vid konstruktion och studie av kvadraturformler för numerisk integration, för att erhålla metoder för att lösa differentialekvationer och integralekvationer.

Bibliografi

1. V.V. Ivanov. Datorberäkningsmetoder. Referensmanual. Förlaget "Naukova Dumka". Kiev. 1986.

2. N.S. Bakhvalov, N.P. Zhidkov, G.M. Kobelkov. Numeriska metoder. Förlaget "Laboratoriet för grundläggande kunskaper". 2003.

3. I.S. Berezin, N.P. Zhidkov. Beräkningsmetoder. Ed. PhysMatLit. Moskva. 1962.

4. K. De Bor. En praktisk guide till splines. Förlaget "Radio och kommunikation". Moskva. 1985.

5. J. Forsyth, M. Malcolm, K. Mowler. Maskinella metoder för matematiska beräkningar. Förlaget "Mir". Moskva. 1980.

Postat på Allbest.ru

...

Liknande dokument

Tillämpning av Newtons första och andra interpolationsformler. Hitta funktionsvärden på punkter som inte är tabellformade. Använder Newtons formel för ojämna punkter. Att hitta värdet på en funktion med hjälp av Aitkens interpolationsschema.

laborationer, tillagd 2013-10-14

Johann Carl Friedrich Gauss är den största matematikern genom tiderna. Gaussiska interpolationsformler, som ger ett ungefärligt uttryck för funktionen y=f(x) med hjälp av interpolation. Användningsområden för Gaussiska formler. De största nackdelarna med Newtons interpolationsformler.

test, tillagt 2014-06-12

Interpolering av en funktion vid en punkt som ligger i närheten av mitten av intervallet. Gaussiska interpolationsformler. Stirlingformel som det aritmetiska medelvärdet av Gauss-interpolationsformler. Kubisk spline fungerar som en matematisk modell av en tunn stav.

presentation, tillagd 2013-04-18

Kontinuerlig och punktapproximation. Lagrange och Newton interpolationspolynom. Globalt interpolationsfel, kvadratiskt beroende. Minsta kvadratiska metod. Urval av empiriska formler. Styckvis konstant och styckvis linjär interpolation.

kursarbete, tillagd 2014-03-14

Metoder för ackord och iterationer, Newtons regel. Interpolationsformler för Lagrange, Newton och Hermite. Punktkvadratisk approximation av en funktion. Numerisk differentiering och integration. Numerisk lösning av vanliga differentialekvationer.

föreläsningskurs, tillagd 2012-11-02

Utföra interpolation med Newtons polynom. Förfina rotens värde på ett givet intervall i tre iterationer och hitta beräkningsfelet. Tillämpning av Newton, Sampson och Euler metoder för att lösa problem. Beräkning av derivatan av en funktion.

test, tillagt 2011-02-06

I beräkningsmatematik spelar interpolering av funktioner en betydande roll. Lagranges formel. Interpolation enligt Aitken-schemat. Newtons interpolationsformler för ekvidistanta noder. Newtons formel med uppdelade skillnader. Spline-interpolation.

test, tillagt 2011-05-01

Beräkning av derivatan enligt dess definition, med ändliga skillnader och baserat på Newtons första interpolationsformel. Lagrange-interpolationspolynom och deras tillämpning i numerisk differentiering. Runge-Kutta-metoden (fjärde ordningen).

abstrakt, tillagt 2011-06-03

Slut på olika beställningar. Samband mellan terminalskillnader och funktioner. Diskret och kontinuerlig analys. Förståelse för divisioner. Newtons interpolationsformel. Uppdatering av Lagrange och Newton formler. Interpolation för lika avlägsna noder.

test, tillagt 2014-06-02

Hitta Lagrange- och Newton-interpolationspolynom som passerar genom fyra punkter i en given funktion, och jämför deras maktlagsrepresentationer. Lösa en icke-linjär differentialekvation med Eulermetoden. Lösa system av algebraiska ekvationer.

Föreläsning 4

1. Ändliga skillnader
2. Första interpolationsformeln
Newton
3. Andra interpolationsformeln
Newton
4. Interpolationsfel

Finita skillnader av 1:a ordningen

Om den interpolerade funktionen y = f(x) ges in
lika åtskilda noder, så xi = x0 + i∙h, där h är tabellsteget, och
i = 0, 1, … n, då kan formlerna användas för interpolation
Newton använder ändliga skillnader.
Den ändliga skillnaden av första ordningen är skillnaden yi
= yi+1 - yi, där
yi+1= f(xi+h) och yi = f(xi). För den angivna funktionen
tabellform i (n+1) noder, i = 0, 1, 2, …, n, ändliga skillnader
första ordningen kan beräknas vid punkterna 0, 1, 2,..., n - 1:
y 0 y1 y 0 ,
y1 y 2 y1,
.......................
yn 1 yn yn 1.

Ändliga skillnader av högre ordning

Genom att använda första ordningens ändliga skillnader kan man
erhåll andra ordningens ändliga skillnader 2yi = yi+1 - yi:
2y0y1y0;
2y1y2y1;
..........................
2 y n 2 y n 1 y n 2 .
Finita skillnader i k:te ordningen vid nodnummer kan jag
beräknas genom skillnader av (k-1):e ordningen:
k yi k 1yi 1 k 1yi
Eventuella ändliga skillnader kan beräknas genom värdena
funktioner i interpolationsnoder, till exempel:
2 y 0 y1 y 0 (y 2 y1) (y1 y 0) y 2 2y1 y 0 .

Ändlig skillnadstabell

x
y
Δ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

Baserat på storleken på de slutliga skillnaderna kan man
do
slutsats
O
grader
interpolation
polynom,
beskriver
tabell
given
fungera.
Om
För
tabeller
Med
lika långt
knutpunkter
slutlig
k:te ordningens skillnader är konstanta eller
står i proportion till ett givet fel, alltså
funktionen kan representeras som ett polynom
kth examen.

Finita skillnader och grad av polynom

Betrakta till exempel den finita differenstabellen för
polynom y = x2 – 3x + 2.
0
y
-0.16
2 år
0.08
3 år
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
y
1.0
Finita skillnader av tredje ordningen är lika med noll, och alla
de slutliga skillnaderna av andra ordningen är desamma och lika med 0,08. Detta
säger att en funktion som ges i en tabell kan vara
representera det som ett polynom av grad 2 (förväntat resultat,
med tanke på hur tabellen erhålls).

Låt funktionen y = f(x) specificeras vid n+1 lika åtskilda noder xi , i = 0, 1,
2,...n med steg h. Vi måste hitta interpolationspolynomet Pn(x)
grad n, som uppfyller villkoret:
Pn(xi) = yi, i =0, 1, 2, …,n .
Vi kommer att leta efter ett interpolationspolynom i formen:
Pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + … + an(x-x0)(x-x1)...(x-xn-1),
där аi, i = 0, 1, 2,...n – okända koefficienter oberoende av noder
interpolation. Låt oss hitta dessa koefficienter från interpolationsvillkoren.
Låt x = x0, sedan Pn(x0) = y0 = a0. Därför är a0 = y0.
Låt x = x1, sedan Pn(x1) = y1 = a0 + a1(x1 - x0) = y0 + a1(x1 - x0), varifrån
a1
y1 y0 y0
.
x1 x0
h
Låt nu x = x2, sedan:
Pn (x 2) y 2 a0 a1(x 2 -x 0) a2 (x 2 -x 0)(x 2 -x1) y 0
y 0
2h a2 2h2.
h
När vi uttrycker a2 från detta uttryck får vi:
y 2 2 y0 y0 y 2 2(y1 y0) y0 y 2 2y1 y 0 2 y 0
a2
.
2h2
2h2
2h2
2h2

Newtons första interpolationsformel

Om vi fortsätter med substitutionerna kan vi få ett uttryck för någon
koefficient med nummer i:
jag y 0
ai
,
jag! Hej
i 0,1,...,n.
Genom att ersätta de hittade värdena för koefficienterna med det ursprungliga uttrycket,
vi får Newtons första interpolationsformel:
y0
2y0
n y 0
Pn(x)y0
(x x0)
(x x 0)(x x1) ...
(x x 0)...(x x n 1).
1!h
2!h2
n!hn
Formeln visar att den använder den översta raden i tabellen
ändliga skillnader (bild 4). En speciell egenskap hos formeln är också
successiv ökning av graden av polynomet när det läggs till
nästa villkor. Detta gör att du kan förfina resultatet som erhålls utan
omräkning av redan beaktade villkor.

Newtons första interpolationsformel

Newtons första interpolationsformel kan skrivas in
i en mer kompakt och bekväm form för mjukvaruimplementering.
Efter att ha utsett
q
x x0
,
h
x x 0 qh
och utföra enkla transformationer av formuläret:
x x1 x x 0 h
q 1;
h
h
x xn
x x2
qn 1,
q 2;.....;
h
h
vi får Newtons första interpolationsformel, uttryckt
i förhållande till okänt q:
n y 0
2y0
q(q 1)...(q n 1).
q(q 1) ...
Pn (x) Pn (x0 hq) y0 y0q
n!
2!

10. Newtons första interpolationsformel

Finita skillnader av högre ordning som används i formeln
Newton, har vanligtvis ett stort fel i samband med fel
avrundning vid subtrahering av nära värden. Därför motsvarande
termerna i formeln har också ett stort fel. Att minska
deras bidrag till summan, det vill säga till slutresultatet, måste uppfyllas
skick |q|< 1. Это обеспечивается, если точка интерполяции x находится
mellan de två första noderna i tabellen: x0< x < x1. По этой причине
interpolation med Newtons första formel kallas
interpolation i början av tabellen eller framåtinterpolation.

interpolation Newtons första interpolationsformel tar
följande formulär:
P1(x) y0 y0q.
P2 (x) y 0 y 0 q 2 y 0
q(q 1)
.
2

11. Ett exempel på användning av Newtons första interpolationsformel

som i exemplet på bild 6. Du måste hitta en ungefärlig
värdet på funktionen vid punkt x = 1,1 med kvadratisk
interpolation med Newtons första formel.
x
1.0
1.2
1.4
1.6
1.8
y
0
-0.16
-0.24
-0.24
-0.16
y
-0.16
-0.08
0
0.08
2y 3y
0.08 0
0.08 0
0.08
Tabellsteg 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
Resultatet stämmer
värdet på polynomet
y = x2 – 3x + 2, varav
bord mottagits

12. Schema för beräkningsalgoritmen med hjälp av Newtons första interpolationsformel

13. Newtons andra interpolationsformel

Newtons andra formel har liknande egenskaper
i förhållande till den högra sidan av bordet. För att bygga den använd
polynom av formen:
Pn(x) = a0 + a1(x-xn) + a2(x-xn)(x-xn-1) + … + an(x-xn)(x-xn-1)…(x-x1),
där аi, i = 0, 1, 2, … n är koefficienter som inte beror på interpolationsnoderna.
För att bestämma koefficienterna ai kommer vi att använda detta uttryck en efter en
ersätta interpolationsnoder. För x = xn Pn(xn) = yn, därför,
a0 = yn.
För x = xn-1 har vi Pn(xn-1) = yn-1 = a0 + a1(xn-1-xn) = yn + a1(xn-1-xn),
var
a1
yn 1 yn yn yn 1 yn 1
.
xn 1 xn xn xn 1
h

14. Newtons andra interpolationsformel

Om vi fortsätter med substitutionerna får vi uttryck för alla koefficienter
polynom och Newtons andra interpolationsformel:
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
Formeln visar att den använder den nedre diagonalen i tabellen
ändliga skillnader (bild 4). Som i Newtons första formel, att lägga till
successiva terminer leder till en konsekvent ökning av graden
polynom, vilket gör att du kan förtydliga resultatet utan att räkna om
beaktas villkor.
Genom att ange notationen: q
x xn
,
h
x xn hq
och efter att ha utfört enkla transformationer får vi den andra interpolationen
Newtons formel uttryckt med avseende på substitutionsvariabeln q:
n y 0
2yn 2
Pn (x) yn yn 1q
q(q 1) ...
q(q 1)...(q n 1).
2!
n!

15. Newtons andra interpolationsformel

Från samma överväganden som i fallet med Newtons första formel, för
För att minska beräkningsfelet är det nödvändigt att villkoret är uppfyllt
|q|< 1. Это обеспечивается, если точка интерполяции x находится между
de två sista noderna i tabellen: xn-1< x < xn. По этой причине
interpolation med Newtons andra formel kallas
interpolation från slutet av tabellen eller bakåtinterpolation.
För speciella fall av linjär (n=1) och kvadratisk (n=2)
interpolation Newtons andra interpolationsformel tar
följande formulär:
P1 (x) y n y n 1q
2 y n 2
P2 (x) y n y n 1 q
q(q 1)
2!

16. Ett exempel på användning av Newtons andra interpolationsformel

Låt den interpolerade funktionen f(x) ges av samma tabell,
som i exemplet på bild 11. Du måste hitta en ungefärlig
värdet för funktionen i punkt x = 1,7 med kvadratisk
interpolation med hjälp av Newtons andra formel.
x
1.0
1.2
1.4
1.6
1.8
y
0
-0.16
-0.24
-0.24
-0.16
y
-0.16
-0.08
0
0.08
2y 3y
0.08 0
0.08 0
0.08
Tabellsteg h = 0,2
q = (x – xn)/h = -0,5
Resultatet stämmer
värdet på polynomet
y = x2 – 3x + 2, från
som mottogs
tabell
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. Schema för beräkningsalgoritmen med hjälp av Newtons andra interpolationsformel

18. Interpolationsfel

Interpolerande funktion vid punkter mellan
interpolationsnoder ersätter interpolering
funktion ungefär:
f(x) = F(x) + R(x), där R(x) är felet
interpolation.
För att uppskatta felet är det nödvändigt att ha
det är nödvändigt att ha viss information om
interpolerad funktion f(x). Låt oss låtsas som det
f(x) definieras på segmentet som innehåller alla
noder xi, och för x som tillhör , har alla
derivator f"(x), f""(x), … f(n+1)(x) upp till (n+1)th
beställning inklusive.

19. Interpolationsfel

Sedan

20. Val av interpolationsnoder med hjälp av Lagrange-formeln

För en fast grad av ett polynom:
x*
x0
x1
x2
x3
x4
x5
x
Med successiv gradhöjning
polynom
x*
x4
x2
x0
x1
x3
x5
x

21. Praktisk bedömning av interpolationsfelet med hjälp av Lagrange-formeln

I praktiken uppskattar det maximala värdet av derivatan av (n+1)th
ordning Mn+1 är sällan möjlig när man använder Lagrange-formeln,
och använd därför en ungefärlig feluppskattning
Rn (x) f(x) Ln (x) Ln 1 (x) Ln (x) ,
där n är antalet använda noder.
Av formeln ovan följer att för att uppskatta felet
interpolation med ett lagrangepolynom av n:e graden är nödvändig
beräkna dessutom värdet av ett polynom med (n+1) grad. Om
det tillåtna interpolationsfelet ges, då är det nödvändigt att lägga till alla
nya noder, öka graden av polynomet tills modulen
skillnad mellan de två sista värdena av polynomet |Ln+1(x)-Ln(x)| Inte
kommer att bli mindre än det angivna värdet.

22. Schema för interpolationsalgoritmen med hjälp av Lagrange-formeln med en given noggrannhet

23. Uppskattning av fel i Newtons interpolationsformler

För interpolering
anta följande form.
Newtons första formel:
Rn(x)h
n 1
formler
Newton
bedömningar
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)!
Newtons andra formel:
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)!
fel

24. Praktisk bedömning av fel i Newtons interpolationsformler

När du använder Newtons interpolationsformler, värdet
f(n+1)(ξ) kan uppskattas ungefär från värdena av ändliga skillnader:
f
(n 1)
n 1
Δy0
() n 1
h
och i det här fallet tar formlerna för att uppskatta felet följande
se:
Newtons första formel:
Rn(x)
q(q 1) (q n) n 1
Δy0
(n 1)!
Newtons andra formel:
Rn(x)
q(q 1) (q n) n 1
Δy0
(n 1)!

25. Interpolation med hjälp av Newtons formler med en given noggrannhet

Jämför dessa formler med formler
Newton, man kan se det för att uppskatta
fel vid interpolering med ett polynom
n:e graden måste du ta en extra nod
och beräkna termen för (n+1):e graden.
Om det tillåtna felet anges
interpolation ε, då är det nödvändigt att sekventiellt
lägga till nya noder och följaktligen,
nya villkor, vilket ökar graden
interpolationspolynom tills
tills nästa term blir mindre än ε.

anteckning

Den förklarande noten till kursarbetet "Interpolation av en funktion av en variabel med Newtons metod" innehåller en introduktion, analys av uppgiften med en beskrivning av in- och utdata, en genomgång av litterära källor, en beskrivning av den matematiska modellen och metoder. av beräkningsmatematik, förklaringar av algoritmen, programtext och instruktioner. När man studerade disciplinen "Informatik" användes olika litterära källor för att skriva kursarbetet, som listas i detta dokument. Detta kursarbete tillhandahåller ett program som används för att interpolera en tabellspecificerad funktion med hjälp av Newtons metod. Den använde den strukturerade programmeringsmetoden för att göra det lättare att skriva och felsöka programmet, samt förbättra dess tydlighet och läsbarhet. Syftet med att skriva detta arbete var att erhålla och befästa praktiska färdigheter i att utveckla algoritmer med olika metoder. Det presenterade programmet är implementerat i programmeringsspråket Pascal. Den förklarande anteckningen innehåller 25 ark, som innehåller två ritningar, programmets text samt en beskrivning av programmet och algoritmen.

Introduktion

Arbetsanalys

Matematisk modell av problemet

Programmera Newtons formelfunktion

Genomgång av litteraturkällor

Utveckling av ett program enligt algoritmschemat

Instruktioner för att använda programmet

Programtext

Inledande data och resultat av att lösa testfallet

Slutsats

Lista över använda källor

Introduktion

Den moderna utvecklingen av fysik och teknik är nära relaterad till användningen av elektroniska datorer (datorer). För närvarande har datorer blivit vanlig utrustning på många institut och designbyråer. Detta gjorde det möjligt för oss att gå från de enklaste beräkningarna och bedömningarna av olika strukturer eller processer till ett nytt arbetssteg - detaljerad matematisk modellering (beräkningsexperiment), vilket avsevärt minskar behovet av fullskaliga experiment, och i vissa fall kan ersätta dem.

Komplexa beräkningsproblem som uppstår vid studiet av fysiska och tekniska problem kan delas in i ett antal elementära, såsom att beräkna en integral, lösa en differentialekvation etc. Många elementära problem är enkla och väl studerade. Metoder för numerisk lösning har redan utvecklats för dessa problem och det finns ofta vanliga datorprogram för att lösa dem. Det finns också ganska komplexa elementära uppgifter; Metoder för att lösa sådana problem utvecklas nu intensivt.

I detta avseende måste en modern specialist med högre utbildning inte bara ha en hög utbildningsnivå i profilen för sin specialitet, utan också ha goda kunskaper om matematiska metoder för att lösa tekniska problem, vara inriktad på användningen av datorteknik, och praktiskt behärska principerna för att arbeta på en dator.

Arbetsanalys

Följande användes som indata:

1. Antal noder.

2. Tabellvärden för funktionen.

Utdata, d.v.s. Resultatet av programmet är:

1. Värden för en tabellspecificerad funktion i mellanvärden.

2. Polynomgraf.

Matematisk modell av problemet

När du utförde kursarbetet valdes följande matematiska modell:

Interpolation och approximation av funktioner.

1. Redogörelse för problemet.

Ett av huvudproblemen med numerisk analys är problemet med interpolering av funktioner. Det är ofta nödvändigt att återställa funktionen

för alla värden på ett intervall om dess värden är kända vid ett visst ändligt antal punkter på detta intervall. Dessa värden kan hittas som ett resultat av observationer (mätningar) i något slags naturligt experiment, eller som ett resultat av beräkningar. Dessutom kan det visa sig att funktionen ges av en formel och att beräkna dess värden med denna formel är mycket arbetskrävande, så det är önskvärt att ha en enklare (mindre arbetskrävande att beräkna) formel för funktionen , vilket skulle göra det möjligt för en att hitta det ungefärliga värdet för funktionen i fråga med erforderlig noggrannhet var som helst på segmentet. Som ett resultat uppstår följande matematiska problem.

Låt och" segmentera

ett rutnät med

och funktionsvärdena anges i dess noder

, likvärdig .

Det krävs för att konstruera en interpolant - en funktion

, som sammanfaller med funktionen vid rutnätsnoderna: .

Huvudsyftet med interpolation är att få en snabb (ekonomisk) algoritm för att beräkna värden

för värden som inte finns i datatabellen.

2. Newtoninterpolation

Givet en tabellfunktion:

i
0
1
2
..	..	..
n

, (1)

Punkter med koordinater

kallas nodpunkter eller noder.

Antalet noder i tabellfunktionen är N=n+1.

Det är nödvändigt att hitta värdet på denna funktion vid en mellanliggande punkt, till exempel,

, och . För att lösa problemet används ett interpolationspolynom.

Interpolationspolynomet enligt Newtons formel har formen:

där n är graden av polynomet,

Newtons interpolationsformel låter dig uttrycka interpolationspolynomet

genom värdet vid en av noderna och genom de uppdelade skillnaderna i den funktion som byggs över noderna.

Först tillhandahåller vi nödvändig information om separerade skillnader.

Släpp in noder

funktionsvärdena är kända

. Låt oss anta att bland punkterna , , finns det inga sammanfallande. Delade skillnader av första ordningen kallas relationer, , .

Vi kommer att överväga uppdelade skillnader som består av angränsande noder, dvs uttryck

En ganska vanlig interpolationsmetod är Newtons metod. Interpolationspolynomet för denna metod har formen:

P n (x) = a O + 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).

Uppgiften är att hitta koefficienterna a i för polynomet P n (x). Koefficienterna hittas från ekvationen:

P n (x i) = y i, i = 0, 1, ..., n,

så att du kan skriva systemet:

aO + ai (xl - x0) = y1;

aO + ai (x 2 - x 0) + a2 (x 2 - x 0) (x 2 - x 1) = y2;

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

a O +... + a n (x n - x 0) (x n - x 1) ... (x n - x n-1) = y n;

Vi använder den finita differensmetoden. Om noderna x i ges med lika intervall h, dvs.

x i+1 - x i = h,

då i det allmänna fallet x i = x 0 + i×h, där i = 1, 2, ..., n. Det sista uttrycket tillåter oss att reducera ekvationen som löses till formen

y1 = a0 + a 1 xh;

y2 = a O + a 1 (2h) + a 2 (2h)h;

- - - - - - - - - - - - - - - - - - -

y i = a 0 + a 1 ×i×h + a 2 ×i×h[(i-1)h] + ... + a i ×i!×h i,

varifrån vi får för koefficienterna

där Dу 0 är den första ändliga skillnaden.

Om vi fortsätter med beräkningarna får vi:

där D 2 y 0 är den andra ändliga skillnaden, som är skillnaden mellan skillnader. Koefficient a i kan representeras som:

Genom att sätta de hittade värdena för koefficienterna a i i värdena för P n (x), får vi Newton-interpolationspolynomet:

Låt oss omvandla formeln, för vilken vi introducerar en ny variabel, där q är antalet steg som krävs för att nå punkt x, flytta från punkt x 0. Efter transformationer får vi:

Den resulterande formeln är känd som Newtons första interpolationsformel, eller Newtons formel för framåtinterpolation. Det är fördelaktigt att använda den för att interpolera funktionen y = f(x) i närheten av initialvärdet x – x 0, där q är litet i absolut värde.

Om vi skriver interpolationspolynomet i formen:

då kan man på ett liknande sätt få Newtons andra interpolationsformel, eller Newtons formel för att interpolera "bakåt":

Det används vanligtvis för att interpolera en funktion nära slutet av en tabell.

När man studerar detta ämne är det nödvändigt att komma ihåg att interpolationspolynom sammanfaller med den givna funktionen f(x) vid interpolationsnoderna, och vid andra punkter, i det allmänna fallet, kommer de att skilja sig åt. Detta fel ger oss felet i metoden. Felet för interpolationsmetoden bestäms av resttermen, som är densamma för Lagrange- och Newtonformlerna och som gör att vi kan få följande uppskattning för det absoluta felet:

Om interpolering utförs med samma steg, ändras formeln för den återstående termen. I synnerhet när man interpolerar "framåt" och "bakåt" med hjälp av Newtons formel, skiljer sig uttrycken för R(x) något från varandra.

När man analyserar den resulterande formeln är det tydligt att felet R(x) är, upp till en konstant, produkten av två faktorer, varav en, f (n+1) (x), där x ligger inuti, beror på egenskaper hos funktionen f(x) och kan inte regleras, men storleken på en annan,

bestäms enbart av valet av interpolationsnoder.

Om placeringen av dessa noder inte lyckas, den övre gränsen för modulen |R(x)| kan vara ganska stora. Därför uppstår problemet med det mest rationella valet av interpolationsnoder x i (för ett givet antal noder n) så att polynomet П n+1 (x) har det minsta värdet.

2. Newtoninterpolation

Givet en tabellfunktion:

i
0
1
2
..	..	..
n

Punkter med koordinater kallas nodpunkter eller noder.

Antalet noder i tabellfunktionen är N=n+1.

Det är nödvändigt att hitta värdet för denna funktion vid en mellanliggande punkt, till exempel , och . För att lösa problemet används ett interpolationspolynom.

Interpolationspolynomet enligt Newtons formel har formen:

där n är graden av polynomet,

Newtons interpolationsformel låter dig uttrycka interpolationspolynomet i termer av värdet vid en av noderna och i termer av de delade skillnaderna för funktionen som är konstruerad vid noderna.

Först tillhandahåller vi nödvändig information om separerade skillnader.

Släpp in noder

funktionens värden är kända. Låt oss anta att bland punkterna , , finns det inga sammanfallande. Delade skillnader av första ordningen kallas relationer

, ,.

Vi kommer att överväga uppdelade skillnader som består av angränsande noder, dvs uttryck

Från dessa första ordningens separerade skillnader kan vi konstruera andra ordningens separerade skillnader:

Således kan den separerade skillnaden i den th ordningen på en sektion bestämmas genom de separerade skillnaderna i den th ordningen med hjälp av den återkommande formeln:

där , , är graden av polynomet.

Maxvärdet är . Då är den delade skillnaden i n:e ordningen på sektionen lika med

de där. är lika med skillnaden mellan de delade skillnaderna i den e ordningen dividerat med längden på sektionen.

Delade skillnader

är väldefinierade tal, därför är uttryck (1) verkligen ett algebraiskt polynom av den e graden. Dessutom, i polynomet (1) definieras alla uppdelade skillnader för sektioner , .

Vid beräkning av delade skillnader är det vanligt att skriva dem i form av en tabell






■

Den uppdelade skillnaden i -th ordningen uttrycks i termer av funktionsvärdena vid noderna enligt följande:

. (1)

Denna formel kan bevisas genom induktion. Vi kommer att behöva ett specialfall av formel (1):

Newtons interpolationspolynom kallas ett polynom

Den övervägda formen av Newtons polynom kallas Newtons första interpolationsformel och används vanligtvis när man interpolerar i början av tabellen.

Observera att att lösa det Newtonska interpolationsproblemet har vissa fördelar jämfört med att lösa Lagrange-interpolationsproblemet. Varje term i Lagrange-interpolationspolynomet beror på alla värden för tabellfunktionen y i, i=0,1,...n. Därför, när antalet nodpunkter N och graden av polynomet n (n=N-1) ändras, måste Lagrange-interpolationspolynomet konstrueras på nytt. I Newtons polynom, när du ändrar antalet nodpunkter N och graden av polynomet n, behöver du bara lägga till eller ignorera motsvarande antal standardtermer i Newtons formel (2). Detta är praktiskt praktiskt och påskyndar beräkningsprocessen.

Programmera Newtons formelfunktion

För att konstruera Newtonpolynomet med formeln (1) organiserar vi en cyklisk beräkningsprocess enligt . I det här fallet hittar vi vid varje söksteg separerade skillnader i k:te ordningen. Vi kommer att placera de uppdelade skillnaderna vid varje steg i Y-matrisen.

Då kommer den återkommande formeln (3) att se ut så här:

Newtons formel (2) använder separerade skillnader av den e ordningen, beräknade endast för sektioner, dvs. separerade skillnader av ordningen för . Låt oss beteckna dessa separerade skillnader i k:te ordningen som . Och de dividerade skillnaderna som beräknas för , används för att beräkna delade skillnaderna av högre ordning.

Med hjälp av (4) komprimerar vi formel (2). Som ett resultat får vi

(5)