实用数值计算方法方程求根

1、计计 算算 方方 法法授课老师：聂德明 仰仪北楼606计量测试工程学院计量测试工程学院Numerical Method 方程求根方程求根1 问题的提出问题的提出2 二分法二分法3 迭代法迭代法4 牛顿法及割线法牛顿法及割线法预备知识预备知识1. Taylor公式公式( )20000000( )000( )1( )( )( )( -)( )( -).( -).2!( )( -)( )!kkikikifxf xf xf xx xfxx xx xkfxx xr xi (1)100( )( )( -), () ,(1)!kkkfr xx xksix xk拉格朗日余项：拉格朗日余项：2. 拉格朗日中值定

2、理拉格朗日中值定理( )()()fbfafba预备知识预备知识若若f(x)在在a, b上连续，且上连续，且f(x)在在(a, b)内可导，则存在内可导，则存在a, b，使：，使：或或( )( )()(), ,f bfafbaa b设函数设函数f(x)在区间在区间a, b上连续，在上连续，在(a, b)内可导，则内可导，则f(x)在在a, b上单调递增上单调递增(递减递减)的充要条件是的充要条件是3. 函数的单调性函数的单调性预备知识预备知识(a, b), f (x)0(f (x)0)x1 问题的提出问题的提出方程的一般形式：f(x)=0 ，满足方程的x值通常叫做方程的根或解，也叫函数f(x)的

3、零点。 实际问题实际问题n 代数方程代数方程5次以上的方程无求根公式次以上的方程无求根公式 n 超越方程：包含超越函数，如超越方程：包含超越函数，如 sinx, lnx, ex近似求解近似求解1 问题的提出问题的提出u 求根的隔离区间隔离区间 ，即确定根所在区间u 根的精确化。粗糙的近似值-满足精度的近似值 方程求根步骤：方程求根步骤：1 问题的提出问题的提出求根的求根的隔离区间隔离区间设函数f(x)在a, b内连续，严格单调，且有f(a)f(b)0，则在a, b内方程f(x)=0有且仅有一个实根。 u 函数函数y=f(x)与横轴与横轴( (y=0) )交点交点u f(x)=0 f1(x)=f

4、2(x)，函数，函数f1(x)与与f2(x)的交点的交点u 区间区间a, b内选择内选择x1, x2, x3, x4 ，根据，根据f(x)在这些在这些 点上值的符号确定点上值的符号确定 2 二分法二分法二分法二分法也称对分区间法、对分法等，是最简单的求根也称对分区间法、对分法等，是最简单的求根方法，属于区间法求根类型。方法，属于区间法求根类型。 设函数f(x)在a, b内连续，严格单调，且有f(a)f(b)0，则在a, b内方程f(x)=0有且仅有一个实根。 *111()()22kkkkxxbaba2 二分法二分法误差估计误差估计对于所给定的精度对于所给定的精度 ，则可得，则可得11ln()l

5、n()12ln 2kbabak2 二分法二分法32( )210f xxxx例例3 用二分法求下列方程在区间用二分法求下列方程在区间0, 1内的实根，要内的实根，要求有求有3位有效数字。位有效数字。1. (0)10,(1)10ff 2172.( )3()0,0,123fxxx3. (0.1)0f*0.1,1x*3111()1022kxxba3 迭代法迭代法基本思想：逐次逼近基本思想：逐次逼近粗糙的初值粗糙的初值校正后的近似值校正后的近似值迭代公式迭代公式END满足精度满足精度不满足精度不满足精度3 迭代法迭代法( )0( )f xxx0 , ,xa b取用递推公式1()kkxx可得序列可得序列

6、xk: x0, x1, x2, x3, 如果当如果当k时，序列时，序列xk有极限有极限x*，则，则x*是方程是方程f(x)=0的根。的根。 迭代公式迭代公式序列有极限：迭代公式收敛序列有极限：迭代公式收敛 序列无极限：迭代公式发散序列无极限：迭代公式发散用迭代法求下列方程在区间用迭代法求下列方程在区间2, 4的根。的根。2( )230f xxx3 迭代法迭代法12323kkxxxx取取x0 =4，则，则1023113.317xx21239.6343.104xx32239.2083.034xx43239.0683.011xx54239.0223.004xx收敛收敛3 迭代法迭代法22111(3)

