Download - cap rez ec

Transcript

DanielFlorinSOFONEAAnalizaNumericasiTeoriaAproximariiSibiu2006CuprinsI Rezolvareaecuat iilortranscendente 41 Introducere 52 Metodeiterative 72.1 Ordinuldeconvergent aalmetodeloriterative . . . . . . 72.2 Criteriideconvergent a . . . . . . . . . . . . . . . . . . . 82.3 Punctedeatract ie sipunctederepulsie. . . . . . . . . . 133 Metodeclasicederezolvareaecuat iilortranscendente 173.1 Metodacoardei . . . . . . . . . . . . . . . . . . . . . . . 173.1.1 Ordindeconvergent a. . . . . . . . . . . . . . . . 183.1.2 Interpretaregeometrica. . . . . . . . . . . . . . . 223.2 Metodasecantei . . . . . . . . . . . . . . . . . . . . . . . 223.2.1 Convergent ametodei . . . . . . . . . . . . . . . . 223.2.2 Ordindeconvergent a. . . . . . . . . . . . . . . . 233.2.3 Interpretaregeometrica. . . . . . . . . . . . . . . 263.3 MetodaluiNewton . . . . . . . . . . . . . . . . . . . . . 263.3.1 Construct iametodei . . . . . . . . . . . . . . . . 263.3.2 Ordindeconvergent a. . . . . . . . . . . . . . . . 303.3.3 Interpretaregeometrica. . . . . . . . . . . . . . . 313.4 Comparat ii ntremetodacoardei simetodaNewton . . . 323.5 Metoda njumat at iriiintervalului . . . . . . . . . . . . . 333.6 Metoda lui Schroder pentru determi-narea rad acinilormultiple . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 Metodecuordindeconvergent asuperior 374.1 Teoremadepunctx . . . . . . . . . . . . . . . . . . . . 374.2 Metodecumaimult ipasi . . . . . . . . . . . . . . . . . 392Cuprins 34.3 MetodaluiCebsev . . . . . . . . . . . . . . . . . . . . . 444.3.1 Cazuriparticulare . . . . . . . . . . . . . . . . . . 454.4 MetodaluiSteensen. . . . . . . . . . . . . . . . . . . . 464.4.1 Cazuriparticulare . . . . . . . . . . . . . . . . . . 474.5 MetodaluiTraub . . . . . . . . . . . . . . . . . . . . . . 494.5.1 C atevafunct iiiterativecuunsingurpunctdestart 514.6Imbunat at ireaordinuluideconvergent a. . . . . . . . . . 524.6.1 Aplicat ie(MetodaluiRomberg) . . . . . . . . . . 54ParteaIRezolvareaecuat iilortranscendente4Capitolul1IntroducereUnul dintreobiectiveleanalizei numericel constituieg asireaunormetode aproximative pentru determinarea solut iilor unei ecuat ii de formaf(x) = 0, x J, (1.1)undef:X R, J X R, poates ae ngeneral chiarsi ofunct ietranscendent a.Pentruexplicareaacestuitermens aconsider ammult imeaecuat iilordiferent ialeliniare,deordinarbitrarM,cucoecient iia0, a1, . . . , aM,E(y; x) M

