工程数学(19) 非线性方程的数值方法

1、工程数学工程数学 工程数学工程数学 在科学研究的数学问题中更多的是非线性问题，在科学研究的数学问题中更多的是非线性问题， 它们又常常归结为非线性方程或非线性方程组的它们又常常归结为非线性方程或非线性方程组的 求解问题。求解问题。 第一节第一节 非线性方程求根的迭代法非线性方程求根的迭代法 第二节第二节 非线性方程组的简单迭代法非线性方程组的简单迭代法 第三节第三节 非线性方程组的非线性方程组的NewtonNewton型迭代法型迭代法 第九章第九章 非线性方程组的数值方法非线性方程组的数值方法 工程数学工程数学 工程数学工程数学 满足方程满足方程(1)(1)的的x值通常叫做值通常叫做方程的根或解

2、方程的根或解， 也叫函数也叫函数f( (x)=0)=0的零点。的零点。 非线性方程的一般形式非线性方程的一般形式 f(x)=0 (1) 这里这里f( (x) )是单变量是单变量x 的函数，它可以是的函数，它可以是代数多项式代数多项式 f( (x)=)=a0+a1x+anxn (an0) 也可以是也可以是超越函数超越函数，即不能表示为上述形式的函数。，即不能表示为上述形式的函数。 第一节第一节 非线性方程求根的迭代法非线性方程求根的迭代法 工程数学工程数学 工程数学工程数学 在用近似方法时，需要知道方程的根所在区间。在用近似方法时，需要知道方程的根所在区间。 若区间若区间 a,b 含有方程含有方

3、程f(x)=0 0的根，则称的根，则称 a,b 为为f(x)=0 的的有根区间有根区间；若区间若区间 a,b 仅含方程仅含方程f(x)= 0 0的一个根，的一个根， 则称则称 a,b 为为f(x)= 0的一个的一个隔根区间。隔根区间。求隔根区间有求隔根区间有 两种方法：两种方法： 一、非线性方程求根的基本问题包括：根的存在一、非线性方程求根的基本问题包括：根的存在 性、根的隔离和根的精确化性、根的隔离和根的精确化 根的存在定理根的存在定理( (零点定理零点定理) )： f(x)为为 a,b 上的连续函数，若上的连续函数，若 f(a)f(b)0 0，则，则 a,b 中至少有一个实根。如果中至少有

4、一个实根。如果f(x)在在 a,b 上还是单上还是单 调递增或递减的，则调递增或递减的，则f(x)=0 0仅有一个实根。仅有一个实根。 工程数学工程数学 工程数学工程数学 例如，求方程例如，求方程3 3x-1-1-cosx=0 0的隔根区间。的隔根区间。 将方程等价变形为将方程等价变形为3 3x-1=-1=cosx ，易见，易见y=3 3x-1-1与与 y=cosx的图像只有一个交点位于的图像只有一个交点位于0.50.5，11内内。 画出画出y= =f( (x) )的略图，从而看出曲线与的略图，从而看出曲线与x轴交点轴交点 的大致位置。也可将的大致位置。也可将f( (x)=0)=0等价变形为等

5、价变形为g1 1( (x)=)=g2 2( (x) ) 的形式，的形式，y= =g1 1( (x) )与与y= =g2 2( (x) )两曲线交点的横坐标所两曲线交点的横坐标所 在的子区间即为含根区间。在的子区间即为含根区间。 (1)描图法描图法 工程数学工程数学 工程数学工程数学 (2)逐步搜索法逐步搜索法 运用零点定理可以得到如下逐步搜索法：运用零点定理可以得到如下逐步搜索法： 先确定方程先确定方程f( (x)=0)=0的所有实根所在的区间的所有实根所在的区间 为为 a, ,b,从从x0 0= =a 出发出发, ,以步长以步长 h=( (b-a) )/n 其中其中n是正整数，在是正整数，在

