第3章非方程(组)的数值解法

1、第3章 非方程（组）的数值解法3.1 引 言在第2章中，我们已经学过线性方程组的数值解法，但是在实际问题中，常常遇到的是非线性方程（组）的求解问题，而非线性问题比线性问题复杂，因此，非线性模型常常用线性模型来近似代替；然而，在精度要求比较高的情形下，必须直接求解非线性问题。本章首先讨论单个方程的求根方法，如二分法，不动点迭代法及其加速方法，牛顿迭代法及其改进方法，并讨论迭代序列的收敛性，收敛速度和误差估计等，最后简要介绍非线性方程组的一些数值解法。定义3.1.1 对于单变量方程 (3.1.1)如果有(实数或复数)，使，则称为方程(3.1.1)的根(root)，或函数的零点(zero point

2、). 定义3.1.2 设是整数，若函数可以写成，且， (3.1.2)则称为方程(3.1.1)的m重根(root of multiplicity m)或函数的m重零点(zero of multiplicity m). 特别地，当时，称为方程(3.1.1)的单根(simple root).定理3.1.1 设在处阶导数存在，则是函数的重零点的充分必要条件是，. (3.1.3)若为多项式 ,其中，为实数，则称方程(3.1.1)为n次代数方程(algebraic equation of degree n)。根据代数基本定理，方程(3.1.1)在复数范围内有且仅有n个根(含复根，m重根为m个根)。理论上已

3、证明，当次数, 方程的根可用求根公式表示；而当时，方程没有一般的求根公式，通常都要用数值方法求解。若为超越函数(transcendental function)，则称方程(3.1.1)为超越方程(transcendental equation)；如. 超越方程一般更难求得精确解，都要使用数值方法求解。高次代数方程和超越方程都属于非线性方程(nonlinear equation)。对于非线性方程根的数值解法，主要解决以下3个问题：(1) 研究根的存在性；(2) 找出有根区间；(3) 计算根的近似值。根的存在性，主要依据以下零点定理(zero-point theorem): 定理3.1.2 (零点

4、定理) 设为上的连续函数，若有，则在区间内至少有一个实根。通常称为有根区间。若在上还是单调函数，则在区间内仅有一个实根。如何找出有根区间，通常可用图像法或逐次搜索法，具体做法是：从点出发，以为步长依次取点，如果，则区间为有根区间。在有根区间内，用适当的数值方法求出根的近似值，使其满足一定的精度要求。3.2 求实根的二分法求根方法中最简单直观的方法就是二分法(Bisection Method)。计算过程如下：设为上的连续函数, 且为有根区间，取中点，如果，则是方程的根；否则，将它平均分为两半，检查与是否同号。若是，则根x*在右侧，取, ; 否则取, ，得到新的有根区间，且 (见图3.2.1).图

5、3.2.1重复以上过程，取，若，则是方程的根；否则，将平均分为两半，确定根在的哪一侧，得到新的有根区间，且；如此反复二分可得一系列有根区间其中每一个区间长度都是前一个区间长度的一半，显然，的长度为.这时，取最后一个区间的中点作为根的近似值，其误差估计为. (3.2.1)当时，即. 对给定的精度，要使，只需令 解得. (3.2.2)由式(3.2.2)可预先确定出二分法的次数.二分法的优点是计算过程简单且收敛性有保证，但收敛的速度较慢，且该方法只能求实根，不能求复根或偶数重根，通常可用于求其他更好的求根迭代法的初始值。例3.2.1 求方程的实根，要求精确到小数点后第2位。解 设，则在实数域上均连续

6、，且，由零点定理知，在内至少有一个实根。又因为，所以在内有且仅有一个实根。下面从区间-3, 3开始，以1为步长，通过计算的函数值，逐步缩小方程的有根区间(表3.2.1)表3.2.1-3-2-10123-39-18-9-6-3627由表3.2.1知，方程在区间内有且仅有一个实根。记 则 取的中点，将区间二等分，由于，即与同号，此时令，得到新的有根区间；如此反复二分下去。下面估计二分的次数. 因为题目要求精确到小数点后第2位，所以可取精度，由(3.2.2)得，.取，即至多二分7次即可，计算结果见表3.2.2.表3.2.2符号01.00002.00001.500011.00001.50001.250

