Lec 10. Solution for Nonlinear Equations

《Lec 10. Solution for Nonlinear Equations》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AdvancedVLSICircuitAnalysisLecture10:SolutionforNonlinearEquationsGraduateCourseofFudanUniversityFanYang1Outline•NonlinearProblems:üDiodeCircuitExample•Newton’sMethod:üOneandmultidimensionalNewton•ContinuationSchemes:üUpdateFormulasandArclength•NewtonIterativeMethods:üImageSe

2、gmenterExampleüMatrixFreeMethods2Nonlinearproblems10VV121IV-=0+rr10VVd10-VV/I-Ie(dt-=1)0dsNeedtoSolveII+=0drII-=0r3vsrcNonlinearproblems•Hardtofindanalyticalsolutionforfx()0=0•Solveiterativelyxx=0guessatasolutionkk+1repeaxtfo=rkWx=()0,1,2,…k+1fx()0»Questionunts:ilØDoestheiter

3、ationconvergetocorrectsolution?ØHowfastdoestheiterationconverge?4Newton’smethod•FromtheTaylorseriesaboutsolution**kdfkk0=f(x)»f(x)+-(x)()xxdxDefineiterationDok=0to…k+-11kdfkkx=-x[(x)]fx()dxdfk-1if[(x)]existsdxuntilconvergence5Newton’sMethod6Newton’smethod3*3f(x)=xx-2,=»21.259

4、921EXAMPLE:kxk

5、xk-x*

6、010.08.740Asymptotically,16.6733335.413akk+1**...x-x»-Cxx81.2616651.744e-0391.2599242.410e-06C=0.7951101.2599214.609e-12a=2.000Quadratic7Newton’smethodk*xx-8Newton’smethod2*kdfk*kkdf*20=f(x)=f(x)+(x)(x-x)+-(x%)()xx2dxdxk*x%Î[xx,]MeanValuetheoremtruncatesT

7、aylorseriesButkdfkkk+1ByNewton0=f(x)+-(x)()xxdxdefinition9Newton’smethod2dfkkk+1*df*2subtracting(x)(x-x)=-(x%)()xx2dxdx2k+-1*dfkk1df*2Dividingthrough(x-x)=-[(x)](x%)()xx2dxdx-12éùdfdfSuppose(x)()xL£forallxêú2ëûdxdx2kk+1**thenx-x£-LxxConvergenceisquadraticifLisbounded10Newton’

8、smethod2*f(x)=x-1==0,findx(x1)dfkk(xx)2=dx2kk+1kkk2x(x-x)=f(xx)1=--(())22kk+1*k**kk2x(x-x)+2x()x-xx=--(()(x))kk+1*1*2or(x--x)=()xxk2xConvergenceisquadratic11Newton’smethod2*f(x)=xx==0,0dfkk(xx)2=æödfdxNote:ç÷notboundedèødxkk+12kkkÞ2x(x-x)=f(xx)=-()awayfromzerokk+1*k*kk2*2Þ2x(

9、x-x)+2x(x-x)=--((xx)())kkk+1**2Þ2x(x-xx)=-()xkkk+12Þ2x(xx-0)=-(0)k+1*1kkx-0=(x-0)for0xx¹=2*1*Convergenceislinearor(x-x)=-()xx12kk+12Newton’smethod13Newton’smethoddf2dfIfLisbounded(boundedawayfromzero;bounded)dx2dxthenNewton’smethodisguaranteedtoconvergegivena“closeenough”gues

10、sAlwaysconverges?14Newton’smethodConvergenceDependsonaGoodInitialGue