6、 a, ,b 内取定节点：内取定节点： xi=x0 0ih ( (i=0,1,2=0,1,2，n) ) 计算计算f( (xi) )的值的值, ,依据函数值异号及实根的个数确依据函数值异号及实根的个数确 定隔根区间定隔根区间, ,通过调整步长，总可找到所有隔根通过调整步长，总可找到所有隔根 区间。区间。 工程数学工程数学 工程数学工程数学 例例2.22.2 求方程求方程 x3 3-3.2-3.2x2 2+1.9+1.9x+0.8=0+0.8=0的隔根区间。的隔根区间。 解：设方程的根为解：设方程的根为 ， = max 1， |-3.2-3.2| ，|1.91.9| 8.0 1 = max |-3

7、.2-3.2| , |1.91.9| , |0.80.8| =3.23.2 故故 ,即有根区间为即有根区间为(-4.2,-0.2-4.2,-0.2)和和(0.2,4.20.2,4.2)2420.|. 对于对于m次代数方程次代数方程 f (x) = xm+am-1 1xm-1 1+ +a1 1x+a0=0其根的其根的 模的上下界有如下结论：模的上下界有如下结论： (1)若若= max |am-1 1| , , |a1 1| , |a0 0| ，则方程根的模小于则方程根的模小于+1 (2)若若= max 1， |am-1 1| , , |a1 1| ,则方程根的模大于则方程根的模大于 0 1 a1