7、021.25001.5.001.375031.37501.50001.437541.43751.50001.468851.43751.46881.453161.45311.46881.460971.45311.46091.4570其中为方程精确到小数点后第2位的近似根。3.3 迭代法及其收敛性迭代法(Iterative Method)是用收敛于所给问题的精确解的极限过程，是一种逐步逼近精确解的数值方法。其基本思想是将方程求根问题转化为某个函数求不动点的问题，利用不动点的迭代法求方程的近似根。3.3.1 不动点的迭代法及其收敛性将方程(3.1.1)改写成等价形式 (3.3.1)例如，可取.定义3

8、.3.1 若数满足，则称为的一个不动点(fixed point).注 的不动点是方程(3.1.1)的一个根，求方程的根等价于求函数的不动点。在根的附近取一点作为的初始近似值，把代到式(3.3.1)的右端，计算得到 . 如果连续，可构造迭代公式 (3.3.2)并称之为不动点迭代法(fixed point iterative method)，称为迭代函数(iterative function). 由式(3.3.2)逐次迭代可得到序列，如果，则由式(3.3.2)两端取极限，得,即为的不动点。从几何图像看，的不动点就是直线与曲线的交点的横坐标.从它的某个初始近似值出发，在曲线上确定一点，引平行于轴的直

9、线，与直线交于点，其横坐标即为，由式(3.3.2)逐次求得的，即为如图3.3.1所示点的横坐标。若迭代收敛，则序列将越来越逼近所求的交点的横坐标(参见图3.3.1)，如果迭代发散，则序列将越来越远离所求的交点的横坐标(图3.3.2).图 3.3.1图 3.3.2迭代法主要研究以下3个问题：(1) 如何选取合适的迭代函数？(2) 迭代函数满足什么条件时，序列才收敛？(3) 序列的收敛速度及误差估计？例3.3.1 用迭代法求方程的实根。解 在例3.2.1中，我们使用搜索法确定有根区间，也可用图像法来确定。曲线与直线只有一个交点，其横坐标介于1与2之间，见图3.3.3. 故原方程在区间内有唯一实根，

10、因此有根区间为. 将方程转化成等价形式，迭代函数有很多种取法，例如： 图 3.3.3，, 等等。下面仅取前两种迭代函数进行计算，其余的读者可作为练习。对应于迭代函数的迭代公式分别为方法1 ， (3.3.3)方法2 . (3.3.4)取区间中点作为初值，迭代结果见表3.3.1. 表3.3.1k01234567(方法1)(方法2)1.51.51.44221.31251.46051.86951.4548-0.26701.45663.00951.4560-10.62891.4562603.39401.4562-1.0984×108显然，方法1收敛，原方程的准确值为；而方法2发散。例3.3.1

11、表明构造迭代法(3.3.2)的形式有很多种，但有的收敛，有的发散。那么，迭代函数满足什么条件以及初值如何选取，才能使迭代序列收敛？  定理3.3.1 设迭代函数，满足； (1) 当时，；(2) 满足Lipschitz条件，即存在常数，使，都有, (3.3.5)则在区间上存在唯一不动点，且由式(4.3.2)生成的迭代序列对任何初值都收敛于，并有误差估计, (3.3.6). (3.3.7)证明 首先证明不动点存在性。记，由条件(1)，得 及 .若上述2个不等式有一个等号成立，则或，即有不动点；否则必有. 因为在上连续，所以由零点定理知，必有,使，即 ,亦即是的不动点。其次证明的唯一性。若

12、都是的不动点，即，且，则由条件(3.3.5)得,矛盾！这表明，即不动点是唯一的。然后证明收敛性。即要证由式(3.3.2)生成的迭代序列收敛于的唯一不动点. 因为，所以. 再由条件(3.3.5)，得 (3.3.8)因为，所以，即.最后证明估计式(3.3.6)和(3.3.7). 因为，所以.注意到，利用上式第一个不等式，可得(3.3.6)，再利用最后一个不等式可得式(3.3.7)，证毕!注1 式(3.3.6)称为事后估计。对给定的精度，由式(3.3.6)解得. (3.3.10)由此可知, 只要相邻两次计算结果的偏差足够小, 那么就可保证近似值具有足够的精度。实际计算过程中，常用条件来判断迭代过程是

