第7章 非线性方程与方程组的数值解法

上页下页第7章非线性方程与方程组的数值解法•7.1方程求根与二分法•7.2不动点迭代法及其收敛性•7.3迭代收敛的加速方法•7.4牛顿法•7.5弦截法与抛物线法•7.6求根问题的敏感性与多项式的零点•7.7解非线性方程组的牛顿迭代法上页下页非线性是实际问题中经常出现的，并且在科学与工程计算中的地位越来越重要，很多我们熟悉的线性模型都是在一定条件下由非线性问题简化得到的，为得到更符合实际的解答，往往需要直接研究非线性模型，从而产生非线性科学，它是21世纪科学技术发展的重要支柱.非线性问题的数学模型有无限维的如微分方程，也有有限维的.但要用计算机进行科学计算都要转化为非线性的单个方程或方程组的求解.从线性到非线性是一个质的变化，方程的性质有本质不同，求解方法也有很大差别.本章将首先讨论单个方程求根，然后再简单介绍非线性方程组的数值解法.上页下页7.1方程求根与二分法7.1.1引言本章主要讨论求解单变量非线性方程f(x)=0.(1.1)其中x∈R,f(x)∈C[a,b],[a,b]也可以是无穷区间.如果实数x*满足f(x*)=0，则称x*是方程(1.1)的根，或称x*是函数f(x)的零点，若f(x)可分解为f(x)=(x-x*)mg(x)，其中m为正整数,且g(x*)≠0.则称x*为方程(1.1)的m重根，或x*为f(x)的m重零点，m=1时x*为单根，若x*是f(x)的m重零点，且g(x)充分光滑，则有.0)(,0)()()()()1(xfxfxfxfmm上页下页如果函数f(x)是多项式函数，即)2.1(),0()(01110aaxaxaxaxfnnnn其中系数a0≠0,ai(i=0,1,,n)为实数，则称方程(1.1)为n次代数方程.根据代数基本定理可知，n次代数方程在复数域有且只有n个根(含重根,m重根为m个根),当n=1,2时的求根公式是熟知的，n=3,4时的求根公式可在数学手册中查到，但比较复杂，不适合数值计算.n5时就不能直接用公式表示方程的根，所以n3时求根仍用一般的数值方法.另一类是超越方程，例如010sin10xex它在整个x轴上有无穷多个解，若x取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调x的定义域，即x的求解区间[a,b].上页下页另外，非线性问题一般不存在直接的求解公式，故没有直接方法求解，都要使用迭代法求解，迭代法要求先给出根x*的一个近似，若f(x)∈C[a,b]且f(a)f(b)0，根据连续函数性质中的介值定理可知方程f(x)=0在(a,b)内至少有一个实根，这时称[a,b]为方程(1.1)的有根区间，通常可通过逐次搜索法求得方程(1.1)的有根区间.上页下页例1求方程f(x)=x3-11.1x2+38.8x-41.77=0的有根区间.解根据有根区间定义，对f(x)=0的根进行搜索计算，结果如表x0123456f(x)的符号--++--+由此可知方程f(x)=0的有根区间为[1,2],[3,4],[5,6].上页下页7.1.2二分法设f(x)在区间[a,b]上连续,f(a)·f(b)0,则在[a,b]内有方程的根.取[a,b]的中点将区间一分为二.若f(x0)=0,则x0就是方程的根,否则判别根x*在x0的左侧还是右侧.,)(210bax若f(a)·f(x0)0,则x*∈(a,x0),令a1=a,b1=x0;若f(x0)·f(b)0,则x*∈(x0,b),令a1=x0,b1=b.不论出现哪种情况,(a1,b1)均为新的有根区间,它的长度只有原有根区间长度的一半,达到了压缩有根区间的目的.上页下页对压缩了的有根区间,又可实行同样的步骤,再压缩.如此反复进行,即可的一系列有根区间套],[],[],[11nnbababa由于每一区间都是前一区间的一半，因此区间[an,bn]的长度为)(ababnnn21若每次二分时所取区间中点都不是根，则上述过程将无限进行下去.当n→时，区间必将最终收缩为一点x*，显然x*就是所求的根.上页下页若取区间[an,bn]的中点)(nnnbax21作为x*的近似值，则有下述误差估计式111*()(),(1.3)22nnnnxxbaba只要n足够大,(即区间二分次数足够多)，误差就可足够小.),(,*11nnnbaxx由于在偶重根附近曲线y=f(x)为上凹或下凸,即f(a)与f(b)的符号相同,因此不能用二分法求偶重根.上页下页例2用二分法求例1中方程f(x)=x3-x-1=0的实根,要求误差不超过0.005.解由例1可知x*∈(1,1.5),要想满足题意，即：则要005.021)15.1(21)(21211nnnab|x*-xn|≤0.005由此解得取n=6,按二分法计算过程见下表,x6=1.3242为所求之近似根.,6.512lg2n上页下页nanbnxnf(xn)说明01234561.01.251.251.31251.31251.31251.32031.51.51.3751.3751.34381.32811.32811.251.3751.31251.34381.32811.32031.3242-+-++--(1)f(a)0,f(b)0(2)根据精度要求，取到小数点后四位即可.二分法的优点是算法简单，且总是收敛的，缺点是收敛的太慢，故一般不单独将其用于求根，只是用其为根求得一个较好的近似值.上页下页二分法的计算步骤:步骤1准备计算函数f(x)在区间[a,b]端点处的值f(a),f(b).若f(a)·f((a+b)/2)0,则以(a+b)/2代替b，否则以(a+b)/2代替a.步骤2二分计算函数f(x)在区间中点(a+b)/2处的值f((a+b)/2).步骤3判断若f((a+b)/2)=0，则(a+b)/2即是根，计算过程结束，否则检验.反复执行步骤2和步骤3，直到区间[a,b]长度小于允许误差ε，此时中点(a+b)/2即为所求近似根.上页下页7.2不动点迭代法及其收敛性7.2.1不动点与不动点迭代法将方程f(x)=0改写为等价方程形式x=(x).(2.1)若要求x*满足f(x*)=0，则x*=(x*)；反之亦然，称x*为函数(x)的一个不动点.求f(x)的零点就等于求(x)的不动点，选择一个初始近似值x0，将它代入(2.1)右端，即可求得x1=(x0).上页下页.limxxkk可以如此反复迭代计算xk+1=(xk)(k=0,1,2,).(2.2)(x)称为迭代函数.如果对任何x0∈[a,b]，由(2.2)得到的序列{xk}有极限则称迭代方程(2.2)收敛.且x*=(x*)为(x)的不动点，故称(2.2)为不动点迭代法.上述迭代法是一种逐次逼近法，其基本思想是将隐式方程(2.1)归结为一组显式的计算公式(2.2)，迭代过程实质上是一个逐步显式化过程.上页下页当(x)连续时，显然x*就是方程x=(x)之根(不动点).于是可以从数列{xk}中求得满足精度要求的近似根.这种求根方法称为不动点迭代法,1()(0,1,2,)kkxxk称为迭代格式,(x)称为迭代函数,x0称为迭代初值,数列{xk}称为迭代序列.如果迭代序列收敛,则称迭代格式收敛,否则称为发散.（几何意义的解释见书p215页）1()(0,1,2,)kkxxk.limxxkk上页下页03224xxx分别按以上三种形式建立迭代公式，并取x0=1进行迭代计算，结果如下：14)(2xxx32)(243xxxx4121)23()(xxxx解对方程进行如下三种变形：例3用迭代法求方程x4+2x2-x-3=0在区间[1,1.2]内的实根.上页下页准确根x*=1.124123029,可见迭代公式不同,收敛情况也不同.第二种公式比第一种公式收敛快得多,而第三种公式不收敛.73496,8.49530710xx12()41kkkxxx4213()23kkkkxxxx12411()(32)kkkkxxxx26271.124123xx671.124123xx参见书p215页-例3.上页下页例3表明原方程化为(2.1)的形式不同，有的收敛，有的不收敛，有的发散，只有收敛的的迭代过程(2.2)才有意义，为此我们首先要研究(x)的不定点的存在性及迭代法(2.2)的收敛性.上页下页7.2.2不动点的存在性与迭代法的收敛性首先考察(x)在[a,b]上不动点的存在唯一性.定理1设(x)∈C[a,b]满足以下两个条件：(1)对任意x∈[a,b]有a≤(x)≤b.)4.2(.)()(yxLyx(2)存在正数L1，使对任意x,y∈[a,b]都有则(x)在[a,b]上存在唯一的不动点x*.证明先证不动点的存在性.若(a)=a或(b)=b，显然(x)在[a,b]上存在不动点.因为a≤(x)≤b，以下设(a)a及(b)b定义函数上页下页.)()(xxxf显然f(x)∈C[a,b],且满足f(a)=(a)-a0,f(b)=(b)-b0,由连续函数性质可知存在x*∈(a,b)使f(x*)=0，即x*=(x*)，x*即为(x)的不动点.再证不动点的唯一性.设x1*,x2*∈[a,b]都是(x)的不动点，则由(2.4)得.)()(21212121xxxxLxxxx引出矛盾，故(x)的不动点只能是唯一的.证毕.在(x)的不动点存在唯一的情况下，可得到迭代法(2.2)收敛的一个充分条件.上页下页定理2设(x)∈C[a,b]满足定理1中的两个条件，则对任意x0∈[a,b]，由(2.2)得到的迭代序列{xk}收敛到(x)的不动点x*，并有误差估计式)6.2(.1)5.2(.1101kkkkkxxLLxxxxLLxx证明设x*∈[a,b]是(x)在[a,b]上的唯一不动点,由条件(1)，可知{xk}∈[a,b]，再由(2.4)得.)()(011xxLxxLxxxxkkkk因0L1，故当k→∞时序列{xk}收敛到x*.上页下页下面证明估计式(2.5)，由(2.4)有111)()(kkkkkkxxLxxxx.01212xxLxxLkkk于是对任意正整数p有.11)1()(010101211211xxLLxxLLLxxLLLxxxxxxxxkpkkpkpkkkpkpkpkpkkpk上述令p→∞,注意到limxk+p=x*(p→∞)即得(2.5)式.上页下页又由于对任意正整数p有.1111)(111211211kkkkpkkppkkpkpkpkpkkpkxxLxxLLxxLLLxxxxxxxx上述令p→∞,及limxk+p=x*(p→∞)即得(2.6)式.证毕.迭代过程是个极限过程.在用迭代法进行时，必须按精度要求控制迭代次数.误差估计式(2.5)原则上确定迭代次数，但它由于含有信息L而不便于实际应用.而误差估计式(2.6)是实用的，只要相邻两次计算结果的偏差足够小即可保证近似值xk具有足够精度.上页下页对定理1和定理2中的条件(2)可以改为导数，即在使用时如果(x)∈C[a,b]且对任意x∈[a,b]有)7.2(.1)(Lx则由微分中值定理可知对任意x,y∈[a,b]有).,(,)())(()()(bayxLyxyx故定理中的条件(2)是成立的.上页下页例如，在前面例3中采用的三种迭代公式，在隔根区间(1,1.2)内，有11.051544144)(112xxx187.0)2.1