Parabola metoda (Simpson)

Suština metode, formula, procjena greške.

Neka je funkcija y = f(x) kontinuirana na intervalu i trebamo izračunati definitivni integral.

Podijelimo segment na n elementarno

segmenti [;], i = 1., n dužina 2*h = (b-a)/ n tačaka

a =< < < < = b. Пусть точки, i = 1., n являются серединами отрезков [;], i = 1., n соответственно. В этом случае все «узлы» определяются из равенства = a + i*h, i = 0,1., 2*n.

Na svakom intervalu [;], i = 1,2., n integrand

aproksimira se kvadratnom parabolom y = a* + b*x + c koja prolazi kroz tačke (; f ()), (; f ()), (; f ()). Otuda i naziv metode - parabola metoda.

Ovo se radi kako bi se kao približna vrijednost uzeo određeni integral, koji možemo izračunati korištenjem Newton-Leibnizove formule. To je ono o čemu se radi suštinu metode parabole.

Derivacija Simpsonove formule.

Da bismo dobili formulu za metodu parabole (Simpson), moramo samo izračunati

Pokažimo da kroz tačke (; f ()), (; f ()), (; f ()) prolazi samo jedna kvadratna parabola y = a* + b*x + c. Drugim riječima, dokazujemo da su koeficijenti određeni na jedinstven način.

Pošto su (; f ()), (; f ()), (; f ()) tačke parabole, svaka od jednačina sistema je važeća

Napisani sistem jednačina je sistem linearnih algebarskih jednačina za nepoznate varijable, . Determinanta glavne matrice ovog sistema jednačina je Vandermondeova determinanta, i ona je različita od nule za tačke koje se ne podudaraju. To ukazuje da sistem jednačina ima jedinstveno rješenje (o tome se govori u članku rješavajući sisteme linearnih algebarskih jednačina), odnosno da se koeficijenti određuju na jedinstven način, i to kroz tačke (; f ()), ( ; f ()), (; f ()) prolazi kroz jedinstvenu kvadratnu parabolu.

Pređimo na pronalaženje integrala.

Očigledno:

f() = f(0) = + + =

f() = f(h) = + +

f () = f (2*h) = + +

Koristimo ove jednakosti da napravimo posljednju tranziciju u sljedećem lancu jednakosti:

= = (++) = h/3*(f ()+4*f ()+f ())

Tako možemo dobiti formulu za metodu parabole:

Primjer Simpsonove metode.

Izračunajte približno definitivan integral koristeći Simpsonovu formulu sa tačnošću od 0,001. Počnite dijeliti s dva segmenta

Integral se, inače, ne može uzeti.

Rješenje: Odmah vam skrećem pažnju na vrstu zadatka - potrebno je izračunati određeni integral sa određenom tačnošću. Kao i kod metode trapeza, postoji formula koja će vam odmah omogućiti da odredite potreban broj segmenata kako biste jamčili potrebnu točnost. Istina, morat ćete pronaći četvrti izvod i riješiti ekstremni problem. U praksi se gotovo uvijek koristi pojednostavljena metoda procjene greške.

Počinjem da odlučujem. Ako imamo dva segmenta particije, onda će postojati čvorovi još jedan: , . A Simpsonova formula ima vrlo kompaktan oblik:

Izračunajmo korak particije:

Hajde da popunimo tabelu obračuna:

U gornjem redu pišemo "brojač" indeksa

U drugom redu prvo upisujemo donju granicu integracije a = = 1.2, a zatim sukcesivno dodajemo korak h = 0.4.

U treći red unosimo vrijednosti integrala. Na primjer, ako je = 1,6, onda. Koliko decimalnih mjesta trebam ostaviti? Zaista, stanje opet ništa ne govori o ovome. Princip je isti kao u trapezoidnoj metodi, gledamo potrebnu tačnost: 0,001. I dodajte još 2-3 cifre. Odnosno, trebate zaokružiti na 5-6 decimalnih mjesta.

Kao rezultat:

Primarni rezultat je primljen. Sad duplo broj segmenata do četiri: . Simpsonova formula za ovu particiju ima sljedeći oblik:

Izračunajmo korak particije:

Hajde da popunimo tabelu obračuna:

ovako:

Procjenjujemo grešku:

Greška je veća od tražene tačnosti: 0,002165 > 0,001, pa je potrebno ponovo udvostručiti broj segmenata: .

Simpsonova formula postaje sve veća:

Izračunajmo korak:

I ponovo popunite tabelu obračuna:

ovako:

Imajte na umu da je preporučljivo ovdje detaljnije opisati izračune, budući da je Simpsonova formula prilično glomazna:

