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

第二章非线性方程的求根方法第二章非线性方程的求根方法引言方程求根的二分法迭代法及其收敛性Newton迭代法方程是在科学研究中不可缺少的工具；方程求解是科学计算中一个重要的研究对象；几百年前就已经找到了代数方程中二次至五次方程的求解公式；但是，对于更高次数的代数方程目前仍无有效的精确解法；对于无规律的非代数方程的求解也无精确解法；因此，研究非线性方程的数值解法成为必然。2.1引言非线性方程的一般形式：f(x)=0代数方程（多项式）：f(x)=a0+a1x+……+anxn（an0）超越方程：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。1()2kkkbaba以[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满足不等式*22nnnnbabaxx*2nnbaxx证明：方法一（事后估计法）每次计算后判别（bn-an）/2是否成立，若成立，则停止计算，否则继续计算；方法二（事前估计法）由二分法精度控制的两种方法：*22nnnnbabaxx得：ln()lnln2bak这样就可以由给定的精度要求,事先计算出计算次数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附近的一个根。解：将所给方程改写成31xx假设初值x0=1.5是其根，代入得35721.115.113301xxx1≠x0，再将x1代入得33086.1135721.113312xxx2≠x1，再将x2代入得32588.1133086.113323xx如此下去，这种逐步校正的过程称为迭代过程。这里用的公式称为迭代公式，即311kkxxk=0,1,2,……迭代结果见下表：kxkkxk012341.51.357211.330861.325881.3249456781.324761.324731.324721.32472仅取六位数字，x7与x8相同，即认为x8是方程的根。x*≈x8=1.324722.3.1不动点迭代法将连续函数方程f(x)＝0改写为等价形式：x=(x)其中(x)也是连续函数，称为迭代函数。不动点：若x*满足f(x*)=0，则x*=(x*)；反之，若x*=(x*)，则f(x*)=0，称x*为(x)的一个不动点。不动点迭代：)(1kkxx(k=0,1,……)若对任意x0[a,b]，由上述迭代得序列{xk}，有极限*limxxkk则称迭代过程收敛，且x*=(x*)为(x)的不动点。)(xx)(xyxyx2x1x0y=x)(xy几何意义：但迭代法并不总令人满意，如将前述方程x3-x-1=0改写为另一等价形式：13xx131kkxx此时称迭代过程发散。则有x1=2.375，x2=12.396，x3=1904,结果越来越大。仍取初值x0=1.5，建迭代公式：012*xxxxO)(xyxy0231*xxxxxO)(xyxy收敛附近较平缓在*)(xx2013*xxxxxO)(xyxy*012xxxxO)(xyxy发散附近较陡峭在*)(xx定理3（存在性）设(x)C[a,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不动点的存在性与迭代法的收敛性不动点的存在性证明：证：若aa)(bb)(或显然(x)有不动点；否则，设aa)(bb)(则有aa)(bb)(（因a≤(x)≤b）记xxx)()(则有0)()(ba故存在x*使得0*)(x即**)(xxx*即为不动点。不动点存在的唯一性证明：设有x1*≠x2*,使得*1*1)(xx*2*2)(xx则|||)(||)()(|||*2*1*2*1*2*1xxxxxx其中，ξ介于x1*和x2*之间。由定理条件1|)(|Lx可得||||*2*1*2*1xxxx矛盾！故x1*=x2*，不动点唯一存在。定理4（全局收敛性）设(x)C[a,b]且满足以下两个条件：则对任意x0[a,b]，由xn+1=(xn)得到的迭代序列{xn}收敛到(x)的不动点x*，并有误差估计：||11||1*nnnxxLxx011*xxLLxxnn（2）若(x)在[a,b]一阶连续，且存在常数0L1，使得对任意x[a,b]，|`(x)|≤L1成立（1）对于任意x[a,b]，有a≤(x)≤b；)()(**1xxxxnn|||)(||)()(|||*1*1*xxxxxxnnn||||*1*xxLxxnn||||*0*xxLxxnn0||lim||lim*0*xxLxxnnnn(0L1)故迭代格式收敛。*limxxnn所以证明：||||||||||||*1*11*11*xxLxxxxxxxxxxxxnnnnnnnnnn||||)1(1*nnnxxxxL||11||1*nnnxxLxx反复递推，可得误差估计式011*xxLLxxnn定义设(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}发散。**0lim||lim||nnnnxxLxx(L≥1)故迭代格式发散。（L=1？）limnnx所以定理4的条件是迭代法收敛的充分不必要条件；且收敛时L越小收敛越快;定理4条件不满足时，收敛与否不但和迭代函数(x)有关，且与初值x0也有关；由于|`(x)|≤L1的条件判断比较困难，所以常用|`(x)|1来代替；对于给定的精度要求|x*-xk|≤由于很难估计，采用事后估计法不动点迭代法可以求方程的复根和偶数重根。关于不动点迭代法的几点说明：10*1nnLxxxxL*111||||||1nnnnnxxxxxxL，L大误差大。321kkkxxxkkxx31211(3)5kkkxxx)3(211kkkxxx例032x用不同方法求在x=2附近的根。解：格式（1）格式（2）格式（3）格式（4）取x0=2，对上述四种方法，计算三步所得结果如下：kxk(1)(2)(3)(4)0x022221x131.51.81.752x2921.7521.7321433x3871.51.7380991.732051注：x*=1.7320508……收敛阶定义：收敛速度的快慢是衡量算法优劣的一个重要标准，而刻画收敛速度快慢的一个指标就是收敛阶，设序列{xk}收敛于x*，若误差ek=xk–x*当k时成立下列渐近关系式：1limkpkkece（c0,p≥1）则称序列{xk}是p阶收敛于x*，c称为误差常数，也可称相应的迭代方法是p阶收敛的。特别地，p=1，0c1时称线性收敛,此时c称为收敛率；p=2时称平方收敛；p1时称超线性收敛，且p越大，收敛越快。一阶收敛vs.二阶收敛：一阶收敛vs.二阶收敛：定理6：设x*为x=(x)的不动点，若(x)满足：（1）(x)在x*附近是p次连续可微的(p1)；（2）则迭代过程xn+1=(xn)在点x*的邻域内是p阶收敛的。pnnpnnnxxpxxxxxxxx))((!1))((!21))(()()(*)(2*****0*)(,0*)(*)(*)()()1(xxxxpp)(!|*||*)()(||*|)(1nppnnnpxxxxxx得|*)(|!1|)(|!1lim|*||*|lim)()(1xppxxxxpnpnpnnn所以故迭代过程xn+1=(xn)p阶收敛，若极限为0，超P阶。证：由Taylor公式例：例：由定理6可得，此时迭代格式xk+1=g(xk)，至少2阶收敛。2.3.3迭代收敛的加速方法解：由前知，迭代格式xk+1=xk3-1是发散的。现用埃特金法迭代格式迭代法计算。取(x)=x3-1，结果如下