第四章非线性方程的数值解法

1、数数 值值 分分 析析武武 汉汉 大大 学学数学与统计学院基础数学系数学与统计学院基础数学系刘丁酉 主页主页4.1 引言引言4.2 二分法和试位法二分法和试位法4.3 迭代法迭代法4.4 迭代加速收敛的方法迭代加速收敛的方法4.5 Newton迭代法和割线法迭代法和割线法4.6 非线性方程组的数值解法非线性方程组的数值解法4 4 非线性方程的数值解非线性方程的数值解法法主页主页4.1 4.1 引言引言( )0f x , , , , xRfC a ba b()0f x主页主页本章主要讨论数值求解方程（4.1.1）其中 也可以是无穷区间。如果实数 满足方程（4.1.1），即 ，则称 是方程（4.1

2、.1）的根，或称 是 的零点。 两类方程：两类方程：1.代数方程代数方程：1110( ),nnnnf xa xaxa xa0na 5n 其中 ，易知，对于 情形，它无求根公式，只能用数值方法求根。 2. 2.超越方程超越方程：例如，方程 等，也只能用数值法求根。21sin,302xxxxexxx( )f x1 1根的存在性。方程有没有根？若有根，有几个根？根的存在性。方程有没有根？若有根，有几个根？2 2这些根大致在哪里？如何把根隔离开来？这些根大致在哪里？如何把根隔离开来？3 3根的精确化根的精确化定理定理1 1（介值定理）（介值定理）设函数设函数 f f ( (x x) ) 在区间在区间a

3、, ba, b上连续，如果上连续，如果 f f ( (a a) ) f f ( (b b) 0) 0，则方程则方程 f f ( (x x) = 0 ) = 0 在在a, ba, b内至少有一实根内至少有一实根x x* *。 数值求根需要探讨的问题：数值求根需要探讨的问题：1画出画出 f(x) 的略图，从而看出曲线与的略图，从而看出曲线与x 轴交点的位置。轴交点的位置。f(x)0 xhx 0 x*ba2从左端点从左端点x = a出发，按某个预先选定的步长出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点一步一步地向右跨，每跨一步都检验每步起点x0和终点和终点x0 + h的函数值

4、，若的函数值，若0)()(00hxfxf那么所求的根那么所求的根x*必在必在x0与与x0+h之间，这里可取之间，这里可取x0或或x0+h作为根的初始近似。作为根的初始近似。 基本步骤：基本步骤：例例1 1：考察方程：考察方程01)(3xxxfx00.51.01.5f (x) 的符号的符号4.2 4.2 二分法和试位法二分法和试位法主页主页4.2.1 4.2.1 二分法二分法4.2.2 4.2.2 试位法试位法4.2.14.2.1二分法二分法 二分法是方程求根中最为简单、直观的一种求根进代法，其理论基础是高等数学中闭区间上连续函数的介值定理。 主页主页 执行步骤执行步骤1计算计算f (x)在有解

5、区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f (x)在区间中点处的值在区间中点处的值f (x1)。3判断若判断若f (x1) = 0，则则x1即是根，否则检验即是根，否则检验：（1）若若f (x1)与与f (a)异号异号，则知解位于区间则知解位于区间a, x1， b1=x1, a1=a;（2）若若f (x1)与与f (a)同号同号，则知解位于区间则知解位于区间x1, b， a1=x1, b1=b。主页主页反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：(a, b), (a1, b1), , (ak, bk), 4、当当11kka

6、b时时)(211kkkbax5、则、则即为根的近似即为根的近似简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 主页主页例例2 2： 求方程01)(3xxxf的根。kakbkxkf (xk)的符号的符号011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-主页主页 4.3 迭代法迭代法1 1简单迭代法简单迭代法简单迭代法的基本思想第一

7、步:求出与方程f(x)=0等价的方程x=g(x)第二步:给定 ，由迭代格式： xn+1=g(xn)n=0,1,2, 产生一收敛的数列xn 设X*是xn的极限,若g(x)是连续的,再由第一步可推出X*是f(x)=0的解.xn+1是f(x)=0解的第n+1次近似; x0是解的初始近似;g(x)是迭代函数; xn+1=g(xn)是迭代格式.0X主页主页2.2.几何意义几何意义 的根从几何上看是 与 交点的横坐标。( )xg xyx yg x例例3 3 求方程 在 附近的根。310 xx 01.5x 解解：方程 等价方程为310 xx (1)31xx 311kkxx012871.51.35721,1.

8、33086,1.32472xxxxx 1.32472x(2)1xx 311kkxx01231.5,2.375,12.396,1903.739xxxx 主页主页 由上面例子可看出，迭代格式可能收敛，也可能发散。因而须解决以下两个问题：（1）怎样选择迭代格式 及 使 收敛？1kkxg x0 x kx（2）给出误差 的估计式，并给出控制迭代次数的具体方法。kxx3.3.迭代过程的收敛性迭代过程的收敛性简单迭代法的两个基本问题: (1)如何选取初值和迭代公式. (2)如何停止迭代过程xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)

