方程求根的迭代法

本章处理二分法和牛顿法在第二节课已讲过。加深算法收敛性方面的理解。介绍几种新方法。引言在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程f(x)=0的求根问题，其中f(x)为非线性函数。方程f(x)=0的根,亦称为函数f(x)的零点如果f(x)可以分解成,其中m为正整数且,则称x*是f(x)的m重零点,或称方程f(x)=0的m重根。当m=1时称x*为单根。若f(x)存在m阶导数,则是方程f(x)的m重根(m1)当且仅当)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(**xfxfxfxfmm记笔记当f(x)不是x的线性函数时，称对应的函数方程为非线性方程。如果f(x)是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称n次多项式构成的方程)0(00111nnnnnaaxaxaxa为n次代数方程,当n＞1时,方程显然是非线性的一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法数值解法步骤n①判定根的存在性。即方程有没有根？如果有n根，有几个根？n②确定根的分布范围。即将每一个根用区间隔n离开来，这个过程实际上是获得方程各根的n初始近似值。n③根的精确化。将根的初始近似值按某种方法n逐步精确化，直到满足预先要求的精度为止二分法（略）复习作业题不动点迭代对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。迭代法的基本思想为求解非线性方程f(x)=0的根，先将其写成便于迭代的等价方程其中为x的连续函数)(x)(xx即如果数使f(x)=0,则也有,反之,若,则也有,称为迭代函数任取一个初值,代入式的右端,得到*x)(**xx)(**xx0)(*xf)(x0x)(xx)(01xx再将代入式的右端,得到,依此类推,得到一个数列…，其一般表示1x)(xx)(12xx)(23xx),2,1,0()(1kxxkk称为求解非线性方程的简单迭代法。如果由迭代格式产生的序列收敛,即nx)(1kkxx*limxxnn则称迭代法收敛。实际计算中当然不可能也没必要无穷多步地做下去,对预先给定的精度要求ε，只要某个k满足1kkxx即可结束计算并取kxx*当然，迭代函数的构造方法是多种多样的。)(x例1用迭代法求方程在x=1.5附近的一个根解将方程改写成如下两种等价形式013xx1)(1)(3231xxxxxx相应地可得到两个迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值＝1.5，用上述两个迭代公式分别迭代，计算结果0x30111.51,(0,1,2,).kkxxxk（），kxk012345671.51.357211.330861.325881.324941.324761.324731.32472.,39.12,375.2,5.1,1(2)21031xxxxxkk几何意义通常将方程f(x)=0化为与它同解的方程的方法不止一种,有的收敛,有的不收敛,这取决于的性态,方程的求根问题在几何上就是确定曲线y=与直线y=x的交点P*的横坐标)(xx)(x)(xx)(xy=xyy=)(xy=x1)(0*x0)(1*xP0P2P*Q1Q2x1x0x2x*xyx0xx1x2x3x*y=)(x)(xP*P1(a)(b)几何意义y=xyy=xy=)(x1)(*x1)(*x（c）（d）P*x1x0xyx0xx1x2x3x*y=)(x)(xx*x2P*对方程f(x)=0可以构造不同的迭代公式,但迭代公式并非总是收敛。那么,当迭代函数满足什么条件时，相应的迭代公式才收敛呢？即使迭代收敛时，我们也不可能迭代很多次，而是迭代有限次后就停止，这就需要估计迭代值的误差，以便适时终止迭代。),2,1,0()(1kxxkk)(x不动点迭代收敛性定理1，2设函数在[a,b]上具有连续的一阶导数,且满足（1）对所有的x∈[a,b]有∈[a,b]（2）存在0L1,使所有的x∈[a,b]有≤L则方程在[a,b]上的解存在且唯一，对任意的∈[a,b]，迭代过程均收敛于。并有误差估计式)(x)(x)(x)(xx*x0x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk①②由连续函数介值定理知,必有∈[a,b],使所以有解存在,即假设有两个解和,,∈[a,b]，则，由微分中值定理有其中ξ是介于x*和之间的点从而有ξ∈[a,b]，进而有由条件(2)有1,所以-=0，即=，解唯一。证:构造函数,由条件（1）对任意的x∈[a,b]∈[a,b]有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(***xxx*xx~*xx~)(**xx)~(~xx)~)(()~()(~***xxxxxxx~0)(1)~(*xx)(x*xx~*xx~按迭代过程,有)(1kkxx))(()()(1*1**kkkxxxxxx1*1**))((kkkxxLxxxx0*2*21**xxLxxLxxLxxkkkk由于L1,所以有,可见L越小,收敛越快*limxxkk再证误差估计式1*1kkkxxLLxx01*1xxLLxxkk①②∵1*1**kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1(kkkxxLxxL1*1kkkxxLLxx∴即①得证。2121211))(()()(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxLxxkkkkkk即②得证。例2对方程,构造收敛的迭代格式,求其最小正根,计算过程保留4位小数。解容易判断[1,2]是方程的有根区间,且在此区间内,所以此方程在区间[1,2]有且仅有一根。将原方程改写成以下两种等价形式。0245xx045)(4xxf①,即不满足收敛条件。②,即此时迭代公式满足迭代收敛条件。425xx2,1145)(,42)(45xxxxx524xx,24)(5xx2,112.0)24(51)24(51)(5454xxx局部收敛性当迭代函数较复杂时,通常只能设法使迭代过程在根的邻域(局部)收敛。定理3设在的根的邻域中有连续的一阶导数,且则迭代过程具有局部收敛性。证:由于,存在充分小邻域△:,使成立这里L为某个定数,根据微分中值定理当故有由定理1知对于任意的都收敛)(x)(xx*x1)(*x)(1kkxx1)(*x*xx1)(*Lx))(()()(**xxxx**)(xxx***)(xxxxLxx)(1kkxx0x例3设,要使迭代过程局部收敛到,求的取值范围。解：由在根邻域具有局部收敛性时,收敛条件)5()(2xxx)(1kkxx5*x)5()(2xxxxx21)(5*x1521)(*ax15211a0522a所以051a例4已知方程在内有根,且在上满足,利用构造一个迭代函数,使局部收敛于。解:由可得,)(xxba,*xba,13)(x)(x)(xg),2,1,0()(1kxgxkk*x)(xxxxxx3)(3)()3)((21xgxxx1213)(21)3)((21)(xxxgbax,故,迭代公式1)(*xg)3)((21)(1kkkkxxxgx局部收敛迭代法的收敛速度一种迭代法具有实用价值，首先要求它是收敛的，其次还要求它收敛得比较快。定义2.2设迭代过程收敛于的根,记迭代误差若存在常数p（p≥1）和c（c0），使)(1kkxx)(xx*xkkxxe*ceepkkk1lim则称序列是p阶收敛的,c称渐近误差常数。特别地,p=1时称为线性收敛,p=2时称为平方收敛。1p2时称为超线性收敛。kx数p的大小反映了迭代法收敛的速度的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。定理4设迭代过程,若在所求根的邻域连续且则迭代过程在邻域是p阶收敛的。证:由于即在邻域,所以有局部收敛性,将在处泰勒展开)(1kkxx)()(xp*x0)(,0)()()(*)(*)1(**xxxxpp*x0)(*x*x1)(*x)(1kkxx)(kx*xpkpkkkxxpxxxxxxxx))((!1))((!21))(()()(*)(2*****根据已知条件得pkpkxxpxx))((!1)()(*)(*由迭代公式)(1kkxx及)(**xx有pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkk例5已知迭代公式收敛于证明该迭代公式平方收敛。证:迭代公式相应的迭代函数为21132kkkxxx3*3x2132)(xxx436)(232)(xxxx，将代入，根据定理4可知，迭代公式平方收敛。3*3x032336)(0)(33**xx，为了使迭代过程收敛或提高收敛的速度,可设法①提高初值的精度以减少迭代的次数②提高收敛的阶数p设是根的某个近似值,用迭代公式校正一次得又根据中值定理有kx*x)(1kkxx)(**xx))(()()(**1*kkkxxxxxx其中),(*kxx)(*kxx）（当范围不大时,设变化不大,其估计值为L,则有)(*1*kkxxLxx可见,若将迭代值与加权平均,则可得到的1kxkxkkkxLLxLx11111是比更好的近似根1kxkkxLLxLx1111*迭代法的加速（加权法）迭代：改进：或合并写成：kkkxLLxLx1111_1)(1_kkxxkkkLxxLx)(111例6用加权法加速技术求方程在0.5附近的一个根。解：因为在附近取L=-0.6，建立如下迭代公式xex5.00x6.0'5.05.05.0eexxkxkxkxexexkk6.06.116.0)6.0(111仍取,逐次计算得=0.56658…=0.56714。迭代4次便可得到精度的结果,而不用加速技术需迭代18次,效果显著。5.00x1x4x410埃特金（Aitken）方法在加权法中,估计L的值有时不太方便。假设在求得以后,先求出由,利用中值定理可得(在求根区间变化不大,用某个定值L近似地替代之)L将迭代值再迭代一次,得新的迭代值则将上述两个方程联立消去常数L化简可得kx)(~1kkxx)(**xx)()()()(~***1xxLxxxxkkk1~kx)~(11kkxx)~()()~(*1*1*1xxLxxxxkkkkkkkkkxxxxxxx1121