资源描述
定义：设f(x)为一元连续函数，称方程f(x)=0为函数方程。特别地，当f(x)不是 x 的线性函数时，称对应的函数方程为非线性方程。,在非线性方程中，当f(x)为多项式函数时，称为代数方程，其一般形式如下：,此即为n次代数方程。若存在一点x*，使f(x*)=0，则x*称为方程f(x)=0的根。,1,当f(x)不是多项式函数时，如f(x)=ex-sinx，则f(x)=0称为超越方程。 在非线性方程中，绝大部分没有求根公式，就必须借助于数值计算方法逐次逼近法来完成。,对,分,法,及,区,间,迭,代,法,利用连续函数f(x)的零点定理，将f(x)=0的含根区间逐次减半缩小，构造出收敛的点列xk，来逐步逼近f(x)=0的根x*的数值计算方法称为对分法。,2,零点定理指出： 若f(x)a , b，且满足f(a)f(b)0，则在区间a , b上至少有一点，使f()=0。,将含根区间对分为两个子区间后，在其上又可利用零点定理确定根在哪个子区间上。如此继续下去就得到各子区间的中点构成点列xk中，它将收敛于f(x)=0的根x*处。,3,例2.1 用对分法求下面方程在区间1，2内的根，要求绝对误差不超过10-3。,解 因为f(1)= -5，f(2)=14，所以在区间1 , 2内有根，故可以使用对分法。 c=(1+2)/2=1.5，f(c)2.375，含根区间为 a1 , b1= 1 , 1.5 c1=(1+1.5)/2=1.25，f(c1)-1.79687，含根区间为 a2 , b2= 1.25 , 1.5， c9=(1.36128125+1.365234375)/2=1.364257813，,4,f(c9)= -0.01605，含根区间为 a10 , b10= 1.364257813 , 1.365234375,因误差,故可停止计算，得准确根x*的近似值为 c9=1.365234375。,5,1、二分法的收敛性 二分法又称区间迭代法。在求根区间a , b上，只要满足f(a)f(b)0，则此种迭代是收敛的。 2、如何控制迭代（一般而言）？ （1）给定精度控制量EPS，如二分法以长度 |ak-bk|EPS或区间中点ck函数值|f(ck)|EPS为控制条件； （2）给定最大允许迭代次数（即区间对分次数），以避免因迭代发散而无穷迭代。,6,二分法迭代次数估算： 设迭代次数为N，精度控制量为EPS，则可按下式估算：,如例2.1，EPS=10-3，b-a=1，故有：,故所需迭代次数为N=10。,为在计算机上实现二分法求根，下面对其计算步骤（或称算法）进行描述：,7,INPUT 端点a , b；误差EPS；迭代次数上界N；定义函数f(x)。 OUTPUT 近似解 c 或迭代失败的信息 Step1 FA= f(a) ; FB= f(b) If（FAFB0）Then k=0 ; Do Step2 Else OUTPUT （不能用对分法求解) STOP End If Step2 While kN Do Steps36 Step3 c=(a+b)/2 ; FC= f(c) Step4 If（|FC|EPSOr（(b-a)/20）Then a=c ; FA=FC Else b=c End If /计算ak，bk转向Step3 Step7 OUTPUT（次数已达上界，迭代不收敛 , k） STOP,8,9,练习题 求方程cosx=x的根（1）验证方程在区间0,/2内有单根；（2）令a0=0，b0=/2，用对分法求解可得一系列的含根区间a0 , b0、a1 , b1、a2 , b2，试求出a2、b2。,1、对分法的缺点： 每迭代一次含根区间缩小一半，收敛速度较慢。 2、比例求根法： 基本思想：以函数 f(x)曲线在含根区间上ak , bk的割线与 x 轴的交点 xk 逐步逼近根 x*。,10,如下图所示，连接AB弦交x轴于xk，判断f(xk)是否与f(ak) 同号： 若同号，则ak+1=xk，bk+1=bk； 不同号，则ak+1=ak，bk+1=xk 。,利用三角形akAxk与三角形bkBxk相似，有,11,于是得到数列xk的迭代格式：,如果给定条件f(a)f(b)0，且f (x)与f ”(x)不变号，则上述方法一定收敛于所求的根。,12,1、由非线性方程f(x)=0，将其变换为等价形式 x=(x)； 2、构造迭代公式 xk+1=(xk)； 3、取初值 x0，计算x1=(x0)、x2=(x1)、，即可获得一个数列xk，并以此数列的收敛点作为所求根的数值计算方法简单迭代法，其中(x)迭代函数， xk迭代数列，如果该数列收敛，即 ：,简,单,迭,代,法,13,因此有=()，则即为方程f(x)=0的根。 在实际的计算中给定一个精度控制量，当 |xk+1-xk|时，取=xk+1作为方程f(x)=0的根。,由方程f(x)=0构造等价形式x=(x)时，(x)的形式不是唯一的，而且并非每种迭代函数(x)所构成的迭代形式xk+1=(xk)都能保证所形成的数列收敛，如下例所示：,例 用迭代法求区间2 , 3内方程x3-2x-5=0的根,14,解一 将方程两边同时加上2x+5，再开三次方得同解方程：,作迭代格式：,取,迭代得：,x1=2.154434690， x2=2.103612029, x3=2.095927410， x4=2.094553215, x5=2.094583250， x6=2.094556309,15,x7=2.094552215, x8=2.094551593, x9=2.094551498, x10=2.094551484, x11=2.094551482=x12 由于x11=x12，再迭代已无变化，可见 x11。,解二 将方程两边同加2x3+5，再同除3x2-2，得同解方程：x=(2x3+5)/(3x2-2)。作迭代格式 ：,取x0=2.5迭代得： x1=2.164179104, x2=2.097135356, x3=2.094555232, x4=2.094551484, x5=x4，故 x4,16,解三 将方程两边同时加上2x，再同除2，得同解方程：,作迭代格式：,取x0=2.5迭代得： x1=5.3125, x2=72.46643066, x3=190272.0118, x4=3.4442505361015, x5=2.0429333981046， 计算 x6 时将溢出。,由此可见，迭代序列是否收敛和收敛的速度的快慢，与迭代函数 (x) 有关。,17,说明：方程f(x)=0 改写为等价形式x= (x)，则求f(x)=0的根即求直线y=x与曲线y= (x)的交点。由xk+1= (xk)的迭代过程示意如下图：,设迭代函数(x)满足条件： （1） 当xa , b时，(x)a , b; （2） 存在正数L1，使对任意xa , b有|(x)|L1，则对任意初值x0a , b，迭代数列xk+1=(xk)收敛于方程x=(x)在a , b上唯一的根即(x) 的不动点x*且有如下误差限表达式：,18,y=x,y=(x),x0,x1,x2,x*,I） | (x) |1 1）取初值x0 2）x1= (x0) 3）x2= (x1)， 如此经若干次迭代后（设为第k+1次迭代后），可认为xk+1已充分接近于直线与曲线的交点(x*, (x*)，而x*即为所求根，以xk+1近似替代。,19,II） | (x) |1 1）取初值x0 2）x1= (x0) 3）x2= (x1)， 迭代计算的结果xk+1离直线与曲线的交点(x*, (x*)越来越远。即迭代序列不能收敛。,y=x,x0,x1,x2,x*,y=(x),20,对上例中的三种迭代函数，因2.094551482，可分别验证如下：,故依上述迭代法收敛定理可知，前两种迭代函数能保证所构成迭代数列在根处收敛，而第三种迭代函数不能保证收敛。,21,迭代法收敛定理的证明：,（1）根（不动点x*）的存在与唯一 存在性：f(x)=x-(x)，由a (a)，得f(a)=a-(a)0，由(b) b，得f(b)=b-(b) 0，则a,b区间上必存在 x*使f(x*)=x*- (x*)=0 唯一性：假设存在另一个根（不动点x*）使得x*- (x*)=0,由,因 L1，所以x*-x*=0，即x*=x*,（2）给定迭代初值x0，收敛性的证明：,因 L1，当k时Lk+10，即xk+1x*,（3）误差估计（误差限表达式）：取某xk作为根时误差不超过多少？,22,当整数p时，Lp0，xk+px*，即|x*-xk|Lk|x1-x0|/(1-L),23,在区间1 , 2上显然有|(x)|1，而且当x1 , 2时显然也有(x)1 , 2，由迭代法收敛定理可知，迭代格式,解：先形成等价形式,则迭代函数及其导数为,能收敛于所求的根。,24,由迭代法收敛定理可知，在区间1，3上，迭代式,解：令,，共有k个开方号，则有,和迭代公式,，共k+1个开方号，,取迭代函数,（1）选区间1 , 3，当x1 , 3时，(x) 1 , 3；,（2）,对x0 1 , 3收敛于g。事实上由k+时，g2=2+g，得g=2。,25,采用迭代法应关注迭代序列收敛速度的快慢。 1、对简单迭代法而言，选取不同的迭代函数(x)会导致不同的收敛速度，即|(x)|越接近于0，则收敛速度越快。,26,2、不同迭代法的收敛速度也存在较大差异，为此引入收敛阶的概念。,当=1且01时称为超线性收敛。特别地，当=2时称为平方收敛。 显然，收敛阶越高，则收敛速度越快。,27,可知，当迭代过程收敛且(x)连续时，有,3、简单迭代法的收敛阶讨论：,由,这表明，当(x)0时，简单迭代法是线性收敛的。,4、Aitken加速收敛法 设简单迭代序列xk收敛于根x*，则由下式,28,这一操作总结为如下式表示的过程：,可知，当k充分大时有,这说明，在计算出xk、xk+1和xk+2后再用三者组合计算一个新值，有可能更接近于方程的根x*，从而加快迭代速度。,29,牛顿迭代法又称切线法。如下图所示，函数方程f(x)=0有根为，为求出： （1）过点(x0,y0)作曲线y=f(x)的切线，该切线与x轴交于x1；该切线的点斜式方程为,令y=0，得该切线与x轴的交点 :,牛,顿,迭,代,法,30,（2）过点(x1,y1)再作切线则与x轴交于x2，同理可得：,y=f(x),x0,x1,x2,x3,(x0,y0),(x1,y1),(x2,y2),31,如此继续下去，即构成了迭代格式（牛顿迭代格式）：,32,对以上三个条件的说明： （1） 保证了根的存在；,（2） 保证了函数f(x)的单调性及根的唯一性；,（3）三个条件则共同保证了序列xk的收敛性。,下面只证明在满足上述条件时的收敛性： 为方便叙述，不妨设：,即函数曲线y=f(x)单调增加、上凹。此时，因取初值x0使,则由,得：,从而有：,33,故知x1x0。同理可证：xkxk-1x1x0。这表明迭代序列xk单调减小而且有下界，即收敛于所求根。,例 用牛顿迭代法求x3+2x2+10x-20=0在x=1附近的根，计算结果误差小于10-5。,解：令f(x)= x3+2x2+10x-20，考虑区间0，2上f(0)f(2)0，f”(x)=6x+40，可知f(x)=0在0，2上有唯一的根，按牛顿迭代法构造迭代式：,34,取初值x0=2时显然有f(x0)f”(x0)0，故牛顿迭代收敛。,解： 令,则方程f(x)=x2-3=0的根即为所求，取含根区间1 , 2时有,所以方程有唯一的根。构造牛顿迭代格式：,取初值x0=2，显然有,故迭代数列收敛于函数方程的根。,35,牛顿迭代法为平方收敛（收敛阶为2）。 证明： 由f(x)在xk处的泰勒展开式,将x=x*代入上式，并由f(x*)=0可得：,故有：,因而：,所以由收敛阶的定义可知，牛顿迭代法具有2阶收敛。,36,弦截法又称割线法。如下图所示，函数方程f(x)=0有根为，为求出：,弦,截,法,37,（1）过点(x0,y0)和点(x1,y1)作曲线y=f(x)的割线，该割线 与x轴交于x2；该割线的点斜式方程为,令y=0，得该割线与x轴的交点x2 :,（2）过点(x0,y0)和(x2,y2)再作割线则与x轴交于x3，可得：,如此继续下去，即构成了迭代格式：,38,每次所作割线与x轴的交点将逐步逼近所求根。此种弦割法称为单点弦割法。,双点弦截法：如下图所示，过点(x0,y0)和点(x1,y1)作曲线y=f(x)的割线，该割线与x轴交于x2；过点(x1,y1)和(x2,y2)再作割线则与x轴交于x3，。,双点弦截法迭代格式为：,39,一）数据说明： （1）精度控制量EPS，最大迭代次数MAXREPT； （2）迭代初值x0，x1； （3）x_k0、x_k1、x_k2，用于进行迭代计算； （4）自定义函数f(x) 二）操作说明： step1 输入迭代初值x0和x1； step2 x_k0=x0 ; x_k1=x1 ; x_k2 ; k=0 ; p=1.0; step3 While pEPS And k=MAXREPT Do step4 x_k2=x_k1-f(x_k1)*(x_k1-x_k0)/(f(x_k1)-f(x_k0); step5 p= fabs(x_k2-x_k1); step6 x_k0=x_k1 ; x_k1=x_k2; step7 k=k+1; step8 输出x_k2即为所求根。,40,一、问题描述 以二阶非线性方程组为例：,非,线,性,方,程,组,求,解,其中至少有一个方程为非线性方程，求其根，即一组数据(x* , y*),二、基本思想（牛顿迭代法） 将非线性方程组作向量化处理，即：,令,，则原方程组为,所求根即：,，使,41,如此则可用迭代法求根，即用u0,u1,uk,uk+1序列逐次逼近根u*。,三、构造方法 将f1(x , y),f2(x , y)在(xk , yk)处作泰勒展开，并取其线性部分，得到方程组：,令,，则有,42,将u=uk+1代入上式得牛顿迭代格式：,，即,令,，得,上式左右两边同乘,，得,从初值u0开始，逐次计算,，及,，直到,43,取初值,四、实例 求解非线性方程组：,解：,44,由,按此种方法继续做下去，直到,45,
展开阅读全文