计算方法第二章ppt课件.ppt

《计算方法第二章ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算方法第二章ppt课件.ppt（53页珍藏版）》请在三一办公上搜索。

1、第2章 一元非线性方程的解法,2.1 初始近似根的确定,2.2 二分法,2.3 迭代法的一般知识,2.4 牛顿迭代法（切线法）,2.5 弦截法（割线法）,2.6 埃特金（Aitken）迭代法,目录,引言,本章讨论： 求一元非线性方程f(x)=0的根的近似值。,引言,例如e-x-x=0, x8-x3+5x-3=0,x-sin x=0, 等等,求根的大致步骤：,(1)判定根的存在性。(2)确定根的初始近似值(初始近似根)。(3)根的精确化。,如果f(x*)=f (x*)=f(x*)=f(m-1)(x*)=0, 但f(m)(x*)0,其中m是正整数，则称x*为方程f(x)=0的m重根-函数f(x)的

2、m重零点。,Home,目录,如果 f(x*)=0 ,则x*是方程f(x)=0的根,也称它是函数f(x)的零点。,方程的 1 重根称为单根，这时 f(x*)=0 而 f(x*)0。,定理 如果函数f(x)在区间a,b上连续，严格单调，且f(a)f(b)0，则在(a,b)内方程有且仅有一个实根。,假设f(x)在某区间(a,b)内有且仅有一个实根x*,若 b a较小，则可在(a,b)上任取一点x0作为初始近似根。一般情形，也可用逐步扫描法等。,2.1 初始近似根的确定,Home,目录,Home,目录,例,由于f(0)= -10，,f()0，,故方程至少有一正实根。,设从x=0 出发，取h=0.5为步

3、长向右扫描，得,所以f(x)在区间1,1.5上单调连续，因而在(1,1.5)内有且仅有一个实根，故可在1 ,1.5上任取一点做初始近似根。,可见在（1，1.5）内有根。,Home,目录,(1)x0a; (2)若f(x0)f(x0+h)0则结束；否则做下步。 (3)x0 x0+h，转(2) （其中h为预选的步长）,求初始近似根的逐步扫描法： （设(a,b)内有根）,二分法的基本思想和计算过程,近似根的误差估计,二分法的计算流程,二分法的例,2.2 二分法,Home,目录,二分法的基本思想,将含方程根的区间平分为两个小区间，然后判断根在哪个小区间，舍去无根的区间，而把有根的区间再一分为二，再判断根

4、属于哪个更小的区间，如此周而复始 ，直到求出满足精度要求的近似根。,条件： 函数f(x)在a,b上连续，严格单调，且f(a)f(b)0，这时方程在区间内有且仅有一个实根x*。,Home,目录,二分法的基本思想和计算过程,目录,Home,具体计算过程,第1次二分，取中点,若 f(a)f(x0 )0，则 x*( a, x0 )，,令a1=a , b1=x0；,令a1=x0 , b1=b 。,新的有根区间为(a1 , b1 ) ，长度是原来的一半。,目录,否则,x*(x0 ,b )，,x*,x*,Home,第2次二分，取中点,若 f(a1 )f(x1 )0，则 x*( a1 , x1 )，,令a2=

5、a1 , b2=x1；,否则 令 a2=x1 , b2=b1 。,新的有根区间为(a2 , b2 ) 。,目录,Home,如此反复，有,( a k , b k ) , k=0,1,2,.,目录,Home,近似根xk的误差估计,x* l m |ak xk bk,目录,Home,由此得二分过程的结束原则：,先给定精度要求(绝对误差限)，,（1）当|bk+1 ak+1| 时结束二分计算，取 x*xk ；,（2）事先由估计出二分的最小次数 k+1 ，取 x*xk,目录,Home,二分法的计算流程,目录,Home,例,求方程,要求用二分法，取四位小数计算，精确到10 -2。,解,a=1, b=1.5,得

6、k+1 =7 满足要求， 二分7次计算到 x6 即可。,x0=,=1.25 ,f(1)= -10.,f(1.25)0,得有根区间 1.25,1.5;,x1=,f(1.375)0, f(1)f(1.375)0,得有根区间 1.25,1.375;,在区间(1, 1.5)内的根。,目录,Home,如此继续，计算结果见列表：,得x6=1.3243, 所以根 x*1.32,目录,Home,2.3.1 迭代法的基本思想及几何意义,2.3.2 迭代法的收敛条件及误差估计式,2.3 迭代法的一般知识,Home,目录,Home,目录,1. 迭代法的基本思想,2.3.1 迭代法的基本思想及几何意义,2. 迭代法的

