第7章-非线性方程迭代解法yjs讲解.ppt

1、科大研究生学位课程 数值分析,1,第7章 非线性方程迭代解法,1根的存在性。方程有没有根？如果有根，有几个根？,2这些根大致在哪里？如何把根隔离开来？,3根的精确化,本章介绍求解非线性方程 f(x)=0 的几种常见和有效的数值方法.,其中(x)是高次多项式函数或超越函数.如 (x)=3x5-2x4+8x2-7x+1 (x)=e2x+1-xln(sinx)-2 等等.,科大研究生学位课程 数值分析,2,7.1 根的搜索与二分法,求非线性方程,确定方程的有根区间 计算根的近似值,f(x)=0的根的方法,分为两步：,科大研究生学位课程 数值分析,3,首先确定有限区间：依据零点定理。 设 ，且 ，则方

2、程 在区间 上至少有一个根。如果 在 上恒正或恒负，则此根唯一。,科大研究生学位课程 数值分析,4,等步长扫描法求有根区间,用计算机求有根区间：等步长扫描法。 设h0是给定的步长，取x0=a,x1=a+h ， 若f(x0)*f(x1)b 则扫描失败。再将h 缩小， 继续以上步骤。,科大研究生学位课程 数值分析,5,等步长扫描算法,算法：（求方程 f(x)=0 的有根区间） (1) 输入 a,b,h ；(2) f0 =f(a) ； (3) x=a+h, f1=f(x) , 若xb 输出失败信息，停机。 (4)若 f1=0 , 输出 x ，已算出方程的一个根，停机。,(5) 若 f0 f1 0 .

3、输出 a,x, a,x 为有根区间，停机 (6) a=x ，转 3） 注：如果对足够小的步长h扫描失败。说明： 在 a,b 内无根 在 a,b 内有偶重根,具体看书上Matlab程序P148 看例7.1,科大研究生学位课程 数值分析,6,用二分法(将区间对平分)求解。 令a1=a, b1=b, c1=(a1+b1)/2 若 f(a1)f(c1)0 ，则 a1, c1 为有根区间，否则 c1, b1 为有根区间 记新的有根区间为 a2, b2 ， 则a1, b1 包含a2, b2 ，且 b2-a2= (a1+b1)/2,二 分 法,对 a2, b2 重复上述做法得,科大研究生学位课程 数值分析,

4、7,设 所求的根为 x*，则 即 取 为 x* 的近似解,二 分 法,科大研究生学位课程 数值分析,8,求方程f(x)=0的根的二分法算法,(2)置x:=(a+b)/2,(3)若f(x)=0，输出x，停算；否则，转步(4);,(4)若f(a)f(b)0，则置b:=x ；否则，置a:=x ;,(5)置x:=(a+b)/2,若|b-a| ,输出x，停算，否则，转步(3).,参看教材程序P150,科大研究生学位课程 数值分析,9,误差 分析：,第 k 步产生的 xk 有误差,对于给定的精度 ,可估计二分法所需的步数 k ：,简单; 对f (x) 要求不高(只要连续即可) .,无法求复根及偶重根 收敛

5、慢,注：用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。,科大研究生学位课程 数值分析,10,7.2 简单迭代法及其加速,f (x) = 0,x = (x),f (x) 的根, (x) 的不动点,思路,从一个初值 x0 出发，计算 x1 = (x0), x2 = (x1), , xk+1 = (xk), 若 收敛，即存在 x* 使得 ，且 连续，则由 可知 x* = (x* )，即x* 是 的不动点，也就是

6、f 的根。,科大研究生学位课程 数值分析,11,迭代法需解决的三个问题,迭代函数的构造 由迭代函数产生的解序列的收敛性 序列的收敛速度和误差估计,科大研究生学位课程 数值分析,12,迭代法的几何意义,交点的横坐标,y=x,y= (x),科大研究生学位课程 数值分析,13,例1 试用迭代法求方程 在区间(1，2)内的实根。 解：由 建立迭代关系 k=0,1,2,3. 计算结果如下:,精确到小数点后五位,科大研究生学位课程 数值分析,14,但如果由 建立迭代公式 仍取 ，则有 ， 显然结果越来越大， 是发散序列.,科大研究生学位课程 数值分析,15,科大研究生学位课程 数值分析,16,定理,k,科

