电子科大_数值分析课件第二章_非线性方程求根.ppt

1、第二章 非线性方程的求根方法,第二章 非线性方程的求根方法,引言 方程求根的二分法 迭代法及其收敛性 Newton迭代法,方程是在科学研究中不可缺少的工具； 方程求解是科学计算中一个重要的研究对象； 几百年前就已经找到了代数方程中二次至五次方程的求解公式； 但是，对于更高次数的代数方程目前仍无有效的精确解法； 对于无规律的非代数方程的求解也无精确解法； 因此，研究非线性方程的数值解法成为必然。,2.1引言,非线性方程的一般形式： f(x)=0,代数方程： f(x)=a0+a1x+anxn （an0）,超越方程 ：f(x)中含三角函数、指数函数、或其他超越函数。,用数值方法求解非线性方程的步骤：

2、,（1）找出隔根区间；（只含一个实根的区间称隔根区间）,（2）近似根的精确化。从隔根区间内的一个或多个点出发，逐次逼近，寻求满足精度的根的近似值。,2.2 方程求根的二分法,定理1（介值定理）设函数f(x)在区间a,b连续，且f(a)f(b)0，则方程f(x)=0在区间a,b内至少有一个根。,二分法的基本思想：,假定f(x)=0在a,b内有唯一单实根x*，考察有根区间a,b，取中点x0=(a+b)/2，若f(x0)=0，则x*= x0 ，否则，,（1）若f(x0)f(a)0，则x*在x0右侧，令a1=x0， b1=b;,（2）若f(x0)f(a)0，则x*在x0左侧，令a1=a， b1= x0

3、。,以a1, b1为新的隔根区间，且仅为a, b的一半，对a1, b1重复前过程，得新的隔根区间a2, b2，,如此二分下去，得一系列隔根区间： a, b a1, b1 a2, b2 ak, bk ,其中每个区间都是前一区间的一半，故ak, bk 的长度：,当k趋于无穷时趋于0。,即若二分过程无限继续下去，这些区间最后必收敛于一点x*，即方程的根。,二分法性质： f(an)f(bn)0; bn an = (b a)/ 2n,实际计算中，若给定充分小的正数0和允许误差限1，当|f(xn)| 0或bn- an 1时，均可取x* xn。,每次二分后，取有根区间的中点xk= (ak+bk) /2作为根

4、的近似值，则可得一近似根序列： x0, x1, x2, 该序列必以根x*为极限。,定理2 设x*为方程f(x)=0在a, b内唯一根，且f(x)满足f(a)f(b)0，则由二分法产生的第n个区间an, bn 的中点xn满足不等式,证明：,计算过程简单，收敛性可保证； 对函数的性质要求低，只要连续即可。 收敛速度慢； 不能求复根和重根； 调用一次求解一个a, b间的多个根无法求得。,二分法求解非线性方程的优缺点：,不动点迭代法 不动点的存在性与迭代法的收敛性 迭代收敛的加速方法,2.3 迭代法及其收敛性,迭代法的基本思想：,迭代法是一种逐次逼近的方法，用某个固定公式反复校正根的近似值，使之逐步精

5、确化，最后得到满足精度要求的结果。,例：求方程 x3-x-1=0 在 x=1.5 附近的一个根。,解：将所给方程改写成,假设初值x0=1.5是其根，代入得,x1x0，再将x1代入得,x2x1，再将x2代入得,如此下去，这种逐步校正的过程称为迭代过程。这里用的公式称为迭代公式，即,k=0,1,2,迭代结果见下表：,仅取六位数字，x7与x8相同，即认为x8是方程的根。,x*x8=1.32472,2.3.1 不动点迭代法,将连续函数方程f(x)0改写为等价形式：x=(x) 其中(x)也是连续函数，称为迭代函数。,不动点：若x*满足f(x*)=0，则x*=(x*)；反之，若x*=(x*) ，则f(x*

6、)=0 ，称x*为(x)的一个不动点。,不动点迭代：,(k=0,1,),若对任意 x0a, b，由上述迭代得序列xk，有极限,则称迭代过程收敛，且x*=(x*)为(x)的不动点。,几何意义：,但迭代法并不总令人满意，如将前述方程x3-x-1=0改写为另一等价形式：,此时称迭代过程发散。,则有x1=2.375， x2=12.396，x3=1904, 结果越来越大。,仍取初值x0=1.5，,建迭代公式：,定理3（存在性） 设(x)Ca, b且满足以下两个条件： （1）对于任意x a, b，有a(x)b； （2）若(x)在a, b一阶连续，且存在常数0L1，使得对任意x a, b，成立 | (x)|

