第二章非线性方程的数值解法优秀PPT.ppt

第二章非线性方程的数值解法第一页，本课件共有57页求非线性方程根的一些常用方法：求非线性方程根的一些常用方法：区间分割法（逐步搜索法、区间分割法（逐步搜索法、二分法）二分法）迭代法迭代法牛顿法牛顿法割线法割线法第二页，本课件共有57页2.1区间分割法区间分割法预备知识：预备知识：方程的根：单根、重根。方程的根：单根、重根。根的存在性定理：根的存在性定理：定理：定理：若若 f 在在a,b上连续，且上连续，且 f(a)f(b)0，则，则 f 在在(a,b)上必有一根；若上必有一根；若 f 在在a,b上上连续且单调连续且单调则则 f 在在(a,b)上上有且仅有有且仅有一根。一根。定理定理 函数函数 f(x)对于对于x*有有f(x*)=0，但，但 则称则称 为方程的单根。如果有为方程的单根。如果有 但但 ，则称，则称 是方程是方程 的的 m重根。重根。第三页，本课件共有57页2.1.1逐步搜索法逐步搜索法思路：思路：先把区间先把区间a,b均分均分为为N等分，从初始值等分，从初始值x0=a开始，步长开始，步长h（ba）/N来增值。每跨一步进行一次根的搜索。来增值。每跨一步进行一次根的搜索。计算速度慢，一般用于确定根的位置计算速度慢，一般用于确定根的位置例：例：求连续函数求连续函数 f(x)在有限区间在有限区间a,b上的根。上的根。2.1.2 二分法二分法思路思路：二分法的基本思想二分法的基本思想 就是逐步就是逐步对分对分区间区间,经过对根的搜索，经过对根的搜索，将有根区间的长度缩小到充分小，从而求出满足精度的根将有根区间的长度缩小到充分小，从而求出满足精度的根 的近的近似值。似值。第四页，本课件共有57页二分法的步骤：二分法的步骤：在有根区间在有根区间 取中点取中点 ，计算函数值，计算函数值 ，若，若 ，就得到方程的实根，就得到方程的实根 ，否则检查，否则检查 与与 是否同号，如同号，说明待求的根是否同号，如同号，说明待求的根 在在 的右的右侧，这时令侧，这时令 ；如；如 在在 的左侧，这时令的左侧，这时令 ，这样新的有根区间，这样新的有根区间 的长度为的长度为 之半。之半。二分法二分法abx0 x1a1x*b1第五页，本课件共有57页 对压缩了的有根区间对压缩了的有根区间 又可施以同样的手续，又可施以同样的手续，即用中点即用中点 将区间将区间 分为两半，然分为两半，然后判定待求的根后判定待求的根 在在 的哪一侧，从而又确定一的哪一侧，从而又确定一个新的有根区间个新的有根区间 ，其长度为，其长度为 的一的一半。如此反复，即可得出一系列有根区间半。如此反复，即可得出一系列有根区间其中其中 的长度的长度二分法二分法第六页，本课件共有57页 每次二等分后，设取有根区间的中点每次二等分后，设取有根区间的中点 作为根的近似值，则在二分过程中可以获得一个近作为根的近似值，则在二分过程中可以获得一个近似根的序列似根的序列 ，该序列以根，该序列以根 为极限。为极限。误差误差 分析分析：若取区间的中点若取区间的中点 作为作为 的近的近似值，则误差估计为：似值，则误差估计为：所以在实际计算时，只要二分足够多次，便有所以在实际计算时，只要二分足够多次，便有 。这里，为预定精度。这里，为预定精度。二分法二分法第七页，本课件共有57页优点：优点：简单，简单，对对f(x)要求不高要求不高(只要连续即可只要连续即可).注：注：注：注：用二分法求根，最好先给出用二分法求根，最好先给出 f(x)草图以确定根的大概草图以确定根的大概位置。或用搜索程序，将位置。或用搜索程序，将a,b分为若干小区间，对每一个分为若干小区间，对每一个满足满足 f(ak)f(bk)0 的区间调用二分法程序，可找出区间的区间调用二分法程序，可找出区间a,b内的多个根，内的多个根，二分法二分法二分法特点：二分法特点：缺点缺点：收敛慢（：收敛慢（等比级数等比级数）无法求复根及偶重根无法求复根及偶重根 对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k：第八页，本课件共有57页求方程求方程f(x)=0f(x)=0的根的二分法算法的根的二分法算法第九页，本课件共有57页2.2 2.2 简单迭代法简单迭代法2.2.1 2.2.1 迭代原理迭代原理2.2.2 2.2.2 迭代的收敛性迭代的收敛性2.2.3 2.2.3 迭代的收敛速度迭代的收敛速度2.2.4 2.2.4 迭代的加速迭代的加速第十页，本课件共有57页2.2 简单迭代法简单迭代法f(x)=0 x=(x)等价变换等价变换f(x)的根的根(x)的不动点的不动点思思路路从一个初值从一个初值 x0 出发出发,计算计算 x1=(x0),x2=(x1),xk+1=(xk),若若 收敛，即存在收敛，即存在 x*使得使得 ，只要，只要 连续，则连续，则 ，也，也就是就是 x*=(x*)，即，即x*是是 的根，也就是的根，也就是f 的根。若的根。若 xk发散，则迭代发散，则迭代 法失败。法失败。2.2.1迭代法原理：迭代法原理：第十一页，本课件共有57页 迭代法迭代法：是一种逐次逼近的方法。它是用某个固定是一种逐次逼近的方法。它是用某个固定公式反复校正根的近似值，使之逐步精确，最后得到公式反复校正根的近似值，使之逐步精确，最后得到满足精度要求的结果。满足精度要求的结果。xk+1=(xk)称为称为迭代格式，迭代格式，(x)称为称为迭代函数迭代函数x x0 0 称为称为迭代初值迭代初值,数列数列 称为称为迭代序列迭代序列 迭代法思想迭代法思想：将隐式方程将隐式方程 的求根问题归的求根问题归结为计算一组显式结为计算一组显式xk+1=(xk)，也就是说，迭代过程是，也就是说，迭代过程是一个逐步显式化的过程。一个逐步显式化的过程。x=(x)第十二页，本课件共有57页例题例题 例2.2.1 试用迭代法求方程 在区间(1，2)内的实根。解：由 建立迭代关系 k=0,1,2,3.计算结果如下:第十三页，本课件共有57页例题例题精确到小数点后五位第十四页，本课件共有57页例题但如果由 建立迭代公式 仍取 ，则有 ，显然结果越来越大，是发散序列第十五页，本课件共有57页第十六页，本课件共有57页xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1简单迭代法简单迭代法第十七页，本课件共有57页收敛定理收敛定理 考虑方程考虑方程 x=(x),(x)在在a,b上连续上连续,若若(I)对所有对所有 x a,b，有，有 (x)a,b；(II)存在存在 0 L 1，使所有使所有 x a,b 有有|(x)|L 1。则：则：1）方程）方程x=(x)在在a,b上的解上的解x*存在且唯一。存在且唯一。2）任取）任取 x0 a,b，由迭代过程，由迭代过程 xk+1=(xk)收敛于收敛于x*简单迭代法简单迭代法推论推论 验后误差估计：验后误差估计：误差估计式：误差估计式：验前误差估计：验前误差估计：第十八页，本课件共有57页证明：证明：(x)在在a,b上有根？上有根？令令有根有根 根唯一？根唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则在在和和之间。之间。而而 当当k 时，时，xk 收敛到收敛到 x*？3 简单迭代法简单迭代法有根有根L1第十九页，本课件共有57页 可用可用 来控制来控制收敛精度收敛精度L 越越 收敛越快收敛越快小小注注注注：定理条件非必要条件，对某些问题在区间定理条件非必要条件，对某些问题在区间a,b上上不满不满足足|(x)|L 1，迭代也收敛。，迭代也收敛。实际应用中还是用此定理判断收敛性，当不满足收敛实际应用中还是用此定理判断收敛性，当不满足收敛条件时，改变迭代公式使之满足。条件时，改变迭代公式使之满足。3 简单迭代法简单迭代法第二十页，本课件共有57页2.2.3 迭代法局部收敛性迭代法局部收敛性 对以上定理中的条件对以上定理中的条件，所有，所有 ，一一般不容易验证。实际使用迭代法时，通常总是在根般不容易验证。实际使用迭代法时，通常总是在根 的邻域进行。的邻域进行。定义定义 如果存在如果存在 的某个邻域的某个邻域 ，是任意指是任意指定的正数，使迭代过程定的正数，使迭代过程 对于任意初值对于任意初值 1 均收敛，则迭代过程均收敛，则迭代过程 在根在根 邻域具有邻域具有局部收敛性局部收敛性。第二十一页，本课件共有57页 证证证证:由于由于由于由于 ，存在存在存在存在 的充分小邻域的充分小邻域的充分小邻域的充分小邻域 ，使使使使 成立，据成立，据成立，据成立，据微分中值定理，有微分中值定理，有微分中值定理，有微分中值定理，有:注意到注意到注意到注意到 ，又当，又当，又当，又当 时时时时 ，故有，故有，故有，故有:由收敛定理的条件由收敛定理的条件由收敛定理的条件由收敛定理的条件可以断定可以断定可以断定可以断定 对于任意对于任意对于任意对于任意 收敛。收敛。收敛。收敛。局部收敛性定理局部收敛性定理：设函数设函数 在在 的根的根 邻近有连续的一阶导邻近有连续的一阶导数，且数，且 ，则迭代过程则迭代过程 具有具有局部收局部收敛性。敛性。第二十二页，本课件共有57页由于在实际应用中根由于在实际应用中根 x*事先不知道，故条件事先不知道，故条件|(x*)|1无法验证。但已知根的初值无法验证。但已知根的初值x0在根在根 x*邻域，又根据邻域，又根据(x)的连的连续性，则可采用续性，则可采用|(x0)|1 来代替来代替|(x*)|1，判断迭代的收敛性。，判断迭代的收敛性。第二十三页，本课件共有57页2.2.42.2.4迭代过程的收敛速度迭代过程的收敛速度迭代过程的收敛速度迭代过程的收敛速度迭代过程的收敛速度，是指在收敛时迭代过程的收敛速度，是指在收敛时迭代过程的收敛速度，是指在收敛时迭代过程的收敛速度，是指在收敛时迭代误差的下降速度迭代误差的下降速度迭代误差的下降速度迭代误差的下降速度。定义定义：设迭代过程设迭代过程 收敛于收敛于 的根的根 ，令迭，令迭代误差代误差 ，若存在常数，若存在常数 和和 ，使，使 ，则称序列则称序列 是是 阶收敛的阶收敛的，称称渐近误差常数渐近误差常数。收敛速度是误差的收缩率，阶数越高，收敛得越收敛速度是误差的收缩率，阶数越高，收敛得越快。特别地，快。特别地，时称时称线性收敛线性收敛，时称时称平方收平方收敛敛或二次收敛，或二次收敛，时称时称超线性收敛超线性收敛。迭代法的收敛速度常用迭代法的收敛速度常用迭代法的收敛速度常用迭代法的收敛速度常用收敛阶收敛阶表示表示表示表示第二十四页，本课件共有57页 定理定理 对迭代过程对迭代过程 ，若，若 在所求根在所求根 的邻域连续，且的邻域连续，且则迭代过程在则迭代过程在 邻域是邻域是 阶收敛的阶收敛的.证证:p28Q:如何实际确定收敛阶？如何实际确定收敛阶？第二十五页，本课件共有57页例题例：例：证明函数 在区间1，2上满足迭代收敛条件。证明：第二十六页，本课件共有57页例题 第二十七页，本课件共有57页例题若取迭代函数 ，不满足收敛定理，故不能肯定 收敛到方程的根。第二十八页，本课件共有57页2.2.5迭代过程的加速迭代过程的加速 对于收敛的迭代过程对于收敛的迭代过程,只要迭代足够多次只要迭代足够多次,就可以就可以使结果达到任意的精度。但有时迭代过程收敛缓慢使结果达到任意的精度。但有时迭代过程收敛缓慢,从从而使计算量加大而使计算量加大.因此迭代过程的加速是个重要的课题因此迭代过程的加速是个重要的课题.常用迭代加速方法常用迭代加速方法加权法加权法埃特金加速法埃特金加速法斯蒂芬生算法斯蒂芬生算法第二十九页，本课件共有57页 Aitken 加速：加速：简单迭代法简单迭代法xyy=xy=(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：一般地，有：比比 收敛得略快。收敛得略快。Steffensen 加速：加速：第三十页，本课件共有57页2.3 2.3 牛顿迭代法牛顿迭代法2.3.1 2.3.1 迭代公式的建立迭代公式的建立2.3.2 2.3.2 牛顿迭代法的收敛情况牛顿迭代法的收敛情况2.3.3 2.3.3 牛顿迭代法的修正法牛顿迭代法的修正法第三十一页，本课件共有57页2.3 牛顿法牛顿法原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:，在在 x0 和和 x*之间。之间。将将(x*x0)2 看成高阶小量，则有：看成高阶小量，则有：线性线性xyx*x0 x1迭代公式迭代公式：迭代函数迭代函数：第三十二页，本课件共有57页牛顿切线法牛顿切线法2.3.2牛顿切线法的收敛情况牛顿切线法的收敛情况 定理定理 （局部收敛性局部收敛性）设函数设函数 在包含在包含 的某邻域的某邻域内有内有 阶连续导数，阶连续导数，是方程是方程 的的单根单根，则当初，则当初值值 充分接近充分接近 时，牛顿切线法收敛，且至少为二阶时，牛顿切线法收敛，且至少为二阶收敛。并有收敛。并有这里这里单根单根意味着：意味着：第三十三页，本课件共有57页牛顿切线法牛顿切线法证明：证明：牛顿法牛顿法 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代 其中其中 ，则，则收敛收敛由由 Taylor 展开：展开：只要只要f(x*)0在在单根单根 附近收敛快附近收敛快 第三十五页，本课件共有57页牛顿切线法牛顿切线法注：注：注：注：牛顿法收敛性依赖于牛顿法收敛性依赖于x0 的选取。的选取。x*x0 x0 x0具有具有局部恒收敛性局部恒收敛性，收敛性依赖于，收敛性依赖于初值初值 的选取。的选取。收敛性好收敛性好（至少平方收敛）（至少平方收敛）每次计算要计算导数，每次计算要计算导数，效率不高效率不高牛顿法特点：牛顿法特点：第三十六页，本课件共有57页例题例题例1:用Newton法求 的近似解。（取8位有效数字）。解：由零点定理。第三十七页，本课件共有57页例题第三十八页，本课件共有57页例题例2:用Newton法计算 。解：第三十九页，本课件共有57页牛牛顿顿迭迭代代法法算算法法框框图图第四十页，本课件共有57页Newton迭代法算法迭代法算法第四十一页，本课件共有57页牛顿切线法改进牛顿切线法改进牛顿法的改进与推广牛顿法的改进与推广 改进一：改进一：重根时的收敛速度及改进：重根时的收敛速度及改进：Q1:若若 ，牛顿法牛顿法是否仍收敛？是否仍收敛？设设 x*是是 f 的的 n 重根，则：重根，则：且且 。因为因为牛顿法事实上是一种特殊的不动点迭代，牛顿法事实上是一种特殊的不动点迭代，其中其中 ，则，则A1:有局部收敛性，收敛慢（有局部收敛性，收敛慢（线性收敛线性收敛）。）。Q2:如何加速重根的收敛？如何加速重根的收敛？A2:修正修正迭代格式（迭代格式（平方收敛平方收敛）n n证明过程证明过程见书见书p42第四十二页，本课件共有57页 改进二：改进二：牛顿牛顿下山法下山法扩大初值范围的修正牛顿法扩大初值范围的修正牛顿法：原理原理：若由若由 xk 得到的得到的 xk+1 不能使不能使|f|减小，则在减小，则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使得，使得 。xkxk+1通过适当选取的通过适当选取的 保证函数值能单调下降保证函数值能单调下降牛顿切线法改进牛顿切线法改进下山法：下山法：迭代过程中保证函数值单调下降，即迭代过程中保证函数值单调下降，即牛顿下山法：牛顿下山法：将牛顿法与下山法结合使用的算法将牛顿法与下山法结合使用的算法 下山因子下山因子第四十三页，本课件共有57页牛顿牛顿下山法几点讨论下山法几点讨论实用中从实用中从 =1开始反复将开始反复将 减半计算。一旦单调下降则称减半计算。一旦单调下降则称“下山下山成功成功”。反之则称。反之则称“下山失败下山失败”，需另选初值，需另选初值x0计算。计算。牛顿切线法改进牛顿切线法改进当当 1时。牛顿下山法只有线性收敛速度，但对初值的选取却时。牛顿下山法只有线性收敛速度，但对初值的选取却可放的很宽。常用牛顿下山法选取初值。可放的很宽。常用牛顿下山法选取初值。实用中常用牛顿下山法选取初值。为加快收敛速度，转入牛顿法实用中常用牛顿下山法选取初值。为加快收敛速度，转入牛顿法来求解根的精确值。来求解根的精确值。第四十四页，本课件共有57页牛顿法每一步要计算牛顿法每一步要计算 f 和和 f，相当于，相当于2个函数值，且有些导个函数值，且有些导数难求。为了避开导数的计算，用数难求。为了避开导数的计算，用差商差商代替代替导数。导数。x0切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率2.42.4弦截法弦截法 ：x2x1第四十五页，本课件共有57页用用割线斜率割线斜率（差商）替换（差商）替换切线斜率切线斜率，代入牛顿法迭代公式：，代入牛顿法迭代公式：上式中，固定弦的一个端点（上式中，固定弦的一个端点（x x0 0,f f(x0)），而另一端点变动，称），而另一端点变动，称为为单点弦法。单点弦法。2.4.1 2.4.1 单点弦法单点弦法：第四十六页，本课件共有57页单点弦法几何意义单点弦法几何意义第四十七页，本课件共有57页因为因为f(x*)f(x*)=0=0，故求导数得，故求导数得所以所以0 0 (x*)(x*)1 1，所以，所以单点弦法单点弦法仅为仅为线性收敛线性收敛。单点弦法收敛速度单点弦法收敛速度：迭代函数迭代函数：当初值当初值x x0 0充分接近充分接近 时时很接近很接近f f(x*)(x*)第四十八页，本课件共有57页2.4.2 2.4.2 双点弦法双点弦法：为了加快收敛速度为了加快收敛速度，弦的两个端点都在变动，称为弦的两个端点都在变动，称为双点双点弦法弦法或称或称快速弦截法。快速弦截法。迭代时需要迭代时需要2个初值个初值 xk 和和 xk1。双点弦法迭代公式双点弦法迭代公式：。第四十九页，本课件共有57页双点弦法几何意义双点弦法几何意义P1P2第五十页，本课件共有57页双点弦法收敛速度双点弦法收敛速度：双点弦截法的收敛性与牛顿迭代法一样，即在根的某双点弦截法的收敛性与牛顿迭代法一样，即在根的某个邻域内，个邻域内，f(x)f(x)有直至二阶的连续导数，且有直至二阶的连续导数，且f f(x(x*)0 0，具有局部收敛性，同时在邻域任取初值，具有局部收敛性，同时在邻域任取初值x0 x0、x1x1，迭，迭代均收敛。代均收敛。可以证明，双点弦截法具有超线性敛速度，可以证明，双点弦截法具有超线性敛速度，收敛的阶为：收敛的阶为：第五十一页，本课件共有57页 例例例例4.4 4.4 用用Newton法和弦截法解下面方程的根，并比较法和弦截法解下面方程的根，并比较 解解解解:由由Newton法法由弦截法由弦截法第五十二页，本课件共有57页x0=0.5;x1=0.4;x2=0.3430962343x3=0.3473897274x4=0.3472965093x5=0.3472963553x6=0.3472963553Newton法法由弦截法由弦截法要达到精度要达到精度10-8 弦截法迭代弦截法迭代5次次Newton迭代法迭代迭代法迭代4次次x0=0.5;x1=0.3333333333x2=0.3472222222x3=0.3472963532x4=0.3472963553第五十三页，本课件共有57页2.5 2.5 各种迭代方法的误差特性总结各种迭代方法的误差特性总结方法的误差特性方法的误差特性即方法的收敛速度即方法的收敛速度。二分法：二分法：线性收敛线性收敛牛顿法：牛顿法：单根：单根：平方收敛平方收敛复根：复根：线性收敛线性收敛改进牛顿法：改进牛顿法：线性收敛线性收敛或或平方收敛平方收敛单点弦截法：单点弦截法：双点弦截法：双点弦截法：超线性收敛超线性收敛线性收敛线性收敛简单迭代法：视迭代函数不同而定简单迭代法：视迭代函数不同而定第五十四页，本课件共有57页掌握如何确定方程的有根区间及用区间二分法确定掌握如何确定方程的有根区间及用区间二分法确定一个足够好的近似值。一个足够好的近似值。掌握简单迭代法收敛性定理，能灵活运用简单迭代掌握简单迭代法收敛性定理，能灵活运用简单迭代法求非线性方程的根，并判断迭代序列的收敛性。法求非线性方程的根，并判断迭代序列的收敛性。掌握收敛阶的定义，能确定迭代法的收敛阶，了解迭掌握收敛阶的定义，能确定迭代法的收敛阶，了解迭代法加速原理和算法。代法加速原理和算法。掌握牛顿法、弦截法求根方法的原理。掌握牛顿法、弦截法求根方法的原理。掌握各种迭代法的误差特性。掌握各种迭代法的误差特性。掌握算法框图的编制方法。掌握算法框图的编制方法。本章要求本章要求第五十六页，本课件共有57页习题（习题（p52）3、6、16、17本章作业本章作业第五十七页，本课件共有57页