Skaitinių teorija


Netiesiniu lygciu sistemu sprendimo metodai Siuo metodu paskaiciuojama netiesines lygciu sistemos f(x)=0 kintamieji norimu tixlumu. Simpleksų metodas. Siuo metodu sprendziami f-jos optimizavimo uzdaviniai, ty randamas optimalus uzdavinio sprendinys.


1.1 Apytiksliai skaičiai ir paklaidos skaičiaus a artinio x absoliučiąja paklaida vadinamas to skaičiaus ir jo artinio skirtumo modulis: ∆a = |a-x| |(a+b)-(x+y)|=|(a-x)+(b-y)|<=|a-x|+|b-y|= ∆a+∆b Dvieju apytixliu skaiciu sumos ar skirtumo absoliucioji paklaida yra ne didesne uz tu skaiciu absoliuciuju paklaidu suma. Skaiciaus a artinio x santykine paklaida vadinama absoliucios paklaidos ir skaiciaus a modulio santykis. 1.taisykle skaiciavimo algoritmus reikia sudaryti taip, kad nebutu atimami dideli (palyginti su skirtumu) vienodo didumo skaiciai.Nustatome apytiksliu skaiciu sandaugos santykine paklaidaPanasiai irodoma ir dalmens santyk.paklaida

2.1 Interpoliavimas Niutono interpoliacinis daugianaris:: Iš šios formulės pavidalo matyti viena svarbi ypatybė-jei yra žinoma užtektinai funkcijos f(x) reikšmių, Niutono interpoliacinę formulę lengvai galima papildyti naujais nariais ir kartu padidinti jos tikslumą.Tai svarbu, jei atliekant experimenta gaunami nauji matavimo duomenys (xi,f(xi)) ir reikia apskaiciuoti naujas tarpines f-jos reiksmes.TEOREMA. Jei (n+1)-oji funkcijos f(x) isvestine intervale [x0,xn] yra aprezta, tai Niutono interpoliacines formulas paklaida ivertinama: , cia Mn+1 yra f –jos f(x) (n+1)-osios isvestines rezis |f(n+1)(x)|<=Mn+1. Is sios teoremos galima padaryti 2 isvadas.Pirma, nevisais atvejais yra naudinga didinti interpoliacinio daugianario laipsni. Is paklaidos ivercio matyti, kad didinti laipsni tixlinga tada kai (n+1)-oji f-jos isvestine nera daug didesne uz n-taja isvestine ir taskas xn nera perdaug nutoles nuo tasko x, kai galioja nelygybe: Antroji isvada yra apie interpoliavimo mazgu isdestyma. Reikia siekti, kad sie mazgai butu kuo arciau interpoliavimo tasko x ir issideste simetriskai jo atzvilgiu.

2.2 Splainas Splaino apibrėžimas Tarkime, kad funkcija y=f(x) yra apibrėžta reikšmių lentele, yi=f(xi), i=0,1,2...N, ir visame funkcijos f(x) apibrėžimo intervale [x0,xN] dalyje. Toks interpoliavimas vadinamas dalimis daugianarių funkcijų interpoliavimu . Sakykime, kad intervale [a,b] yra apibrėžta funkcija y=f(x), tame intervale pasirinkime N+1 tašką a=x0, x1, x2,..., xN=b ir kiekviename daliniame intervale [xi,xi+1] aproksimuokime funkciją f(x) m – tojo laipsnio daugianariu. Si(x)=aixm+ ai1xm-1+...+ aim-1x+ aim Parinksime tokius šio daugianario koeficientus, kad gautoji funkcija ir visos jos išvestinės iki (m-1) – osios eilės imtinai būtų tolydžios kiekviename intervalo [a,b] taške; tokią interpoliacinę funkciją vadinsime m – osios eilės splainu. Splaino užrašymo formos: 1. kiekviename intervale [xi-1 ; xi] nurodoma polinomo išraiška, t.y. dalimis polinominė forma 2.splainas užrašomas tiesine B splainų kombinacija.