Procjenjujemo grešku:

Greška je manja od tražene tačnosti: 0,000247< 0,001. Осталось взять наиболее точное приближение, округлить его до трёх знаков после запятой и записать.

Metoda zlatnog omjera

Razmotrimo takav simetričan raspored tačaka na segmentu [A; b], u kojem jedna od njih postaje testna tačka na novom segmentu dobijenom nakon isključivanja dijela originalnog segmenta. Upotreba ovakvih tačaka omogućava da se pri svakoj iteraciji metode eliminacije segmenta, osim prve, ograničimo na određivanje samo jedne vrednosti, pošto je druga vrednost već pronađena na jednoj od prethodnih iteracija.

Tačke koje imaju sljedeće svojstvo: svaka dijeli segment [A; b] na dva nejednaka dijela tako da je odnos dužine cijelog segmenta i dužine njegovog većeg dijela jednak omjeru dužina većeg i manjeg dijela segmenta. Pozivaju se tačke sa ovim svojstvom zlatni omjer bodova segment [A; b]. Ovo objašnjava naziv dotične metode.

Hajde da opišemo algoritam metode zlatnog preseka.

Korak 1. Pronađite koristeći formule. Izračunati. Staviti .

Korak 2. Provjera kraja pretraživanja: ako je , onda idite na korak 3, u suprotnom - na korak 4.

Korak 3. Prelazak na novi segment i nove probne tačke. Ako, onda stavi i izračunaj, inače, stavi i izračunaj.

Spustite ga i idite na korak 2.

Korak 4. Kraj pretraživanja: stavite .

Pronalaženje minimalne tačke pomoću metoda eliminacije segmenta zasniva se na poređenju vrijednosti funkcije u dvije točke. Sa takvim poređenjem razlika u vrijednostima f(x) na ovim tačkama se ne uzimaju u obzir, važni su samo njihovi znaci.

Uzmite u obzir informacije sadržane u relativnim promjenama vrijednosti f(x) na probnim tačkama, dozvolite metode polinomske aproksimacije , čija je glavna ideja to za funkciju f(x) konstruiran je aproksimirajući polinom i njegova minimalna tačka služi kao aproksimacija X*. Za učinkovito korištenje ovih metoda na funkciji f(x), pored unimodalnosti, nameće se i dodatni zahtjev dovoljne glatkoće (barem kontinuiteta).

Da biste povećali točnost aproksimacije, možete, prvo, povećati red polinoma i, drugo, smanjiti dužinu segmenta aproksimacije. Prvi način dovodi do brzog kompliciranja računskih procedura, pa se u praksi koriste aproksimirajući polinomi ne višeg od trećeg reda. Istovremeno, smanjenje segmenta koji sadrži minimalnu tačku unimodalne funkcije nije posebno teško.

Najjednostavnija metoda polinomske aproksimacije, metoda parabole, koristi polinome drugog reda. Na svakoj iteraciji ove metode konstruiše se kvadratni trinom čiji graf (parabola) prolazi kroz tri odabrane tačke na grafu funkcije f(x)(Sl. 2).

Hajde da opišemo metodu parabole. Razmotrimo unimodalno na segmentu [A; b] funkcija f(x), dostižući minimum u unutrašnjoj tački ovog segmenta. Odaberimo tri tačke segmenta [A; b], za koje su nejednakosti zadovoljene

Rice. 2. Ilustracija za metodu parabole

Od unimodalnosti f(x) sledi to. Konstruirajmo kvadratni trinom čiji graf prolazi kroz tačke grafa funkcije f(x). Pretpostavit ćemo da je barem jedna od nejednakosti (3) za stroga (ako je , onda je traženje točke X * ovo je potpuno, jer iz unimodalnosti funkcije f(x) slijedi da dostiže minimum u svakoj tački segmenta). Tada iz (3) slijedi da su grane željene parabole usmjerene prema gore, a minimalna tačka trinoma pripada segmentu .

Određivanje koeficijenata iz sistema jednačina

Minimalni poen X kvadratni trinom q(x) Izračunajmo ga tako što ćemo njegovu derivaciju izjednačiti sa nulom. Dobijamo

Broj X iz (4) služi kao još jedna aproksimacija metode parabole na X *. Zatim se opisani postupak ponavlja za nove tačke koje zadovoljavaju nejednakosti (3).

Možete odabrati ove tačke između i pomicanjem s originalnog na novi segment koji sadrži točku X *, metodom eliminacije segmenata. Za ovaj prelaz se koriste probne tačke i vrednosti u tim tačkama se upoređuju. Početak i kraj novog segmenta, kao i probna tačka koja na njega pada, čine trio tačaka koje imaju svojstvo (3).sa brojem . Ako je , onda dovršite pretragu, pod pretpostavkom da, u suprotnom idite na korak 4.

