非线性方程与方程组的数值解法.pptx

非线性是实际问题中经常出现的，并且在科学与工程计算中的地位越来越重要，很多我们熟悉的线性模型都是在一定条件下由非线性问题简化得到的，为得到更符合实际的解答，往往需要直接研究非线性模型，从而产生非线性科学，它是21世纪科学技术发展的重要支柱.非线性问题的数学模型有无限维的如微分方程，也有有限维的.但要用计算机进行科学计算都要转化为非线性的单个方程或方程组的求解.从线性到非线性是一个质的变化，方程的性质有本质不同，求解方法也有很大差别.本章将首先讨论单个方程求根，然后再简单介绍非线性方程组的数值解法.第1页/共109页7.1 方程求根与二分法方程求根与二分法引 言本章主要讨论求解单变量非线性方程f(x)=0.(1.1)其中xR,f(x)Ca,b,a,b也可以是无穷区间.如果实数x*满足f(x*)=0，则称x*是方程(1.1)的根，或称x*是函数f(x)的零点，若f(x)可分解为f(x)=(x-x*)mg(x)，其中m为正整数,且g(x*)0.则称x*为方程(1.1)的m重根，或x*为f(x)的m重零点，m=1时x*为单根，若x*是f(x)的m重零点，且g(x)充分光滑，则有第2页/共109页如果函数f(x)是多项式函数，即其中系数a00,ai(i=0,1,n)为实数，则称方程(1.1)为n次代数方程.根据代数基本定理可知，n次代数方程在复数域有且只有n个根(含重根,m重根为m个根),当n=1,2时的求根公式是熟知的，n=3,4时的求根公式可在数学手册中查到，但比较复杂，不适合数值计算.n5时就不能直接用公式表示方程的根，所以n3时求根仍用一般的数值方法.另一类是超越方程，例如它在整个x轴上有无穷多个解，若x取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调x的定义域，即x的求解区间a,b.第3页/共109页另外，非线性问题一般不存在直接的求解公式，故没有直接方法求解，都要使用迭代法求解，迭代法要求先给出根x*的一个近似，若f(x)Ca,b且f(a)f(b)0，根据连续函数性质中的介值定理可知方程f(x)=0在(a,b)内至少有一个实根，这时称a,b为方程(1.1)的有根区间，通常可通过逐次搜索法求得方程(1.1)的有根区间.第4页/共109页 例1 求方程f(x)=x3-11.1x2+38.8x-41.77=0的有根区间.解 根据有根区间定义，对f(x)=0的根进行搜索计算，结果如表x 0 1 2 3 4 5 6f(x)的符号的符号-+-+-+-+由此可知方程f(x)=0的有根区间为1,2,3,4,5,6.第5页/共109页二分法 设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)均为新的有根区间,它的长度只有原有根区间长度的一半,达到了压缩有根区间的目的.第6页/共109页 对压缩了的有根区间,又可实行同样的步骤,再压缩.如此反复进行,即可的一系列有根区间套 由于每一区间都是前一区间的一半，因此区间an,bn的长度为若每次二分时所取区间中点都不是根，则上述过程将无限进行下去.当 n时，区间必将最终收缩为一点x*，显然x*就是所求的根.第7页/共109页 若取区间an,bn的中点作为x*的近似值，则有下述误差估计式只要 n 足够大,(即区间二分次数足够多)，误差就可足够小.由于在偶重根附近曲线 y=f(x)为上凹或下凸,即 f(a)与f(b)的符号相同,因此不能用二分法求偶重根.第8页/共109页 例2 用二分法求例1中方程 f(x)=x3-x-1=0的实根,要求误差不超过0.005.解 由例1可知x*(1,1.5),要想满足题意，即：则要|x*-xn|0.005由此解得 取n=6,按二分法计算过程见下表,x6=1.3242 为所求之近似根.第9页/共109页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)根据精根据精 度要求，度要求，取到小数取到小数点后四位点后四位 即可即可.二分法的优点是算法简单，且总是收敛的，缺点是收敛的太慢，故一般不单独将其用于求根，只是用其为根求得一个较好的近似值.第10页/共109页二分法的计算步骤:步骤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即为所求近似根.第11页/共109页7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性不动点与不动点迭代法 将方程f(x)=0改写为等价方程形式 x=(x).(2.1)若要求x*满足f(x*)=0，则x*=(x*)；反之亦然，称x*为函数(x)的一个不动点.求f(x)的零点就等于求(x)的不动点，选择一个初始近似值x0，将它代入(2.1)右端，即可求得 x1=(x0).第12页/共109页可以如此反复迭代计算 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)，迭代过程实质上是一个逐步显式化过程.第13页/共109页当(x)连续时，显然x*就是方程x=(x)之根(不动点).于是可以从数列xk中求得满足精度要求的近似根.这种求根方法称为不动点迭代法,称为迭代格式,(x)称为迭代函数,x0 称为迭代初值,数列xk称为迭代序列.如果迭代序列收敛,则称迭代格式收敛,否则称为发散.（几何意义的解释见书p215页）第14页/共109页分别按以上三种形式建立迭代公式，并取x0=1进行迭代计算，结果如下：解 对方程进行如下三种变形：例3 用迭代法求方程x4+2x2-x-3=0 在区间1,1.2内的实根.第15页/共109页准确根 x*=1.124123029,可见迭代公式不同,收敛情况也不同.第二种公式比第一种公式收敛快得多,而第三种公式不收敛.参见书p215页-例3.第16页/共109页 例3表明原方程化为(2.1)的形式不同，有的收敛，有的不收敛，有的发散，只有收敛的的迭代过程(2.2)才有意义，为此我们首先要研究(x)的不定点的存在性及迭代法(2.2)的收敛性.第17页/共109页不动点的存在性与迭代法的收敛性 首先考察(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)收敛的一个充分条件.第19页/共109页 定理2 设(x)Ca,b满足定理1中的两个条件，则对任意x0a,b，由(2.2)得到的迭代序列xk收敛到(x)的不动点x*，并有误差估计式 证明 设x*a,b是(x)在a,b上的唯一不动点,由条件(1)，可知xka,b，再由(2.4)得因0L1时称超线性收敛，p=2时称平方收敛.第29页/共109页 定理4 对于迭代过程xk+1=(xk)，如果(p)(x)在所求根x*的邻近连续，并且则该迭代过程在x*的邻近是p阶收敛的.证明 由于(x*)=0，根据定理3立即可以断定迭代过程xk+1=(xk)具有局部收敛性.再将(xk)在根x*处做泰勒展开,利用条件(2.4),则有注意到(xk)=xk+1，(x*)=x*，由上式得第30页/共109页因此对迭代误差，令k时有这表明迭代过程xk+1=(xk)确实为p阶收敛.证毕.上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数(x)的选取.如果xa,b但(x)0时，则该迭代过程只可能是线性收敛.对例4的讨论见书p220.第31页/共109页的三阶方法.假设 x0 充分靠近 x*,求 证明 首先由泰勒展式可得 例子 证明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a)是求而1/4a0，故此迭代公式是三阶方法.第32页/共109页7.3 迭代收敛的加速方法迭代收敛的加速方法埃特金加速收敛方法 对于收敛的迭代过程，只要迭代足够多次，就可以使结果达到任意的精度，但是有时迭代过程收敛较慢，从而使计算量变得很大，因此迭代过程的加速是个重要的课题.设x0是根x*的某个近似值,用迭代公式校正一次得 x1=(x0)而由微分中值定理，有第33页/共109页假设(x)改变不大,近似地取某个近似值L,则有由于 x2-x*L(x1-x*).若将校正值x1=(x0)再校正一次，又得 x2=(x1)将它与(3.1)式联立，消去未知的L，有由此推知第34页/共109页在计算了x1及x2之后，可用上式右端作为x*的新近似,记作x1，一般情形是由xk计算xk+1,xk+2，记它表明序列xk的收敛速度比xk的收敛速度快.(3.2)式称为埃特金(Aitken)2加速方法.可以证明第35页/共109页也称为埃特金(Aitken)外推法.可以证明:为线性收敛,则埃特金法为平方收敛；这个加速迭代法也可写成下面格式若为 p(p 1)阶收敛，导数连续，则埃特金法为 2p1 阶收敛.的 p 阶若第36页/共109页 例题 求方程 x=e x 在 x=0.5 附近的根.解 取 x0=0.5,迭代格式x25=x26=0.5671433 若对此格式用埃特金法,则 得第37页/共109页仍取 x0=0.5,得由此可见,埃特金法加速收敛效果是相当显著的.第38页/共109页斯特芬森(Steffensen)迭代法 埃特金方法不管原序列xk是怎样产生的，对xk进行加速计算，得到序列xk.如果把埃特金加速技巧与不定点迭代结合，则可得到如下的迭代法：称为斯特芬森(Steffensen)迭代法.它可以这样理解，我们要求x=(x)的根x*，令误差(x)=(x)-x，有等式(x*)=(x*)-x*=0，已知x*的近似值xk及yk，其误差分别为第39页/共109页把误差(x)“外推到零”，即过(xk,(xk)及(yk,(yk)两点做线性插值函数，它与x轴交点就是(3.3)中的xk+1，即方程的解第40页/共109页 实际上(3.3)是将不定点迭代法(2.2)计算两步合并成一步得到的，可将它写成另一种不动点迭代其中 对不动点迭代(3.5)有以下局部收敛性定理.定理5 若x*为(3.5)定义的迭代函数(x)的不动点，则x*为(x)的不定点.反之，若x*为(x)的不动点，设(x)存在，(x)1，则x*是(x)的不动点，且斯特芬森迭代法(3.3)是2阶收敛的.证明可见文献3.第41页/共109页 例5 用斯特芬森迭代法求解方程f(x)=x3-x-1=0.解 在例3中已指出迭代 xk+1=xk3-1 是发散的，现用(3.3)式计算，取(x)=x3-1，计算结果见表k xk yk zk 012345 1.5 2.37500 12.3965 1.41629 1.84092 5.23888 1.35565 1.49140 2.31728 1.32895 1.34710 1.44435 1.32480 1.32518 1.32714 1.32472计算表明它是收敛的，这说明即使迭代法(2.2)不收敛，用斯特芬森迭代法(3.3)仍可能收敛.至于原来已收敛的迭代法(2.2)，由定理5可知它可达到二阶收敛.更进一步还可知若迭代法(2.2)为p阶收敛，则迭代法(3.3)为p+1阶收敛.第42页/共109页 例6 求方程3x2-ex=0在3,4中的解.解 由方程得ex=3x2，取对数得x=ln3x2=2lnx+ln3=(x).若构造迭代法 xk+1=2lnxk+ln3，由于且当x 3,4时，(x)3,4，根据定理2此迭代法是收敛的.若取x0=3.5达到16次得x16=3.73307，有六位有效数字.若用迭代法(3.3)式进行加速，计算结果如表k xk yk zk 012 3.5 3.60414 3.66278 3.73835 3.73590 3.73459 3.73308这里计算第2步(相当于(2.2)式达到4步)结果与相同，说明用迭代法(3.3)的收敛速度比(2.2)快得多.第43页/共109页7.4 牛牛 顿顿 法法牛顿法及其收敛性 对于方程f(x)=0，如果f(x)是线性函数，则它的求根是容易的.牛顿法实质上是一种线性化方法，其基本思想是将非线性方程f(x)=0逐步归结为某种线性方程来求解.设已知方程f(x)=0有近似根xk，且在 xk附近f(x)可用一阶泰勒多项式近似，表示为第44页/共109页当f(xk)0时，方程f(x)=0可用线性方程(切线)近似代替，即 f(xk)+f(xk)(x-xk)=0.(4.1)解此线性方程得得迭代公式此式称为牛顿(Newton)迭代公式.(也是牛顿法)第45页/共109页牛顿法有显然的几何意义，方程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第46页/共109页牛顿迭代法的收敛性设x*是f(x)的一个单根，即f(x*)=0，f(x*)0,有牛顿迭代法的迭代函数为由定理4的(2.9)式可得第47页/共109页由此得到，当x*为单根时，牛顿迭代法在根x*的邻近是二阶(平方)收敛的.关于x*为重根时，牛顿迭代法在根x*的邻近的收敛性在后面讨论.定理(局部收敛性)设fC2a,b,若x*为f(x)在a,b上的根，且f(x*)0，则存在x*的邻域U,使得任取初值x0U，牛顿法产生的序列xk收敛到x*，且满足即有下面的局部收敛性定理.第48页/共109页 解 将原方程化为xex=0，取牛顿迭代公式为取 x0=0.5，迭代得x1=0.566311,x2=0.5671431,x3=0.5671433.f(x)=xex，f(x)=1+ex，例7 用牛顿法求方程 xex1=0.(4.4)参见书p223的例7.(取的函数不一样)第49页/共109页牛顿法的计算步骤:步骤1 准备 选定初始近似值x0，计算f0=f(x0)，f0=f(x0).步骤2 迭代 按公式 x1=x0-f0/f0，迭代一次，得新的近似值x1，计算 f1=f(x1)，f1=f(x1).步骤3 控制 如果x1满足|1或|f1|0都是收敛的.可导出求开方值 的计算程序第52页/共109页事实上，对(4.5)式施行配方整理，易知以上两式相除得据此反复递推有第53页/共109页记整理(4.6)式，得对任意初值x00，总有|q|0均收敛，并且收敛的速度很快，因此我们可取确定的初值如x0=1编制通用程序，用这个通用程序求1151/2，也只要迭代7次便得到了上面的结果10.723805.计算结果第55页/共109页简化牛顿法与牛顿下山法牛顿法的优点是收敛快，缺点每步迭代要计算f(xk)及f(xk)，计算量较大，且有时f(xk)计算较困难；初始近似值x0只在根x*附近才能保证收敛，如x0给的不合适可能不收敛.为克服这两个缺点，通常可用下述方法.(1)简化牛顿法，也称平行弦法，其迭代公式为迭代函数为 (x)=x-Cf(x).第56页/共109页若|(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页/共109页(2)牛顿下山法,牛顿法收敛性依赖初值x0的选取,如果x0偏离所求根x*较远,则牛顿法可能发散.注：注：Newtons Method收敛性依赖于x0的选取.x*x0 x0 x0第58页/共109页例如，用牛顿法求解方程 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页/共109页为了防止迭代发散，我们对迭代过程再附加一项要求，即具有单调性.满足这项要求的算法称为下山法.我们将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.为此，我们将牛顿法的结果与前一项的近似值xk适当加权平均作为新的改进值第60页/共109页其中(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*的近似.第61页/共109页 下山法/*Descent Method*/Newtons Method 局部微调：原理：若由 xk 得到的 xk+1 不能使|f|减小，则在 xk 和 xk+1 之间找一个更好的点 ，使得 。xkxk+1注：注：=1 时就是Newtons Method 公式。当 =1 代入效果不好时，将 减半计算。第62页/共109页一般情况下，只要能使条件选择(4.10)成立，则可得到极限从而使数列xk收敛.第63页/共109页重根情形设f(x)=(x-x*)mg(x)，整数m2,g(x*)0，则x*为方程f(x)=0的m重根，此时有只要f(xk)0，仍可用牛顿迭代法(4.2)计算，此时迭代函数 的导数满足 ，且 ，所以牛顿法求重根只是线性收敛.第64页/共109页下面给出两种提高求重根的收敛速度的方法：1)取如下迭代函数得到迭代公式求m重根具有2阶收敛.但要知道x*的重数m.介绍一个求重数m的方法(不证明)，令因此得估计m的式子为第65页/共109页 例 用牛顿迭代法求函数 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第66页/共109页由重根数m=2,用(4.13)式加速法，作求得 x0=0.95,x1=0.9988559,x2=x3=1.收敛速度大大加快于直接用牛顿迭代公式.第67页/共109页对f(x)=(x-x*)mg(x),g(x*)0，令函数则为求(x)=0的单根x*的问题，对它用牛顿法是二阶(平方)收敛的.其迭代函数为2)将求重根问题化为求单根问题.从而构造出迭代方法为它是二阶(平方)收敛的.第68页/共109页 例9 方程f(x)=x4-4x2+4=0的根,x*=21/2是二重根,用上述三种方法求根.解 先求出三种方法的迭代公式kxk方法方法(1)方法方法(2)方法方法(3)123x1 x2 x31.4583333331.4366071431.4254973191.4166666671.4142156861.4142135621.4117647061.4142114381.414213562用初值x0=1.5计算结果如表.计算三步，方法(2)及(3)均达到10位有效数字，而用牛顿法只有线性收敛，要达到同样精度需迭代30次.第69页/共109页7.5 弦截法与抛物线法弦截法与抛物线法用牛顿法求方程f(x)=0的根，每步除计算f(xk)外还要算f(xk)，当函数f(x)比较复杂时,计算f(x)往往比较困难，为此可以利用已求函数值f(xk),f(xk-1),来回避导数值f(xk)的计算.这类方法是建立在插值原理基础上的，下面介绍两种常用方法.第70页/共109页弦截(割线)法设xk,xk-1是f(x)=0的近似根，我们利用f(xk),f(xk-1)构造一次插值多项式p1(x)，并用p1(x)=0的根作为方程f(x)=0的新的近似根xk+1，由于因此有第71页/共109页这样导出的迭代公式(5.2)可以看做牛顿公式中的导数 用差商 取代的结果.(5.2)式有明显的几何意义：设曲线y=f(x)上横坐标为xk-1和xk的点分别为Pk-1和Pk,则差商 表示弦 的斜率,弦 的方程为第72页/共109页Ox*xk+1xkPkxk-1yxPk-1因此，按(5.2)式求得xk+1实际上是两点弦线 与x轴交点的横坐标(令y=0解出x即可).这种算法因此而形象地称为弦截(割线)法.第73页/共109页 例10 用弦截法求方程f(x)=xex-1=0的根.设方程的两个初始近似根为x0=0.5,x1=0.6.解 设取x0=0.5,x1=0.6作为开始值，用弦截法求得结果见表，与例7牛顿法的计算结果相比较，可以看出弦截法的收敛速度也是相当快的，迭代到第4步就得到精度=10-4的结果.kxkxk-xk-1012340.50.60.565320.567090.56714 0.1-0.03468 0.00177 0.00005计算结果表实际上，下面的定理6断言，弦截法具有超线性的收敛性.第74页/共109页弦截法与切线法(牛顿法)都是线性化分法，但两者有本质的区别.切线法在计算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的正根.定理证明可见文献3.第75页/共109页因为(5.2)式用到前两点xk-1和xk的值，故此方法又称为双点割线法.每步只用一个新点xk的值，此方法称为单点割线法.如果把(5.2)式中的xk-1改为x0，即迭代公式为第76页/共109页例题 用牛顿迭代法和割线法求方程 f(x)=x4+2x2x3=0，在区间(1,1.5)内之根(误差为10-9).解 取x0=1.5，用牛顿法,可得x6；取x0=1.5,x1=1，用双点割线法，迭代6次得到同样的结果，而采用单点割线法，则迭代18次得x18=1.124123029.第77页/共109页抛物线法设已知方程f(x)=0的三个近似根xk,xk-1,xk-2，我们以这三点为节点构造二次插值多项式p2(x)，并适当选取p2(x)的一个零点xk+1作为新的近似根，这样确定的迭代过程称为抛物线法，亦称为密勒(Mller)法.在几何图形上,这种方法的基本思想是用抛物线y=p2(x)与x轴的交点xk+1作为所求根x*的近似位置.第78页/共109页Ox*xk+1xky=P2(x)xk-2yxy=f(x)xk-1抛物线法的几何意义见下面图形.第79页/共109页现在推导抛物线法的计算公式.对插值多项式有两个零点式中为了从(5.3)式定出一个值xk+1，我们需要讨论根式前正负号的取舍问题.在xk,xk-1,xk-2三个近似值中，自然假定xk更接近所求的根x*，这时，为了保证精度，我们选(5.3)式中接近xk的一个值作为新的近似根xk+1.为此，只要取根式前的符号与的符号相同.第80页/共109页 例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页/共109页事实上,在一定条件下可以证明,对于抛物线法，迭代误差有下列渐近关系式由此式可见抛物线法也是超线性收敛的，其收敛的阶是p=1.840(是方程3-2-1=0的根)，收敛速度比弦截法更接近于牛顿法.从(5.3)式看到，即使 xk,xk-1,xk-2 均为实数，xk+1也可以是复数，所以抛物线法适用于求多项式的实根和复根.第82页/共109页7.6 求根问题的敏感性与多项式零点求根问题的敏感性与多项式零点求根问题的敏感性与病态代数方程 方程求根的敏感性与函数求值是相反的,若f(x)=y,则由y求x的病态性与由x求y的病态性相反，光滑函数y在根x*附近函数绝对误差与自变量误差之比若f(x)0，则求根为反问题,即输入x*满足y=f(x*)=0,若找到一个自变量x使|f(x)|，则解的误差|x|=|x-x*|与|y|=|f(x)-f(x*)|=|f(x)|之比为第83页/共109页即|x|误差将达到如果|f(x*)|非常小，这个值就非常大，直观的可用图表示.良态病态 导数几乎为零第84页/共109页对多项式方程若系数有微小扰动其根变化很大，这种根对系数变化的敏感性称为病态的代数方程.若多项式p(x)的系数有微小变化，可表示为其中q(x)0是一个多项式，次数不大于n.p(x)的零点表示为x1(),x2(),xn()，令x1(0),x2(0),xn(0)为p(x)的零点，即xi=xi(0)(i=1,2,n)，将(6.2)式对 求导，可得第85页/共109页于是当=0时有当|充分小时，利用xk()在=0处的泰勒展开式得它表明了系数有微小变化时引起根变化的情况.当|xk()-xk|很大时代数方程(6.1)就是病态的.第86页/共109页 例12 判断多项式方程求根敏感性 解 取q(x)=x6,=-0.002,p(x)的根xk=k(k=1,2,7).由(6.4)式可得实际上，方程p(x)+x6=0的根xk()分别为这说明方程是严重病态的.第87页/共109页多项式的零点很多问题要求多项式的全部零点，即方程(6.1)的全部根，它等价于求的全部根.前面讨论的任一种方法都可用于求出一个根x1，但通常使用牛顿法最好，可利用秦九韶算法(见节)计算p(x1(k)及p(x1(k)的值.由牛顿法计算到|x1(k+1)-x1(k)|，则得到x1x1(k+1).第88页/共109页由于p(x)=(x-x1)q1(x),即q1(x)=p(x)/(x-x1),将p(x)的次数降低一阶,再求q1(x)=0的一个根x2,q1(x)=(x-x2)q2(x),如此反复直到求出全部n个根.一般地，这里q0(x)=p(x),qn-2(x)为二次多项式，在此过程中当k 增加时不精确性增加，为了解决此困难可通过原方程p(x)=0的牛顿法改进x2,xn-2的结果.由于x1可能是复根，因此使用抛物线法对求复数根更有利.若x1为复根,记 x1=a+bi,则x1=a-bi也是一个根,于是(x-x1)(x-x1)=x2-2ax+a2+b2是p(x)的一个二次因子，于是是n-2阶的多项式，可降低二阶.即使不是复根，也可通过抛物线法求出两个实根，它比牛顿法更优越.第89页/共109页 例13 求p(x)=16x4-40 x3+5x2+20 x+6=0的全部零点.解 先用抛物线法求方程的根，取x0=0.5,x1=-0.5,x2=0，计算到为止|f(xk)|0，存在实数 0，使得对满足0|x-x0|0，使则称x(k)为p阶收敛.第99页/共109页例15 用不动点迭代法求解方程组设D=(x1,x2)|0 x1,0 x21.5,不难验证有 0.81(x)1.25,0.82(x)1.2875,故有x D时(x)D.又对一切x,y D,解 将方程组化为(7.4)式的形式，其中第100页/共109页于是有|(y)-(x)|10.75|y-x|1，即满足条件(7.6).根据定理7，在区域D中存在唯一不动点x*，D内任一点x(0)出发的迭代法收敛于x*，今取x(0)=(0,0)，用迭代法(7.5)可求得 由于对一切x D都有 ，故|(x)|10.9，从而有(x*)0,使则x(k)至少平方收敛于x*.第104页/共109页例16 用牛顿法解例15的方程组.解 由于选x(0)=(0,0)T,解线性方程组F(x(0)x(0)=-F(x(0)，即解得x(0)=(08,0.88)T,x(1)=x(0)+x(0)=(08,0.88)T,按牛顿迭代法(7.1)计算结果入表.x(0)x(1)x(2)x(3)x(4)x1(k)x2(k)0 0.80 0.9917872 0.9999752 1.0000000 0 0.88 0.9917117 0.9999685 1.0000000第105页/共109页解非线性方程组(6.2)的牛顿迭代法.例 求解方程组给定初值x(0)=(1.5,1.0)T，用牛顿法求解.解 先求Jacobi矩阵第106页/共109页用牛顿法(7.10)得即第107页/共109页由x(0)=(1.5,1.0)T逐次迭代得到x(3)的每一位都是有效数字.本章评注见书p236.第108页/共109页感谢您的观看！第109页/共109页