k=0ak(x)y(Mk)(x) = 0, x X,funct ii rat ionale. Dac a nuexist aoastfelde ecuat ieastfel ca E(f; x) = 0spunemcafestetranscendentape X. Exemplede astfel de funct ii suntfunct iaGamma,funct iaZetaaluiRiemann,etc.Scopul acestei lucr ari estedeaprezentaosintez aaasanumitelormetode iterativepentru rezolvareaunorastfel de ecuat ii,pe scurtacestemetodeseobt inastfel:Ecuat ia(1.1)sescriesuboform aechivalent ax = (x), x J, (1.2)unde(x) = (f; x).Deexempluputemconsidera(f; x)=x f(x)h(x)cuh(x) =0,oricare ar x J. Presupunand c a (1.1) are o singur a solut ie x, x J56 Capitolul1. Introducerevarezultac axesteunpunctxalui . Seformeaz asirul deiterat ie(xn)n0xn+1= (xn), n = 0, 1, . . . . (1.3)Adesea funct ia ind continua pe Jne intereseaza s a alegem astfelncat:termenii lui (xn)n0sasepoat aconstrui, adicaxk J, oricareark= 0, 1, . . .;(xn)n0 sa convearg a, n care caz pe baza continuitat ii limnxn= x;Rapiditatea de convergent a a lui (xn)nsa e c at mai mare.Aceastarapiditatedeconvergent asevaevaluaprinintermediulordinuluideconvergent a.Capitolul2Metodeiterative2.1 Ordinul de convergent a al metodeloriterativeFie(xk)unsir numericoarecareconvergent lax. Vomconsiderantotdeaunaunastfel desirgeneratdeometod aiterativ adecalcul iarpexdreptsolut ieauneiecuat ii,f(x) = 0.Denit ia2.1.1Vomspunec asirul (xk) areordinul deconvergent ardacalimk|xxk+1||xxk|r= , (2.1)unde0 < < +. Constantareal asenumesteeroareaasimptotic aametodei.Numarul rconstituieomasur aavitezei deconvergent a(cuc atrestemai marecuat atiterataurm atoarexk+1trebuiesaemai aproapedesolut ie). Vomspunec aconvergent aesteliniar adac ar = 1,superliniar adaca1 < r< 2sipatraticadac ar= 2. Dac asirulsatisfaceorelat iedeforma|xxk+1| |xxk|r0,78 Capitolul2. Metodeiterativeatunci,daca exist aun rastfel ncat (2.1) s aaib a loc, avem r r0. Dac ar < r0,rezult a|xxk+1||xxk|r0= |x xk+1|xxk|r1|xxk|r0r , k ,n contrazicere cu relat ia precedent a. Vom spune c a metoda are ordin deconvergent acelput inr0.2.2 Criteriideconvergent aConsideram[a, b]unintervalalaxeireale siconsideramecuat iaf(x) = 0undef: [a, b] R.Fie

= (xn)n=0unsirdenumererealedinintervalul[a, b]sis 2unnumarnaturaldat.Cercetam condit iile n care sirul

este convergent, av and ordinul deconvergent a num arul natural s, fat a de fsi daca not am cu x=limnxn,atuncixesteor ad acin aaecuat ieif(x) = 0.Teorema2.2.1(vezi [?]). Dacasirul

, funct iafsi num arul real sipozitivsuntastfel nc at:(i) intervalul = (x0, x0 + )estecont inut nintervalul [a, b];(ii) funct iafestederivabil ap an alaordinulsinclusivpeecarepunctal intervaluluisisupx|f(s)(x)| = M< +;(iii) exist aoconstantareal asi nenegativ a, independent adenastfelnc atpentruoricen = 0, 1, . . .,aulocinegalit at ile:s1

i=0f(i)(xn)i!(xn+1xn)i |f(xn)|s,undexn

, n = 0, 1, . . . ;2.2. Criteriideconvergent a 9(iv) exist aoconstant areal asi nenegativ aindependentadenastfelnc atpentruoricen = 0, 1, . . .,aulocinegalit at ile:|xn+1xn| |f(xn)|undexn

,n = 0, 1, . . .;(v) constantele,sinumerelerealeMsiveric arelat iile:0= v|f(x0)| < 1;0v(1 0) ,undeprinvamnotatv =_ +Ms1s!_1s1,atuncirelativlaecuat iaf(x) = 0silasirul

aulocurm atoarelepropriet at i:(j) sirul

are ordinul de convergent assi dacax=limnxn,atunci(x) = 0;(jj) x [a, b];(jjj) |xn+1xn| s0nv;(jv) |xxn| s0nv(1 s0n);(v) |f(xn)| s0nv.Demonstrat ie: Ar at amc aelementelesirului

suntcont inute nin-tervalul.Pentrux1,baz andu-nepeipoteza(iv)avem|x1x0| |f(x0)| =v|f(x0)|v=0v0v(1 0) ; (2.2)10 Capitolul2. Metodeiterativede unde rezultac a x1 . Deoarece x1 , folosim formula lui Taylor,vomdeduceurmatoareainegalitate:|f(x1)| f(x1) s1

i=0f(i)(x0)i!(x1x0)i+s1