13、否结束。式(3.3.7)称为先验估计，它可用来估计达到精度所需的迭代次数k：由解得迭代次数应满足. (3.3.11)例如，在例3.2.1中，若要求近似根的误差不超过，只要使k满足，将代入，得，即迭代9次即可。注2 从估计式(3.3.8)可以看出，常数L越小，收敛速度越快。 在实际应用中，要验证函数是否满足Lipschitz条件比较困难，因此常常采用下面的充分条件代替Lipschitz条件。推论 设 (表示在上具有一阶连续导数)，若， (3.3.9)则定理3.3.1中结论成立。证明 由微分中值定理可得，对任意，有，其中介于与之间，故式(3.3.5)成立，证毕!注 若对任意，都有，只要初值，则由式

14、(3.3.2)生成的迭代序列都是发散的。事实上，因为，其中介于与之间，所以，故迭代序列发散。 例3.3.2 讨论例3.3.1中，方法1及方法2中迭代序列的敛散性。解 对于方法1, 迭代函数. 在中, ,且. 而,故迭代格式(3.2.3)产生的迭代序列收敛。对于方法2，迭代函数. 在区间中，故迭代格式(3.3.4)是发散的。3.3.2 局部收敛性与收敛阶很多迭代格式只在根邻近收敛, 即初值必须取在的邻近。若离根较远, 所用迭代格式有可能发散, 因此有下列局部收敛性的概念：定义3.3.2 设在某区间 I上有不动点，若存在的一个邻域，对，迭代法(3.3.2)生成的序列，且收敛于，则称迭代序列在根附近

15、局部收敛的(locally convergent)。定理3.3.2 设为的不动点，在的邻域连续，且，则迭代法(3.3.2)局部收敛。证明 由的连续性，存在，使，并有.因此对任意，有，故在区间上满足定理3.3.1的推论的条件，故由式(3.3.2)生成的序列对均收敛于. 证毕!例3.3.3 构造不同迭代法求的根.解 (1) 构造迭代公式则迭代函数为. 因为,所以不满足定理3.3.2的条件。(2) 构造迭代公式 则迭代函数为.因为, ，所以由定理3.3.2知，迭代法收敛。(3) 构造迭代公式 则迭代函数为.因为，所以由定理3.3.2知，迭代法收敛。若取，分别用上述三种迭代计算，结果见表3.3.2，.

16、 从表3.3.2看到迭代法(1)不收敛，迭代法(2)和迭代法(3)收敛，且迭代法(3)收敛最快。表 3.3.2k迭代法(1)迭代法(2)迭代法(3)022211.51.751.75221.734 751.732 14331.51.732 3611.732 051 实际应用中，一般事先不知道，故难以验证，但如果存在在根的邻域内，可用 来代替.为了描述序列收敛的快慢，引入收敛阶的概念。一个具有实用价值的迭代法，不仅要求它收敛，而且还要求它收敛比较快。迭代收敛的速度是指迭代误差的下降速度。在定理3.3.1中我们知道L越小收敛越快，但要准确反映收敛速度，还需要引进收敛阶(order of conver

17、gence)的概念，它是衡量迭代好坏的标志之一。定义3.3.3 设序列收敛到，记误差，若存在实数及，使, (3.3.10)则称序列是按渐进误差常数，阶收敛到 (converges to of order p with asymptotic error constant )。特别地，当且，称为线性收敛 (linearly convergent)。当时，称为平方收敛 (quadratically convergent)。当时，统称为超线性收敛 (superlinarly convergent)。显然，数的大小反映了收敛速度的快慢。越大，则收敛越快。因此迭代法的收敛阶是对收敛速度的一种度量。定理3.

18、3.3 设为的不动点，整数p1，在的邻域连续，且满足 而 (3.3.11)则由迭代法(3.3.2)产生的序列在的邻域是阶收敛的，并有. (3.3.12)证明 由于，故, 由定理3.3.3可知局部收敛，对邻域中的初始近似值，由式(3.3.2)迭代到，将在处按Taylor展开，得,其中，介于与之间。由式(3.3.11)得即.由的连续性，上式两边取极限，即得式(3.3.12).特别地，(1) 当 但时，序列线性收敛；(2) 当, 但时，序列平方收敛。根据定理3.3.3的结论，例3.3.3中迭代法(3)的,而, ，故知，即该迭代序列是平方收敛的。3.3.3 迭代法加速不动点迭代式(3.2.2)通常只有