7、大研究生学位课程 数值分析,17,证明： (x) 在a, b上存在不动点？,令,有根, 不动点唯一？,反证：若不然，设还有 ，则,而, 当k 时， xk 收敛到 x* ？,科大研究生学位课程 数值分析,18,可用 来控制收敛精度,L 越 收敛越快,小,注：定理条件非必要条件，可将a, b缩小，定义局部收敛性：若在 x* 的某 领域 B = x | | x x* | 有 (x) C1a, b 且 | (x*) | 1，则由x0B 开始的迭代收敛。即调整初值可得到收敛的结果。（局部收敛性）,科大研究生学位课程 数值分析,19,迭代过程的收敛速度,设由某方法确定的序列xk收敛于方程的根x*， 如果存

8、在正实数p，使得,（C为非零常数）,定义：,则称序列xk收敛于x*的收敛速度是p阶的，或称该方法 具有p 阶敛速。称C为渐进常数。当p = 1时，称该方法为 线性（一次）收敛；当p = 2时，称方法为平方（二次）收敛； 当1 p 2时，称方法为超线性收敛。,科大研究生学位课程 数值分析,20,Q: 如何实际确定收敛阶和渐进误差常数？,证明：,科大研究生学位课程 数值分析,21, 待定参数法：,若 | (x) | 1，则将 x = (x) 等价地改造为,求K，使得,例：求 在 (1, 2) 的实根。,如果用 进行迭代，则在(1, 2)中有,现令,在 (1, 2) 上可取任意 ，例如K = 0.5

