数值分析 lec非线性方程组解法.pptx

《数值分析 lec非线性方程组解法.pptx》由会员分享，可在线阅读，更多相关《数值分析 lec非线性方程组解法.pptx（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十讲非线性方程组的迭代解法第三章非线性方程与非线性方程组的迭代解法第1页/共36页常用的求非线性方程根的方法回顾 二分法（对分法、搜索法）二分法（对分法、搜索法）不动点法不动点法 （简单迭代法、压缩映象法）及其加速算法（简单迭代法、压缩映象法）及其加速算法 NewtonNewton方法及其变体方法及其变体第2页/共36页计算框图为：对分法（二分法）：对分法（二分法）：利用连续函数的性质进行对分利用连续函数的性质进行对分第3页/共36页简单迭代法（线性收敛）迭代法的构想迭代法的构想 从一个初值从一个初值x0出发，计算出发，计算如果如果 xk收敛，即存在收敛，即存在x*,使得使得 则由则由 得得

2、 即即 x*是是 (x)(x)的不动点，也就是的不动点，也就是 f(x)f(x)的根。的根。第4页/共36页简单迭代法的变体：简单迭代法的变体：SteffensenSteffensen加速收敛方法加速收敛方法 第5页/共36页至少二阶收敛至少二阶收敛 速度速度第6页/共36页Newton 迭代法迭代法（二阶收敛）（二阶收敛）非线性问题的最简单解法是线性近似.将非线性方程线性化，以线性方程的解逐步逼近非线性方程的解，这就是Newton法的基本思想。第7页/共36页第8页/共36页计算步骤（框图）：第9页/共36页Newton 迭代法的变体：割线法（割线法（简化牛顿法简化牛顿法）（）（1.6181

3、.618）NewtonNewton迭代法需要计算迭代法需要计算f(x)f(x)的一阶导数，对复杂的函数，特别是的一阶导数，对复杂的函数，特别是多元隐函数，求导数或偏导数是一个相对繁琐和复杂的，往往采多元隐函数，求导数或偏导数是一个相对繁琐和复杂的，往往采用近似计算的办法！用近似计算的办法！在在NewtonNewton迭代法中用迭代法中用来近似来近似f(x)f(x)在在x xk k处的一阶导数处的一阶导数由此得到的算法叫割线法。由此得到的算法叫割线法。第10页/共36页Newton 迭代法的变体：单点割线法（一阶）割线法（一阶）NewtonNewton迭代法需要计算迭代法需要计算f(x)f(x)

4、的一阶导数，对复杂的函数，特别是的一阶导数，对复杂的函数，特别是多元隐函数，求函数值是计算量比较大或者比较繁琐，尽量减少多元隐函数，求函数值是计算量比较大或者比较繁琐，尽量减少函数值的计算！函数值的计算！在在NewtonNewton迭代法中用迭代法中用来近似来近似f(x)f(x)在在x xk k处的一阶导数处的一阶导数由此得到的算法叫割线法。由此得到的算法叫割线法。第11页/共36页牛顿下山法：目的是解决初值的选取范围太小这一困难。构造迭代格式为：其中的参数满足：这个方法称为牛顿下山法。其中的参数称为下山因子：通常取 ，然后逐步减半。牛顿下山法当 时，只有线性收敛速度，但对初值的选取却放的相当

5、宽。第12页/共36页第13页/共36页第14页/共36页非线性方程组的解法第15页/共36页含含n n个方程的个方程的n n元非线性方程组的一般形式是元非线性方程组的一般形式是非线性方程组的一些基本概念非线性方程组的一些基本概念第16页/共36页上面的方程组化为：上面的方程组化为：F(X)=0 F(X)=0 第17页/共36页第18页/共36页例子：将方程组将方程组 F(X)=0,F(X)=0,写成与之等价的形式写成与之等价的形式:X=G(X),:X=G(X),然后再然后再利用利用 X X(k+1)(k+1)=G(X=G(X(k)(k),k=1,2,),k=1,2,求解原方程的根。求解原方程

6、的根。简单迭代法第19页/共36页x=0.0y=0.010 x1=x y1=y x=0.25*(1+y1-0.1*exp(x1)y=0.25*(x1-0.125*x1*x1)write(10,*)x,y if(abs(x-x1)+abs(y-y1).lt.0.00000001)then goto 15endif goto 1015 end第20页/共36页简单迭代法的收敛性第21页/共36页第22页/共36页NewtonNewton迭代法迭代法第23页/共36页第24页/共36页计算步骤（框图）：第25页/共36页kx(k)0123(1.5,1.0)T(1.5,0.75)T(1.488095,

7、0.755952)T(1.488034,0.755983)T第26页/共36页例：用牛顿法解方程组第27页/共36页取初始值（取初始值（1 1，1 1，1 1），计算如下），计算如下N x y z0 1.0000000 1.0000000 1.0000000012.1893260 1.5984751 1.393900621.8505896 1.4442514 1.278224031.7801611 1.4244359 1.239292441.7776747 1.4239609 1.237473851.7776719 1.4239605 1.237471161.7776719 1.4239605

8、 1.2374711第28页/共36页简化牛顿法。目的是避免计算迭代公式中繁杂的导数，解决方法与一元函数牛顿法类似，即将所有导数取为固定值，如迭代初值的导数值。第29页/共36页与单个方程的情形类似，牛顿法中 f 的导数的元素用合适的差商来近似，如就可得到拟牛顿法或弦截法。第30页/共36页若用格式其中下山因子合适地选取使得就得到牛顿下山法。若用格式，其中是的简单修正，且满足则得到Broyden算法。特别，若取，其中u,v 是待定的列向量，使其满足上式，则得到秩一Broyden算法。比如第31页/共36页小结 1、本章的目的是求解形如 f(x)=0 的方程，而其核心方法是将所要求解的方程变形为 x=(x)，利用 (x)为压缩映射，通过迭代求出其解。2、变形中切记要恒等变形！3、在恒等变形中，为使变形得到的函数 (x)为压缩映射，一个技巧是利用待定参数。4、恒等变形的一种重要格式是牛顿迭代，证明其迭代收敛阶的一个常用技巧是泰勒展开。5、n维空间中代数方程迭代求解的收敛条件是谱半径小于 1.第32页/共36页Newton-Krylov subspace methods第33页/共36页作业教材P93页习题10、11第34页/共36页第35页/共36页感谢您的观看。第36页/共36页