7、几何意义,方程f(x)=0化为等价形式的方程 x=g(x) ，,若,当g(x)(称为迭代函数）连续，,，则由,得,，等价地有f(x*)=0,故x* 即为方程的根。,实际计算到 |xk xk-1 |（是预定的精度），取x*xk 。,1、迭代法的基本思想：,取初始近似根x0 ,迭代计算 x1=g(x0), x2=g(x1),. 得到迭代序列xk ,构造迭代公式 xk+1= g(xk ) , k=0,1,2,例 f(x)=xex-1=0,可化为等价形式x=e x迭代公式xk+1=e xk,迭代法也称逐次逼近法。,Home,目录,迭代公式收敛（发散）指迭代序列 xk 收敛（发散）。,目录,求方程 f(

8、x)=x 10 x+2=0的一个根，取4位有效数字计算。,问题：迭代公式是否一定收敛？,因 f(0)=,1 0,f(1)=,-7 0,所以方程在（0，1）中有根。方程改写为两种等价形式：,看下例：,解,对应的迭代公式分别为,10 x= x+2x=lg(x+2),Home,目录,用迭代公式（1）,x1=lg3=0.4771,x2=lg(x1+2)=0.3939,., x6=0.3758, x7=lg(x6+2)=0.3758,用迭代公式（2）,x1=10-2=8,x2=108-2108,x3=10108-2 10108，,x6、x7重合，所以迭代公式（1）是收敛的，x*0.3758。,迭代公式（

9、2）发散。,取 x0=1, 算得, x0=1, 算得,Home,2. 迭代法的几何意义,问题：迭代函数g(x)满足什么条件时，迭代序列才收敛?,目录,x1=g(x0 ),x2=g(x1 ),Home,2.3.2 迭代法的收敛条件及误差估计式,定理2.1 设方程 x=g(x) 在a, b上有一阶导数，如果,(1)当 xa, b时 g(x) a, b;(2) 存在正数 q 1，使对任意 x a, b 都有 |g(x)| q 1则方程x=g(x)在 a, b上有惟一的根x* ；且对于a,b上任意初始近似根x0 ,迭代公式 xk+1=g(xk)均收敛于方程的根x*;还有误差估计式,Home,目录,证明

10、,记f(x)=x-g(x),由条件（1）有 ag(a)、g(b)b ,于是 f(a)0, f(b)0，,由于f(x)是连续函数，故必存在 x* a, b 使f(x*)=0.,于是x*为方程 x=g(x)的根。,先证根的存在性。,目录,其次，证根的惟一性 。,设y*也是方程的根，则x*=g(x*), y*=g(y*),|x*- y*|=|g(x*) g(y*)|,= |g()(x*- y*)|,q |x*- y*|,由已知条件|g (x)| q 1,故必有x*=y*,所以方程在a,b的根是惟一的。,微分中值定理,在x*,y*之间,Home,再证迭代公式收敛 。,由x 0a, b 知 xka, b

11、，k =0,1,2,|xk +1 - x*| =|g(xk) g(x*)|= |g()(xk-x*)|q |x k- x*|,q2|xk-1-x*|,|x k- x*| q |xk-1-x*|,q3| xk-2-x*|,qk+1 |x0-x*|,0 （k）,所以，对a,b上任取的x0 ,迭代公式xk+1= g(xk )都收敛于x*。,0q1, qk+10,误差公式的证明从略 。,目录,|x k-1 - x*| q |xk-2 -x*|,Home,目录,Home,目录,Home,推论 设在区间 a , b 上方程 x = g(x)有根 x*,且g(x)有连续的一阶导数。如果有正数 q1 ,使得对

12、任意 xa, b 都有|g(x)| q 1，则存在x*的某个邻域，只要x0 属于此邻域，迭代公式xk+1= g(xk )必收敛于x*。（也称迭代公式有局部收敛性）,目录,|g(x)| q 1, | x-x* | ，由中值定理得 |g(x)-x*|=|g(x)-g(x*)|=|g()(x-x*)|q| x-x* |，于是g(x) (x*-, x*+)，这说明在该邻域内定理的条件（1）也成立。所以结论成立。,证明,存在x*的邻域(x*-, x*+)a, b, 当x (x*-, x*+)时，,Home,定理 设在区间a, b上方程 x=g(x) 有根x*,且对一切xa, b 都有|g(x)| 1，则

13、对于该区间上任意x0(x*), 迭代公式xk+1= g(xk )一定发散。,证明,不可能收敛于0。,目录,Home,目录,Home,目录,Home,迭代法的计算步骤,（1）确定方程 f(x)=0 的一个等价形式 x=g(x), 要求在某个含根区间a,b内满足|g(x)| q 1 。,(2)构造迭代公式 xk+1=g(xk)，选取初始近似根x0 ,进行迭代计算。,(3) 当|xk+1 xk |（是预定的精度）时停止计算，取x*xk +1 。,目录,Home,迭代法的计算框图,目录,Home,例,求方程 x=e x在x=0.5附近的一个根，按5位小数计算，结果的精度要求为=10 3.,解,方程等价

14、于 f(x)=x e x=0.,由于f(0.5)0, 故x*(0.5, 0.6),令g(x)=e x,在(0.5, 0.6)内, g(x) 的一阶导数连续，且有,所以用迭代公式 xk+1=e xk 进行计算是收敛的。,根据定理2.1的推论,目录,Home,迭代结果:,k,xk,xk xk-1,xk xk-1,k,xk,|x10 - x9 |=0.00065，,目录,故 x*x10 0.567,x0=0.5,x2=e x1=0.54524,.,x1=e x0=0.60653,Home,例,方程f(x)=x3-2x-5=0在(1.5, 2.5)内有一实根，分别取,作为迭代函数，试判断对应的迭代公式

15、是否收敛，并用一个收敛的迭代公式求方程的根，精度要求为=10 -4。,解,(1),单调，且,所以迭代公式,收敛。,目录,Home,取x0=2 计算,因为 |x5-x4|=0.0000510-4,所以x*x5=2.09454,目录,结果列表：,Home,目录,(2),迭代函数,根据定理2.2, 迭代函数对应的迭代公式,是发散的。,Home,1. 牛顿法的基本思想,2. 牛顿法的收敛性,2.4 牛顿迭代法（切线法）,Home,目录,3. 牛顿法的计算步骤,把非线性方程线性化，用线性方程的解逐步逼近非线性方程的解。,1、牛顿迭代法的基本思想：,切线的方程 y=f(xk)+f (xk)(x xk) 点

16、(xk+1 , 0)满足该方程，即 0= f(xk)+f (xk)(xk+1 xk),过曲线上的点pk(xk , f(xk)作切线，取切线与轴的交点为 xk+1 。,由此得,Home,目录,用这个迭代公式求根的方法也称牛顿迭代法、切线法。,目录,Newton迭代公式,若 f (xk )0，则得,f (xk)(xk+1 xk) = - f(xk),Home,目录,Home,2、牛顿迭代法的收敛性： 局部收敛,牛顿法迭代函数：,若x*是单根（即f(x*)=0， f (x*)0）， f (x)连续从而有界，则当x足够靠近 x*时，就能满足 |g(x)|q 1， 保证迭代公式收敛。,目录,Home,定

17、理2.3,如果在有根区间 a,b上 f(x)0，f(x)连续且不变号，在 a,b上取初始近似根 x0 ,使得,则牛顿迭代法收敛。,目录,Home,目录,3、牛顿迭代法的计算步骤,(1)给出x0 , ；,(2)计算,(3)若,则转(4)；否则,，转(2);,(4)输出x1 ,结束。,例,用牛顿迭代法求方程 xex-1=0 在x=0.5附近的根（取5位小数计算），精度要求为=10 3.,解,相应的牛顿迭代公式为,取x0=0.5，经计算可得,Home,则x2-3=0,求,等价于求方程,令,例,用牛顿迭代法计算,解,的正实根。因为 f(x)=2x ，由牛顿迭代公式得,取初值 x0=1.5，迭代5次可得

18、,1.732050808,问题,如何用牛顿法计算任意正数的算术平方根？是否还能用牛顿法计算一个正数的立方根？,目录,Home,2.5 弦截法（割线法）,研究目的：在牛顿法基础上，构造既有较高的收敛速度，又不须导数的迭代公式。,思想： 用差商,弦截迭代公式,Home,目录,几何意义,Home,目录,目录,例,用弦截迭代法求上一节的方程 xex-1=0 在x=0.5附近的根。,解,弦截迭代公式为,方程化为 x-e x=0, 令,（点击框内显示公式）,Home,弦截法的计算框图,出,目录,Home,2.6 埃特金(Aitken)迭代法,研究目的：有时迭代过程收敛缓慢，如何加速？,埃特金迭代法的构造条件：,已有迭代公式 xk+1= g(xk) 假定g(x) 在求根区间内改变不大 。,埃特金迭代公式,Home,目录,用埃特金迭代法求 x3-x-1=0 在 (1, 1.5)内的根。,例,解,将方程改写成 x=x3- 1，建立迭代公式,埃特金迭代公式为,Home,目录,埃特金算法的几何解释。,目录,Home,