非线性方程数值解法缩资料.ppt

第一章非线性方程和方程组的数值解法非线性方程根的概念给定非线性方程f(x)=0如果有α使得f(α)=0，则称α为f(x)=0的根或f(x)的零点.设有正整数m使得f(x)=(x-α)mg(x)且g(α)0，则当m2时，称α为f(x)=0的m重根；当m=1时，称α为f(x)=0的单根.若α为f(x)=0的m重根，则f(α)=f(α)==f(m-1)(α)=0,f(m)(α)0这里只讨论实根的求法.求根步骤（1）根的存在性.（2）根的隔离.（3）根的精确化.非线性方程求根的数值方法二分法迭代法单点迭代法(不动点迭代，Newton迭代法)多点迭代法(弦截法）迭代法的一般理论迭代法是一种逐次逼近的方法，它的基本思想是通过构造一个递推关系式(迭代格式)，计算出根的近似值序列,并要求该序列收敛于方程的根.单点迭代法将方程f(x)=0改写成等价形式x=(x)(1)建立迭代公式xk+1=(xk)(2)在根的附近任取一点x0，可得一序列.若收敛，即，且(x)连续，则对(2)两端取极限有α=(α)，从而α为方程(1)的根，也称为(x)的不动点，这种求根算法称为不动点迭代法（Picard迭代法）.(x)称为迭代函数.多点迭代法建立迭代公式xk+1=(xk-n+1,,xk-2,xk-1,xk)(3)对于迭代法需要考虑一下几个主要问题收敛性收敛速度计算效率迭代法的全局收敛性定义1设为f(x)=0的根，如果x0[a,b]，由迭代法产生的序列都收敛于根，则称该迭代法是全局收敛的.迭代法的局部收敛性定义2设方程x=(x)有根α,如果存在α的某个邻域:x-α，对任意初值x0，迭代过程所产生的序列均收敛于根α，则称该迭代法是局部收敛的.迭代过程的收敛速度定义3设迭代过程xk+1=(xk)产生的序列收敛于方程x=(x)的根α，记ek=α-xk，若则称迭代过程是p阶收敛的.特别地，当p=1时，称为线性收敛；当p1时，称为超线性收敛，当p=2时，称为平方收敛.p越大，收敛越快.效率指数定义3称为效率指数.其中p表示迭代的收敛阶，表示每步迭代的计算量.EI越大，计算效率越高.不动点迭代法不动点迭代法的整体收敛性定理1.1设(x)满足(1)当x[a,b]时，(x)[a,b]；(2)x1,x2[a,b]，有(x1)-(x2)Lx1-x2，L1则对任意初值x0[a,b],迭代过程xk+1=(xk)收敛于x=(x)在[a,b]上的惟一根，且有误差估计式证根的存在性由(2)知(x)连续.令f(x)=x-(x),f(a)0,f(b)0,从而f(x)=0在[a,b]上有根α，即x=(x)在[a,b]上有根α.根的唯一性设x=(x)在[a,b]上有两根α1,α2，α1α2，α1-α2=(α1)-(α2)Lα1-α2与L1矛盾.故α1=α2序列的收敛性xk+1-α=(xk)-(α)Lxk-α,xk+1-αLk+1x0-α由0L1有误差估计xk+1-xk=(xk)–(xk-1)Lxk-xk-1xk+2-xk+1=(xk+1)–(xk)L2xk-xk-1xk+p-xk+p-1Lpxk-xk-1xk+p-xkxk+p-xk+p-1+xk+p-1-xk+p-2++xk+1-xk(Lp+Lp-1++L)xk-xk-1=令p，有定理1.2设(x)在[a,b]上具有一阶导数，且(1)当x[a,b]时,(x)[a,b]；(2)x[a,b]，有(x)L1则对任意初值x0[a,b],迭代过程xk+1=(xk)收敛于x=(x)在[a,b]上的惟一根.不动点迭代法的局部收敛性定理1.3若(x)在方程x=(x)的根α的邻域内有一阶连续的导数，且(α)1,则迭代过程xk+1=(xk)具有局部收敛性证由连续函数性质，存在α的充分小邻域:x-α,使当x时，有(x)L1由微分中值定理有(x)–α=(x)–(α)=()x-αx-α故(x)，由定理1.2知对任意初值x0均收敛.不动点迭代法的局部收敛阶定理1.4若(x)在方程x=(x)的根α的邻域内有充分阶连续的导数，则迭代过程xk+1=(xk)在α邻域是p阶收敛的充分且必要条件是(j)(α)=0,j=1,2,,p-1(p)(α)0证充分性必要性(反证法)设迭代法xk+1=(xk)是p阶局部收敛的，如果结论不成立，那么必有最小正整数p0p，使得(j)(α)=0,j=1,2,,p0-1(p0)(α)0由充分性的证明知此迭代法