3.1 Pusiaukirtos metodas. Siuo metodu paskaiciuojama netiesines lygciu sistemos f(x)=0 kintamieji norimu tixlumu. {Bolcano ir Koši Teorema. Jei funkcija f(x) yra tolydi intervale [a,b] ir šio intervalo galuose įgyja priešingų ženklų reikšmes, tai tarp a ir b yra toks taškas c, a

3.2 Relaksacijos metodas Siuo metodu paskaiciuojama netiesines lygciu sistemos f(x)=0 kintamieji norimu tixlumu. Tarkime, kad funkcijos ((x) išvestinė yra neigiama ir aprėžta: -M((((x) (m<0. Jei M>1, tai paprastųjų iteracijų metodas xn+1=((xn) diverguoja – (n+1) artinys yra toliau nuo tiksliojo sprendinio negu n-asis. Tačiau jei (n+1)-uoju artiniu laikytume n-tojo ir (n+1)-ojo paprastųjų iteracijų metodo artinio xn+1 tiesinę kombinaciją, t.y. xn+1=(1-()xn+(((xn), tai naujasis artinys, specialiai parinkus parametrą (, būtų geresnis negu n-asis. Šis metodas ir yra vadinamas relaksacijos metodu. Skaičius ( - relaksacijos parametras. Paaiškinsime, kaip nustatoma optimalioji šio parametro reikšmė, su kuria greičiausiai pasiekiamas reikiamas tikslumas. Įrašykime tikslųjįlygties sprendinį x į relaksacijos metodo formulę x((1-()x+(((x), ir panariui atimkime iš jos gautąją tapatybę: zn+1=(1-()zn+((((xn)- ((x)), čia pažymėjome zn+1=xn+1-x ir zn=xn-x; dydis zn yra relaksacijos metodo paklaida. Pritaikę Lagranžo formulę funkcijos ((x) reikšmių skirtumui, ((xn)- ((x)= (((()(xn-x), (=xn+((xn-x), |(|<1, gausime lygtį, kurios nežinomasis yra relaksacijos metodo paklaida: zn+1=(1-((1+|(((()|))zn =q((,(()zn. Optimalioji relaksacijos parametro reikšmė (0 yra paklaidos zn+1 minimumo uždavinio min( maxm(|((| (M |q((,(()|=|q((0,(()| sprendinys. Kadangi q=1-((1+|(((()| yra tiesės lygtis kintamojo ( atžvilgiu, tai (0 yra lygties 1-(0(1+m)= (0(1+M)-1 sprendinys: (0=2/2+m+M.

3.3 Niutono metodas. Siuo metodu paskaiciuojama netiesines lygciu sistemos f(x)=0 kintamieji norimu tixlumu. Pasirinkime pradinį lygties f(x)=0 sprendinio c artinį x0, apskaičiuokime funkcijos reikšmę f(x0) ir taške (x0,f(x0)) nubrėžkime funkcijos f(x) liestinę – jos lygtis yra y-f(x0)=f((x0)(x-x0). Šios liestinės ir Ox ašies susikirtimo taškas apskaičiuojamas įrašius į liestinės lygtį nulį vietoj y: x=x0-f(x0)/f((x0). Šis taškas yra arčiau sprendinio negu pradinis artinys. Pažymėkime x1: x1=x0-f(x0)/f((x0). Šiame taške vėl apskaičiuokime funkcijos reikšmę f(x1), taške (x1;f(x1)) nubrėžkime liestinę ir raskime jos susikirtimo tašką x2. Kartodami šį procesą, gausime iteracinę seką x0,x1,x2,...,xn,..., kurios nariai apskaičiuojami pagal tokią taisyklę: xn+1=xn-f(xn)/f((xn). Nustatysime sąlygas, kuriomis Niutono metodas konverguoja. TEOREMA. Jei, pirma, lygtis f(x)=0 turi sprendinį, antra, pirmoji funkcijos f(x) išvestinė nelygi nuliui, t.y. |f((x)|(M1>0, trečia, antroji funkcijos f(x) išvestinė aprėžta, |f(((x)|(M2, ir ketvirta, pradinis artinys x0 yra pakankamai arti tiksliojo sprendinio, tai Niutono metodo iteracijų seka konverguoja į tikslųjį sprendinį, ir (n+1)-osios iteracijos paklaida įvertinama tokia nelygybe: |xn+1-c|( (M2/2M1)(|xn-c|2.

3.4 Netiesiniu lygciu sistemu sprendimo metodai Siuo metodu paskaiciuojama netiesines lygciu sistemos f(x)=0 kintamieji norimu tixlumu. Bendruoju atveju, nagrinesime n netiesiniu lygciu sistemu. Sia lygciu sistema uzrasysime vektoriniu pavidalu: f(x)=0. Cia x=(x1, x2...xn). Kai kurie metodai, naudojami neties. lyg. sist. spresti: Paprastuju iteraciju metodas: perrasykime vektorine lygti f(x)=0 tokiu pavidalu: x=S(x). Jei yra zinomas k-asis vektoriaus x artinys , tai naujaji artini apskaiciuosime pagal tokia taisykle:. Konvergavimo salygos: Apibrezimas: Vektoriaus X norma vadinamas skaicius, zymimas ||X||, turintis sias savybes: 1. ||X||>0, jei X ( 0 ir ||0||=0, cia 0=(0,0...0)- nulinis vektorius. 2. ||cX||=|c| ||X||, cia c – skaicius. 3. ||X+Y||<= ||X||+||Y||. Apibrezimas: f-ja S(x) yra vadinama spudine f-ja n-maciu vektoriu aibeje V, jei yra toks skaicius q((0, 1), kad su bet kurio x’ ir x” (V galioja nelygybe ||S(x’)-S(x’’)||(q||x’-x’’||. Teorema. Sakykime, kad vektoriaus a aplinkoje Bz(a)={x:||x-a||(z} yra apibrezta spudine funkcija S(x). Jei nelygybe ||S(x)-a||((1-q)z galioja aplinkoje Bz(a), tai joje yra vienintelis vektorines lygties x=S(x) sprendinys x*, ir paprastuju iteraciju seka su bet kokiu pradiniu artiniu x0, priklausanciu aplinkai Bz(a), konverguoja i si sprendini, o k-ojo artinio paklaida ivertinama tokia nelygybe: . Pikaro metodas: Tarkime, kad f(x)=Ax+G(x), cia A yra kvadratine n-osios eiles matrica. Sudarome iteracini procesa vadinama Pikaro metodu. Juo skaiciuojant, kiekvienoje iteracijoje reikia spresti tiesiniu lygciu sistema. Jei funkcija yra spudine, tai Pikaro metodu gaunama iteracine seka konverguoja. Isreikstinis iteracinis metodas. Daugeliu atveju konverguojantis iteracinis procesas gaunamas lygciu sistema pertvarkius tokiu pavidalu:, cia - iteracinis parametras, parenkamas taip, kad procesas konverguotu greiciausiai. Sio iteracinio metodo funkcija S(x)=x-f(x). Niutono metodas. Paprastuju iteraciju ir Pikaro metodas konverguoja tiesiniu greiciu. Netiesiniu lygciu sistemoms apibendrinsime Niutono metoda, kurio konvergavimo greitis yra yra kvadratinis. Tam funkcija fi(x1,x2,x3...xn) pakeisime Teiloro eilutes taske xk skleidiniu su nariais iki pirmojo laipsnio imtinai. Irase gauta reiskini i lygti, gausime tiesiniu lygciu sistema, kuria apibreziamas Niutono metodas netiesiniu lygciu sistemoms spresti:, cia yra Jakobio matrica, kurios elementai yra funkcijos f(x) isvestiniu reiksmes taske xk. Skaiciuojant Niutono metodu, kiekvienoje iteracijoje tenka apskaiciuoti Jakobio matricos elementus – n2 skaiciai, o po to isspresti tiesiniu lygciu sistema, todel sio metodo realizacija yra sudetingesne negu anksciau nagrinetuju. Isaldytasis Niutono metodas. Kadangi skaiciuojant Niutono metodu didesnioji aritmetiniu veiksmu dalis tenka Jakobio matricai apskaiciuoti ir isspresti gautaja lygciu sist., tai isaldytuoju Niut. Metodu atvirkstine Jakobio matrica perskaiciuojama tik kas m-aja iteracija. Jei f-ja f(x) yra sudetingo pavidalo, tai skaiciuojant dalines isvestines (ju yra), reikia atlikti daug aritmetini veiksmu, todel patartina Jakobio matricos elementus – dalines isvestines pakeisti baigtiniu skirtumu artiniais. Netiesiniai iteraciniai metodai yra pagristi tuo, kad neties. lyg. sistemos sprendimas yra pakeiciamas nepriklausomu lygciu arba mazesnes eiles sistemu sprendiniu. Skaiciuodami viena artini, turime isspresti n nepriklausomu netiesiniu lygciu. Jei kiekvienoje lygtyje vartosime ankstesneje lygtyje apskaiciuota artinio komponente, tai gausime Zeidelio metodo apibendrinima. Jei is uzdavinio fizines prasmes yra zinoma, kad keli sistemos nezinomieji yra glaudziai susije, tai visa sistema galima suskaidyti mazesnes eiles blokais, susiejanciais tuos nezinomuosius.

4.1 Gauso metodas. Tai tiesinių algebrinių lygčių sistemų sprendimo metodas, kuriuo per baigtinį žingsnių skaičių gaunamas tikslusis sprendinys (jei nedaroma apvalinimo paklaidų). Šio metodo esmė yra matricos pertvarkymas į viršutinę trikampę matricą. Sistema yra pertvarkoma taip kad antrojoje lygtyje neliktų nario su nežinomuoju x1, trečiojoje – narių su nežinomaisiais x1 ir x2, ir tt., n-tojoj lygtyje liktų tik narys su nežinomuoju xnAtbuline Gauso metodo eiga, pradedant nuo xn, iš pertvarkytos sistemos apskaičiuojami visi sistemos nežinomieji. Jei ant pagrindinės įstrižainės yra nulis arba labai mažas skaičius reikia sukeisti lygtis vietom, taip kad ant įstrižainės neliktų tokių skaičių, nes dalyba iš nulio negalima, o dalyba iš mažo sk. Gali sukelti dideles paklaidas. Šis met.tinka ir sistemoms kurios turi be galo daug spr. (neapibrėžtom) ir visai neturinčiom spr.- nesuderintom sist. Lygtys sukeičiamos vietomis taip kad k-tąja lygtimi taptų ta kurios koef.modulių suma yra mažiausia: .

4.2 Triįstrižainės sistemos. Tai tiesinių algebrinių lygčių sistemų sprendimo metodas, kuriuo per baigtinį žingsnių skaičių gaunamas tikslusis sprendinys (jei nedaroma apvalinimo paklaidų Jei kiekvienoje lygtyje yra tik po tris nenulinius koef.- pagr.sistemos įstrižainėj ir abiejose gretutinėse, tai tokios sistemos yra vad.triįstrižainėm ir sprendžiamos modifikuotu Gauso metodu vadinamu perkelties metodu: . Pirmąją lygtį dalijame iš įstrižainės elemento b1 ir išreiškiame x1. , žymėkim C1=-c1/b1, D1=d1/b1: x1=C1x2+D1. Iš antros lygties pašalinsim x1 ir išreikšim x2: , kur , . Tęsiant nežinomųjų šalinimą iš i-tosios lygties išreiškiamas xi: xi=Cixi+1+Di, kur , . Paskutinėj n-ojoj, lygtyje cn=0, todėl Cn=0 ir xn=Dn. Žinant xn reikšmę, kiti nežinomieji nuosekliai apskaičiuojami iš grįžtamosios xi=Cixi+1+Di, i=n-1, n-2,..., 1.

4.3 Skaidos metodai (LU ir Choleckio). (LU)Tai tiesinių algebrinių lygčių sistemų sprendimo metodas, kuriuo per baigtinį žingsnių skaičių gaunamas tikslusis sprendinys (jei nedaroma apvalinimo paklaidų). Skaidos metodu lygčių sistemos AX=F matricą A išskaidoma į dviejų trikampių matricų sandaugą, A=LU, matricos L įstrižainės el. lygūs vienetui ( LUX=F. Sprendinys randamas išsprendus šias lygčių sistemas: LY=F ir UX=Y. Gauso metodu ekvivalenčiais pertvarkiais (lygtis dauginama iš skaičiaus,nelygaus nuliui. Dvi lygtys keičiamos vietom. Sudedamos lygtys. Jų sprendinių aibės sutampa) pradinė lygčių sistema paverčiama į viršutinę trikampę sistemą, ty.apskaičiuojami matricos U elementai. i-ajame žingsnyje padauginus i-ąją matricos A eilutę iš daugiklio k=i+1, i+2, ..., n, ir atėmus ją iš k-osios eilutės, visi i-ojo stulpelio elementai, esantys po įstrižaine, tampa lygūs nuliui, o kiti elementai apskaičiuojami taip: akj=akj-lkiaij, j=i+1, i+2,.., n. Laisvųjų narių stulpelio elementai po šių pertvarkių išreiškiami taip: y1=f1, , k=2,3,..,n, arba LY=F. Apatinės trikampės matr.L elementai yra tiesioginiai Gauso metodo eigos daugikliai lki, i=1,2,..,n-1, k=i+1, i+2, ...,n. (Choleckio) Matrica A turi būti simetrinė ir teigiamai apibrėžta. APIBRĖŽIMAS kvadratinė n-osios eilės matrica vadinama simetrine jei aij=aji, . APIBRĖŽIMAS kvadratinė n-osios eilės matrica yra teigiamai apibrėžta, jei su betkuriuo nenuliniu vektorium X galioja nelygybė (AX,X)>0. Reikia rasti apatinę trikampę matr.L kad matrica būtų lygi matricos L ir jos transponuotosios matr.LT sandaugai A=L*LT. Iš šios lygybės rasime L elementus. Matricą L dauginam iš matr.LT pirmojo stulpelio , , k=2,3,..,n. Antru etapu matricą L dauginam iš antrojo matricos LT stulpelio: , , k=3,4,..,n. Dauginam matricą L iš j-ojo transponuotos matricos stulpelio: , , k=j+1, j+2,...,n.

5.1 Jakobio ir Zeidelio metodas Tai tiesinių algebrinių lygčių sistemų sprendimo metodas, kuriuo gaunami norimo tikslumo artiniai. Jakobio metodas. Turime tiesinių lygčių sistemą AX=F, arba: ir pertvarkykim jos lygtis šitaip: iš pirmos lygties išreikškimeX1, iš antrosios –X2,ir taip pat visus kitus likusius narius Xn. Pasirenkam pradinį artinį ir įstatom į sistemos dešinę pusę.Paskaičiuojam pirmąji artini (iteraciją). Vėl įrašę gautąjį rezultatą į sistemos dešinę pusę gausim sekantį artinį. Skaičiuodami toliau gausime tikslesnį rezultatą. APIBRĖŽIMAS. k-tojo artinio paklaida vadinsime didžiausią atitinkamą šio artinio ir sprendinio komponenčių skirtumo modulį. TEOREMA (pakankamoji Jakobio metodo konvergavimo sąlyga) Jei tiesinių lygčių sistemos įstrižainės koeficientų moduliai yra didesni už kitų atitinkamos eilutės koeficientų modulių sumą, t.y., , tai Jakobio metodas konverguoja. TEOREMA. Jei tiesinių lygčių sistemos koeficientams galioja sąlyga tai Jakobio metodas kenverguoja. APIBRĖŽIMAS. k-ojo artinio paklaida vadinsime šio artinio ir sprendinio komponenčių skirtumų modulių sumą: Zeidelio metodas. Zeidelio metode atliekami tie patys veiksmai, taip pat issireiskiami nariai(is pirmos lygties x1 is antros x2 ir t.t.), pasirenkami norimi artiniai, tik apskaiciavus x1 jis iskart statomas i antra lygti, nelaukiant kol bus surasti visi nauji artiniai. Zeidelio konvergavimo ir paklaidu skaiciavimo salygos tokios pacios kaip ir Jakobio metodo atveju.

5.2 Stacionarieji iteraciniai metodai Tai tiesinių algebrinių lygčių sistemų sprendimo metodas, kuriuo gaunami norimo tikslumo artiniai. , cia B yra matrica, o (- iteracinis parametras. Iteraciniai metodai, isreiskiami sia formule, kurioje matrica B ir parametras ( nepriklauso nuo iteracijos numerio k, vadinamai stacionariaisiais. Jei matrica B nera vienetine B(E, tai iteracinis metodas yra neisreikstinis , o jei B=E- isreikstinis.

- tai yra bendra stacionariuju iteraciju procesu pakankamoji konvergavimo salyga. Teorema. Jei visu matricos tikriniu reiksmiu moduliai yra mazesni uz vieneta, tai stacionarusis iteracinis procesas konverguoja. Konvergavimo greitis didziausias su ta parametro ( reiksme, su kuria reiskinys igyja maziausia reiksme. Si reiksme yra lygties 1-((m=((M-1 sprendinys . Neisreikstiniai stacionarieji iteraciniai metodai.. 1 reikalavimas matricai B: Matrica B turi buti spektriskai artima matricai A. Antrasis reikalavimas: Matrica B turi buti tokia, kad lygciu sistema BXk+1=Xk-((AXk-F) butu lengvai issprendziama. Abieju reikalavimu kartu vykdyti neimanoma- jie yra priesingi, todel dazniausiai tenka ieskoti kompromisu. Paprasciausiu atveju B imama istrizainine arba trikampe. Istrizainiu matricu atvejis. Jei matrica B yra istrizainine, tai lygciu sistema BXk+1=Xk-((AXk-F) issprendziama atlikus n dalybos veiksmu. Bet kokiai matricai A is istrizaininiu matricu spektriskai artimiausia yra jos istrizainine dalis D, todel B=D: . Trikampiu matricu atvejis. Simetrine teigiamai apibrezta matrica A isreiskime dvieju trikampiu matricu suma, A=S+S* ir matrica B apibrezkime kaip dvieju trikampiu matricu sandauga: B=(E+(S)( E+(S*), (- dar vienas iteracinis parametras. Lygciu sistema BXk+1=Xk-((AXk-F) issprendziama taip: pirmiausia randamas pagalbines trikampes lygciu sistemos sprendinys, o po to ir nezinomuju vektorius Xk: . , (,(- teigiami skaiciai. Optimalusis parametras: .

5.3 Variaciniai metodai. Tai tiesinių algebrinių lygčių sistemų sprendimo metodas, kuriuo gaunami norimo tikslumo artiniai. Tarkime, kad matricos A ir B yra simetrines ir teigiamai apibreztos. Tokiu atveju tiesiniu lygciu sistemos AX=F sprendimas yra ekvivalentus kvadratinio funkcionalo Q(Y)=(A(Y-X),Y-X) minimumo uzdavinio sprendimui. Q(Y)>0, jei Y nelygu X; Q(Y)=0, jei Y=X, todel funkcionalo Q(Y) minimumo taskas(vektorius) sutampa su lygties AX=F sprendiniu. Sakykime, kad yra zinomas lygciu sistemos AX=F sprendinio X artinys Xk+1. tikslesni artini Xk+1 ieskosime tokio pavidalo: Xk+1=Xk-(kPk, cia Pk yra zinomas vektorius, vadinamas krypties vektoriumi. Iteracinis parametras (k yra kvadratines vieno kintamojo f-jos minimumo uzdavinio sprendinys: . Kadangi matrica A yra teigiamai apibrezta, tai (APk,Pk)>0, todel f-ja qk(() maziausiaja reiksme igyja taske:

. Parenkant konkrecius vektorius Pk, gaunami ivairus variaciniai metodai. Aptarsim 2 is ju: didziausio nuolydzio ir jungtiniu gradientu.Didziausio nuolydzio metodas. Zinoma, kad f-ja didziausiu greiciu (lokaliai) mazeja kryptimi, priesinga gradiento krypciai, todel imkime toki variacinio metodo krypties vektoriu: . Su siuo krypties vektoriumi gaunamas variacinis metodas vadinamas didziausiojo nuolydzio metodu: , . Jei krypties vektoriumi imsime , tai gausime neisreikstini didziausiojo nuolydzio metoda: ,. Teorema. Didziausiojo nulydzio metodas konverguoja, ir konvergavimo greitis ivertinamas sia nelygybe:||Xk+1-X||A<= (||Xk-X||A, (=1-(/1+(, (=(m/(M, cia (m>0 ir yra maziausioji ir didziausioji matricos B-1 A tikrine reiksme, o norma ||.||A apibreziama tokia lygybe: ||Y||A2=(AY,Y). Jungtiniu gradientu metodas. Teorema. Jei matrica A yra simetrine ir teigiamai apibrezta, o vektoriai Po ,P1 ,...,Pn-1 sudaro matricos A atzvilgiu jungtiniu vektoriu sistema, tai ne daugiau kaip per n iteraciju su bet kuriuo pradiniu vektoriumi Xo iteraciniu metodu Xk+1=Xk-(kPk, (k=(AXk-F,Pk)/(APk,Pk) gaunamas tixlus tiesiniu lygciu sistemos AX=F sprendinys(jei nedaroma apvalinimo paklaidu).

6.1 Stačiakampių, trapecijų, Simpsono formulės. Stačiakampių formulės. Skaitinio integravimo metodai grindžiami integralo apibrėžimu, ir jais galima apskaičiuoti integralo reikšmę kokiu norima tikslumu. Funkcijos y = f(x) apibrėžtinio integralo skaitinė reikšmė yra kreivinės trapecijos plotas, kurią iš viršaus riboja kreivė y = f(x), iš apačios – Ox ašies atkarpa [a,b], o iš kraštų – vertikaliosios tiesės x=a ir x=b:

Apskaičiuosime šį plotą. Padalykime intervalą [a,b] į N lygių dalių, a=x0, x1, x2,.....,xN= b, xi+1- xi = h, h=b-a/N , šiuos taškus vadinsime integravimo mazgais, skaičių h –integravimo žingsniu.

kreivinės trapecijos, kurios pagrindas yra dalinis intervalas [xi, xi+1], plotas apytiksliai lygus įbrėžtinio stačiakampio su tuo pačiu pagrindu plotui: , čia f(xi) yra stačiakampio aukštinė. Apskaičiavę ir sudėję visų dalinių stačiakampių plotus, gausime apytikslę visos kreivinės trapecijos ploto reikšmę, arba . Tai ir yra kairiųjų stačiakampių formulė. Visiškai panašiai sudaroma ir dešiniųjų stačiakampių formulė: .

Sudarysime kitą skaitinio integravimo formulę, kurios tikslumas proporcingas integravimo žingsniui kvadratu, h2. Vėl padalykime intervalą [a,b] į N lygių dalių, a=x0, x1, x2,.....,xN= b, xi+1- xi = h, h=b-a/N , ir į kiekvieną kreivinę trapeciją, kurios stačioji kraštinė sutampa su intervalu [xi,xi+1], įbrėžkime po trapeciją. Įbrėždami trapeciją, kreivės y=f(x) lanką, esantį virš intervalo [xi,xi+1], pakeičiame tiesės atkarpa .

arba . Tai ir yra trapecijų formulė. Trapecijų metodas yra gerokai tikslesnis už stačiakampių metodą.

Funkcijos y=f(x) apibrėžtinį integralą galime skaičiuoti ir tikslesnėmis formulėmis negu trapecijų; vieną iš jų, Simpsono formulę, dabar ir sudarysime. Išvesdami stačiakampių formules, kreivę y=f(x) kiekviename intervale [xi+xi+1] keitėme konstantą f(xi) arba f(xi+1); sudarydami trapecijų formulę – tiese, einančia per du taškus (xi, f(xi)) ir (xi+1,f(xi+1)). Simpsono formulė sudaroma parabolėmis pakeitus funkciją y=f(x). Padalykime integravimo intervalą [a,b] į lyginį dalių skaičių: a=x0,x1,x2....,xN=b, xi+1- xi = h, h=b-a/N , N=2m. ir kiekviename intervale[xi,xi+2] nubrėžkime paraboles, einančias per taškus (xi, f(xi)), (xi+1,f(xi+1)), (xi+2,f(xi+2)). y=L(x) – parabolė einanti per tris kreivės y=f(x) taškus. Ši parabolė reiškiama tokia kvadratine lygtimi: . dešiniojoje šios lygybės pusėje yra laipsninė funkcija – ją lengva integruoti. Įrašę šia funkciją į pradinį integralą ir suintegravę gausime apytikslę skaitinio integravimo formulę:

, arba . Tai ir yra Simpsono formulė. Jos paklaidos įvertis išvedamas taip pat, kaip ir trapecijų formulės: , čia M4 yra funkcijos f(x) ketvirtosios išvestinės modulio rėžis: . Atkreipsime dėmesį į konstantą paklaidos rėžio vardiklyje – ji yra 15 kartų didesnė už trapecijų formulės konstantą; šitai taip pat rodo didesnį Simpsono formulės tikslumą.

6.2 Neapibrėžtinių koeficientų metodas Skaitinio integravimo metodai grindžiami integralo apibrėžimu, ir jais galima apskaičiuoti integralo reikšmę kokiu norima tikslumu. Skaitinio integravimo skaičiavimų apimtis tiesiogiai priklauso nuo mazgų skaičiaus- juo daugiau mazgų , juo daugiau reikia apskaičiuoti integruojamos funkcijos reikšmių, todėl natūralu siekti kuo didesnio integravimo formulės tikslumo su tam tikru integravimo mazgų skaičiumi.

Pakeiskime funkcijos f(x) integralą jo skaitinių artinių: , čia xi=a+ih, h =1/N, o koeficientai ci – kol kas nežinomi, juos turėsime nustatyti.

Koeficientus ci parinksime tokius, kad skaitinio integravimo formulė tiksliai integruotų kuo aukštesnio laipsnio vienanarius xm, t.y. sakysime, kad ε (1)=0, ε (x)=0, ε (x2)=0,..., ε (xk)=0.

Skaitinio integravimo formule tisliai integruojami tik nulinės eilės vienanariai – konstantos, k=0: c0=b-a. Šią reikšmę įrašę į integralo artinio formulę, gausime tokį integralo artinį: . Jei intervalą [a,b] suskaidytume į N dalių, a=x0 < x1 <... < xN =b, ir kiekvienoje iš jų integralą pakeistume pagal šią formulę, tai gautume anksčiau nagrinėtą (sudėtinę) kairiųjų stačiakampių formulę: .

kurios sprendinys yra c0=(b-a)/2, c1=(b-a)/2. Šiuo atveju gausime trapecijų formulę:

Juos parinksime taip, kad skaitinio integravimo formule būtų tiksliai integruojami kuo aukštesnio laipsnio daugianariai. Šitaip sudarytos skaitinio integravimo formulės vadinamos N-osios eilės Gauso skaitinio integravimo formulėmis.

Nustatydami integravimo mazgų koordinates, remsimės ortoganaliųjų daugianarių ypatybėmis, todėl pirmiausia priminsime svarbiausius apibrėžimus.

APIBRĖŽIMAS.Dviejų funkcijų u(x) ir v(x) skaliarine sandauga (su svoriu p) vadinsime skaičių čia funkcija p(x) vadinama svorio funkcija arba tiesiog svoriu, ir p(x)>0 su visais x.

Bet kurią tiesiškai nepriklausomų funkcijų sistemą v1(x),....,vm(x) galima ortogonalizuoti Šmidto metodu:

Turim sistema , j=1,2,...,n ; pazymekim X=(x1,x2,...xn), matrica A sudaryta is aij koeficientu. Su šiais žymėjimais sistemą perrašykime matriciniu pavidalu AX=(X, čia ( yra skaičius. Perkėlę dešiniąsias lygčiu puses į kairiąją pusę ir sutraukę panašiuosius narius, gausime sistemą (A-(E)X=0, čia E yra vienetinė matrica. Si lygčiu sistema yra homogeninė (visu lygčių laisvieji nariai - nuliai) ir turi nulinį sprendinį: vektorius X, kurio visos komponentės lygios nuliui, tenkina pradinę sistemą (tai trivialus spr.). Reikia rasti ( reikšmes, su kuriomis ši sistema turi nenuliniu sprendiniu. Vektoriai X nustatomi tik konstantos tikslumu, todėl galima nagrinėti normuotuosius vektorius, t.y. tuos, kuriu norma lygi vienetui: ||X||=1. Šis lygčių sistemos sprendimo uždavinys ir yra vadinamas matricos A tikriniu reikšmių uždaviniu. Parametro ( reikšmė, su kuria tikriniu reikšmiu uždavinys turi nenuliniu sprendiniu X, vadinama tikrine matricos A reikšme, o šis sprendinys X — tikriniu matricos A vektoriumi.Homogeninė tiesiniu algebriniu lygčiu sistema turi nenulinį sprendinį tada, kai jos determinantas lygus 0:kvadratinė n-osios eilės matrica turi n tikrinių reikšmių; iš jų kai kurios gali būti kartotinės ir kompleksinės. Tikrinių reikšmių uždavinio sprendimą galima suskirstyti: charakteristinio daugianario (ir lygties) sudarymas, charakteristinio daugianario šaknų - matricos A tikriniu reikšmių radimas, tikrinių vektorių apskaičiavimas.

7.2 Parabolių metodas. Siuo metodu randami sistemu tikriniai vektoriai ir tikrines reiksmes.

Šis metodas yra panašus į kirstinių metodą. Vietoj kreivės y=f(x) kirstinių čia imamos parabolės, einančios per tris šios kreivės taškus. Funkcija f(x) yra charakteristinis triųstrižainės matricos daugianaris pn. Pasirinkime tris kintamojo ( reikšmes (0, (1, (2, ir apskaičiuokime charakteristinio daugianario reikšmes pn((0), pn((1), pn((2). Per tris taškus ((0; pn((0)), ((1; pn((1)), ((2; pn((2)) paraboles kurios lygtis yra antrojo laipsnio interpoliacinis daugianaris.Tai yra antrojo laipsnio daugianaris kintamojo ( atžvilgiu. Apskaičiavę jo šaknis, gausime du naujus charakteristinės lygties sprendinio artinius; iš ju pasirinksime tą kur |(-(2| yra mažesnis, ir pažymėsime jį (3. Jei šio artinio tikslumas nepakankamas, tai nubrėšime dar vieną parabolę per taškus su naujomis abscisėmis ((1, (2, (3), apskaičiuosime daugianario L2(() šaknis ir t.t., šį procesą tęsime tol, kol šaknies artinio tikslumas taps pakankamas. Parabolių metodas visada konverguoja. Konvergavimo greitis artimas kvadratiniam: |(-(k+1|(q|(-(k|1.83. Su realiuoju pradiniu artiniu iteracinis procesas gali konverguoti į kompleksinę daugianario šaknį. Radus m šaknų, (m + 1)-oji šaknis ieškoma su funkcija.

7.3 Atvirkštinių iteracijų metodas. Siuo metodu randami sistemu tikriniai vektoriai ir tikrines reiksmes. Sakykime, kad tikrinė reikšmė (k, kurią apskaičiuosime atvirkštinių iteracijų metodu, yra intervale (ak,bk). Pasirinkime pradinį tos reikšmės ir atitinkamo tikrinio vektoriaus artinį, (0k=0.5(ak+bk), X0k,ir kiekvieną naują tikrinio vektoriaus artinį apskaičiuokime pagal tokią taisyklę: (A-(mkE)Ykm+1=Xmk. Apskaičiuotąjį vektorių Ykm+1 normuosime, ir gautąjį tikrinį vektorių Xkm+1 laikysime (m+1)-uoju tikrinio vektoriaus artiniu: Xkm+1=csYkm+1, ||Xkm+1||=1. Naujas tikrinės reikšmės artinys: (km+1=(AXkm+1, Xkm+1). Šitaip tikrinio vektoriaus ir tikrinės reikšmės artinius skaičiuosime tol, kol skirtumas tarp dviejų gretimų artinių (ir tikrinės reikšmės, ir vektoriaus) taps mažesnis už reikalaujamą paklaidą.|Xkm+1-Xmk|((, |(km+1-(mk|((.

7.4 Laipsnių metodas. Siuo metodu randami sistemu tikriniai vektoriai ir tikrines reiksmes

Laipsniu metodu randama tik viena moduliu didžiausioji arba mažiausioji, tikrinė reikšmė ir atitinkamas tikrinis vektorius. Jis yra atvirkštinių iteracijų metodo dalis. Tarkime, kad visos matricos A tikrinės reikšmės yra realiosios, o tikriniai vektoriai sudaro pilnąją vektoriu sistemą. Be to sakykime, kad didžiausioji moduliu tikrinė reikšmė nėra kartotinė: |(1|>|(2|(|(3|( ((|(n|. Ši ypatybė būdinga toms matricoms, kuriu visi elementai yra realieji teigiamieji skaičiai. Kadangi tikrinių vektorių sistema yra pilnoji, tai bet kurį kitą vektoriu X0 galima išreikšti jų tiesiniu dariniu: X0=c1X1+c2X2+(+cnXn. Sakykime, kad vektorius X0 yra normuotasis, t.y. ||X0||=1, o koeficientas c1 nelygus nuliui. Vektorių Xk seką, sudaromą pagal tokią taisyklę: Yk=AXk-1=(1Ck-1(c1X1+c2qk2X2+(+cnqknXn), Xk=Ck(c1X1+c2qk2X2+(+cnqknXn), ||Xk||=1. Vektoriai Xk, kai k tolsta į begalybę, artėja prie tikrinio vektoriaus X1, atitinkančio didžiausiąją moduliu tikrinę reikšmę (1, nes visi |qi|<1, qk=(k/(1 ir . Laipsnių metodo konvergavimo greitis yra tiesinis ir priklauso nuo daugikliu q2, q3,(, qn dydžio. Didžiausiosios tikrinės reikšmės (1 artinys paskaiciuojamas taip :. Kadangi q2 reikšmė nėra žinoma,tai :.Pritaikysime laipsniu metodą mažiausiajai matricos A tikrinei reikšmei ir atitinkamam tikriniam vektoriui rasti. Sakykime, kad visos matricos A tikrinės reikšmės yra realios ir teigiamos, o mažiausioji tikrinė reikšmė nėra kartotinė: (1((2((3( ( ((n>0. Jei matrica A yra bendro pavidalo, laipsniu metodą patartina taikyti su matrica B=(E-A, čia (((1; ( galima rasti pagal laipsnių metodu apskaičiavus didžiausiąją tikrinę reikšmę. Matricos B tikrinės reikšmės su matricos A tikrinėmis reikšmėmis yra susijusios lygybę (i=(-(i, ir (-(n>(-(n-1( ( ((-(2((-(1, o tikriniai vektoriai sutampa. Matricos A tikrinės reikšmės (n artiniai apskaičiuojami pagal lygybę: (kn=(AXkn, Xkn).

xn+1=xn-f’(xn)/f’’(xn). Taigi šiuo metodu ieškant funkcijos minimumo, reikia apskaičiuoti pirmąją ir antrąją išvestinę, todėl aukso pjūvio metodas realizuojamas paprasčiau, nes juo užtenka apskaičiuoti tik pačios funkcijos f(x) reikšmes. Tačiau Niutono metodas daugeliui funkcijų konverguoja žymiai sparčiau, nei aukso pjuvio met. Niutono metodas konverguoja kvadratiniu greičiu.

8.3 Kelių kintamųjų funkcijų minimumo uždavinys. Išspręsime kelių kintamųjų funkcijos y = f (x), kur x=(x1,x2,...,xn), minimumo uždavinį: rasime tokį n-matės erdvės D tašką x0 su kuriuo ši funkcija įgyja lokalų minimumą, t.y. pakankamai mažoje taško x0 aplinkoje U(x0,() su kiekvienu x iš tos aplinkos galioja nelygybė f(x0)(f(x). Jei funkcija y=f(x) kuriame nors vidiniame srities D taške įgyja lokalų minimumą arba maximumą, tai jos gradientas šiame taške lygus nuliui: (f(x)=0. Koordinatinis šios vektorinės lygties pavidalas yra n lygčių sistema: , i=1,2,...,n. Ekstremumas yra minimumas, jei funkcijos f(x) hesijanas taške x0 yra teigiamai apibrėžta matrica, t.y. (H(x0)v,v)>0 su visais vektoriais v, v (0.

8.4 Simpleksų metodas.Simpleksų metodas yra panašus į aukso pjūvių metodą, ir jų abiejų privalumas yra tas, kad visiškai nereikia skaičiuoti funkcijos f(x) išvestinių. APIBRĖŽIMAS. /n-matės erdvės simpleksu yra vadinamas n-matis iškilasis daugiasienis/ pvz trikampė piramidė yra trimatis simpleksas, trikampis – dvimatis simpleksas. Simplekso metodo algoritmas: Sumažinus simpleksą, jo viršūnėse apskaičiuojamos funkcijos reikšmės ir tikrinamas tikslumas: 1) Sakysime, kad funkcijos f(x) minimumas apskaičiuotas tikslumu (, jei k-ojo simplekso skersmuo yra ne didesnis už (. 2) Sakysime, kad reikiamas tikslumas ( pasiektas, jei funkcijos reikšmių k-ojo simplekso viršūnėse nuokrypis.

  • Microsoft Word 95 KB
  • 2019 m.
  • Lietuvių
  • 4 puslapiai (4584 žodžiai)
  • Kolegija
  • Vytautas
  • Skaitinių teorija
    10 - 1 balsai (-ų)
Skaitinių teorija. (2019 m. Spalio 08 d.). https://www.mokslobaze.lt/skaitiniu-teorija.html Peržiūrėta 2019 m. Spalio 15 d. 21:35
×
Užduokite klausimą bet kuria mokslo tema