数值分析第7章非线性方程的数值解法46;.ppt

1,在科学研究的数学问题中更多的是非线性问题，它们又常常归结为非线性方程或非线性方程组的求解问题。,2,第7章 非线性方程与方程组的数值解法/*Numerical Solutions of Nonlinear Equations*/,7.1 方程求根与二分法 7.2 不动点迭代法及其收敛性 7.3 迭代收敛的加速方法 7.4 牛顿法 7.5 弦截法与抛物线法 7.6 求根问题的敏感性与多项式的零点7.7 非线性方程组的数值解法,3,7.1 方程求根与二分法,引言,（1.1）,单变量非线性方程的一般形式,其中 也可以是无穷区间.,f(x)是高次多项式函数或超越函数,（1.2）,如果函数 是多项式函数，即,其中 为实数，则称方程(1.1)为 次代数方程.,超越函数,不能表示为多项式的函数,如(x)=3x5-2x4+8x2-7x+1,(x)=e2x+1-xln(sinx)-2,高次代数方程,超越方程,4,若 是 的 重零点，且 充分光滑，则,次方程在复数域有且只有 个根（含重根，重根为 个根）.,超越方程,它在整个 轴上有无穷多个解，若 取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调 的定义域，即 的求解区间,如果实数 满足，则称 是方程(1.1)的根，或称 是 的零点.,若 可分解为,其中 为正整数，且 则称 为方程(1.1)的 重根，或 为 的 重零点，时为单根.,结论,5,通常方程根的数值解法大致分为三个步骤进行：,非线性问题一般不存在直接的求解公式，要使用迭代法.,本章将介绍常用的求解非线性方程的近似根的几种数值解法,判定根的存在性。即方程有没有根？如果有根，有几个根？,确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。,根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止.,6,如何求方程 的有根区间？,设 f(x)Ca,b,且 f(a)f(b)0,存在(a,b)，使 f()=0.,根的存在性定理闭区间上连续函数的介值定理,有根区间,如果f(x)在a,b上还是单调递增或递减的，则f(x)=0仅有一个实根。,(1)描图法,画出y=f(x)的略图，从而看出曲线与x轴交点的大致位置。也可将f(x)=0等价变形为g1(x)=g2(x)的形式，y=g1(x)与y=g2(x)两曲线交点的横坐标所在的子区间即为含根区间。,例1 求方程3x-1-cosx=0的有根区间。,方程等价变形为3x-1=cosx，,y=3x-1与y=cosx的图像只有一个交点位于0.5，1内。,7,对 的根进行搜索计算，,例2 求方程 的有根区间.,由此可知方程的有根区间为,(2)逐步搜索法,先确定方程f(x)=0的所有实根所在的区间为a,b,从x0=a 出发,以步长 h=(b-a)/n 其中n是正整数，在a,b内取定节点：xi=x0ih(i=0,1,2，n)计算f(xi)的值,依据函数值异号及实根的个数确定有根区间,通过调整步长，总可找到所有有根区间。,解,8,二分法,求解方程f(x)=0的近似根的一种常用的简单方法。,原理,基本思想,设函数f(x)在闭区间a,b上连续,且f(a)f(b)0,则 f(x)=0在(a,b)内必有实根区间。,逐步将区间二等分,通过判断区间端点f(x)的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。,具体做法,9,以此类推,由二分法的过程知,(1),(2),(3),作为根的近似,可得一个近似根的序列,10,（1.3）,且,(4),只要二分足够多次（即 充分大），便有,这里 为预定的精度.,要使,解：,例3 用二分法求方程 在区间 上的根，误差限为，问至少需对分多少次？,11,二分法的算法,步骤1 准备 计算 在有根区间 端点处的值,步骤2 二分 计算 在区间中点 处的值,步骤3 判断 若，则 即是根，计算过程结束，否则检验.,12,13,例4 求方程,在区间 内的一个实根，要求准确到小数点后第2位.,欲使,只需，即只要二分6次，便能达到预定的精度.,解,得到新的有根区间,14,二分法对多个零点的情况，只能算出其中一个零点。即使 f(x)在a,b上有零点，也未必有 f(a)f(b)0。,不管有根区间多大,总能求出满足精度要求的根,且对函数f(x)的要求不高,只要连续即可,计算亦简单。,优点,缺点,注：用二分法求根，最好先给出 f(x)草图以确定根的大概位置。或用搜索程序，将a,b分为若干小区间，对每一个满足 f(ak)f(bk)0 的区间调用二分法程序，可找出区间a,b内的多个根，且不必要求 f(a)f(b)0。,15,7.2 不动点迭代法及其收敛性,不动点与不动点迭代法/*Fixed-Point Iteration*/,（2.1）,若 满足，则；反之亦然，称为函数 的一个不动点.,求 的零点就等价于求 的不动点.,基本思想,（2.2）,称为迭代函数.,得到的序列 有极限,如果对任何，由迭代,不动点迭代法,16,则称迭代法收敛，且 为 的不动点，,不动点迭代是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。,对预先给定的精度要求，只要某个k满足,即可结束计算并取,迭代终止的判定,17,几何意义,交点的横坐标,y=x,18,19,例5 求方程,（2.3）,在 附近的根,设将方程改写成,建立迭代公式,解,各步迭代的结果如下表,即为所求的根.,如果仅取6位数字，结果 与 完全相同，,发散,说明：迭代函数不唯一，迭代点列可能收敛，也可能发散，迭代收敛与否不仅与迭代函数有关，还与初始点有关。,20,7.2.2 不动点的存在性与迭代法的收敛性,不动点的存在唯一性定理,证明,存在性,若 或，则不动点为 或，,因，,以下设 及，,定义函数,显然，,且,由零点定理知存在,使,即,21,唯一性,设 都是 的不动点，,故 的不动点是唯一的.,则由,即为 的不动点.,得,矛盾.,（2.5）,L 越 收敛越快,小,事前估计：选取k，预先估计迭代次数。,22,证明,设 是 在 上的唯一不动点，,由条件，可知,因，故当 时序列 收敛到.,又由,误差估计,收敛性,由,（2.6）,得,反复递推得,23,迭代过程的控制,只要相邻两次计算结果的偏差 足够小，即可保证,近似值 具有足够精度.,事后估计,事前估计：选取k，预先估计迭代次数。,注：,定理1、2的条件(2)可替换为,（2.7）,如果 且对任意 有,则由中值定理可知对 有,24,例5,又因，,而当 时，在区间 中 不满足定理条件.,当 时，,在区间 中，,所以迭代法是收敛的.,25,7.2.3 局部收敛性与收敛阶,迭代序列 在区间 上的收敛性，,全局收敛性,定义1 设 有不动点,如果存在 的某个邻域 对任意，迭代 产生的序列 且收敛到，则称迭代法局部收敛.,定理3 设 为 的不动点，在 的某个邻域连续，且，则迭代法 局部收敛.,局部收敛性,证明,由连续函数的性质，存在 的某个邻域,使对于任意 成立,所以，,对于任意，,总有。,因为,26,迭代序列的收敛速度,例6 用不同方法求方程 的根,解,构造不同的迭代法,27,取，对上述4种迭代法，计算三步所得的结果如下表.,从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.,注意.,迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中.,28,求方程xex-1=0在0.5附近的根,精度要求=10-3。,可以验证方程xex-1=0在区间0.5,0.61内仅有一个根。,例7,改写方程为x=e-x,建立迭代格式,由于(x)=e-x,在0.5,0.61上有|(x)|e-0.50.6 1，且(x)0.5,0.61，所以迭代法收敛。,取x0=0.5,得,解,29,所以,取近似根x10=0.56691满足精度要求。,如果精度要求为=10-5,则由,可知,需要迭代20次。,实际上,方程在区间0.55,0.6上有唯一根，而在区间0.55,0.6上有|(x)|e-0.550.581。若取L=0.58，则有,注意：这里迭代次数20是充分的但不是必要的。,可知,只需迭代17次。,30,迭代法的收敛阶/*the order of Convergence*/,特别地,时称线性收敛，,时称超线性收敛，,时称平方收敛.,数p的大小反映了迭代法收敛的速度的快慢，p愈大，则收敛的速度愈快，故迭代法的收敛阶是对迭代法收敛速度的一种度量。,设(x)连续,|ek+1|=|xk+1-x|=|(xk)-(x)|=|(k)|ek|,当(x)0时,有,所以,当(x)0时,简单迭代法只具有线性收敛。,31,由于，可以断定迭代过程 局部收敛.,将 在根 处做泰勒展开，,则有,证明,由上式得,因此,当 时有,（2.9）,32,迭代过程的收敛速度依赖于迭代函数 的选取.,如果当 时，,注：,则该迭代过程是线性收敛.,33,7.3 迭代收敛的加速方法/*Accelerating Method*/,埃特金加速收敛方法,设 是根 的某个近似值，用迭代公式迭代一次得,由微分中值定理,其中 介于 与 之间.,假定 改变不大，,（3.1）,若将校正值 再迭代一次，又得,有,34,一般情形,（3.2）,埃特金（Aitken）加速方法,可以证明,它表明序列 的收敛速度比 的收敛速度快.,假定 改变不大，,有,35,Aitken 加速：,P(x0,x1),P(x1,x2),比 收敛得略快。,将 视为新的初值，重复上述步骤,Steffensen 加速：,36,7.3.2 斯蒂芬森迭代法,斯蒂芬森(Steffensen)迭代法,（3.3）,要求 的根,不动点迭代,（3.4）,其中,（3.5）,定理5 若 为 定义的迭代函数 的不动点，则 为 的不动点.反之，若 为 的不动点，设 存在，则 是 的不动点，且斯蒂芬森迭代法是2阶收敛的.,37,迭代,取.,例8 用斯蒂芬森迭代法求解方程,计算结果如下表.,解,是发散的.,用斯蒂芬森迭代法,斯蒂芬森加速可使原本不收敛的迭代改进到收敛.,38,例9 求方程 在 中的解.,由方程得等价形式，取对数得,构造迭代法,且当 时，,由于,根据定理2此迭代法是收敛的.,若 为 阶收敛，则为 阶收敛.,解,39,若取 迭代16次得，有六位有效数字.,若用斯蒂芬森加速，计算结果如下：,这里计算2步结果与 相同，,说明用迭代法（3.3）的收敛速度比迭代法（2.2）快得多.,注意：对本来就是P(1)阶收敛的方法，改用Stefensen迭代方法优点不多。,40,7.4 牛顿法,7.4.1 牛顿法及其收敛性,设已知方程 有近似根（假定)，,将函数 在点 展开，有,于是方程 可近似地表示为,（4.1）,（4.2）,牛顿法,41,几何意义,切线法,收敛性,（4.2）,只要 f C1，每一步迭代都有f(xk)0，而，则 x*就是 f 的根。,迭代函数,假定 是 的一个单根，即，则由上式知,局部平方收敛,（4.3）,42,注：Newtons Method 收敛性依赖于x0 的选取。,x*,6.1.4 牛顿迭代法,43,例10 用牛顿法解方程,（4.4）,解,取迭代初值，迭代结果列于表7-7中.,所给方程（4.4）实际上是方程 的等价形式.,牛顿公式为,若用不动点迭代到同一精度,要迭代17次.,可见牛顿法的收敛速度是很快的.,44,牛顿法的计算步骤：,步骤1 准备 选定初始近似值，计算,步骤3 控制 如果 满足 或，则终止迭代，以 作为所求的根；否则转步骤4.,此处 是允许误差，而,其中 是取绝对误差或相对误差的控制常数，,一般可取,步骤4 修改 如果迭代次数达到预先指定的次数，,或者，则方法失败；,否则以 代替 转步骤2继续迭代.,45,7.4.2 牛顿法应用举例,对于给定的正数，应用牛顿法解二次方程,可导出求开方值 的计算程序,（4.5）,这个迭代公式对于任意初值 都是收敛的.,配方,两式相除,反复递推,（4.6）,46,取初值，对 按(4.5)式迭代3次便得到精度为 的结果（见表7-8).,例11 求.,解,由于公式（4.5）对任意初值 均收敛，并且收敛的速度很快，因此可取确定的初值如 编成通用程序.,47,7.4.3 简化牛顿法与牛顿下山法 牛顿法的改进,每步迭代要计算 及.,牛顿法的变形,(1)简化牛顿法-平行弦法,（4.7）,迭代函数,初始近似 只在根 附近才能保证收敛.,优点,缺点,收敛快,若在根 附近成立，,该迭代法局部收敛.,取,-简化牛顿法,48,用平行弦与 轴交点作为 的近似.,图7-5,o,x,y,y=(x),x,x0,x1,x2,x3,几何意义,(2)牛顿下山法,牛顿法求方程,在 附近的一个根.,设取迭代初值，用牛顿法公式,（4.9）,计算,迭代3次得到的结果 有6位有效数字.,49,这个结果反而比 更偏离了所求的根.,附加要求,（4.10）,满足这项要求的算法称下山法.,保证函数值稳定下降,牛顿法的计算结果,前一步的近似值,（4.11）,其中 称为下山因子，,（4.12）,牛顿下山法,50,从 开始，逐次将 减半进行试算，,直到能使下降条件 成立为止.,下山因子的选取,当 时求得,，,通过 逐次取半进行试算，当 时可求得,此时有，,而,不满足条件,显然.,由 计算 时,均能使下山条件成立.,（4.12）,51,计算结果：,即为 的近似.,下山条件成立，可得到，从而使 收敛.,52,7.4.4 重根情形,设，整数，则 为方程 的 重根，此时有,设,导数,且，,则.,牛顿法的改进,迭代法,（4.13）,局部线性收敛,牛顿法,迭代函数,求 重根，至少有2阶收敛，,知道 的重数,53,令,若 是 的 重根，则,迭代法,（4.14）,至少2阶收敛.,故 是 的单根.,牛顿法,改进求重根迭代法的改进,迭代函数为,54,例12 方程 的根 是二重根，用上述三种方法求根.,解,（1）牛顿法,（2）用（4.13）式,（3）用（4.14）式,取初值，计算结果如表7-9.,（4.13）,（4.14）,55,从结果看出，经过三步计算，方法（2）及（3）均达到10位有效数字，而由于牛顿法只有线性收敛，所以要达到同样精度需迭代30次.,56,7.5 弦截法与抛物线法,计算 较困难,每步迭代要计算 及.,缺点,弦截法,（5.1）,由,有,（5.2）,牛顿公式,中的导数 用差商 取代的结果.,57,几何意义,曲线 上横坐标为 的点分别记为，,则弦线 的斜率等于差商值,其方程为,按（5.2)式求得的 实际上是弦线 与 轴交点的横坐标.,这种算法因此而称为弦截法.,表7-6,58,而弦截法（5.2），在求 时要用到前面两步的结果，,弦截法与切线法的区别,切线法在计算 时只用到前一步的值.,因此使用这种方法必须先给出两个开始值.,例12 用弦截法解方程,设取 作为开始值，用弦截法求得的结果见表7-10，,解,弦截法的收敛速度也是相当快的,59,这里 是方程 的正根.,定理6 假设 在根 的邻域 内具有二阶连续导数，且对任意 有，又初值 那么当邻域充分小时，弦截法（5.2）将按 阶收敛到根.,（5.2）,60,设已知方程 的三个近似根，,几何上，这种方法的基本思想是用抛物线与 轴的交点 作为所求根 的近似位置（图7-7).,图7-7,密勒（Mller）法,7.5.2 抛物线法,插值多项式,61,有两个零点：,（5.3）,式中,问题是该如何确定.,假定在 三个近似根中，更接近所求的根.,为了保证精度，选（5.3）中较接近 的一个值作为新的近似根.,为此，只要取根式前的符号与 的符号相同.,62,例13 用抛物线法求解方程,设用表7-10的前三个值,作为开始值，计算得,解,故,代入（5.3）式求得,63,以上计算表明，抛物线法比弦截法收敛得更快.,在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式,从（5.3）看到，即使 均为实数，也可以是复数，所以抛物线法适用于求多项式的实根和复根.,64,7.6 求根问题的敏感性与多项式的零点,求根问题的敏感性与病态代数方程,多项式的零点,（6.5）,牛顿法求出一个根,利用秦九韶算法计算 及 的值.,牛顿法 计算到，则得到.,再求 的一个根，,如此反复直到求出全部 个根.,65,一般地，这里 为二次多项式，,在此过程中当 增加时不精确性也增加，为了解决此困难可通过原方程 的牛顿法改进 的结果.,若 是复根，使用抛物线法更有利.,若 为复根，记，则 也是一个根，于是 是 的一个二次因子，于是 是 阶多项式，可降低二阶.,66,例 求 的全部零点.,先用抛物线法求方程的根，取 计算到 为止.结果见表7-11.,解,67,求得根为，,再由 可求得另外两根为,可对原方程，以此两根为初值，用牛顿法迭代一次可得到更精确的根,从而可得,68,转化为求矩阵的特征值问题求多项式零点.,利用计算矩阵特征值方法求矩阵 的全部特征值，则可得到方程的全部根，MATLAB中的roots函数使用的就是这种方法.,的特征多项式，,69,作业(1)P238 1,2,3(2)P238 5,8(3)P238 7,9,12,