数值分析_2

1课程内容第一章数值计算中的误差第二章方程（组）的迭代解法第三章解线性方程组的直接解法第四章解线性方程组的迭代法第五章插值法第六章数值积分与数值微分2第二章方程(组)的迭代解法3本章内容§1引言§2迭代解法§3迭代公式的改进§4联立方程组的迭代解法§5联立方程组的牛顿解法§6联立方程组的延拓解法4•方程的根满足方程f(x)=0的x值通常叫做方程的根或解，也叫函数f(x)的零点。•单根和重根如果f(x)=(x-a)mg(x)且g(a)≠0，则称a为f(x)=0的m重根。m=1称为单根，m1称为重根。•f(x)代数多项式：f(x)=a0xn+a1xn-1+…+an-1x+an(a0≠0)超越函数：如三角函数,指数函数的复合函数等。§1引言5•本章重点：讨论求方程f(x)=0实根的迭代解法•注意：适用于求解代数方程和超越方程仅限于求方程的实根§1引言6本章内容§1引言§2迭代解法§3迭代公式的改进§4联立方程组的迭代解法§5联立方程组的牛顿解法§6联立方程组的延拓解法7x0xn迭代方法基本思想：计算f(xn)判断f(xn)＝0？xnx(xn)xn+1xn+1xnYesNo§2迭代解法结束82.1根的初值确定方法2.2迭代解法的求解过程2.3迭代解法的几何意义2.4迭代解法的收敛性2.5迭代序列的误差估计§2迭代解法9•圈定根所在的范围，称为圈定根或根的隔离–代数方程•根的个数与其最高次数相同，有成熟的圈定根的方法–超越方程•可能有1个、多个根或者无解。无固定的圈定根的方法•求方程根的问题，就几何上讲，是求曲线y=f(x)与x轴交点的横坐标。§2迭代解法2.1根的初值确定方法代数方程a0xn+a1xn-1+…+an-1x+an=0(a0≠0)的根x*满足|x*|(n+1)max|ai|/|a0|10x*af(a)bf(b)定理2.1(连续函数的性质）：设f(x)为区间[a,b]上的连续函数，如果f(a)·f(b)0，则[a,b]中至少有一个实根。如果f(x)在[a,b]上还是单调地递增或递减，则仅有一个实根。几何意义如下abx*f(a)f(b)§2迭代解法2.1根的初值确定方法11•必须满足连续函数，否则可能没有实根。运用此定理，确定根所在子区间的方法有：(1)画图法(2)扫描法(3)对分法ab§2迭代解法2.1根的初值确定方法定理2.1(连续函数的性质）：设f(x)为区间[a,b]上的连续函数，如果f(a)·f(b)0，则[a,b]中至少有一个实根。12画出y=f(x)的略图f(x)=0分解为1(x)=2(x)的形式，1(x)与2(x)两曲线交点的横坐标所在的子区间为含根区间。例如x㏒x–1=0㏒x＝1/x§2迭代解法2.1根的初值确定方法2.1.1画图法y=1/xy=logx13对于某些看不清根的函数，可以扩大一下曲线y0xy=f(x)y=kf(x)§2迭代解法2.1根的初值确定方法2.1.1画图法14•对于给定的f(x)，设有根区间为[A,B]，从x0=A出发，以步长h=(B-A)/n(n是正整数)在[A,B]内取点：xi=x0＋ih(i=0，1，2，…，n)，从左至右检查f(xi)的符号，如发现xi与xi-1的函数值异号，则缩小了的子区间［xi-1,xi］有根。y0xABa1b1a2b2§2迭代解法2.1根的初值确定方法2.1.2扫描法15–h过大则可能会漏掉根a+(k+1)ha+khh–h过小则计算量很大如要求精度达到0.001,则在长度为1的搜索区间中,要计算1000个函数值,欲使精度提高一位,计算量就要增加10倍关键是选取步长h§2迭代解法2.1根的初值确定方法2.1.2扫描法16•设[xk-1，xk]为含根子区间，初值对于根的误差要求为,令a=xk-1,b=xk,计算出f(a)，f(b)后转下:1)取[a,b]的中点r=(a+b)/2，计算f(r)。2)若f(r)·f(a)0，取a=r；否则取b=r。3)若b-a，转向1)；否则结束。§2迭代解法2.1根的初值确定方法2.1.3对分法17•其几何意义如图:b1=(a+b)/2b2=(a+b1)/2b3=(a+b2)/2a1=(a+b2)/2YXabx*Algorithm:while((b-a)tol){m=a+(b-a)/2;if(sign(f(a))=sign(f(m)))a=m;elseb=m;}§2迭代解法2.1根的初值确定方法2.1.3对分法18•误差分析第1步产生的21bax有误差21abx*||x第n步产生的xn有误差nnabx*||x22lnlnln2εabnεabn优点：①计算简单;②对f(x)要求不高(只要连续即可)。缺点：①收敛速度慢，计算工作量大。对分法可作为求解近似解的迭代法，xk=(a+b)/2。§2迭代解法2.1根的初值确定方法2.1.3对分法192.1根的初值确定方法2.2迭代解法的求解过程2.3迭代解法的几何意义2.4迭代解法的收敛性2.5迭代序列的误差估计§2迭代解法20第一步：建立迭代函数第二步：迭代计算§2迭代解法2.2迭代法求解过程21例如：f(x)=x3+2x2－4=0变换x=x+f(x)=x3+2x2+x－4;f(x)=0x=(x)等价变换迭代函数04223xx§2迭代解法2.2迭代法求解过程2.2.1建立迭代函数3242xx223xx也可以变换22迭代计算：x1=(x0)x2=(x1)…xn+1=(xn)（n=0,1,2,…）称为迭代公式x0,x1,x2,…称为迭代序列序列的计算过程称为迭代过程–如果序列x0,x1,x2,…收敛于x*,即*limxxnn*)(*)lim()(limlim1xxxxxnnnnnn连续）（x*为方程的解§2迭代解法2.2迭代法求解过程2.2.2迭代法求解过程23•例2.3用迭代法求方程f(x)=x3-x-1=0在x0=1.5附近的根(要求根的近似值稳定至小数点后5位)。•解：(1)将方程改写为x=(x)=(1+x)1/3按上式建立迭代公式xn+1=(xn)=(1+xn)1/3(2)取x0=1.5逐次迭代：x1=(1.5)=1.35721,x2=(1.35721)=1.33086,x3=(1.33086)=1.32588,x4=(1.32588)=1.32494x5=(1.32494)=1.32476,x6=(1.32476)=1.32473,x7=(1.32473)=1.32472,x8=(1.32472)=1.32472近似解：x=1.32472§2迭代解法2.2迭代法求解过程2.2.2迭代法求解过程24•例2.3用迭代法求方程f(x)=x3-x-1=0在x0=1.5附近的根(要求根的近似值稳定至小数点后5位)•解法二•(1)将方程改写为x=x3-1，•建立迭代公式xn+1=(xn)＝xn3－1•(2)取x0=1.5逐次迭代：x0=1.5,x1=2.375,x2=12.39648,……•迭代法失效。§2迭代解法2.2迭代法求解过程2.2.2迭代法求解过程•迭代序列有极限存在的迭代过程称为收敛的迭代过程；否则就是发散的。252.1根的初值确定方法2.2迭代解法的求解过程2.3迭代解法的几何意义2.4迭代解法的收敛性2.5迭代序列的误差估计§2迭代解法26•求根问题求直线y=x与曲线y=(x)的交点的横坐标yx0x*x2x1x0y=xy=(x)A0[x0,(x0)]A0‘A1‘A1A§2迭代解法2.3迭代解法的几何意义27xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1§2迭代解法2.3迭代解法的几何意义282.1根的初值确定方法2.2迭代解法的求解过程2.3迭代解法的几何意义2.4迭代解法的收敛性2.5迭代序列的误差估计§2迭代解法29•影响迭代法收敛性的要素迭代函数在根近旁的性态初值的选取范围•迭代法收敛的类型大范围收敛:从任何可取初值出发都能保证收敛局部收敛:为了保证收敛性必须选取初值充分接近于所要求的根。局部收敛方法比大范围收敛方法收敛得快§2迭代解法2.4迭代解法的收敛性30•合理的求根算法–先用一种大范围收敛方法求得接近于根的近似值(如对分法)，再以其作为新的初值使用局部收敛法。§2迭代解法2.4迭代解法的收敛性31•定理2.2设(x)在包含根x*的区间[a,b]上连续，(a,b)内可导，且满足条件(1)对任意x[a,b],(x)[a,b](2)任意x[a,b],|’(x)|q1则对任何x0[a,b]，迭代过程xn+1=(xn)（n=0,1,2,…）一定收敛。§2迭代解法2.4迭代解法的收敛性32证明：(x)在区间[a,b]连续，(a,b)内可导，且对任意x[a,b],(x)[a,b]，则根据中值定理，*)('*)()(*0101xxxxxx*)('*)()(*1212xxxxxx*)('*)()(*11xxxxxxnnnn………...*'''*021xxxxnn所以又1'qxbax,**0xxqxxnn0*lim,0,xxqnnnn时当§2迭代解法2.4迭代解法的收敛性33•注意：1.该定理的条件是充分条件；2.q值等于新旧迭代值之误差比,即对旧误差的缩小率。q愈小，新近似值逼近就愈快。3.在实际应用时,因’(x)连续且[a,b]较小,’(x)的值变化不大,可用|’(x0)|1代替。§2迭代解法2.4迭代解法的收敛性34•例如:解方程x3-2x-5=0区间[2,3]有根取x0=2,则x1=1.5,x2=-0.8125,x3=-2.76819,x4=-13.10615,x5=-1128.12935……是发散数列。取x0=3,则x1=11,x2=663,x3=1.45717*108……是发散数列。§2迭代解法2.4迭代解法的收敛性)5(213xx)5(21)(3xx223)('xx迭代解法步骤：圈定根区间收敛的迭代公式迭代计算解：f(2)=-1，f(3)=16x∈[2,3]，6≤(x)≤13.535325xx3()25xx232()3(25)xx3250xx取x0=2,则x1=2.08008,x2=2.09235,x3=2.09422,x4=2.09450,x5=2.09454,x6=2.09455,x7=2.09455收敛。在有根区间[2,3]，1154.0392)('03x§2迭代解法2.4迭代解法的收敛性x∈[2,3]，2(x)336•设迭代序列收敛，如果存在正数r和c，使得cxxxximrnnn**1成立，则称该迭代序列是r阶收敛的，或称迭代序列收敛的阶为r，c为渐近误差常数r反映了迭代过程的收敛速度，r越大绝对误差缩减得越快，即方法收敛得越快，它是衡量迭代法好坏的重要标志。不同的迭代法具有不同的收敛阶数。r=1线性收敛r1超线性收敛r=2平方收敛新近似值的误差与旧近似值误差的r次方成正比§2迭代解法2.4迭代解法的收敛性37•定理2.4设迭代函数(x)在x*邻域有r阶连续导数，且满足’(x*)=’’(x*)=…=(r-1)(x*)=0，及(r)(x*)≠0，则该迭代序列在x*邻域是r阶收敛的。证明：xn+1=(xn)=(x*+(xn-x*))rnrrnrnnxxrxxrxxxxxxxx*)(!*)()!1(*...*)(!2*''*)(!1*'*)(1)1(2!*)(*)(rxxxrrn!*)(*)(1rxxxxrrn