1、1第第7章章 非线性方程与方程组的数非线性方程与方程组的数值解法值解法 7.1 方程求根与二分法方程求根与二分法 7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 7.3 迭代收敛的加速方法迭代收敛的加速方法 7.4 牛顿法牛顿法 7.5 弦截法与抛物线法弦截法与抛物线法 7.6 非线性方程组的数值解法非线性方程组的数值解法2 例如例如代数方程代数方程 x5-x3+24x+1=0,超越方程超越方程 sin(5x2)+e-x=0.对于不高于对于不高于4次的代数方程已有求根公式，而次的代数方程已有求根公式，而高于高于4次的代数方程则无精确的求根公式，至于超次的代数方程则无精确的求根公式，至于超
2、越方程越方程 就更无法求出其精确的解，因此，就更无法求出其精确的解，因此，如何求如何求得满足一定精度要求的方程的近似根得满足一定精度要求的方程的近似根也就成为迫也就成为迫切需要解决的问题，为此，本章介绍几种常见的切需要解决的问题，为此，本章介绍几种常见的非线性方程的近似求根方法非线性方程的近似求根方法.引言引言3主要讨论主要讨论单变量非线性方程单变量非线性方程f(x)=0 (1.1)的求根问题，这里的求根问题，这里xR,f(x)Ca,b.在科学与工程在科学与工程计算中有大量方程求根问题，其中一类特殊的问题计算中有大量方程求根问题，其中一类特殊的问题是多项式方程是多项式方程)2.1(),0()(
3、01110aaxaxaxaxfnnnn其中系数其中系数ai(i=0,1,n)为实数为实数.4方程方程f(x)=0的的根根x*，又称为函数又称为函数f(x)的的零点零点，它使得，它使得f(x*)=0，若，若f(x)可分解为可分解为f(x)=(x-x*)mg(x)，其中其中m为正整数，且为正整数，且g(x*)0.当当m=1时，则称时，则称x*为单为单根，若根，若m1称称x*为为(1.1)的的m重根重根，或，或x*为函数为函数f(x)的的m重零点重零点.若若x*是是f(x)的的m重零点重零点，且，且g(x)充分光滑，则充分光滑，则当当f(x)为代数多项式为代数多项式(1.2)时，根据代数基本定理时，
4、根据代数基本定理可知，可知，n次代数方程次代数方程f(x)=0在复数域有且只有在复数域有且只有n个根个根(含含复根，复根，m重根为重根为m个根个根).0)(,0)()()()()1(xfxfxfxfmm5n=1,2时方程的根是大家熟悉的，时方程的根是大家熟悉的，n=3,4时虽有求时虽有求根公式但比较复杂，可在数学手册中查到，但已不适根公式但比较复杂，可在数学手册中查到，但已不适合数值计算，而合数值计算，而n5时就不能用公式表示方程的根时就不能用公式表示方程的根.因因此，通常对此，通常对n3的多项式方程求根与一般连续函数方的多项式方程求根与一般连续函数方程程(1.1)一样都可采用迭代法求根一样都
5、可采用迭代法求根.迭代法要求给出根迭代法要求给出根x*的一个近似，若的一个近似，若f(x)Ca,b且且f(a)f(b)0，根据连续函数性质中的介值定理可知方，根据连续函数性质中的介值定理可知方程程f(x)=0在在(a,b)内至少有一个实根，这时称内至少有一个实根，这时称a,b为方为方程程(1.1)的的有根区间有根区间.例例1 判断方程判断方程 f(x)=x3-x-1=0的有根区间的有根区间.x00.511.52f(x)-+6 设设f(x)在区间在区间a,b上连续上连续,f(a)f(b)0,则在则在a,b 内有方程的根内有方程的根.取取a,b的中点的中点 将区间一分为二将区间一分为二.若若 f(
6、x0)=0,则则x0就是方程的根就是方程的根,否则判别根否则判别根 x*在在 x0 的的左侧左侧还是还是右侧右侧.,)(210bax 若若f(a)f(x0)0,则则x*(a,x0),令令 a1=a,b1=x0;若若f(x0)f(b)0,则则x*(x0,b),令令 a1=x0,b1=b.不论出现哪种情况不论出现哪种情况,(a1,b1)均为均为新的有根区间新的有根区间,它它的的长度只有原有根区间长度的一半长度只有原有根区间长度的一半,达到了达到了压缩有根压缩有根区间区间的目的的目的.7.1 方程求根与二分法方程求根与二分法7 对压缩了的有根区间对压缩了的有根区间,又可实行同样的步骤又可实行同样的步
7、骤,再压再压缩缩.如此反复进行如此反复进行,即可的一系列即可的一系列有根区间套有根区间套 ,11nnbababa 由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间an,bn的长度为的长度为)(ababnnn 21若每次二分时所取区间中点都不是根，则上述过程将若每次二分时所取区间中点都不是根，则上述过程将无限进行下去无限进行下去.当当 n 时，区间必将最终收缩为一时，区间必将最终收缩为一点点x*，显然，显然x*就是所求的就是所求的根根.8abx0 x2abWhen to stop?11xxkk 2)(xf 或或不能保证不能保证 x 的精度的精度x*2xx*9 若取
8、区间若取区间an,bn的中点的中点)(nnnbax 21作为作为x*的近似值，则有下述的近似值，则有下述误差估计式误差估计式111*()()22nnnnxxbaba 只要只要 n 足够大足够大,(即区间二分次数足够多即区间二分次数足够多)，误差就可，误差就可足够小足够小.),(,*11 nnnbaxx 由于在偶重根附近曲线由于在偶重根附近曲线 y=f(x)为上凹或下凸为上凹或下凸,即即 f(a)与与f(b)的符号相同的符号相同,因此因此不能用二分法求偶重根不能用二分法求偶重根.10 例例2 用二分法求例用二分法求例1中方程中方程 f(x)=x3-x-1=0的实根的实根,要求误差不超过要求误差不
9、超过0.005.解解 由例由例1可知可知x*(1,1.5),要想满足题意，即：要想满足题意，即：则要则要005.021)15.1(21)(21211 nnnab|x*-xn|0.005由此解得由此解得 取取n=6,按二分法计算过程见按二分法计算过程见下表下表,x6=1.3242 为所求之近似根为所求之近似根.,6.512lg2 n11n an bn xn f(xn)说明说明01234561.01.251.251.31251.31251.31251.32031.51.51.3751.3751.34381.32811.32811.251.3751.31251.34381.32811.32031.3
10、242-+-+-(1)f(a)0(2)根据精根据精 度要求，取度要求，取到小数点后到小数点后四位四位 即可即可.二分法的二分法的优点优点是算法简单，且总是收敛的，是算法简单，且总是收敛的，缺缺点点是收敛的太慢，故一般不单独将其用于求根，只是收敛的太慢，故一般不单独将其用于求根，只是用其为根求得一个较好的近似值是用其为根求得一个较好的近似值.12逐步搜索法逐步搜索法 从区间从区间a,b的左端点的左端点 a 出发出发,按选定的步长按选定的步长h 一步步向右搜索，若一步步向右搜索，若f(a+jh)f(a+(j+1)h)0 (j=0,1,2,)则区间则区间a+jh,a+(j+1)h内必有根内必有根.搜
11、索过程也可从搜索过程也可从b开开始，这时应取步长始，这时应取步长 h0.137.2 不动点迭代法及其收敛性不动点迭代法及其收敛性7.2.1 不动点迭代法不动点迭代法 将方程将方程f(x)=0改写为等价方程形式改写为等价方程形式 x=(x).(2.1)若要求若要求x*满足满足f(x*)=0，则，则x*=(x*)；反之亦然，称；反之亦然，称x*为为函数函数(x)的一个的一个不动点不动点.求求f(x)的零点就等于求的零点就等于求(x)的的不动点不动点，选择一个初始近似值，选择一个初始近似值x0，将它代入，将它代入(2.1)右端，右端，即可求得即可求得 x1=(x0).14.lim xxkk可以如此反
12、复迭代计算可以如此反复迭代计算 xk+1=(xk)(k=0,1,2,).(2.2)(x)称为迭代函数称为迭代函数.如果对任何如果对任何x0a,b，由，由(2.2)得得到的序列到的序列xk有极限有极限则称迭代方程则称迭代方程(2.2)收敛收敛.且且x*=(x*)为为(x)的的不动点不动点，故称故称(2.2)为为不动点迭代法不动点迭代法.15当当(x)连续时，连续时，显然显然x*就是方程就是方程x=(x)之之根根(不动点不动点).于是可以从数列于是可以从数列xk中求得满足精度要求的近似根中求得满足精度要求的近似根.这种求根方法这种求根方法称为称为不动点迭代法不动点迭代法,1()(0,1,2,)kk
13、xxk 称为称为迭代格式迭代格式,(x)称为称为迭代函数迭代函数,x0 称为称为迭代初值迭代初值,数列数列xk称为称为迭代序列迭代序列.如果迭代序列收敛如果迭代序列收敛,则称迭则称迭代格式代格式收敛收敛,否则称为否则称为发散发散.（几何意义的解释见下几何意义的解释见下页页）1()(0,1,2,)kkxxk .lim xxkk16xyy=xxyy=xxyy=xxyy=xx*x*x*x*x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p117 03224xxx分别按以上三种形式建立迭代公式，并取分别按以上三种形式建立迭代公式，并取x0=1进行进行迭代计算，结果如下：迭代计算
14、，结果如下：14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 解解 对方程进行如下三种变形：对方程进行如下三种变形：例例1 用迭代法求方程用迭代法求方程x4+2x2-x-3=0 在区间在区间1,1.2内的实根内的实根.18准确根准确根 x*=1.124123029,可见可见迭代公式不同迭代公式不同,收敛情收敛情况也不同况也不同.第二种公式比第一种公式收敛快得多第二种公式比第一种公式收敛快得多,而而第三种公式第三种公式不收敛不收敛.73496,8.495307 10 xx12()41kkkxxx 4213()23kkkkxxxx 12411()(32)kkkkxxxx
15、26271.124123xx671.124123xx19 当方程有多个解时，同一个迭代法的当方程有多个解时，同一个迭代法的不同初值不同初值也也可能收敛到可能收敛到不同的根不同的根.20 例例1 表明原方程化为表明原方程化为 x=(x)的形式不同，有的的形式不同，有的收敛，有的不收敛，有的发散收敛，有的不收敛，有的发散.例例2 表明同一个迭代法的不同初值可能收敛到表明同一个迭代法的不同初值可能收敛到不同的根不同的根.只有收敛的的迭代过程才有意义，为此我们首只有收敛的的迭代过程才有意义，为此我们首先要研究先要研究(x)的不定点的存在性及迭代法的收敛性的不定点的存在性及迭代法的收敛性.217.2.2
16、 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察首先考察(x)在在a,b上不动点的存在唯一性上不动点的存在唯一性.定理定理1 设设(x)Ca,b满足以下两个条件：满足以下两个条件：1 对任意对任意xa,b有有a(x)b.)4.2(.)()(yxLyx 2 存在正数存在正数La及及(b)0,f(b)=(b)-b0,由连续函数性质可知存在由连续函数性质可知存在 x*(a,b)使使 f(x*)=0，即，即x*=(x*)，x*即为即为(x)的不动点的不动点.再证不动点的再证不动点的唯一性唯一性.设设x1*,x2*a,b都是都是(x)的不动点，则由的不动点，则由(2.4)得得.)
17、()(21212121 xxxxLxxxx 引出矛盾，故引出矛盾，故(x)的不动点只能是唯一的的不动点只能是唯一的.证毕证毕.在在(x)的不动点存在唯一的情况下，可得到迭代的不动点存在唯一的情况下，可得到迭代法法(2.2)收敛的一个收敛的一个充分条件充分条件.23 定理定理2 设设(x)Ca,b满足定理满足定理1中的两个条件，中的两个条件，则对任意则对任意x0a,b，由，由(2.2)得到的迭代序列得到的迭代序列xk收敛收敛到的不动点到的不动点x*，并有，并有误差估计式误差估计式)6.2(.1)5.2(.1101kkkkkxxLLxxxxLLxx 证明证明 设设x*a,b是是(x)在在a,b上的
18、唯一不动点上的唯一不动点,由条件由条件1，可知，可知xka,b，再由，再由(2.4)得得.)()(011xxLxxLxxxxkkkk 因因0L1时称时称超线性收敛超线性收敛，p=2时称时称平方收敛平方收敛.33 定理定理4 对于迭代过程对于迭代过程xk+1=(xk)，如果，如果(p)(x)在在所求根所求根x*的邻近连续，并且的邻近连续，并且)8.2(.0)(,0)()()()()1(xxxxpp 则该迭代过程在则该迭代过程在x*的邻近是的邻近是p阶收敛的阶收敛的.证明证明 由于由于(x*)=0，根据定理，根据定理3立即可以断定迭立即可以断定迭代过程代过程xk+1=(xk)具有局部收敛性具有局部
19、收敛性.再将再将(xk)在根在根x*处做泰勒展开处做泰勒展开,利用条件利用条件(2.8),则有则有.,)(!)()()()(之间之间与与在在 xxxxpxxkpkpk 注意到注意到(xk)=xk+1，(x*)=x*，由上式得，由上式得34,)(!)()(1pkpkxxpxx 因此对迭代误差，令因此对迭代误差，令k时有时有这表明迭代过程这表明迭代过程xk+1=(xk)确实为确实为p阶收敛阶收敛.证毕证毕.!)()(1pxeeppkk 上述定理告诉我们，迭代过程的收敛速度依赖于上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数迭代函数(x)的选取的选取.如果如果xa,b但但 (x)0时，则时，则该
20、迭代过程只可能是线性收敛该迭代过程只可能是线性收敛.357.3 迭代收敛的加速方法迭代收敛的加速方法7.3.1 埃特金加速收敛方法埃特金加速收敛方法 对于收敛的迭代过程，只要迭代足够多次，就可对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大，因此迭代过程的加速是慢，从而使计算量变得很大，因此迭代过程的加速是个重要的课题个重要的课题.设设x0是根是根x*的某个近似值的某个近似值,用迭代公式校正一次得用迭代公式校正一次得 x1=(x0)而由微分中值定理，有而由微分中值定理，有.),)()(
21、)(0001之间之间与与在在xxxxxxxx 36假设假设 (x)改变不大改变不大,近似地取某个近似值近似地取某个近似值L,则有则有由于由于 x2-x*L(x1-x*).)1.3().(01 xxLxx 若将校正值若将校正值x1=(x0)再校正一次，又得再校正一次，又得 x2=(x1)将它与将它与(3.1)式联立，消去未知的式联立，消去未知的L，有，有 xxxxxxxx1021由此推知由此推知.2)(201220100122120 xxxxxxxxxxxxx 37 Aitken 加速加速：xyy=xy=(x)x*x0P(x0,x1)x1x2x P(x1,x2)21020102)(xxxxxxx
22、 一般地有：一般地有：2112()2KKKKKKKxxxxxxx .),(,),(,),(),(,34123012010 xxxxxxxxxxx比比 收敛得略快。收敛得略快。kxkx38.0lim1 xxxxkkk在计算了在计算了x1及及x2之后，可用上式右端作为之后，可用上式右端作为x*的新近似的新近似,记作记作x1，一般情形是由，一般情形是由xk计算计算xk+1,xk+2，记，记它表明序列它表明序列xk的收敛速度比的收敛速度比xk的收敛速度快的收敛速度快.()()(.)(,).kkkkkkkkkkkkkxxxxxxxxxxxxxk221211221213 2220 1(3.2)式称为式称为
23、埃特金埃特金(Aitken)2加速方法加速方法.可以证明可以证明39也称为也称为埃特金埃特金(Aitken)外推法外推法.可以证明可以证明:)(1kkxx 为线性收敛为线性收敛,则埃特金法为平方收敛则埃特金法为平方收敛；这个加速迭代法也可写成下面格式这个加速迭代法也可写成下面格式(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 为为 p(p 1)阶收敛，阶收敛，)(x 导数连续，则埃特金法为导数连续，则埃特金法为 2p1 阶收敛阶收敛.的的 p 阶阶若若40例题例题 求方程求方程 x=e x 在在
24、 x=0.5 附近的根附近的根.解解 取取 x0=0.5,迭代格式迭代格式x25=x26=0.5671433 若对此格式用埃特金法若对此格式用埃特金法,则则kxkex 1 得得(1)1(1)(2)11(2)(1)2(2)1111(2)(1)11()2kkxxkkkkkkkkkxexexxxxxxx 41(2)(1)2(2)1111(2)(1)11()2kkkkkkkxxxxxxx 仍取仍取 x0=0.5,得得5671433.05671433.05671433.05671433.05672979.05668708.05676279.05452392.06065307.03)2(3)1(32)2(
25、2)1(21)2(1)1(1 xxxxxxxxx由此可见由此可见,埃特金法加速收敛效果是相当显著的埃特金法加速收敛效果是相当显著的.(1)1(1)(2)11kkxxkkxexe 427.3.2 斯蒂芬森斯蒂芬森(Steffensen)迭代法迭代法 埃特金方法埃特金方法不管原序列不管原序列xk是怎样产生的，对是怎样产生的，对xk进行加速计算，得到序列进行加速计算，得到序列xk.如果把如果把埃特金加速技埃特金加速技巧与不动点迭代结合巧与不动点迭代结合，则可得到如下的迭代法：，则可得到如下的迭代法：),(),(kkkkyzxy )3.3().,1,0(2)(21 kxyzxyxxkkkkkkk称为称
26、为斯蒂芬森斯蒂芬森(Steffensen)迭代法迭代法.43 实际上实际上(3.3)是将不定点迭代法计算两步合并成一是将不定点迭代法计算两步合并成一步得到的，可将它写成另一种不动点迭代步得到的，可将它写成另一种不动点迭代)4.3(),1,0()(1 kxxkk)5.3(.)(2)()()(2xxxxxxx 其中其中 对不动点迭代对不动点迭代(3.5)有以下局部收敛性定理有以下局部收敛性定理.定理定理5 若若x*为为(3.5)定义的迭代函数定义的迭代函数(x)的不动点，的不动点，则则x*为为(x)的不定点的不定点.反之，若反之，若x*为为(x)的不动点，的不动点，设设(x)存在，存在，(x)1，
27、则，则x*是是(x)的不动点，且的不动点，且斯斯蒂芬森迭代法蒂芬森迭代法(3.3)是是2阶收敛的阶收敛的.44457.4 牛顿法牛顿法7.4.1 牛顿法及其收敛性牛顿法及其收敛性)()()(000 xxxfxfxf 对于方程对于方程f(x)=0，如果，如果f(x)是线性函数，则它的是线性函数，则它的求根是容易的求根是容易的.牛顿法实质上是一种线性化方法，其牛顿法实质上是一种线性化方法，其基本思想是基本思想是将非线性方程将非线性方程f(x)=0逐步归结为某种线性逐步归结为某种线性方程来求解方程来求解.设已知方程设已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一阶
28、泰勒多项式近似，表示为用一阶泰勒多项式近似，表示为46当当f(x0)0时，方程时，方程f(x)=0可用线性方程可用线性方程(切线切线)近似代近似代替，即替，即 f(x0)+f(x0)(x-x0)=0.(4.1)解此线性方程得解此线性方程得)()(000 xfxfxx 得迭代公式得迭代公式此式称为此式称为牛顿牛顿(Newton)迭代公式迭代公式.)2.4(),1,0()()(1 kxfxfxxkkkk47牛顿法有显然的牛顿法有显然的几何意义几何意义，方程，方程f(x)=0的根的根x*可可解释为曲线解释为曲线y=f(x)与与x轴交点的横坐标轴交点的横坐标.设设xk是根是根x*的的某个近似值，过曲线
29、某个近似值，过曲线y=f(x)上横坐标为上横坐标为xk的点的点Pk引切引切线，并将该切线与线，并将该切线与x轴交点的横坐标轴交点的横坐标xk+1作为作为x*的新的的新的近似值近似值.注意到切线方程为注意到切线方程为这样求得的值这样求得的值xk+1必满足必满足(4.1),从而就是牛顿公式从而就是牛顿公式(4.2)的计算结果的计算结果.由于这由于这种几何背景，所以牛顿迭种几何背景，所以牛顿迭代法也称代法也称切线法切线法.xyx*xky=f(x)xk+1PkPk+1xk+2).)()(kkkxxxfxfy )2.4(),1,0()()(1 kxfxfxxkkkk48牛顿迭代法的收敛性牛顿迭代法的收敛
30、性)()()(xfxfxx 设设x*是是f(x)的一个的一个单根单根，即，即f(x*)=0，f(x*)0,有有.0)()()(,0)()()()(2*xfxfxxfxfxfx 牛顿迭代法的迭代函数为牛顿迭代法的迭代函数为由定理由定理4的的(2.9)式可得式可得.0)(2)()(!21)()(lim)(lim22!2121 xfxfxxxxxxxxxkkkkkk 49由此得到，当由此得到，当x*为为单根单根时，牛顿迭代法在根时，牛顿迭代法在根x*的的邻近是邻近是二阶二阶(平方平方)收敛收敛的的.关于关于x*为为重根重根时，牛顿迭代法在根时，牛顿迭代法在根x*的邻近的收的邻近的收敛性在后面讨论敛性
31、在后面讨论.定理定理(局部收敛性局部收敛性)设设f C2a,b,若若x*为为f(x)在在a,b上的根，且上的根，且f(x*)0，则存在，则存在x*的邻域的邻域U,使得任取初使得任取初值值x0 U，牛顿法产生的序列，牛顿法产生的序列xk收敛到收敛到x*，且满足，且满足即有下面的局部收敛性定理即有下面的局部收敛性定理.)(2)()(lim21 xfxfxxxxkkk50 解解 将原方程化为将原方程化为xex=0，则，则牛顿迭代公式为牛顿迭代公式为kkxxkkkeexxx 11取取 x0=0.5，迭代得，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.f(x)=xe
32、x，f(x)=1+ex，例例7 用牛顿迭代法求方程用牛顿迭代法求方程x=ex在在x=0.5附近的根附近的根.517.4.2 牛顿法应用举例牛顿法应用举例对于给定的正数对于给定的正数C，应用牛顿法解二次方程，应用牛顿法解二次方程,02 Cx我们现在证明，这种迭代公式对于任意初值我们现在证明，这种迭代公式对于任意初值x00都是收敛的都是收敛的.可导出求开方值可导出求开方值 的计算程序的计算程序C.21)()()(,)(2 xCxxfxfxxCxxf)5.4(.211 kkkxCxx52事实上，对事实上，对(4.5)式施行配方整理，易知式施行配方整理，易知 .2121CxxCxkkk 以上两式相除得
33、以上两式相除得.211 CxCxCxCxkkkk据此反复递推有据此反复递推有)6.4(.200kCxCxCxCxkk 53记记.200kCxCxq 整理整理(4.6)式，得式，得.1222kkqqCCxk 对任意初值对任意初值x00，总有，总有|q|1，故由上式推知，当，故由上式推知，当k时时 ，即迭代过程，即迭代过程恒收敛恒收敛.Cxk54Newtons Method 收敛性依赖于初值收敛性依赖于初值x0 的选取。的选取。x*x0 x0 x0557.4.3 简化牛顿法简化牛顿法牛顿法的牛顿法的优点优点是收敛快，是收敛快，缺点缺点每步迭代要计算每步迭代要计算f(xk)及及f(xk)，计算量较大
34、，且有时，计算量较大，且有时f(xk)计算较困难；计算较困难；初始近似值初始近似值x0只在根只在根x*附近才能保证收敛，如附近才能保证收敛，如x0给给的不合适可能不收敛的不合适可能不收敛.为克服这两个缺点，通常可用为克服这两个缺点，通常可用下述方法下述方法.简化牛顿法简化牛顿法，也称，也称平行弦法平行弦法，其迭代公式为，其迭代公式为)7.4(.,1,0,0)(1 kCxCfxxkkk迭代函数为迭代函数为 (x)=x-Cf(x).56若若|(xk)|=|1-Cf(x)|1，即取，即取0Cf(x)0)重根重根时，则时，则f(x)可表为可表为 f(x)=(x-x*)mg(x).其中其中g(x*)0，
35、此时用牛顿迭代法，此时用牛顿迭代法(4.2)求求x*仍然收敛，仍然收敛，只是只是收敛速度将大大减慢收敛速度将大大减慢.事实上，因为迭代公式事实上，因为迭代公式)()()()()()()(*1kkkkkkkkkkxgxxxmgxgxxxxfxfxx 令令ek=xkx*，则，则)()()(*11kkkkkkkkxgexmgxgeexxe 58可见用牛顿法求方程的重根时仅为可见用牛顿法求方程的重根时仅为线性收敛线性收敛.011)()()(1limlim1 mxgexmgxgeekkkkkkkk从而有从而有两种两种提高求重根的收敛速度提高求重根的收敛速度的的方法方法：1)取如下迭代函数取如下迭代函数.
36、0)(,)()()(xxfxfmxx 则则)13.4().,1,0()()(1 kxfxfmxxkkkk得到迭代公式得到迭代公式求求m重根重根具有具有2阶收敛阶收敛.但要知道但要知道x*的的重数重数m.59对对f(x)=(x-x*)mg(x),g(x*)0，令函数，令函数.)()()()()()()()(xgxxxmgxgxxxfxfx 则为求则为求(x)=0的单根的单根x*的问题，对它用牛顿法是的问题，对它用牛顿法是二阶二阶(平方平方)收敛的收敛的.其迭代函数为其迭代函数为2)将求重根问题化为求单根问题将求重根问题化为求单根问题（去重数）（去重数）.)()()()()()()()(2xfxf
37、xfxfxfxxxxx )14.4().,1,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk从而构造出迭代方法为从而构造出迭代方法为60例例8 用牛顿迭代法求函数用牛顿迭代法求函数 f(x)=(x-1)sin(x-1)+3x-x3+1=0 在在0.95附近之根附近之根.解解 取取x0=0.95 用牛顿迭用牛顿迭代法求得的代法求得的xk见右表见右表.可见可见xk收敛很慢收敛很慢.kxk01234560.950.97442790.98705830.99348780.99673280.99835760.999190161由重根数由重根数m=2,用用(4.13)式加速法，作式加
38、速法，作求得求得 x0=0.95,x1=0.9988559,x2=x3=1.收敛速度大大加快于直接用牛顿迭代公式收敛速度大大加快于直接用牛顿迭代公式.1()()kkkkf xxxmfx 627.5 弦截法与抛物线法弦截法与抛物线法用牛顿法求方程用牛顿法求方程f(x)=0的根，每步除计算的根，每步除计算f(xk)外外还要算还要算f(xk)，当函数，当函数f(x)比较复杂时，计算比较复杂时，计算f(x)往往往往比较困难，为此可以利用已求函数值比较困难，为此可以利用已求函数值f(xk),f(xk-1),来来回避导数值回避导数值f(xk)的计算的计算.这类方法是建立在插值原理这类方法是建立在插值原理基
39、础上的，下面介绍两种常用方法基础上的，下面介绍两种常用方法.637.5.1 割线割线(弦截弦截)法法设设xk,xk-1是是f(x)=0的近似根，我们利用的近似根，我们利用f(xk),f(xk-1)构造一次插值多项式构造一次插值多项式p1(x)，并用，并用p1(x)=0的根作为方程的根作为方程f(x)=0的新的近似根的新的近似根xk+1，由于，由于)1.5().()()()()(111kkkkkkxxxxxfxfxfxp 因此有因此有().(.)()()kkkkkkkxxxxf xf xf x1115 264这样导出的迭代公式这样导出的迭代公式(5.2)可以看做牛顿公式可以看做牛顿公式.)()(
40、1kkkkxfxfxx 11)()(kkkkxxxfxf中的导数中的导数 用用差商差商 取代的结果取代的结果.)(kxf (5.2)式有明显的式有明显的几何意义几何意义：设曲线设曲线y=f(x)上横坐标为上横坐标为xk-1和和xk的点分别为的点分别为Pk-1和和Pk,则差商则差商 表示弦表示弦 的斜率的斜率,弦弦 的方程为的方程为11)()(kkkkxxxfxfkkPP1 kkPP1()()()()kkkkkkf xf xyf xx xxx1165Ox*xk+1xkPkxk-1yxPk-1因此，按因此，按(5.2)式求得式求得xk+1实际上是两点弦实际上是两点弦线线 与与x轴交点轴交点的横坐标
41、的横坐标(令令y=0解出解出x即可即可).这种算法因此这种算法因此而形象地称为而形象地称为割线割线(弦截弦截)法法.kkPP1 66割线法与牛顿法割线法与牛顿法(切线法切线法)都是线性化分法，但两都是线性化分法，但两者有本质的区别者有本质的区别.牛顿法在计算牛顿法在计算xk+1时只用到前一步的时只用到前一步的值值xk，而割线法要用到前面两步的结果，而割线法要用到前面两步的结果xk-1,xk，因此，因此使用这种方法必须先给出两个开始值使用这种方法必须先给出两个开始值x0,x1.定理定理6 假设假设f(x)在根在根x*的邻域内的邻域内:|x-x*|具有具有二阶连续导数，且对任意二阶连续导数，且对任
42、意x 有有f(x)0，所取的初，所取的初值值x0,x1，那么当邻域，那么当邻域充分小时，弦截法充分小时，弦截法(5.2)将将按阶按阶15618.21.p收敛到收敛到x*.这里这里p是方程是方程2-1=0的正根的正根.67因为因为(5.2)式用到前两点式用到前两点xk-1和和xk的值，故此方法的值，故此方法又称为又称为双点割线法双点割线法.().()()kkkkkxxxxf xf xf x010每步只用一个新点每步只用一个新点xk的值，此方法称为的值，此方法称为单点割线法单点割线法.如果把如果把(5.2)式中的式中的xk-1改为改为x0，即迭代公式为，即迭代公式为68例题例题 用牛顿迭代法和割线
43、法求方程用牛顿迭代法和割线法求方程 f(x)=x4+2x2x3=0，在区间在区间(1,1.5)内之根内之根(误差为误差为10-9).解解 取取x0=1.5，用牛顿法，用牛顿法,可得可得x6=1.12412303030取取x0=1.5,x1=1，用，用双点割线法双点割线法，迭代，迭代6次得到同样的次得到同样的结果，而采用结果，而采用单点割线法单点割线法，则迭代，则迭代18次得次得 x18=1.124123029.697.5.2 抛物线法抛物线法设已知方程设已知方程f(x)=0的三个近似根的三个近似根xk,xk-1,xk-2，我们，我们以这三点为节点构造二次插值多项式以这三点为节点构造二次插值多项
44、式p2(x)，并适当选，并适当选取取p2(x)的一个零点的一个零点xk+1作为新的近似根，这样确定的作为新的近似根，这样确定的迭代过程称为迭代过程称为抛物线法抛物线法，亦称为，亦称为密勒密勒(Mller)法法.在在几何图形上几何图形上,这种方法的基本思想是用抛物线这种方法的基本思想是用抛物线y=p2(x)与与x轴的交点轴的交点xk+1作为所求根作为所求根x*的近似位置的近似位置.70Ox*xk+1xky=P2(x)xk-2yxy=f(x)xk-1抛物线法的抛物线法的几何意义几何意义见下面图形见下面图形.71现在推导抛物线法的计算公式现在推导抛物线法的计算公式.插值多项式插值多项式).)(,)(
45、,)()(12112 kkkkkkkkkxxxxxxxfxxxxfxfxp有两个零点有两个零点,().kkkkkkkkf xxf xxxxx1121().(.)(),kkkkkkkkkf xxxf xf xxx121225 34式中式中72为了在为了在(5.3)式定出一个值式定出一个值xk+1，我们需要讨论根，我们需要讨论根式前正负号的取舍问题式前正负号的取舍问题.在在xk,xk-1,xk-2三个近似值中，自然假定三个近似值中，自然假定xk更接近更接近所求的根所求的根x*，这时，为了保证精度，我们选，这时，为了保证精度，我们选(5.3)式中式中接近接近xk的一个值作为新的近似根的一个值作为新的
46、近似根xk+1.为此，为此，只要取根只要取根式前的符号与式前的符号与的符号相同的符号相同.().(sgn(),kkkkkkkkkkf xxxf xf xxx12122473 例例 用抛物线法求解方程用抛物线法求解方程f(x)=xex-1=0.解解 取取x0=0.5,x1=0.6,x2=0.56532开始，计算得开始，计算得f(x0)=-0.175639,f(x1)=0.093271,f(x2)=-0.005031.fx1,x0=2.68910,fx2,x1=2.83373,fx2,x1,x0=2.21418.故故.75694.2)(,1201212 xxxxxfxxf 代入代入(5.3)式求得
47、式求得.56714.0,)(4)(201222223 xxxfxfxfxx 74事实上事实上,在一定条件下可以证明在一定条件下可以证明,对于抛物线法，对于抛物线法，迭代误差有下列渐近关系式迭代误差有下列渐近关系式.)(6)(42.0840.11 xfxfeekk由此式可见抛物线法也是超线性收敛的，其收敛的阶由此式可见抛物线法也是超线性收敛的，其收敛的阶是是p=1.840(是方程是方程3-2-1=0的根的根)，收敛速度比割线，收敛速度比割线法更接近于牛顿法法更接近于牛顿法.757.6 解非线性方程组的数值解法解非线性方程组的数值解法考察方程组考察方程组)1.6(.0),(.,0),(111 nn
48、nxxfxxf其中其中f1,fn均为均为(x1,xn)的多元函数的多元函数.若用向量记若用向量记号记号记x=(x1,xn)TRn,F=(f1,fn)T,(6.1)就可写成就可写成 F(x)=0.(6.2)76当当n2，且，且 f1,fn 中至少有一个是自变量中至少有一个是自变量 x1,xn 的的非线性函数，则称方程组非线性函数，则称方程组(6.1)为为非线性方程组非线性方程组.非线非线性方程组求根问题是前面介绍的方程性方程组求根问题是前面介绍的方程(即即n=2)求根的直求根的直接推广，实际上只要把前面介绍的接推广，实际上只要把前面介绍的单变量函数单变量函数f(x)看看成成向量函数向量函数F(x
49、)，则可得，则可得向量方程向量方程(6.2)的一个近似根的一个近似根x(k)=(x1(k),xn(k)T，将函数，将函数F(x)的分量的分量fi(x)(i=1,n)在在x(k)用多元函数泰勒展开，并取其线性部分，则可表示用多元函数泰勒展开，并取其线性部分，则可表示为为.).)()()()()()(kkkxxxFxFxF 77令上式右端为零，得到线性方程组令上式右端为零，得到线性方程组)3.6().()()()()(kkkxFxxxF 其中其中)4.6(.)()()()()()()()()()(12221212111 nnnnnnnxxfxxfxxfxxfxxfxxfxxfxxfxxfxF78称
50、为称为F(x)的的雅可比雅可比(Jacobi)矩阵矩阵.求解线性方程组求解线性方程组(6.3)，并记解为并记解为x(k+1)，则得，则得)5.6().,1,0()()()(1)()()1(kxFxFxxkkkk这就是这就是解非线性方程组解非线性方程组(6.2)的的牛顿迭代法牛顿迭代法.79例例 求解方程组求解方程组 .052),(,032),(222121221211xxxxfxxxxf给定初值给定初值x(0)=(1.5,1.0)T，用牛顿法求解，用牛顿法求解.解解 先求先求Jacobi矩阵矩阵.1422821)(,2421)(1212121 xxxxxFxxxF80用牛顿法用牛顿法(6.5)