19、线性收敛，有时甚至不收敛，为了加快迭代法的收敛速度，通常可采用斯特芬森加速迭代(Steffensens acceleration)。设是的不动点，记，利用中值定理有介于与之间。通常依赖于，若变化不大，设，于是有 从上两式消去C，则得 或 .解得.若记 (3.3.13)则用序列作为不动点的新的近似值序列，一般它比迭代法(3.3.2)收敛更快。迭代法(3.3.13)可改写为下列形式 (3.3.14)称为Steffensen迭代法(Steffensens iterative method)，它是将原不动点迭代式(3.3.2)的计算两步合并成一步得到，可改为另一种不动点迭代格式, (3.3.15)其中

20、 (3.3.16)Steffensen迭代法具有比不动点迭代法更高的收敛速度；特别地，这种迭代方法还能使原来发散的迭代法变为收敛的迭代法。定理3.3.4 若为式(3.3.16)定义的函数的不动点，则为的不动点。反之，若是的不动点，设连续，且，则是的不动点，且Steffensen迭代法(3.3.14)是平方收敛的。(证明见文献3)。例3.3.4 试用Steffensen迭代法求方程的根的近似值。解法1 原方程变形为，此时迭代函数为，以该迭代公式形成的Steffensen迭代公式为结果见表3.3.3. 表 3.3.3k01.500001.442249571.4605260011.456132451

21、.456174241.4561611021.456164251.456164241.4561642531.456164251.456164251.45616425比较例3.3.2的结果，可知本方法收敛速度更快。事实上，原迭代法是线性收敛，现在是平方收敛的。解法2 原方程变形为，此时迭代函数为，例3.3.2曾指出，迭代公式是发散的。以该迭代公式形成的Steffensen迭代公式为结果见表3.3.4. 表 3.3.4k01.500001.312500001.8695068411.452779141.466905961.4217462621.456164291.456224541.455972473

22、1.456164251.456164251.4561642441.45616425 1.456164251.45616425此迭代法是收敛的。这表明，即使不收敛的迭代法，用Steffensen加速迭代后仍可能收敛。3.4 Newton迭代法不动点迭代法求解非线性方程近似根有2个缺点：一是选择迭代函数，并验证收敛性比较麻烦；二是这种迭代法一般收敛速度较慢。Newton迭代法(Newtons iterative method)采用另一种迭代格式，其基本思想就是将非线性方程近似转化为线性方程求解，具有较快的收敛速度。Newton迭代法是求解非线性方程的一种重要而常用的迭代法。3.4.1 Newton

23、迭代法及其收敛性 设是方程的一个初始近似根，如果存在且连续，那么函数在处的一阶Taylor展开式为，介于与之间。忽略余项，则得方程的在附近的线性近似 上式右端是的线性方程，若，解得，记作，即，它可作为新的近似根。重复以上过程，并假设，得 . (3.4.1)称式(3.4.1)为Newton迭代公式(Newton iterative formula)，其迭代函数为. (3.4.5)几何意义：求方程的根，几何上就是求曲线与轴交点的横坐标. 若已知的一个近似，通过点作曲线的切线，其切线方程为，该切线与x轴交点的横坐标(令，解出)正好是，记为，即有，这就是Newton迭代公式，如图3.4.1所示。鉴于此

24、，Newton迭代法也称为切线法(tangent method)。图 3.4.1例3.4.1 用Newton迭代法求方程在1.5附近的根。解 ，所以Newton迭代公式为取初值，迭代结果见表3.4.1表3.4.1k012341.51.4571428571428571.4561647462066851.4561642461360391.456164246135909可见，Newton迭代法的收敛速度很快。例3.4.2 用Newton迭代法求在附近的根。解 ，取初值，迭代结果见表3.4.2表3.4.2k012340.50.57102043980.56715556870.56714329050.56

