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

第六章,非线性方程求根,1根的存在性。方程有没有根？如果有，有几个根？,2根的搜索。这些根大致在哪里？如何把根隔离开？,3根的精确化。,f (x) = 0 （2.1）,1.根的存在性,定理1：设函数 f (x) 在区间a, b上连续，如果f (a) f (b) 0， 则方程 f (x) = 0 在a, b内至少有一实根x*。,定义：,如果存在 使得 ，则称 为方程（2.1）,的根或函数 的零点。,m重根,若,其中，,为正整数，,则当m=1时，,称 为方程（2.1）,的单根或函数 的单零点。,称 为方程（2.1）,的 m重根或函数 的m重零点。,当 时，,2. 根的搜索,(1) 图解法（利用作图软件如 Matlab),(2) 解析法,(3) 近似方程法,(4) 定步长搜索法,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) 要求不高(只要连续即可) .,无法求复根及偶重根 收敛慢,定义f (x),f (a) f (b)0,f (a) f (b)=0,f (a) =0,打印b, k,打印a, k,结束,是,是,是,否,否,否,m=(a+b)/2,|a-b|,f(a)f(b)0,打印m, k,a=m,b=m,结束,k=K+1,是,是,否,否,输入,k = 0,例2： 求方程,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.2),注 此处L可以看成是 在区间a,b内的上界。,3迭代法的结束条件,求方程,在,内的根,例：,。,解：,原方程可以等价变形为下列三个迭代格式,由迭代格式 （1）,取初值,得,结果是发散的？！,由迭代格式 （2）,取初值,得,结果精确到四位有效数字，迭代到,得到收敛结果。,十步才能得到收敛的结果！,由迭代格式（3）,取初值,得,结果精确到四位有效数字，迭代到,得到收敛结果。,四步就能得到收敛的结果了！,迭代格式（1）的迭代函数为,求导得,当,时,故迭代格式（1）是发散的。,分析:,迭代格式（2）的迭代函数为,当,时,由,知当,时，,所以迭代格式（2）是收敛的。,迭代格式（3）的迭代函数为,当,时,由,时，,知当,所以迭代格式（3）也是收敛的。,结论:,通过以上算例可以看出对迭代函数,所得到的,若小于1，则收敛；且上界越小收敛速度越快。,求导，,的上界若是大于1，则迭代格式发散；,4迭代过程的收敛速度,设由某方法确定的序列xk收敛于方程的根x*，如果存在正实数p，使得,（C为非零常数）,定义：,则称序列xk收敛于x*的收敛速度是p阶的，或称该方法具有p 阶收敛速度。当p = 1时，称该方法为线性（一次）收敛；当p = 2时，称方法为平方（二次）收敛；当1 p 2或C=0,p=1时，称方法为超线性收敛。,5.迭代法收敛阶的判别,定理3 如果 在 附近的某个领域内有p( )阶 连续导数，且,则迭代格式 在 附近是p阶局部收敛的。,3 牛顿法,一、牛顿法的迭代公式 考虑非线性方程,原理：将非线性方程线性化 Taylor 展开,取 x0 x*，将 f (x)在 x0 做一阶Taylor展开:,， 在 x0 和 x 之间。,将 (x* x0)2 看成高阶小量，则有：,只要 f C1，且每步迭代都有f ( xk ) 0， 而且,则 x*就是 f (x)的根。公式（2.3）称为牛顿迭代公式。,(2.3),构造迭代公式,x*,x0,x1,x2,二、牛顿法的几何意义,三、牛顿法的收敛性,定理4： 设f (x)在a, b上存在二阶连续导数且满足下列条件：（1）f (a) f (b) 0则由（2.3）确定的牛顿迭代序列xk二阶收敛于f (x)在a, b上的唯一单根x*。,注：Newton法的收敛性依赖于x0 的选取。,x*,四、求m重根的牛顿法,1、迭代格式,(2.4),2、重数m的确定,3、迭代格式（2.4)的收敛阶（至少2阶收敛）,五、牛顿法的变形-牛顿下山法,1、牛顿下山法的计算步骤：,（1）选取初始近似值x0；,（2）取下山因子 = 1；,（3）计算,（4）计算f (xk+1)，并比较 与 的大小，分以下二种情况,1）若 ，则当 时，取x* xk+1，计算过程结束；当 时，则把 xk+1 作为新的 近似值，并返回到（3）。,2）若 ，则当且|f(xk+1)| ，取x* xk，计算过程结束；,否则若，而 时，则把xk+1加上一个适当选定的小正数，,即取xk+1+作为新的xk值，并转向（3）重复计算；当；且 时，则将下山因子缩小一半，取/2代入，并转向（3）重复计算。,例5：求方程f (x) = x3 x 1 = 0 的根。,牛顿下山法的计算结果：,牛顿法一步要计算 f 和 f ，相当于2个函数值。现用 f 的值近似 f :,切线,割线,切线斜率割线斜率,2、割线法：,3、 双点弦截法 ：,切线斜率割线斜率,初值 x0 和 x1。,