《数值计算方法第二章.docx》由会员分享，可在线阅读，更多相关《数值计算方法第二章.docx（19页珍藏版）》请在三一办公上搜索。
1、第二章非线性方程数值解法在科学计算中常需要求解非线性方程/(x)= 0(2.1)即求函数f (x)的零点.非线性方程求解没有通用的解析方法，常采用数值求解算 法.数值解法的基本思想是从给定的一个或几个初始近似值出发，按某种规律产 生一个收敛的迭代序列x 卬，使它逐步逼近于方程(2.1)的某个解.本章介绍非 线性方程实根的数值求解算法：二分法、简单迭代法、Newton迭代法及其变 形，并讨论它们的收敛性、收敛速度等.2.1二分法一、实根的隔离定义2.1设非线性方程(2.1)中的f(x)是连续函数.如果有x*使f(x*) = 0，则 称x*为方程(2.1)的根，或称为函数f (x)的零点；如果有f
2、 (x) = (x-x*)mg(x)，且g(x) 在x*邻域内连续，g(x*)尹0，m为正整数，则称x*为方程(2.1)的m重根.当m = 1 时，称x*为方程的单根.非线性方程根的数值求解过程包含以下两步(1) 用某种方法确定有根区间.称仅存在一个实根的有根区间为非线性方程 的隔根区间，在有根区间或隔根区间上任意值为根的初始近似值；(2) 选用某种数值方法逐步提高根的精度，使之满足给定的精度要求.对于第(1)步有时可以从问题的物理背景或其它信息判断出根的所在位置，特 别是对于连续函数f (x)，也可以从两个端点函数值符号确定出有根区间.当函数f (x)连续时，区间搜索法是一种有效的确定较小有
3、根区间的实用方 法，其具体做法如下设a,b是方程(2.1)的一个较大有根区间，选择合适的步长h = (b-a)/n，x = a + kh，(k = 0,1,n) .由左向右逐个计算f (x )，如果有f (x )f (x ) 0知f (x)为(-8,8)上的单调递增函数，进 而f (x)在(-8,8)内最多只有一个实根.经计算知f (0) 0，所以f (x) = 0 在区间0,2内有惟一实根.尤=1.5如果希望将有根区间再缩小，可以取步长h = 0.5，在点尤= 0.5,计算出函数值的符号，最后可知区间1.5,2内有一个实根.二二分法二分法是求非线性方程实根近似值的最简单的方法.其基本思想是将
4、有根区 间分半，通过判别函数值的符号，逐步缩小有根区间，直到充分逼近方程的根， 从而得到满足一定精度要求的根的近似值.设f (x)在区间a,b上连续，f (a)f (b) 0，且方程(2.1)在区间(a,b)内有惟一实 根x* .记a = a，b = b，中点x = (a +b )/2将区间a ,b 分为两个小区间a ,x 和 x ,b ，计算函数值 1 f (x )，根据如下3种情况确定新的有根区间：1 11 1(1)如果f (x1) = 0，则是所要求的根；(2) 如果f (a1)f (x1) 0，取新的有根区间a2,b = a气；(3) 如果f (x ) f (b ) 0，取新的有根区间
5、a ,b = x ,b .11、.2211.新有根区间a ,b 的长度为原有根区间a ,b 长度的一半.对有根区间a ,b 221122施以同样的过程，即用中点x = (a + b )/2将区间a ,b 再分为两半，选取新的有2.2222根区间，并记为a ,b ，其长度为a ,b 的一半(如图2.1所示). 3322a, b = a , b d a , b d d a , b d .11_22. k k其中每个区间的长度都是刖一个区间长度的一半，因此a ,b 的长度为b - a = 2 (b - a)由 x* g a ,b 和 x = (a + b )/2，得 k kk k kx -x* -2
6、(b -a ) = (b-a)当k TS时，显然，有x x* .总结得到如下收敛定理:定理2.1设f (x)在隔根区间a, b上连续，且f(a)f(b) 0，则由二分法产生的 序列气广。收敛于方程(2.1)在a,b上的根x，并且有误差估计|x 一 x* 2-(b 一 a) (k = 1,2,)(2-2)设预先给定根x*的绝对误差限为，要求|x-x*|&，只要上(b-a) (2.3)ln2取k为大于(ln(b-a)-ln8)/ln2的最小整数.近似值.注：由于舍入误差和截断误差存在，二分法中的判断f (x ) = 0几乎不可能满足，取而代之为判断条件If (x )1 8为根近似值的函数值允许误差
7、限.0总结以上内容，给出如下算法算法2.1 (二分法)输入输出Step 1Step 2Step 3Step 4Step 5例2.2 0，故 f (x) = 0在1,2上有惟一实根x* .确定循环次数为k = 11，利用二分法计算结果见 表 2.1.此时气是方程(2.1)的满足精度要求的根利用浮点运算不可能精确计算函数值，k 8。，其中端点a,b、根的绝对误差限8、根近似值的函数值允许误差限80;近似解c或失败信息；用公式(2.3)计算最大迭代次数k ;对n = 1,.,k循环执行Step 35；c = (a + b)/2，计算 f (c)；若|f (c)|8，则输出 c，end；若 f (c)
8、f (b) 0，则 a = c，否则 b = c .用二分法求 f (x) = x3 + 4x2 -10 = 0 在1,2 上的根x*的近似值，要求|x - x*k有根区间a ,b xf (x )k kkk11.0,2.01.52.37521.0,1.51.25-1.79689531.25,1.51.3750.162109441.25,1.3751.3125-0.848388751.3125,1.3751.34375-0.350982761.343725,1.3751.359375-0.0964088表2.1二分法计算结果71.359375,1.3751.36718750.032355881.
9、359375,1.36718751.3632813-0.032150091.3632813,1.36718751.36523440.0000720101.3632813,1.36523441.36425785-0.0160460111.36425785, 1.36523441.364746125-0.0079887二分法具有如下特点(1) 优点：计算简单，对函数f的光滑性要求不高，只要它连续，且在两端 的函数值异号，算法收敛就可以保证；(2) 缺点：只能求单实根和奇数重实根，收敛较慢，与1/2为公比的等比级数 相同.当函数f(x)连续时，方程(2.1)的实重根可转换为也=0的实单根. f (x
10、)一般在求方程根近似值时不单独使用二分法，而常用它为其它数值方法提供 初值.2.2简单迭代法简单迭代法是求解非线性方程根的近似值的一类重要数值方法.本节将介绍 简单迭代法的基本思想、收敛条件、收敛速度以及相应的加速算法.一、简单迭代法的基本思想简单迭代法采用逐步逼近的过程建立非线性方程根的近似值.首先给出方程 根的初始近似值，然后用所构造出的迭代公式反复校正上一步的近似值，直到满 足预先给出的精度要求为止.在给定的有根区间也,瓦上，将方程(2.1)等价变形为x = 9 (x)(2.4)在也,瓦上选取x0作为初始近似值，用如下迭代公式xk+广xk)(k = 0,1,2,)(2-5)建立序列x g
11、 .如果有lim x = x*，并且迭代函数9 (x)在x*的邻域内连续，对式 k k = 0k(2.5)两边取极限，得jx* = 9 (x*)因而x*是(2.4)的根，从而也是(2.1)的根.称9(x)为迭代函数，所得序列x g为 迭代序列.将这种求方程根近似值的方法称为简单迭代法，简称迭代法k=0例2.3试用方程f (x) = x3-x-1 = 0的不同形式的变形建立迭代公式，并试 求其在1.5附近根的近似值.利用方程的变形建立如下4种迭代公式取初值x0，X+1 = 31+X，X = X 3 1=1.5k公式(1)公式(2)公式(3)公式(4)01.51.51.51.511.35722.3
12、751.290991.937521.3308612.39651.332144.1053531.325881904.011.3231336.148241.324936.90244 x1091.3250623634.751.324763.28857 xm1.324646.60124 X101261.324723.55651 X10881.324731.43829 X103871.324714.49856 X102651.324711.4877 X10U481.32471inf1.32471inf迭代计算，结果见表2.2.表2.2迭代法计算结果例2.3表明非线性方程的不同等价形式对应不同的迭代过程，
13、从某一初值出 发，有的迭代收敛快，有的收敛慢，甚至不收敛.那么迭代函数9(x)满足什么条 件时才能保证迭代序列收敛？迭代序列x g的误差如何估计？怎样才能建立收敛k k=0速度快的迭代公式？定理2.2若函数中在区间,上具有一阶连续导数，且满足条件 对任意x e a, b，有中(x) e a,b； 存在常数 L : 0 L 1，使得对任意x e a,b有b，(x)| L成立.则方程x = 9(x)在a,b上有惟一实根x*对任意r e a,b，迭代公式(2.5)收敛，且lim x = x .0k(3)迭代公式(2.5)有误差估计式kkL(2.6)x 一 x* x 一 xk1 - L kk-11(2
14、.7)(4) lim k+i=中(x*)5 X *k证明 (1)构造函数g (x) = X f (x)，(2.8)由条件知g色)=a f (a) 0，因此g(x) = 0在a,b上至少存在一个实根，又由条件知当x e a,b时，g (x) = 1-时(x) 1 - L 0，所以 g(x) = 0 在a, b内存在惟一实根,即 x =中(x)在a,b内存在惟一实根，记为x* -(2)由x e a, b及条件知，x e a, b (k = 1,2,)，并且有x =中(x )， 0kk+1kX* =中(X* )， 二者作差，并由微分中值定理得+x一 x*=9(x) 9(x*) =。(&)(x一 x*
15、)(k= 1,2,)(2.9)其中，介于气与x*之间.结合条件，得kk|x -x* l|x -x*|(k = 1,2,)(2.1。)反复递推，有k+1k0 |x故 limx = x*T8 k(3)由式(2.10)得x* I L|x x* | L |x. x* Lk+1x X* I，(k = 1,2，)从而I = |x - X + Xx*| |x -X:|+ 一 X* |xk+1x | + L|x - x*(2.11)又由于lx X | = 9(X ) 9(X )1=90 )(X X )|k+1 kkk1kkk1 l|x - xI(k = 1,2,)(2.12)其中气介于气和X*之间.综合式(2
16、.11)及式(2.12)得误差估计|x - x* | L1 uXkXk-1I l|x -x由式(2.12)反复递推， k 并代入式(2.6)得误差估计lx x* L x x | 0)以及小 于1的正数l，使得V()连续且M)L 1 .则对任意GU(*,5)，迭代 =()收敛.0kr1证南 由9()在U(*,5)内连续，且有()1 L 1，则对任意e U(*,5)，有|平()*| =()甲(*)| = |甲0*)| *| L5 0和实为刻画迭代法收敛速度的快慢，引进收敛序列的收敛阶概念. 定义2.2设迭代序列 g收敛到*，elim , k r1 = cp数p 1，使得I =0(2.13)称 g为
17、线性收敛的，此时要求 .收敛到*越快.kTs e k -则称序列 +s是p阶收敛的.当p = 1时，0 c 1=为超线性收敛.p越大，序列 +S收敛到*越快.c称为渐进常k k=0数，c越小，收敛越快.所以迭代法的收敛阶是对迭代法收敛速度的一种度量.显然，由定理2.2(4)知，当(*)尹0时简单迭代法线性收敛，渐进常数c = (*)1 .算法2.2 (简单迭代法)输入初始值、容许误差8 ；输出 近似解；或失败信息；Step 1 对n = 1, ,m循环执行Step 23；Step 2 =()；Step 3 若| 02ln10 x中(3) r 3.74，中(4) r 3.80，所以x e 3,4
18、， 知 中(x) 在区间3,4内仅有一根.又当 x e 3,4时，中(x) e 3,4-,图2.2函数y = 2x-7和y = lgx的图形因为 L = max |甲(x)|*(3) r 0.07，所以对于一切 x e 3,4有3.5 x 4,(x)| V(3) r 0.07 1由定理2.2知，迭代法收敛.(3)迭代计算.取x0 = 4.0，有x =3.801030，x =3.789951，x =3.789317，x =3.7892801234因为 Ix4-x3l - X 10-31 二 7， 所以方程的最大根x* r x4 =3.789280 .三、迭代法的加速对于收敛的迭代序列，理论上迭代
19、次数足够多时，就可以使计算结果满足任 意给定的精度要求.但在应用中，有的迭代过程收敛极为缓慢，计算量很大，因 此研究迭代格式的加速方法是非常必要的.1.线性收敛序列的Aitken加速法limk Sxkx*x - x*设xJ+七是一个线性收敛的序列，极限为x*.即有小于1的正数c使得卜面介绍Aitken加由于它线性收敛，误差减少的速度较慢，值得采用加速技术. 速法.对充分大的k，有X- X*X- X*x - X*X - X*，由上面两式得kX一 X*X一 X*X - X*X一 X*(X - X )2解得X* 牝*k*k + 2 kT1 = X krlkX 2 x + xk X 2 x + Xk
20、+2k +1kk + 2k + 1k+利用上式右端的值可定义另一序列(y g，即得Aitken加速公式 k k=0(2.14)(X X )2它仍然收敛到X *，但收敛速度更快.证2明请蓼考文献19.2. Steffensen 迭代法Aitken加速方案是对任意线性收敛序列x g构建的，并不限定x g如何获 k k=0k k=0得.将Aitken加速方法用于简单迭代法产生迭代序列时，得到著名的Steffensen 迭代法，具体迭代公式如下S =9 (xk)(2.15)t =9 (s)(k = 0,1,2,)X = x - k+1k t 2s + x或者直接写成x = x (9(x一： )2k+1
21、 k 9 (9 (x ) 29 (x ) + x(k = 0,1,2,)k kk_ k 可以证明Steffensen迭代法在一定的条件下与原简单迭代法的迭代序列具有相同 的极限，但Steffensen迭代法收敛速度更快，可以达到二阶收敛.证明请参考文 献19.例25 对例23用Steffensen迭代法求方程根的近似值，要求lx 一 X I 0，当x G U(x*,8) = x* -8,x* +8时，Newton法产生的序列x加至少二阶收 敛.0*=0证明(1) Newton法迭代函数的导数为f (x) f(x)f(x)2又中(x*) = 0，一定存在x*的某个8闭邻域U(x*,8)，显然，中
22、(x)在x*邻域上连续. 当 x G U(x*,8)时，有Ip (x)k L 0 -(c)(d)图2.4定理2.5的几何解释证明满足定理条件(1)共有4种情形，如图2.4所示.下面仅以图2.4(a )情况进行证明，此时满足对任意 x e a,b有，f(x) 0，f(x) 0，初值 x x* -首先用数学归纳法证明x加有下界x*.0当k = 0时，x x*成立. 假设k = n时，0不等式x.x*成立.将f (x*)在x处作一阶Taylor展开，得f (x*) = f (x ) + f(x )(x* -x ) + f E)(x* -x )2 = 0, & e (x*,x ) nnn 2nnn于是
23、又由Newton迭代公式，有x = x W-马(x* - x )2n f (x ) 2f (x ) nnnx* = x - f n ) (x* - x )2(2.20)式(2.20)右端的第二项大于零，因此工】 x* .由数学归纳法知x x*， (k = 0,1,2,)其次证明单调递减.由 f，(x) 0， x x*， f (x*) = 0 知，f (x ) 0，f(x ) 0，于是 Newton 迭代公 式(2.16)的第二项大于零，从而kkx x故迭代序列x加单调减少.山序列%：单调减少有下界x*，它必有极限，记为x，它满足x* x x0，进而 有x e a, b .对x = x -4两端
24、取极限，并利用f (x)，f(x)的连续性，得 k+1 人 f(x ) kf ()=0.结合函数f (x)在a,b上的单倜性知x = x* 因此，Newton法产生的迭代序列加单调收敛于x*，利用式(2.20)及式(2.19)知该Newton迭代序列二阶收敛.=0算法23 (Newton迭代法)输入初始近似值x、容许误差8 ；输出 近似解x1或失败信息；Step 1 对 n = 1,., m 循环执行 Step 23；Step 2 x = x - f (x )/f(x )；Step 3 若|x-x l8，则输出x1，end；否则x = x，转向step2.例2.6利用非线性方程x2 -3 =
25、0的Newton迭代公式计算&的近似值，使得 lx - x 1 0 .0(2)判断收敛性_在区间(0,+8)内，f(X)= 2X 0，f(X) = 2 0，当选取初值X G心,+3)时，存 在足够大的M，使得X。e T,M .由定理2.5知，该迭代公式产生的迭代序列 =当选取初值X0 e(0,73)时，1 /. 3、天x =成(x + ) 3 .这样，从X起，以后的X (k 2)都大于 0都收敛.(3)取初值X = 2，迭代计算，结果见表2.4.表2.4 Newton法计算结果nxX 一 Xnnn-10211.752.5 x10-12 1.7321429 1.7857143 x10-23 1.
26、73205089.2047128 x10-441.73205082.4458500 x10-8_从表2.4可见，迭代4步后已经满足精度要求，精确解 V3 = 1.7320508075688-.三、Newton迭代法的变形Newton迭代格式构造容易，迭代收敛速度快，但对初值的选取比较敏感， 要求初值充分接近真解，另外对重根收敛速度较慢(仅有线性收敛速度)，而且 当函数复杂时，导数计算工作量大.下面从不同的角度对Newton法进行改进.1 Newton下山算法Newton迭代法的收敛性依赖于初值 x的选取，如果x偏离x*较远，则 Newton迭代法有可能发散，从而在实际应用中选出较好的初值有一定
27、难度，而 Newton下山法则是一种降低对初值要求的修正Newton迭代法.方程(2.1)的根X*也是If (X)|的最小值点，若把If (X)|看成f (X)在X处的高度，则 X*是山谷的最低点.若序列X 3满足单调性条件If (X：+1)l 2)重根，并且存在函数g(X)，使得有f (x) = (x - x*) mg (x), g (x*)尹 0(2.23)式中g(x)在x*的某邻域内可导，则Newton迭代函数一，、f (x)(x x*)mg (x)(x x*)g (x)中(x) = x = x = x ，f(x)m( x x* )m1 g (x) + (x x* )m g(x)mg (
28、x) + (x x*) g(x)(x x*) g (x)x x*(x*) = lim 中 M 34 = lim mg (x) + (x - x*) g，( x)x T x*x x*x T x*g (x)其导数在x*处的值x - x*1=lim 1 = 1 x T x* mg (x) + (x x*) g(x)m所以05(x*) 1，由定理2.2知Newton迭代法此时只有线性收敛速度.为了 加速收敛，可以采用如下两种方法方法一 令|1 (x)=也，则x*是方程Mx) = 0的单根，将Newton迭代函数修 f (x)改为v (x) = x-些=x 口 (x) f (x)2 f (x) f(x)
29、因此有重根加速迭代公式f (x )f(x )气+1 = T f (x )2 f (x ) f (x )(k = 0,1,2, .)kk k(2.24)它至少二阶收敛.方法二 将Newton迭代函数改为两、f (x)中=xf)这时中(x*) = 0，由此得到加速迭代公式x = x - m f:k ；(k = 0,1,2,)(2.25)3割线法kNewton法每步需要计算导数值f x).如果函数f比较复杂时，导数的计 算量比较大，此时使用Newton法不方便.为了避免计算导数，可以改用平均变化率f (号一f (气/替换Newton迭代公式 x 一 x中的导数f(x )，即使用如下公式人Ikx =
30、X (x 一 x )(2.26)k+1 k f (x ) 一 f (x ) kk-1- . _kk-1上式即是割线法的迭代公式.割线法也具有明显的几何意义，如图2.5所示，依次用割线方程f(x ) f 3,(、y = f (x ) +kk (x 一 x )k x 一 xk的零点逐步近似曲线方程f (x) = 0的零点.k k1割线法的收敛速度比Newton法稍慢一点，可以证明其收敛阶约为1.618，证 明请参考文献4.此外在每一步计算时需要前两步的信息x , x，即这种迭代法 也是两步法.两步法在计算前需要提供两个初始值x与x . k k1图2.5割线法的几何意义例2.7己知方程 f (x)
31、= x4 一 4x2 + 4 = 0 有一个二重根x* = 3，分别用Newton法(2.16)和重根Newton法(2.24)和(2.25)求其近似值，要求|x -x J 2x 10一6解 f r(x) = 4x3 一 8x, f(x) = 12x2 一 8，p (x)= ，m = 2 .f(x)4 x由 Newton 法(2.16)得(k = 0,1,2,)_x2 2 3x2 + 2k+1k 4 x4 x由 Newton 法(2.24)得X = X k+1kx (x2 - 2)4xX2 + 2X2 + 2(k = 0,1,2,)由 Newton 法(2.25)得Xk+1(k = 0,1,2,)kk利用上述三种迭代格式，取初值X0 = 1.4，分别计算，结果见表2.5.k式(2.16) X式(2.24) X式(2.25) Xkkk01.41.41.411.40714291.41414141.414285721.41068711.41421361.414213631.41245251.41421361.4142136B a a101.4141998141.4142
