《数值计算第二章》ppt课件

1、1根的存在性。方程有没有根？假设有根，有几个根？根的存在性。方程有没有根？假设有根，有几个根？定理定理1 1：设函数：设函数 f (x) f (x) 在区间在区间a, ba, b上延续，假设上延续，假设f (a) f (a) f (b) 0 f (b) 0打打 印印结结 束束否否是是继续扫描继续扫描 例例1 1：调查方程：调查方程01)(3xxxfx00.51.01.5f (x) 的符号的符号abx1x2ab11xxkk 2)(xf 或或不能保证不能保证 x 的精的精度度x* 2xx* 执行步骤1计算计算f (x)在有解区间在有解区间a, b端点处的值，端点处的值，f (a)，f (b)。2计

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), 4、当、当11kkab时时)(211kkkbax5、那么、那么即为

3、根的近似即为根的近似简单简单; 对对f (x) 要求不高要求不高(只需延续即可只需延续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 定义定义f (x)f (a) f (b)0f (a) f (b)=0f (a) =0打印打印b, k打印打印a, k终了终了是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m, ka=mb=m终了终了k=K+1是是是是否否否否输入输入 ,bak = 0例例2： 求方程求方程01)(3xxxfkakbkxkf (xk)的符的符号号011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751

4、.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-1 1简单迭代法简单迭代法x1 = 0.4771x2 = 0.3939x6 = 0.3758x7 =0.37582迭代过程的收敛性迭代过程的收敛性f (x) = 0 x = g (x)等价变换等价变换例例3：求方程：求方程0210)(xxxf的一个根的一个根210 xx)2lg( xx迭代格式迭代格式)2lg(1kkxxxyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p

5、0 x1p1 x0p0 x1p1x0p0 x1p1定理定理2 2：假设：假设 (x) (x)满足以下条件满足以下条件1 1当当x xa, ba, b时，时，(x)(x)a, ba, b2 2当恣意当恣意x xa, ba, b，存在，存在0 L 10 L 1，使，使 那么方程那么方程x = x = (x) (x)在在a, ba, b上有独一的根上有独一的根x x* *, ,且对恣且对恣意初值意初值 x0 x0a, ba, b时，迭代序列时，迭代序列xk+1=xk+1= (xk) (k = 0, 1, ) (xk) (k = 0, 1, )收敛于收敛于x x* *。1)( Lx(2.1)3迭代法的

6、终了条件迭代法的终了条件例例4 4：求方程：求方程 在在0, 0.50, 0.5内的根，准确到内的根，准确到10-510-5。0133 xxx1 = (0.25) = 0.33854161kkxx(2.2)x2 = (x1) = 0.3462668x3 = (x2) =0.3471725x4 = (x3) =0.3472814x5 = (x4) =0.3472945x6 = (x5) =0.3472961x7 = (x6) =0.3472963 4迭代过程的收敛速度 设由某方法确定的序列设由某方法确定的序列xk收敛于方程的根收敛于方程的根x*，假设存在正实数假设存在正实数p，使得，使得Cxxx

7、xpkkk*1*limC C为非零常数为非零常数定义：定义：那么称序列那么称序列xkxk收敛于收敛于x x* *的收敛速度是的收敛速度是p p阶的，或称该方法阶的，或称该方法具有具有p p 阶敛速。当阶敛速。当p = 1p = 1时，称该方法为线性一次收敛；时，称该方法为线性一次收敛；当当p = 2p = 2时，称方法为平方二次收敛；当时，称方法为平方二次收敛；当1 p 21 p 2时，时，称方法为超线性收敛。称方法为超线性收敛。 3 3 牛顿法牛顿法一、牛顿法的迭代公式一、牛顿法的迭代公式x*x0 x1x2xyf(x)原理：将非线性方程线性化原理：将非线性方程线性化 Taylor 展开展开取

8、取 x0 x*，将，将 f (x)在在 x0 做一阶做一阶Taylor展展开开:20000)(! 2)()()()(xxfxxxfxfxf ， 在在 x0 和和 x 之间。之间。将将 (x* x0)2 看成高阶小量，那么有：看成高阶小量，那么有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 只需只需 f C1，每一步迭代都有，每一步迭代都有f ( xk ) 0， 而而 且且 ，*limxxkk ，那么，那么 x*就是就是 f (x)的根。的根。)()(1kkkkxfxfxx (2.3)二、牛顿法的收敛性二、牛顿法的收敛性定理定理3： 设设f (x)在在a, b上

9、满足以下条件：上满足以下条件：1f (a) f (b) 0那么由那么由2.3确定的牛顿迭代序列确定的牛顿迭代序列xk收敛于收敛于f (x)在在a, b上的独一根上的独一根x*。x*x0 x0 x03牛顿下山法牛顿下山法牛顿下山法计算步骤可归纳如下：牛顿下山法计算步骤可归纳如下：1选取初始近似值选取初始近似值x0；2取下山因子取下山因子 = 1；)( )(1kkkkxfxfxx3计算计算)(1kxf)(kxf4计算计算f (xk+1)，并比较，并比较 与与 的大小，分以下二种情况的大小，分以下二种情况)() 1kkxfxf21kkxx21kkxx1假设假设 ，那么当，那么当 时，取时，取x* x

10、k+1，计算，计算过程终了；过程终了； 当当 时，那么把时，那么把xk+1作为新的作为新的xk值，并反复回到值，并反复回到3。)() 1kkxfxf 2假设假设 ，那么当，那么当 且，取且，取x* xk，计算过程终了；，计算过程终了；11)(kxf否那么假设否那么假设 ，而，而 时，那么把时，那么把xk+1加上一个适中选加上一个适中选定的小正数，定的小正数，11)(kxf即取即取xk+1+作为新的作为新的xk值，并转向值，并转向3反复计算；当反复计算；当；且；且 ，那么将下山因子减少一半，取那么将下山因子减少一半，取/2代入，并转向代入，并转向3反复计算。反复计算。 例例5 5：求方程：求方程f (x) = x3 x 1 = 0 f (x) = x3 x 1 = 0 的根的根k xk010.611/251.14063211.36681311.32628411.32472牛顿下山法的计算结果：牛顿下山法的计算结果：1 1、 单点弦截法单点弦截法 ：牛顿法一步要计算牛顿法一步要计算 f f 和和 f f ，相当于，相当于2 2个函数值。现个函数值。现用用 f f 的值近似的值近似 f f : :x0 x1切线切线 割线割线 切线斜率