第七章非线性方程求根 §70简介 §7.1二分法(对分法) §7.2迭代法的基本理论 §7.3迭代的加速收敛方法 §74 Newton迭代法 §7.5弦割法和抛物线法 2004-11-22
2004-11-22 1 第七章 非线性方程求根 •§ 7.0 简介 •§ 7.1 二分法（对分法） •§ 7.2 迭代法的基本理论 •§ 7.3 迭代的加速收敛方法 •§ 7.4 Newton迭代法 •§ 7.5 弦割法和抛物线法
§7.0简介 、问题 求解非线性方程(x)=0 如多项式方程: pn(x)=anx+an1x”+…+a1x+a0=0 困难:方程的解难以用公式表达。 需要一定精度的近似解! 2004-11-22 2
2004-11-22 2 § 7.0 简介 一、问题 求解非线性方程 f(x)=0 ！ 如多项式方程： ( ) 1 0 0 1 = + 1 + + + = − p x a x a − x a x a n n n n n L 困难：方程的解难以用公式表达。 需要一定精度的近似解！
概念 方程∫(x)=0的解x称为方程∫(x)=0的根或 称为(x)的零点。若()=(x-x)g(x)其中 m为正整数,g()满足()≠0,则显然f()=0 这时称x为f(x)的m重零点,或称x为/(x)=0 的m重根。 定理:若f(x)有m阶连续导数,则x:是f(x) 的m重零点的充要条件为: f(x)=f(x)=…=∫(m)(x')=0,fm(x)≠0 2004-11-22
2004-11-22 3 二、概念 方程 的解 称为方程 的根或 称为 的零点。若 其中 m为正整数， 满足 ，则显然 这时称 为 的m重零点，或称 为 的m重根。 f ( ) x = 0 * x f (x) f (x) = 0 f ( ) x (x x ) g( ) x * m = − g(x) g(x) ≠ 0 ( ) 0 * f x = * x f ( ) x * x f (x) = 0 定理：若 有m阶连续导数，则 是 的m重零点的充要条件为： f (x) * x f (x) ( ) ( ) ( ) 0, ( ) 0 * * ( 1) * ( ) * = ′ = = = ≠ − f x f x f x f x L m m
概念(续) 证明:必要性 设x是fx)的m重零点,则fx)=(x-x)y(x)且g(x)≠0 f(x)=∑cx-x)yg(x ∑cm(m-1)…(m-i+1)(x-x m-1(m g 当0≤k≤m-1时 (x)=∑cm(m-1)…(Om-i+1(x-x)yg{m(x)=0 当k=m时 f(x)=∑cm(m-1)(m-+1)x-x)ngm"(x) =m!g(x)≠0 2004-11-22
2004-11-22 4 概念（续） 证明 ：必要性 设 是 的m重零点，则 且 * x f ( ) x ( ) ( ) ( ) * f x x x g x m = − ( ) 0 * g x ≠ ∑ [ ] = − = − k i k i m i i k k f x c x x g x 0 ( ) ( ) ( ) * ( ) ( ) ( ) ∑ = − − = − − + − k i i m i m i k c m m m i x x g x 0 * ( ) ( 1)L( 1)( ) ( ) ! ( ) 0 ( ) ( 1) ( 1)( ) ( ) * 0 ( ) * * * ( ) * = ≠ = ∑ − − + − = − − m g x f x c m m m i x x g x m i i m i m i m k L 当 时 k = m 0 ≤ k ≤ m −1 ( ) ( 1) ( 1)( ) ( ) 0 0 ( ) * * * ( ) * = ∑ − − + − = = − − k i i m i m i k k f x c m m L m i x x g x 当 时
概念(续) 充分性:设x使得八x)=0, f(x)=0,…,f(m(x)=0,f(m(x)≠0 由 Taylor公式得 f(x)=f(x)+f(x:)(x-x)+…+ x (x-x)+ f (x+e(x-x)) X-x 其中0<0<1。令9(x)=/m(x+(x-x)则有 f(x)=(x-x)"g(x) 且 g(x)=-f(m(x)≠0 根据定义x为f(x)的m重零点 证毕 2004-11-22
2004-11-22 5 概念（续） 充分性： m m m m x x m f x x x x x m f x f x f x f x x x ( ) ! ( ( )) ( ) ( 1)! ( ) ( ) ( ) ( )( ) * * * * 1 ( 1) * * * * − + − − + − = + ′ − + + − − θ L 由Taylor公式得 0 <θ <1 ( ( )) ! 1 ( ) ( ) * * f x x x m g x m = +θ − ( ) ( ) ( ) * f x x x g x m = − ( ) 0 ! 1 ( ) * ( ) * = f x ≠ m g x m 其中 。令 则有 且 ( ) 0 * f x = ( ) 0, , ( ) 0, ( ) 0 * ( 1) * ( ) * ′ = = ≠ − f x f x f x L m m * 设 使x 得 ， * 根据定义 x 为f (x) 的m重零点。 证毕
根的隔离 方程可能有多个实根,我们只能逐个求出来。 定义:设在区间[a,b]上方程有一个根,则称该区间 为方程的一个有根区间。若在区间[a,b上方程只有 个根,则称把方程的根隔离出来了 Remark:若能把有根区间不断缩小,则可以得出 根的近似值。 基于函数(x)的连续性质,常用的根的隔离的方法 有:函数作图法与试算法。 要找出方程的所有的根,要进行“根的搜索”。 返回 2004-11-22
2004-11-22 6 三、根的隔离 方程可能有多个实根，我们只能逐个求出来。 定义：设在区间[a,b]上方程有一个根，则称该区间 为方程的一个有根区间。若在区间[a,b]上方程只有 一个根，则称把方程的根隔离出来了。 Remark：若能把有根区间不断缩小，则可以得出 根的近似值。 基于函数f(x)的连续性质，常用的根的隔离的方法 有：函数作图法与试算法。 要找出方程的所有的根，要进行“根的搜索”。 返回
§7.1二分法(对分法) 算法 设f(x)在[ab]上连续,f(a)(b)<0且在a,b]内(x)=0 仅有一个实根x。二分法的基本思想是:逐步将 有根区间分半,通过判别函数值的符号,进一步 搜索有根区间,将有根区间缩小到充分小,从而 求出满足给定精度的根x的近似值。 具体算法: 记[ab为[a1b]。将区间[a1,b1分半,计算中点 (+b)以及函数值f(x)。 若f(x1)=0则x=x1。 2004-11-22 7
2004-11-22 7 § 7.1 二分法（对分法） 一、算法 设 在[a,b]上连续，f(a)f(b)<0且在[a,b]内f(x)=0 仅有一个实根 。二分法的基本思想是：逐步将 有根区间分半，通过判别函数值的符号，进一步 搜索有根区间，将有根区间缩小到充分小，从而 求出满足给定精度的根 的近似值。 f (x) * x * x 具体算法： ( ) 21 1 1 1 x = a + b ( )1 f x 记[a,b]为[a1,b1]。将区间[a1,b1]分半，计算中点 以及函数值 。 1 * 若则。 ( ) 0 x = x f x1 =
二分法(对分法)(续) 否则,若有f(x)f(a1)<0,则x∈[a1,x,令a2=a1,b2=x 或f(x1)f(b)<0,则x∈[x,b],令a2=x1,b2=h 新的有根区间[a2,b的长度b2-a2=,(b1-a)=(b-a) 再计算[a2,b2中点x2=22的函数值f(x2)。 若(x2)=0则x=x2。否则f(x2)f(a2)<0则x∈[a2x2], 令a3=a2,b=x2,或f(x2)f(b2)<0则x∈[x2h2, 令a3=x2b 新的有根区间{a3b的长度b2-a3=2(b2-a2)=n2(b-a 2004-11-22
2004-11-22 8 二分法（对分法）（续） 2 1 2 1 否则，若有 ，则 [ , ]，令 a = a ,b = x 1 1 * ( ) ( ) 0 x ∈ a x f x1 f a1 < 或 ， f (x1 ) f (b1 ) < 0 则 [ 1, 1] ，令 * x ∈ x b 2 1 2 1 a = x ,b = b 再计算[a2 ,b2 ]中点 的函数值 。 2 2 2 2 a b x + = ( ) 2 f x ( ) 21 ( ) 21 2 2 1 1 新的有根区间 的长度 b − a = b − a = b − a [ , ] a2 b2 [ , ] a3 b3 ( ) 21 ( ) 21 3 3 2 2 2 新的有根区间 的长度 b − a = b − a = b − a 令 。 3 2 3 2 a = a ,b = x 3 2 3 2 a = x ,b = b 令 ，或 f (x2 ) f (b2 ) < 0 则 ， 若 则 2。否则 则 ， * ( ) 0 x = x f x2 = ( ) ( ) 0 f x2 f a2 < [ , ] 2 2 * x ∈ a x [ , ] 2 2 * x ∈ x b
二分法(对分法)(续) 如此对分下去则得到一系列的有根区间 [a12b][a2,b2]→…=[ak2bk]2 且b k-1 (b-a) a1+ 由xk=k 及-x1s2(b-a)=7(b-a)k=12 当对分过程无限继续下去,则有根区间必收敛到 点,即imxx=x k->oo 2004-11-22
2004-11-22 9 二分法（对分法）（续） 如此对分下去则得到一系列的有根区间 [a1,b1] ⊃ [a2 ,b2 ] ⊃L⊃ [ak ,bk ] ⊃L ( ) 21 ( ) 21 1 1 1 b a b a b a k k k k k − = − = = − 且 − − L − ( ), 1,2,L 21 ( ) 2 * 1 x − x ≤ b − a = b − a k = 由 及 k k k k 2 k k k a b x + = 当对分过程无限继续下去，则有根区间必收敛到 一点，即 * lim xk x k = →∞
二分法(对分法)(续) 误差估计 定理:给定方程fx)=0,设fx)在区间[a,]上 连续,且(a)(b)<0,则由二分法产生的序列 xk}收敛于方程的根x*,且具有误差估计 xk-x≤(b-a)(k=1,2,…) 2004-11-22
2004-11-22 10 二分法（对分法）（续） 二、误差估计 定理：给定方程 f(x)=0，设 f(x)在区间[a,b]上 连续，且f(a)f(b)<0，则由二分法产生的序列 {xk}收敛于方程的根x*，且具有误差估计 ( ) ( 1,2, ) 2 * 1 xk − x ≤ k b − a k = L