计算方法7.1-7.3

1、第七章第七章 非线性方程的解法非线性方程的解法 12021-7-9 2021-7-92 7.1 隔根区间的确定隔根区间的确定 第七章第七章 非线性方程的解法非线性方程的解法 7.3 迭代迭代法法 7.2 对分法对分法 7.5 迭代法的收敛速度迭代法的收敛速度 7.4 牛顿牛顿(Newton)迭代法迭代法 7.6 弦截法弦截法 2 7.7 非线性方程组的解法非线性方程组的解法 在科学研究和工程设计中, 经常会遇到的一大类 问题是非线性方程 0)(xf-(1) 0*)(*,xfx使得如果存在一点 的根或零点为方程则称)1(*x 上只有一个根，在区间如果方程,)1(ba 为单根区间则称,ba 上有多

2、个根，在区间如果方程,)1(ba 为多根区间则称,ba 2021-7-93 当f(x)不是x的线性函数时，称对应的函数方程为 非线性方程。如果f(x)是多项式函数，则称为代数方 程，否则称为超越方程（三角方程，指数、对数方程 等）。一般称n次多项式构成的方程 )0(0 01 1 1 n n n n n aaxaxaxa 为n次代数方程,当n1时,方程显然是非线性的 一般稍微复杂的3次以上的代数方程或超越方程, 很难甚至无法求得精确解。本章将介绍常用的求解非 线性方程的近似根的几种数值解法 2021-7-94 通常方程根的数值解法大致分为三个步骤进行： 判定根的存在性。即方程有没有根？如果有根，

3、 有几个根？ 确定根的分布范围。即将每一个根用区间隔离开 来，这个过程实际上是获得方程各根的初始近似值。 根的精确化。将根的初始近似值按某种方法逐步 精确化，直到满足预先要求的精度为止。 2021-7-95 本章介绍方程的迭代解法，它既可以用来求解代数 方程，也可以用来解超越方程，并且仅限于求方程 的实根。 运用迭代法求解方程的根应解决以下两个问题： 确定根的初值; 将进一步精确化到所需要的精度。 2021-7-96 为了确定根的初值，首先必须圈定根所在的范围， 称为圈定根或根的隔离。 在上述基础上，采取适当的数值方法确定具有一定 精度要求的初值。 对于代数方程，其根的个数（实或复的）与其次数

4、 相同。至于超越方程，其根可能是一个、几个或无 解，并没有什么固定的圈根方法 求方程根的问题，就几何上讲,是求曲线 y=f (x) 与x轴交点的横坐标。 7.1 隔根区间的确定隔根区间的确定 2021-7-9 7 由高等数学知识知, 设f(x)为区间a,b上的单值连 续, 如果f(a)f(b)0 , 则a,b中至少有一个实根。如 果f(x)在a,b上还是单调地递增或递减，则仅有一个 实根。 n由此可大体确定根所在子区间，方法有： (1) 画图法 (2) 逐步搜索法 y=f(x) a b y x 2021-7-98 (1) (1) 画图法画图法 画出y=f(x)的略图，从而看出曲线与x轴交点的大

5、致位置。 也可将f(x)= 0分解为1(x)= 2(x)的形式，1(x)与2(x)两 曲线交点的横坐标所在的子区间即为含根区间。 例如例如 xlgx-1= 0 可以改写为lgx=1/x 画出对数曲线y=lgx, 与双曲线y= 1/x, 它们交点的横坐标位于区间2,3内 gxy x y 1 230 y x 2021-7-99 n对于某些看不清根的函数，可以扩大一下曲线 y 0 x y=f(x)y=kf(x) 2021-7-9 10 y 0 x A B a1b1a2b2 (2) (2) 搜索法搜索法 对于给定的f (x),设有根区间为A,B,从x0=A出发,以步 长h=(B-A)/n(n是正整数)

6、,在A,B内取定节点:xi=x0ih (i=0,1,2,n),从左至右检查f (xi)的符号,如发现xi与端点x0的 函数值异号,则得到一个缩小的有根子区间xi-1,xi。 2021-7-911 运用零点定理可以得到如下逐步搜索法： 先确定方程f(x)=0的所有实根所在的区间为 a,b,从x0=a 出发,以步长 h=(b-a)/n 其中n是正整数，在a,b内取定节点： xi=x0ih (i=0,1,2，n) 计算f(xi)的值,依据函数值异号及实根的个数确 定隔根区间,通过调整步长，总可找到所有隔根 区间。 2021-7-912 例例 求方程求方程 x3 3-3.2-3.2x2 2+1.9+1

7、.9x+0.8=0+0.8=0的隔根区间。的隔根区间。 解：设方程的根为解：设方程的根为 ， = max 1， |-3.2-3.2| ，|1.91.9| 8.0 1 = max |-3.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| , , |a

8、1 1| , |a0 0| ，则方程根的模小于则方程根的模小于+1 (2)若若= max 1， |am-1 1| , , |a1 1| ,则方程根的模大于则方程根的模大于 0 1 a1 1 2021-7-913 例1 方程f(x)=x3-x-1=0 确定其有根区间 解：用试凑的方法，不难发现 f(0)0 在区间（0，2）内至少有一个实根 设从x=0出发,取h=0.5为步长向右进行根的 搜索,列表如下 x f(x) 0 0.5 1.0 1.5 2 + + + + 可以看出，在可以看出，在1.01.0,1.5,1.5内必有一根内必有一根 2021-7-914 用逐步搜索法进行实根隔离的关键是选取步

9、长h 要选择适当h ，使之既能把根隔离开来，工作量 又不太大。 为获取指定精度要求的初值,可在以上隔离根的 基础上采用对分法继续缩小该含根子区间 二分法可以看作是搜索法的一种改进二分法可以看作是搜索法的一种改进 2021-7-915 对分法又称二分区间法,是求解方程(1)的近似根 的一种常用的简单方法。 设函数f(x)在闭区间a,b上连续,且f(a)f(b)0,根 据连续函数的性质可知, f(x)=0在(a,b)内必有实根, 称区间a,b为有根区间。为明确起见,假定方程 f(x)=0在区间a,b内有惟一实根x*。 二分法的基本思想二分法的基本思想: : 首先确定有根区间,将区间 二等分, 通过

10、判断f(x)的符号, 逐步将有根区间缩小, 直至有根区间足够地小, 便可求出满足精度要求的近 似根。 7.2 对分法对分法 2021-7-9 16 取有根区间a,b之中点, 将它分为两半,分点 , 这样就可缩小有根区间； 二分法求根过程二分法求根过程 设方程设方程 f(x)=0 在区间在区间 a,b 内有根内有根, ,二分法就是逐步收缩二分法就是逐步收缩 有根区间，最后得出所求的根。具体过程如下有根区间，最后得出所求的根。具体过程如下: : 2 0 ba x y y=f(x) y=f(x) x* a x1 x* x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2 20

11、21-7-917 对压缩了的有根区间 重复的步骤,即取中点 ,将区间 再分为两半,然后再确定有 根区间 ,其长度是 的二分之一； 如此反复下去,若不出现 ,即可得出一系列有 根区间序列： 上述每个区间都是前一个区间的一半,因此 的长 度: 11 , ba 2 11 1 ba x 11 ,ba 22,b a 11 ,ba 0)( k xf kk babababa, 2211 kk ba , )( 2 1 )( 2 1 11 ababab k kkkk 当k时趋于零,这些区间最终收敛于一点x* 即为所求的根 a x* x0 b ( )f x a1 b1 2021-7-918 每次二分后,取有根区间

12、 的中点 作为根的近似值，得到一个近似根的序列 该序列以根x*为极限 只要二分足够多次(即k足够大),便有 这里为给定精度,由于 ,则 1 11 22 k kk kk ab ab ab 1 * 22 k kk k abab xx kk ba ,)( 2 1 kkk bax , 210k xxxx k xx* kk bax, * 2021-7-919 当给定精度0后,要想 成立,只要 取k满足 即可，亦即当: k xx * )( 2 1 1 ab k 1 2lg lg)lg( ab k 时,做到第k+1次二分,计算得到的 就是满足精度 要求的近似根 。 在程序中通常用相邻的 与 的差的绝对值 或

13、 与 的差的绝对值是否小于来决定二分区间 的次数。 k x k x 1k x k a k b 2021-7-920 例例1 1 求方程f(x)=x3-x-1=0在区间1.0,1.5内 的一 个实根, 使误差不超过0.510-2。 例例2 2 证明方程 在区间2,3内有一个根, 使用二分法求误差不超过0.510-3 的根要二 分多少次？ 证明 令 052 3 xx 52)( 3 xxxf 016)3(, 01)2(ff 且f(x)在2,3上连续,故方程f(x)=0在2,3内至少有 一个根。又 ，当时 时, 故f(x)在2,3上是单调递增函数,从而f(x)在2,3上有 且仅有一根。 23)( 2

14、xxf 3 , 2x0)( x f 2021-7-921 误差限为 只要取k满足 )( 2 1 1 * abxx k k 3 1 10 2 1 )( 2 1 ab k 即可，亦即 3 102 k 97.9 21 10lg3 g k 给定误差限0.510-3 ,使用二分法时 所以需二分10次便可达到要求。 2021-7-922 二分法的优点是不管有根区间a,b多大,总能求 出满足精度要求的根,且对函数f(x)的要求不高,只要 连续即可,计算简单;它的局限性是只能用于求函数 的实根,不能用于求复根及重根,它的收敛速度与比 值为1/2的等比级数相同，不算太快，因此一般在求 方程近似根时，不太单独使用

15、，常用它来为其它方 法求方程近似根提供好的初始值。 2021-7-923 对于一般的非线性方程,没有通常所说的求根 公式求其精确解,需要设计近似求解方法,即迭代法。 它是一种逐次逼近的方法,用某个固定公式反复校正 根的近似值,使之逐步精确化，最后得到满足精度要 求的结果。 迭代法的基本思想迭代法的基本思想 为求解非线性方程f(x)=0的根，先将其写成便于 迭代的等价方程 其中 为x的连续函数)(x )(xx 7.3 迭代法迭代法 -(2) 2021-7-9 24 2021-7-925 得的右端代入任取一个初值,)2(, 0 x )( 01 xx )( 12 xx )( 1kk xx -(3)

16、),2,1 ,0(k 称(3)式为求解非线性方程(2)的简单迭代法简单迭代法 再将 代入式 的右端，得到 1 x)(xx 依此类推, 得到一个数列)( 23 xx 其一般表示 2021-7-9 26 步迭代值为第称为迭代函数称kxx k ,)( 满足使得迭代序列如果存在一点 0 *, k xx *limxxk k 则称迭代法(3)收敛,否则称为发散 -(4) 012 *xxxxO )(xy xy 0231 *xxxxxO )(xy xy 将(2)式表示为 )(xy xy 收敛收敛 2021-7-927 例3.012 3 xx用迭代法求解方程 解: 12 3 xx (1) 将原方程化为等价方程

17、得由迭代法如果取初值),3(,0 0 x * 012 xxxxO )(xy xy 2013 *xxxxxO )(xy xy 发散发散 2021-7-928 12 3 01 xx1 12 3 12 xx3 12 3 23 xx55 0 0 x 显然迭代法发散 3 2 1 x x (2) 如果将原方程化为等价方程 2021-7-929 0 0 x 3 0 1 2 1 x x 仍取初值 3 2 1 7937.0 3 1 2 2 1 x x 3 2 7937.1 9644.0 x2 = 0.9644 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7

18、= 1.0000 依此类推,得 已经收敛,故原方程的解为 0000.1x 迭代法的几何意义 通常将方程f(x)=0化为与它同解的方程 的方法不止一种,有的收敛,有的不收敛,这取决于 的性态,方程 的求根问题在几何上就是确定曲 线y= 与直线y=x的交点P*的横坐标。 )(xx )(x )(xx )(x 对方程f(x)=0可以构造不同的迭代公式, 但迭 代公式 并非总是收敛。那么,当迭 代函数 满足什么条件时，相应的迭代公式 才收敛呢？ )( 1kk xx )(x 2021-7-9 30 2021-7-931 定理1.且满足上连续在设迭代函数,)(bax ;)(,)1(bxabax时当 有且满足

19、存在一正数,10,)2(baxLL Lx|)(| *,)(.1xbaxx o 内有唯一解在方程则 *)(,.2 10 xxxbax kk o 均收敛于迭代法对于任意初值 1 1 * kkk xx L L xx 01 1 *xx L L xx k k 且有误差估计式 1.迭代法收敛的条件 这是事后估计，也就是停机标准。L越小，收敛速度越快 这是事前估计。选取n，预先估计迭代次数 2021-7-932 例4.用迭代法求方程的近似解,精确到小数点后6位 0210 xe x 解: 本题迭代函数有两种构造形式 10 2 )( 1 x e xx )102ln()( 2 xxx |)(| 1 x 10 x

20、e |)(| 2 x x102 10 ,0 x e由于0102x则 2 .0 x 1 10 2 .0 e 10 2 )( 1 x e xx 因此采用迭代函数 ,0时x,10 x e2102x 为有根区间因此2 .0 ,0 5 由于 2021-7-933 0 0 x取初值 10 2 0 1 x e x 1 .0 d1 = 0.1000000 d2 = -0.0105171 d3 = 0.1156e-2 d4 = -0.1265e-3 d5 = 0.1390e-4 d6 = -0.1500e-5 d7 = 0.1000e-6 由于|d7| =0.1000e-0061e-6 因此原方程的解为 x7

21、= 0.090525 *x x1 = 0.1000000 x2 = 0.0894829 x3 = 0.0906391 x4 = 0.0905126 x5 = 0.0905265 x6 = 0.0905250 x7 = 0.0905251 2.迭代法的加速 一个具有实用价值的迭代法，不仅要求它收 敛，而且还要求它收敛比较快。迭代收敛的速度 是指迭代误差的下降速度。在定理1中我们知道L 越小或 迭代法收敛越快。 若迭代过程收敛缓慢，就会增加计算量，因此， 需要设法提高迭代速度。 ,| )(|上越小在bax 2021-7-9 34 当 范围不大时,设 变化不大,其估计值为L, 则有 （1）加速迭代法

22、 设 是根 的某个近似值,用迭代公式校正一次得 又 根据微分中值定理有 k x * x )( 1kk xx )( * xx )()()( * 1 * kkk xxxxxx 其中 ),( * k xx )( * k xx ）（ )( * 1 * kk xxLxx )( 1 11 * kkk xx L L xx 的误差与根近似值 xx k1 2021-7-9 35 令 可见,若将误差值 补偿到 ,则可 得到的比 更好的近似值 1k x )( 1 1kk xx L L 1k x )( 1 11 * kkk xx L L xx )( 1 111kkkk xx L L xx 得到加速迭代公式 )( 1 )( 111 1 kkkk kk xx L L xx xx 2021-7-9 36 例5. 用加速迭代法求方程 在0.5附近的根。 解： 因为在 附近 取L=-0.6，建立如下迭代公式 x ex 5 . 0 0 x 6 . 0 5 . 0 5 . 05 . 0 eex x 仍取