《计算方法》第二章（2-1）求隔根区间

第二章非线性方程求解 首先引入定义: f(x)=0的解x称为方程f(x)=0的根 或函数f(x)的零点。 若f(x)=(x-x)mg(x),其中ml∈z,m>1, 且g(x)≠0,则称x为方程f(x)=0 的m重根,或函数f(x)的m重零点。 §2.1根的隔离与二分法 方程求根问题一般分两步 1、根的隔离:确定根所在区间[a,b],使该 区间内只有方程的一个根,该区间叫隔根 区间。 2、近似根的精确化:已知根的一个近似值 后,用某种方法对其进行加工,使之满足 给定的精度要求

第二章 非线性方程求解 首先引入定义： f x( ) 0= 的解 * x 称为方程 f x( ) 0= 的根 或函数 f x( ) 的零点。 若 f x x x g x ( ) ( ) ( ) = − * m ，其中 m Z m   , 1 ， 且 g x( ) 0 *  ，则称 * x 为方程 f x( ) 0= 的 m 重根，或函数 f x( ) 的 m 重零点。 §2.1 根的隔离与二分法 方程求根问题一般分两步： 1、 根的隔离：确定根所在区间 [ , ] a b ,使该 区间内只有方程的一个根，该区间叫隔根 区间。 2、 近似根的精确化：已知根的一个近似值 后，用某种方法对其进行加工，使之满足 给定的精度要求

求隔根区间的一般方法 理论依据: 设f(x)∈CIa,b,且f(a)f(b)<0,则 f(x)=0在[a内至少有一个实根x;若f(x) 在[a,b]内严格单调,则f(x)=0在[a,b]内只有 个根。由此可得求隔根区间的几种方法。 1、验证法 验证f(a)f(b)<0是否成立? 先取定一点a,再找一点b,使得不等式 f(a)f(b)<0成立。则[a,b]为所求 2、作图法

一、 求隔根区间的一般方法 理论依据： 设 f x C a b ( ) [ , ]  ， 且 f a f b ( ) ( ) 0   ， 则 f x( ) 0= 在 [ , ] a b 内至少有一个实根 * x ；若 f x( ) 在 [ , ] a b 内严格单调，则 f x( ) 0= 在 [ , ] a b 内只有 一个根。由此可得求隔根区间的几种方法。 1、验证法 验证 f a f b ( ) ( ) 0   是否成立？ 先取定一点 a ，再找一点 b ，使得不等式 f a f b ( ) ( ) 0   成立。则 [ , ] a b 为所求。 2、作图法

利用f(x)的单调性、凹凸性、对称性、 奇偶性描点,画出f(x)的图象,根据图象 判断隔根区间 缺陷:只能对一些较简单的函数作分 析。对复杂一点的函数f(x),像f(x),f(x)难 求的,聚点,凹凸点难求的f(x),用此种方 法效率很差。 3、作图法的改进 将f(x)=0÷9x)=v(x),其中y1=0(x)与 y2=(x)的图象比较容易画出来,则n1与n2 的交点的横坐标即为f(x)=0的根。 4、逐步扫描(逐步搜索)法 利用计算机来搜寻隔根区间(前三种方 法都是手算)。 预先给定一点a和步长h(>0),利用计算 机重复判断 f(a+ih)f(a+(i+1)h)<0(i=0,2, 是否成立,直至找到这样的区间 [a+ita+(i+1)h)为止

利用 f x( ) 的单调性、凹凸性、对称性、 奇偶性描点，画出 f x( ) 的图象，根据图象 判断隔根区间。 缺陷：只能对一些较简单的函数作分 析。对复杂一点的函数 f x( ) ，像 f x f x   ( ), ( ) 难 求的，聚点，凹凸点难求的 f x( ) ，用此种方 法效率很差。 3、作图法的改进 将 f x( ) 0=   ( ) ( ) x x = ，其中 ( ) 1 y x = 与 ( ) 2 y x = 的图象比较容易画出来，则 1 y 与 2 y 的交点的横坐标即为 f x( ) 0= 的根。 4、逐步扫描（逐步搜索）法 利用计算机来搜寻隔根区间（前三种方 法都是手算）。 预先给定一点 a 和步长 h( 0)  ，利用计算 机重复判断 f a ih f a i h ( ) ( ( 1) ) 0 +  + +  ( 0,1,2, ) i= 是 否 成 立 ， 直 至 找 到 这 样 的 区 间 [ , ( 1) )] a ih a i h + + + 为止

