数值分析课件第二章-非线性方程求根.ppt

第二章 非线性方程的求根方法,第二章 非线性方程的求根方法,引言方程求根的二分法迭代法及其收敛性Newton迭代法,方程是在科学研究中不可缺少的工具；方程求解是科学计算中一个重要的研究对象；几百年前就已经找到了代数方程中二次至五次方程的求解公式；但是，对于更高次数的代数方程目前仍无有效的精确解法；对于无规律的非代数方程的求解也无精确解法；因此，研究非线性方程的数值解法成为必然。,2.1引言,非线性方程的一般形式： f(x)=0,代数方程（多项式）： f(x)=a0+a1x+anxn （an0）,超越方程 ：f(x)中含三角函数、指数函数、或其他超越函数。,用数值方法求解非线性方程的步骤：,（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。,以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-1,实际计算中，若给定充分小的正数0和允许误差限1，当|f(xn)| 0或bn- an 1时，均可取x* xn。,每次二分后，取有根区间的中点xk= (ak+bk) /2作为根的近似值，则可得一近似根序列： x0, x1, x2, 该序列必以根x*为极限。,定理2 设x*为方程f(x)=0在a, b内唯一根，且f(x)满足f(a)f(b)0，则由二分法产生的第n个区间an, bn 的中点xn满足不等式,证明：,方法一（事后估计法） 每次计算后判别（bn- an）/2 是否成立，若成立，则停止计算，否则继续计算；方法二（事前估计法） 由,二分法精度控制的两种方法：,得：,这样就可以由给定的精度要求, 事先计算出计算次数 k。,计算过程简单，收敛性可保证；对函数的性质要求低，只要连续即可。收敛速度慢；不能求复根和重根；调用一次求解一个，a, b间的多个根无法求得。,二分法求解非线性方程的优缺点：,二分法的基本原理就是以 0.5的比例逐次缩小有根区间，事实上，这个比例还可取0到1之间的任何值，即令 xk= ak +c(ak+bk), 其中0c1;若取c=0.618，即令xk= ak +0.618(ak+bk), 得到著名的黄金分割法。,二分法的一种改进：,不动点迭代法不动点的存在性与迭代法的收敛性迭代收敛的加速方法,2.3 迭代法及其收敛性,迭代法的基本思想：,迭代法是一种逐次逼近的方法，用某个固定公式反复校正根的近似值，使之逐步精确化，最后得到满足精度要求的结果。,例：求方程 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*)=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)| L1则(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, b一阶连续，且存在常数0L1，使得对任意x a, b，| (x)| L1成立,（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)-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 )局部收敛。,证明：推导过程同定理4，,补充定理 设方程x=(x)的在a,b上有不动点x* ，且当x属于a,b， |(x)|1，则对任意x0 a,b且 x0 x* ，由迭代格式xk+1=(xk) ，k=0,1,2产生的序列xk发散。,(L1 ),故迭代格式发散。（L=1？）,所以,定理4的条件是迭代法收敛的充分不必要条件；且收敛时L越小收敛越快;定理4条件不满足时，收敛与否不但和迭代函数(x)有关，且与初值x0也有关；由于| (x)| L1的条件判断比较困难，所以常用 | (x)| 1来代替；对于给定的精度要求|x*- xk | 由于 很难估计，采用事后估计法不动点迭代法可以求方程的复根和偶数重根。,关于不动点迭代法的几点说明：,，L大误差大。,例,解：,格式（1）,格式（2）,格式（3）,格式（4）,取x0=2，对上述四种方法，计算三步所得结果如下：,kxk (1) (2)(3) (4)0 x0 2 2221 x1 3 1.51.81.752 x2 9 21.7521.7321433 x3 87 1.51.7380991.732051,注：x*=1.7320508,收敛阶定义：,收敛速度的快慢是衡量算法优劣的一个重要标准，而刻画收敛速度快慢的一个指标就是收敛阶，设序列xk收敛于x*，若误差 ek=xk x* 当k时成立下列渐近关系式：,（c0,p 1）,则称序列xk 是p阶收敛于x* ，c称为误差常数，也可称相应的迭代方法是p阶收敛的。,特别地，p=1，01时称超线性收敛，且p 越大，收敛越快。,一阶收敛 vs. 二阶收敛：,一阶收敛 vs. 二阶收敛：,定理6：设x*为x=(x )的不动点，若(x )满足：（1） (x )在x*附近是p次连续可微的(p1)；（2）则迭代过程xn+1=(xn )在点x*的邻域内是p阶收敛的。,得,所以,故迭代过程xn+1=(xn ) p阶收敛，若极限为0，超P阶。,证：由Taylor公式,例：,例：,由定理6可得， 此时迭代格式xk+1=g(xk) ，至少2阶收敛。,2.3.3 迭代收敛的加速方法,解：由前知，迭代格式 xk+1=xk3-1 是发散的。现用埃特金法迭代格式迭代法计算。取(x )=x3-1，结果如下：,表明即使不动点迭代法不收敛，用埃特金法迭代格式仍可能收敛。,例：用埃特金法迭代格式求解方程 x3-x-1=0，x0=1.5 。,例,解,由,取对数,构造迭代格式,故,当x 3,4时，(x ) 3,4，且,故迭代格式收敛。,取x0=3.5，经计算可得迭代16次后x16=3.73307，有6位有效数字。,若用埃特金法迭代格式加速，结果如下：k xk yk zk03.53.604143.6620213.734443.733813.7334723.73307,说明埃特金法迭代格式的收敛速度比不动点迭代快得多。,Newton迭代法及其收敛性简化Newton迭代法（平行弦法）弦截法Newton下山法重根情形,2.4 Newton迭代法,2.4.1 Newton迭代法及其收敛性,Newton迭代法的几何意义： （亦称切线法）,切线方程,故,Newton迭代法局部收敛,Newton迭代法的收敛性：迭代函数：,定理：假设f(x)在x*的某邻域内具有连续的二阶导数，且设f(x*)=0， f (x*)0，则对充分靠近x*的初始值x0，Newton迭代法产生的序列xn至少平方收敛于x*。,设f(x*)=0，f (x*)0，则 (x*)=0，故Newton迭代法在x*附近至少平方收敛。,全局收敛性条件苛刻，见P24 定理2.4,解： f (x)=ex+xex，故Newton迭代公式为,k xk 00.51 0.5710220.5671630.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)近似为零。,对 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 弦截法（割线法）,称弦截法，避免了求导数，但需要两个初值x0 ，x1 ，其收敛速度为1.6。,得,弦截法的几何意义：,弦线PkPk-1的方程：,当y0时，,单点割线法,慢于割线法,例 用简化的Newton迭代法和弦截法计算方程x3-3x+1=0的根。,解：设f(x)=x3-3x+1，则f (x)=3x2-3,由简化的Newton法，得,由弦截法，得,x0=0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.3468683325x4 = 0.3473702799x5 = 0.3472836048x6 = 0.3472985550 x7 = 0.3472959759x8 = 0.3472964208x9 = 0.3472963440 x10 = 0.3472963572x11 = 0.3472963553,x0=0.5;x1=0.4;x2 = 0.3430962343x3 = 0.3473897274x4 = 0.3472965093x5= 0.3472963553x6 = 0.3472963553,简化Newton法,弦截法,要达到精度10-8，简化Newton法迭代11次，弦截法迭代5次， Newton迭代法迭代4次。,无论前面哪种迭代法：,（Newton迭代法、,简化Newton法、,弦截法）,Newton迭代法,x0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017,是否收敛均与初值的位置有关。,如,x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.9631e-010 x5 = 0,收敛,发散,为防止Newton法发散，可增加一个条件： |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.13384x8= 2.32607 x9 = 1.90230 x10= 1.75248 x11= 1.73240 x12= 1.73205 x13= 1.73205,需迭代13次才达到精度要求,用Newton下山法，结果如下：,设f(x)=(x-x*)m g(x) ,m 2，m为整数，g(x*)0,则x*为方程f(x)=0的m重根。此时有 f(x*)=f (x*)= f(m-1) (x*)=0, f(m) (x*) 0,2.4.5 重根情形,方法一只要f (xk ) 0，仍可用Newton法计算，此时为线性收敛。,方法二若取,则(x*)=0，用迭代法求m重根，则具2阶收敛，但要知道m。,方法三还可令 则故x*是(x)=0的单根，对(x)用Newton法，可得 它是二阶收敛的，每次计算需要计算函数值，一阶、二阶导数。,关于精度控制问题,精度控制方法一,是一种比较简单的精度控制方法，特别是求复数根的时候，但其与真正误差的偏差为,当,则,这时 是很好的停机准则,但若 很大或很小，则与实际误差偏差较大。,关于精度控制问题,精度控制方法二,是一种最常用的停机准则，对于不动点（简单）迭代法,L难估计且L越大误差越大，故,这时取 ，可以得到更好的停机准则,关于精度控制问题,精度控制方法二,是一种最常用的停机准则，对于牛顿法,由,K越大，k越接近于xk，则越接近于实际误差。,得,P27-28习题二：2，5，8。,本章作业,二分法MATLAB程序,