Korak 4. Izračunajte vrijednost. Idite na korak 5.

Korak 5. Definirajte novu trojku brojeva. Dodijelite odgovarajuće vrijednosti f(x), pronađeno ranije. Idite na korak 2.

Metoda sekante može se smatrati zamjenom funkcije interpolirajućim polinomom prvog stepena nacrtanim preko čvorova

Koristeći posljednje tri iteracije, moguće je konstruirati interpolacijski polinom drugog stepena, odnosno zamijeniti graf funkcije parabolom. Zapišimo interpolacijski polinom u Newtonovom obliku

Izjednačavajući ga sa nulom, dobijamo kvadratnu jednačinu

Koji god od dva korijena kvadratne jednadžbe (36) je manji po apsolutnoj vrijednosti, određuje se nova aproksimacija

Očigledno, da biste započeli proračun, morate navesti tri prve aproksimacije (obično se tri broja biraju nasumično), odnosno proces je u tri koraka.

Metoda parabole je modelirana prema metodama trećeg reda. Međutim, zamjena izvedenica odvojenim razlikama dovodi do značajnog smanjenja stope konvergencije. Koristeći argumente slične onima u paragrafu 7, možemo pokazati da blizu jednostavnog korijena vrijedi relacija:

tj. konvergencija je čak sporija od kvadratne. U blizini višestrukog korijena, konvergencija je čak i sporija (iako je brža od linearne). Imajte na umu da je konstruiranje sličnih metoda korištenjem interpolacionog polinoma još višeg stupnja neisplativo: konvergencija će i dalje biti sporija od kvadratne, a proračun postaje mnogo složeniji.

U metodi parabole, „labavost“ izračunavanja blizu korijena utječe na njega čak i jače nego u metodi sekante, jer su druge razlike uključene u proračun. Ipak, korijeni se mogu pronaći sa dobrom tačnošću; Za određivanje optimalnog broja iteracija zgodno je koristiti Garwickovu tehniku, opisanu u paragrafu 7.

Metoda parabole ima važnu prednost. Čak i ako su sve prethodne aproksimacije važeće, jednačina (36) može dovesti do kompleksnih brojeva. Stoga, proces može prirodno konvergirati kompleksnom korijenu originalne jednadžbe. U jednostavnim iteracijama, metodama tangente ili sekante, konvergencija kompleksnom korijenu može zahtijevati specificiranje složene početne aproksimacije (ako je ) realna za pravi argument).

Korijeni polinoma. Metoda parabole se pokazala izuzetno efikasnom u pronalaženju svih korena polinoma visokog stepena. Ako je algebarski polinom, onda, iako konvergencija metode sa proizvoljnom početnom aproksimacijom nije dokazana, u praksi iteracije uvijek konvergiraju nekom korijenu, i to brzo.

Za polinom, količnik je također polinom; dakle, sekvencijalnim uklanjanjem pronađenih korijena, mogu se pronaći svi korijeni originalnog polinoma.

Napomena 1. Ako je polinom visokog stepena, onda se javljaju dodatne poteškoće. Polinom se brzo povećava kako se argument povećava, tako da kompjuterski program mora imati osiguranje od prelivanja. Obično se uvode faktori skale, čija je vrijednost povezana s rasponom promjene argumenta.

Napomena 2. Koreni polinoma visokog stepena sa najvećim modulom mogu biti veoma osetljivi na grešku koeficijenata na višim stepenima. Na primjer, korijeni polinoma

su uzastopni cijeli brojevi, malo modificirani polinom ima sljedeće korijene:

(ovdje je prikazano samo jedno decimalno mjesto). Višestruki ili bliski korijeni mogu biti slabo stabilni čak i pri nižim potencijama polinoma.

Napomena 3. Da biste uklonili izračunate korijene, morate... podijeliti polinom. Ovo unosi grešku zaokruživanja u koeficijente i utiče na tačnost pronalaženja sledećih korena. U praksi je uočeno da ako prvo uklonite korijene s manjim modulom, preciznost blago opada, ali ako počnete uklanjati velike korijene, tačnost može katastrofalno pasti. Stoga, iteracije obično konvergiraju najmanjem korijenu u apsolutnoj vrijednosti kao početnoj aproksimaciji. Uklanja se i traži se sljedeći korijen koristeći istu početnu aproksimaciju, itd. Sa ovakvom organizacijom proračuna, gubitak tačnosti će biti mali.

Odsjek za višu matematiku