i=0f(i)(x0)i!(x1x0)iMs!|x1x0|s+ |f(x0)|s_Mss!+ _|f(x0)|sdeundededucem|f(x1)| = vs1|f(x0)|s. (2.3)Presupunemprininduct iecaaulocurm atoarelepropriet at i:1. xi ,i = 1, 2, 3, . . . , n;2. |xixi1| s0i1v,i = 1, 2, . . . , n;3. |f(xi)| = vs1|f(xi1)|s,i = 1, 2, . . . , n.Inipotezeledemaisusar at amc aaulocurm atoarelerelat ii:xn+1 ; |xn+1xn| =s0nv, |f(xn+1)| vs1|f(xn)|s.Propriet at ile 1-3 sunt vericate pentri i = 1. Dac a nmult im ambii mem-bri ai inegalit at ilor3cuvsi dacanot ami=v|f(xi)|, i=0, 1, . . . , n,atuncideducemurmatoareleinegalitat ii s0i, i = 1, 2, . . . , n. (2.4)Din inegalit at ile (2.4) si din ipoteza (iv) deducem urmatoarea inegalitate:|xn+1xn| |f(xn)| =v|f(xn)|v=s0nv. (2.5)Dininegalitateademaisusdeduceminegalitat ile:|xn+1x0| n

i=0|xi+1xi| =vn

i=0s0i0v(1 0) .deunderezultac axn+1 . Dinrelat ia(2.5)pentrui = n + 1rezult ainegalitatea2.Pentruinegalitatea3. avem:|f(xn+1)| f(xn+1) s1

i=0f(i)(xn)i!(xn+1xn)i+2.2. Criteriideconvergent a 11+s1

