(西南交大戴克俭版)计算方法非线性方程求解

1、1第第2章章 非线性方程求解非线性方程求解西南交通大学信息科学与技术学院西南交通大学信息科学与技术学院戴克俭制作戴克俭制作数值计算科学数值计算科学2第第2章章 非线性方程求解非线性方程求解设非线性方程为：设非线性方程为：f (x) = 0(2-1)方程方程(2-1)的解的解x*称为方程的称为方程的根根或函数或函数f(x)的的零点零点。若若f(x)可表示为：可表示为：f(x)=(x-x*)mg(x)其中其中m为大于为大于1的整数，且的整数，且g(x*)0，则称则称x*为方程为方程(2-1)的的m重根重根，或函数，或函数f(x)的的m重零点重零点。若。若f(x)为为n次次多项式多项式，则称，则称f

2、(x)=0为为n次代数方程次代数方程；若；若f(x)为为超越超越函数函数，则称，则称f(x)=0为为超越方程超越方程。32.1 二分法二分法2.1.1 二分法的基本思想二分法的基本思想求方程的方法最简单最直观的方法就是二分法。求方程的方法最简单最直观的方法就是二分法。在高等数学中有如下定理：在高等数学中有如下定理：定理定理 若若f(x)在在a, b内连续，且内连续，且f(a) f(b)0，则，则f(x)=0在在a, b内必有根；若内必有根；若f(x)在在a, b内还严格单调，内还严格单调，则则f(x)=0在在a, b内只有一个根。内只有一个根。a, b称为方法的称为方法的有根区间有根区间。42