25、71432904若取初值，迭代结果见表3.4.3.表3.4.3 k0123-1.5-13.463378-5.643480×104-Inf显然，迭代发散。例3.4.2说明，对Newton迭代法，初值选取非常重要，选择得好，迭代收敛且迭代速度快；反之，可能迭代发散。关于Newton迭代法的收敛性有以下的局部收敛定理：定理3.4.1 设函数在附近有二阶连续导数，若是方程的一个单根，即：，但, 则Newton迭代法(3.4.1)至少是平方收敛的。 证明 由式(3.4.1)知，迭代函数. 因为，, (3.4.2)所以由定理3.3.3可知，Newton迭代法(3.4.1)至少是平方收敛的，证毕!

26、注 定理3.4.1表明Newton法收敛很快，但是对初值要求比较高，必须足够靠近时，才能保证迭代序列局部收敛。下面给出初值在较大范围内收敛的一个充分条件：定理3.4.2设函数，且满足条件： (1) ; (2) 当时，； (3) 当时，不变号； (4) 任意初值，使则由Newton迭代格式(3.4.1)确定的序列收敛于在区间内唯一的根.图 3.4.2证明 首先证明根的存在性。由条件(1)及连续，知在内至少有一根，由条件(2)知，是单调函数，因此方程在内有唯一根.然后证明收敛性。不妨设(见图3.4.2)，由知：，所以，即 .另一方面，.上面两式相减，得 因此，再以代替继续上述过程，有,故序列是单调

27、减少且有下界的数列，故必有极限，记，由，知：当时，可得，由根的唯一性，知.例3.4.3 用Newton迭代法求方程在内的实根，讨论收敛性，并要求.解 设，则. 当时，有，.取，有. 由定理3.4.2知：相应的Newton迭代公式,收敛。且为满足精度要求的近似根(见表3.4.4)。表3.4.4k0123410.75036386780.73911289090.73908513340.7390851332例3.4.4 (1) 设，求平方根的过程可化为解方程. 若用Newton法求解，证明对任何初值，相应的Newton迭代公式都收敛于. (2) 求的近似值。证 (1) 对，Newton迭代公式为. (

28、3.4.3)由此可得.故对任意的，均有. 又因为所以由式(3.4.3)产生的迭代序列单调递减且有下界，从而迭代序列的极限存在，记其极限为. 对式(3.4.3)两边取极限得，解得.这是在计算机上作开方运算的一个实际有效的方法，它每步迭代只做一次除法和一次加法再做一次移位即可，计算量少，收敛速度快。(2) 此时，代人式(3.4.3)， 取初值，得, , ,与的精确值相比较，是具有10位有效数字的近似值。例3.4.5（悬索垂度与张力计算）公路和铁路设计中常出现高架悬索桥梁，由于桥梁的重量，在设计中需计算各个支撑部件所承受的张力. 设高架悬索系统如图3.4.3，其中表示悬索的跨度，是悬索的垂度，是悬索

29、承受的质量。图 3.4.3解 设悬索承受的重量是均匀分布的，表示重力加速度，则悬索承受的负荷密度为 若不计温度变化的影响，悬索端点的张力由公式确定；为此需计算悬索垂度. 设悬索长度为，垂度近似满足如下的非线性代数方程不妨设 则悬索的负荷密度。采用Newton迭代法求解非线性方程，取迭代初值，误差精度开始计算，迭代到第7步，得到结果，悬索端点承受张力。由张力计算公式知：悬索的垂度越大，悬索受到的张力越小，因此可调节悬索的长度，增加悬索的垂度，减小其承受的张力. 表3.4.5显示了对于悬索的不同长度，数值计算所得悬索的垂度及其端点所受的张力。表3.4.5L/米125130135140145150x

30、/米15.2721.9427.1931.6335.4538.75T/牛16168.512426.810922.110109.19608.69275.93.4.2 Newton迭代法求重根设为方程的m重根，由定义3.1.2及定理3.1.1知：在的某领域内可表示为 (3.4.4)其中，是正整数。且有，. Newton法的迭代函数. 因为, (3.4.5)且，所以由定理3.3.3知：Newton迭代法求重根时仍收敛，但只是线性收敛的。下面将对Newton迭代法加以改进正，使得改进的Newton迭代法求重根时是平方收敛的。若根的重数m已知，则可将Newton迭代法改写为, (3.4.6)其迭代函数为.

