数值分析第二章

1、方程求根问题引例方程求根问题引例二分法算法及其应用二分法算法及其应用不动点迭代法不动点迭代法Newton迭代法迭代法数值分析Ch2 r d 例例2.2.水中浮球问题水中浮球问题 有一半径有一半径r =10 cm的球体的球体,密密度度 =0.638.球体浸入水中后球体浸入水中后,浸入水中的深度浸入水中的深度d 是多少是多少？ 根据阿基米德定律根据阿基米德定律,物体排开水的质量就是水物体排开水的质量就是水对物体的浮力对物体的浮力。 334rM ddxxrrV022)( 整理得整理得: d 3 3 r d 2 + 4 r 3 = 0 05101520-2000-10000100020003000由由

2、 =0.638, r = 10.代入代入,得得d 3 30 d 2 + 2552 = 0 令令 f (x) = x 3 30 x 2 + 2552 ,函数图形如下所示函数图形如下所示求解方程求解方程 f(x)=0,即即是求函数是求函数 f(x)的零的零点点. f(x) 的零点所的零点所在区间为在区间为:0, 20roots(1 -30 0 2552)ans = 26.3146 11.8615 -8.1761第一步第一步:对根进行隔离对根进行隔离,找出隔根区间找出隔根区间,或在隔根或在隔根区间内确定一个解的近似值区间内确定一个解的近似值x0;设设f(x) = 0的根为的根为 x*,通过迭代计算通

3、过迭代计算,产生序列产生序列: x0 x1 x2 xn 用数值方法求非线性方程的根用数值方法求非线性方程的根, ,分两步进行分两步进行:第二步第二步:逐步逼近逐步逼近,利用近似解利用近似解x0 (或隔根区间或隔根区间) 通过通过迭代算法迭代算法得到更精确的近似解得到更精确的近似解.*limxxnn 只须只须已知方程已知方程 f(x)=0有一隔根有一隔根区间区间a, b,且且f(x)满足满足f(a)f(b)0,则先将则先将a , b等等分为两个小区间分为两个小区间,判断根属判断根属于哪个小区间于哪个小区间,舍去无根区舍去无根区间保留有根区间间保留有根区间a1, b1;二分法迭代二分法迭代把区间把

4、区间a1, b1 一分为二一分为二, ,进一步判断根属于哪个更进一步判断根属于哪个更小的区间小的区间 a2, b2,如此不断二分以缩小区间长度如此不断二分以缩小区间长度 . .a, bx0=0.5(a+b)a1,b1=a,x0a1,b1=x0,bx1=0.5(a1+b1)f(a1) f(b1) 0已知已知f(x)=0在在a,b内有一根内有一根,且且f(a)f(b)0(1)计算计算: yaf(a) , x00.5(a+b), y0f(x0) 判断判断,若若y0=0,则则x0是根是根,否则转下一步否则转下一步;(2)判断判断,若若y0ya0,则则a1a, b1 x0 否则否则 a1x0, b1b,

5、 ya y0二分法迭代将得到一系列隔根区间二分法迭代将得到一系列隔根区间 ,2211nnbabababa定理定理2.22.2 设设x*是是 f(x)=0在在a, b内的唯一根内的唯一根,且且 f(a)f(b)0,则二分计算过程中则二分计算过程中, 各区间的中点数列各区间的中点数列 ), 2 , 1 , 0( )(21 nbaxnnn性质性质:1. f(an)f(bn)0; 2. bn an = (b a)/ 2n满足满足: | xn x*| (b a)/ 2n+1思考思考: | xn+1 xn | = ？-1-0.500.511.52-101234例例 3 用二分法求方程用二分法求方程 在区间

6、在区间 0, 1内的根内的根,要求误差不超过要求误差不超过2-5. x=-1:.5:2;y=exp(-x)-sin(pi*x/2);plot(x,y)grid有一个点介于有一个点介于0和和1之间之间.显然显然f(0)f(1)er0 x0=.5*(a+b); y0=f(x0); if ya*y0er0 x0=.5*(a+b); y0=f(x0); if ya*y00.00001 x=fi(x0); er=abs(x-x0); x0=x;k=k+1;endfi=inline(sqrt(10/(4+x);x0=1.5;er=1;k=0;while er0.00001 x=fi(x0); er=abs

7、(x-x0); x0=x;k=k+1;endk=16x0=1.3652k=6x0=1.3652roots(1,4,0,-10)ans = -2.6826 + 0.3583i -2.6826 - 0.3583i 1.3652 x2 x1 x0y = x)(xyf(x) = 0)(xx 迭代格式迭代格式:)(1nnxx( n = 0, 1, 2, )(x迭代函数迭代函数若存在若存在 x*,使得使得 ,则称则称x*为不动点为不动点*)(*xx)(xx )(xyxy ,)(1baCx 引理引理2.1 如果如果 ,满足条件满足条件:(1) ; (2)bxa)(1| )(|Lx则则 在在 a, b 有唯一

8、的不动点有唯一的不动点 x*)(x证证 若若 或或 ,显然显然 有不动点有不动点aa )(bb )()(x设设 , 则有则有 ,aa )(bb )(aa )(bb )(记记 则有则有xxx)()(0)()(ba所以所以,存在存在x*,使得使得即即 , x*即为不动点即为不动点.0*)(x*)(xx,)(1baCx 定理定理2.4 如果如果 ,满足条件满足条件:(1) ; (2)bxa )( 1| )(| Lx 则对任意的则对任意的 x0 a, b , 迭代格式迭代格式 产生的序列产生的序列 xn 收敛到不动点收敛到不动点 x*,且有且有)(1nnxx|11|1*nnnxxLxx 证证 )()(

9、*1xxxxnn |)(| )()(|*1*1*xxxxxxnnn |*1*xxLxxnn |*0*xxLxxnn0|lim|lim*0* xxLxxnnnn( 0L0 , r0 使得使得axxxxrnnn|*|*|lim1则称数列则称数列xn r 阶收敛阶收敛.特别特别: (1) 收敛阶收敛阶r=1时时,称为线性收敛称为线性收敛; (2) 收敛阶收敛阶r1时时,称为超收敛称为超收敛; (3) 收敛阶收敛阶r=2 时时,称为平方收敛称为平方收敛序列的收敛阶数越高序列的收敛阶数越高, ,收敛速度越快收敛速度越快例例2.3 方程方程 x3+10 x-20=0,取取 x0 = 1.5, 证明迭代法证

10、明迭代法)10/(2021 nnxx是线性收敛是线性收敛)10/(20)(2 xx 22)10/(40)( xxx 证证:令令 f (x) = x3 + 10 x 20, 绘出绘出 y = f(x) 图形可知图形可知方程的根方程的根 x*1.5, 令令-6-4-20246-300-200-1000100200300 xx3+10 x-203998. 0)5 . 1()(* x|*|)(|*)()(|*|1xxxxxxnnnn |*)(| )(|lim|*|*|lim1xxxxxnnnnn 利用利用Lagrange中值定理中值定理, 有有其中其中, 介于介于xn和和x*之间之间. 所以所以n由此

11、可知由此可知,这一序列的收敛阶数为这一序列的收敛阶数为1,即迭代法即迭代法是线性收敛是线性收敛.显然显然,在在x*附近附近1| )(| x 0)( x 定理定理2.6 设设x*是是 的不动点的不动点,且且)(x0*)(*)(*)()1( xxxp 而而 则则 p阶收敛阶收敛0*)()( xp )(1nnxx | )(|!|*|*)()(|*|)(1nppnnnpxxxxxx 由由Taylor公式公式其中其中, 介于介于xn和和x*之间之间. 所以所以n |*)(|!1| )(|lim!1|*|*|lim)()(1xppxxxxpnpnpnnn 故迭代法故迭代法p阶收敛阶收敛.初值初值: x1=

12、1.5迭代格式迭代格式: xn+1=0.5(xn+2/xn) (n = 1,2,)平方根算法求平方根算法求2 xn Error1.416666666666667 2.45e-0031.414215686274510 2.12e-0061.414213562374690 1.59e-0121.414213562373095 2.22e-0161.414213562373095 2.22e-016设设 x*是方程是方程 f(x)=0 的根的根, x0是是x*的近似值的近似值.在在 x0 附近附近,对函数做局部线性化对函数做局部线性化)()()(000 xxxfxfxf x1比比x0更接近于更接近于

13、x*x0 x1x*0)()(000 xxxfxf f(x) = 0 )()(0001xfxfxx )()(1nnnnxfxfxx (n = 0, 1, 2, )牛顿迭代格式牛顿迭代格式给定初值给定初值 x0 , 迭代产生数列迭代产生数列x0, x1, x2, xn, 应用应用求正数平方根算法求正数平方根算法设设C 0,Cx x2 C = 0令令 f(x) = x2 C , 则则xxf2)( nnnnxCxxx221 211nnnxCxx 由此可知由此可知, 平方根迭代具有平方根迭代具有 2 阶收敛速度阶收敛速度 nnnxCxCx21)(21 CCxCxnnn21|lim21 CxCxCxnnn

14、 21122)(21221CxxCCxxxnnnnn Cxnn limNewton迭代法的局部收敛性迭代法的局部收敛性定理定理2.7 设设 f(x) 在点在点x*的某邻域内具有二阶连的某邻域内具有二阶连续续导数导数, ,且且设设 f(x*)=0, f (x*) 0, 则对充分靠近则对充分靠近点点x*的初值的初值x0, Newton迭代法至少平方收敛迭代法至少平方收敛.)()(1nnnnxfxfxx )()()(xfxfxx 0)(/)()()(2* xfxfxfx 所以所以, Newton迭代法至少平方收敛迭代法至少平方收敛)()()(*xfxfx 例例2.求求 f(x)=xex 1= 0 在

15、在 x0=0.5 附近的根附近的根解解: 迭代格式为迭代格式为xexxf)1 ()(nnxnxnnnexexxx)1(11 (n = 0, 1, )f=inline(x*exp(x)-1);f1=inline(x+1)*exp(x);x0=0.5;er=1;k=0;while er0.00001 x=x0-f(x0)/f1(x0); er=abs(x-x0) x0=x;k=k+1endx = 0.5671 k=4er=1.2348e-01000.51-101xx exp(x)-1缺陷缺陷1.被零除错误被零除错误2.程序死循环程序死循环-6-4-20246-200-1000100200 xx3-

16、3 x+2y = arctan x方程方程: f(x)=x3 3x + 2 = 0在重根在重根x*=1附近附近,f(x)近近似为零似为零对对 f(x) = arctan x存在存在 x0,Newton迭代迭代法陷入死循环法陷入死循环 x0 y x1 x2 x3 y=x3 x 3 x Newton迭代法陷入死循环的另一个例子迭代法陷入死循环的另一个例子133231 nnnnnxxxxx取取 x0=0,(n = 0, 1, )f0 f0, f”0 f0, f”0 f0, f”0 牛顿迭代法收敛的四种情况牛顿迭代法收敛的四种情况定理定理: : 若函数若函数f(x) 在在a，b 上满足条件上满足条件则

17、方程则方程 f(x) = 0 在在a，b 上有唯一根上有唯一根 x*，且且由初值由初值x0按牛顿迭代公式求得的序列按牛顿迭代公式求得的序列 xn 二二阶收敛于阶收敛于x*。 （1）f(a) f(b) 0。0)(21)()()(2* kkkkkxxfxxxfxfxf 2*)()(2)()()(kkkkkkxxxffxfxfxx 2*1*)()(2)(kkkkxxxffxx | )(|2| )(| )(|2| )(|lim)(|lim*2*1xfxfxffxxxxkkkkkk 牛顿迭代法的收敛域问题牛顿迭代法的收敛域问题: : 用牛顿迭代法求解复数方程用牛顿迭代法求解复数方程 z3 1 = 0，该方程在复该方程在复平面上三个根分别是平面上三个根分别是iz23212 iz23213 z1 = 1选择中心位于坐标原点，边长选择中心位于坐标原点，边长为为2 2的正方形内的任意点作初始的正方形内的任意点作初始值，进行迭代，把收敛到三个值，进行迭代，把收敛到三个根的初值分为三类，并分别标根的初值分为三类，并分别标上不同颜色（例如红、