Taikomoji diskrečioji matematika - algoritmai

1. Uždavinio sąlyga ir jo analizė • Sudaryti procedūrą, kuri įgalintų apskaičiuoti tikslumu epsilion. Naudoti Simpsono kvadratūrinę formulę ir Adaptyviojio integravimo strategija. • Norint apskaičiuoti Simpsono metodu, kvadratūrinė formulė išvedama taip. Pirmiausia intervalas taškais padalijamas į lygių dalių ir kiek­­vie­noje jų taikoma Simpsono kvadratūrinė formulė , kurios , o . Tada visi rezultatai sumuojami ir gaunama apibendrinta Simpsono kvadratūrinė formulė: . Matome, kad ji susijusi su integravimo strategija: integravimo intervalas da­li­jamas į lygių dalių. Jei integravimo intervale yra sričių, kuriose pointegralinė funkcija kinta sparčiau nei kitose integravimo intervalo srityse, tai taikyti to­kią strate­giją būtų neprotinga. Šiuo atveju, norint apskaičiuoti integralą tam tikru tiks­lumu, reikėtų visame integravimo intervale imti tokį inte­gra­vimo žingsnį h, kuris ga­ran­tuotų reikiamą tikslumą srityse, kuriose funk­cija kinta sparčiausiai, ne­paisant to, kad srityse, kuriose funkcija kinta lėčiau, reikiamas tikslumas ga­li būti pasiektas esant didesniam integra­vimo žingsniui. Vadinasi, taikant šią stra­tegiją, bus naudojama per daug pointegralinės funkcijos reikšmių, todėl padidės in­tegra­vimo paklaidos. Paprastai norimą integravimo tikslumą stengiamasi pasiekti imant kuo ma­žiau pointegralinės funkcijos reikšmių. Todėl pastaruoju metu taikoma adapty­viojo integravimo strategija. Tarkime, kad norime apskaičiuoti reikšmę tikslumu , integravimui taikydami kvadratūri­nę for­mulę, kurios liekamasis narys proporcingas ; čia h — integravimo žingsnis. Adaptyviojo integravimo strategijos idėja labai paprasta: inter­valas dalijamas į trumpesnius intervalus ten, kur pointegralinė funk­­cija kinta sparčiau, ir į ilgesnius intervalus ten, kur ji kinta lėčiau. Kiekvienam intervalui taikoma pasirinkta kvadratūrinė formulė, o intervalas imamas tokio ilgio, kad jame integravimo paklaida būtų ne didesnė už ; čia — intervalo ilgis. Tada integravimo paklaida visame intervale bus ne didesnė kaip . 2. Algoritmo aprašymas Adaptyviojo integravimo strategija vykdoma taip: 1) apskaičiuojamas integravimo intervalo ilgis ; 2) kvadratūrinė formulė taikoma intervale ir gaunama integralo reikšmė ; čia h žymi integravimo žingsnį; 3) apskaičiuojama ; čia ir — integralo R reikšmės atitinkamai integravimo intervalo kairiajame ir dešiniajame pusintervalyje, kai integravimo žingsnis ; 4) jei , tai nagrinėjamame intervale integravimo tikslumas yra nepakankamas. Tada dešiniojo pusintervalio integralo reikšmę , integravimo abscises bei jas atitinkančias pointegralinės funkcijos reikšmes įsimename; integravimo intervalą imame lygų kairiajam pusintervaliui, t. y. , , ir grįžtame į 3 punktą. Jei , tai nagrinėjamame intervale, kurio ilgis H, integravimo tikslumas yra pasiektas ir . Toliau, jei yra, nagrinėjame dešinįjį pusintervalį, t. y. , suren­kame įsimintas jo integravimo abscises bei tas abscises atitinkančias pointe­gra­linės funkcijos reikšmes, integravimo intervalą imame lygų dešiniajam pus­intervaliui, apskaičiuojame intervalo integravimo ilgį H ir grįžtame į 3 punktą. Jei nagrinėtų dešiniųjų pusintervalių nėra, tai integralo R reikšmė tikslu­mu lygi visų sumai. Skaičiavimas laikantis adaptyviojo integravimo strategijos vykdomas pagal binarųjį medį. Nesunku pastebėti, kad adaptyviojo integravimo strategijos organiza­vimas yra sudėtingesnis nei vienodo žingsnio visame integravimo intervale strategijos, tačiau, taikant adaptyviojo integravimo strategiją, norimas in­te­gravimo tikslu­mas pasiekiamas esant gerokai mažesniam pointegralinės funkcijos reikšmių skaičiui. a) b) Binarusis medis (a) ir jį atitinkantis integravimo intervalo skaidymas į subintervalus (b) 3. Programos tekstas unit Unit1; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, TeEngine, Series, ExtCtrls, TeeProcs, Chart; const n = 30; const m = 8; type funkcija = function (x:real):real; mas1 = array[0..n+1] of real; mas2 = array[0..2*m] of real; matr = array[0..m,0..n] of real; TForm1 = class(TForm) Edit1: TEdit; Edit2: TEdit; Edit3: TEdit; Label1: TLabel; Label2: TLabel; Label3: TLabel; Memo1: TMemo; Button1: TButton; Button2: TButton; Chart1: TChart; Series1: TFastLineSeries; procedure Button1Click(Sender: TObject); procedure FormCreate(Sender: TObject); procedure FormActivate(Sender: TObject); procedure Button2Click(Sender: TObject); private { Private declarations } public a, b, ar, rr:real; r,er,flag:real; nn:integer; eps:integer; procedure rc8(ff:funkcija; a,b,ar,rr:real; var r,er,flag:real; var nn:integer); { Public declarations } end; var Form1: TForm1; implementation {$R *.DFM} function funk(x:real):real; begin result := x*x + 6*cos(x); end; function funk2(x:real):real; begin result := x + Ln(x); end; procedure TForm1.rc8(ff:funkcija; a,b, ar, rr:real; var r,er, flag:real; var nn:integer); var levmax,levout,nmax,nf,lev,i,j,nim,pw, poz,sgn :integer; w0,w1,w2,w3,w4,area,stone,step,cor11,temp, qprev,qnow,qdiff,qleft,esterr,tolerr,c :real; qright :mas1; f,x :mas2; fsave,xsave :matr; { Funkcija rc8 apskaiciuoja apibrežtini integrala adaptyviojo integravimo metodu Formalus parametrai: f - vardas funkcijos, apskaiciuojancios pointegraline funkcija, a - apatinis integravimo režis, b - viršutinis integravimo režis, r - integralo reikšme, nn - integruojant panaudotu funkcijos reikšmiu kiekis, } begin levmax:=30; levout:=6; nmax:=5000; pw:=1; for i:=1 to levout+1 do pw:=pw*2; nf:=nmax-8*(levmax-levout+pw); { Jei nn pasiekia nf reikšme, tai pointegraline funkcija nurodytuose integravimo režiuose gali buti truki } { 8-osios eiles Niutono ir Koteso kvadraturines formules koeficientai } c:=14175.; w0:=3956./c; w1:=23552./c; w2:=-3712./c; w3:=41984./c; w4:=-18160./c; { Pradiniu reikšmiu suteikimas kintamiesiems } flag:=0.; r:=0; cor11:=0.; er:=0.; nn:=0; lev:=0; nim:=1; poz:=1; if a tolerr) and (lev = levmax ) then flag:=flag+1; { Funkcijos reikšmiu skaicius artimas ribiniam } if ( nn > nf ) then begin nf:=2*nf; levmax:=levout; flag:=flag+(b-x[0])/(b-a) end; { Tikslumo salyga i-tajame intervale tenkinama } r:=r+qnow; er:=er+esterr; cor11:=cor11+qdiff/1023.; { Rasti kita intervala } while ( (nim mod 2) 0 ) do begin nim:=nim div 2; lev:=lev-1 end; nim:=nim+1; if (lev 0. ) then begin temp:=abs(r)+er; while ( temp = abs(r) ) do begin er:=er*2.; temp:=abs(r)+er end end end; procedure TForm1.Button1Click(Sender: TObject); begin a := StrToInt(Edit1.text); b := StrToInt(Edit2.text); eps := StrToInt(Edit3.text); rc8(funk, a, b, ar, rr, r, er, flag, nn); Memo1.Lines.Add('----------------------------------------'); Memo1.Lines.Add('| a | b | eps | apsk. |'); Memo1.Lines.Add('----------------------------------------'); Memo1.Lines.Add('| ' + FloatToStr(a) + ' | ' + FloatToStr(b) + ' | ' + IntToStr(eps) + ' | ' + FloatToStrF(r,ffFixed,8,eps)+' |'); { while (j

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!