现在数值分析课件科大 现代数值分析06 非线性方程求解.ppt

《现在数值分析课件科大 现代数值分析06 非线性方程求解.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§4牛顿法/*Newton-RaphsonMethod*/原理：将非线性方程线性化——Taylor展开/*Taylor’sexpansion*/取x0x*，将f(x)在x0做一阶Taylor展开:,在x0和x之间。将(x*x0)2看成高阶小量，则有：线性/*linear*/xyx*x0只要fC1，每一步迭代都有f’(xk)0，而且，则x*就是f的根。§4Newton-RaphsonMethod定理（收敛的充分条件）设fC2[a,b]，若(1)f(a)f(b)<0；(2)在整个[a,b]上f”不变号且f’(x)0；(3)选取x0[a,b]使得f(x0)f”(x0)

2、>0；则Newton’sMethod产生的序列{xk}收敛到f(x)在[a,b]的唯一根。有根根唯一产生的序列单调有界，保证收敛。定理（局部收敛性）设fC2[a,b]，若x*为f(x)在[a,b]上的根，且f’(x*)0，则存在x*的邻域使得任取初值，Newton’sMethod产生的序列{xk}收敛到x*，且满足§4Newton-RaphsonMethod证明：Newton’sMethod事实上是一种特殊的不动点迭代其中，则收敛由Taylor展开：只要f’(x*)0，则令可得结论。在单根/*simpleroot*/附近收敛快§4Newton-RaphsonMethod

3、注：Newton’sMethod收敛性依赖于x0的选取。x*x0x0x0§4Newton-RaphsonMethod改进与推广/*improvementandgeneralization*/重根/*multipleroot*/加速收敛法：Q1:若　　　，Newton’sMethod是否仍收敛？设x*是f的n重根，则：且。因为Newton’sMethod事实上是一种特殊的不动点迭代，其中，则A1:有局部收敛性，但重数n越高，收敛越慢。Q2:如何加速重根的收敛？A2:将求f的重根转化为求另一函数的单根。令　　　　　，则f的重根=的单根。§4Newton-RaphsonMe

4、thod正割法/*SecantMethod*/：Newton’sMethod一步要计算f和f’，相当于2个函数值，比较费时。现用f的值近似f’，可少算一个函数值。x0x1切线/*tangentline*/割线/*secantline*/切线斜率割线斜率需要2个初值x0和x1。收敛比Newton’sMethod慢，且对初值要求同样高。§4Newton-RaphsonMethod下山法/*DescentMethod*/——Newton’sMethod局部微调：原理：若由xk得到的xk+1不能使

5、f

6、减小，则在xk和xk+1之间找一个更好的点，使得。xkxk+1注：=1时就是

7、Newton’sMethod公式。当=1代入效果不好时，将减半计算。§4Newton-RaphsonMethodAlgorithm:Newton’sDescentMethodFindasolutiontof(x)=0givenaninitialapproximationx0.Input:initialapproximationx0;f(x)andf’(x);minimumstepsizeofxmin;toleranceTOL1forx;toleranceTOL2for;maximumnumberofiterationsNmax.Output:approximatesolu

8、tionxormessageoffailure.Step1Setk=1;Step2While(kNmax)dosteps3-10Step3Set=1;Step4Set;/*computexk*/Step5If

9、xx0

10、TOL2thenGOTOStep4;/*computeabetterxi*/Step9Setx0=x0+xmin;/*m

11、oveforwardanywaytoavoiddeadlock*/Step10Setk++;Step11Output(MethodfailedafterNmaxiterations);STOP./*unsuccessful*/计算量未见得减小§4Newton-RaphsonMethod求复根/*FindingComplexRoots*/——Newton公式中的自变量可以是复数记z=x+iy,z0为初值，同样有设代入公式，令实、虚部对应相等，可得迭代法的收敛阶/*OrderofConverg