1、第第7 7章章 非线性方程求根非线性方程求根 7.1 7.1 方程求根与二分法方程求根与二分法 7.2 7.2 迭代法及其收敛性迭代法及其收敛性 7.3 7.3 迭代收敛的加速方法迭代收敛的加速方法 7.4 7.4 牛顿法牛顿法 7.5 7.5 弦截法与抛物线法弦截法与抛物线法 7.6 7.6 解非线性方程组的牛顿迭代法解非线性方程组的牛顿迭代法2022-12-317.1 7.1 方程求根与二分法方程求根与二分法 例如例如代数方程代数方程 x x5 5-x x3 3+2424x+x+1=0,1=0,超越方程超越方程 sin(5sin(5x x2 2)+e)+e-x x=0.=0.对于不高于对于
2、不高于4 4次的代数方程已有求根公式，而次的代数方程已有求根公式，而高于高于4 4次的代数方程则无精确的求根公式，至于超次的代数方程则无精确的求根公式，至于超越方程越方程 就更无法求出其精确的解，因此，如何求就更无法求出其精确的解，因此，如何求得满足一定精度要求的方程的近似根也就成为迫得满足一定精度要求的方程的近似根也就成为迫切需要解决的问题，为此，本章介绍几种常见的切需要解决的问题，为此，本章介绍几种常见的非线性方程的近似求根方法非线性方程的近似求根方法.2022-12-327.1.1 7.1.1 引言引言本章主要讨论本章主要讨论单变量非线性方程单变量非线性方程f f(x x)=0)=0 (
3、1.1)(1.1)的求根问题，这里的求根问题，这里x x R R,f f(x x)C C a a,b b.在科学与工程在科学与工程计算中有大量方程求根问题，其中一类特殊的问题计算中有大量方程求根问题，其中一类特殊的问题是多项式方程是多项式方程)2.1(),0()(01110 aaxaxaxaxfnnnn其中系数其中系数a ai i(i i=0,1,=0,1,n n)为实数为实数.2022-12-33方程方程f f(x x)=0)=0的的根根x x*，又称为函数又称为函数f f(x x)的的零点零点，它使得，它使得f f(x x*)=0)=0，若，若f f(x x)可分解为可分解为f f(x x
4、)=()=(x x-x x*)mmg g(x x)，其中其中mm为正整数，且为正整数，且g g(x x*)0)0.当当mm=1=1时，则称时，则称x x*为单为单根，若根，若mm11称称x x*为为(1.1)(1.1)的的mm重根重根，或，或x x*为函数为函数f f(x x)的的mm重零点重零点.若若x x*是是f f(x x)的的mm重零点重零点，且，且g g(x x)充分光滑，充分光滑，则则当当f f(x x)为代数多项式为代数多项式(1.2)(1.2)时，根据代数基本定理时，根据代数基本定理可知，可知，n n次代数方程次代数方程f f(x x)=0)=0在复数域有且只有在复数域有且只有
5、n n个根个根(含复根，含复根，mm重根为重根为mm个根个根).).0)(,0)()()()()1(xfxfxfxfmm2022-12-34n n=1,2=1,2时方程的根是大家熟悉的，时方程的根是大家熟悉的，n n=3,4=3,4时虽有时虽有求根公式但比较复杂，可在数学手册中查到，但已不求根公式但比较复杂，可在数学手册中查到，但已不适合数值计算，而适合数值计算，而n n 5 5时就不能用公式表示方程的根时就不能用公式表示方程的根.因此，通常对因此，通常对n n 3 3的多项式方程求根与一般连续函数的多项式方程求根与一般连续函数方程方程(1.1)(1.1)一样都可采用迭代法求根一样都可采用迭代
6、法求根.迭代法要求给出根迭代法要求给出根x x*的一个近似，若的一个近似，若f f(x x)C C a a,b b 且且f f(a a)f f(b b)00，根据连续函数性质中的介值定理可知，根据连续函数性质中的介值定理可知方程方程f f(x x)=0)=0在在(a a,b b)内至少有一个实根，这时称内至少有一个实根，这时称 a a,b b 为方程为方程(1.1)(1.1)的的有根区间有根区间，通常可通过，通常可通过逐次搜索法逐次搜索法求得求得方程方程(1.1)(1.1)的有根区间的有根区间.2022-12-35 若若 f f(x x)在在 a,ba,b 内连续内连续,且且 f f(a a)
7、f f(b b)0)0,(-)0,f f(0)(0)=10,10,f f(3)(3)=-260,-260(+)0.可见可见f f(x x)仅有两个实根仅有两个实根,分别位于分别位于(0,3),(3,+)(0,3),(3,+),又又f f(4)(4)=1010,所以第二根的隔根区间可缩小为所以第二根的隔根区间可缩小为(3,4)(3,4).以上分析可用下表表示以上分析可用下表表示x(-,0)0(0,3)3(3,4)4(4,+)f(x)f(x)-0+-0-+隔根区间隔根区间(0,3)(3,4)2022-12-382.2.逐步搜索法逐步搜索法 从区间从区间 a a,b b 的左端点的左端点 a a 出
8、发出发,按选定的步长按选定的步长h h 一步步向右搜索，若一步步向右搜索，若f f(a+jha+jh)f f(a+a+(j+j+1)1)h h)0 0 (j=j=0,1,20,1,2,)则区间则区间 a+jha+jh,a+a+(j+j+1)1)h h 内必有根内必有根.搜索过程也可从搜索过程也可从b b开始，这时应取步长开始，这时应取步长 h h00.2022-12-397.1.2 7.1.2 二分法二分法 设设f f(x x)在区间在区间 a a,b b 上连续上连续,f f(a a)f f(b b)0 0,则在则在 a a,b b 内有方程的根内有方程的根.取取 a a,b b 的中点的中
9、点 将区间一分为二将区间一分为二.若若 f f(x x0 0)=0 0,则则x x0 0就是方程的就是方程的根根,否则判别根否则判别根 x x*在在 x x0 0 的的左侧左侧还是还是右侧右侧.,)(210bax 若若f f(a a)f f(x x0 0)0)0,则则x x*(a a,x x0 0),令令 a a1 1=a=a,b b1 1=x x0 0;若若f f(x x0 0)f f(b b)0)0,则则x x*(x x0 0 ,b b),令令 a a1 1=x=x0 0,b b1 1=b b.不论出现哪种情况不论出现哪种情况,(a a1 1,b b1 1)均为均为新的有根区间新的有根区间
10、,它的它的长度只有原有根区间长度的一半长度只有原有根区间长度的一半,达到了达到了压缩有压缩有根区间根区间的目的的目的.2022-12-310 对压缩了的有根区间对压缩了的有根区间,又可实行同样的步骤又可实行同样的步骤,再再压缩压缩.如此反复进行如此反复进行,即可的一系列即可的一系列有根区间套有根区间套 ,11nnbababa 由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间 a an n,b bn n 的长度为的长度为)(ababnnn 21若每次二分时所取区间中点都不是根，则上述过程将若每次二分时所取区间中点都不是根，则上述过程将无限进行下去无限进行下去.当当
11、 n n 时，区间必将最终收缩为一时，区间必将最终收缩为一点点x x*，显然，显然x x*就是所求的就是所求的根根.2022-12-311 若取区间若取区间 a an n,b bn n 的中点的中点)(nnnbax 21作为作为x x*的近似值，则有下述的近似值，则有下述误差估计式误差估计式111*()()22nnnnxxbaba 只要只要 n n 足够大足够大,(,(即区间二分次数足够多即区间二分次数足够多)，误差就可，误差就可足够小足够小.),(,*11 nnnbaxx 由于在偶重根附近曲线由于在偶重根附近曲线 y=fy=f(x x)为上凹或下凸为上凹或下凸,即即 f f(a a)与与f
12、f(b b)的符号相同的符号相同,因此因此不能用二分法求偶重根不能用二分法求偶重根.2022-12-312 例例2 2 用二分法求例用二分法求例1 1中方程中方程 f f(x x)=x=x3 3-x x-1-1=0 0的实根的实根,要求误差不超过要求误差不超过0.0050.005.解解 由例由例1 1可知可知x x*(1,1.5)(1,1.5),要想满足题意，即：要想满足题意，即：则要则要005.021)15.1(21)(21211 nnnab|x x*-x xn n|0.005|0.005由此解得由此解得 取取n=6,按二分法计算过程见按二分法计算过程见下表下表,x6=1.3242 为所求之
13、近似根为所求之近似根.,6.512lg2 n2022-12-313n 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.3242-+-+-(1)f(a)0(2)根据精根据精 度要求，度要求，取到小数取到小数点后四位点后四位 即可即可.二分法的二分法的优点优点是算法简单，且总是收敛的，是算法简单，且总是收敛的，缺缺点点是收敛的太慢，故一般不单独将其用于求根，只是收敛的太慢，故一般不单独将其用
14、于求根，只是用其为根求得一个较好的近似值是用其为根求得一个较好的近似值.2022-12-314二分法的计算步骤二分法的计算步骤:步骤步骤1 1 准备准备 计算函数计算函数f f(x x)在区间在区间 a a,b b 端点处的端点处的值值f f(a a),f f(b b).若若f f(a a)f f(a a+b b)/2)/2)0 0,则以则以(a a+b b)/2)/2代替代替b b ，否则，否则以以(a a+b b)/2)/2代替代替a a.步骤步骤2 2 二分二分 计算函数计算函数f f(x x)在区间中点在区间中点(a a+b b)/2)/2处处的值的值f f(a a+b b)/2)/2
15、).步骤步骤3 3 判断判断 若若f f(a a+b b)/2)=0)/2)=0，则，则(a a+b b)/2)/2即是根，即是根，计算过程结束，否则检验计算过程结束，否则检验.反复执行步骤反复执行步骤2 2和步骤和步骤3 3，直到区间，直到区间 a a,b b 长度小长度小于允许误差于允许误差，此时中点，此时中点(a a+b b)/2)/2即为所求近似根即为所求近似根.2022-12-3157.2 7.2 迭代法及其收敛性迭代法及其收敛性7.2.1 7.2.1 不动点迭代法不动点迭代法 将方程将方程f f(x x)=0 0改写为等价方程形式改写为等价方程形式 x=x=(x x).(2.1).
16、(2.1)若要求若要求x x*满足满足f f(x x*)=0 0，则，则x x*=(x x*)；反之亦然，称；反之亦然，称x x*为为函数函数(x x)的一个的一个不动点不动点.求求f f(x x)的零点就等于求的零点就等于求(x x)的的不动点不动点，选择一个初始近似值，选择一个初始近似值x x0 0，将它代入，将它代入(2.1)(2.1)右端，右端，即可求得即可求得 x x1 1=(x x0 0).2022-12-316.lim xxkk可以如此反复迭代计算可以如此反复迭代计算 x xk k+1+1=(x xk k)(k k=0,1,2=0,1,2,).(2.2)(2.2)(x x)称为迭
17、代函数称为迭代函数.如果对任何如果对任何x x0 0a a,b b，由，由(2.2)(2.2)得得到的序列到的序列 x xk k 有极限有极限则称迭代方程则称迭代方程(2.2)(2.2)收敛收敛.且且x x*=(x x*)为为(x x)的的不动点不动点，故称故称(2.2)(2.2)为为不动点迭代法不动点迭代法.上述迭代法是一种逐次逼近法，其基本思想是将上述迭代法是一种逐次逼近法，其基本思想是将隐式方程隐式方程(2.1)(2.1)归结为一组显式的计算公式归结为一组显式的计算公式(2.2)(2.2)，迭，迭代过程实质上是一个逐步显式化过程代过程实质上是一个逐步显式化过程.2022-12-317当当
18、(x x)连续时，连续时，显然显然x x*就是方程就是方程x=x=(x x)之之根根(不动点不动点).于是可以从数列于是可以从数列 x xk k 中求得满足精度要求的近似根中求得满足精度要求的近似根.这种求根方法这种求根方法称为称为不动点迭代法不动点迭代法,1()(0,1,2,)kkxxk 称为称为迭代格式迭代格式,(x x)称为称为迭代函数迭代函数,x x0 0 称为称为迭代初值迭代初值,数列数列 x xk k 称为称为迭代序列迭代序列.如果迭代序列收敛如果迭代序列收敛,则称迭则称迭代格式代格式收敛收敛,否则称为否则称为发散发散.（几何意义的解释见书几何意义的解释见书p265p265页页）1
19、()(0,1,2,)kkxxk .lim xxkk2022-12-318 03224xxx分别按以上三种形式建立迭代公式，并取分别按以上三种形式建立迭代公式，并取x x0 0=1 1进行进行迭代计算，结果如下：迭代计算，结果如下：14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 解解 对方程进行如下三种变形：对方程进行如下三种变形：例例3 3 用迭代法求方程用迭代法求方程x x4 4+2+2x x2 2-x x-3=0-3=0 在区间在区间1,1,1.21.2内的实根内的实根.2022-12-319准确根准确根 x x*=1.1241230291.124123029,
20、可见可见迭代公式不同迭代公式不同,收敛收敛情况也不同情况也不同.第二种公式比第一种公式收敛快得多第二种公式比第一种公式收敛快得多,而第三种公式而第三种公式不收敛不收敛.73496,8.49530710 xx12()41kkkxxx 4213()23kkkkxxxx 12411()(32)kkkkxxxx 26271.124123xx671.124123xx 参见书参见书p266p266页页-例例3 3.2022-12-320 例例3 3表明原方程化为表明原方程化为(2.1)(2.1)的形式不同，有的收的形式不同，有的收敛，有的不收敛，有的发散，只有收敛的的迭代过敛，有的不收敛，有的发散，只有收
21、敛的的迭代过程程(2.2)(2.2)才有意义，为此我们首先要研究才有意义，为此我们首先要研究(x x)的不定的不定点的存在性及迭代法点的存在性及迭代法(2.2)(2.2)的收敛性的收敛性.2022-12-3217.2.2 7.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察首先考察(x x)在在 a a,b b 上不动点的存在唯一性上不动点的存在唯一性.定理定理1 1 设设(x x)CCa a,b b 满足以下两个条件：满足以下两个条件：1 1 对任意对任意x x a a,b b 有有a a (x x)b b.)4.2(.)()(yxLyx 2 2 存在正数存在正
22、数L L1 a a及及(b b)00,f f(b b)=(b b)-b b00,由连续函数性质可知存在由连续函数性质可知存在 x x*(a a,b b)使使 f f(x x*)=0=0，即即x x*=(x x*)，x x*即为即为(x x)的不动点的不动点.再证不动点的再证不动点的唯一性唯一性.设设x x1 1*,x x2 2*a a,b b 都是都是(x x)的不动点，则由的不动点，则由(2.4)(2.4)得得.)()(21212121 xxxxLxxxx 引出矛盾，故引出矛盾，故(x x)的不动点只能是唯一的的不动点只能是唯一的.证毕证毕.在在(x x)的不动点存在唯一的情况下，可得到迭代
23、的不动点存在唯一的情况下，可得到迭代法法(2.2)(2.2)收敛的一个收敛的一个充分条件充分条件.2022-12-323 定理定理2 2 设设(x x)CCa a,b b 满足定理满足定理1 1中的两个条件，中的两个条件，则对任意则对任意x x0 0a a,b b，由，由(2.2)(2.2)得到的迭代序列得到的迭代序列 x xk k 收敛收敛到的不动点到的不动点x x*，并有，并有误差估计式误差估计式)6.2(.1)5.2(.1101kkkkkxxLLxxxxLLxx 证明证明 设设x x*a a,b b 是是(x x)在在 a a,b b 上的唯一不动点上的唯一不动点,由条件由条件1 1，可
24、知，可知 x xk k a a,b b，再由，再由(2.4)(2.4)得得.)()(011xxLxxLxxxxkkkk 因因00L L111时称时称超线性收敛超线性收敛，p p=2=2时称时称平方收敛平方收敛.2022-12-333 定理定理4 4 对于迭代过程对于迭代过程x xk k+1+1=(x xk k)，如果，如果(p p)(x x)在在所求根所求根x x*的邻近连续，并且的邻近连续，并且)8.2(.0)(,0)()()()()1(xxxxpp 则该迭代过程在则该迭代过程在x x*的邻近是的邻近是p p阶收敛的阶收敛的.证明证明 由于由于(x x*)=0)=0，根据定理，根据定理3 3
25、立即可以断定迭立即可以断定迭代过程代过程x xk k+1+1=(x xk k)具有局部收敛性具有局部收敛性.再将再将(x xk k)在根在根x x*处做泰勒展开处做泰勒展开,利用条件利用条件(2.4),(2.4),则则有有.,)(!)()()()(之间之间与与在在 xxxxpxxkpkpk 注意到注意到(x xk k)=)=x xk k+1+1，(x x*)=)=x x*，由上式得，由上式得2022-12-334,)(!)()(1pkpkxxpxx 因此对迭代误差，令因此对迭代误差，令k k时有时有这表明迭代过程这表明迭代过程x xk k+1+1=(x xk k)确实为确实为p p阶收敛阶收敛
26、.证毕证毕.!)()(1pxeeppkk 上述定理告诉我们，迭代过程的收敛速度依赖于上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数迭代函数(x x)的选取的选取.如果如果x xa a,b b 但但 (x x)0 0时，则时，则该迭代过程只可能是线性收敛该迭代过程只可能是线性收敛.对例对例4 4的讨论见书的讨论见书p272p272.2022-12-335)0(aa的三阶方法的三阶方法.假设假设 x x0 0 充分靠近充分靠近 x x*,求求31)(limkkkxaxa 证明证明 首先由泰勒展式可得首先由泰勒展式可得113311limlim()()3!4()kkkkkkaxeaeaax 例子例
27、子 证明迭代公式证明迭代公式 x xk+k+1 1=x xk k(x xk k2 2+3 3a a)/(3)/(3x xk k2 2+a a)是是求求而而1/41/4a a00，故此迭代公式是三阶方法故此迭代公式是三阶方法.2022-12-3367.3 7.3 迭代收敛的加速方法迭代收敛的加速方法7.3.1 7.3.1 埃特金加速收敛方法埃特金加速收敛方法 对于收敛的迭代过程，只要迭代足够多次，就可对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大，因此迭代过程的加速是慢，从而使计算量变
28、得很大，因此迭代过程的加速是个重要的课题个重要的课题.设设x x0 0是根是根x x*的某个近似值的某个近似值,用迭代公式校正一次得用迭代公式校正一次得 x x1 1=(x x0 0)而由微分中值定理，有而由微分中值定理，有.),)()()(0001之间之间与与在在xxxxxxxx 2022-12-337假设假设 (x x)改变不大改变不大,近似地取某个近似值近似地取某个近似值L L,则有则有由于由于 x x2 2-x x*L L(x x1 1-x x*).)1.3().(01 xxLxx 若将校正值若将校正值x x1 1=(x x0 0)再校正一次，又得再校正一次，又得 x x2 2=(x
29、x1 1)将它与将它与(3.1)(3.1)式联立，消去未知的式联立，消去未知的L L，有，有 xxxxxxxx1021由此推知由此推知.2)(201220100122120 xxxxxxxxxxxxx 2022-12-338.0lim1 xxxxkkk在计算了在计算了x x1 1及及x x2 2之后，可用上式右端作为之后，可用上式右端作为x x*的新近似的新近似,记作记作x x1 1，一般情形是由，一般情形是由x xk k计算计算x xk k+1+1,x xk k+2+2，记，记它表明序列它表明序列 x xk k 的收敛速度比的收敛速度比 x xk k 的收敛速度快的收敛速度快.)2.3().
30、,1,0()(2)(2212211 kxxxxxxxxxxkkkkkkkkkk (3.1)(3.1)式称为式称为埃特金埃特金(Aitken)(Aitken)2 2加速方法加速方法.可以证明可以证明2022-12-339也称为也称为埃特金埃特金 (Aitken)(Aitken)外推法外推法.可以证明可以证明:)(1kkxx 为线性收敛为线性收敛,则埃特金法为平方收敛则埃特金法为平方收敛；这个加速迭代法也可写成下面格式这个加速迭代法也可写成下面格式(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 为为
31、 p p(p p 1)1)阶收敛，阶收敛，)(x 导数连续，则埃特金法为导数连续，则埃特金法为 2 2p p11 阶收敛阶收敛.的的 p p 阶阶若若2022-12-340 例题例题 求方程求方程 x x=e e xx 在在 x x=0.5=0.5 附近的根附近的根.解解 取取 x x0 0=0.5=0.5,迭代格式迭代格式x x2525=x x2626=0.5671433=0.5671433 若对此格式用埃特金法若对此格式用埃特金法,则则kxkex 1 得得(1)1(1)(2)12(2)(1)2(2)1111(2)(1)11()2kkxxkkkkkkkkkxexexxxxxxx 2022-1
32、2-341(2)(1)2(2)1111(2)(1)11()2kkkkkkkxxxxxxx 仍取仍取 x x0 0=0.5=0.5,得得5671433.05671433.05671433.05671433.05672979.05668708.05676279.05452392.06065307.03)2(3)1(32)2(2)1(21)2(1)1(1 xxxxxxxxx由此可见由此可见,埃特金法加速收敛效果是相当显著的埃特金法加速收敛效果是相当显著的.(1)1(1)(2)12kkxxkkxexe 2022-12-3427.3.2 7.3.2 斯蒂芬森斯蒂芬森(Steffensen)(Steffe
33、nsen)迭代法迭代法 埃特金方法埃特金方法不管原序列不管原序列 x xk k 是怎样产生的，对是怎样产生的，对 x xk k 进行加速计算，得到序列进行加速计算，得到序列 x xk k.如果把如果把埃特金加速技埃特金加速技巧与不定点迭代结合巧与不定点迭代结合，则可得到如下的迭代法：，则可得到如下的迭代法：),(),(kkkkyzxy )3.3().,1,0(2)(21 kxyzxyxxkkkkkkk称为称为斯蒂芬森斯蒂芬森(Steffensen)(Steffensen)迭代法迭代法.它可以这样理解，它可以这样理解，我们要求我们要求x x=(x x)的根的根x x*，令误差，令误差(x x)=
34、)=(x x)-x x，有等式，有等式(x x*)=)=(x x*)-x x*=0=0，已知，已知x x*的近似值的近似值x xk k及及y yk k，其误差分，其误差分别为别为2022-12-343,)()(kkkkkxyxxx .)()(kkkkkyzyyy 把误差把误差(x x)“外推到零外推到零”，即过，即过(x xk k,(x xk k)及及(y yk k,(y yk k)两点做线性插值函数，它与两点做线性插值函数，它与x x轴交点就是轴交点就是(3.3)(3.3)中的中的x xk k+1+1，即方程，即方程.0)()()()(kkkkkkxxxyxyx 的解的解)()()()()(
35、kkkkkkxyxyxxx .2)(12 kkkkkkkxxyzxyx2022-12-344么么么么方面么么么么方面 Sds绝对是假的绝对是假的 实际上实际上(3.3)(3.3)是将不定点迭代法是将不定点迭代法(2.2)(2.2)计算两步合计算两步合并成一步得到的，可将它写成另一种不动点迭代并成一步得到的，可将它写成另一种不动点迭代)4.3(),1,0()(1 kxxkk)5.3(.)(2)()()(2xxxxxxx 其中其中 对不动点迭代对不动点迭代(3.5)(3.5)有以下局部收敛性定理有以下局部收敛性定理.定理定理5 5 若若x x*为为(3.5)(3.5)定义的迭代函数定义的迭代函数(
36、x x)的不动的不动点，则点，则x x*为为(x x)的不定点的不定点.反之，若反之，若x x*为为(x x)的不动的不动点，设点，设(x x)存在，存在，(x x)11，则，则x x*是是(x x)的不动点，的不动点，且且斯蒂芬森迭代法斯蒂芬森迭代法(3.3)(3.3)是是2 2阶收敛的阶收敛的.证明可见证明可见2.2.2022-12-346 例例5 5 见书见书p274.p274.例例6 6 见书见书p275.p275.2022-12-3477.4 7.4 牛牛 顿顿 法法7.4.1 7.4.1 牛顿法及其收敛性牛顿法及其收敛性)()()(000 xxxfxfxf 对于方程对于方程f f(
37、x x)=0)=0，如果，如果f f(x x)是线性函数，则它的是线性函数，则它的求根是容易的求根是容易的.牛顿法实质上是一种线性化方法，其牛顿法实质上是一种线性化方法，其基本思想是将非线性方程基本思想是将非线性方程f f(x x)=0)=0逐步归结为某种线性逐步归结为某种线性方程来求解方程来求解.设已知方程设已知方程f f(x x)=0)=0有近似根有近似根x x0 0，且在，且在 x x0 0附近附近f f(x x)可用一阶泰勒多项式近似，表示为可用一阶泰勒多项式近似，表示为2022-12-348当当f f(x x0 0)0)0时，方程时，方程f f(x x)=0)=0可用线性方程可用线性
38、方程(切线切线)近似近似代替，即代替，即 f f(x x0 0)+)+f f(x x0 0)()(x x-x x0 0)=0)=0.(4.1)(4.1)解此线性方程得解此线性方程得)()(000 xfxfxx 得迭代公式得迭代公式此式称为此式称为牛顿牛顿(Newton)(Newton)迭代公式迭代公式.)2.4(),1,0()()(1 kxfxfxxkkkk2022-12-349牛顿法有显然的牛顿法有显然的几何意义几何意义，方程，方程f f(x x)=0)=0的根的根x x*可可解释为曲线解释为曲线y y=f f(x x)与与x x轴交点的横坐标轴交点的横坐标.设设x xk k是根是根x x*
39、的的某个近似值，过曲线某个近似值，过曲线y y=f f(x x)上横坐标为上横坐标为x xk k的点的点P Pk k引切引切线，并将该切线与线，并将该切线与x x轴交点的横坐标轴交点的横坐标x xk k+1+1作为作为x x*的新的的新的近似值近似值.注意到切线方程为注意到切线方程为这样求得的值这样求得的值x xk k+1+1必满足必满足(4.1),(4.1),从而就是牛顿公式从而就是牛顿公式(4.2)(4.2)的计算结果的计算结果.由于这由于这种几何背景，所以牛顿迭种几何背景，所以牛顿迭代法也称代法也称切线法切线法.xyx*xky y=f f(x x)x xk k+1+1P Pk kP Pk
40、 k+1+1x xk k+2+2).)()(kkkxxxfxfy 2022-12-350牛顿迭代法的收敛性牛顿迭代法的收敛性)()()(xfxfxx 设设x x*是是f f(x x)的一个单根，即的一个单根，即f f(x x*)=0)=0，f f(x x*)0)0,有有.0)()()(,0)()()()(2*xfxfxxfxfxfx 牛顿迭代法的迭代函数为牛顿迭代法的迭代函数为由定理由定理4 4的的(2.9)(2.9)式可得式可得(4.3)(4.3)式式.0)(2)()(!21)()(lim)(lim22!2121 xfxfxxxxxxxxxkkkkkk 2022-12-351由此得到，当由此
41、得到，当x x*为为单根单根时，牛顿迭代法在根时，牛顿迭代法在根x x*的的邻近是邻近是二阶二阶(平方平方)收敛收敛的的.关于关于x x*为为重根重根时，牛顿迭代法在根时，牛顿迭代法在根x x*的邻近的收的邻近的收敛性在后面讨论敛性在后面讨论.定理定理(局部收敛性局部收敛性)设设f f C C2 2 a a,b b,若若x x*为为f f(x x)在在 a a,b b 上的根，且上的根，且f f(x x*)0 0，则存在，则存在x x*的邻域的邻域U U,使得任取使得任取初值初值x x0 0 U U，牛顿法产生的序列，牛顿法产生的序列 x xk k 收敛到收敛到x x*，且满足，且满足即有下面
42、的局部收敛性定理即有下面的局部收敛性定理.)(2)()(lim21 xfxfxxxxkkk2022-12-352 解解 将原方程化为将原方程化为x x e e x x=0=0，则，则牛顿迭代公式为牛顿迭代公式为kkxxkkkeexxx 11取取 x x0 0=0.5=0.5，迭代得，迭代得x x1 1=0.566311,=0.566311,x x2 2=0.5671431,=0.5671431,x x3 3=0.5671433=0.5671433.f f(x x)=)=x x e e x x，f f(x x)=1+)=1+e e x x，例例7 7 用牛顿迭代法求方程用牛顿迭代法求方程x x=
43、e e x x在在x=x=0.50.5附近的根附近的根.参见书参见书p277p277的的例例7 7.牛顿法的计算步骤见书牛顿法的计算步骤见书p278.p278.2022-12-3537.4.2 7.4.2 牛顿法应用举例牛顿法应用举例对于给定的正数对于给定的正数C C，应用牛顿法解二次方程，应用牛顿法解二次方程,02 Cx我们现在证明，这种迭代公式对于任意初值我们现在证明，这种迭代公式对于任意初值x x0 000都是收敛的都是收敛的.可导出求开方值可导出求开方值 的计算程序的计算程序C.21)()()(,)(2 xCxxfxfxxCxxf)5.4(.211 kkkxCxx2022-12-354
44、事实上，对事实上，对(4.5)(4.5)式施行配方整理，易知式施行配方整理，易知 .2121CxxCxkkk 以上两式相除得以上两式相除得.211 CxCxCxCxkkkk据此反复递推有据此反复递推有)6.4(.200kCxCxCxCxkk 2022-12-355记记.200kCxCxq 整理整理(4.6)(4.6)式，得式，得.1222kkqqCCxk 对任意初值对任意初值x00，总有，总有|q|1，故由上式推知，当，故由上式推知，当k时时 ，即迭代过程恒收敛，即迭代过程恒收敛.Cxk参见书参见书p279p279的的例例8 8.2022-12-3567.4.3 7.4.3 简化牛顿法与牛顿下
45、山法简化牛顿法与牛顿下山法牛顿法的牛顿法的优点优点是收敛快，是收敛快，缺点缺点每步迭代要计算每步迭代要计算f f(x xk k)及及f f(x xk k)，计算量较大，且有时，计算量较大，且有时f f(x xk k)计算较困难；计算较困难；初始近似值初始近似值x x0 0只在根只在根x x*附近才能保证收敛，如附近才能保证收敛，如x x0 0给给的不合适可能不收敛的不合适可能不收敛.为克服这两个缺点，通常可用为克服这两个缺点，通常可用下述方法下述方法.(1)(1)简化牛顿法简化牛顿法，也称，也称平行弦法平行弦法，其迭代公式为，其迭代公式为)7.4(.,1,0,0)(1 kCxCfxxkkk迭代
46、函数为迭代函数为 (x x)=)=x x-CfCf(x x).2022-12-357若若|(x xk k)|=|1-)|=|1-CfCf(x x)|1)|1，即取，即取00CfCf(x x)2)2.在根在根x x*附近成立，则迭代法附近成立，则迭代法(4.7)(4.7)局部收敛局部收敛.在在(4.7)(4.7)中取中取C C=1/=1/f f(x x0 0)，则称为简化牛顿法，这，则称为简化牛顿法，这类方法计算量省，但只有线性收敛，其类方法计算量省，但只有线性收敛，其几何意义几何意义是用是用平行弦与平行弦与x x轴交点作为轴交点作为x x*的近似，见下图的近似，见下图.y=f(x)x0 x1x
47、2x*2022-12-358(2)(2)牛顿下山法牛顿下山法,牛顿法收敛性依赖初值牛顿法收敛性依赖初值x x0 0的选取的选取,如果如果x x0 0偏离所求根偏离所求根x x*较远较远,则牛顿法可能发散则牛顿法可能发散.Newtons MethodNewtons Method收敛性依赖于收敛性依赖于x x0 0的选取的选取.x x*x0 x0 x02022-12-359例如例如，用牛顿法求解方程，用牛顿法求解方程 x x3 3-x x-1=0-1=0.(4.8).(4.8)此方程在此方程在x x=1.5=1.5附近的一个根附近的一个根x x*.设取迭代初值设取迭代初值x x0 0=1.5=1.
48、5，用牛顿迭代法公式，用牛顿迭代法公式 )9.4(.131231 kkkkkxxxxx计算得计算得 x x1 1=1.34783=1.34783,x x2 2=1.32520=1.32520,x x3 3=1.32472=1.32472.迭代迭代3 3次得到的结果次得到的结果x x3 3有有6 6位有效数字位有效数字.但是，如取但是，如取x x0 0=0.6=0.6，用，用(4.9)(4.9)式迭代式迭代1 1次得次得 计算得计算得 x x1 1=17.9=17.9.这个结果反而比这个结果反而比x x0 0=0.6=0.6更偏离了所求的根更偏离了所求的根x x*=1.32472=1.32472
49、.2022-12-360为了防止迭代发散，我们对迭代过程再附加一项为了防止迭代发散，我们对迭代过程再附加一项要求，即具有单调性要求，即具有单调性.)10.4(.)()(1kkxfxf 满足这项要求的算法称为满足这项要求的算法称为下山法下山法.我们将牛顿法与下山法结合起来使用，即在下山我们将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛法保证函数值稳定下降的前提下，用牛顿法加快收敛速度速度.为此，我们将牛顿法的结果为此，我们将牛顿法的结果)()(1kkkkxfxfxx 与前一项的近似值与前一项的近似值x xk k适当加权平均作为新的改进值适当加权平均作为新的改
50、进值)11.4(,)1(11kkkxxx 2022-12-361其中其中(0(0 1)1)称为称为下山因子下山因子，(4.11)(4.11)即为即为)12.4().,1,0()()(1 kxfxfxxkkkk 称为称为牛顿下山法牛顿下山法.选择下山因子时从选择下山因子时从=1 1开始，逐次将开始，逐次将 减半进行试减半进行试算，直到能使下降条件算，直到能使下降条件(4.10)(4.10)成立为止成立为止.若用此法解方程若用此法解方程(4.8)(4.8)，当，当x x0 0=0.6=0.6时由时由(4.9)(4.9)式求式求得得x x1 1=17.9=17.9，它不满足条件，它不满足条件(4.1