3、.1 二分法二分法例例2.1 判断下列方程有几个实根，并求出其有根区间。判断下列方程有几个实根，并求出其有根区间。 f(x) = x3-x-1= 0 f(x) = x4-4x3+1= 0 解：解： 将方程变形为将方程变形为x3=x+1，绘曲线，绘曲线y=x3与与y=x+1由图可知，方程只有一个实根由图可知，方程只有一个实根x* (1,1.5)，所以即所以即(1,1.5)为有根区间。为有根区间。52.1 二分法二分法3)(4124)(223xxxxxf令：令：0)( xf解之得驻点：解之得驻点：30,21xx 解：解：)(xf 该两点将实轴分为三个区间：该两点将实轴分为三个区间：(-,0)、(0

4、,3)、(3,+)，在此三个区间上的符号分别为在此三个区间上的符号分别为“-”、“-”、“+”。由此可见由此可见f(x)仅有两个根。分别在仅有两个根。分别在(0,3)、(3,+)内。内。二分法的基本思想是：逐步二分区间二分法的基本思想是：逐步二分区间a,b，通过判断两，通过判断两端点函数值的符号，进一步缩小有根区间，将有根区间端点函数值的符号，进一步缩小有根区间，将有根区间的长度缩小到充分小，从而求出满足精度要求的近似根。的长度缩小到充分小，从而求出满足精度要求的近似根。62.1 二分法二分法)(210bax 二分法的计算过程：二分法的计算过程：取取a, b的中点的中点，将区间一分为二。，将区

5、间一分为二。若若f(x0)=0，则则x0就是方程的根，否则判断根就是方程的根，否则判断根x*在在x0的的左侧还是右侧。左侧还是右侧。若若f(a) f(x0)0，则则x*(x0, b)，令令a1= x0，b1=b。不论出现哪种情况，不论出现哪种情况，(a1, b1)均为新的有根区间，均为新的有根区间，它的长度只有原有根区间长度的一半。它的长度只有原有根区间长度的一半。72.1 二分法二分法 ,11nnbababa)(21ababnnn 对压缩了的有根区间，又可施行同样的步骤，再次对压缩了的有根区间，又可施行同样的步骤，再次压缩有根区间。如此反复进行下去，即可得到一系压缩有根区间。如此反复进行下去

6、，即可得到一系列有根区间套：列有根区间套：由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间an, bn的长度为：的长度为：当当n 时，区间必将最终收缩为一点时，区间必将最终收缩为一点x*。 82.1 二分法二分法)(21)(21|*|1ababxxnnnn 若取区间若取区间an, bn的中点的中点xn=(an+ bn)/2作为作为x*的近似值，的近似值，则有下述误差估计式：则有下述误差估计式：(2-2)只要只要n足够大，足够大，xn的误差就可足够小。的误差就可足够小。二分法的流程图如下：92.1 二分法二分法二分法的流程图：输入初始有根区间的端点输入初始有根区间

7、的端点a，b的值的值输入精度输入精度 ，x1=a计算函数值计算函数值f1=f(a),中点中点x=(a+b)/2.0当当|x-x1| 计算函数值计算函数值f=f(x)f =0退出循环f1*f0b=xx1=xx=(a+b)/2.0a=xx1=xx=(a+b)/2.0输出输出x的值的值TFTF102.1 二分法二分法注意：由于在偶重根附近曲线注意：由于在偶重根附近曲线y=f(x)为向上凹或向下凹，为向上凹或向下凹，即即f(a)与与f(b)的正负号相同，因此不能用二分法求偶重根。的正负号相同，因此不能用二分法求偶重根。例例2.2 用二分法求用二分法求f(x)=x3-x-1=0方程的实根，要求误差方程的

8、实根，要求误差不超过不超过0.005。有例有例1可知可知x* (1, 1.5)，要想，要想|x*-xn| 0.005， 则要则要解：解：0.005211)(1.521)(212n1n1nab，5.61lg22n由此解得：由此解得：所以取所以取n=6。112.1 二分法二分法按二分法计算过程见下表。按二分法计算过程见下表。nanbnxnf(a)f(xn)的符号的符号01.01.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.

9、3242-x6=1.3242为所求近似根。为所求近似根。122.2 迭代法迭代法2.2.1 迭代法的基本思想迭代法是用某种收敛于所给问题的精确解的极限过程，来逐步逼近精确解的一种计算方法，是求方程根最重要的方法之一。迭代法的基本思想是，已知方程（2.1）的一个近似根后，通过构造一个递推关系，即迭代格式，使用这个迭代格式反复校正根的近似值，计算出方程（2.1）的一个近似值序列，使之逐步精确化，一直到满足给定的精度要求为止，该序列收敛于方程（2.1）的根。132.2 迭代法迭代法计算结果生成数列：2.2.2 不动点迭代法及收敛性不动点迭代法及收敛性xk+1=(xk) (2-4) 不动点迭代法不动点

10、迭代法将方程f (x) = 0 化为等价方程：x=(x)(2-3)根x*初始近似值，按下式计算：若x*满足f (x*) = 0 ，则x*=(x*)；反之亦然，称x*为(x)的一个不动点。然后在隔根区间内取一点x0作为142.2 迭代法迭代法*limxxkkx0, x1, , xk, (2-5)如果这个数列有极限，显然x*就是方程x=(x) 的根。于是可从此数列中求得满足精度要求的近似根。这种求根方法称为迭代法，式(2-4)称为迭代格式，(x)称为迭代函数，x0称为迭代初值，数列(2-5)称为迭代序列。如果迭代序列收敛，则称迭代格式(2-4)收敛，否则称为发散。152.2 迭代法迭代法 不动点迭

11、代法的几何解释不动点迭代法的几何解释不动点迭代法是一种逐次逼近的方法，其基本思想是将隐式方程f(x)=0转化为求一组显式的计算公式(2-4)，也就是说不动点迭代过程是一个逐步显式化的过程。不动点迭代法的几何解释，见图2.2和图2.3。Oyxy=xy= (x)x*x0P0P0P1x1P1P2x2图2.2Oyxy=xy= (x)x*x0P0P0P1x1P1P2x2图2.3162.2 迭代法迭代法13 xx 用迭代法确定方程的近似根，需要讨论的问题用迭代法确定方程的近似根，需要讨论的问题一是如何选择初始值x0及其迭代函数(x)才能保证按迭代格式（2-4）求出的序列xk收敛；二是当序列xk收敛，如何估

12、计k次近似值的误差k=xk-x*。下面的例子说明迭代函数的选取将直接影响迭代效果。例2.3 用迭代法求方程x3-x-1=0在1,1.5内的实根，要求误差不超过0.005。解：算法A取原方程的等价形式得迭代函数131kkxx建立迭代格式，取初始值x0=1.5，计算结果如下：172.2 迭代法迭代法31xx31)(xxx计算结果如下：x1=2.375，x2=12.397，其结果越来越大，不可能趋向某个极限，可见迭代法所产生的迭代序列不一定都是收敛的，只有在一定条件下才能收敛。算法B取原方程的等价形式，得迭代函数，建立迭代格式311kkxx，取初始值x0=1.5，计算结果见表2.2182.2 迭代法

13、迭代法kxkkxkkxkkxk01.500021.330941.324961.324711.357231.325951.324871.3247192.2 迭代法迭代法 收敛条件与误差估计收敛条件与误差估计定理定理2.1 设迭代函数设迭代函数(x)且满足条件：且满足条件： 当当x a, b，a (x) b； 存在正数存在正数 L 1，使对任意的使对任意的x，ya, b，都有都有|(x) -(y)|L|x-y|成立。成立。则则 方程方程x=(x)在在a, b上有唯一根上有唯一根x*; 对任意迭代初值对任意迭代初值x0a, b，迭代序列迭代序列xk+1=(xk) (k=0, 1, 2, )收敛于收敛

14、于x*，且，且*limxxkk202.2 迭代法迭代法定理定理2.2 设迭代函数设迭代函数(x) C1a, b且满足条件：且满足条件： 当当x a, b，a (x) b； 存在正数存在正数 L 1，使对任意的使对任意的x a, b，都有都有| (x)| L1成立。成立。则则 方程方程x=(x)在在a, b上有唯一根上有唯一根x*; 对任意迭代初值对任意迭代初值x0a, b，迭代序列迭代序列xk+1=(xk) (k=0, 1, 2, )收敛于收敛于x*，且，且*limxxkk212.2 迭代法迭代法定理定理2.3 在定理在定理2.2的条件下，有如下误差估计式：的条件下，有如下误差估计式：|1|*

15、|1 kkkxxLLxx(2-6)|1|*|01xxLLxxkk (2-7)其中其中L1为常数为常数222.2 迭代法迭代法定义2.1 局部收敛如果存在x*的某邻域U(x*,)，使得对x0U(x*,)，迭代过程xk+1=(xk)所产生的序列xk都收敛于x*，则称迭代过程在根x*附近局部收敛。定理定理2.4 设设(x)在方程在方程 x=(x)根根x*附近有连续导数附近有连续导数，且且| (x*)|1， 则迭代格式则迭代格式 xk+1=(xk)局部收敛。局部收敛。232.2 迭代法迭代法反之，若在根反之，若在根x*的邻域的邻域R内，有：内，有： | (x)|1 (2-8) 则迭代必发散。则迭代必发

16、散。由式由式(2-6)可知，若可知，若|xk-xk-1|，则近似解则近似解xk有如下误差估计：有如下误差估计： LLxxk 1|*|242.2 迭代法迭代法 1|1|11kkkkkkkxxxxxxxE当当当当其中：其中：控制迭代结束的条件也常取为控制迭代结束的条件也常取为E。因此在正常收敛情况下，即因此在正常收敛情况下，即 L 不十分接近于不十分接近于 1时，时，可用可用|xk-xk-1| 控制迭代结束。这种用前后两次迭代结果控制迭代结束。这种用前后两次迭代结果估计误差的方法称为事后误差估计。在实际应用中，估计误差的方法称为事后误差估计。在实际应用中，25流程图流程图如下：如下：2.2 迭代法

17、迭代法输入迭代初值输入迭代初值x0，精度精度，最大迭代次数最大迭代次数N k=1, 2, , N | x |1时为时为超线性收敛超线性收敛，p=2时为时为平方收敛平方收敛。 迭代法的收敛速度迭代法的收敛速度292.2 迭代法迭代法0*)(, 0*)(*)(*)()() 1( xxxxpp)(0*)(!1)(!1)()(1 kxppeepkppkk 定理定理2.5 设设x*为为 x =(x)的根，在的根，在 x*的邻域内的邻域内(x)有连有连续的续的p 阶导数阶导数( p 1)，则：则： 若若0| (x*)|0)的三阶方法。假设xk充分靠近x*求解：axxxaxaaxakkkkk23223133