8、 1 工程数学工程数学 工程数学工程数学 定义定义1 若有若有x* 满足满足 (x*)=0 ， 则称则称x*为方程为方程 的根或函数的根或函数f( (x) )的零点，特别地，如果函数的零点，特别地，如果函数f( (x) )可分可分 解为解为 f( (x) ) =(x x*)mg(x) 且且 g(x* ) 0, 则称则称x*是是f( (x) )的的m重零点或重零点或f( (x) ) =0的的m重根。重根。 当当m=1时，称时，称x*是是f( (x) )的单根的单根 或单零点。或单零点。 工程数学工程数学 工程数学工程数学 定理定理1 设函数设函数 f( (x) )Cma, ,b, 则点则点p(a

9、, ,b)是是f( (x) ) 的的m重零点，当且仅当重零点，当且仅当 f( (p) ) = f( (p) ) = f( (p) ) =f(m-1)(p)=0, 但但 f(m)(p) 0 证明证明:(充分性充分性)将将f( (x) )在点在点p作作m-1阶阶Taylor展开展开 之之间间。与与位位于于px px m f px m pf pxpfpfxf x mx m m m )( ! )( )( )!1( )( )( )()( )( 1 ) 1( 由假设由假设 )()()( ! )( )( )( xgpxpx m f xf mmx m 0 ! )( )( )( m pf pg m 这这里里，

10、证毕证毕 .)(1重重零零点点的的是是，由由定定义义mxfp ! )( )( )( m f xg x m 工程数学工程数学 工程数学工程数学 例例 给定方程：给定方程： x-sinx =0,问问x*=0是几重零点是几重零点. 解：解：设设 f( (x) ) = x-sinx,则则 f( (0) )=0; f( (x) ) =1-cosx , f (0)=0; f(x)=sinx , f(0)=0; f (3)(x)=cosx , f (3)(0)=1; 由定理由定理1, x*=0是是3重零点重零点. 工程数学工程数学 工程数学工程数学 )lim()(limlim 1k k k k k k xx

11、x 知知=( () )，即即 xk 收敛于方程的根收敛于方程的根 。 二、简单迭代法二、简单迭代法 简单迭代法简单迭代法又称为又称为不动点迭代法不动点迭代法，基本思想是基本思想是 首先构造不动点方程首先构造不动点方程 x=(x)，即由方程，即由方程 f(x)=0变换变换 为等价形式为等价形式 x=(x), 式中式中(x)称为称为迭代函数。然后迭代函数。然后 建立迭代格式：建立迭代格式：xk+1 =(xk)称为不动点迭代格式。称为不动点迭代格式。 当给定初值当给定初值x0 后后, , 由迭代格式由迭代格式xk+1 =(xk)可求得可求得 数列数列 xk 。如果。如果 xk 收敛于收敛于，且，且(

12、x)在在连续，连续，则则 就是不动点方程的根。因为：就是不动点方程的根。因为： 工程数学工程数学 工程数学工程数学 记记y1=x , y2=(x) , 它们交点的横坐标它们交点的横坐标即为方程的根即为方程的根 xy 1 )( 2 xy )(,( 00 xx )(,( 11 xx ),( 22 xx )(,( 22 xx ),( 11 xx 0 x 2 x 1 x p x y 0 0 x 1 x 2 x )( 2 xy xy 1 x y 0 工程数学工程数学 工程数学工程数学 x y y = x x y y = x x y y = x x y y = x x*x* x*x* y=(x) y=(x

13、) y=(x) y=(x) x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 工程数学工程数学 工程数学工程数学 对于迭代法需要讨论的基本问题是，迭代函数的构对于迭代法需要讨论的基本问题是，迭代函数的构 造，迭代序列的收敛性和收敛速度以及误差估计。造，迭代序列的收敛性和收敛速度以及误差估计。 问题：问题：( (x) )的形式不唯一，如：的形式不唯一，如： 2100210 xx xx )2lg( xx 210 1 n x n x )2lg( 1 nn xx 取初始值取初始值 ，计算结果如下：，计算结果如下：3 . 0 0 x 0.3 0.3 -0.0

14、047 0.3617 -1.0108 0.3732 0.3753 0.3757 210 1 n x n x )2lg( 1 nn xx 0 x 1 x 2 x 3 x 4 x 工程数学工程数学 工程数学工程数学 用蛛网图观察不动点迭代用蛛网图观察不动点迭代 2 2 1 1 2 1 ( )40 4 4 1 4 12 nn n n nn nn n f xxx xx x x xx xx x 求求方方程程的的根根。构构造造如如下下三三个个格格式式： （1 1） （2 2） （3 3） zlxp113 工程数学工程数学 工程数学工程数学 若从任何可取的初值出发都能保证收敛，则若从任何可取的初值出发都能保

15、证收敛，则 称它为称它为大范围收敛大范围收敛。如若为了保证收敛性必须选。如若为了保证收敛性必须选 取初值充分接近于所要求的根，则称它为取初值充分接近于所要求的根，则称它为局部收局部收 敛敛。 通常局部收敛方法比大范围收敛方法收敛得通常局部收敛方法比大范围收敛方法收敛得 快。因此，一个合理的算法是先用一种大范围收快。因此，一个合理的算法是先用一种大范围收 敛方法求得接近于根的近似值（如对分法），再敛方法求得接近于根的近似值（如对分法），再 以其作为新的初值使用局部收敛法（如迭代法）以其作为新的初值使用局部收敛法（如迭代法） 。 这里讨论迭代法的收敛性时，均指的是局部这里讨论迭代法的收敛性时，均指

16、的是局部 收敛性。收敛性。 工程数学工程数学 工程数学工程数学 考虑方程考虑方程 x = (x), (x) Ca, b, 若若 ( I ) 当当 x a, b 时，时， (x) a, b； ( II )对对 x a, b,有有 | (x) | L 1 成立。成立。 则任取则任取 x0 a, b，由，由 xk+1 = (xk) 得到的序列得到的序列 收敛于收敛于(x) 在在a, b上的唯一不动点。并且有误差估上的唯一不动点。并且有误差估 计式：计式： 0kk x 1 | *| 1 kkk L xxxx L 10 | *| 1 k k L xxxx L ( k = 1, 2, ) 且存在极限且存在

17、极限 1 * lim* * k k k xx x xx 定理定理2 2（收敛定理）（收敛定理） 工程数学工程数学 工程数学工程数学 证明：证明： (x) 在在a, b上存在不动点？上存在不动点？ 令令( )( )f xxx ()axb 0( )( ),f aaa 0( )( )f bbb )(xf有根有根 不动点唯一？不动点唯一？ 反证：若不然，设还有反证：若不然，设还有 ，则，则()xx ( *)( )( )( *),xxxx xx* 在在和和 之间之间 *x x 10 ()( )x*x 而而1 |( )|*xx 当当k 时，时， xk 收敛到收敛到 x* ？ |*| k xx 111 |

18、( *)()| |()| | *| kkk xxxx 0|*|.|*| 01 xxLxxL k k 工程数学工程数学 工程数学工程数学 ?| 1 |*| 1 kkk xx L L xx |*|*|*|*| 11kkkkkk xxLxxxxxxxx ?| 1 |*| 01 xx L L xx k k 1110 |.| k kkkk xxL xxLxx 1 * lim*? * k k k xx x xx 1 *()(*) limlim( *) * kkk kk kk xxxx x xxxx 111 11 | ()()|()()| |()|()| kkkkkkk kkkkk xxxxxx xxL x

19、x | 1 | 1 1 |*| 11 kkkkk xx L L xx L xx 工程数学工程数学 工程数学工程数学 定理条件非必要条件，可将定理条件非必要条件，可将a, b缩小，定义缩小，定义局部收局部收 敛性敛性：若在：若在 x* 的某的某 领域领域 B = x | | x x* | 有有 C1a, b 且且 | (x*) | 1，则由则由 x0 B 开始的迭代开始的迭代 收敛。即收敛。即调整初值可得到收敛的结果调整初值可得到收敛的结果。 工程数学工程数学 工程数学工程数学 则称数列则称数列 为为 阶收敛，也称相应的迭代法为阶收敛，也称相应的迭代法为 阶阶 方法。当方法。当 且且 时，称数列

20、时，称数列 为线性收敛为线性收敛. 当当 时，称数列时，称数列 平方收敛（或二阶收敛）平方收敛（或二阶收敛）. 当当 时，称数列时，称数列 为超线性收敛。为超线性收敛。 定义定义 设数列设数列 收敛于收敛于 ,令误差令误差 ,如果存如果存 在某个实数在某个实数 及正常数及正常数 ，使，使 n x nn xe 1p C C e e p n n n | | lim 1 n xpp 1p 10 C n x 2p n x 1p n x p 显然显然 ， 越大，数列收敛的越快。所以，迭代法越大，数列收敛的越快。所以，迭代法 的收敛阶是对迭代法收敛速度的一种度量。的收敛阶是对迭代法收敛速度的一种度量。 工

21、程数学工程数学 工程数学工程数学 定理定理3 3 （迭代法的局部收敛定理）（迭代法的局部收敛定理） 设设是方程是方程x= =( (x) )的根，如果的根，如果 (1)(1)迭代函数迭代函数( (x) )在在的邻域的邻域可导；可导； (2)(2)在在的某个邻域的某个邻域S= =x:|:|x- -| | , ,对于任对于任 意的意的 x S 有有 1| )( | Lx 则对于任意的初值则对于任意的初值 x0 0 S S ，迭代公式，迭代公式xn+1 1= =( (xn) ) 产生的数列产生的数列 xn ，收敛于方程的根，收敛于方程的根 。 工程数学工程数学 工程数学工程数学 定理定理3 3 （迭代

22、法的局部收敛定理）（迭代法的局部收敛定理） 设设是方程是方程x= =( (x) )的根，如果的根，如果 (1)(1)迭代函数迭代函数( (x) )在在的邻域的邻域一阶导数连续；一阶导数连续； 则存在则存在的某个邻域的某个邻域S= =x:|:|x- -| | 及正数及正数 L1,L1,使对于任意的使对于任意的 x S 有有 | ( )|1xL 取任意的初值取任意的初值 x0 0 S S ，迭代公式，迭代公式xn+1 1= =( (xn) ) 产生的数列产生的数列 xn ，收敛于方程的根，收敛于方程的根 。 (2)| ( )| 1 工程数学工程数学 工程数学工程数学 控制误差控制误差的方法：的方法

23、： (1) 先计算满足误差要求的迭代次数先计算满足误差要求的迭代次数n，再迭代。由，再迭代。由 | 1 | 01 xx L L x n n 可得可得 L xx L n ln | )1 ( ln 01 (2) 事后误差估计法。由于事后误差估计法。由于 | 1 | 1 nnn xx L L x 因而可用因而可用| |xn-xn-1| |来控制迭代过程。来控制迭代过程。 工程数学工程数学 工程数学工程数学 例例 用迭代法求用迭代法求x3 3- -x2-1=0-1=0在隔根区间在隔根区间1.4,1.51.4,1.5 内的根，要求准确到小数点后第内的根，要求准确到小数点后第4 4位位. 解：解：(1)(

24、1)由方程的等价形式由方程的等价形式 )(1 32 xxx 构造迭代公式构造迭代公式 3 2 1 1 nn xx 由由 3 22 )1(3 2 )( x x x 知知( (x) )在在（1.4,1.5)1.4,1.5)可导，且可导，且 15 . 0| )(| x 故迭代法收敛。故迭代法收敛。 工程数学工程数学 工程数学工程数学 y x 0 b )(xfy a 0 x 1 x 2 x 任取初始值任取初始值 ， bax, 0 )(xfy 上过点上过点 的切线方程的切线方程 为：为： )(,( 00 xfx )()( 000 xxxfxfy 与与 轴交于点轴交于点 1 xx )( )( 0 0 01

25、 xf xf xx 过点过点 的切线方程为的切线方程为 )(,( 11 xfx )()( 111 xxxfxfy 与与 轴交于点轴交于点x 2 x )( )( 1 1 12 xf xf xx 如此下去得牛顿迭代公如此下去得牛顿迭代公 式式: )( )( 1 k k kk xf xf xx 用切线代替曲线，用用切线代替曲线，用 线性函数的零点作为线性函数的零点作为 f(x)的零点的近似值。的零点的近似值。 工程数学工程数学 工程数学工程数学 （收敛的充分条件收敛的充分条件）设）设 f C2a, b，若，若 (1) f (a) f (b) 0； 则则Newtons Method产生的序列产生的序列

26、 xk 收敛到收敛到f (x) 在在 a, b 的的 唯一根。唯一根。 根唯一根唯一 产生的序列单调有产生的序列单调有 界，保证收敛。界，保证收敛。 定理定理4 工程数学工程数学 工程数学工程数学 y x 0 b a x0 0)( x f 0)( x f y x 0 b a x0 0)( x f 0)( x f y x 0 b a x0 0)( x f 0)( x f y x0 B a x0 0)( x f 0)( x f 工程数学工程数学 工程数学工程数学 例例 用迭代法求用迭代法求 在隔根区间在隔根区间1.4,1.51.4,1.5 01 23 xx 内的根，要求准确到小数点后第内的根，要求

27、准确到小数点后第4 4位。位。 （1 1）牛顿迭代公式为牛顿迭代公式为 nn nn nn nn n n n nn xx xx xx xx x xf xf xx 23 12 23 1 )( )( 2 23 2 23 1 （2 2）2 . 0)4 . 1( f2 . 0)5 . 1( f 5 . 1 , 4 . 1 x 当当 时有，时有， 023)( 2 xxxf06)( xxf 因因 , ,故取故取 , ,牛顿迭代法收敛。牛顿迭代法收敛。0)5 . 1()5 . 1( f f5 . 1 0 x 工程数学工程数学 工程数学工程数学 （局部收敛性局部收敛性）设）设 f C2a, b，若，若 x* 为

28、为 f (x) 在在a, b 上的根，且上的根，且 f (x*) 0，则存在，则存在 x* 的邻域的邻域 使得任取初使得任取初 值值 ，Newtons Method产生的序列产生的序列 xk 收敛到收敛到x*， 且满足且满足 *)(xB *)( 0 xBx *)(2 *)( )*( * lim 2 1 xf xf xx xx k k k 定理定理5 证明：证明：Newtons Method 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代 其中其中 ，则，则 ( ) ( ) ( ) f x xx fx 2 01 ( *)( *) ( *) ( *) fxf x x fx 收敛收敛 由由

29、 Taylor 展开：展开： 2 )*( !2 )( )*)()(*)(0 k k kkk xx f xxxfxfxf 工程数学工程数学 工程数学工程数学 2 )*( )(! 2 )( )( )( * k k k k k k xx xf f xf xf xx 1 k x )(2 )( )*( * 2 1 k k k k xf f xx xx 只要只要 f (x*) 0，则令，则令 可得结论。可得结论。 k 注：注：在在单根单根 附近收敛快，是平方收敛的附近收敛快，是平方收敛的 由由 Taylor 展开：展开： 2 )*( !2 )( )*)()(*)(0 k k kkk xx f xxxfxf

30、xf 工程数学工程数学 工程数学工程数学 对于迭代过程对于迭代过程 ，如果，如果 在所求根在所求根 的邻近连续，并且的邻近连续，并且 (*) 则该迭代过程在点则该迭代过程在点 邻近是邻近是P阶收敛的。阶收敛的。 p k p k xx p xx)( ! )( * )( * 1 因此对迭代误差有因此对迭代误差有: 。这表明迭代过程。这表明迭代过程 确实为确实为P阶收敛，阶收敛，证毕。证毕。 ! *)( )( 1 p x e e p p k k )( 1kk xx )( 1kk xx )( )( x p * x 0)()()( *) 1(* xxx p 0)( *)( x p * x 定理定理6 6

31、 0 * ()x )( 1kk xx )( k x () * ( ) ()()() ! p p kk xxxx p 1 )( kk xx * )(xx * x 证明：证明：由于由于 。据上定理，立即可以断定迭代过程。据上定理，立即可以断定迭代过程 具有局部收敛性。再将具有局部收敛性。再将 在根在根 处展开，利用条件处展开，利用条件( (* *) )，则有，则有 注意到注意到 ，由上式得，由上式得 工程数学工程数学 工程数学工程数学 1 ( )0(), , () (0). () : k kk k f xma mZ f x xxmk fx 若若方方程程有有重重根根试试证证明明 牛牛顿顿迭迭代代法法

32、是是线线性性收收敛敛的的 而而改改用用修修改改的的格格式式 才才是是局局部部平平方方收收敛敛的的 例例 1 ( ) (1) ( ) ( )0 ( )()( ),( )0. ( )()( )()( ) () ( ) ) ( )( ) : ) m mm f x xx fx f xm f xxah xh a fxm xah xxah x xa h x xx mh xxah x 对对牛牛顿顿格格式式, , 迭迭代代函函数数 ( ( 因因有有重重根根, , 故故有有且且 代代入入迭迭代代函函数数式式 ( ( 证证明明 工程数学工程数学 工程数学工程数学 ( ) )1 ( )()( ) ( ) ()()

33、( )()( ) h x x mh xxa h x dh x xa dx mh xxa h x ( ( 1 1 1 ,( )10. , ( )()( ()( ) ( )()() |1 ( )10 lim | . kkk kk k k k xaa m axaxxa axao xa ax Ca axm 代代入入有有 于于是是 由由 得得到到 故故这这种种牛牛顿顿迭迭代代法法只只有有线线性性收收敛敛速速度度 工程数学工程数学 工程数学工程数学 2 1 2 ( ) (2) ( ) () ( ) ) ( )()( ) ( ) )1 ( )()( ) ( ) ()() ( )()( ) ,)0 1 ) 2

34、 1 ) 2 kkkk kk f x xxm fx xa h x xxm mh xxa h x mh x x mh xxa h x dh x m xa dx mh xxa h x a axaxaxa ax 对对修修改改的的牛牛顿顿格格式式, , 迭迭代代函函数数 ( ( ( ( ( ( 此此时时( ( 再再由由( ( ( ( ( 工程数学工程数学 工程数学工程数学 1 2 |11 |)|)|0 |22 . k k k ax Ca ax 得得到到 ( ( ( 因因此此修修改改后后的的牛牛顿顿格格式式是是平平方方收收敛敛的的 工程数学工程数学 工程数学工程数学 1 1、优点：牛顿迭代法具有平方收敛的速度，所以、优点：牛顿迭代法具有平方收敛的速度，所以 在迭代过程中只要迭代几次就会得到很精确的解。在迭代过程中只要迭代几次就会得到很精确的解。 这是牛顿迭代法比简单迭代法优越的地方。这是牛顿迭代法比简单迭代法优越的地方。 2 2、缺点：选定的初值要接近方程的解，否则有可、缺点：选定的初值要接近方程的解，否则有可 能得不到收敛的结果。再者，牛顿