31、 (3.4.7)由式(3.4.5)得,由定理3.3.3知：迭代公式(3.4.6)至少平方收敛。称式(3.4.6)为改进的Newton迭代法(modified Newton iterative method).若根的重数m未知，令， (3.4.8)由式(3.4.4)，得, (3.4.9)容易验证是方程的单根，对它应用Newton法，迭代函数为 (3.4.10)从而可构造迭代格式 (3.4.11)因为Newton迭代法求单根时是至少平方收敛的，所以迭代公式(3.4.11)求也是至少平方收敛的。例3.4.6 已知方程的二重根，试用Newton迭代法及迭代法(3.4.6)、(3.4.11)三种方法求根

32、的近似值。解 ，方法1：Newton迭代法： .方法2：迭代法(3.4.6) .方法3：迭代法(3.4.11) .取初值，结果见表3.4.6.表 3.4.6方法1方法2方法31.77777782.05555561.94117651.89351852.00050061.99940011.94775732.00000012.00000001.97411222.00000002.0000000方法2与方法3均达到精确度，而方法1只有线性收敛，要达到相同精度需迭代16次。3.5 弦 截 法Newton迭代法对于单根的求解具有收敛快、稳定性好、精度高等优点，它是求解非线性方程的最有效的方法之一。但在应用

33、迭代公式时，每步迭代都要计算函数值与导数值，计算量较大。当导数值计算困难时，Newton迭代法将无法进行。注意到因为Newton迭代序列是收敛的，当充分大时，有，代入式(3.4.1)，则得离散的Newton迭代法.(3.5.1)并称式(3.5.1)为弦截法(secant method). 几何意义：通过曲线上两点作割线，方程为，其割线与x轴交点的横坐标恰好是式(3.5.1)中的, 如图3.5.1所示，因而迭代法(3.5.1)又称为割线法。图 3.5.1弦截法与Newton迭代法不同，它需要给出两个初始近似，才能启动迭代过程，因此称之为多步迭代法。关于弦截法的收敛性有以下结果：定理3.5.1 设

34、是方程的单根，若在的某个邻域内有二阶连续导数，且对任意，有，则当邻域充分小时，对，弦截法按阶收敛于根.证明 (1) 首先证明：由弦截法得到的序列.设是过两点的弦与x轴的交点横坐标，则差商 因为所以又因为在的某个邻域内有二阶连续导数，则,其中介于之间，介于和之间，即. 记，.取充分小的，使其满足：，则有,所以，当，即时， ,即，从而序列.(2) 其次证明：由弦截法得到的序列收敛。由(1)的证明过程容易看出.依次递推可得.又因为，所以，即.(3) 最后证明：弦截法的收敛阶为.记，则. 由的收敛性可知，当k充分大时，.记，则. 将上式两边同时乘以得为了讨论问题的方便，可将近似式看作等式.令，或，则上

35、式可化为.这是一个二阶常系数齐次差分方程，可设，代入差分方程可得.解得故差分方程的通解为令分别等于，解得.由不难验证：；故. 又因为，所以当时，即，所以有，从而所以弦截法的收敛阶为. 证毕！由此可知，弦截法是超线性收敛的，且收敛阶, 虽然收敛速度比Newton迭代法低，但是因为不需要计算导数，所以也是工程计算中常用的方法之一。例3.5.1 用弦截法法求方程在1.5附近的根。解 ，所以弦截法迭代公式为取初值，迭代结果见表3.5.1，而方程在1.5附近的根是表 3.5.101234561.00000001.33333331.42553191.45822111.45613111.45616421.4

36、5616423.6 抛物线（Müller）法如果考虑用的二次插值多项式的零点来近似的零点，就导出了抛物线法。设已知方程(3.1.1)的根的3个近似值 以这三点为节点的的二次插值多项式为 (3.6.1)为简便起见，令 (3.6.2)则式(3.6.1)可改写为, (3.6.3)其零点为：. (3.6.4)按式(3.6.4)，的二次插值多项式有两个零点，取哪个作为新的近似根，考虑到已是方程(3.1.1)的近似根，新的近似根自然应在的邻近，故选取近似根的原则是使得较小，于是有 (3.6.5)按式(3.6.5)计算方程(3.1.1)的近似根称为抛物线法(parabolic method)，也称