7、 L 则(x)在a, b上存在唯一的不动点x*。,2.3.2 不动点的存在性与迭代法的收敛性,不动点的存在性证明：,证：,若,或,显然 (x) 有不动点；,否则，设,则有,（因a(x)b）,记,则有,故存在x*使得,即,x*即为不动点。,不动点存在的唯一性证明：,设有 x1* x2*, 使得,则,其中，介于 x1* 和 x2* 之间。,由定理条件,可得,矛盾！,故 x1* = x2*，不动点唯一存在。,定理4（全局收敛性）,设(x)C a, b且满足以下两个条件：,则对任意x0 a, b，由xn+1=(xn )得到的迭代序列xn 收敛到(x)的不动点x *，并有误差估计：,（2）若(x)在a,

8、 b一阶连续，且存在常数0L1，使得对任意x a, b，成立| (x)| L,（1）对于任意x a, b，有a(x)b；,( 0L1 ),故迭代格式收敛。,所以,证明：,反复递推，可得误差估计式,定义 设(x)有不动点x*，若存在x*的某邻域R：|x-x*| ，对任意x0 R，迭代过程xk+1=(xk )产生的序列xk R且收敛到x*，则称不动点迭代法xk+1=(xk )局部收敛。,定理4给出的收敛性称全局收敛性，实际应用时通常只在不动点x*邻近考察其收敛性，称局部收敛性。,证明：根据连续函数性质，因(x)连续，存在x*的某邻域R：|x-x*| ，对任意x R， |(x)| L1，且 |(x)

9、-x*| = | (x)-(x*)| = |()| | x- x*| L | x- x*| | x- x*| 即对任意x R， 总有(x) R。 由全局收敛性定义知，迭代过程 xk+1=(xk )对于任意初值x0 R均收敛。,定理5（局部收敛性） 设x*为(x)的不动点， (x)在x*的某邻域连续，且|(x*)|1，则不动点迭代法xk+1=(xk )局部收敛。,例,解：,格式（1）,格式（2）,格式（3）,格式（4）,取x0=2，对上述四种方法，计算三步所得结果如下：,kxk (1) (2)(3) (4) 0 x0 2 222 x1 3 1.51.751.75 x2 9 21.734751.7

10、32143 x3 87 1.51.7323611.732051,注：x*=1.7320508,收敛阶定义：,设迭代过程 xk+1=(xk ) 收敛于方程x=(x )的根x*，若迭代误差 ek=xk x* 当k时成立下列渐近关系式：,（c为常数，且c0）,则称迭代过程是r阶收敛的。,特别地，r=1时称线性收敛； r=2时称平方收敛； r1时称超线性收敛。 且r 越大，收敛越快。,定理：设x*为x=(x )的不动点，若(x )满足： （1） (x )在x*附近是p次连续可微的(p1)； （2） 则迭代过程xn+1=(xn )在点x*邻近是p阶收敛的。,得,所以,故迭代过程xn+1=(xn ) p阶

11、收敛。,证：由Taylor公式,假定(x )改变不大，近似取某个近似值L，则有,2.3.3 迭代收敛的加速方法,一、Aitken加速收敛方法：,由微分中值定理，有,同理,两式相比，得,类推可得,故,上式即为Aitken加速收敛方法的迭代格式。,将Aitken加速技巧与不动点结合可得,或将其写为,二、Steffensen迭代法：,解：由前知，迭代格式 xk+1=xk3-1 是发散的。现用steffensen迭代法计算。取(x )=x3-1，结果如下：,表明即使不动点迭代法不收敛，用steffensen迭代法仍可能收敛。,例：用steffensen迭代法求解方程 x3-x-1=0 。,例,解,由,

12、取对数,构造迭代格式,故,当x 3,4时，(x ) 3,4，且,故迭代格式收敛。,取x0=3.5，经计算可得迭代16次后x16=3.73307，有6位有效数字。,若用steffensen迭代法加速，结果如下： k xk yk zk 03.53.604143.66202 13.734443.733813.73347 23.73307,说明steffensen迭代法的收敛速度比不动点迭代快得多。,1. 不动点的存在性与迭代法的收敛性,前一次课内容回顾,2. 收敛阶的判定,3. 迭代收敛的加速方法,4. Steffensen迭代法,Newton迭代法及其收敛性 简化Newton迭代法（平行弦法） 弦