i=0f(i)(xn)i!(xn+1xn)i_ +Mss!_|f(xn)|s= vs1|f(xn|s.Rezult ac apropriet at ile1.-3. aulocpentruoricen = 1, 2, . . ..Ar at amc a sirul

esteconvergent.Fie n si p doua numere naturale. Din faptul ca propriet at ile 1.-3. suntvericatepentruoricenumarnaturaln,rezult aurm atoareledelimit ari:|xn+pxn| n+p1

i=n|xi+1xi| vn+p1

i=ns0is0nv(1 s0n), (2.6)n = 1, 2, . . . .Inegalitateademaisusestevericatapentruoricenum arnaturalp. Deaici rezultac apentruorice>0num arreal exist aunnum arnaturalN()astfel ncatpentrun > N()avems0nv(1 s0n)< deoarece 0< 1. Deci sirul

este un sir fundamental, adica convergent.Dac atrecemlalimitapentrup ninegalitatea(2.6)si not amcux=limnxn,deducem|xxn| vs0nv(1 s0n), n = 1, 2, . . . .Pentrun = 0obt inemdinultimainegalitate|xx0| =0v(1 0) ceeacenearat ac ax . Trebuiesamai ar at amc axesterad acinaecuat ieif(x) = 0. Dinrelat ia(2.4)pentrui avemlimii=limis0i= 0adicalimn|f(xn)| = |f(x)| = 0.Observat ia2.2.1Dacasirul

estegeneratdeometod aiterativadetipulxn+1= g(xn); x0 (a, b], n = 0, 1, . . . , (2.7)12 Capitolul2. Metodeiterativeundeg: [a, b] Resteofunct iecareareurm atoareaform ag(x) = x + (x), (2.8)pentruorice x [a, b], iar : [a, b]R, atunci teorema2.2.1areurm atorul enunt :Teorema2.2.2Fiex0 [a, b], >0si = {x R : |x x0 }.Daca num arul real x0, numarul pozitiv si funct ia dat a de (2.8) se potalegeastefel nc ats ae ndepliniteurm atoarelecondit ii(i) intervalul estecont inut nintervalul[a, b];(ii) funct iafestederivabil ap an alaordinulsinclusivundes 2esteunnumarnaturalsisupx|f(s)(x)| M< +;(iii) aulocurm atoareleinegalit at i:s1

i=0f(i)(x)i!i(x) |f(x)|s,pentruoricex , unde 0esteoconstant areal a, indepen-dent adexsi|(x)| |f(x)|,pentruoricex , unde>0esteoconstant areal a, indepen-dent adex;(iv) numerele,,Msisuntastfel nc ataulocinegalit at ile0= v|f(x0)| < 1,undev=_ +sMs!_1s12.3. Punctedeatract ie sipunctederepulsie 13si0v(1 0) .atunciaulocurm atoarelepropriet at i:(j) sirul(xn)n=0generatdemetodaiterativa(2.7)esteconvergent;(jj) dacax=limnxn,atuncif(x) = 0six ;(jjj) |xn+1xn| s0nv,pentruoricen = 0, 1, . . .;(jv) |xxn| s0nv(1 s0n),pentruoricen = 0, 1, . . ..Aceastateorem aesteconsecint aimediat aateoremeiprecedente.2.3 Puncte de atract ie si puncte de re-pulsieFie(x)denit nJxsiex1 Jx. Form amx2= (x1), x3= (x2), . . . , x+1= (x), . . . (2.9)si se presupune ca punctele astfel obt inute sunt din Jx. Dac an particular(x1) = x1 ntreagasecvent ax(= 1, 2, . . .)const a nrepetarealuix1.Un num arcu proprietatea ca() = este un punctxdeiterat iesau un centru de iterat ie (2.9). Funct ia (x), denit a mai sus se numestefunct iedeiterat ie.Vom folosi V (0) pentru a nota o vecin atate simetrica a lui 0, de exemplu0< x < 0 + , > 0.Presupunem0= (0).14 Capitolul2. MetodeiterativeDenit ia2.3.10este numit punct de atract ie dac a oricare ar ovecin atateV0alui 0si oricarearunpunct destart x1 V0sirul(x)cutermenul generalprecizat n(2.9)satisfacelimnx= 0.Denit ia2.3.20este numit punct de repulsie dac a oricare ar ovecin atateV0alui 0si oricarearunpunct destart x1 V0sirul(x)cutermenul generalprecizat n(2.9)satisfacelimnx = 0.(nafar adecazul ncareunul dinx= 0). (vezi[?]).Teorema2.3.1Fie (x) o funct ie de iterat ie denit an Jx. Pre-supunemc a0=(0), 0(Jx) si ca()

(0). Atunci 0esteunpunctdeatract iesaurepulsiedenitdac aeste ndeplinitarelat ia|

(0)| < 1sau |

(0)| > 1.Inprimulcazavemx+1x

(0)Demonstrat ie: ParteaI.Presupunem|

(0)| < 1.Atunci, dacaalegemunpcu |

(0)| p > 1avempentruoricexdinV (0)(x) (0)x 0 p. (2.12)Caurmare,pentruunx1 V (0)obt inem|x20| p|x10|,astfel ncatx2estemai ndepartatde 0decatx1. Acelasiargumentestevalabil pentru()xat atatimpcatestedinV (0)si estediferitde0.Caurmare,x 0,cuexcept iax= 0si0esteunpunctderepulsie.Observat ia2.3.1 (a) Dacaseiauvalorinafaravecin at at ii V (0),inegalitatea(2.12) nuarelocsi esteposibil caurm atorul nostrupunct s a e 0. Este posibil s a se construiasc a o funct ie neanalitic a(x) astfel nc at n afara unei vecin atat i a lui 0funct ia sa e pestetotegalacu0. Chiar si ofunct ieanalitic aneconstant a(x)poateconstruit aastfel nc ats aeegal acu0launnum ardepunctenit nafaravecin at at iilui0.(b)Incazul |

(0)| 0,3. f(x0)f(x1) < 0.Atunciecuat iaf(x) = 0areosolut ieunicax n(x0, x1),iar sirul {xk}datdemetodacoardei(3.2)convergelax.3.1. Metodacoardei 21Demonstrat ie:Putempresupunecaf

(x)>0pe[a, b]si decif(x0)>0,f(x1) |h(x)| de-alungul luiC. Atuncifunct iileg(x)sig(x) + h(x)auacelasinum ardezerouri nsubregiunealuiG nchis adeC.Aplicamaceast ateorem alui g(x)=L(x), h(x)=T(x), nvecin atatealuiKxpentruC,siL(x) + T(x)= f(x) . Din(3.26)vedemc adoarzeroulluiL(x)estedatprinx

0=f

0.Folosindrelat ia(3.21)obt inem|x

0| = ||f

0| < r Mr22|f

0|< r,x0estedininteriorulluiKx.Inplus,avem nKxexactor ad acin aaluif(x) = .Vedem ca funct ia invers ax = () este analitic a si satisface inegalitatea(3.22).Capitolul4Metodecuordindeconvergent asuperior4.1 TeoremadepunctxDenit ia4.1.1Funct iaf: R Resteocontract iedaca()c (0, 1)astfel nc atoricarearx, y Rsaaib alocinegalitatea:|f(x) f(y)| c|x y|.Teoremadepunct xalui Banach, carest alabazaunormetodeiterative de rezolvare a ecuat iilor de forma f(x) = x, presupune ca festeocontract iepeR.Teorema4.1.1Fief: [a, b] Rsix (a, b)unpunctxal funct ieif. Presupunem c a feste contract ie pe mult imeaS(x, r) = [xr, x+r].Atunci xesteunpunct xunicnS(x, r)si fk(x0) x, k pentruoricex0dinS(x, r).Demonstrat ie: Fie, 0