37、Müller方法(Müller method)，或二次插值法。如图3.6.1所示，是过曲线上的三点的抛物线，故抛物线法的几何意义是以过曲线上的三点的抛物线与轴的交点作为曲线与周轴交点的近似。图3.6.1抛物线法的计算步骤为：(1) 给定精度，初始值 计算（要求互异）。(2) 计算(3) 若，则；否则再转步骤(2).例3.6.1 用抛物线法求方程在内的根的近似值，取初值，.解 因为初值，所以.按式(3.6.2)和式(3.6.5)计算，得仿上述过程，继续进行下去，计算结果见表3.5.1.表3.5.1k01411.51.754.522513.591831.6666670.0740

38、7415.22223710.33340111.77777341.6729220.00070711.72929510.67917711.79609351.6729822.48×10-7注1 若在其零点邻近三阶连续可微，且初始值充分接近，则Müller方法是收敛的。若是方程(3.1.1)的单根，则Müller方法的收敛阶为1.84. 注2 在收敛性证明中虽然要求初始值充分接近根，但实际计算表明，抛物线法对初始值要求并不苛刻，在初值不太好的情形下常常也能收敛。它的缺点是程序比较复杂，并且在计算过程中，也常常采用复数运算，增加了工作量。因此，抛物线法适用于当初值不太好时求

39、方程(3.1.1)的复根的情况。3.7 非线性方程组的迭代法简介设非线性方程组(system of nonlinear equations) (3.7.1)其中是变量的元函数，且至少有一个是自变量的非线性函数。若记，则式(3.7.1)可写成 . (3.7.2)求解非线性方程组，从形式上，只要把单变量函数看成向量函数，就可将前面单个非线性方程的求根方法用于来求非线性方程组。下面主要介绍不动点迭代法、牛顿迭代法及拟牛顿迭代法。但因为非线性方程组(3.7.1)可能无解，有唯一解或无穷多解，所以有关它的求解问题一般要比单个非线性方程困难。3.7.1 解非线性方程组的不动点迭代法首先将式(3.7.2)改

40、写为, (3.7.3)其中向量函数为连续函数。如果向量满足，称为函数的不动点，也就是方程组(3.7.1)的一个解。由式(3.7.3)可构造不动点迭代法 (3.7.4)如果由它产生的向量序列满足，则为向量函数的不动点。例3.7.1 用不动点迭代法解下列非线性方程组解 将方程组改写成等价形式 (3.7.5) 记， ,则式(3.7.5)可写为.由此构造不动点迭代公式 (3.7.6)即取初始近似 ，按迭代公式(3.7.6)计算得近似值，见表3.7.1.表 3.7.1k012341000.80.92800000.97283170.98936560.999957100.80.93120000.973270

41、00.98943510.9999571 其收敛性类似于单个方程情况。定理3.7.1 设函数的定义域，且(1) 存在闭集，实数，对，有(2) 对，有则在有唯一的不动点，且对任意的，由迭代法(3.7.4)产生的向量序列收敛到，并有误差估计.例3.7.2 对于例3.7.1中的方程组，设，证明：对任意的初始点，由迭代法(3.7.6)生成的序列均收敛到.证 首先，对任意，可以验证.因此当，有.其次，对一切，都有 ，.从而有.根据定理3.7.1知，在上有唯一不动点，因此对任意的初始点，由迭代法(3.7.6)生成的序列均收敛到.定理3.7.2 设函数的定义域内有不动点，的分量函数有连续的偏导数，且谱半径 (

42、3.7.7)则存在的一个邻域，对任意的，迭代法(3.7.4)产生的序列收敛到. 其中的导数为Jacobi矩阵(Jacobi matrix).根据矩阵谱半径与1-范数的关系，可得到如下结论：对于定义在上的函数，若存在常数，使得当时，,则矩阵的谱半径.例如，对于例3.7.1，由可知，对一切，都有，其中，因此在内有，满足定理3.7.2的条件，故迭代序列局部收敛。3.7.2 解非线性方程组的Newton迭代法设向量是方程组(3.7.1)的解，向量是方程组的初始近似解，假定在可微，将在处作多元函数的Taylor展开，并取其线性部分：即其中为Jacobi矩阵在处的值.若Jacobi矩阵非奇异，则方程组有唯