18、)(3)(axxaxakkk23131)(axxakk233)(故04131lim)(lim231aaxxaxakkkkk332.2 迭代法迭代法)(1kkxx 迭代过程的加速迭代过程的加速kx)()()(xxxx迭代过程产生的序列有时收敛很慢，利用定理2.5可以对这样的迭代过程作加速处理，令新的迭代函数为：式中0是待定常数，要想得到收敛速度更快的收敛函数，选择使 (x*)=0是最理想的。*)*)(*)(*)(xxxx由得*)(1*)(xx(2-9)(2-10)(2-11)34*xxk)(kkx)(xxkkkkkkxxxx)(1)(1kkkkkkxxx1)(1112.2 迭代法迭代法由于x*未

19、知，不易计算，因，可用xk代替x*，并令，即取kkkkxx1)(1)(将其代入新的不动点方程，可得加速的迭代格式(2-12)即(2-13)352.2 迭代法迭代法Lxk)(, 3 , 2 , 1,1)(111kxLLxLxkkk特别地，若)(x在所考虑的范围改变不大，其估计值为L，则可取，从而得加速公式(2-14)实际计算表明式（2-14）有加速效果，而且有时会将发散的迭代公式处理后，变为收敛的迭代公式。362.2 迭代法迭代法)(xx1x 松弛法松弛法对迭代函数引入一个常数，在方程的两端加上得)()1 (xxx于是)(111xxx(2-15)显然方程（2-15）与方程)(xx等价，若令)(x

20、x(2-16)372.2 迭代法迭代法)(111)(xxxx)(xx)(11)(xx方程（2-15）可写成(2-17)为了使用方程作迭代比用方程)(xx作迭代收敛得快，希望 (x)比 (x)更小，又由于(2-18)若 (x)连续，则当x在x*附近时， (x)也在 (x*)附近，为此选取=- (x*)，这样可以使得 (x)的绝对值较小，382.2 迭代法迭代法kk11)(11kkx)()1 (1kkkkkxxx但在求解过程中x*未知，故可用xk代替x*，只要k=- (xk)-1，记,2, 1kk，于是代入方程（2-15）有松弛迭代公式(2-19)称为松弛因子，松弛法的加速是明显的，甚至不收敛的迭

21、代函数经加速后一般也能获得收敛。392.2 迭代法迭代法)(, )()1(1)2(1)1(1 kkkkxxxx 埃特金埃特金(Aitken)加速法加速法设xk为方程x= (x) 的近似根序列，从xk开始相继迭代两次，将其结果记作：(2-20)上述迭代加速公式在实际应用中常常会遇到 (x)不太容易估计等困难，为避免对导数 (x)的估计，可采用下述改进方法进行迭代加速。402.2 迭代法迭代法之之间间与与介介于于kkkxxxxxx*)*)(*)1 (1之之间间与与介介于于)1(1)1(1)2(1*)*)(*kkkxxxxxxkkkkxxxxxxxx*)1(1)1(1)2(1kkkkkkkkkkkk

22、xxxxxxxxxxxxx)1(1)2(12)1(1)2(1)2(1)1(1)2(12)1(1)2(12)(2)(*所以当xkx*时，因此：则由微分中值定理，有412.2 迭代法迭代法可望得到精度更高的x*的近似值。于是得到如下迭代)2(1 kx)2(1 kxkkkkkkkkkkkxxxxxxxxxxx )1(1)2(12)1(1)2(1)2(11)1(1)2(1)1(12)()()( 称之为埃特金外推加速法。(2-21)此式右端可看成是的误差估计值，若以它修正格式：可以证明，若(2-4)为线性收敛，则埃特金法为平方收敛；，若(2-4)为p( p1)阶收敛，(x)的p阶导数连续，则埃特金为2p

23、-1阶收敛。422.2 迭代法迭代法埃特金加速法的流程图如下：埃特金加速法的流程图如下：输入迭代初值输入迭代初值x0，精度精度，最大迭代次数最大迭代次数N k=1, 2, , N D=0 F T 输出失败信息，结束输出失败信息，结束 x1=(x0)， x2=(x1)，D=x2-2x1+x0 |xd|1)重根，则f (x)可表示为：其中g(x*)0，此时用牛顿迭代法求x*仍然收敛，收敛速度将大大减慢。事实上，因为：62*)()()(*11xgexmgxgeexxekkkkkkk011)()()(1limlim1mxgexmgxgeekkkkkkkk令ek = xk- x*，则：(2-34)可见用

24、牛顿法求方程的重根仅为线性收敛。为了提高计算重根的收敛速度，有以下几种方法可供选择。2.2 迭代法迭代法63)()()(xfxfmxx0 )()()(11)(2 xfxfxfmx), 2 , 1 , 0()()(1kxfxfmxxkkkk 若已知重数若已知重数m，则可将迭代函数改为：则可将迭代函数改为：则：故迭代格式：(2-35)仍然是平方收敛的，这样就得到求m重根的牛顿迭代公式。但在实际问题中，一般重数m是不知道的，因此使用公式(2-16)就有困难。应另想办法。2.2 迭代法迭代法64)(*)()(*)()()(*)()()()(xQxxxgxxxmgxgxxxfxfxu)()()()()(

25、)()(21kkkkkkkkkxfxfxfxfxfxxuxuxx 2.2 迭代法迭代法将重根的问题转化为求单根问题将重根的问题转化为求单根问题为此注意函数：显然Q(x*)=1/m0，x*是方程u(x)=0的单根。因此求f(x)=0的m重根x*求u(x)=0的单根x*。而对u(x)=0用牛顿迭代法求根是平方收敛的，其迭代格式为：65kkkxxx,12211kkkkkxxxx121121121111*)(*)(*)(*)(kkkkkkkkkkkkkkkeeeeeeeeeexxxxxxxx2.2 迭代法迭代法仍然采用迭代公式(2-35)计算m重根。问题是如何确定根的重数？有一种边迭代边估计重数的方法

26、。设为用牛顿迭代公式(2-26)所得三个相邻的迭代值，令则66mmmkk111limmmxxxxkkkkk1211km112.2 迭代法迭代法因此可用下式估计m(2-36)故由式(2-15)可知67作业作业课后作业：P47 1(1)、2、5、6、8、12上机实验0112sin)(3xxxxf用下列方案求方程4334, 1sin12)(31xxxxxx或2 . 00),1sin(121)(32xxxxx的全部实根，精度要求 =10-6。并比较取相同迭代初值时各方法的收敛速度。方案一：用牛顿法。方案二：用普通迭代法，参考格式：方案三：用Aithen加速法。68作业作业要求：根据具体给定的练习题，用

27、框图描述算法、步骤，说明有关变量及数组含义，写出源程序，分析比较计算结果。692.4 解非线性方程组的牛顿法解非线性方程组的牛顿法 设设(x*, y*)为非线性方程组：为非线性方程组： (2-18)的解，已知的解，已知(x0, y0)为其近似解为其近似解(简记为简记为P0)，将将函数函数u, v在在P0点附近用一阶点附近用一阶Taylor多项式近似多项式近似表示：表示： 0),(0),(yxvyxu)()(),(),(000000yyyuxxxuyxuyxuPP )()(),(),(000000yyyvxxxvyxvyxvPP 70 在在P0附近非线性方程组附近非线性方程组(2-18)可用下述

28、线可用下述线性方程组近似代替：性方程组近似代替： (2-19) 若以方程组若以方程组(2-19)的解的解(x1, y1)作为原方程作为原方程组的新近似解，反复采用以上过程，可得方组的新近似解，反复采用以上过程，可得方程组的一近似解序列程组的一近似解序列(xk, yk) (k= 0, 1, ）。）。2.4 解非线性方程组的牛顿法解非线性方程组的牛顿法 ),()()(),()()(000000000000yxvyyyvxxxvyxuyyyuxxxuPPPP71(xk, yk)(简记为简记为Pk)的计算可采用如下迭代格式：的计算可采用如下迭代格式： (2-20)令令2.4 解非线性方程组的牛顿法解非

29、线性方程组的牛顿法), 1,0(),(),(11 kkkkkkkkkPkPkkkPkPyyyxxxkyxvyyvxxvyxuyyuxxukkkk 1|,|1|, |1111kkkkkxxxxxE当当当当 1|,|1|, |1112kkkkkyyyyyE当当当当72 当当maxE1, E2 (容许误差容许误差)时，停止迭代，时，停止迭代，并取并取(xk+1, yk+1)作为非线性方程组之解。作为非线性方程组之解。 式式(2-20)称为解非线性方程组称为解非线性方程组(2-18)的牛的牛顿迭代公式。若用矩阵形式表示迭代过程，顿迭代公式。若用矩阵形式表示迭代过程，令：令：2.4 解非线性方程组的牛顿

30、法解非线性方程组的牛顿法kPkkkkxfxJxfx yvxvyuxukkkkkkyxvyxuyx)()()(),(),(73则式则式(2-20)等价于：等价于： (2-21)其中其中 称为雅可比矩阵。称为雅可比矩阵。例例9 用牛顿法求下述方程组在用牛顿法求下述方程组在P0=(1,1)附近的解附近的解2.4 解非线性方程组的牛顿法解非线性方程组的牛顿法)()(11kkkkxfxfxx )(kxf 0)13()1(),(05),(22xyxyxvyxyxu742.5 劈因子法劈因子法对对n 次实系数代数方程次实系数代数方程 (2-21)由代数学可知，由代数学可知，f (x)= 0有有n 个根，其中

31、可能有个根，其中可能有实根，也可能有成对出现的共轭复根。下面实根，也可能有成对出现的共轭复根。下面介绍一种既可求其实根，又可求其复根的方介绍一种既可求其实根，又可求其复根的方法，即劈因子法。法，即劈因子法。 劈因子法的基本思路是先给出一个初始劈因子法的基本思路是先给出一个初始二次式二次式0)(110 nnnaxaxaxfvuxxx 2)( 75用用(x)去除去除f(x)，得商得商Q(x)与余数与余数R(x)因此因此 (2-22)当当|r0|、|r1|均小于给定的误差限均小于给定的误差限时，则可认为时，则可认为(x)为为f(x)的近似二次因式，令的近似二次因式，令(x)= 0可得可得f(x)=

32、0的两个近似根的两个近似根 (2-23)2.5 劈因子法劈因子法0)(23120 nnnbxbxbxQ10)(rxrxR )()()()(2xRxQvuxxxf )4(212vuux 76否则，不断修改否则，不断修改u、v，直到直到r0 、 r1满足要求为满足要求为止。止。 如何修改如何修改u、v呢？比较式呢？比较式(2-22)两端的系两端的系数，可导出数，可导出r0 、 r1的递推公式的递推公式 (2-24)2.5 劈因子法劈因子法)2,3,2(2132102101100 nivbarvbubarvbubabubababnnnnniiii77显然显然r0 、 r1是是u、v的函数，记为的函数

33、，记为r0= r0(u,v)， r1= r1(u,v)。当当|r0| 或或|r1| 时，需要选择修时，需要选择修正量正量 u、 v，使使按照牛顿法的思想将此方程组左端函数用一按照牛顿法的思想将此方程组左端函数用一阶阶Taylor多项式代替，可得关于多项式代替，可得关于 u、 v的近的近似线性方程组似线性方程组 (2-25)2.5 劈因子法劈因子法 0),(0),(10vvuurvvuur 111000rvvruurrvvruur78将此方程组的系数记为将此方程组的系数记为将式将式(2-22)两端分别对两端分别对u、v求导，移项后可得求导，移项后可得 (2-26) (2-27)式式(2-26)表

34、明表明s0 x+s1为用为用x2+ux+v去除去除Q(x)所得所得之余数，之余数， 为所为所n-4次商式，记次商式，记2.5 劈因子法劈因子法urturtvrsvrs 11001100)()()(102sxsvQvuxxxQ )()()(102txtuQvuxxxxQ vQ 79代入式代入式(2-26)并比较系数，可求得并比较系数，可求得s0、s1的递推的递推计算公式计算公式 (2-28)2.5 劈因子法劈因子法25140 nnncxcxcvQ)4,3,2(42154302101100 nivcbsvcucbsvcucbcucbcbcnnnnniiii80将式将式(2-26)两端乘以两端乘以x

35、，得得将此式与将此式与(2-27)比较，即知比较，即知 t0=s1-s0u t1= - s0v (2-29)将由式将由式(2-28)与式与式(2-29)求出的求出的s0、s1、t0、t1代代入式入式(2-25)得修正量得修正量 u、 v应满足的方程组应满足的方程组2.5 劈因子法劈因子法vsxusssvQxvuxxxsxsvQxvuxxxxQ001021202)()()()( 81 (2-30)若式若式(2-30)的系数行列式的系数行列式 (2-31)则可解得则可解得 (2-32)从而得从而得u、v 的新近似值的新近似值u1=u+ u、v1=v+ v和和新的近似二次因式新的近似二次因式2.5

36、劈因子法劈因子法 111000rvsutrvsut001101100 ststststD)(1)(110010110trtrDvsrsrDu 1121)(vxuxx 82例例10 给定方程给定方程f(x)=x4+x3+5x2+4x+4=0，用劈用劈因子法求其根，使因子法求其根，使 10-6。解解 首先取首先取 (x)= x2+0.8x+0.8，则用则用 (x)除除f(x)所得的商式所得的商式Q(x)及余式及余式R(x)如下：如下： Q(x)=x2+0.2x+4.04 R(x)=r0 x+r1=0.608x+0.768因为因为|r0|=0.608与与|r1|=0.768较大，需继续迭代。较大，需

37、继续迭代。于是用于是用 (x)除除Q(x)，得余式：得余式： s0 x+s1=-0.6x+3.24再用再用 (x)除除s0 x2+s1, 得余式得余式: t0 x+t1=3.72x+0.482.5 劈因子法劈因子法83用用ri、si、ti ( i=0, ,1)生成方程组生成方程组解得解得 u=0.1969662、 v=0.2078569，由此得新由此得新的近似二次因式：的近似二次因式： 1(x)= x2+(u+ u)x+(v+ v) = x2+0.9969662x+1.0078569用用 1(x)除除f(x)得余式：得余式： r0 x+r1=0.01992596x-0.020460612.5

38、劈因子法劈因子法 768. 024. 348. 0608. 06 . 072. 3vuvu84继续迭代两次，继续迭代两次，r0、r1即达到了机器零，并得即达到了机器零，并得到准确的二次因式到准确的二次因式 (x)=x2+x+1，故：故： f(x)= (x)Q(x)=(x2+x+1)(x2+4)有有 (x)=0、Q(x)=0即可求即可求f(x)的四个根：的四个根： x1, ,2=- -0.50.866025i x3, ,4=2i2.5 劈因子法劈因子法85例例11 不同迭代格式和算法的比较不同迭代格式和算法的比较用下列迭代格式求方程用下列迭代格式求方程f(x)=x3-x-1=0在在x=1.5附附

39、近的根。近的根。 分别对、两种迭代格式用埃特金外推分别对、两种迭代格式用埃特金外推 加速法。加速法。311 kkxx131 kkxx2.6 典型例题分析典型例题分析862.6 典型例题分析典型例题分析例例12 假收敛现象及避免方法假收敛现象及避免方法已知方程已知方程 的最小正根在的最小正根在(3.5, 5)内，试用割线法求此根。内，试用割线法求此根。解：弦割法公式为：解：弦割法公式为：用四组不同的初值用四组不同的初值x0，x1进行迭代，结果如下：进行迭代，结果如下：02)cos()(xeexfxx17.070775)(3.6357273.93.8(1)5(1)5(1)4(1)1(1)0 xf,

40、xx,x,x)()()(111kkkkkkkxfxfxxxfxx87每一组迭代值都出现了每一组迭代值都出现了xk=xk-1的情况，继续迭代不的情况，继续迭代不会再有改善，表面上看似乎得到了四个根，其中第会再有改善，表面上看似乎得到了四个根，其中第组结果组结果 为所求的最小正根，然而由图为所求的最小正根，然而由图2-13可见，在区间可见，在区间(3.5, 5)内方程只有一个根。由各内方程只有一个根。由各组结果对应的函数值组结果对应的函数值f(xk)可以看出，只有第结果可以看出，只有第结果 才是所求最小正根的近似值，其他才是所求最小正根的近似值，其他各组结果均为各组结果均为“假收敛假收敛”。2.6

41、 典型例题分析典型例题分析37.6997)(3.9(2)4(2)5(2)4(2)1(2)0 xf,xx,x,x4437.89988)(3.9181143.95(3)10(3)10(3)9(3)1(3)0 xf,xx,x,x4-5(4)9(4)9(4)8(4)1(4)0102.253056)(4.7300414.14xf,xx,x,x3.918114(3)10 x4.730041(4)9(4)8 xx88以第组计算结果为例分析如下：由于以第组计算结果为例分析如下：由于都靠近曲线都靠近曲线f(x)的极小值点，因此过的极小值点，因此过(3.9, f(3.9)与与(4, f(4)两点的弦线两点的弦线L与与x轴的夹角较小，从而与轴的夹角较小，从而与x轴的交点轴的交点 远离远离