若经过很多步之后,仍找不到满足条件 的区间,则用一h做步长试一试。 、二分法 假定f(x)∈(Ia,b,f(a)·f(b)<0,则 f(x)=0在[a,内至少有一个实根。 ●主要思想(步骤): 先选定两个小的正数δ和E。 1、记[ab]={an,取其中点为x=+by 判断f(x)6?若成立,则x即为所求的 根,停;否则进入下一步。 2、判断f(a)f(x)<0?若成立,说明在[anx 内有一根,则令a1=an,b=x;否则, a1=x=b,形成新的隔根区间 a,b且b-a=(b-a)/2 3、对新的有根区间重复步骤1、2,仅当出 现情况1时计算过程中断 ●误差分析及做多少次二分的估计:

若经过很多步之后，仍找不到满足条件 的区间，则用−h 做步长试一试。 二、 二分法 假 定 f x C a b ( ) [ , ]  ， f a f b ( ) ( ) 0   ， 则 f x( ) 0= 在 [ , ] a b 内至少有一个实根。 ⚫ 主要思想（步骤）： 先选定两个小的正数  和  。 1、 记 0 0 [ , ] [ , ] a b a b = ，取其中点为 0 0 0 2 a b x + = ， 判断 0 | ( )| f x  ？若成立，则 0 x 即为所求的 根，停；否则进入下一步。 2、判断 0 0 f a f x ( ) ( ) 0   ？若成立，说明在 0 0 [ , ] a x 内有一根，则令 1 0 a a = , 1 0 b x = ；否则， 1 0 1 0 a x b b = = , ， 形 成 新 的 隔 根 区 间 1 1 1 1 [ , ] ( )/2 a b b a b a ，且 − = − . 3、对新的有根区间重复步骤 1、2，仅当出 现情况 1 时计算过程中断. ⚫ 误差分析及做多少次二分的估计：

记第n次过程得到的有根区间为nh2,有 anbl,b]…→[mbhn an bn b1 若hn-an<E,则取 a .+b 作为x的近似值,此时误差为 (b-a) 考虑误差xnx*(b-a)<E,则可通过不 等式大致估计出需经多少步能达到精度要 求。 由于二分法的收敛速度较慢,常用作求 初始近似值。 优点:算法简单,且收敛总能得到保证。 注意:由于在偶重根附近曲线y=f(x)为向 上凹或向下凹,即f(a)与f(b)的正负号相 同,所以不能用二分法求偶重根。 例1:用二分法求方程f(x)=x3-x-1=0在

记第 n 次过程得到的有根区间为 [ , ] a b n n ，有 0 0 1 1 [ , ] [ , ] [ , ] a b a b a b    n n 若 b a n n −  ，则取 * 2 a b x x n n n + = = . 作为 * x 的近似值，此时误差为 1 * 1 | | ( ) 2 2n b a x x b a n n n + − −  = − . 考虑误差 1 * 1 | | ( ) 2n x x b a n  + −  −  ，则可通过不 等式大致估计出需经多少步能达到精度要 求。 由于二分法的收敛速度较慢，常用作求 初始近似值。 优点：算法简单，且收敛总能得到保证。 注意： 由于在偶重根附近曲线 y f x = ( ) 为向 上凹或向下凹，即 f a( ) 与 f b( ) 的正负号相 同，所以不能用二分法求偶重根。 例 1：用二分法求方程 f x x x ( ) 1 0 = − − = 3 在

[15内的实根,要求E0,其具体过程如下 f(xn)的 符号 1.51.25 11.251 5 375 21.251.3751.3125 31.31251.3751.3438 41.31251.34381.3281 5 31251.32811.3203 61.32031.32811.3242 x=x.=1.3242 =0.0039.<0.005 7 课堂练习:P35.2 试位法(二分法的一种改进) 设f(x)∈CIa,b],且f(a)f(b)<0,则f(x)=0

[1,1.5] 内的实根，要求  0.005 。 解： 1 1 * 1.5 1 | | 0.005 2 2 n n n b a x x  + + − − −  =  = ， n 取 6 即 可。 已知 0 0 f a f b ( ) 0, ( ) 0   ，其具体过程如下： n an bn xn f x( ) n 的 符号 0 1 1.5 1.25 - 1 1.25 1.5 1.375 + 2 1.25 1.375 1.3125 - 3 1.3125 1.375 1.3438 + 4 1.3125 1.3438 1.3281 + 5 1.3125 1.3281 1.3203 - 6 1.3203 1.3281 1.3242 - 6 * 1.5 1 1.3242 0.0039 0.005 27 x x − = = =  课堂练习：P35.2 三 .试位法（二分法的一种改进） 设 f x C a b ( ) [ , ]  ，且 f a f b ( ) ( ) 0   ，则 f x( ) 0=

在小内至少有一个实根x,且总假定所 讨论的隔根区间只有一个根 y=f(x) b 试位法的主要思想如下:先选定两个小 的正数δ和E。 1、记anb=[ab,过两点(an,f(a) 和(b,f(b)作一条直线,它与x轴的交 点的横坐标记为x,判断f(x)?若成立 则x即为所求的根,停;否则进入下一步。 2、判断f(a)f(x)<0?若成立,说明在 [anx]内有一根,则令a=anb=x; 否则,a=x,b=b,则形成新的有根区间

在 [ , ] a b 内至少有一个实根 x * ，且总假定所 讨论的隔根区间只有一个根。 试位法的主要思想如下：先选定两个小 的正数  和  。 1、 记 0 0 [ , ] a b [ , ] a b ，过两点 0 0 ( , ( )) a f a 0 0 和( , ( )) b f b 作一条直线，它与 x 轴的交 点的横坐标记为 0 x ，判断 0 | ( )| f x  ？若成立， 则 0 x 即为所求的根，停；否则进入下一步。 2、 判断 0 0 f a f x ( ) ( ) 0   ？若成立，说明在 0 0 [ , ] a x 内有一根，则令 1 0 1 0 a a b x = = , ； 否则， 1 0 1 0 a x b b = = , ，则形成新的有根区间

3、对新的有根区间重复以上步骤,当出现 情况1时停止; 记第n次过程得到的有根区间为[ an,bnl此时 anb1,b]…→[ an,bn 在试位的每一步计算中,有 若bn-ankE,则取=xn,作为x的近似值 可以验证,x∈[a,b]f"(x)≥0,试位法总是 收敛的。在一定条件下,试位法比二分法收 敛快些

1 1 [ , ] a b . 3、 对新的有根区间重复以上步骤，当出现 情况 1 时停止； 记第 n 次过程得到的有根区间为 [ , ], a b n n 此时 0 0 1 1 [ , ] [ , ] [ , ], a b a b a b    n n 在试位的每一步计算中，有 ( ) , 0,1, , ( ) ( ) b a x b f b n n n n n n f b f a n n − = −  = − 若 | | b a n n −  ，则取 x x * n = ，作为 x * 的近似值。 可以验证，    x a b f x [ , ], ( ) 0,  试位法总是 收敛的。在一定条件下，试位法比二分法收 敛快些