|
5.njutnova interpolacija za zapis interpolacionih polinoma u ovom omliku koriste se podeljene razlike.Neka su date tacke (Xi,Yi) i=1,n Xi!=Yi i!=j.Podeljene razlike k-tog reda oznacavaju se sa Y[Xi..Xi+k] i odredjuju na sledeci nacin:k=0,i=0..n Y[Xi]=Yi, a k=1..n i=0..n-k, Y[Xi..Xi+k]=(Y[Xi+1..Xi+k]-Y[Xi..Xi+k-1])/Xi+k-Xi Teorema:za podeljene razlike vazi Y[X0..Xk]=SUM(i=0,k)Yi MUL(j=0,k j!=i) 1/(Xi-Xj) TT:neka su date tacke (Xi,Yi) Nn(X)=SUM(i=0,n)Y[X0..Xi] MUL(j=0,i-1)(X-Xj)->Njutnov int.pol. Greska interp. f(x)-Nn(x). TT:neka su tacke X..Xk medjusobno razlicite neka je f-ja f neprekudna u intervalu In(X,X0..Xk) i neka f^(k+1)(x) postoji u svakoj tacki tog interv.Tada za neko (x)=x (x) iz interv. In(X,X0..Xk) vazi f[X0..Xk,X]=(f^(k+1)( x)) / (k+1)! Neka je data fiksna tacka X0 i rastojanje susednih tacaka h>0 Xi=X0+ih.U ovakvim slucajevima int. pol. se moze izraziti pomocu konacnih razlika.Opadajuce razlike k-tog reda za k=0 TR->truogao TR^0 Yi=Yi a za k=1..n i i=0..n-k TR^k Yi=TR^(k-1) Yi+1 - TR^(k-1) Yi.Rasuce razlike za k=0 OTR^0 Yi=Yi, za k=1..n za i=k..n OTR^k Yi=OTR^(k-1) Yi - OTR^(k-1) (Yi-1) 6.Splajn int. Neka je nad svakim od pod intervala [xk, xk+1] odredjen inter. pol. ako je sa Sk(x) oznacen osecak odgovarajuceg inter. pol. nad [xk, xk+1], onda se dobija niz polin. Sk(x), k=0..n-1. Spajanjem ovih pol. dobija inter. f-ja S(x) = Sk(x), za x Î [xk, xk+1], koja se naziva splajn. Delovi splajna Sk(x) i Sk+1(x) nad susednim podintervalima, prolaze kroz zajednicki cvor (xk+1, yk+1) odnosno Sk(xk+1) = Sk+1(xk+1) = yK+1. Funkcija Sp(x) se snaziva splajn stepena sa cvorovima iz mreze TR ako je Sp(x) = SUM(i=0, 5) Si,k(x-xk)^i, gde su keficijenti Si,k Î R, i=0..p, k=0..n. Splajn Sp(x) se naziva interp. splajn f-je f(x) na mrezi TR ako vazi Sp(xk) = f(xk). Koriscenjem formule Sk(x) = yk+dk(x-xk) gde je dk=(yk+1-yk)/(xk+1-xk). Najcesce se koristi kun\bnji splajn, ima svojstvo minimalne krive. Pri odredjivanju kubnog splajna zahteva se da splajn i njegovi 1 i 2 izvod budu neprekidni. Neka je data mreza TR i vrednosti y0..yn. Funkcija S(x) naziva se kubni splajn ako postoji n polinoma 3-ceg stepena. Sk(x) = Sk,0+Sk,1(x-xk)+Sk,2(x-xk)^2+Sk,3(x-xk)^3 takvih da vazi (I) za svako k=0..n-1 S(x) = Sk(x) , x Î [xk, Xk+1] (II) Splajn prolazi kroz zadate cvorove S(Xk) = Yk k=0..n (III) Neprekidna f-ja Sk(Xk+1) = Sk+1(Xk+1) k=0..n-2 (IV) Splajn glatka f-ja S'k(Xkk+1) = S'k+1(Xk+1) k=0..n-2 (V) 2 izvod splajna je neprekidna f-ja S''k(Xk+1) = S''k+1(Xk+1) k=0..n=2 7.Metod najmanjih kvadrata Zahtev da ukupna odstupanja budu sto manja. Razmotricemo prvo najednostavniji linear slucaj.Mozemo pretpostaviti da je trazen f-ja zapravo linearna, a to sto sve tacke ne leze na pravoj liniji posledica je gresaka pri merenju.Dakle kao aproksimaciju gresaka iz tabel trazicemo line, f-ju Y=Ax+B gde su A,B koef. koje trebaodrediti.Za one tacke Xk koje lexe na ovoj pravoj imamo da je AXk+B-Yk=0 a za sve one tacke koje nisu na pravoj odstupanje iznosi apsolutno |AXk+B-Yk|.Ukupna greska za svih n tacaka je SUM(k=1,n) |AXk+B-Yk|. Za odredjivanje 2 nepoznata parametra A,B dovoljne su 2 jednacine.Jedan od nacina da odredimo param. A,B bio bi minimizacija f-je F(A,B)=SUM(k=1,n) (AXk+B-Yk)^2.Da bi f-ja F imala minimum, mora da bude ispunjen uslov ðF/ðA=0 i ðF/ðB=0 sto daje sledece jed.: SUM(k=1..n) 2(AXk+B Yk)Xk=0,SUM(k=1..n)2(AXk+B-Yk)=0 Metoda najmanjih kvadrata nije ogranicen na lin. pol.Princip najm.kvad. moze se uopstiti na proizvoljnu lin. komb. f-ja f (x)=SUM(k=1,m)Ckfk(x) gde f-je f1.. fm pripadaju skupu linea.nezavisnih f-ja koje su unapred fiksirane i poznate.Problem aproksimacije f-je f koja je data preko svojih vrednosti Yj=f(Xj) pomocu f-je f svodi se na odredjivanje koef. C1..Cm pri tom mora da bude m<n, jer bi inace bila u pitanju interpolacija. SUM(k=1,n) ( SUM(j=1..n) fi(Xj) fk(Xj) ) Ck = SUM(j=1,n) fi(Xj)Yj i=1..m 8.Metod najmanjih kvadrata-neprekidni slucaj Neka je L^2(a,b) skup svih realnih f-ja integrabilnih sa kvadratom na intervalu [a,b], tj. skup f-ja za koje vazi ò(a,b) f^2(t)dt < +... Neka je p nenegativna integrabilna f-ja def. na intevalu [a,b]. Ovako def. f-ju p zvacemo tezinska fu-ja. u L^2 (a,b) uvodi se pojam skalarnog proizvoda 2 elementa f,g Î L^2(a,b) u odnosu na tezinsku funkciju p, u oznazi (f,g), na sledeci nacin (f,g)= ò(a,b) p(t) f(t) g(t) dt. Pomocu ovako uvedenog skalarnog proizvoda definisemo normu proizvoljnog elementa f Î L^2(a,b) kao ||f||=Koren iz(f,f) = (ò(a,b) p(t) f^2(t) dt )^(1/2). Uspecijalnom slucaju kada je tezinska f-ja p(x) =1 prethodne dve formule svode se na (f,g) = ò(a,b) f(t) g(t) dt , ||f|| =( ò(a,b) f^2(t) dt )^(1/2)). Svaka f-ja [fi] pripada i (i-konacan ili beskonacan skup indeksa) iz L^2(a,b) jeste ortogonalan sistem ako je (fi, fj)=za j!=i 0, a za j=i sledi ||fi||^2. U raznim primenama osobina ortogonalnosti je veoma pozeljna, pa je zato cesto potrebno iz postojece baze dobiti ortogonalnu bazu. Postupak kojim se ovo vrsi Poznat je kao Gram_smidtov postupa ortogonalizacije. Neka je dat sistem lienarno nezavisnih funkcija f0,f1,... sistem ortogonalnih f-ja q0,q1,... dobicemo prema formulama q0=f0, gk=fk-SUM(i=0,k-1)((fk,gi)/(qi,qi))qi k=1,2.... Ovaj postupak se najcesece vrsi tako sto polazimo od prirodne baze u L^2 (a,b). U prostoru L^2(-1,1) sa tezinskom f-jom p(x)=1 sistem ortogonalnih polinoma cine takozvani Lezandrovi polinomi Pn(x)=((1/(2^n*n!))(d^n/dx^n))(x^2-1)^n. Kvadrat norme Lezandrovih polinoma dat je izrazom ||Pn||^2=2/(2n+1). Uprostoru L^2(-1,1) sa tezinom p(x)=(1-x^2)^(-1/2) dobijamo Cebisevljeve polinome Tn. Cebisevljevi polinomi imaju normu: ||T0||^2=p i ||Tk||^2=p/2. Cebisevljevi polinomi mogu se predstaviti u sledecem obliku Tk(x) = cos(k arccosx) u prostoru L^2 [0,+...) sa tezinskom funkcijom p(x)=e^(-x) imamo Lagerove polinome, ciji je opsti oblik dat fomulom Ln(x) = e^x(d^n/dx^n)(x^n e^(-x)). U prosotru funkcija L^2 (-...,+...) sa tezinskom funkcijom p(x) = e^(-x^2) imamo Hermitove polinome Hn(x) = (-1^n e^(x^2)(d^n/dx^n)(e^(-x^2)). 10.Num.Integ. Primitivne kvadraturne formule.Neka je data podela interv. [a,b] na n podintervala tackama a=X0<X1-..<Xn=b.Pod prim. kvad.formulama podrazumevaju se Rimanove sume dobijene za specijalne izbore tacaka Ti. Za izbor Ti=Xi-1 dobija se formula levih pravougaonika Ln(f;a,b)=SUM(i=1,n) f(Xi-1)(Xi-Xi-1) za Ti=Xi formula desnih pravougaonika Dn(f;a,b)=SUM(i=1,n)f(Xi)(Xi-Xi-1) a za Ti=(1/2)(Xi-1+Xi) dobija se formula srednjih pravougaonika Mn(f;a,b)=SUM(i=1,n)f((Xi-1+Xi)/2)*(Xi-Xi-1) TT:neka je f elem. C^1[a,b] tada postoji b Î (a,b) takvo da je I(f;a,b)-Dn(f;a,b)=(-1/2)f'(b) SUM(i=1,n)(Xi-Xi-1)^2 TT:neka je fÎC^2[a,b].tada postoji gÎ (a,b) takvo da je I(f;a,b)-Mn(f;a,b)=(1/24)f''(g) SUM(i=1,n) (Xi-Xi-1)^3. Ako su cvorovi integracije ekvidistantno rasporedjeni tj. ako je Xi=a+ih i=0..n h=(b-a)/n, navedene formule i izrazi za greske sepojednstavljuju. TT:Ako je fÎC^1[a,b] onda je |I(f;a,b)-Ln(f;a,b) <= (M1/2 SUM(i=1,n)(Xi-Xi-1)^2 TT:ako je fÎC^2[a,b] onda je |I(f;a,b)-Mn(f;a,b)|<=(M2/24) SUM(i=1,n) (Xi-Xi=1)^3 11 Njutn-Kotesove kvad. formule posmatraju se kvadraturne formule oblika Qn=SUM(i=0,n) Aif(Xi), sa pretpostavkom da cvorovi integracije Xi obrazuju mrezu. Odredjivanje greske numericke integracije: En(f;a,b) = In(f;a,b) - Qn(f;a,b). Jedinu mogucnost za odredjivanje greske Num. integ. pruza red tacnosti. Kvad. formula Qn(f;a,b) je reda tacnosti k ako je En(x^i;a,b) = 0, i=0..k. Kvadraturna formula Qn(f;a,b) je inter. kvad. formula n-tog reda ako za sve f Î C[a,b] vazi SUM(i=0,n) Ai f(Xi) = Integral(a,b) Pn(f,x)dx gde je Pn(f,x) interp. pol. n-tog stepena za f-ju f u odnosu na medjusobno razlicite cvorove Xi, i=0..n. Za interp. kvad, formule n-tog reda vazi En(q; a,b) = 0, za svaki polinom q stepena < ili = sa n , jer je, prema teoremi Pn(q,x) = q(x) TT: koeficijenti interp. kvad. formule dati su sa Ai = MUL(j=0,n j!=i) 1/(Xi-Xj) (Integral(a,b) MUL(j=0,n j!=i)(X - Xj)dx), i=0..n. TT: interp. kvad. formula ima red tacnosti > ili = sa n. 12 Njutn-Kotesove kvad, formule zatvorenog tipa -> su interp. kvad. formule n-tog reda sa equidistantnim cvorovima Xi = a+ih, i=0..n , h=(b-a)/n, n Î N. Kod Njut-Kot. kvad. formula zatvorenog tipa svi cvorovi integracije pripadaju intervalu [a,b], a X0=a i Xn=b su prvi i poslednji cvor integracije, sto se oznacava recima "zatvorenog tipa". TT: NJutn-Kotesova kvad. formula reda n glasi Nn(f;a,b) = h SUM(i=0,n) An,i f(Xi) gde je An,i = ((-1)^(n-1))/(i!(n-1)!) (Integral(0,n) MUL(j=0,n j!=i)(t-j)dt) i=0..n. Neka je n=1 tada je X0 = a X1=b h=b-a odgovarajuca Njut_kot formula je N1(f;a,b) = (b-a)(A1,0 f(a) + A1,1 f(b)) gde je A1,0 = A1,1= -Integral(0,1)(s-1)ds=1/2. Znaci N1(f;a,b) = (b-a)/2(f(a)+f(b)). Ova formula se naziva trapezna from. Simpsonova jvad. formula: N2(f;a,b) = (b-a)/6(f(a)+4f((a+b)/2)+f(b)). Za interpolacione kvad. fomule Qn(f;a,b) greska integracije En(f;a,b) = Integral(a,b)f(x)dx - Qn(f;a,b) data je sa En(f;a,b) = Integral(a,b)Rn(f,x)dx gde je Rn(f,x) greska interpolacije Rn(f,x) = f(x)-Ln(f,x)= (f^(n+!)(x))/(n+1)! * w n(x), w n(x) = MMUL(j=0,n)(X-Xj). 13 Njutn- Kotesove kvad. formule otovrenog tipa .Interpol. kvad. formule n-tog reda sa ekvidinstantnim cvorovima Xi = X0+ih, i=0..n pri cemu je h=(b-a)/(n+2), X0=a+h, Xn = b-h. nazivaju se Njut-Kot.kvad.formule otovrenog tipa. Kod NJutn_Kot. kvad. formula otovrenog tipa cvorovi Xi pripadaju intervalu(a,b), a krajnje tacke, oznacene sa X-1 = a i Xn+1 =b nisu cvorovi inegracije. Neka je Njut-Kot. forula n-tog reda i otvorenog tipa Kn(f;a,b) = h SUM(j=0,n j!=i) Bn,i F(Xi) tada su koefic. Bn,i dati sa Bn,i = Bn,n-1 =((-1)^(n-1))/(i!(n-i!)) Integral(-1,n+1) MUL(j=0,n j!=i)(s-j)ds=0..n TT: Greska Njut-Kot. kvad. formule n-tog reda i otovrenog tipa je En(f;a,b) = ako je n parno ->h^(n+3)f^(n+2)(x) Integral(-1,n+1)(s nad n+2) ds, ako je n neparno En(f;a,b) = h^(n+2)f^(n+1)(x) Integral(-1,n+1)(s nad n+1) ds. Neka je interval [a,b] tackama Xi podeljen na m podintervala iste duzine hm, tj. neka je hm=(b-a)/m , Xi = a=ihm i=0..m. Njut-Kot. formule zatvorenog tipa dobijaju se integracijom od X0=a do Xm=b interpolacionog polinoma za f-ju f sa cvorovima interpolcije Xi, i=0..m. Koriste se sve tacke Xi. Njut-Kot formule otvorenog tipa se dobijaju integracijom od Xo=a do Xm=b, interpolacionog polinoma sa cvorovima interpolacije Xi i=1..m-1. Veza izmedju reda n kvadraturne formule i broja podintetvala m kod formule otvorenog tipa je n=m. Otuda za datu podelu intervala [a,b] formule zatvorenog tipa imaju red tacnosti za 2 veci od formula otvorenog tipa. 14. Kvadraturne formule Gausovog tipa Interp. kvad. formule Qn(f;a,b) n-tog reda su tacne za sve polinome p Î MULn, tj. vazi Qn(p;a,b) = I(p;a,b). U kvadraturnoj formuli Qn(f;a,b)=SUM(i=0,n)Ai f(Xi), imamo 2n +2 parametara Xi, Ai, i=0..n, to se pojavljuje mogucnost da se posebnim izborom i cvorova integracije Xi i koefic. Ai dobije kvad. formula koja ce biti tacna za polnome p Î MUL2n+1. Neka je W pozitivna neprekidna funkcija za x Î [a,b]. Posmatra se aproksimacija integrala ò(a,b) W(x) f(x) dx, za neprekidnu f-ju f Î C[a,b], pomocu Gn(f;a,b) = SUM (i=0,n) ai f(Xi). Interpolaciona kvad. formula n-tog reda naziva se kvad. formula Gaussovog tipa, ako za sve polinome p Î MUL2n+1, vazi ò(a,b) W(x) p(x) dx = SUM (i=0,n) ai p(Xi). TT: Ako je f Î C^(2n+2)[a,b], onda za neko x Î (a,b) vazi ò(a,b) W(x) f(x) dx-SUM(i=0,n) ai f(Xi) = (f^(2n+2)(x))/(2n+2)! * (Pn+1, Pn+1). Za razlicite funkcije W(x), kao sto znamo, dobijamo razlicite klase ortogonalnih polinoma. U praksi se najcesce koriste Gauss-Lezandrove kvad. fromule, tj. formula kod kojih je W(x)=1. 15. Lokalizacija resenja jednacina Lokalizacija resenja, odnosno odredjivenje skupa koji sadrzi jedno ili vise resenja posmatrane jednac. moze se cesto sprovesti crtanjem f-je f cije se nule traze apscise tacaka preseka grafika f-je i X ose su resenja jednac. f(x)=0 ukoliko je f-ja f komplikovanija za crtanje posmatra se ekviv. jednac. h(x)=g(x), pri cemu su h i g pogodno izabrane f-je.Dve jednac. su ekviv. na skupu D ako du resenja iz D jedne jednac. istovremeno i reenja druge jednac. i obrnuto.Drugi nacin za lokalizaciju resnja jednac. je tabeliranje funkcije.Lema:neka je f(x) neprekidna f-ja na intervalu [a,b].Ako je f(a)f(b)<0 onda postoji bar jedno resenje jednac. f(x)=0 u interv. (a,b). Jednac. br 3 pn(x)=X^n +an-1 x^(n-1) + ..+ a1x+ a0=0 TT:Ako je kompleks. br. x=a+ib res. jed.3 visestrukosti k,onda je i broj x=a-ib res. jed. visestrukosti k. TT:Algebarska jednac. neparnog stepena ima bar jedno realno res.Ako su poznata res. x1.. xi jednac. 3 redom visestrukosti k1..ki pri cemu je k1+..+ki=n, jednac. 3 se moze zapisati u obliku ((x-x1)^k1)..((x-xi)^ki)=0 TT:Nek je S={iÎ{0..n-1}:ai!=0}.Ako su ci i=0..n-1 nenegativni brojevi za koje vazi 0<SUM(i=0,n-1)ci<=1, ci>0, iÎS onda za res. x jednac. 3 vazi |x|<=max TT:Neka je K {iÎ{o..n-1}:ai<0} neprazan skup.Tada za svako pozitivno resenje x jed. 3 vazi x<1 + m-ti koren od b. 16.Opsti iterativni postupak za res. jednac. Neka je sa D Ì R oznacen zatvoreni interval i neka je j:D->R Tacka aÎD je nepokretna tacka f-je j ako je a=j(a).Iterativni postupak za resavanje jednac. x=j(x) sastoji se od izbora pocetne aproksimacije x0ÎD i racunanja niza aproksimacija xk+1=j(xk) k=0.. Pri tome se zahteva da je j(xk) ÎD, jer je f-ja j definisana na tom intervalu.Tako se dobija niz x0,x1=j(x0), x2=j(x1) ...koji se naziva niz sukcesivnih aproksimacija ili iterativni niz.Pored uslova j(xk) ÎD f-ja treba da bude neprekidna na posmatranom intervalu i da generise konvergentan niz xk tj. da postoji lim(k->...)xk=xÎD tada je x=lim(k->...)xk=lim(k->...)j(xk-1)= j(lim(k->...)xk-1)= j(x).Uslov za egzistenciju nepokretne tacke->TT:neka je D=[a,b] i j:D->R neprekidna f-ja sa osobinom j(a) ÎD j(b) ÎD.Tada postoji nepokretna tacka aÎD f-je f TT:neka je j kontrakcija na D.Jednac. j(x)=x ima najvise jedno res. u D. TT:neka je j:D->D kontrakcija sa konstantom g tada iterativni niz xk odredjenim iterativnim pravilom xk+1= j(xk) k=0... Sa proizvoljnim x0ÎD konvergira ka jedinstvenom res. jednac. x=j(x) u D. 20. Postupak polovljenja postupak polovljenja intervala je jedan od najednostavnijih, eli u nekim slucajevima i veoma efikasan metod. Neka je data jednacina 1 f(x) = 0 gde je f Î C(D), D=[a,b], f(a)f(b)<0. Na osnovu leme tada postoji bar jedna tacka x Î D takva da je f(x)=0. POstupak polovljenja intervala sastoji se u sledecem: POdelimo segment [a,b] tackom c=(1/2)(a+b) na segmente [a,c] i [c,b]. Ako je f(c)=0 onda je x=c jedno resenje jednac., ako je f(c)!=0, onda se jedno resenje onda se jedno resenje nalazi u jednom od intervala [a,c] [c,b]. Ako je f(a)f(c) <0 onda se resenje jednac nalazi sigurno u interv. [a,c], a ako je f(c)f(b) <0 resenje u interv. [c,b]. Neka je novi interval koji sadrzi bar jenu nulu oznacen sa [a1,b1] tada je [a1,b1] Ì[a,b] i b1-a1=(1/2)(b-a). Postupak polovljenja sada ponavljamo na isti nacin sa intervalom [a1,b1] itd. Tako dobijamo niz intervala [a1,b1]..[an,bn] kao niz sredina ovih intervala c1..cn... koje predstavljaju aproksimacije resenja x date jednac. Postupak zavrsavamo kada dovoljno mali interval [an,bn] uzevsi njegovu sredinu c=(1/2)(an+bn) za aproksimaciju resenja. Duzina intervala [an,bn] jednaka je bn-an=(1/2^n)(b-a). Ako pocetni interval [a,b] oznacimo sa [a0,b0] a njegovu sredinu sa c0=(1/2)(a0+b0) imamo da je |x-c0|<=(b0-a0)/2 u svakom koraku vazi procena |x-cn|<=(bn-an)/2 |x-c0|<=(b0-a0)/(2^(n+1)) lim(n->...)cn=x. Predpostavimo da aproksimacija cn korena xtrazimo sa tacnoscu e tj. trazimo cn za koje vazi |x-cn|<e, ovo ce biti postignuto ako je (b-a)/(2^(n+1))< e n>(log(b-a)-log2e)/(log2) 22. Greska gausovog postupka eliminacije Resenje dobijeno gausovim postupkom eliminacije se razlikuje od teorijski tacnog resenja x=A^(-1)b. Do ovog odstupanja dolazi zbog zaokruzivanja elementa matrice A, koordinata vektora b i zbog gresaka zaokruzivanja koje se pokavljuju tokom postupa eliminacije. Neka je novodobijena matrica oznacena sa  i novi vektor sa  . Matrica i vektor TRA= - A TRb = - b predstavljaju pocetne greske. Uslovno broj regularne matrice A za neku prirodnu matricnu normu || || je broj c(A) = ||A|| ||A^(-1)|| uslovni broj matrice je uvek veci ili jednak 1 jer je 1=||E||=||AA^(-1)||<=||A|| ||A^(-1)||=cA neka je TRx= -x gde je x=A^(-1)b, a je resenje sistema =. LEma ako je za neku prirodnu matricnu normu ||A||<1 onda su matrice E-A i E+A regulrane i 1/(1+||A||)<=||(E+-A^(-1))||<=1/(1-||A||). TT: Neka je dat sistem Ax=b pri cemu je A regularna matrica. Ako pocetne greske matrice sistema i slobodnog vektora TRA i TRb uzrokuju gresku resenja TRx odnosno vazi (A+TRA)(x+TRx)=b+TRb pri cemu je ||TRA|| ||A^(-1)||<1 onda je ||TRx||/||x||<=c(A)/(1-(c(A)(||TRA||/||A||)))(||TRA||/||A|| + ||TRb||/||b||).Neka je x=A^(-1)b tacno resenje i =x+dx resenje dobijeno postupkom eleminacije.Tada je A=A(x+dx)=b+r gde je r rezidualni vektor za tj. r=A-b. Neka je C priblizna inverzna matrica za matricu A R+AC-E rezidualna matrica,  stvarno izracunata rezidulana matrica . Matrica dR=-R i njena norma ||R|| mogu se proceniti. Ako je =x+dx resenje sistema dobijenog gausovim sistemom eliminacije i ||||+||dR||<1 onda je ||dx||<=(||C||/(1-||||-||dR||))(|| ||+||dr||. 23. Iterativni postupci za resavanje sistema linearnih jednacina Jedinstveno resenje x=a^(-1)b posmatranog sistema odredjuje se kao resenje ekvivalentnog sistema x=Gx+d (8). Dvva sistema liner. jednac. su ekviv.ako je svako resenje sist. resenje i drugog sist. i obrnuto. Polazeci od sistema (8) i proizvoljnog pocetnog vektora x^0 Î R^n konstruise se iterativni niz x^k po iterativnom pravilu X^(k+1)=Gx^k+d (9) , k=0... Kada je niz x^k konvergentan, kaze se da iterat. postupak konvergira. Za regulranu matricu A postoji proizvoljni mnogo matrica G takvih da su sistemi Ax=b i x=Gx+d ekvivalentni, ali su samo neke matrice pogodne za iterativnu matricu. U opstem slucaju se moze reci kako birati matricu G tako da se dobije konvergentan iterativni postupak. Najcesce se posmatra razlaganje matrice A A=M-N, sistem Ax=b se transformise u sistem x=M^(-1)Nx+M^(-1)b gde je G=M^(-1)N, d=M^(-1)b. TT: niz x^k dat iterativnim pravilom (9) konvergira ka jedinstvenom resenju sist.(8) za proizvoljno x^0 Î R^n ako i samo ako p(G)<1. Pri resavanju sist. linear. jednac. izracunava se konacan broj clanova iterativnog niza i neko x^k se uzima kao aproksimacija tacnog resenja, potrebno je proceniti gresku –ktog clana niza tj. ||x^k-x|| gde je x tacno resenje sistema (8). TT: Neka je G Î R^n,n takva matrica da je za neku normu zadovoljeno ||Gy-Gz||<= g||y-z|| y,z Î R^n gde je g R [0,1). Ako je x jedinstveno resenje sist. (8) a niz x^k dat intrevalnim pravilom (9) sa proizvoljnim x^0 Î R^n onda je ||x^k-x||<= (g/(1-g))||x^k-x^(k-1)||<=( g^k/(1-g))||x^1-x^0|| k=1... Gaus-Zajdelov postupak x^(k+1)=BGx^k+h, k=0... 24. Konvergencija iterativnih postupaka za resavanje sistema linear. jednac. Matrica A =[aij] Î R^(n,n) je strogo dijagonalno dominantna po vrstama ako je |aii|>SUM(j=1,n j!=i) |aij|, i=1..n, a strogo dijagonalno dominantna po kolonama ako je |ajj|>SUM(i=1,n j!=i) |aij|, j=1..n. TT: Neka je A strogo dijagonalno dominantna matrica po vrstama ili kolonama. Tada Jakobijev postupak konvergira ka jednostavnom res. sist. Ax=b za proizvoljno x^0 Î R^n. LEma: Neka je A strogo dijag. dominantna matrica po vrstama ili kolonama. Tada je A regularna matrica. TT: Neka je A strogo dijag. dominantna matrica po vrstama ili kolonama. Tada Gauss-Zajdelov postupak konvergira ka resenju sistema Ax=b za svako x0 Î R^n. 25. Metode za inverziju matrica Neka je data regular. matrica A=[aij] Î R^n. Njena inverzna matrica  ima elemente xij i,j=1..n koje treba odrediti. Za svaku kolonu matrice A^(-1) uvedimo oznaku x^((k))=[xk1..xkn]^T k=1..n i analogno tome oznacimo sa e^((1))=[1 0...0]^T e^((2))=[0 1...0]^T, .., e^((n))=[0 0...1]^T kolone jedinicne matrice E reda n. A x^((k)) = e^((k)) k=1..n. Neka je data regular. matrica A reda n
ciju je inverznu matricu A^-1 potrebno odrediti. Pretpostavimo da je pronadjena matrica X0 koja predstavlja aproksimaciju iverzne matrice A^-1. Takvu matricu moguce je dobiti pomocu Gausovog metoda kao sto je upravo opsiano. Datu aproksimaciju X0 mozemo poboljsati koriscenjem iterat. metoda. Def. matricu F0=E-AX0 koja predstavlja meru odstupanja matrice X0 od A^(-1). Ako bi vazila jednakost X0=A^(-1) tada bismo imali da je F0 = 0. Inace , sto je manja norma matrice F0 utoliko se X0 i A^(-1) manje razlikuju. Ideja je da pomocu matrice F0 procenjujemo gresku aproksimacije X0 omogucava konstrukciju iterat. procesa za dobijanje niza poboljsanih aproksimacija [Xk] koje ce konvergirati ka trazenoj matrici A^(-1). Neka m Î N i m>1. Def. niz matrica Xk=Xk-1(E+Fk-1+(Fk-1)^2+(Fk-1)^(m-1)) k=1... gde je Fk=E-Axk. TT: Neka je data matrica X0 takva da je ||F0||<=q<1. Tada niz matrica [Xk] def. formulom onvergira ka a^(-1). TT: iterativni proces def. formulom ima red konvergencije m pod uslovom da vazi prethodna teorema. 26.Odredjivanje sopstvenioh vrednosti matrica Neka je A{aij}ÎC^n.Vektor x!=0 naziva se sopstveni vektor matrice A ako postoji skalar lÎC tako da vazi Axlx(18).Skalar l naziva se sopstvena vrednost matrice A koja odgovara sopstvenom vektoru x.Sopstveni vektori su ne nula resenja matricne jednac.(18) koje se drugacije moze napisati u obliku (A-lE)x=0(19).Matricna jednac.(19)predstavlja homogen linearni sistem koji ima netrivijalna resenja akko je DET sistema =0. TT:neka je A{aij}ÎC^n,neka su Ci(i=1..n) diskovi u kompleksnoj ravni sa centrima u aii i poluprecnicima ri=SUM(j=1,n,j!=i)|aij|.Tada se sve sopstvene vrednosti matrice A nalaze se u oblasti C=unija(i=1,n)Ci.Skup svih sopstvenih vrednosti matrice A naziva se spektar matrice A. Neka su l1.. ln sve sopstvene vrednosti matrice reda n.Tada se broj J(A)=max|li| naziva spektralni radijus. Za sopstvene vrednosti date matrice mozemo pretpostaviti da su numerisani tako da vazi |l1|=...=|lr|>=|lr+1|>=...>=|ln|.Tada se l1.. lr nazivaju dominantne sopstvene vrednosti.Sopstveni vektor koji odgovara dominantnoj sopstvenoj vrednosti naziva se dominatni vektor.Metod stepenovsnja: z^(k+1)=Ay^k, y^k=z^k/gk gde je gk=max(i|(zi)^k|=||z^k||.Tada je lim(k->...)gk=l1 a lim(k->...)y^k=x1. 28.Gradijentni metod Za res.sist.nelin.jednac. koristi se i gradijentni metod koji ne zahteva izracunavanje inverzne matrice.Uvedimo pomocnu f-ju U(x)=SUM(i=1,n)fi^2(x1..xn)=(F(x),F(x)).Ako je x=(x1.. xn) res.sist. tada je U(x)=0. Gradijentni metod zasniva s upravo na minimizaciji ove f-je.Neka je X^0 neka pocetna aproksimacija.Konstruisimo niz aproksimacija x^n koji su takve da je U(x^0)>U(x^1)>... elemente niza x^n dobicemo po formuli x^(k+1)=x^k-lk gradU(x^k) (8),k=0...U formuli (8) treba odrediti faktore lk.To cemo uciniti iz uslova da skalarna f-ja f(l)=U(x^k-lk gradU(x^k) ima minimum u tacki lk. f’(l)=(¶/¶l)U(x^k l gradUx^k.Uvodjenjem Jakobijeve matrice za vektor f-je Fmozemo napisati da je lk (F(x^k), J(x^k)gradU(x^k)/(J(x^k)gradU(x^k), J(x^k)gradU(x^k) ).Konacno za koeficijente lk dobajamo lk=(1/2)((F^k,JkJk^TF^k)/(JkJk^TF^k, JkJk^TF^k ) )gde je F^k=F(x^k) Jk=J(x^k).Gradijentni metod mozemo napisati u obliku x^(k+1)=xk-2lkJk^TF^k k=0... 29. Priblizno analiticki metodi i Ojlerov metod za resavanje difer. jednac. Analiticki metodi daju priblizno resenje postavljenog problema . Najjednostavniji je metod neodredjenih koeficijenata. Neka je dat Kosijev problem tj. y’=f(x,y), y(x0)=y0 potrazimo resenje ovog problema u obliku reda y(x)=a0+a1(x-x0)+a2(x-x0)^2... gde su a0,a1,a2... nepoznati koefic. Na osnovu pocetnog uslova y(x0)=y0 dobijamo za prvi koefic. a0=y0. Ostale koefic. dobicemo izjednacavanjem y’(x)=f(x,y(x)) gde je y’(x)=a1+2a2(x-x0)+3a3(x-x0)^2+... Pikarov metod sukcesivnih aproksimacija sastjoi se u sledecem: Kosijev problem mozemo predstaviti y(x)=y0 + ò(x0,x) f(t,y(t))dt (3). Polazeci od neke pocetne aproksimativne funkcije y^[0](x), na osnovu (3) mozemo konstruisati niz uzastopnih aproksimacija y^[k] pomocu formule y^[n+1](x) = y0 + ò(x0,x)f(t,y^[n](t))dt. Ojlerov metod ne spada u analiticke metode. Neka je na intervalu [a,b] dat kosijev problem y’=f(x,y), y(x0)=y0 cije resenje se trazi. Interval [a,b] podelicemo na n podintervala x0=a, xk=a+ahk (k=1..n, h=(b-a)/n. Pretpostavimo da je funkcija y neprekidna zajedno sa svojim izvodima . Tada na osnovu tejlorove formule postoji tacka x1 izmedju tacaka x0 i x takva da je y(x) = y(x0)+(x-x0)y’(x0)+(((x-xo)^2)/2)y’’(x1). Ukoliko je korak h dovoljno mali mozemo zanemariti poslednji clan na desnoj strani i za aproksimaciju tacne vrednosti y1(x) uzeti y1=y0+hf(x0,y0). yk+1=yk+hf(xk,yk) k=0..n-1(5). Usvakom koraku definisanom formulom (5) ucinjena je greska jednaka y’’(xk)(h^2)/2 na celom intrevalu [a,b] posle n koraka greska iznosi SUM(k=1,n)y’’(xk)(h^2)/2. 30. Metodi Runge-Kuta Runge i Kuta razvili su metode koje se zasnivaju na primeni tejlorovog reda ali izbegavaju izracunanje izvoda date difer. jednac. Neka je dat kosijev problem y’=f(x,y) y(x0)=y0, resenje y=y(x) problema ima tejlorov razvoj y(x+h)=y(x)+hy’(x)+((h^2)/2!)y’’(x)+((h^3)/3!)y’’’(x)+... Kod metode runge-kuta reda dva pribliznu formulu trazimo u obliku y(x+h)=y(x)+w1k1+w2k2 gde je k1=f(x,y), k2=f(x+ah,y+bk1), odnosno u obliku y(x+h)=y(x)+ w1hf(x,y) +w2hf(x+ah,y +bhf(x,y)) potrebno je oderediti w1 i w2, b i a tako da prethodna formula bude sto tacnija. w1=1/2 =w2, b = a=1 Metod runge kuta reda 2 gasi y(x+h)=y(x)+(h/2)f(x,y)+(h/2)f(x+h, y+hf(x,y)). Oznacimo sa yn=y(x) i yn+1=y(x+h) dobijamo yn+1=yn+(h/2)(k1+k2) gde he k1=f(x,y), k2=f(x+h,y+k1). Metod R-K reda 4 yn+1=yn+(h/6)(k1+2k2+2k3+k4) gde su k1=f(x,y), k2=f(x+(h/2), y+(h/2)k1), k3=f(x+(h/2), y+(h/2)k1), k4=f(x+h, y+hk3). 32.Racunanje sa intervalima. Pod realnim intervalom [a,b] podrazumevamo zatvoren ogranicen skup realnih brojeva [a,b]={x:a<=x<=b;a,b, ÎR}.Intervale cemo oznacavati velikim slovima,a njihove krajeve malim slovima latinice npr. A=[a1,a2].Skup svih intervala oznacicemo sa Int R.Realne brojeve,smatracemo za degenerisane intervale i obelezavati ih malim slovima latinice;npr. a=[a,a].Dva intervala A=[a1,a2] i B=[b1,b2] su jednaka,u oznaci A=B,akko su oni jednaki kao skupovi.Neka je * jedna od osnovnih operacija u skupu R.Odgovarajuce operacije u skupu Int R defenisu se kao globalne operacije,tj. A*B={a*b:aÎA,bÎB}.U definiciji se pretpostavlja da kod deljenja 0ÏB. [a1,a2]+[b1,b2]=[a1+b1,a2+b2] [a1,a2]-[b1,b2]=[a1-b1,a2-b2].Za mnozenje vazi [a1,a2][b1,b2]=[min(a1b1,a1b2,a2b1,a2b2),max(a1b1,a1b2,a2b1,a2b2)].Ako je A=[a1,a2],onda je -A odredjeno sa -A={-a:aÎA}=(-1)A=[-a2,-a1],a 1/A odredjeno sa 1/A={1/a:aÎA}=[1/a2,1/a1], 0ÏA.Sada je A-B=A+(-B); A/B=A*(1/B) -ÏB.TT:Naka A,B,CÎInt:R.Tada vazi A+B=B+A i AB=BA}komutativnost;A+(B+C)=(A+B)+C i A(BC)=(AB)C} asocijativnost;A+0=0+A=A-neutralni elem.za sabiranje;A*1=1*A=A-neutralni elem.za mnozenje;A(B+C) ÍAB+AC subdistributivnost; a(B+C)=aB+aC, aÎR-"distributivnost".TT:Neka je Ak, BkÎInt:R, k=1,2.. i neka vazi Ako Í Bk,k=1...Tada za opraciju *E{+,-,puta,:} imamo A1*A2ÍB1*B2.Poluprecnik(poluduzina) r(A) i sredina(centar) c(A) intervala A=[a1,a2] definisu se sa r(A)=1/2(a2-a1) i c(A)=1/2(a1+a2).Velicina d(A)=2r(A) naziva se duzina(sirina) intervala A. 33.Intervalni vektori i matrice.Skup svih n-dimenzionalnih vektora x=(x1,x2,...,xn)takvih da xiÎXiÎInt R,i=1..n nazivamo n-dimenzionalni intervalni vektor i oznacavamo sa x=(X1,X2..Xn)-veliki X!!!.Skup svih n-dimenz. interv. vektora oznacavamo sa Int R^n.n-dimenz. interv.vektor je uredjena n-torka intervala.Svaki interval Xi(i=1..n) nazivamo intervalna koordinata vektora X.Neka je R^(m,n) skup svih realnih matrica tipa mxn.Skup svih intervalnih matrica A=[aij]m,n takvih da aijÎAijÎInt R (i=1..m)(j=1..n) nazivamo intervalna matrica tipa mxn i oznacavamo A=[Aij]m,n.Skup svih intervalnih matrica mxn oznacavamo sa Int R^(m,n).Intervalna matrica je pravougaona sem intervala.TT:Neka A,B,C intervalne matrice,a B,C obicne matice,tada vazi A+B=B+A-komutativnost; A+(B+C)=(A+B)+C-asocijativnost;A+O=O+A=A-(O je nula matrica); A°I=I°A=A-(I je jedinicna matrica); (A+B) °CÍA°C+B°C i C° (A+B)podsup=C°A+C°B}subdistributivnost; (A+B) °C=A°C+B°C i Ckr(A+B)=C°A+C°B}"distributivnost";A°BCÍ(A°B) °C.Umesto A°B pisemo AB.matrica poluduzina r(A)=r[r(Aij)];matrica srdina c(a)=[c(Aij)];matrica apsolutnih vrednosti |A|=||Aij||.Matricna norma intervalnematrice A=|Aij| definise se sa max{||A||},AÎA gde je ||tacka|| proizvoljna matricna norma.U upotrebi je najcesce matricna norma ||A||...=max{||A||...}=max{sum(j)|Aij|} AÎA i <-ovaj red treba tako!!!! 34.Sistemi linearnih intervalnih jedacina Posmatrajmo sistem liearnih jednacina Ax=b (3) gde je A=[aij]n, b=[bi]n,1 x=[xj]n,1. neka je poznato samo da elementi aij matrice A leze u intervalima Aij, a koordinate bi vektora b u intervalima Bi. Stavimo A=[Aij]n i b=[Bi]n,1. Interesuje nas skup resenja sistema (3) kada se matrica A menja unutar intervalne matrice A, vektor b menja unutar intervalnog vektora b. Interesuje nas skup x^*={x: Ax=b, A Î A, b Î b)}. Sistem (3) nazivamo intervalni sistem linear. jednac. Ax=b gde je x intervalni vektor Ax Ê b . x^* Í A^(-1)b. Skup resenja x^* je komlikovan. Zbog toga se cesto umesto tacnog resenja x^* uzima n-dimnezionalni intervalni vektor koji sadrzi x^*. Intervalni vektor: IC{x^*} = [inf{X^*},sup{X^*}]^T Ê x^*, najmanji je medju svim intervalnim vektorima koji sadrze x^* i naziva se intervalno zatvaranje skupa resenja. Posmatrajmo prosirenu matricu sistema [ A: b ] primenjujuci formule: Aij’=Aij, (j=1..n) B1’=B1 i Aij’=Aij-A1j(Ai1/A11), Bi’=Bi-Bi(Ai1/A11), Ai1’=0 (i,j=2..n) dobijamo novu prosirenu matricu sistema [A’ : b’] gde je A’=[Aij’] i b’=[bi’]. Neka A=[aij]n Î A i b=[bi]n,1Î b. Obrazujmo novu matricu A’=[aij’] i novi vektor b’=[bi’]n,1 gde je aij’=aij, (j=1..n) b1’=b1 i aij’=aij-a1j(ai1/a11), bi’=bi-b1(ai1/a11), ai1’=0 (i,j=2..n). Ax=b i A’x’=b’ kako je A’ Î A’ i b’ Î b’ moxemo zakljuciti da vazi x^*={x: Ax=b. A Î A, b Î b} Í {x’: A’x’ = b’, A’ Î A’, b’ Î b’}. konvergencija niza intervalnih matrica A^((k)) k=0... tipa mxn ka matrici A tj. lim(k->...)A^((k))=A ekvivalentna je sa lim(k_...)Aij^((k))=Aij. Posmatrajmo sada jednacinu oblika x=Ax+b (8) gde A Î A b Î b. Tada vazi teorema TT: Iterativni niz x^(k+1)=Ax^((k)) = b ,k>=0 konvergira ka jedinstvenoj nepokretnoj tacki x^* sistema (8) za proizvoljno x^((0)) Î Int R akko je J(|A|)<1. 17.Greske i konvergencije opsteg iterativnog postupka za res. jednac. Nepokretna tacka f-je f (x), odnosno res. ekviv. jednac. f(x)=0, moze se dobiti kao granicna vrednost konvergentnog niza sukcesivnih aproksimacija. Uvek se izracunava samo konacan broj clanova iterativnog niza i potrebno je odrediti gresku aproksimacije xk. TT:Neka je fÎC^1(D), xÎD res.jednac. f(x)=0 i xkÎD.Ako je |f'(x)|>=m>0 za xÎD,onda je |xk-x|<=|f(xk)|/m TT:Neka je f kontrakcija na D sa konstantom kontrakcije g; x0ÎD;Xk+1=f (xk) ÎD,k=0...Ako je aÎD jednacine x=f (x)onda je |xk-a|<=g/(1-g) |Xk-1 - Xk|<=g^k/(1-g)|x1-x0|,k=1...Posto se izracunava samo konacan broj aproksimacija,priblizno res. x je potrebno izracunati sa odredjenom tolerancijom x.Ukoliko je proces Xk+1=f (xk) konvergentan, tada postoji indeks K za koji je |Xk=x|<x . Ako je iterativni proces takav da vazi |Xk-Xk-1|>=|Xk-x|, gde su Xk+-1 i Xk dve uzastopne aproksimacije, tada se za izlazni kriterijum uzima relacija |Xk-Xk-1|<=x.Proces se zaustavlja nakon k-tog iterativnog koraka, a za aproksimaciju resenja x uzima se vrednost Xk.Uslove koje je potrebno ispuniti da bi se aproksimaciaa Xk prihvatila kao res.posmatrane jednac. nazivaju se pravila zaustavljanja ili izlazni kriterijumi.Brzina konvergencije iterativnog postupka meri se redom konvergencije. Neka je aÎD i lim(k->...)Xk=a.Ako postoji konstanta NETAE [0,1) i ceo broj K>=0 takav da za k>=K vazi |Xk+1-a|<=h|Xk-a| kaze se da je niz {Xk} linearno konvergentan.Red konvergencije opsteg iterativnog postupka moze se odrediti na osnovu sledece TT: Nake je fÎC^p(D).Ako je x0ÎD,Xk+1=f (Xk) ÎD,k=0..., lim(k0->...)Xk=a i f (a)=a, f'(a)= f''(a)=...= f^(p-1)( a)=0, f^p(a)!=0 onda je niz {Xk} konvergentan sa redom p. 18.Njutnov iterativni postupak.Jedan od najjednostavnijih postupaka za resavanje jednac. oblika f(x)=0 je Njutnov postupak.U osnovi ovog postupka je aproksimacija posmatrane f-je f linearnom f-jom u bliziniresenja. Za lin.f-ju se uzima tangenta na krivu f(x) u tacki (x0,f(x0)), gde je x0 pocetna aproksimacija trazenog res. Presek tangente i X-ose je nova aproksimacija trazenog resenja.Onda se postavlja tangenta na krivu f(x) u tacki (x1,f(x1)) i postupak se nastavlja. Jednac.tangente u tacki (x0,f(x0)) je:y(x)=f(x0)+f'(x0)(x-x0).Ako je f'(x)!=0 naredna aproksimacija x1 se dobija kao res.jednac. y(x)=0,tj.x1=x0-f(x0)/f'(x0).Ako je Xk k-ta aproksimacija posmatrane jednac., sledece aproksimacije se dobijaju po iterativnom pravilu xk+1=xk-f(xk)/f'(xk) k=1... TT:Neka je D otvoreni interval u R,f:D->R,f'ÎLipg (D) i neka postoji m>0 takvo da je |f'(x)|>=m,xÎD.Ako jednacina f(x)=0 ima resenje xÎD,onda postoji enta>0 takvo da za x0 sa osobinom |x0-x|<=enta,niz {xk}def.iterat. pravilom postoji i konvergiara ka x.Pri tome vazi |x(k+1)- x|<=g/2m |xk-x|^2,k=0...Ova TT daje uslove za konvergenciju Njutnovog postupka.TT:Neka je D otvoreni interval u R,f:D->R,fÎC(D),|f''(x)|<M,xÎD,M>0 i za neko m>0,|f'(x)|>=m,xÎD. Ako jednacina f(x)=0 ima resenje xÎD,onda postoji enta>0 takvo da za x0 sa osobinom |x0-x|<=enta,niz {xk} def.iterat. pravilom postoji i konvergiara ka x.Pri tome vazi |xk-x|<=M/2m |xk-x(k-1)|^2,k=0...TT:Neka je D=[a,b], f:D->R, fÎC^2(D).Ako su zadovoljeni uslovi 1]f(a)f(b)<0,2]f'(x)!=0, xÎD,3]f''(x)<=0,xÎD ili f''(x)>=0,xÎD , 4]za neko x0ÎD,f(x0)f''(x0)>0, onda Njutnov iterativni postupak konvergiraa ka jedinstvenom resenju xÎD jednac. f(x)=0.Pored toga, ukoliko se postupak ne prekine zbog f(xk)=0,vazi za k=0...Njutnov postupak zahteva izracunavanje vrednosti I izvoda f-je u svakoj iteraciji.Ako je racunanje f-je slozeno pribegava se modifikacijam Njutnovog postupka sa ciljem pojednostavljenja racunanja.najjednostavniji primer takvih modifikacija je pojednostavljeni Njutnov postupak. Za konstantnu vrednost C definise se xk+1=xk-f(xk)/C,k=0.. 19.Postupak secice.Neka su date 2 pocetne aproksimacije x0 i x1 resenja jednac.f(x)=0.Linerni interp.polinom za f-ju f(x) sa cvornim tackama (x0,f(x0)),(x1,f(x1)) ima oblik p(x)=f(x0)+f[xo,x1](x0-x1),gde je f[x0,x1] podeljena razika prvog reda,pa je njegov izvod p'(x)=f[x0,x1].Zamenjujuci f'(x1) u Njtnovom interpolacionom pravilu sa p'(x1),dobija se aproksimacija x2, x2=x1-(f(x1)/f[x0,x1])=x1-((x1-x0)/(f(x1)-f(x0))f(x1).Pri izracunavanju aproksimacije xk+1 formira se interpolacioni polinom sa cvornim tackama (xk,f(xk)),(xk-1,f(xk-1)),pa se na opisani nacin,uz pretpostavku xk!=xk-1 i f(xk)!=f(xk-1),dobija iterativno pravilo xk+1=xk-((xk-xk-1)/f(xk)-f(xk-1))f(xk),k=0... TT:neka je f-ja fÎC^2(D) takva da je |f'(x)|>=m>0, M>=|f''(x)|,xÎD.Ako jednac. f(x)=0 ima res. xÎD,onda postoji h>0 takvo da za sve x0,x1ÎDn(x),x0!=x1,postupak secice konvergira ka x i vaze ocene |xk-x|<=(2m/M)q^Fk,k=2,3.. i |xk-x|<=(M/2m)|xk-1-xk||xk-2-xk|,k=2,3..gde je q=(M/2m) h<1,ili se postupak prekida zbog f(xk)=0.TT:Nela je D=[a,b],f:D->R,fÎC^2(D).Ako su zadovoljeni uslovi 1]f(a)f(b)<0,2]f'(x)!=0, xÎD,3]f''(x)<=0, xÎD ili f''(x)>=0, xÎD , 4]za neko 1ÎD,f(x1)f''(x1)>0,onda postupak secice konvergiraa ka jedinstvenom resenju xÎD jednac. f(x)=0.Ukoliko se postupak ne prekine zbog f(xk)=0.
 |
RSS link na komentare