计算方法 非线性方程的数值解法

1、第11次 非线性方程的数值解法 计算方法计算方法 (numerical analysis) 1）非线性方程与方程组的数值解法的概念 2）确定有根区间的方法 2）二分法 3）不动点迭代法及其收敛性 4）牛顿迭代法 5）算法实现 本讲内容 非线性方程与方程组的数值 解法的概念 在科学研究和工程设计中, 经常会遇到非线性方程 f(x)=0 (5.1) 的求根问题，其中f(x)为非线性函数。 如果f(x)是多项式函数，则称为代数方程， 否则称为超越方程（三角方程，指数、对数方程等）。 方程f(x)=0的根, 亦称为函数f(x)的零点。 y=f(x) y x 0)(a0axaxaxa n01 1n 1n

2、 n n 本章将介绍常用的求解非线性方程的近似根的几 种数值解法 当n1时,方程显然是非线性的。 代数方程 一般稍微复杂的3次以上的代数方程或超越方程, 很难甚至无法求得精确解。 通常方程根的数值解法大致分为三个步骤进行： a) 判定根的存在性。即方程有没有根？如果有根， 有几个根？ b) 确定根的分布范围。即将每一个根用区间隔离 开来，这个过程实际上是获得方程各根的初始 近似值。 c) 根的精确化。将根的初始近似值按某种方法逐 步精确化，直到满足预先要求的精度为止 y=f(x) y x() home 确定有根区间的方法 7.1.1 确定有根区间的方法 为了确定根的初值，首先必须圈定根所在的范

3、围， 称为圈定根或根的隔离。 在上述基础上，采取适当的数值方法确定具有一 定精度要求的初值。 求方程根的问题，就几何上讲,是求曲线 y=f (x) 与x轴交点的横坐标。 例1. 怎样确定方程 x3 -3 x2 + 2x = 0 的有根区间？ 讨论：这个3次方程最多有3个实根，可能的情况 1）有3个实根 2）有1个实根，2个复根 事实上：方程可以通过分解因式，改写为 x(x-1)(x-2) = 0 从而此方程有3个实根x=0, x=1, x=2 而大多数方程都不可能这样凑巧，能很快计算出 根，因此只能首先确定根的存在区间，然后利用 一些方法求出根的近似值。 设f (x)为区间a, b上连续, 由

4、此可大体确定根所在子区间，方法有： (1) 画图法 (2) 逐步搜索法 a) 由介值定理知道如果f (a)f (b)0 , 则f(x)=0 在a, b中至少有一个实根。 b) 如果你发现f (x)在a, b上还是单调递增或递减， 则仅有一个实根（从而可以在该区间内利用近 似方法求解）。 y=f(x) y x() (1) 画图法 (使用matlab)画出连续函数y = f (x)的略图，从而看 出曲线与x轴交点的大致位置。 可将f (x) = 0分解为 1(x)= 2(x)的形式，y= 1(x)与 y= 2(x)两曲线交点的横坐标所在的子区间即为含根区 间(区间越小越好)。 例如 xlnx-1=

5、 0 可以改写为lnx=1/x. 分别绘制曲线y=1/x 和y=lnx,观察得知 有根区间为 （2， 3） 023 y x y= 1/x y= lnx (2) 搜索法 假设在a=x0, x5=b上定义的连续函数f(x)。从 x0=a出发,以步长h=(b-a)/n(n是正整数),在a, b 内取定节点: xi=x0ih (i=0,1,2,n), 从左至右检查f (xi)的符号,如发现f(xi )f(x0)0，则 得到一个缩小的有根子区间xi-1,xi。 有根子区间：x0, x1, x2, x3, x4, x5 y=f(x) y x x0 x1 x2 x3 x5 x4 例2. 方程f(x)=x3-

6、x-1=0，确定其有根区间。 可以看出，f(x)在(1.0, 1.5)内必有一根。 解：不难发现：f(0)0。可断定方程在区间 (0，2)内至少有一个实根。用搜索的方法，从x=0出发, 取h=0.5为步长向右进行根的搜索,列表如下: 问题：方程是三次方程，除了这一个根之外，是否 还有其它的根呢？ x f(x) 0 0.5 1.0 1.5 2 + + f(x)=x3 -x 1, f(x) = 3x2 -1 = 0， 解得x1 = -3/3, x2 = 3/3, f(x)在（-， -3/3）单调增加，在 （-3/3， 3/3）单调减少，在 （3/3， +）单调增加 f(-3/3) f(-0.577

7、)0是极大值， f(3/3) f(0.577)1.5后，f（x）0， x0.577, f(x) 0 f(x)在(0.577, +)单调增加，所以在(1.0, 1.5)内 单调增加。综合上述，f(x)=0仅仅有一个实根。 例3. 方程f(x) = x3-4.2x2 + 4.88x -1.344 = 0，确 定其有根区间。（此方程有根0.4， 1.4，2.4） x f(x) 0 0.5 1.0 1.5 2 2.5 3 + + - - + + 可以看出，f(x)分别在(0, 0.5)，(1， 1.5)与(2, 2.5) 内分别各有一实根。 解：不难发现：f(0)0。可断定方程在区间 (0，3)内至少

