《数值分析-第7章非线性方程求根》由会员分享，可在线阅读，更多相关《数值分析-第7章非线性方程求根（88页珍藏版）》请在金锄头文库上搜索。
1、第7章 非线性方程求根,7.1 方程求根与二分法 7.2 迭代法及其收敛性 7.3 迭代收敛的加速方法 7.4 牛顿法 7.5 弦截法与抛物线法 7.6 解非线性方程组的牛顿迭代法,7.1 方程求根与二分法,例如代数方程 x5-x3+24x+1=0, 超越方程 sin(5x2)+e-x=0.,对于不高于4次的代数方程已有求根公式，而高于4次的代数方程则无精确的求根公式，至于超越方程 就更无法求出其精确的解，因此，如何求得满足一定精度要求的方程的近似根也就成为迫切需要解决的问题，为此，本章介绍几种常见的非线性方程的近似求根方法.,7.1.1 引言,本章主要讨论单变量非线性方程,f(x)=0 (1
2、.1),的求根问题，这里xR, f(x)Ca, b. 在科学与工程计算中有大量方程求根问题，其中一类特殊的问题是多项式方程,其中系数ai(i=0,1,n)为实数.,方程f(x)=0的根x*，又称为函数f(x)的零点，它使得f(x*)=0，若f(x)可分解为,f(x)=(x-x*)mg(x)，,其中m为正整数，且g(x*)0. 当m=1时，则称x*为单根，若m1称x*为(1.1)的m重根，或x*为函数f(x)的m重零点. 若x*是f(x)的m重零点，且g(x)充分光滑，则,当f(x)为代数多项式(1.2)时，根据代数基本定理可知，n次代数方程f(x)=0在复数域有且只有n个根(含复根，m重根为m
3、个根).,n=1,2时方程的根是大家熟悉的，n=3,4时虽有求根公式但比较复杂，可在数学手册中查到，但已不适合数值计算，而n5时就不能用公式表示方程的根.因此，通常对n3的多项式方程求根与一般连续函数方程(1.1)一样都可采用迭代法求根.,迭代法要求给出根x*的一个近似，若f(x)Ca, b且f(a)f(b)0，根据连续函数性质中的介值定理可知方程f(x)=0在(a, b)内至少有一个实根，这时称a, b为方程(1.1)的有根区间，通常可通过逐次搜索法求得方程(1.1)的有根区间.,若 f(x)在a,b内连续, 且 f(a) f(b)0, 则 f(x)=0 在a,b内必有根; 若f(x)在a,
4、b内还严格单调, 则f(x)=0在a,b内只有一根, 据此可得求隔根区间的两种方法.,1. (描)做图法,画出 y=f(x) 的草图, 由f(x)与横轴交点的大概位置来确定隔根区间; 或者利用导函数f(x)的正、负与函数f(x)的单调性的关系确定根的大概位置.,求隔根区间的一般方法,若f(x)比较复杂, 还可将方程f(x)=0化为一个等价方程(x)=(x), 则曲线y=(x)与y=(x)之交点A(x*,y*)的横坐标 x*即为原方程之根, 据此也可通过作图求得x*的隔根区间.,例1 判别下列方程有几个实根，并求隔根区间. (1) f(x)=x3-x-1=0, (2) f(x)=x4-4x3+1
5、=0.,解 (1)将方程变形为 x3=x+1 绘曲线图 y=x3 及 y=x+1 由图可知, 方程只有一个实根x*(1, 1.5)，所以(1, 1.5) 即为其隔根区间.,(2) 方程 f(x)=x4-4x3+1=0.,由f(x)= 4x2(x-3)=0 得驻点x1=0, x2=3. 该二点将实轴分为三个区间: (-, 0), (0, 3)，(3, +),f(x)在此三个区间上的符号分别为“-”、“-”、“+”, 又知 f(-)0, f(0)=10, f(3)=-260.,可见f(x)仅有两个实根, 分别位于(0, 3), (3, +), 又f(4)=10, 所以第二根的隔根区间可缩小为(3,
6、 4).,以上分析可用下表表示,2. 逐步搜索法,从区间a, b的左端点 a 出发, 按选定的步长h 一步步向右搜索，若,f(a+jh)f(a+(j+1)h)0 (j=0,1,2,),则区间a+jh, a+(j+1)h内必有根. 搜索过程也可从b开始，这时应取步长 h0.,7.1.2 二分法,设f(x)在区间a, b上连续, f(a)f(b)0, 则在a, b,内有方程的根. 取a, b的中点,将区间一分为二. 若 f (x0)=0, 则x0就是方程的根, 否则判别根 x*在 x0 的左侧还是右侧.,若f(a) f(x0)0, 则x*(a, x0), 令 a1= a, b1=x0;,若f(x0
7、) f(b)0, 则x*(x0 , b), 令 a1=x0, b1=b.,不论出现哪种情况, (a1, b1)均为新的有根区间, 它的长度只有原有根区间长度的一半, 达到了压缩有根区间的目的.,对压缩了的有根区间, 又可实行同样的步骤, 再压缩. 如此反复进行, 即可的一系列有根区间套,由于每一区间都是前一区间的一半，因此区间an , bn的长度为,若每次二分时所取区间中点都不是根，则上述过程将无限进行下去. 当 n 时，区间必将最终收缩为一点x* ，显然x*就是所求的根.,若取区间an , bn的中点,作为x*的近似值，则有下述误差估计式,只要 n 足够大, (即区间二分次数足够多)，误差就
8、可足够小.,由于在偶重根附近曲线 y=f(x) 为上凹或下凸, 即 f(a)与f(b)的符号相同, 因此不能用二分法求偶重根.,例2 用二分法求例1中方程 f(x)=x3-x-1=0的实根,要求误差不超过0.005.,解 由例1可知x*(1, 1.5), 要想满足题意，即：,则要,|x*-xn|0.005,由此解得 取n=6, 按二分法计算过程见下表, x6 = 1.3242 为所求之近似根.,二分法的优点是算法简单，且总是收敛的，缺点是收敛的太慢，故一般不单独将其用于求根，只是用其为根求得一个较好的近似值.,二分法的计算步骤:,步骤1 准备 计算函数f(x)在区间a, b端点处的值f(a),
9、 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)的零点
10、就等于求(x)的不动点，选择一个初始近似值x0，将它代入(2.1)右端，即可求得,x1=(x0).,可以如此反复迭代计算,xk+1=(xk) (k=0,1,2,). (2.2),(x)称为迭代函数. 如果对任何x0a, b，由(2.2)得到的序列xk有极限,则称迭代方程(2.2)收敛. 且x*=(x*)为(x)的不动点，故称(2.2)为不动点迭代法.,上述迭代法是一种逐次逼近法，其基本思想是将隐式方程(2.1)归结为一组显式的计算公式(2.2)，迭代过程实质上是一个逐步显式化过程.,当(x)连续时，显然x*就是方程x=(x)之根(不动点). 于是可以从数列xk中求得满足精度要求的近似根. 这种
11、求根方法称为不动点迭代法,称为迭代格式, (x)称为迭代函数, x0 称为迭代初值,数列xk称为迭代序列. 如果迭代序列收敛, 则称迭代格式收敛,否则称为发散. （几何意义的解释见书p265页）,分别按以上三种形式建立迭代公式，并取x0=1进行迭代计算，结果如下：,解 对方程进行如下三种变形：,例3 用迭代法求方程x4+2x2-x-3=0 在区间1, 1.2内的实根.,准确根 x* = 1.124123029, 可见迭代公式不同, 收敛情况也不同. 第二种公式比第一种公式收敛快得多, 而第三种公式不收敛.,参见书p266页-例3.,例3表明原方程化为(2.1)的形式不同，有的收敛，有的不收敛，
12、有的发散，只有收敛的的迭代过程(2.2)才有意义，为此我们首先要研究(x)的不定点的存在性及迭代法(2.2)的收敛性.,7.2.2 不动点的存在性与迭代法的收敛性,首先考察(x)在a, b上不动点的存在唯一性.,定理1 设(x)Ca, b满足以下两个条件：,1 对任意xa, b有a(x)b.,2 存在正数L1，使对任意x,ya, b都有,则(x)在a, b上存在唯一的不动点x*.,证明 先证不动点的存在性. 若(a)=a或(b)=b，显然(x)在a, b上存在不动点. 因为a(x)b，以下设(a)a及(b)b定义函数,显然f(x)Ca, b,且满足f(a)=(a)-a0, f(b)=(b)-b
13、0, 由连续函数性质可知存在 x*(a, b) 使 f(x*)=0，即x*=(x*)，x*即为(x)的不动点.,再证不动点的唯一性. 设x1*, x2*a, b都是(x)的不动点，则由(2.4)得,引出矛盾，故(x)的不动点只能是唯一的. 证毕.,在(x)的不动点存在唯一的情况下，可得到迭代法(2.2)收敛的一个充分条件.,定理2 设(x)Ca, b满足定理1中的两个条件，则对任意x0a, b，由(2.2)得到的迭代序列xk收敛到的不动点x*，并有误差估计式,证明 设x*a, b是(x)在a, b上的唯一不动点,由条件1，可知xka, b，再由(2.4)得,因0L1，故当k时序列xk收敛到x*
14、.,下面证明估计式(2.5)，由(2.4)有,于是对任意正整数p有,上述令p, 注意到limxk+p=x* (p)即得(2.5)式.,又由于对任意正整数p有,上述令p, 及limxk+p=x* (p)即得(2.6)式. 证毕.,迭代过程是个极限过程. 在用迭代法进行时，必须按精度要求控制迭代次数. 误差估计式(2.5)原则上确定迭代次数，但它由于含有信息L而不便于实际应用. 而误差估计式(2.6)是实用的，只要相邻两次计算结果的偏差足够小即可保证近似值xk具有足够精度.,对定理1和定理2中的条件2可以改为导数，即在使用时如果(x)Ca, b且对任意xa, b有,则由微分中值定理可知对任意x,
15、ya, b有,故定理中的条件2是成立的. 见书p269.,例如，在前面例3中采用的三种迭代公式，在隔根区间(1, 1.2)内，有,故前两个迭代公式收敛，第三个迭代公式不收敛.,7.2.3 局部收敛性与收敛阶,上面给出了迭代序列xk在区间a, b上的收敛性,通常称为全局收敛性. 有时不易检验定理的条件，实际应用时通常只在不动点x*的邻近考察其收敛性，即局部收敛性.,定义1 设(x)有不动点x*，如果存在x*的某个邻域R: |x-x*|，对任意x0R，迭代公式(2.2)产生的序列xkR，且收敛到x*，则称迭代法(2.2)局部收敛.,定理3 设x*为(x)的不动点， 在x*的某个邻域连续，且 ，则迭代法(2.2)局部收敛.,证明 由连续函数的性质，存在不动点x*的某个邻域R: |x-x*|，使对于任意xR成立,此外，对于任意xR，总有(x)R，这时因为,于是依据定理2可以断定迭代过程xk+1=(xk)对于任意初值x0R均收敛. 证毕.,例4 用不同迭代法求方程x2-3=0的根 .,解 这里f(x)= x2-3，可以改写为各种不同的等价形式x=(x)，其不动点为 ，
