数值分析ppt非线性方程求根公开课一等奖优质课大赛微课获奖课件.pptx

上页上页下页下页第第7章章 非线性方程求根非线性方程求根7.1 方程求根与二分法方程求根与二分法7.2 迭代法及其收敛性迭代法及其收敛性7.3 迭代收敛加速办法迭代收敛加速办法7.4 牛顿法牛顿法7.5 弦截法与抛物线法弦截法与抛物线法7.6 解非线性方程组牛顿迭代法解非线性方程组牛顿迭代法第1页第1页上页上页下页下页7.1 方程求根与二分法方程求根与二分法 比如比如代数方程代数方程 x5-x3+24x+1=0,超越方程超越方程 sin(5x2)+e-x=0.对于不高于对于不高于4次代数方程已有求根公式，而高次代数方程已有求根公式，而高于于4次代数方程则无准确求根公式，至于超越方程次代数方程则无准确求根公式，至于超越方程 就更无法求出其准确解，因此，如何求得满足一就更无法求出其准确解，因此，如何求得满足一定精度要求方程近似根也就成为迫切需要处理问定精度要求方程近似根也就成为迫切需要处理问题，为此，本章简介几种常见非线性方程近似求题，为此，本章简介几种常见非线性方程近似求根办法根办法.第2页第2页上页上页下页下页7.1.1 引言引言本章主要讨论本章主要讨论单变量非线性方程单变量非线性方程f(x)=0 (1.1)求根问题，这里求根问题，这里xR,f(x)Ca,b.在科学与工程计在科学与工程计算中有大量方程求根问题，其中一类特殊问题是多项算中有大量方程求根问题，其中一类特殊问题是多项式方程式方程其中系数其中系数ai(i=0,1,n)为实数为实数.第3页第3页上页上页下页下页方程方程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)时，依据代数基本定理时，依据代数基本定理可知，可知，n次代数方程次代数方程f(x)=0在复数域有且只有在复数域有且只有n个根个根(含含复根，复根，m重根为重根为m个根个根).第4页第4页上页上页下页下页n=1,2时方程根是大家熟悉，时方程根是大家熟悉，n=3,4时虽有求根公时虽有求根公式但比较复杂，可在数学手册中查到，但已不适合数式但比较复杂，可在数学手册中查到，但已不适合数值计算，而值计算，而n5时就不能用公式表示方程根时就不能用公式表示方程根.因此，通因此，通常对常对n3多项式方程求根与普通连续函数方程多项式方程求根与普通连续函数方程(1.1)同同样都可采用迭代法求根样都可采用迭代法求根.迭代法要求给出根迭代法要求给出根x*一个近似，若一个近似，若f(x)Ca,b且且f(a)f(b)0，依据连续函数性质中介值定理可知方程，依据连续函数性质中介值定理可知方程f(x)=0在在(a,b)内至少有一个实根，这时称内至少有一个实根，这时称a,b为方程为方程(1.1)有根区间有根区间，通常可通过，通常可通过逐次搜索法逐次搜索法求得方程求得方程(1.1)有根区间有根区间.第5页第5页上页上页下页下页 若若 f(x)在在a,b内连续内连续,且且 f(a)f(b)0,f(0)=10,f(3)=-260.可见可见f(x)仅有两个实根仅有两个实根,分别位于分别位于(0,3),(3,+),又又f(4)=10,因此第二根隔根区间可缩小为因此第二根隔根区间可缩小为(3,4).以上分析可用下表表示以上分析可用下表表示x(-,0)0(0,3)3(3,4)4(4,+)f(x)f(x)-0+-0-+隔根区间隔根区间(0,3)(3,4)第8页第8页上页上页下页下页2.逐步搜索法逐步搜索法 从区间从区间a,b左端点左端点 a 出发出发,按选定步长按选定步长h 一一步步向右搜索，若步步向右搜索，若f(a+jh)f(a+(j+1)h)0 (j=0,1,2,)则区间则区间a+jh,a+(j+1)h内必有根内必有根.搜索过程也可从搜索过程也可从b开始，这时应取步长开始，这时应取步长 h0.第9页第9页上页上页下页下页7.1.2 二分法二分法 设设f(x)在区间在区间a,b上连续上连续,f(a)f(b)0,则在则在a,b 内有方程根内有方程根.取取a,b中点中点 将区间一分为二将区间一分为二.若若 f(x0)=0,则则x0就是方程根就是方程根,不然判别根不然判别根 x*在在 x0 左侧左侧还是还是右侧右侧.若若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)均为均为新有根区间新有根区间,它它长度只有原有根区间长度二分之一长度只有原有根区间长度二分之一,达到了达到了压缩有根压缩有根区间区间目的目的.第10页第10页上页上页下页下页 对压缩了有根区间对压缩了有根区间,又可实行同样环节又可实行同样环节,再压缩再压缩.如此重复进行如此重复进行,即可一系列即可一系列有根区间套有根区间套 由于每一区间都是前一区间二分之一，因此区间由于每一区间都是前一区间二分之一，因此区间an,bn长度为长度为若每次二分时所取区间中点都不是根，则上述过程将若每次二分时所取区间中点都不是根，则上述过程将无限进行下去无限进行下去.当当 n 时，区间必将最后收缩为一时，区间必将最后收缩为一点点x*，显然，显然x*就是所求就是所求根根.第11页第11页上页上页下页下页 若取区间若取区间an,bn中点中点作为作为x*近似值，则有下述近似值，则有下述误差预计式误差预计式只要只要 n 足够大足够大,(即区间二分次数足够多即区间二分次数足够多)，误差就，误差就可足够小可足够小.由于在偶重根附近曲线由于在偶重根附近曲线 y=f(x)为上凹或下凸为上凹或下凸,即即 f(a)与与f(b)符号相同符号相同,因此因此不能用二分法求偶重根不能用二分法求偶重根.第12页第12页上页上页下页下页 例例2 用二分法求例用二分法求例1中方程中方程 f(x)=x3-x-1=0实根实根,要要求误差不超出求误差不超出0.005.解解 由例由例1可知可知x*(1,1.5),要想满足题意，即：要想满足题意，即：则要则要|x*-xn|0.005由此解得由此解得 取取n=6,按二分法计算过程按二分法计算过程见下表见下表,x6=1.3242 为所求之近似根为所求之近似根.第13页第13页上页上页下页下页n 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页第14页上页上页下页下页二分法计算环节二分法计算环节:环节环节1 准备准备 计算函数计算函数f(x)在区间在区间a,b端点处值端点处值f(a),f(b).若若f(a)f(a+b)/2)0,则以则以(a+b)/2代替代替b，不然以，不然以(a+b)/2代替代替a.环节环节2 二分二分 计算函数计算函数f(x)在区间中点在区间中点(a+b)/2处处值值f(a+b)/2).环节环节3 判断判断 若若f(a+b)/2)=0，则，则(a+b)/2即是根，即是根，计算过程结束，不然检查计算过程结束，不然检查.重复执行环节重复执行环节2和环节和环节3，直到区间，直到区间a,b长度小长度小于允许误差于允许误差，此时中点，此时中点(a+b)/2即为所求近似根即为所求近似根.第15页第15页上页上页下页下页7.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).第16页第16页上页上页下页下页能够如此重复迭代计算能够如此重复迭代计算 xk+1=(xk)(k=0,1,2,).(2.2)(x)称为迭代函数称为迭代函数.假如对任何假如对任何x0a,b，由，由(2.2)得得到序列到序列xk有极限有极限则称迭代方程则称迭代方程(2.2)收敛收敛.且且x*=(x*)为为(x)不动点不动点，故称故称(2.2)为为不动点迭代法不动点迭代法.上述迭代法是一个逐次迫近法，其基本思想是将上述迭代法是一个逐次迫近法，其基本思想是将隐式方程隐式方程(2.1)归结为一组显式计算公式归结为一组显式计算公式(2.2)，迭代过，迭代过程实质上是一个逐步显式化过程程实质上是一个逐步显式化过程.第17页第17页上页上页下页下页当当(x)连续时，连续时，显然显然x*就是方程就是方程x=(x)之之根根(不动点不动点).于是能够从数列于是能够从数列xk中求得满足精度要求近似根中求得满足精度要求近似根.这种求根办法这种求根办法称为称为不动点迭代法不动点迭代法,称为称为迭代格式迭代格式,(x)称为称为迭代函数迭代函数,x0 称为称为迭代初值迭代初值,数列数列xk称为称为迭代序列迭代序列.假如迭代序列收敛假如迭代序列收敛,则称迭则称迭代格式代格式收敛收敛,不然称为不然称为发散发散.（几何意义解释见书几何意义解释见书p265页页）第18页第18页上页上页下页下页分别按以上三种形式建立迭代公式，并取分别按以上三种形式建立迭代公式，并取x0=1进行进行迭代计算，结果下列：迭代计算，结果下列：解解 对方程进行下列三种变形：对方程进行下列三种变形：例例3 用迭代法求方程用迭代法求方程x4+2x2-x-3=0 在区间在区间1,1.2内实根内实根.第19页第19页上页上页下页下页准确根 x*=1.124123029,可见迭代公式不同,收敛情况也不同.第二种公式比第一个公式收敛快得多,而第三种公式不收敛.参见书参见书p266页页-例例3.第20页第20页上页上页下页下页 例3表明原方程化为(2.1)形式不同，有收敛，有不收敛，有发散，只有收敛迭代过程(2.2)才故意义，为此我们首先要研究(x)不定点存在性及迭代法(2.2)收敛性.第21页第21页上页上页下页下页7.2.2 不动点存在性与迭代法收敛性不动点存在性与迭代法收敛性 首先考察首先考察(x)在在a,b上不动点存在唯一性上不动点存在唯一性.定理定理1 设设(x)Ca,b满足下列两个条件：满足下列两个条件：1 对任意对任意xa,b有有a(x)b.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)得得引出矛盾，故引出矛盾，故(x)不动点只能是唯一不动点只能是唯一.证毕证毕.在在(x)不动点存在唯一情况下，可得到迭代法不动点存在唯一情况下，可得到迭代法(2.2)收敛一个收敛一个充足条件充足条件.第23页第23页上页上页下页下页 定理定理2 设设(x)Ca,b满足定理满足定理1中两个条件，中两个条件，则对任意则对任意x0a,b，由，由(2.2)得到迭代序列得到迭代序列xk收敛收敛到不动点到不动点x*，并有，并有误差预计式误差预计式 证实证实 设设x*a,b是是(x)在在a,b上唯一不动点上唯一不动点,由条件由条件1，可知，可知xka,b，再由，再由(2.4)得得因因0L1时称时称超线性收敛超线性收敛，p=2时称时称平方收敛平方收敛.第33页第33页上页上页下页下页 定理定理4 对于迭代过程对于迭代过程xk+1=(xk)，假如，假如(p)(x)在在所求根所求根x*邻近连续，并且邻近连续，并且则该迭代过程在则该迭代过程在x*邻近是邻近是p阶收敛阶收敛.证实证实 由于由于(x*)=0，依据定理，依据定理3马上能够断定迭马上能够断定迭代过程代过程xk+1=(xk)含有局部收敛性含有局部收敛性.再将再将(xk)在根在根x*处做泰勒展开处做泰勒展开,利用条件利用条件(2.4),则有则有注意到注意到(xk)=xk+1，(x*)=x*，由上式得，由上式得第34页第34页上页上页下页下页因此对迭代误差，令因此对迭代误差，令k时有时有这表明迭代过程这表明迭代过程xk+1=(xk)确实为确实为p阶收敛阶收敛.证毕证毕.上述定理告诉我们，迭代过程收敛速度依赖于迭上述定理告诉我们，迭代过程收敛速度依赖于迭代函数代函数(x)选取选取.假如假如xa,b但但 (x)0时，则该时，则该迭代过程只也许是线性收敛迭代过程只也许是线性收敛.对例对例4讨论见书讨论见书p272.第35页第35页上页上页下页下页三阶办法三阶办法.假设假设 x0 充足靠近充足靠近 x*,求求 证实证实 首先由泰勒展式可得首先由泰勒展式可得 例子例子 证实迭代公式证实迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求是求而而1/4a00，故此故此迭代公式是三阶办法迭代公式是三阶办法.第36页第36页上页上页下页下页7.3 迭代收敛加速办法迭代收敛加速办法7.3.1 埃特金加速收敛办法埃特金加速收敛办法 对于收敛迭代过程，只要迭代足够多次，就能够对于收敛迭代过程，只要迭代足够多次，就能够使结果达到任意精度，但是有时迭代过程收敛较慢，使结果达到任意精度，但是有时迭代过程收敛较慢，从而使计算量变得很大，因此迭代过程加速是个主要从而使计算量变得很大，因此迭代过程加速是个主要课题课题.设设x0是根是根x*某个近似值某个近似值,用迭代公式校正一次得用迭代公式校正一次得 x1=(x0)而由微分中值定理，有而由微分中值定理，有第37页第37页上页上页下页下页假设假设 (x)改变不大改变不大,近似地取某个近似值近似地取某个近似值L,则有则有由于由于 x2-x*L(x1-x*).若将校正值若将校正值x1=(x0)再校正一次，又得再校正一次，又得 x2=(x1)将它与将它与(3.1)式联立，消去未知式联立，消去未知L，有，有由此推知由此推知第38页第38页上页上页下页下页在计算了在计算了x1及及x2之后，可用上式右端作为之后，可用上式右端作为x*新近似新近似,记记作作x1，普通情形是由，普通情形是由xk计算计算xk+1,xk+2，记，记它表明序列它表明序列xk收敛速度比收敛速度比xk收敛速度快收敛速度快.(3.1)式称为式称为埃特金埃特金(Aitken)2加速办法加速办法.能够证实能够证实第39页第39页上页上页下页下页也称为也称为埃特金埃特金(Aitken)外推法外推法.能够证实能够证实:为线性收敛为线性收敛,则埃特金法为平方收敛则埃特金法为平方收敛；这个加速迭代法也可写成下面格式这个加速迭代法也可写成下面格式若若为为 p(p 1)阶收敛，阶收敛，导数连续，则埃特金法为导数连续，则埃特金法为 2p1 阶收敛阶收敛.p 阶阶若若第40页第40页上页上页下页下页 例题例题 求方程求方程 x=e x 在在 x=0.5 附近根附近根.解解 取取 x0=0.5,迭代格式迭代格式x25=x26=0.5671433 若对此格式用埃特金法若对此格式用埃特金法,则则 得得第41页第41页上页上页下页下页仍取仍取 x0=0.5,得得由此可见由此可见,埃特金法加速收敛效果是相称明显埃特金法加速收敛效果是相称明显.第42页第42页上页上页下页下页7.3.2 斯蒂芬森斯蒂芬森(Steffensen)迭代法迭代法 埃特金办法埃特金办法无论原序列无论原序列xk是如何产生，对是如何产生，对xk进行加速计算，得到序列进行加速计算，得到序列xk.假如把假如把埃特金加速埃特金加速技巧与不定点迭代结合技巧与不定点迭代结合，则可得到下列迭代法：，则可得到下列迭代法：称为称为斯蒂芬森斯蒂芬森(Steffensen)迭代法迭代法.它能够这样理它能够这样理解，我们要求解，我们要求x=(x)根根x*，令误差，令误差(x)=(x)-x，有等式有等式(x*)=(x*)-x*=0，已知，已知x*近似值近似值xk及及yk，其，其误差分别为误差分别为第43页第43页上页上页下页下页把误差把误差(x)“外推到零外推到零”，即过，即过(xk,(xk)及及(yk,(yk)两点做线性插值函数，它与两点做线性插值函数，它与x轴交点就是轴交点就是(3.3)中中xk+1，即方程，即方程解解第44页第44页上页上页下页下页 事实上事实上(3.3)是将不定点迭代法是将不定点迭代法(2.2)计算两步合计算两步合并成一步得到，可将它写成另一个不动点迭代并成一步得到，可将它写成另一个不动点迭代其中其中 对不动点迭代对不动点迭代(3.5)有下列局部收敛性定理有下列局部收敛性定理.定理定理5 若若x*为为(3.5)定义迭代函数定义迭代函数(x)不动点，不动点，则则x*为为(x)不定点不定点.反之，若反之，若x*为为(x)不动点，设不动点，设(x)存在，存在，(x)1，则，则x*是是(x)不动点，且不动点，且斯蒂芬森斯蒂芬森迭代法迭代法(3.3)是是2阶收敛阶收敛.证实可见证实可见2.第45页第45页上页上页下页下页 例例5 见书见书p274.例例6 见书见书p275.第46页第46页上页上页下页下页7.4 牛牛 顿顿 法法7.4.1 牛顿法及其收敛性牛顿法及其收敛性 对于方程对于方程f(x)=0，假如，假如f(x)是线性函数，则它求是线性函数，则它求根是容易根是容易.牛顿法实质上是一个线性化办法，其基本牛顿法实质上是一个线性化办法，其基本思想是将非线性方程思想是将非线性方程f(x)=0逐步归结为某种线性方程逐步归结为某种线性方程来求解来求解.设已知方程设已知方程f(x)=0有近似根有近似根x0，且在，且在 x0附近附近f(x)可可用一阶泰勒多项式近似，表示为用一阶泰勒多项式近似，表示为第47页第47页上页上页下页下页当当f(x0)0时，方程时，方程f(x)=0可用线性方程可用线性方程(切线切线)近近似代替，即似代替，即 f(x0)+f(x0)(x-x0)=0.(4.1)解此线性方程得解此线性方程得得迭代公式得迭代公式此式称为此式称为牛顿牛顿(Newton)迭代公式迭代公式.第48页第48页上页上页下页下页牛顿法有显然牛顿法有显然几何意义几何意义，方程，方程f(x)=0根根x*可解释可解释为曲线为曲线y=f(x)与与x轴交点横坐标轴交点横坐标.设设xk是根是根x*某个近似某个近似值，过曲线值，过曲线y=f(x)上横坐标为上横坐标为xk点点Pk引切线，并将该引切线，并将该切线与切线与x轴交点横坐标轴交点横坐标xk+1作为作为x*新近似值新近似值.注意到切注意到切线方程为线方程为这样求得值这样求得值xk+1必满足必满足(4.1),从而就是牛顿公从而就是牛顿公式式(4.2)计算结果计算结果.由于由于这种几何背景，因此牛顿这种几何背景，因此牛顿迭代法也称迭代法也称切线法切线法.xyx*xky=f(x)xk+1PkPk+1xk+2第49页第49页上页上页下页下页牛顿迭代法收敛性牛顿迭代法收敛性设设x*是是f(x)一个单根，即一个单根，即f(x*)=0，f(x*)0,有有牛顿迭代法迭代函数为牛顿迭代法迭代函数为由定理由定理4(2.9)式可得式可得(4.3)式式第50页第50页上页上页下页下页由此得到，当由此得到，当x*为为单根单根时，牛顿迭代法在根时，牛顿迭代法在根x*邻邻近是近是二阶二阶(平方平方)收敛收敛.关于关于x*为为重根重根时，牛顿迭代法在根时，牛顿迭代法在根x*邻近收敛性邻近收敛性在后面讨论在后面讨论.定理定理(局部收敛性局部收敛性)设设f C2a,b,若若x*为为f(x)在在a,b上根，且上根，且f(x*)0，则存在，则存在x*邻域邻域U,使得任取使得任取初值初值x0 U，牛顿法产生序列，牛顿法产生序列xk收敛到收敛到x*，且满足，且满足即有下面局部收敛性定理即有下面局部收敛性定理.第51页第51页上页上页下页下页 解解 将原方程化为将原方程化为xex=0，则，则牛顿迭代公式为牛顿迭代公式为取取 x0=0.5，迭代得，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.f(x)=xex，f(x)=1+ex，例例7 用牛顿迭代法求方程用牛顿迭代法求方程x=ex在在x=0.5附近根附近根.参见书参见书p277例例7.牛顿法计算环节见书牛顿法计算环节见书p278.第52页第52页上页上页下页下页7.4.2 牛顿法应用举例牛顿法应用举例对于给定正数对于给定正数C，应用牛顿法解二次方程，应用牛顿法解二次方程我们现在证实，这种迭代公式对于任意初值我们现在证实，这种迭代公式对于任意初值x00都是收敛都是收敛.可导出求开方值可导出求开方值 计算程序计算程序第53页第53页上页上页下页下页事实上，对事实上，对(4.5)式施行配方整理，易知式施行配方整理，易知以上两式相除得以上两式相除得据此重复递推有据此重复递推有第54页第54页上页上页下页下页记记整理整理(4.6)式，得式，得对任意初值对任意初值x00，总有，总有|q|1，故由上式推知，当，故由上式推知，当k时时 ，即迭代过程恒收敛，即迭代过程恒收敛.参见书参见书p279例例8.第55页第55页上页上页下页下页7.4.3 简化牛顿法与牛顿下山法简化牛顿法与牛顿下山法牛顿法牛顿法长处长处是收敛快，是收敛快，缺点缺点每步迭代要计算每步迭代要计算f(xk)及及f(xk)，计算量较大，且有时，计算量较大，且有时f(xk)计算较困计算较困难；难；初始近似值初始近似值x0只在根只在根x*附近才干确保收敛，如附近才干确保收敛，如x0给不适当也许不收敛给不适当也许不收敛.为克服这两个缺点，通常可为克服这两个缺点，通常可用下述办法用下述办法.(1)简化牛顿法简化牛顿法，也称，也称平行弦法平行弦法，其迭代公式为，其迭代公式为迭代函数为迭代函数为 (x)=x-Cf(x).第56页第56页上页上页下页下页若若|(xk)|=|1-Cf(x)|1，即取，即取0Cf(x)2.在根在根x*附近成立，则迭代法附近成立，则迭代法(4.7)局部收敛局部收敛.在在(4.7)中取中取C=1/f(x0)，则称为简化牛顿法，则称为简化牛顿法，这类办法计算量省，但只有线性收敛，其这类办法计算量省，但只有线性收敛，其几何意义几何意义是是用平行弦与用平行弦与x轴交点作为轴交点作为x*近似，见下图近似，见下图.y=f(x)x0 x1x2x*第57页第57页上页上页下页下页(2)牛顿下山法牛顿下山法,牛顿法收敛性依赖初值牛顿法收敛性依赖初值x0选取选取,假如假如x0偏离所求根偏离所求根x*较远较远,则牛顿法也许发散则牛顿法也许发散.注：注：注：注：Newtons Method收敛性依赖于收敛性依赖于x0选取选取.x*x0 x0 x0第58页第58页上页上页下页下页比如比如，用牛顿法求解方程，用牛顿法求解方程 x3-x-1=0.(4.8)此方程在此方程在x=1.5附近一个根附近一个根x*.设取迭代初值设取迭代初值x0=1.5，用牛顿迭代法公式，用牛顿迭代法公式 计算得计算得 x1=1.34783,x2=1.32520,x3=1.32472.迭代迭代3次得到结果次得到结果x3有有6位有效数字位有效数字.但是，如取但是，如取x0=0.6，用，用(4.9)式迭代式迭代1次得次得 计算得计算得 x1=17.9.这个结果反而比这个结果反而比x0=0.6更偏离了所求根更偏离了所求根x*=1.32472.第59页第59页上页上页下页下页为了预防迭代发散，我们对迭代过程再附加一项为了预防迭代发散，我们对迭代过程再附加一项要求，即含有单调性要求，即含有单调性.满足这项要求算法称为满足这项要求算法称为下山法下山法.我们将牛顿法与下山法结合起来使用，即在下山我们将牛顿法与下山法结合起来使用，即在下山法确保函数值稳定下降前提下，用牛顿法加快收敛速法确保函数值稳定下降前提下，用牛顿法加快收敛速度度.为此，我们将牛顿法结果为此，我们将牛顿法结果与前一项近似值与前一项近似值xk适当加权平均作为新改进值适当加权平均作为新改进值第60页第60页上页上页下页下页其中其中(01)称为称为下山因子下山因子，(4.11)即为即为称为称为牛顿下山法牛顿下山法.选择下山因子时从选择下山因子时从=1开始，逐次将开始，逐次将减半进行试减半进行试算，直到能使下降条件算，直到能使下降条件(4.10)成立为止成立为止.若用此法解方程若用此法解方程(4.8)，当，当x0=0.6时由时由(4.9)式求式求得得x1=17.9，它不满足条件，它不满足条件(4.10)，通过，通过逐次减半进逐次减半进行试算行试算,当当=1/32时可求得时可求得x1=1.140625.有有f(x0)=-1 1.384,f(x1)=-0.656643,显然显然|f(x1)|0)重根重根时，则时，则f(x)可表为可表为 f(x)=(x-x*)mg(x).其中其中g(x*)0，此时用牛顿迭代法，此时用牛顿迭代法(4.2)求求x*仍然收敛，仍然收敛，只是只是收敛速度将大大减慢收敛速度将大大减慢.事实上，由于迭代公式事实上，由于迭代公式令令ek=xkx*，则，则第64页第64页上页上页下页下页可见用牛顿法求方程重根时仅为可见用牛顿法求方程重根时仅为线性收敛线性收敛.从而有从而有两种两种提升求重根收敛速度提升求重根收敛速度办法办法：1)取下列迭代函数取下列迭代函数得到迭代公式得到迭代公式第65页第65页上页上页下页下页下面简介一个下面简介一个求重数求重数m办法办法，令，令则则求求m重根含有重根含有2阶收敛阶收敛.但要知道但要知道x*重数重数m.由式由式得得因此得预计因此得预计m式子为式子为第66页第66页上页上页下页下页对对f(x)=(x-x*)mg(x),g(x*)0，令函数，令函数则为求则为求(x)=0单根单根x*问题，对它用牛顿法是二阶问题，对它用牛顿法是二阶(平方平方)收敛收敛.其迭代函数为其迭代函数为2)将求重根问题化为求单根问题将求重根问题化为求单根问题.从而结构出迭代办法为从而结构出迭代办法为第67页第67页上页上页下页下页 例例8 用牛顿迭代法求函数用牛顿迭代法求函数 f(x)=(x-1)sin(x-1)+3x-x3+1=0 在在0.95附近之根附近之根.解解 取取x0=0.95 用牛顿迭代法求用牛顿迭代法求得得xk见右表见右表.可可见见xk收敛很慢收敛很慢.kxk km01234560.950.97442790.98705830.99348780.99673280.99835760.99919010.50900.50470.50070.51252.03692.01902.00282.0511第68页第68页上页上页下页下页由重根数由重根数m=2,用用(4.13)式加速法，作式加速法，作求得求得 x0=0.95,x1=0.9988559,x2=x3=1.收敛速度大大加快于直接用牛顿迭代公式收敛速度大大加快于直接用牛顿迭代公式.参见书参见书p283例例9.第69页第69页上页上页下页下页7.5 弦截法与抛物线法弦截法与抛物线法用牛顿法求方程f(x)=0根，每步除计算f(xk)外还要算f(xk)，当函数f(x)比较复杂时，计算f(x)往往比较困难，为此可以利用已求函数值f(xk),f(xk-1),往返避导数值f(xk)计算.这类办法是建立在插值原理基础上，下面简介两种常用办法.第70页第70页上页上页下页下页7.5.1 弦截弦截(割线割线)法法设设xk,xk-1是是f(x)=0近似根，我们利用近似根，我们利用f(xk),f(xk-1)结构一次插值多项式结构一次插值多项式p1(x)，并用，并用p1(x)=0根作为方程根作为方程f(x)=0新近似根新近似根xk+1，由于，由于因此有因此有第71页第71页上页上页下页下页这样导出迭代公式这样导出迭代公式(5.2)能够看做牛顿公式能够看做牛顿公式中导数中导数 用用差商差商 取代结果取代结果.(5.2)式有明显式有明显几何意义几何意义：设曲线设曲线y=f(x)上横坐标为上横坐标为xk-1和和xk点分别为点分别为P0和和Pk,则差商则差商 表示弦表示弦 斜率斜率,弦弦 方程为方程为第72页第72页上页上页下页下页Ox*xk+1xkPkxk-1yxPk-1因此，按因此，按(5.2)式求式求得得xk+1事实上是两点事实上是两点弦线弦线 与与x轴交轴交点横坐标点横坐标(令令y=0解出解出x即可即可).这种算法因这种算法因此而形象地称为此而形象地称为弦截弦截(割线割线)法法.参见书参见书p285例例10.第73页第73页上页上页下页下页弦截法与切线法弦截法与切线法(牛顿法牛顿法)都是线性化分法，但两都是线性化分法，但两者有本质区别者有本质区别.切线法在计算切线法在计算xk+1时只用到前一步值时只用到前一步值xk，而弦截法要用到前面两步结果，而弦截法要用到前面两步结果xk-1,xk，因此使用，因此使用这种办法必须先给出两个开始值这种办法必须先给出两个开始值x0,x1.定理定理6 假设假设f(x)在根在根x*邻域内邻域内:|x-x*|含有二阶含有二阶连续导数，且对任意连续导数，且对任意x 有有f(x)0，所取初值，所取初值x0,x1，那么当邻域，那么当邻域充足小时，弦截法充足小时，弦截法(5.2)将按阶将按阶收敛到收敛到x*.这里这里p是方程是方程2-1=0正根正根.定理证实可见定理证实可见2.第74页第74页上页上页下页下页由于由于(5.2)式用到前两点式用到前两点xk-1和和xk值，故此办法又值，故此办法又称为称为双点割线法双点割线法.每步只用一个新点每步只用一个新点xk值，此办法称为值，此办法称为单点割线法单点割线法.假如把假如把(5.2)式中式中xk-1改为改为x0，即迭代公式为，即迭代公式为第75页第75页上页上页下页下页例题例题 用牛顿迭代法和割线法求方程用牛顿迭代法和割线法求方程 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.第76页第76页上页上页下页下页 例题例题 用快速弦截法求方程用快速弦截法求方程xex-1=0根根.设方程两设方程两个初始近似根为个初始近似根为x0=0.5,x1=0.6.计算结果表计算结果表k xk xk-xk-10 0.5 1 0.6 0.12 0.56532 -0.034683 0.56709 0.001774 0.56714 0.00005 与与例例7(p277)中牛中牛顿法计算结果相比较，顿法计算结果相比较，能够看出快速弦截法能够看出快速弦截法收敛速度也是相称快，收敛速度也是相称快，迭代到第迭代到第4步就得到精步就得到精度度 结果结果.第77页第77页上页上页下页下页7.5.2 抛物线法抛物线法设已知方程设已知方程f(x)=0三个近似根三个近似根xk,xk-1,xk-2，我们以，我们以这三点为节点结构二次插值多项式这三点为节点结构二次插值多项式p2(x)，并适当选取，并适当选取p2(x)一个零点一个零点xk+1作为新近似根，这样拟定迭代过程作为新近似根，这样拟定迭代过程称为称为抛物线法抛物线法，亦称为，亦称为密勒密勒(Mller)法法.在几何图形在几何图形上上,这种办法基本思想是用抛物线这种办法基本思想是用抛物线y=p2(x)与与x轴交点轴交点xk+1作为所求根作为所求根x*近似位置近似位置.第78页第78页上页上页下页下页Ox*xk+1xky=P2(x)xk-2yxy=f(x)xk-1抛物线法抛物线法几何意义几何意义见下面图形见下面图形.第79页第79页上页上页下页下页现在推导抛物线法计算公式现在推导抛物线法计算公式.插值多项式插值多项式有两个零点有两个零点式中式中因了在因了在(5.3)式定出一个值式定出一个值xk+1，我们需要讨论根，我们需要讨论根式前正负号取舍问题式前正负号取舍问题.在在xk,xk-1,xk-2三个近似值中，自然假定三个近似值中，自然假定xk更靠近更靠近所求根所求根x*，这时，为了确保精度，我们选，这时，为了确保精度，我们选(5.3)式中式中靠近靠近xk一个值作为新近似根一个值作为新近似根xk+1.为此，只要取根式为此，只要取根式前符号与前符号与符号相同符号相同.第80页第80页上页上页下页下页 例例11 用抛物线法求解方程用抛物线法求解方程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.故故代入代入(5.3)式求得式求得以上计算表明，抛物线法比弦截法收敛更快以上计算表明，抛物线法比弦截法收敛更快.第81页第81页上页上页下页下页事实上事实上,在一定条件下能够证实在一定条件下能够证实,对于抛物线法，对于抛物线法，迭代误差有下列渐近关系式迭代误差有下列渐近关系式由此式可见抛物线法也是超线性收敛，其收敛阶是由此式可见抛物线法也是超线性收敛，其收敛阶是p=1.840(是方程是方程3-2-1=0根根)，收敛速度比弦截法更，收敛速度比弦截法更靠近于牛顿法靠近于牛顿法.从从(5.3)式看到，即使式看到，即使 xk,xk-1,xk-2 均为实数，均为实数，xk+1也能够是复数，因此抛物线法适合用于求多项式实也能够是复数，因此抛物线法适合用于求多项式实根和复根根和复根.第82页第82页上页上页下页下页7.6 解非线性方程组牛顿迭代法解非线性方程组牛顿迭代法考察方程组考察方程组其中其中f1,fn均为均为(x1,xn)多元函数多元函数.若用向量若用向量记号记记号记x=(x1,xn)TRn,F=(f1,fn)T,(6.1)就可就可写成写成 F(x)=0.(6.2)第83页第83页上页上页下页下页当当n2，且，且 f1,fn 中至少有一个是自变量中至少有一个是自变量 x1,xn 非非线性函数，则称方程组线性函数，则称方程组(6.1)为为非线性方程组非线性方程组.非线非线性方程组求根问题是前面简介方程性方程组求根问题是前面简介方程(即即n=2)求根直接求根直接推广，事实上只要把前面简介推广，事实上只要把前面简介单变量函数单变量函数f(x)当作当作向向量函数量函数F(x)，则可得，则可得向量方程向量方程(6.2)一个近似根一个近似根x(k)=(x1(k),xn(k)T，将函数，将函数F(x)分量分量fi(x)(i=1,n)在在x(k)用多元函数泰勒展开，并取其线性部分，则可表用多元函数泰勒展开，并取其线性部分，则可表示为示为.第84页第84页上页上页下页下页令上式右端为零，得到线性方程组令上式右端为零，得到线性方程组其中其中第85页第85页上页上页下页下页称为称为F(x)雅可比雅可比(J