43、一解.一般地，当非奇异时，可得Newton迭代法. (3.7.8) 在第k步计算过程中，不仅要算出雅可比矩阵，还要求逆矩阵，计算量较大。因此，通常把第 k 步迭代分成两步：记，则式(3.7.8)变为 (3.7.9)解此线性方程组，求出解向量后，再令，避免了求矩阵的逆。定理3.7.3 设的定义域，. 若有的开邻域，在其上连续，可逆，则(1) Newton迭代法产生的序列在的某个邻域上超线性收敛于；(2) 若再加上条件：存在常数，使，,则至少平方收敛。例3.7.3 用Newton迭代法解下列非线性方程组解 记，则.取初值，解方程组 ,即,可求得，然后计算得.类似地，可得，具体结果见表3.7.2.表

44、 3.7.2k0123400.80.99178720.99997521.000000000.80.99171170.99996851.0000000可见，Newton迭代法的收敛速度比不动点迭代法的收敛速度要快。3.7.3 解非线性方程组的拟Newton法 在求解非线性方程组(3.7.2)的Newton法中,是的Jacobi矩阵在处的值。当复杂时，的计算量较大，求解困难。在实际计算中，为减少计算量，避免每步都重新计算，类似于割线法的思想，构造, (3.7.10)新的满足： . (3.7.11)这表明矩阵关于点及具有差商性质；即当时，即为关于及的差商。但当时，并不确定。为此我们限制是由的一个低秩

45、修正矩阵得到的，即， (3.7.12)其中，是秩为的修正矩阵。对 称迭代算法 (3.7.13)为拟Newton迭代法(quasi Newton Iterative method)，称式(3.7.10)为拟Newton方程(quasi Newton equation)。此方法只需对给出的初始近似及矩阵，用迭代格式(3.7.13)逐次计算得到及，从而避免了每步都要计算的Jacobi阵，减少了计算量。根据的不同取法，可得到不同的拟Newton法。在拟Newton法中，若矩阵非奇异，可令，于是能得到与式(3.7.13)互逆的迭代格式：对 (3.7.14)可以看出，迭代格式(3.7.14)不用求逆就能逐

46、次递推算出，而迭代格式(3.7.8)需要求逆才能算出，因此在实际计算中可根据具体情况选用其中一种迭代格式。使用拟Newton法时，需要确定修正矩阵和;在此只介绍取的方法，称为秩1拟Newton法(single rank quasi Newton method).设 (3.7.15)待定. 记，则式(3.7.11)变为. (3.7.16)将式(3.7.15)代入式(3.7.12)，得.将其代入式(3.7.16)，得或.若，则有.将其代入式(3.7.15)，即得 (3.7.17)若取，即，由式(3.7.17)得 (3.7.18)于是得到一个秩1拟Newton法：对 (3.7.19)式(3.7.19

47、)称为Broyden秩1拟Newton法(single rank Broyden quasi Newton method).与式(3.7.19)互逆的Broyden秩1方法为：对 (3.7.20)其中. 式(3.7.20) 称为逆Broyden秩1拟Newton法(single rank inverse Broyden quasi Newton method).实际应用式(3.7.19)或(3.7.20)求方程组(3.1.1)的近似解时，只要选择较好的初始向量和初始矩阵和，一般可得到较好的近似解，迭代序列具有超线性收敛速度。例3.7.4 用逆Broyden秩1拟Newton法(3.7.20)求

48、下列方程组的解，取.解 . 因为，所以.取用式(3.7.20)进行迭代，可求得重复以上步骤，共迭代11次，得解若用Newton法(3.7.8)，取相同的初始近似，达到同一精度只需迭代7次，但它每步计算量比Broyden大得多。3.8 算法程序3.8.1 二分法 % 用二分法求非线性方程f(x)=0的根，fun为函数f(x)的表达式% a, b为左右端点，eps为精度，x为近似根，k为二分次数function Bisection(fun, a, b, eps)if nargin < 4 eps=1e-5; %如果输入自变量数目<4，默认eps=1e-5end fa=feval(fun,a); fb=feval(fun,b); % fa, fb分别表示a, b两个端点处的函数值if fa*fb>0 disp('无法判断a, b内是否有根，请重新调整');returnendk=0;while abs(b-a)/2>eps x = (a+b)/2; fx = feval(fun, x); if fx*fa < 0 b = x; fb = fx; else a = x; fa = fx; end k = k+1;endx = (a+b)/2;disp ( '