8、有一个实根。用搜索的方法，从x=0出 发, 取h=0.5为步长向右进行根的搜索,列表如下: a) 用逐步搜索法进行实根隔离的关键是选取步长 h； b) 要选择适当h ，使之既能把根隔离开来，工作 量又不太大； c) 为获取指定精度要求的初值,可在以上隔离根的 基础上采用对分法继续缩小该含根子区间； d) 为了隔离出f(x)=0的所有的根，必要时，可以 使用求导数的方法，求出y=f(x)的单调区间。 注意： home 二分法 7.1 二分法 二分法是求解方程f(x)= 0的近似根的一种常用的简 单方法。 设函数f(x)在闭区间a, b上连续,且f(a)f(b)0,根据 介值定理可知, f(x)=

9、 0在(a, b)内必有实根,称区间a, b为有根区间。 本节假定方程f(x)=0在区间a,b内有唯一实根x*。 二分法基本思想: 先确定有根区间,将区间二等分, 通 过判断f(x)的符号, 逐步将有根区间缩小, 直至有根区 间足够地小, 便可求出满足精度要求的近似根。 取有根区间a, b之中点, 将它分为两半,分点 , 7.1.2 二分法求根过程 条件：设f(x)在区间a, b上连续，f(a)f(b) 0,且方 程f(x)=0在区间a, b内有唯一实根。 2 ba x 0 a) 在a, x0上，观察f(a)f(x0)0是否成立，若成 立，则a, x0是有根区间； b) 否则，必有f(x0)f

10、(b)0,即x0, b是有根区间。 将压缩了的有根区间记为a1, b1 ,其长度是a, b的1/2. 如果f(x0)=0，则已经找到了根，过程停止。否则， 二分法的具体过程如下： y x a b y=f(x) 1) f(a)f(b) 0, 有根区间a, b; 2) f(a)f(m1)0,有根区间m2, m1; 4) f(m2)f(m3)0,有根区间m3, m1; 5) m1m2 m3 对压缩了的有根区间 施行同样的手法, 即取中点 , 将区间 再分为两半,然 后再确定有根区间 ,其长度是 的1/2 b,a 11 2 ba x 11 1 b,a 11 b,a 22 b,a 11 当k时趋于零,根