9、x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1定理4.3.1 如果 g(x)满足下列条件 （1）当xa, b时，g(x)a, b （2）当任意xa, b时，存在0 L 1，使 则方程x = g (x)在a, b上有唯一的根x*,且对任意初值 x0a, b时，迭代序列xk+1=g (xk) (k = 0, 1, ) 收敛于x*。1)( Lxg(4.3.1) 证证:先证解的存在性： 作辅助函数 f(x)=x-g(x),由条件知 f(x)在a,b上连续,且 f(a)f(b)0;由连续函数的零点定理,至少存在一x* a, b,使使 f(x*)=0. 再证解的唯一性： 设f

10、(x1)=0,那么根据微分中值定理有 x1- x*=g(x1)-g(x*)=g(x2)(x1- x*)即有 根据条件有 , ,即即 最后证迭代数列收敛：首先,由于 不等式两边取极限得 1112120()()()()()()()nnnnnnnxxg xg xg yxxL xxL xxL xxnxx12()(1()0 xxg x10 xx1xx 定理 4.3.1中的条件要求对任意的 ，均有不等式(4.3.1)成立.这时对任意的 ,迭代数列收敛.称此迭代格式为全局收敛. , xa b 定义定义4.3.14.3.1 设 是方程 的解,如果存在一个正数 ,使得迭代过程对于任意的 均收敛,则称这种迭代格式

11、为局部收敛.0 , xa b( )xg x0(, )xU xx定理定理4.3.2 设x*是方程x= g(x)的解,如果当xU(x*,) 时，有则对任意初值x0 U(x*,)，迭代序列xk+1=g (xk) (k = 0, 1, )收敛于x*。 如果当xU(x*,) 时，有则对任意初值x0 U(x*,)，迭代序列xk+1=g (xk) (k = 0, 1, )发散。1)( Lxg(4.3.2)1)( Mxg4 4迭代法迭代终止的条件迭代法迭代终止的条件 定理定理4.3.34.3.3 设 是 的解,如果对于任意的 ,均有 则有误差估计式 x),(*xUx1)( Lxg*111nnnxxxxL( )

12、xg x证明证明 首先有再由微分中值定理有所以有nnnnxxxxxx11*nnnnxxLxxgxgxgxx*1*)( )()(*111nnnxxxxL 欲使绝对误差限为 ,只要就够了.故只要即可. 至此,我们可以依迭代法编写程序进行计算了.*111()1nnnxxxxL11)1 (Lxxnn1 5 5迭代过程的收敛速度迭代过程的收敛速度定义定义4.3.1： 设由某方法确定的序列xk收敛于方程的根x*，如果存在正实数p，使得Cxxxxpkkk*1*lim（C为非零常数）则称序列xk收敛于x*的收敛速度是p阶的，或称该方法具有p 阶敛速。当p = 1时，称该方法为线性(一次)收敛；当p = 2时，

13、称方法为平方（二次）收敛；当1 p0;所以在0,1方程至少有一个解. 又方程的等价形式为 令 ,则 于是, 即解的迭代格式为( )1/5/10 xg xe( )102xf xex1510 xex x0,1, g(x)11010 xee 均有 01011510nxnxxe( )/10 xg xe 由于所以取极限得 根据定义知:此迭代格式为线性收敛.*111()()1010nnxxnnxxeeexx *1*110nnnxxexx *1*1lim10 xnnnxxexx4.5 4.5 Newton迭代法和割线法迭代法和割线法1、牛顿法及其收敛性、牛顿法及其收敛性x*x0 x1x2xyf(x)原理：将

14、非线性方程线性化, )()(0000 xxxfxf0100()()f xxxfx只要 f C1，每一步迭代都有f ( xk ) 0， 而 且 *limxxkk 则 x*就是 f (x)的根。)()(1kkkkxfxfxx (4.5.1)( )()(0000 xxxfxfx令 求f (x)在 x1 处的切线方程:)( )()(1111xxxfxfx1211()()f xxxfx一般地 定理定理4.5.1 设f (x)在a, b上满足下列条件：（1）f (a) f (b) 0则由（4.5.1）式确定的牛顿迭代序列xk收敛于f (x)在a, b上的唯一根x*。Newton法的收敛性依赖于法的收敛性依

15、赖于x0 的选取。的选取。x*x0 x0 x02 2牛顿法收敛的阶牛顿法收敛的阶 定理定理4.5.2 对于方程f(x)=0,设f(x)充分光滑，x*是f(x)=0在a,b内的根.（1）x*是单根,则牛顿迭代格式是2阶收敛的;（2） x*是m重根,则牛顿迭代格式是线性收敛的.此定理的证明涉及到定理2.4,请大家自己看例例5 5：求方程 的解01)2(4xex解解:设 则 f(0)=1, f(2)= -1 注:x0=3 or 81)2()(4xexfx44)410(41)( ,)46()( xxexxfexxf, 2 , 1,)46(1)2(04410nexxexxxnnxnnxnn在0,2内,f(x)0, f(0)f(0)0, 所以迭代格式为:例例6:6:设C为正实数,导出用牛顿法求 的公式,并证明迭代叙列的误差 满足解:设 ,则 于是有由于 所以在 内有一正根.又在 内, 根据定理2.5得牛顿迭代格式为:CCxennnnnxee221Cx Cx 22)( ,2)( ,)(2xfxxfCxxf012) 1(,)0(CCfCf1 , 0C1 , 0C0)( , 0)( xfxf)lim( 2, 1n210C