Završio: Matveev F.I.

Provjerio: Burlova L.V.

Ulan-Ude.2002

1.Numeričke metode integracije

2. Izvođenje Simpsonove formule

3.Geometrijska ilustracija

4.Odabir koraka integracije

5.Primjeri

1. Numeričke metode integracije

Problem numeričke integracije je izračunavanje integrala

kroz niz vrijednosti integranda.

Problemi numeričke integracije moraju se riješiti za funkcije navedene u tabelama, funkcije čiji se integrali ne uzimaju u elementarne funkcije, itd. Razmotrimo samo funkcije jedne varijable.

Umjesto funkcije koju treba integrirati, integriramo interpolacijski polinom. Metode zasnovane na zamjeni integrala interpolacijskim polinomom omogućavaju procjenu tačnosti rezultata pomoću parametara polinoma ili odabir ovih parametara na osnovu date tačnosti.

Numeričke metode se mogu uslovno grupirati prema metodi aproksimacije integranda.

Newton-Cotes metode se zasnivaju na aproksimaciji funkcije

stepen polinom. Algoritam ove klase razlikuje se samo po stepenu polinoma. Po pravilu, čvorovi aproksimirajućeg polinoma su ekvirelirani.

Spline metode integracije su zasnovane na aproksimaciji funkcije

spline-piecewise polinom.

Metode najveće algebarske tačnosti (Gaussova metoda) koriste posebno odabrane nejednake čvorove koji daju minimalnu grešku integracije za dati (odabrani) broj čvorova.

Monte Carlo metode se najčešće koriste prilikom izračunavanja više integrala; čvorovi se biraju nasumično, a odgovor je vjerovatnoća.

ukupna greška skraćivanja greške

greška zaokruživanja

Bez obzira na odabranu metodu, u procesu numeričke integracije potrebno je izračunati približnu vrijednost integrala i procijeniti grešku. Greška se smanjuje kako se n-broj povećava

segmentne particije

. Međutim, ovo povećava grešku zaokruživanja

zbrajanjem vrijednosti integrala izračunatih na parcijalnim segmentima.

Greška skraćivanja zavisi od svojstava integrala i dužine

parcijalni segment.

2. Izvođenje Simpsonove formule

Ako za svaki par segmenata

konstruišemo polinom drugog stepena, a zatim ga integrišemo i koristimo svojstvo aditivnosti integrala, dobijamo Simpsonovu formulu. Razmotrimo integrand na segmentu . Zamenimo ovaj integrand sa Lagranžeovim interpolacionim polinomom drugog stepena, koji se poklapa sa u tačkama:

Hajde da se integrišemo

:

i zove se Simpsonova formula.

Dobiveni rezultat za integral

vrijednost se poklapa s površinom krivolinijskog trapeza omeđenog osom, ravnim linijama i parabolom koja prolazi kroz tačke

Procijenimo sada grešku integracije koristeći Simpsonovu formulu. Pretpostavićemo to

postoje kontinuirani derivati ​​na segmentu. Hajde da nadoknadimo razliku

Teorema srednje vrijednosti se već može primijeniti na svaki od ova dva integrala, jer

je kontinuirana i funkcija je nenegativna na prvom intervalu integracije i nepozitivna na drugom (tj. ne mijenja predznak na svakom od ovih intervala). Zbog toga:

(koristili smo teoremu srednje vrijednosti jer

- kontinuirana funkcija; ).

Diferenciranje

dva puta, a zatim primjenom teoreme srednje vrijednosti, dobijamo još jedan izraz za: , gdje

Iz obje procjene za

slijedi da je Simpsonova formula egzaktna za polinome stepena ne višeg od tri. Napišimo Simpsonovu formulu, na primjer, u obliku: , .

Ako segment

integracija prevelika, onda se dijeli na jednake dijelove (pod pretpostavkom ), nakon čega se Simpsonova formula primjenjuje na svaki par susjednih segmenata , ,..., i to:

Zapišimo Simpsonovu formulu u opštem obliku.

Korišćenje tri tačke za interpolaciju integranda omogućava upotrebu paraboličke funkcije (polinom drugog stepena). Ovo dovodi do Simpsonove formule za približno izračunavanje integrala.

Razmotrimo proizvoljni integral

Upotrijebimo promjenu varijable na način da granice segmenta integracije umjesto toga postanu [-1,1]; za to uvodimo varijablu z:

Onda

Razmotrimo problem interpolacije integranda sa polinomom drugog stepena (parabolom), koristeći tri ekvidistantne čvorne tačke kao čvorove - z = -1, z = 0, z = +1 (korak je 1, dužina segmenta integracije je 2). Označimo odgovarajuće vrijednosti integranda na interpolacijskim čvorovima

