数值分析第7章非线性方程求根课件.ppt

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