9、，则对应 即产生收敛序列。,科大研究生学位课程 数值分析,22, 松弛加速：,d,w,w,w,+,=,-,+,=,+,+,+,-,),(,),(,),(,),1,(,*,2,1,*,1,*,1,*,k,k,k,k,k,k,k,k,k,k,k,x,f,x,f,x,x,x,x,x,x,x,x,x,条件下成立,保证如下不等式在一定,以此类推。引入松弛因子,修正计算,再对,的修正，并计算,作为,把,，令,选取适当的松弛因子,科大研究生学位课程 数值分析,23, Aitken 加速：,P(x0, x1),P(x1, x2),一般地，有：,比 收敛得略快。,科大研究生学位课程 数值分析,24, Steff

10、ensen （斯蒂芬森）加速：,其实是将原不动点迭代计算两次合并成一步得到， 可改为另一种不动点迭代法:,将Aitken（埃特金）加速与不动点迭代结合.可得到 如下迭代法:,科大研究生学位课程 数值分析,25,定理 若x*为上式定义的函数g(x)的不动点，则x* 为(x)的不动点.反之，若x*是(x)的不动点，设(x)存在, (x* ) 0，则x*是(x)的不动点且斯蒂芬森迭代法是二阶收敛的.(证明略）,科大研究生学位课程 数值分析,26,例2 试用Steffensen算法求解方程 解法一、取 ，由,n = 0，1，2，,取初值x0=1.5，计算结果如下：,科大研究生学位课程 数值分析,27,

11、解法二、取 ， 对于该迭代函数在一般迭代法中是发散的，而Steffensen格式却是收敛的。,n=0，1，2，,取初值x0=1.5，计算结果如下：,科大研究生学位课程 数值分析,28,Steffensen迭代格式几何解释,科大研究生学位课程 数值分析,29,Steffensen迭代算法,程序见p159。,科大研究生学位课程 数值分析,30,7.3 常用迭代法牛顿法,原理：将非线性方程线性化 Taylor 展开,取 x0 x*，将 f (x)在 x0 做一阶Taylor展开:,， 在 x0 和 x 之间。,将 (x* x0)2 看成高阶小量，则有：,线性 /* linear */,只要 f C1

12、，每一步迭代都有f ( xk ) 0， 而且 ，则 x*就是 f 的根。,科大研究生学位课程 数值分析,31,定理,（收敛的充分条件）设 f C2a, b，若 (1) f (a) f (b) 0； 则Newtons Method产生的序列 xk 收敛到f (x) 在 a, b 的唯一根。,有根,根唯一,产生的序列单调有界，保证收敛。,定理,（局部收敛性）设 f C2a, b，若 x* 为 f (x) 在a, b上的根，且 f (x*) 0，则存在 x* 的邻域 使得任取初值 ，Newtons Method产生的序列 xk 收敛到x*，且满足,科大研究生学位课程 数值分析,32,证明：Newto

13、ns Method 事实上是一种特殊的不动点迭代 其中 ，则,收敛,由 Taylor 展开：,只要 f (x*) 0，则令 可得结论。,在单根 /*simple root */ 附近收敛快,科大研究生学位课程 数值分析,33,Newtons Method 有 ，只要 就有 p 2。至少是二阶收敛。,算法7.5（牛顿法）,取初始点x0，最大迭代次数N和精度要求eps，置k:=0；,(2)计算,xk+1= xk- f(xk)/f(xk),(3)若|xk+1-xk|eps, 则停算；,(4)若k=N,则停算 ；否则，置k:=k+1,转步2 .,程序见P161。,科大研究生学位课程 数值分析,34,例

14、 用Newton法计算 。 解：,科大研究生学位课程 数值分析,35,注：Newtons Method 收敛性依赖于x0 的选取。,x*,科大研究生学位课程 数值分析,36,牛顿法迭代公式,牛顿法的优点,牛顿法是目前求解非线性方程 (组) 的主要方法,至少二阶局部收敛，收敛速度较快，特别是当迭代点充分靠近精确解时。,牛顿的缺点,对重根收敛速度较慢（线性收敛） 对初值的选取很敏感，要求初值相当接近真解,在实际计算中，可以先用其它方法获得真解的一个粗糙近似，然后再用牛顿法求解。,科大研究生学位课程 数值分析,37, 重根加速收敛法：,Q1: 若 ，Newtons Method 是否仍收敛？,设 x

15、* 是 f 的 n 重根，则： 且 。,因为 Newtons Method 事实上是一种特殊的不动点迭代， 其中 ，则,A1: 有局部收敛性，但重数 n 越高，收敛越慢。,Q2: 如何加速重根的收敛？,A2: 将求 f 的重根转化为求另一函数的单根。,令，则 f 的重根 = 的单根。,科大研究生学位课程 数值分析,38,Q3: 如何加速重根的收敛？,A3: 修改迭代函数，令,有，则改进后的迭代法至少具有二阶收敛性。,科大研究生学位课程 数值分析,39, 下山法（阻尼牛顿法） Newtons Method 局部微调：,原理：若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和

16、xk+1 之间找一个更好的点 ，使得 。,注： = 1 时就是Newtons Method 公式。 当 = 1 代入效果不好时，将 减半计算。,科大研究生学位课程 数值分析,40, 割线法：（弦截法）,Newtons Method 一步要计算 f 和 f ，相当于2个函数值，比较费时。现用 f 的值近似 f ，可少算一个函数值。,切线 /* tangent line */,割线 /* secant line */,切线斜率割线斜率,需要2个初值 x0 和 x1。,收敛比Newtons Method 慢，且对初值要求同样高。,科大研究生学位课程 数值分析,41,可以证明，弦截法具有超线性收敛，收敛的阶约为1.618，它与前面介绍的一般迭代法一样都是线性化方法，但也有区别。即一般迭代法在计算xk+1时只用到前一步的值xk，故称之为单点迭代法；而弦截法在求xk+1时要用到前两步的结果xk-1和xk，使用这种方