Sistem jednadžbi za pronalaženje polinomskih koeficijenata

Prolazak kroz tri tačke, i

poprimiće formu

ili

Kvote se mogu lako dobiti

Izračunajmo sada vrijednost integrala interpolacionog polinoma

Inverznom promjenom varijable vraćamo se na originalni integral. Uzmimo to u obzir

Dobijamo Simpsonovu formulu za proizvoljni interval integracije:

Ako je potrebno, originalni segment integracije se može podijeliti na N dvostrukih segmenata, na svaki od kojih se primjenjuje Simpsonova formula. Korak interpolacije će biti

Za prvi segment integracije interpolacioni čvorovi će biti tačke a, a+h, a+2h, za drugi - a+2h, a+3h, a+4h, za treći a+4h, a+5h, a+6h, itd. Približna vrijednost integrala se dobija zbrajanjem N površina:

Ovaj zbir uključuje identične termine (za interne čvorove sa parnom vrijednošću indeksa - 2i). Stoga možemo preurediti članove u ovom zbiru na ovaj način

Šta je ekvivalentno

Jer

Greška ove približne metode opada proporcionalno dužini koraka integracije na četvrti stepen, tj. kada se broj intervala udvostruči, greška se smanjuje za 16 puta

Povećana preciznost

Ovdje gledamo takozvani Aitken proces. Omogućava procjenu greške metode i ukazuje na algoritam za preciziranje rezultata. Proračun se izvodi uzastopno tri puta na različitim koracima particije h 1 , h 2 , h 3 , a njihovi omjeri su konstantni: h 2 / h 1 = h 3 / h 2 = q (na primjer, kada se korak podijeli na pola q = 0,5). Neka se vrijednosti integrala I 1, I 2, I 3 dobiju kao rezultat numeričke integracije. Zatim se rafinirana vrijednost integrala izračunava pomoću formule

a redoslijed tačnosti korištene metode numeričke integracije određen je relacijom

.

Vrijednost integrala se također može precizirati korištenjem Runge-Rombergove metode.

Iz analize grešaka u metodama numeričke integracije proizilazi da tačnost dobijenih rezultata zavisi kako od prirode promene integrala tako i od koraka integracije. Pretpostavit ćemo da smo postavili veličinu koraka. Jasno je da se u cilju postizanja uporedive točnosti pri integraciji funkcije sa slabom promjenom, korak može odabrati veći nego kod integracije funkcija koje se naglo mijenjaju.

U praksi se često dešavaju slučajevi kada se funkcija integranda različito mijenja u pojedinim dijelovima segmenta integracije. Ova okolnost zahtijeva takvu organizaciju ekonomičnih numeričkih algoritama u kojoj bi se oni automatski prilagođavali prirodi promjene funkcije. Takvi algoritmi se nazivaju adaptivni (prilagođavajući). Oni vam omogućavaju da unesete različite vrijednosti koraka integracije u pojedinačne dijelove segmenta integracije. Ovo omogućava smanjenje vremena rada mašine bez gubitka tačnosti rezultata proračuna. Naglašavamo da se ovaj pristup obično koristi kada se integrandska funkcija y=f(x) specificira u obliku formule, a ne u obliku tabele.

Razmotrimo princip rada adaptivnog algoritma. U početku, segment dijelimo na n dijelova. U budućnosti svaki takav elementarni segment dijelimo sukcesivno na pola. Konačan broj koraka, njihova lokacija i veličina zavise od integrala i dozvoljene greške e.

Za svaki elementarni segment primjenjujemo numeričke formule integracije za dvije različite particije. Dobijamo aproksimacije za integral na ovom segmentu:

Uspoređujemo dobivene vrijednosti i procjenjujemo njihovu grešku. Ako je greška u prihvatljivim granicama, tada se jedna od ovih aproksimacija uzima kao vrijednost integrala na ovom elementarnom segmentu. U suprotnom, segment se dalje dijeli i izračunavaju se nove aproksimacije. Radi uštede vremena, tačke podjele su postavljene tako da se koriste izračunate vrijednosti na prethodnim točkama podjele.

Proces dijeljenja segmenta na pola i izračunavanja ažuriranih vrijednosti nastavlja se sve dok njihova razlika ne postane ne veća od određene specificirane vrijednosti d i, ovisno o e i h:

.

Sličan postupak se provodi za svih n elementarnih segmenata. Količina se prihvata kao željena vrijednost integrala. Uslovi i odgovarajući izbor vrijednosti d i osiguravaju ispunjenje uvjeta