数值分析非线性方程求根.ppt

第二章 非线性方程求根,1根的存在性。方程有没有根？如果有根，有几个根？,定理1：设函数 f(x)在区间a,b上连续，如果f(a)f(b)0，则方程 f(x)=0 在a,b内至少有一实根x*。,2这些根大致在哪里？如何把根隔离开来？,3根的精确化,x*,f(x),1画出 f(x)的略图，从而看出曲线与x 轴交点的位置。,2从左端点x=a出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点x0和终点x0+h的函数值，若,那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h作为根的初始近似。,例1：考察方程,x1,x2,a,b,或,不能保证 x 的精度,x*,2,1 二 分 法,执行步骤,1计算f(x)在有解区间a,b端点处的值，f(a)，f(b)。,2计算f(x)在区间中点处的值f(x1)。,3判断若f(x1)=0，则x1即是根，否则检验：,（1）若f(x1)与f(a)异号，则知解位于区间a,x1，b1=x1,a1=a;,（2）若f(x1)与f(a)同号，则知解位于区间x1,b，a1=x1,b1=b。,反复执行步骤2、3，便可得到一系列有根区间：(a,b),(a1,b1),(ak,bk),简单;对f(x)要求不高(只要连续即可).,无法求复根及偶重根 收敛慢,注：显然，二分法能够无限地继续下去，这些区间必收敛于一点x*，该点就是所求的根。事实上，无限过程是不可能实现的，也没有这种必要，因为数值分析的结果允许有一定的误差。,由于,只要有根区间,那么就可以取,作为x*的第k+1次近似值。,其误差估计为：,例2：求方程,在区间1,1.5内的实根。要求准确到小数点后第二位。求二分的次数。,利用误差估计式，可以解得：,2 迭 代 法,1简单迭代法,x1=0.4771x2=0.3939x6=0.3758x7=0.3758,2迭代过程的收敛性,f(x)=0,x=g(x),迭代格式,定理2：如果(x)满足下列条件（1）当xa,b时，(x)a,b（2）当任意xa,b，存在0 L 1，使 则方程x=(x)在a,b上有唯一的根x*,且对任意初值 x0a,b时，迭代序列xk+1=(xk)(k=0,1,)收敛于x*。,(2.1),3迭代法的结束条件,例4：求方程 在0,0.5内的根，精确到10-5。,x1=(0.25)=0.3385416,(2.2),x2=(x1)=0.3462668,x3=(x2)=0.3471725,x4=(x3)=0.3472814,x5=(x4)=0.3472945,x6=(x5)=0.3472961,x7=(x6)=0.3472963,4迭代过程的收敛速度,设由某方法确定的序列xk收敛于方程的根x*，如果存在正实数p，使得,（C为非零常数）,定义：,则称序列xk收敛于x*的收敛速度是p阶的，或称该方法具有p 阶敛速。当p=1时，称该方法为线性（一次）收敛；当p=2时，称方法为平方（二次）收敛；当1 p 2时，称方法为超线性收敛。,3 牛顿法,一、牛顿法的迭代公式,x*,x0,x1,x2,原理：将非线性方程线性化 Taylor 展开,取 x0 x*，将 f(x)在 x0 做一阶Taylor展开:,，在 x0 和 x 之间。,将(x*x0)2 看成高阶小量，则有：,只要 f C1，每一步迭代都有f(xk)0，而 且，,，则 x*就是 f(x)的根。,(2.3),二、牛顿法的收敛性,定理3：设f(x)在a,b上满足下列条件：（1）f(a)f(b)0则由（2.3）确定的牛顿迭代序列xk收敛于f(x)在a,b上的唯一根x*。,注：Newton法的收敛性依赖于x0 的选取。,x*,3牛顿下山法,牛顿下山法计算步骤可归纳如下：,（1）选取初始近似值x0；,（2）取下山因子=1；,（3）计算,（4）计算f(xk+1)，并比较 与 的大小，分以下二种情况,1）若，则当 时，取x*xk+1，计算过程结束；当 时，则把xk+1作为新的xk值，并重复回到（3）。,2）若，则当且，取x*xk，计算过程结束；,否则若，而 时，则把xk+1加上一个适当选定的小正数，,即取xk+1+作为新的xk值，并转向（3）重复计算；当；且，则将下山因子缩小一半，取/2代入，并转向（3）重复计算。,例5：求方程f(x)=x3 x 1=0 的根,牛顿下山法的计算结果：,1、单点弦截法：,牛顿法一步要计算 f 和 f，相当于2个函数值。现用 f 的值近似 f:,切线,割线,切线斜率割线斜率,2、双点弦截法：,切线斜率割线斜率,需要2个初值 x0 和 x1。,