Drugi način da se konstruišu šeme razlike zasniva se na činjenici da se za izračunavanje vrednosti ne dobijaju rezultati jednog, već k prethodni koraci, tj. vrijednosti yi.U ovom slučaju ispada k-step method.
Metode u više koraka mogu se konstruirati na sljedeći način. Zapišimo originalnu jednačinu (1.9) u obliku
(1.28)
Integrirajmo obje strane ove jednačine X na segmentu. Integral lijeve strane
(1.29)
Da biste izračunali integral desne strane jednačine (1.28), prvo konstruirajte interpolacijski polinom Pk-1 stepen k - 1 za aproksimaciju funkcije na segmentu na osnovu vrijednosti . Nakon ovoga možete pisati
(1.30)
Izjednačavajući izraze dobijene u (1.29) i (1.30), dobijamo formulu za određivanje nepoznate vrednosti funkcije mreže u čvoru:
Na osnovu ove formule, možete izgraditi različite metode u više koraka bilo kojeg reda tačnosti. Redoslijed tačnosti ovisi o stupnju interpolacijskog polinoma, za čiju konstrukciju se izračunavaju vrijednosti mrežne funkcije na k prethodni koraci.
Široko korištena porodica metoda u više koraka su Adamsove metode. Najjednostavniji od njih, dobiven od k = 1, poklapa se sa prethodno razmatranom Ojlerovom metodom tačnosti prvog reda. U praktičnim proračunima najčešće se koristi verzija Adamsove metode koja ima četvrti red tačnosti i u svakom koraku koristi rezultate prethodne četiri. To je ono što se obično naziva Adamsovom metodom. Razmotrimo ovu metodu.
Neka se vrijednosti nađu u četiri uzastopna čvora (k = 4). U ovom slučaju postoje i prethodno izračunate vrijednosti desne strane gdje je . Kao interpolacijski polinom R 3(X) možemo uzeti Njutnov polinom (videti odeljak 2.3). U slučaju konstantnog koraka h konačne razlike za desnu stranu u čvoru Xi izgleda kao
Tada se šema razlike četvrtog reda Adamsove metode može napisati nakon potrebnih transformacija u obliku
Upoređujući Adamsovu metodu sa Runge-Kutta metodom iste tačnosti, primećujemo njenu efikasnost, jer zahteva izračunavanje samo jedne vrednosti desne strane u svakom koraku (u Runge-Kutta metodi - četiri). Ali Adamsova metoda je nezgodna jer je nemoguće započeti brojanje koristeći samo jednu poznatu vrijednost y0 . Proračun se može započeti samo iz čvora X 3, ali ne x 0..Vrijednosti y 1, y 2, y 3, potrebno za obračun y 4 se mora dobiti na neki drugi način (na primjer, Runge-Kutta metoda), što značajno komplikuje algoritam. Osim toga, Adamsova metoda ne dozvoljava (bez kompliciranja formula) promjenu koraka h tokom procesa brojanja; Metode u jednom koraku nemaju ovaj nedostatak.
Pogledajmo još jednu porodicu metoda u više koraka koje koriste implicitne šeme - metode predviđanja i korekcije(oni se nazivaju također koristeći metode “prediktor-korektor”.).Suština ovih metoda je sljedeća. U svakom koraku uvode se dva koraka koristeći metode u više koraka: korištenje eksplicitne metode (prediktor) koristeći poznate vrijednosti funkcije u prethodnim čvorovima, pronalaze početnu aproksimaciju u novom čvoru; koristeći implicitnu metodu (korektor), Kao rezultat iteracija, pronalaze se aproksimacije.
Jedna od varijanti metode prognoze i korekcije može se dobiti na osnovu Adamsove metode četvrtog reda. Predstavimo konačni oblik odnosa razlike u fazi prediktora:
u fazi lekture:
(1.33)
Eksplicitna šema (1.32) se koristi jednom u svakom koraku, a uz pomoć implicitne šeme (1.33) se gradi iterativni proces izračunavanja yi+1 jer je ova vrijednost na desnoj strani izraza
Imajte na umu da u ovim formulama, kao iu slučaju Adamsove metode, prilikom izračunavanja yi+1 potrebne su vrijednosti funkcije mreže na četiri prethodna čvora: yi, yi-1, yi-2, yi-3. Stoga, izračunavanje ovom metodom može početi samo od vrijednosti y 4. Neophodan y 1, y 2, y 3 se nalaze pomoću Runge-Kutta metode, y0 je dato početnim uslovom. Ovo je karakteristična karakteristika metoda u više koraka. Algoritam za rješavanje Cauchyjevog problema pomoću razmatrane metode predviđanja i korekcije prikazan je u uvećanom obliku na Sl. 1.4.
Rice. 1.4. Prediktor-korektor metoda
Trenutno su Adamsove metode među najperspektivnijim metodama numeričke integracije za rješavanje Cauchyjevog problema. Dokazano je da se primjenom višestepenih Adamsovih numeričkih metoda za rješavanje Cauchyjevog problema do 12. reda smanjuje područje stabilnosti. Daljnjim povećanjem reda raste područje stabilnosti, kao i tačnost metode. Osim toga, sa istom preciznošću, metode u više koraka u jednom koraku integracije zahtijevaju manje izračunavanja desnih strana diferencijalnih jednačina nego u Runge-Kutta metodama. Prednosti Adamsovih metoda uključuju činjenicu da lako mijenjaju korak integracije i redoslijed metode.
U praksi se široko koriste dvije vrste Adamsovih metoda - eksplicitne i implicitne. Eksplicitne metode su poznate kao Adams-Bashforth metode, implicitne metode su poznate kao Adams-Moultonove metode.
Razmotrimo upotrebu numeričkih metoda za rješavanje Cauchyjevog problema
Prilikom rješavanja problema (2.1) primjenom metoda u jednom koraku vrijednost yn+1 ovisi samo o informaciji u prethodnoj tački xn. Može se pretpostaviti da se veća tačnost može postići ako se koristi informacija o nekoliko prethodnih tačaka xn, xn-1...xn-k. Metode u više koraka su zasnovane na ovoj ideji.
Većina metoda u više koraka proizlazi iz sljedećeg pristupa. Ako zamenimo tačno rešenje y (x) u jednačinu (2.1) i integrišemo jednačinu na segmentu, dobićemo:
Zamjenom funkcije f (x, y (x)) u formuli (2.2) interpolacijskim polinomom P (x), dobijamo približnu metodu
Da bismo konstruirali polinom P (x), pretpostavljamo da su yn, yn-1... yn-k aproksimacije rješenja u tačkama xn, xn-1... xn-k. Pretpostavljamo da su čvorovi xi locirani jednoliko sa korakom h. Tada su fi=f (xi, yi), (i=n, n-1.. n-k) aproksimacije f (x, y (x)) u tačkama xn, xn-1... xn-k.
Kao P (x), uzimamo interpolacijski polinom stepena k koji zadovoljava uslove
Ako eksplicitno integrišemo ovaj polinom, dobićemo sljedeću metodu:
Kada je k=0, polinom P (x) je konstanta jednaka fn, a formula (2.4) se pretvara u uobičajenu Eulerovu metodu.
Za k=1, polinom P (x) je linearna funkcija koja prolazi kroz tačke (xn-1, fn-1) i (xn, fn), tj.
Integracijom ovog polinoma od xn do xn+1 dobijamo metodu u dva koraka
koji koristi informaciju u dvije tačke xn i xn+1.
Ako je k=2, onda je P(x) kvadratni polinom koji interpolira podatke (xn-2, fn-2), (xn-1, fn-1) i (xn, fn). Može se pokazati da odgovarajuća metoda ima oblik
Ako je k=3, onda je odgovarajuća metoda data formulom
Za k=4 imamo
Imajte na umu da je metoda (2.7) metoda u tri koraka, (2.8) je metoda u četiri koraka, a (2.9) je metoda u pet koraka. Formule (2.6) - (2.9) su poznate kao Adams-Bashforth metode. Metoda (2.6) ima tačnost drugog reda, pa se naziva Adams-Bashforthova metoda drugog reda. Slično, metode (2.7), (2.8) i (2.9) se nazivaju Adams-Bashforth metoda trećeg, četvrtog i petog reda.
Nastavljajući ovaj proces, koristeći sve veći broj prethodnih tačaka, kao i interpolirajući polinom višeg stepena, dobijamo Adams-Bashforthove metode proizvoljno visokog reda.
Metode u više koraka uvode poteškoće koje se ne javljaju kod jednostepenih metoda. Ove poteškoće postaju jasne ako se, na primjer, obratimo Adams-Bashforthovim metodama petog reda (2.9).
U zadatku (2.1) data je početna vrijednost y0, ali sa n=0, za izračunavanje po formuli (2.9), potrebne su informacije u tačkama x-1, x-2, x-3, x-4, što je prirodno nedostaje. Uobičajeni izlaz iz ove situacije je korištenje neke metode u jednom koraku istog reda tačnosti, kao što je Runge-Kutta metoda, sve dok se ne dobije dovoljno vrijednosti za rad metode u više koraka. Ili možete koristiti metodu u jednom koraku na prvom koraku, metodu u dva koraka na drugom i tako dalje dok se ne dobiju sve početne vrijednosti. Bitno je da se ove početne vrijednosti izračunaju sa istim stepenom tačnosti kao i konačna metoda. Pošto početne metode imaju niži red točnosti, morate računati u manjim koracima na početku i koristiti više međutočaka.
Izvođenje metoda (2.6) - (2.9) zasniva se na zamjeni funkcije f (x, y) interpolacijskim polinomom P (x). Poznato je da postoji teorema koja dokazuje postojanje i jedinstvenost interpolacionog polinoma. Ako su čvorovi x0, x1...xn različiti, tada za bilo koje f0, f1...fn postoji jedinstveni polinom P (x) stepena koji nije veći od n takav da je P (xi) =fi, i=0 , 1,.. n.
Iako je interpolacijski polinom jedinstven, postoji nekoliko načina da se ovaj polinom predstavi. Lagrangeovi polinomi se najčešće koriste, ali se ispostavljaju i da su nezgodni ako trebate dodati (ili ukloniti iz njega) bilo koji čvor skupu podataka. U ovom slučaju postoji drugačiji prikaz interpolacionog polinoma. Ovo je Newtonov prikaz
Polinom Pn+1 (x) se može zapisati kao
Reprezentacija interpolacionog polinoma u obliku (2.11) u velikom broju slučajeva može biti posebno korisna za praksu.
Adams-Bashforth metode koriste već poznate vrijednosti u tačkama xn, xn-1... xn-k. Prilikom konstruisanja interpolacionog polinoma možete koristiti i tačke xn, xn, xn-1... xn-k. Ovo dovodi do klase implicitnih metoda m koraka poznatih kao Adams-Moulton metode.
Ako je k=0, onda je P (x) linearna funkcija koja prolazi kroz tačke (xn, fn) i (xn+1, fn+1), a odgovarajuća metoda
je Adams-Moultonova metoda drugog reda.
Za k=1, 2, 3 dobijamo odgovarajuće metode
treći, četvrti i peti red aproksimacije. Relacije (2.12) - (2.15) sadrže željene vrijednosti yn+1 implicitno, stoga je za njihovu implementaciju potrebno koristiti iterativne metode.
U praksi obično ne rješavaju direktno jednačine (2.12) - (2.15), već koriste eksplicitne i implicitne oblike zajedno, što dovodi do metode predviđanja i korekcije.
Na primjer, za Adamsovu metodu drugog reda, koristeći notaciju gdje je r broj iteracije, imamo sljedeću shemu proračuna za r = 1:
Ovaj proces se naziva PECE metoda (P znači primjenu prediktivne formule, C znači primjenu formule korekcije, E znači izračunavanje funkcije f). Proces izračunavanja možete skratiti tako što ćete odbaciti posljednju formulu. Ovo dovodi do takozvane PEC metode.
Razmotrimo drugu metodu za rješavanje jednačina (2.12) - (2.15). Formule (2.12) - (2.15) se mogu prepisati kao
gdje gn sadrži poznate količine. Dokazano je da ako, gdje je L Lipschitz konstanta, onda postoji jedinstveno rješenje jednadžbe (2.17), koje se može dobiti korištenjem iterativnog procesa
gde - proizvoljno.
Iteracije u izrazu (2.18) se nastavljaju sve dok se ne postigne konvergencija. U ovom slučaju, broj proračuna funkcije f varira od tačke do tačke i može biti prilično velik.
S druge strane, ako se vrijednost h smanji, tada se konvergencija može postići u fiksnom broju iteracija. Ova metoda se zove korekcija konvergencije.
Na prvi pogled može izgledati da je eksplicitna metoda u više koraka najjednostavnija metoda sa računske tačke gledišta. Međutim, u praksi se eksplicitne metode koriste vrlo rijetko. Implicitna Adams-Moultonova metoda je preciznija od eksplicitne Adams-Bashforth metode. Na primjer, računska shema za Adams-Moultonov metod 5. reda je sljedeća:
Adamsove metode do petog reda uključivo mogu se koristiti za rješavanje običnih diferencijalnih jednačina koje ne zahtijevaju visok stepen tačnosti.
Kao iu slučaju Adams-Bashforth metode, kada se koristi Adams-Moultonova metoda, važno pitanje je izbor optimalnog odnosa između koraka integracije i redoslijeda metode. Treba napomenuti da je kod kreiranja efikasnih algoritama i programa, povećanje redosleda metode poželjnije od smanjenja koraka integracije.
Za rješavanje složenijih problema potrebno je primijeniti Adamsove metode višeg reda. Tabela 2.1 prikazuje vrijednosti koeficijenata za Adamsove metode. Prvi red pokazuje redosled metode; u drugom - vrijednosti koeficijenata Ck za odgovarajući red k; u sljedećim redovima - parovi koeficijenata Bkj i Mkj za Adams-Bashforth i Adams-Moulton metode, respektivno. Zatim, uzimajući u obzir podatke u tabeli 2. 14, koeficijenti u j u izrazu
jer se Adams-Bashforthova metoda k-tog reda može naći iz relacije
i za Adams-Moultonovu metodu k-tog reda koristeći sličnu formulu
Formule za Adamsove metode korekcije prediktora od 6. do 14. reda su sljedeće:
- 6. red:
- 7. red:
- 8. red:
- 9. red:
- 10. red:
- 11. red:
- 12. red:
- 13. red:
- 14. red:
- 15. red:
- 16. red:
Poželjno je koristiti gore navedene formule za praktičnu primjenu rješavanja običnih diferencijalnih jednadžbi ili sistema diferencijalnih jednadžbi prvog reda sa konstantnim korakom integracije. Ako je u procesu rješavanja jednadžbe korak integracije promjenjiv, tada za Adamsove metode postoje posebne tehnike za unos novih početnih podataka prilikom promjene koraka integracije.
At S= 1 formula (6.16) poprima oblik
Ako Q= 2, dobijamo sledeće računsko pravilo:
Obično se u praksi koristi ekstrapolaciona formula (6.18), a zatim se dobijena vrednost koriguje pomoću formule (6.23). A ako rezultat prilagođene vrijednosti ne prelazi dozvoljenu grešku u proračunu, onda korak H smatra prihvatljivim 
.
Za proračune na računaru, formule (6.18) i (6.23) u obliku konačnih razlika su nezgodne. Uzimajući u obzir (6.21), oni se mogu predstaviti u obliku
(6.24)
Navedene formule su prilično tačne. Daju grešku u redosledu ~ O(H4), ali same formule za procjenu greške su prilično složene. Greška se može približno procijeniti korištenjem Rungeovog pravila.
Primjer 6.2. Riješite diferencijalnu jednačinu na segmentu s početnim uvjetom Y(X= 0) = 1. Pronađite Adamsovom metodom (sa korekcijom) u tački X4 , u prve tri tačke pronađite Runge-Kutta metodom, uzimajući korak .
Rješenje. Uzimamo vrijednosti funkcije u prve četiri tačke iz tabele. 6.1 (pogledajte primjer u prethodnom dijelu). Sada je postalo jasno zašto smo sačuvali vrijednosti prvog izvoda u ovim točkama (vidi formule (6.24)).
X4 = X3 + H= 0.15 + 0.05 = 0.2;
Da bi se ispravio dobijeni rezultat, potrebno je izračunati vrijednost derivata u ovom trenutku:
Sada razjasnimo vrijednost pomoću interpolacijske formule (ili to ne morate učiniti, tada će greška metode biti veća):
Pošto se ispravljena vrijednost uzima kao nova vrijednost funkcije, onda Neophodno Vrijednost derivata treba ponovo izračunati. U našem slučaju, modul razlike između ekstrapolacijske i interpolacijske formule je manji od ε , Što vam omogućava da nastavite računanje istim korakom.
Pitanja za samotestiranje
· Formulirati Cauchyjev problem za obične diferencijalne jednadžbe prvog reda.
· Koje je rješenje diferencijalne jednačine: a) u višoj matematici, b) u primijenjenoj matematici?
· Koje metode diferencijalnih jednačina se nazivaju jednostepenim, višestepenim? Navedite primjere.
· Uporedite vrednosti dobijene u prvom i drugom koraku korišćenjem metoda proširenja Euler, Runge-Kutta i Taylor serije (intenzitet rada, greška...).
· Kako procijeniti grešku korištene metode? Kako to smanjiti?
· Uporedite jednostepene i višestepene metode za rešavanje diferencijalnih jednačina, ukazujući na prednosti i nedostatke prve i druge.
· Koje su Adamsove metode ekstrapolacije i interpolacije (formule)?
· Da li je moguće koristiti: a) samo Adamsove ekstrapolacijske metode,
b) samo interpolacija?
· Da li je moguće koristiti: a) višestepene metode bez jednostepenih;
b) jednostepene metode bez višestepenih?
· Kod rješavanja diferencijalne jednadžbe Adamsovom metodom, u 27. koraku potrebno je promijeniti korak. Kako uraditi?
I dalje imamo isti Cauchy problem.
f (1) (t)=F(t, f(t)), a£ t£ b, f(a)=f a.
U metodama u jednom koraku vrijednost f(tk+1) određena je samo podacima iz prethodne tačke tk. Čini se da je moguće povećati tačnost rješenja korištenjem informacija u nekoliko prethodnih tačaka, ako su dostupne. To je ono što se radi u metodama koje se nazivaju višekorak. Već na prvi pogled na konstataciju problema postaje očigledno da u trenutku početka t=t a postoji samo jedan početni uslov i, ako ćemo raditi sa dve, tri ili četiri prethodne tačke, onda ne postoji način da dobijemo drugi, osim korišćenjem metoda u jednom koraku. To je ono što oni rade; “složeni” algoritam rješenja može izgledati ovako:
u prvom koraku, druga točka se dobija metodom u jednom koraku, u drugom se dobija treća metodom u dva koraka, u trećem, četvrta se dobija metodom u tri koraka, itd., dok se ne prikupi dovoljno prethodnih bodova za glavnu metodu koja bi se trebala koristiti.
Druga opcija je da dobijete ceo početni skup tačaka koristeći metodu u jednom koraku, kao što je Runge-Kutta četvrtog reda. Kako se pretpostavlja da su višestepene metode preciznije, za početnu jednostepenu metodu obično se koristi veći broj međutačaka, tj. raditi kraćim koracima.
Algoritmi u više koraka mogu se kreirati ovako. S obzirom na to
f(tk +1)=f(tk)+ ,
možemo numerički integrirati desnu stranu ODE pod predznakom integrala. Ako koristimo metodu pravokutnika (interpolacijski polinom za integrabilnu funkciju je konstanta), dobijamo uobičajenu Eulerovu metodu. Ako koristite 2 točke i interpolacijski polinom prvog reda
str(x)= ,
zatim integracija pomoću trapezoidne metode iz tk prije tk+1 će dati sljedeći algoritam:
f(tk +1)=f(tk)+0.5h(3F k-F k -1).
Slično, za tri tačke ćemo imati kvadratni interpolirajući polinom prema podacima ( tk -2 , F k -2), (tk -1 , F k -1), (tk, F k) i integracija pomoću Simpsonove metode će dati algoritam:
f(tk +1)=f(tk)+ (23F k–16F k -1 +5F k -2).
Za 4 boda polinom će biti kubičan i njegova integracija će dati:
f(tk +1)=f(tk)+ (55F k–59F k -1 +37F k -2 –9F k -3).
U principu, mogli bismo tako nastaviti u nedogled.
Dati algoritmi se nazivaju Adams-Bashforth metoda drugog, trećeg i četvrtog reda.
Formalno, kada se konstruiše interpolacioni polinom, pored N koristite već izračunate bodove i još mnogo toga R budućnost tk +1 , tk+2 ; u najjednostavnijem slučaju skup
tk +1 , tk, tk -1 ,…, tk -N .
Ovo generiše klasu takozvanih Adams-Moultonovih metoda. U verziji sa četiri koraka, radi na podacima ( tk +1 , F k +1), (tk, F k), (tk -1 , F k -1), (tk -2 , F k-2) i njegov algoritam:
f(tk +1)=f(tk)+ (9F k +1 +19F k–5F k -1 +F k -2).
Naravno, nemoguće je izvršiti proračune na osnovu podataka koji nedostaju, pa se Adamsovi algoritmi kombinuju u niz Adams-Bashforth i Adams-Moulton algoritama, čime se dobijaju takozvane metode prognoze i korekcije. Na primjer, metoda predviđanja i korekcije četvrtog reda izgleda ovako: prvo predviđamo koristeći Adams-Bashforth algoritam koristeći "prošle" točke
f(tk +1)=f(tk)+ (55F k–59F k -1 +37F k -2 –9F k -3).
Zatim izračunavamo približnu vrijednost desne strane jednačine
F k +1 =F(tk +1 , f(tk +1).
I konačno, prilagođavamo se f(tk+1) koristeći njegovu približnu vrijednost
f(tk +1)=f(tk)+ (9F k +1 +19F k–5F k -1 +F k -2).
Najefikasniji dostupni kompjuterski programi koji omogućavaju korisniku da promeni veličinu koraka i redosled metoda zasnovani su na Adamsovim metodama visokog reda (preko 10). Iskustvo sa ovim programima pokazuje da razlike u njihovoj implementaciji mogu imati značajniji uticaj na tačnost od razlika u unutrašnjim svojstvima samih metoda.
Adamsova eksplicitna šema.
Gore opisane metode su izričito jednostepene (da bi se pronašla sljedeća aproksimacija, koristi se samo jedna prethodna). Metoda u nastavku je višestepena.
Neka je zadan Cauchyjev problem:
Za tačno rješenje (koje ne znamo) vrijedi sljedeće:
Pretpostavimo da znamo približne vrijednosti funkcije u(x) u k tačaka (početnih k tačaka, posebno, može se pronaći Eulerovom metodom ili Runge-Kutta metodom jednog ili drugog reda), tada funkcija f (x, u(x)) u (2.4.2) za približno izračunavanje integrala može se zamijeniti interpolacijskim polinomom reda k-1, konstruiranim preko k tačaka, čiji se integral izračunava eksplicitno i predstavlja linearna kombinacija vrijednosti sa određenim faktorima. Tako dobijamo sljedeću rekurentnu proceduru za izračunavanje približnih vrijednosti funkcije u(x) (koja je tačno rješenje Cauchyjevog problema) u tačkama:
Opisana shema je k-korak eksplicitna Adamsova formula.
Adamsova implicitna shema.
Neka je interpolacijski polinom reda k, konstruiran od k+1 vrijednosti, od kojih ćemo jednu, naime, smatrati nepoznatom. Modificirajmo (2.4.3) tako što ćemo je zamijeniti polinomom višeg stepena, čiji je integral izražen kao linearna kombinacija vrijednosti sa nekim novim koeficijentima:
Formula (2.4.4) je implicitna Adamsova šema i jednačina je za koju se može riješiti metodom uzastopnih aproksimacija. Naravno, početna aproksimacija mora biti mudro odabrana. Da biste to učinili, zgodno je kombinirati eksplicitnu i implicitnu Adamsovu shemu u jednu, nazvanu “metoda korekcije”. Uz pomoć eksplicitne šeme određuje se početna aproksimacija (predviđanje), a zatim se, koristeći implicitnu shemu, koriguje potreban broj puta (obično jedan ili dva) metodom uzastopnih aproksimacija sve dok se ne postigne određeno postignuta je tačnost (ispravka).