13、截法 Newton下山法 重根情形,2.4 Newton迭代法,设方程f(x)=0有近似根xk（f (xk)0），将f(x)在xk展开：（在x和xk之间）,2.4.1 Newton迭代法及其收敛性,基本思想：将非线性方程逐步归结为某种线性方程求解。,可设,记该线性方程的根为xk+1，则,故f(x)=0可近似表示为,即为Newton法迭代格式。,（k=0,1,）,Newton迭代法的几何意义： （亦称切线法）,切线方程,故,Newton迭代法的收敛性： 迭代函数：,定理：假设f(x)在x*的某邻域内具有连续的二阶导数，且设f(x*)=0， f (x*)0，则对充分靠近x*的初始值x0，Newto

14、n迭代法产生的序列xn至少平方收敛于x*。,设f(x*)=0，f (x*)0，则 (x*)=0，故Newton迭代法在x*附近至少平方收敛。,解： f (x)=ex+xex，故Newton迭代公式为,k xk 00.5 1 0.57102 20.56716 30.56714,迭代3次即可得到精度为10-5的近似解0.56714。若用不动点迭代，达到同一精度需17次。,例：用Newton迭代法解方程 xex-1=0。,即,取迭代初值x0=0.5，结果如下：,Newton迭代法的缺陷：,1.被零除错误,2.程序死循环,方程: f(x)=x3 3x + 2 = 0 在重根x*=1附近，f (x)近似

15、为零。,对 f(x) = arctan x 存在 x0，Newton迭代法陷入死循环。,若| (x)|=|1-cf (x)|1，即取0cf (x)2在x*附近成立，则收敛。 若取c=1/f (x0)，则称简化Newton法。,2.4.2 简化Newton法（平行弦法）,迭代公式：,（c0,k=0,1,）,迭代函数：,在Newton迭代格式中，用差商近似导数，,2.4.3 弦截法（割线法）,称弦截法。,得,弦截法的几何意义：,弦线PkPk-1的方程：,当y0时，,例 用简化的Newton迭代法和弦截法计算方程x3-3x+1=0的根。,解：设f(x)=x3-3x+1，则f (x)=3x2-3,由简

16、化的Newton法，得,由弦截法，得,x0=0.5 x1= 0.3333333333 x2 = 0.3497942387 x3 = 0.3468683325 x4 = 0.3473702799 x5 = 0.3472836048 x6 = 0.3472985550 x7 = 0.3472959759 x8 = 0.3472964208 x9 = 0.3472963440 x10 = 0.3472963572 x11 = 0.3472963553,x0=0.5; x1=0.4; x2 = 0.3430962343 x3 = 0.3473897274 x4 = 0.3472965093 x5= 0

17、.3472963553 x6 = 0.3472963553,简化Newton法,弦截法,要达到精度10-8，简化Newton法迭代11次，弦截法迭代5次， Newton迭代法迭代4次。,无论前面哪种迭代法：,（Newton迭代法、,简化Newton法、,弦截法）,Newton迭代法,x0 = 2 x1 = -3.54 x2 = 13.95 x3 = -279.34 x4 = 122017,是否收敛均与初值的位置有关。,如,x0 =1 x1 = -0.5708 x2 = 0.1169 x3 = -0.0011 x4 = 7.9631e-010 x5 = 0,收敛,发散,为防止Newton法发散，

18、可增加一个条件： |f(xk+1)|f(xk)|，满足该条件的算法称下山法。 可用下山法保证收敛，Newton法加快速度。,2.4.4 Newton下山法,称Newton下山法。,（01,下山因子）,记,即,从=1开始，逐次减半计算。,的顺序，直到使下降条件|f(xk+1)|f(xk)|成立为止。,的选取：,即按,例：求解方程,要求达到精度|xn-xn-1|10-5，取x0= -0.99。,解：先用Newton迭代法：f (x)=x2-1,x2=21.69118 x3=15.15689 x4 = 9.70724 x5 = 6.54091 x6 = 4.46497 x7 = 3.13384 x8= 2.32607 x9 = 1.90230 x10= 1.75248 x11= 1.73240 x12= 1.73205 x13= 1.73205,需迭代13