7、(3)22kkxxxx取取x0 =4，则，则16.5x 219.625x 3191.070 x 发散发散几何意义几何意义3 迭代法迭代法( )0( )f xxx1122( )( )( )yfxxyfxx1yx2( )yx00( , ( )xx11( , ( )xx0 x2x1xpxy02( )yx1yxxy0*x0 x1x*x2x假设迭代函数假设迭代函数 ( (x x) ) 在在a, b上具有一阶连续的导数，且满足上具有一阶连续的导数，且满足n 当当 x a, b 时，时， ( (x x) ) a, b；n 存在正常数存在正常数 L 1， 使得使得 | | (x) |(x) | L ; 则则u

8、 方程在方程在a, b上有唯一根上有唯一根 x*u 对任意对任意x0 a, b，迭代格式，迭代格式xk+1 = ( (x xk k) )都收敛到都收敛到 x* u u u 定理定理1*11kkkLxxxxL*101kkLxxxxL*1*lim()kkkxxxxx2( )230f xxx23( )xxx21(3)( )2xxx1( )23xx2, 4( )1(2)17xx( )xx2, 4( )(2)2xx定义定义1 ：局部收敛性：局部收敛性对于方程对于方程 x= (x)，若在，若在 x* 的某个领域的某个领域 S = x | x x* - , x* + 内，对任意初值内，对任意初值x0 S，迭

9、代格式，迭代格式xk+1 = (xk) 都收敛，都收敛，则称该迭代格式在则称该迭代格式在 x* 的附近是局部收敛的。的附近是局部收敛的。3 迭代法迭代法定理定理3 设方程设方程 x= (x)有根有根x*，且在，且在 x* 的某个领域的某个领域 S = x | x x* - , x* + 内存在一阶连续导数，则内存在一阶连续导数，则u 当当|(x*) |1时，迭代格式时，迭代格式xk+1 =(xk)发散发散 1yx2( )yx00( , ( )xx11( , ( )xx0 x2x1xpxy02( )yx1yxxy0*x0 x1x*x2x3 迭代法迭代法迭代法的收敛速度（收敛阶）迭代法的收敛速度（

10、收敛阶） u p=1，且，且0|c|1，称为线性收敛，称为线性收敛 u p=2，称为平方收敛，称为平方收敛假设迭代函数假设迭代函数 (x)在在a, b上具有一阶连续的导数，且满足上具有一阶连续的导数，且满足n 当当 x a, b 时，时， (x) a, b；n 存在正常数存在正常数 L 1， 使得使得 | (x) | L ; 则则u 方程在方程在a, b上有唯一根上有唯一根 x*u 对任意对任意x0 a, b，迭代格式，迭代格式xk+1 = (xk)都收敛到都收敛到x* u u u 定理定理1*11kkkLxxxxL*101kkLxxxxL*1*lim()kkkxxxxx定理定理2.4 若若

11、(x)在在x*附近的某个领域内有附近的某个领域内有p阶阶(p1)连续导数，且连续导数，且(x*)= x*, (x*)= 0, (p-1)(x*)= 0, (p)(x*) 0, 则对一个任意靠近则对一个任意靠近x*的初始值的初始值x0，迭代公式，迭代公式xk+1 =(xk)是是p阶收敛的，且有阶收敛的，且有3 迭代法迭代法*()*1*()lim()!pkpkkxxxxxp3 迭代法迭代法迭代法的收敛速度（收敛阶）迭代法的收敛速度（收敛阶） u p=1，且，且0|c|1，称为线性收敛，称为线性收敛 u p=2，称为平方收敛，称为平方收敛假设迭代函数假设迭代函数 (x)在在a, b上具有一阶连续的导

12、数，且满足上具有一阶连续的导数，且满足n 当当 x a, b 时，时， (x) a, b；n 存在正常数存在正常数 L 1， 使得使得 | (x) | L ; 则则u 方程在方程在a, b上有唯一根上有唯一根 x*u 对任意对任意x0 a, b，迭代格式，迭代格式xk+1 = (xk)都收敛到都收敛到x* u u u 定理定理1*11kkkLxxxxL*101kkLxxxxL*1*lim()kkkxxxxx定理定理2.4 若若 (x)在在x*附近的某个领域内有附近的某个领域内有p阶阶(p1)连续导数，且连续导数，且(x*)= x*, (x*)= 0, (p-1)(x*)= 0, (p)(x*)

13、 0, 则对一个任意靠近则对一个任意靠近x*的初始值的初始值x0，迭代公式，迭代公式xk+1 =(xk)是是p阶收敛的，且有阶收敛的，且有2.3 迭代法迭代法*()*1*()lim()!pkpkkxxxxxp2.4 牛顿法牛顿法()()()0kkkf xfxxx( )()()()kkkf xf xfxxx()()kkkf xxxfx1()()kkkkf xxxfx牛顿迭代公式牛顿迭代公式( )( )( )f xxxfx几何意义几何意义1()()kkkkf xxxfx()()()kkkyf xfxxxx2x0 x1x*牛顿迭代法牛顿迭代法x3y=f(x)4 牛顿法牛顿法局部收敛性局部收敛性定理定

14、理2.3 设方程设方程 x=(x)有根有根x，且在，且在 x* 的某个领域的某个领域 S = x | x x* - , x* + 内存在一阶连续导数，则内存在一阶连续导数，则u 当当|(x*) |1时，迭代格式时，迭代格式xk+1 =(xk)发散发散 4 牛顿法牛顿法局部收敛性局部收敛性( )( )( )f xxxfx2( )( )( )( )f x fxxfx*2()()()0()f xfxxfx定理定理4 若若 (x)在在x*附近的某个领域内有附近的某个领域内有p阶阶(p1)连续导数，且连续导数，且(x*)= x*, (x*)= 0, (p-1)(x*)= 0, (p)(x*) 0, 则对

15、一个任意靠近则对一个任意靠近x*的初始值的初始值x0，迭代公式，迭代公式xk+1 =(xk)是是p阶收敛的，且有阶收敛的，且有*()*1*()lim()!pkpkkxxxxxp2( )( )( )( )( )( )fxfxxf xfxfx( )( )( )f xxxfx2( )( )( )( )f x fxxfx*()()()fxxfx*()0 x*()0 x二阶局部收敛二阶局部收敛牛顿法牛顿法局部收敛性局部收敛性*11*2*11()limlim()()22()kkpkkkkxxefxxxxefx4 牛顿法牛顿法大范围收敛性大范围收敛性定理定理2.6 若若 f(x)在在a, b上存在二阶导数，且满足下列条件：上存在二阶导数，且满足下列条件：uf(a)f(b) 0则牛顿迭代序列则牛顿迭代序列xk收敛于方程收敛于方