资源描述
第四章 非线性方程的数值解法 非线性方程求根 1根的存在性。方程有没有根？如果有根，有几个根？ 定理 1： 设函数 f (x) 在区间 a, b上连续 ， 如果 f (a) f (b) 0 打 印 结 束 否 是 继续扫描 例 1：考察方程 的含根区间 01)( 3 xxxf x 0 0.5 1.0 1.5 f (x)符号 可见，含根区间为 1, 1.5 4.1 对分区间法 (Bisection Method ) 原理： 若 f(x) Ca, b， 且 f (a) f (b) 0 f (a) f (b)=0 f (a) =0 打印 b, k 打印 a, k 结束 是 是 是 否 否 否 m=(a+b)/2 |a-b|0 打印 m, k a=m b=m 结束 k=k+1 是 是 否 否 输入 ,ba k = 0 例 2 用二分法求 在 (1,2)内的根，要求绝对误差不超过 解 ： f(1)=-50 -(1,2)+ f(1.25)0 (1.25,1.375) f(1.313)0 (1.313,1.375) f(1.344)0 (1.344,1.375) f(1.360)0 (1.360,1.368) 0104 23 xx 210 2 1 f(1.5)0 (1,1.5) nx 1.51 x 364.1 368.1 360.1 344.1 313.1 375.1 25.1 8 7 6 5 4 3 2 x x x x x x x 12 例 3，求方程 f(x)= x 3 e-x =0的一个实 根 。 因为 f(0)0。 故 f(x)在 (0,1)内有根 用二分法解之 ， (a,b） =（ 0,1)计算结果如表： k a bk xk f(xk)符号 0 0 1 0.5000 1 0.5000 0.7500 2 0.7500 0.8750 3 0.8750 0.8125 4 0.8125 0.7812 5 0.7812 0.7656 6 0.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 9 0.7714 0.7724 10 0.7724 0.7729 取 x10=0.7729， 误差为 | x* -x10|=1/211 。 Remark1： 求奇数个根 Find solutions to the equation on the intervals 0, 4， Use the bisection method to compute a solution with an accuracy of 10 7. Determine the number of iterations to use. 0,1, 1.5, 2.5 and 3,4， 利用前面的公式可计算 迭代次数为 k=23. Remark2:要区别根与奇异点 Consider f(x) = tan(x) on the interval (0,3).Use the 20 iterations of the bisection method and see what happens. Explain the results that you obtained. （ 如下图） Remark3:二分法不能用来求重根 f (x) = 0 x = g (x) 等价变换 f (x) 的根 g (x) 的不动点 4.2 单个方程的迭代法 f(x)=0化为等价方程 x=g(x)的方式是不唯一 的 ,有的收敛 ,有的发散 For example： 2x3-x-1=0 xk+1 = g(xk) (3) 321xx(1) 如果将原方程化为等价方程 由此可见，这种迭代格式是发散的 取初值 00 x 3102 1 1xx 3212 1 3xx 3322 1 5 5xx 31 21kkxx 则 迭 代 格 式 为 ： 3 2 1 xx (2) 如果将原方程化为等价方程 00 x 2 103 1 xx 3 2 1 7937.0 3 12 2 1 xx 3 2 7937.1 9644.0 仍取初值 依此类推 ,得 x3 = 0.9940 x4 = 0.9990 x5 = 0.9998 x6 = 1.0000 x7 = 1.0000 已经收敛 ,故原方程的解为 x = 1.0000 同样的方程 不同的迭代格式 有不同的结果 什么形式的迭代 法能够收敛呢 ? 收敛性分析 定义 2 若存在常数 (0 1),使得对一 切 x1,x2 a,b , 成立不等式 |g(x1)-g(x2)| |x1-x2|， (5) 则称 g(x)是 a,b 上的一个压缩映射 ， 称为压缩系数 考虑方程 x = g(x), g(x)Ca, b, 若 ( I ) 当 xa, b 时， g(x)a, b； ( II )在 a,b 上成立不等式： |g(x1)-g(x2)| |x1-x2| 。 则（ 1） g在 a,b 上存在惟一不动点 x* （ 2）任取 x0a, b， 由 xk+1 = g(xk) 得到的序列 xk（ a,b】） 收敛于 x* 。 （ 3） k次迭代所得到的近似不动点 xk与精确不动点 x*有误差估计 式： 定理 4.2.1 * 1 ( 6)1k k kx x x x * 10 ( 7 )1 k kx x x x 3 Fixed-Point Iteration 证明： g(x) 在 a, b上存在不动点？ 不动点唯一？ 当 k 时， xk 收敛到 x* ？ |x*-x|=|g(x *)-g(x)| |x*-x|. 因 0 1，故必有 x=x * 若有 x a,b ,满足 g(x)=x ， 则 |xk-x*|=|g(xk-1)-g(x*)| |x k-1-x*| 2|xk-2-x*| k|x0-x*|0, 令 G(x)=g(x)-x, x a,b， 由条件知 G(a)=g(a)-a0, G(b)=g(b) -b0. 由条件知 G(x)在 a,b 上连续，又由介值定理知 存在 x* a,b， 使 G(x*)=0， 即 x*=g(x*). 3 Fixed-Point Iteration 可用 来 控制收敛精度 | 1 kk xx 越小，收敛越快 (4) |xk-x*|=|g(xk-1)-g(x*)| |x k-1-x*| （ |xk-xk-1|+|xk-x*|） , 故有 |xk-x*| /(1-)|xk-xk-1|. 这就证明了估计式 (6). (5) |xk-xk-1| = |g(xk-1)-g(xk-2)| |x k-1-xk-2| k-1|x1-x0| 联系估计式 (6)可得 |xk-x*| k-1/(1-)|x1-x0|. 即估计式 (7)成立 Remark： 定理条件非必要条件，而且定理 4.2.1中 的压缩条件不好验证，一般来讲 ， 若知道迭代函数 g(x)C 1 a,b ,并 且满足 |g(x)| 1,对任意的 x a,b , 则 g（ x)是 a,b 上的压缩映射 x y y = x x y y = x x y y = x x y y = x x* x* x* x* y=g(x) y=g(x) y=g(x) y=g(x) x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 x0 p0 x1 p1 改进、加速收敛 /* accelerating convergence */ 待定参数法： 若 | g(x) | 1， 则将 x = g(x) 等价地改造为 )()()1()( xxKgxKxKgKxxx 1|)(1|)(| xgKKx求 K，使得 例： 求 在 (1, 2) 的实根。 013)( 3 xxxf )()1(31 3 xgxx 如果用 进行迭代，则在 (1, 2)中有 1|)(| 2 xxg现令 )1(3)1()()1()( 3 xKxKxKgxKx 希望 1|1|)(| 2 KxKx 0 1 2 2 K x ，即 在 (1, 2) 上可取任意 ，例如 K = 0.5， 则对 应 即产生收敛序列。 032 K )1(6123 3 xxx 例题 已知方程 2x-7-lgx 0， 求方程的含根区 间，考查用迭代法解此方程的收敛性。 在这里我们考查在区间 3.5,4的迭代法 的收敛性 很容易验证： f(3.5)0 将方程变形成等价形式： x (lgx+7)/2 (l g ( ) 7 ) 11 () 2 l n 1 0 x gx x 1 g(x)= 2 3 . 5 4m a x | ( ) | 0 .0 6 3 1x gx 由定理 4.2.1知，迭代格式 xk+1 (lgxk+7)/2 在 3.5,4内收敛 局部收敛性定理 定理 4.2.2 设 x*为 g的不动点， g(x)与 g(x) 在 包含 x*的某邻域 U(x*) (即开区间 )内连续， 且 |g(x *)|0，当 x0 x* - ， x*+ 时，迭代法 (3)产生的序列 xk x* - ， x*+ 且收敛于 x*. 证明略（作为练习） We dont know x*,how do we estimate the inequality？ 举例 用一般迭代法求 x3-x-1=0的正实根 x* 3x = x + 1将 方 程 改 写 成 ： 3x) = x+ 1则 迭 代 函 数 为 ： g( 2 3 1x) = 3 x+ 1 g( （ ） 容易得到： g(x) 在包含 x*的某邻域 U(x*) 内 连续，且 |g(x *)|1 *3 kx = x + 1 xk+1因 此 迭 代 格 式 在 附 件 收 敛 例题 用一般迭代法求方程 x-lnx 2在区间（ 2， ） 内的根，要求 |xk-xk-1|/|xk|=10-8 解：令 f(x)=x-lnx-2 f(2)0,故方程在（ 2,4）内至少有一个根 1f ( x ) = 1 0 , 2 x x 又 （ ， ） f ( x ) = 0 2 , 2 * * 因 此 方 程 在 （ ， ） 内 仅 有 一 个 根 x 且 x （ ， ） 将方程化为等价方程： x 2 lnx 1g( x) 2 l nx ( x) |=| | 0. 5 1 , 2 4 x x ， |g （ ， ） 因此， x0（ 2， ）， xk+1 2 lnxk产 生的序列 xk 收敛于 X* 取初值 x0 3.0,计算结果如下： 7 3.146143611 8 3.146177452 9 3.146188209 10 3.146191628 11 3.146192714 12 3.146193060 13 3.146193169 14 3.146193204 k xi 0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6 3.146037143 另一种迭代格式： 1 ( 1 l n ) 1 kk k k xx x x 0 3.000000000 1 3.147918433 2 3.146193441 3 3.146193221 程序演示 由此可见，对同一个非线性方程的迭代格 式，在收敛的情形下，有的收敛快，有 的收敛慢。 定义 1. :设 序列 xk收敛于 x*， 若存在 p 1和正数 c， 使得成立 则称 xk为 p 阶收敛的 特别 , p = 1， 要求 c1, 称线性收敛 ; 1p0，当 x0 x* - ， x*+ (x0 x *)时，由迭代法 (3)产生的序列 xk 以 p阶收敛速度收敛于 x*. Proof: (1)由 g( x*)=0必存在 0，当 x0 x* - ， x*+ U(x)时，由迭代格式 (3)产生的序列 xk收 敛于 x*,并有 xk x* - ， x*+ (2)由泰勒公式有 xk+1=g(xk)=g(x* ） g(x*)(x k- x*)+ +g (p-1) (x*)(xk-x*) p-1/(p-1)! + g (p)(x*+ (xk-x*)(xk-x*) p /p! ， 01. 利用 g在 x*的各阶导数条件及 g(x*)=x*,上式可改写成 ( ) * * * 1 ( ( ) () ! p pk kk g x x x x x x x p (11) (3)由于 g在 x*处 p阶连续可微且 g(p)(x*)0 ， 知必存在 x*的 某邻域 (x*)， 当 xU(x *)时，有 g (p) (x)0. 由于 x*+ (xk-x*) x* - ， x*+ U(x*)， 故 g (p)(x*+ (xk-x*) 0 ， k=0， 1,2, . 可见，当初值 x0 x *时，由 (11)式可推出 xkx * 于是由 (11)式有 * ( ) * *1 * ( ( ) ! p k k p k xx g x x x pxx 上式令 k 取极限 . * ( ) * 1 * () l im 0 ! p k pk k xx gx pxx 即 xk有 p阶收敛速度 .
展开阅读全文