11、据区间套定理，这些区间最终收敛于 一点x*，即为 所求的根 。 0)f(xk kk2211 b,ab,ab,aba, a)(b 2 1 )a(b 2 1 ab k 1k1kkk 如此反复进行,若所有 ,则得有根区间序列： 上述每个区间都是前一个区间的一半,因此： 每次二分后,取有根区间 的中点 作为根的近似值，得到一个近似根的序列 1k 1k1k kk k * 2 ab ab 2 ab |xx| b,a kk )b(a 2 1 x kkk ,x,x,x,x k210 2 ab xx 1k k * b,ax kk * 记其极限为x*，则必有 。注意到 对于任意的给定精度0,可以取k足够大，使得

12、近似根数列的性质 便有： 0)f(x * k a k b k x x 例4. 求方程f(x)=x3-x-1=0 在区间1.0, 1.5内的 实根, 使误差不超过0.510-2。 2k1k k * 2 1 a)(b 2 1 xx 2 2k 10 2 1 2 1 亦即 21k 102 6.64 0.301 2 1g2 2lg10 10log1k 2 2 所以k5.64,需二分6次便可达到要求。 只要取k满足 解：给定 0.510-2 ,使用二分法时误差限为： 方程f(x)=x3-x-1=0，求根过程，区间：1.0, 1.5 f(1)=-10 x1=1.25, f(x1)0; 有根区间1.25, 1

13、.375 x3=1.3125, f(x3)0; 根区间1.3125, 1.34375 x5=1.328125, f(x5)0; 根区间1.3125, 1.328125 x6=1.3203125, f(x6)0; 根区1.3203125, 1.328125 x7=1.3242187 例5. 证明方程 在区间2, 3内仅有一 个根 , 使用二分法求误差不超过0.510-3 的根要二 分多少次？ 052xx 3 016f(3)0,1f(2) 又 2,3x0,23x(x)f 2 52xxf(x) 3 证明 令 则f(x)在2, 3上连续，且 根据介值定理，方程f(x)=0在2,3内至少有一个根。 故f

14、(x)在2, 3上是单调递增函数, 从而f(x)在2, 3 上有且仅有一根。 误差限为 a)(b 2 1 xx 1k k * 3 1k 10 2 1 a)(b 2 1 即可，亦即 3k 1029.97 1g2 3lg10 k 所以需二分10次便可达到要求。 只要取k满足 给定误差限 0.510-3 ,使用二分法时 不管有根区间 多大,总能求出满足精度 要求的根, 对函数f(x)的要求不高,只要连续即可,计算亦简 单; 收敛速度与比值为 1/2的等比级数相同。 ba, 二分法的优点 只能用于求函数的实根,不能用于求复根及重根. 二分法的局限性 home 不动点迭代法及其收敛性 方程的迭代解法既可

15、以用来求解代数方程，也 可以用来解超越方程，但是仅限于求方程的实 根。 运用迭代法求解方程的根应解决以下两个问题： 确定根的初值; 将进一步精确化到所需要的精度。 7.2 不动点迭代法及其收敛性 迭代法是一种逐次逼近的方法,用某个固定公式 反复校正根的近似值,使之逐步精确化，最后得 到满足精度要求的结果。 7.2.1 迭代法的基本思想 为求解非线性方程f(x)=0的根，先将其写成便于 迭代的等价方程 (x) (x)x 其中 为x的连续函数。 (5.3) 迭代法的一般表示： 0,1,2,k，)(xx k1k 式(5.4)称为求解非线性方程的简单迭代法。 (5.4) 如果由迭代格式 产生的序列 收

16、敛,即 xn)(xx k1k * n n xxlim 则称迭代法收敛。 实际计算中当然不可能也没必要无穷多步地做下 去, 对预先给定的精度要求，只要某个k满足： |xx| 1kk 即可结束计算并取 k * xx 当然，迭代函数 的构造方法是多种多样的。(x) 例6. 用迭代法求方程 在 x=1.5附近的一个根。 01xx3 3 1 1x)(xx 相应地可得到两个迭代公式 3 k1k 1xx 如果取初始值 ，用上述两个迭代 公式分别迭代，计算结果： 1.5x 0 解 将方程改写成如下两种等价形式 1x)(xx 3 2 1xx 3 k1k kxk 0 1 2 3 4 5 6 7 1.5 1.357

17、21 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 1.5 x取初值： 2,. 1, 0,k , 1x x(1) 0 3 k1k 此迭代法收敛此迭代法发散 1.5取初值x 0,1,2,.k 1,x x(2) 0 3 k1k kxk 0 1 2 3 4 5 6 7 1.5 2.375 12.4 1905.62 7.2.3 迭代法收敛的条件 0,1,2,.k),(xx k1k (x) 对方程f(x)=0可以构造不同的迭代公式, 但迭代公式并非总是收敛。 那么,当迭代函数 满足什么条件时，相应的 迭代公式才收敛呢？ 即使迭代收敛时，我们也不可能迭代无

18、穷次，而 是迭代有限次后就停止，这就需要估计迭代值的 误差，以便适时终止迭代。 定理1，2 设函数 在a,b上具有连续的一阶 导数, 且满足 （1）对所有的xa, b 有 （2）存在 0 l 1 ,使所有的xa,b有 (x) b(x)a l|(x)| (x)x * x ba,x 0 )(xx k1k * x 1kkk * xx l1 l xx 01 k k * xx l1 l xx 则方程 在a, b上的解 存在且唯一。 对任意的 ，迭代过程 均收敛于 。并有误差估计式 上机计算，用 此式估计误差 手动推导，给 出迭代次数k x y (x)y a b a b (x)y 图形比较平缓 迭代之后的

19、y值也 在a, b内 )(xx k1k xy (x) y和x y 一定有交叉点，故方程 一定有解。 从图中可以看出，曲线 (x)x 例7. 对方程 ，构造收敛的迭代格 式，求其最小正根，计算过程保留4位小数。 024xx 5 045x(x)f 4 1,21，x 4 5x |(x)| 4 解：易知1,2是方程的有根区间, 且在此区间内 因此对应等式(1)的迭代公式不满足收敛条件。 故原方程在1,2有且仅有一根。试构造等式(1)： 4 2x (x)x 5 (1) 1,2x10.2 2)(45 4 2)(4x5 4 (x) 5 4 5 4 因此，对应等式(2)的迭代公式满足收敛条件。 现在以另外一种

20、方式构造等式（2） 5 24x(x)x （2） 5 24x(x)x kxk 0 1 2 3 4 5 1.5 1.5157 1.5180 1.5184 1.5185 1.5185 1.5取初值x 0 1.9取初值x 0 kxk 0 1 2 3 4 5 课堂练习 home 1.9取初值x 0 kxk 0 1 2 3 4 5 1.9 1.5720 1.5265 1.5197 1.5187 1.5185 牛顿迭代法 用迭代法可逐步精确方程 根的近似值。 但必须要找到 的等价方程 如果 选得不合适,不仅影响收敛速度,而且 有可能造成迭代格式发散。 问题：能否找到一种迭代方法,既结构简单,收敛 速度快,又

21、不存在发散的问题。这就是本节要介 绍的牛顿迭代法。 7.4 牛顿迭代法 0f(x) 0f(x)(x)x (x) 7.4.1 牛顿迭代法的基本思想 牛顿迭代法是一种重要和常用的迭代法, 它的 基本思想是将非线性函数f(x)逐步线性化, 从 而将非线性方程 f(x)=0 近似地转化为线性方 程求解。 牛顿迭代公式的推导： 设f(x)有2阶连续的导数，对于方程 , 设其近 似根为 , 则函数f(x)可在 附近作泰勒展开： 0f(x) k x k x 忽略高次项,用其线性部分作为函数f(x)的近似， )x)(x(xf)f(xf(x) kkk 设 的根为 ,则有 ,即 0f(x) * x0)f(x *

22、0)x)(x(xf)f(x k * kk )(xf )f(x xx k k k * 2 kkkkk )x)(x(xf 2 1 )x)(x(xf)f(xf(x) 0,1,2,.k, )(xf )f(x xx k k k1k 于是得到著名的牛顿迭代公式： 将右端视为 ,即 是比 更接近于 的近似值。 1k x 1k x k x * x 评论：牛顿迭代法不属于不动点迭代法。 7.4.3 牛顿迭代法的收敛性 定理2.4 设 是方程 的单根, 且f(x)在 的某邻域内有连续的二阶导数, 则牛顿法在 附近局部收敛。 * x0f(x) * x * x )(xf2 )(xf xx xx lim e e lim

23、 * * 2 k * 1k * k 2 k 1k k 评论：需要f(x)有2阶连续的导数。 此时，牛顿迭代法至少二阶收敛,并且有： 例8. 用牛顿迭代法求 x=e-x的根，使得=10-4 n x n n n x x n n1n x1 ex x )x(1e 1ex xx n n n 解：1)(xe(x)f1,xef(x) xx f(x)在区间（-1， 1）连续，并且 f(-1)0， 从而f(x)=0必然有解。 f”(x) = ex(x+2)在（-1， 1）连续，因此可以使 用newton迭代法求解方程。建立迭代公式： kxk 0 1 2 3 0.5 0.57102 0.56716 0.56714

24、 取初值x0=0.5 x3 - x2 =-0.00002 满足要求。 n x n n n x x n n1n x1 ex x )x(1e 1ex xx n n n 取初值x0=0 kxk 0 1 2 3 4 5 课堂练习 kxk 0 1 2 3 4 5 6 0.0 1 0.68394 0.57745 0.56723 0.56714 0.56714 取初值x0=0.0, x6 - x5 = 0.00000，满足要求。 n x n n n x x n n1n x1 ex x )x(1e 1ex xx n n n 思考题： xex -1 = 0 是否只有一个根？ 解：f(x) = 3x2 - 8.4x + 4.88 例9：用牛顿迭代法分别求方程 f(x) = x3-4.2x2 + 4.88x -1.344 = 0， 在区间（0，1），(1, 2)和(2, 3)中的根。 kxk 0 1 2 3 4 5 0.1 0.32381 0.39261 0.39992 0.400000 0 0.400000 0 x0 = 0.1 课堂练习：用newton迭代法求方程在其它两个区间 内的根。 建立迭代公式： xn+1 = xn - (xn 3-4.2 xn 2 + 4.88 xn - 1.344)/(3 xn 2 - 8.4