数值分析英文版课件-(2)

1Chapter3SolutionofNonlinearEquationsLecturer:GUOTongtongTime:15thDecember,2010The11thLecture2TopicsofToday3.0Introduction3.1Bisection(IntervalHalving)Method3.2Newton’sMethod3.3SecantMethod3TopicsofToday3.0Introduction3.1Bisection(IntervalHalving)Method3.2Newton’sMethod3.3SecantMethod43.0Introduction(1)Theobjectiveofthischapteris:Tosolvetherootsofequations(orzerosoffunctions).Tosolveasystemofnonlinearequations:tofindxsuchthatf(x)=0orfindingX=(x1,x2,…,xn)TsothatF(X)=0.53.0Introduction(2)Examplesofnonlinearequationscanbefoundinmanyapplications.Inthetheoryofdiffractionoflight,weneedtherootsoftheequationtan0xx63.0Introduction(3)Inthecalculationofplanetaryorbits,weneedtherootsofKepler’sequationforvariousvaluesofaandb.sinxaxb73.0Introduction(4)Inthischapter,webeginwiththreesimplemethodsthatarequiteuseful:Thebisectionmethod,Newton’smethod,andthesecantmethod.Also,wediscussspecialmethodsforcomputingthezerosofpolynomials.8TopicsofToday3.0Introduction3.1Bisection(IntervalHalving)Method3.1.0Introduction3.1.1BisectionAlgorithm3.1.2ErrorAnalysis3.2Newton’sMethod3.3SecantMethod93.1.0Introduction(1)Iffisacontinuousfunctionontheinterval[a,b]andiff(a)f(b)0,thenfmusthaveazeroin(a,b).Sincef(a)f(b)0,thefunctionfchangessignontheinterval[a,b]and,therefore,ithasatleastonezerointheinterval.103.1.0Introduction(2)ThisisaconsequenceoftheIntermediate-ValueTheorem(中值定理).Thebisectionmethodexploitsthisideainthefollowingway:Iff(a)f(b)0,thenwecomputec=½(a+b)andtestwhetherf(a)f(c)0.113.1.0Introduction(3)Ifthisistrue,thenfhasazeroin[a,c].Sowerenamecasbandstartagainwiththenewinterval[a,b],whichishalfaslargeastheoriginalinterval.Iff(a)f(c)0,thenf(c)f(b)0,andinthiscasewerenamecasa.Ineithercase,anewintervalcontainingazerooffhasbeenproduced,andtheprocesscanberepeated.123.1.0Introduction(4)Ofcourse,iff(a)f(c)=0,thenf(c)=0andazerohasbeenfound.However,itisquiteunlikelythatf(c)isexactly0inthecomputerbecauseofroundofferrors.Thus,thestoppingcriterionshouldnotbewhetherf(c)=0.133.1.0Introduction(5)Areasonabletolerancemustbeallowed,suchas|f(c)|10-5.Thebisectionmethodisalsoknownasthemethodofintervalhalving(区间减半法).143.1.0Introduction(6)EXAMPLE1Usethebisectionmethodtofindtherootoftheequationex=sinxclosestto0.SolutionIfthegraphsofexandsinxareroughlyplotted,itbecomesclearthattherearenopositiverootsoff(x)=ex–sinxandthatthefirstroottotheleftof0isintheinterval[-4,-3].153.1.0Introduction(7)WhenthebisectionalgorithmwasrunonamachinesimilartotheMarc-32.Thefollowingoutputwasproduced,startingwiththeinterval[-4,-3]163.1.0Introduction(8)11134135000032123250006941033125006051043187506251013318290122101431830019310153183101241kcfc..............4501631831034510..17TopicsofToday3.0Introduction3.1Bisection(IntervalHalving)Method3.1.0Introduction3.1.1BisectionAlgorithm3.1.2ErrorAnalysis3.2Newton’sMethod3.3SecantMethod183.1.1BisectionAlgorithm(1)Someimportantpointsinbisectionalgorithm:First,themidpointciscomputedasc←a+(b–a)/2ratherthanasc←(a+b)/2innumericalcalculationsitisbesttocomputeaquantitybyaddingasmallcorrectiontermtoapreviousapproximation.193.1.1BisectionAlgorithm(2)Second,itisbettertodeterminewhetherthefunctionchangessignovertheintervalusingsign(w)≠sign(u)ratherthanwv0,sincethelatterrequiresanunnecessarymultiplicationandcouldcauseanunderfloworoverflow.Next,eisthecomputationoftheerrorboundthatisestablishedinthetheoremtofollow.203.1.1BisectionAlgorithm(3)Noticethestoppingcriteriaarepresentinthealgorithm.First,Mgivesthemaximumnumberofstepsthattheuserpermits.Next,thecalculationcanbestoppedwheneithertheerrorissmallenoughorthevalueoff(c)issmallenough.21TopicsofToday3.0Introduction3.1Bisection(IntervalHalving)Method3.1.0Introduction3.1.1BisectionAlgorithm3.1.2ErrorAnalysis3.2Newton’sMethod3.3SecantMethod223.1.2ErrorAnalysis(1)Toanalyzethebisectionmethod,letusdenotethesuccessiveintervalsthatarisetheprocessby[a0,b0],[a1,b1],andsoon.Herearesomeobservationsaboutthenumbers:0120012011......10(1)2nnnnaaabbbbababan233.1.2ErrorAnalysis(2)Sincethesequence[an]isnon-decreasingandboundedabove,itconverges.IfweapplyEquation(1)repeatedly,wefindthat002nnnbaba243.1.2ErrorAnalysis(3)Thus,Ifweputthen,bytakingalimitintheinequality0f(an)f(bn),weobtain0≥[f(r)]2,whencef(r)=0.00nnnlimlimlim20nnnbabannlimlimnnrab253.1.2ErrorAnalysis(4)Supposethat,atacertainstageintheprocess,theinterval[an,bn]hasjustbeendefined.Iftheprocessisnowstopped,therootiscertaintolieinthisinterval.Thebestestimateoftherootatthisstageisnotanorbnbutthemidpointoftheinterval:/2nnncab263.1.2ErrorAnalysis(5)Theerroristhenboundedasfollows:Summarizingthisdiscussion,wehavethefollowingtheoremonthebisectionmethod.100122nnnnrcbaba273.1.2ErrorAnalysis(6)THEOREM1TheoremonBisectionMethodIf[a0,b0],[a1,b1],…,[an,bn],…denotetheintervalsinthebisectionmethod,thenthelimitslimn→∞anandlimn→∞bnexist,areequal,andrepresentazerooff.Ifr=limn→∞cnandcn=½(a+bn),then1002(2)nnrcba