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

《第二章非线性方程的数值解法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二章非线性方程的数值解法PPT讲稿.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章非线性方程的数值解法第1页，共57页，编辑于2022年，星期二求非线性方程根的一些常用方法：求非线性方程根的一些常用方法：区间分割法（逐步搜索法、区间分割法（逐步搜索法、二分法）二分法）迭代法迭代法牛顿法牛顿法割线法割线法第2页，共57页，编辑于2022年，星期二2.1区间分割法区间分割法预备知识：预备知识：方程的根：单根、重根。方程的根：单根、重根。根的存在性定理：根的存在性定理：定理：定理：若若 f 在在a,b上连续，且上连续，且 f(a)f(b)0，则，则 f 在在(a,b)上必有一根；若上必有一根；若 f 在在a,b上上连续且单调连续且单调则则 f 在在(a,b)上上有且仅有有且

2、仅有一根。一根。定理定理 函数函数 f(x)对于对于x*有有f(x*)=0，但，但 则称则称 为方程的单根。如果有为方程的单根。如果有 但但 ，则称，则称 是方程是方程 的的 m重根。重根。第3页，共57页，编辑于2022年，星期二2.1.1逐步搜索法逐步搜索法思路：思路：先把区间先把区间a,b均分均分为为N等分，从初始值等分，从初始值x0=a开始，步长开始，步长h（ba）/N来增值。每跨一步进行一次根的搜索。来增值。每跨一步进行一次根的搜索。计算速度慢，一般用于确定根的位置计算速度慢，一般用于确定根的位置例：例：求连续函数求连续函数 f(x)在有限区间在有限区间a,b上的根。上的根。2.1.

3、2 二分法二分法思路思路：二分法的基本思想二分法的基本思想 就是逐步就是逐步对分对分区间区间,经过对根的搜索，经过对根的搜索，将有根区间的长度缩小到充分小，从而求出满足精度的根将有根区间的长度缩小到充分小，从而求出满足精度的根 的近似的近似值。值。第4页，共57页，编辑于2022年，星期二二分法的步骤：二分法的步骤：在有根区间在有根区间 取中点取中点 ，计算函数值，计算函数值 ，若，若 ，就得到方程的实根，就得到方程的实根 ，否则检查，否则检查 与与 是否同号，如同号，说明待求的根是否同号，如同号，说明待求的根 在在 的右的右侧，这时令侧，这时令 ；如；如 在在 的左侧，这时令的左侧，这时令

4、，这样新的有根区间，这样新的有根区间 的长度为的长度为 之半。之半。二分法二分法abx0 x1a1x*b1第5页，共57页，编辑于2022年，星期二 对压缩了的有根区间对压缩了的有根区间 又可施以同样的手续，又可施以同样的手续，即用中点即用中点 将区间将区间 分为两半，然分为两半，然后判定待求的根后判定待求的根 在在 的哪一侧，从而又确定一的哪一侧，从而又确定一个新的有根区间个新的有根区间 ，其长度为，其长度为 的一的一半。如此反复，即可得出一系列有根区间半。如此反复，即可得出一系列有根区间其中其中 的长度的长度二分法二分法第6页，共57页，编辑于2022年，星期二 每次二等分后，设取有根区间

5、的中点每次二等分后，设取有根区间的中点 作为根的近似值，则在二分过程中可以获得一个近作为根的近似值，则在二分过程中可以获得一个近似根的序列似根的序列 ，该序列以根，该序列以根 为极限。为极限。误差误差 分析分析：若取区间的中点若取区间的中点 作为作为 的近的近似值，则误差估计为：似值，则误差估计为：所以在实际计算时，只要二分足够多次，便有所以在实际计算时，只要二分足够多次，便有 。这里，为预定精度。这里，为预定精度。二分法二分法第7页，共57页，编辑于2022年，星期二优点：优点：简单，简单，对对f(x)要求不高要求不高(只要连续即可只要连续即可).注：注：注：注：用二分法求根，最好先给出用二

6、分法求根，最好先给出 f(x)草图以确定根的大概草图以确定根的大概位置。或用搜索程序，将位置。或用搜索程序，将a,b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f(ak)f(bk)0 的区间调用二分法程序，可找出的区间调用二分法程序，可找出区间区间a,b内的多个根，内的多个根，二分法二分法二分法特点：二分法特点：缺点缺点：收敛慢（：收敛慢（等比级数等比级数）无法求复根及偶重根无法求复根及偶重根 对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k：第8页，共57页，编辑于2022年，星期二求方程求方程f(x)=0f(x)=0的根的二分法算法的根的二分法

7、算法第9页，共57页，编辑于2022年，星期二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 迭代的加速迭代的加速第10页，共57页，编辑于2022年，星期二2.2 简单迭代法简单迭代法f(x)=0 x=(x)等价变换等价变换f(x)的根的根(x)的不动点的不动点思思路路从一个初值从一个初值 x0 出发出发,计算计算 x1=(x0),x2=(x1),xk+1=(xk),若若 收敛，即存在收敛，即存在 x*使得使得 ，只要，只要 连续，则连续，则

8、 ，也，也就是就是 x*=(x*)，即，即x*是是 的根，也就是的根，也就是f 的根。若的根。若 xk发散，则迭代发散，则迭代 法失败。法失败。2.2.1迭代法原理：迭代法原理：第11页，共57页，编辑于2022年，星期二 迭代法迭代法：是一种逐次逼近的方法。它是用某个固定是一种逐次逼近的方法。它是用某个固定公式反复校正根的近似值，使之逐步精确，最后得到满公式反复校正根的近似值，使之逐步精确，最后得到满足精度要求的结果。足精度要求的结果。xk+1=(xk)称为称为迭代格式，迭代格式，(x)称为称为迭代函数迭代函数x x0 0 称为称为迭代初值迭代初值,数列数列 称为称为迭代序列迭代序列 迭代法

9、思想迭代法思想：将隐式方程将隐式方程 的求根问题归的求根问题归结为计算一组显式结为计算一组显式xk+1=(xk)，也就是说，迭代过程是，也就是说，迭代过程是一个逐步显式化的过程。一个逐步显式化的过程。x=(x)第12页，共57页，编辑于2022年，星期二例题例题 例2.2.1 试用迭代法求方程 在区间(1，2)内的实根。解：由 建立迭代关系 k=0,1,2,3.计算结果如下:第13页，共57页，编辑于2022年，星期二例题例题精确到小数点后五位第14页，共57页，编辑于2022年，星期二例题但如果由 建立迭代公式 仍取 ，则有 ，显然结果越来越大，是发散序列第15页，共57页，编辑于2022年

10、，星期二第16页，共57页，编辑于2022年，星期二xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1简单迭代法简单迭代法第17页，共57页，编辑于2022年，星期二收敛定理收敛定理 考虑方程考虑方程 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）任取）任取

11、x0 a,b，由迭代过程，由迭代过程 xk+1=(xk)收敛于收敛于x*简单迭代法简单迭代法推论推论 验后误差估计：验后误差估计：误差估计式：误差估计式：验前误差估计：验前误差估计：第18页，共57页，编辑于2022年，星期二证明：证明：(x)在在a,b上有根？上有根？令令有根有根 根唯一？根唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则在在和和之间。之间。而而 当当k 时，时，xk 收敛到收敛到 x*？3 简单迭代法简单迭代法有根有根L1第19页，共57页，编辑于2022年，星期二 可用可用 来控来控制收敛精度制收敛精度L 越越 收敛越快收敛越快小小注注注注：定理条件非必要条件，对

12、某些问题在区间定理条件非必要条件，对某些问题在区间a,b上上不不满足满足|(x)|L 1，迭代也收敛。，迭代也收敛。实际应用中还是用此定理判断收敛性，当不满足收敛实际应用中还是用此定理判断收敛性，当不满足收敛条件时，改变迭代公式使之满足。条件时，改变迭代公式使之满足。3 简单迭代法简单迭代法第20页，共57页，编辑于2022年，星期二2.2.3 迭代法局部收敛性迭代法局部收敛性 对以上定理中的条件对以上定理中的条件，所有，所有 ，一一般不容易验证。实际使用迭代法时，通常总是在根般不容易验证。实际使用迭代法时，通常总是在根 的邻域进行。的邻域进行。定义定义 如果存在如果存在 的某个邻域的某个邻域

13、 ，是任意指定是任意指定的正数，使迭代过程的正数，使迭代过程 对于任意初值对于任意初值 1 均收敛，则迭代过程均收敛，则迭代过程 在根在根 邻域具有邻域具有局部收敛性局部收敛性。第21页，共57页，编辑于2022年，星期二 证证证证:由于由于由于由于 ，存在存在存在存在 的充分小邻域的充分小邻域的充分小邻域的充分小邻域 ，使使使使 成立，据成立，据成立，据成立，据微分中值定理，有微分中值定理，有微分中值定理，有微分中值定理，有:注意到注意到注意到注意到 ，又当，又当，又当，又当 时时时时 ，故有，故有，故有，故有:由收敛定理的条件由收敛定理的条件由收敛定理的条件由收敛定理的条件可以断定可以断定

14、可以断定可以断定 对于任意对于任意对于任意对于任意 收敛。收敛。收敛。收敛。局部收敛性定理局部收敛性定理：设函数设函数 在在 的根的根 邻近有连续的一阶导邻近有连续的一阶导数，且数，且 ，则迭代过程则迭代过程 具有具有局部收局部收敛性。敛性。第22页，共57页，编辑于2022年，星期二由于在实际应用中根由于在实际应用中根 x*事先不知道，故条件事先不知道，故条件|(x*)|1无法验证。但已知根的初值无法验证。但已知根的初值x0在根在根 x*邻域，又根据邻域，又根据(x)的连的连续性，则可采用续性，则可采用|(x0)|1 来代替来代替|(x*)|1，判断迭代的收敛性。，判断迭代的收敛性。第23页

15、，共57页，编辑于2022年，星期二2.2.42.2.4迭代过程的收敛速度迭代过程的收敛速度迭代过程的收敛速度迭代过程的收敛速度迭代过程的收敛速度，是指在收敛时迭代过程的收敛速度，是指在收敛时迭代过程的收敛速度，是指在收敛时迭代过程的收敛速度，是指在收敛时迭代误差的下降速度迭代误差的下降速度迭代误差的下降速度迭代误差的下降速度。定义定义：设迭代过程设迭代过程 收敛于收敛于 的根的根 ，令迭，令迭代误差代误差 ，若存在常数，若存在常数 和和 ，使，使 ，则称序列则称序列 是是 阶收敛的阶收敛的，称称渐近误差常数渐近误差常数。收敛速度是误差的收缩率，阶数越高，收敛得越收敛速度是误差的收缩率，阶数越

16、高，收敛得越快。特别地，快。特别地，时称时称线性收敛线性收敛，时称时称平方收平方收敛敛或二次收敛，或二次收敛，时称时称超线性收敛超线性收敛。迭代法的收敛速度常用迭代法的收敛速度常用迭代法的收敛速度常用迭代法的收敛速度常用收敛阶收敛阶收敛阶收敛阶表示表示表示表示第24页，共57页，编辑于2022年，星期二 定理定理 对迭代过程对迭代过程 ，若，若 在所求根在所求根 的邻域连续，且的邻域连续，且则迭代过程在则迭代过程在 邻域是邻域是 阶收敛的阶收敛的.证证:p28Q:如何实际确定收敛阶？如何实际确定收敛阶？第25页，共57页，编辑于2022年，星期二例题例：例：证明函数 在区间1，2上满足迭代收敛

17、条件。证明：第26页，共57页，编辑于2022年，星期二例题 第27页，共57页，编辑于2022年，星期二例题若取迭代函数 ，不满足收敛定理，故不能肯定 收敛到方程的根。第28页，共57页，编辑于2022年，星期二2.2.52.2.5迭代过程的加速迭代过程的加速迭代过程的加速迭代过程的加速 对于收敛的迭代过程对于收敛的迭代过程对于收敛的迭代过程对于收敛的迭代过程,只要迭代足够多次只要迭代足够多次只要迭代足够多次只要迭代足够多次,就可以就可以就可以就可以使结果达到任意的精度。但有时迭代过程收敛缓慢使结果达到任意的精度。但有时迭代过程收敛缓慢使结果达到任意的精度。但有时迭代过程收敛缓慢使结果达到任

18、意的精度。但有时迭代过程收敛缓慢,从从从从而使计算量加大而使计算量加大而使计算量加大而使计算量加大.因此迭代过程的加速是个重要的课题因此迭代过程的加速是个重要的课题因此迭代过程的加速是个重要的课题因此迭代过程的加速是个重要的课题.常用迭代加速方法常用迭代加速方法加权法加权法埃特金加速法埃特金加速法斯蒂芬生算法斯蒂芬生算法第29页，共57页，编辑于2022年，星期二 Aitken 加速：加速：简单迭代法简单迭代法xyy=xy=(x)x*x0P(x0,x1)x1x2P(x1,x2)一般地，有：一般地，有：比比 收敛得略快。收敛得略快。Steffensen 加速：加速：第30页，共57页，编辑于20

19、22年，星期二2.3 2.3 牛顿迭代法牛顿迭代法2.3.1 2.3.1 迭代公式的建立迭代公式的建立2.3.2 2.3.2 牛顿迭代法的收敛情况牛顿迭代法的收敛情况2.3.3 2.3.3 牛顿迭代法的修正法牛顿迭代法的修正法第31页，共57页，编辑于2022年，星期二2.3 牛顿法牛顿法原理：原理：将非线性方程线性化将非线性方程线性化 Taylor 展开展开取取 x0 x*，将将 f(x)在在 x0 做一阶做一阶Taylor展开展开:，在在 x0 和和 x*之间。之间。将将(x*x0)2 看成高阶小量，则有：看成高阶小量，则有：线性线性xyx*x0 x1迭代公式迭代公式：迭代函数迭代函数：第

20、32页，共57页，编辑于2022年，星期二牛顿切线法牛顿切线法2.3.2牛顿切线法的收敛情况牛顿切线法的收敛情况 定理定理 （局部收敛性局部收敛性）设函数设函数 在包含在包含 的某邻域的某邻域内有内有 阶连续导数，阶连续导数，是方程是方程 的的单根单根，则当初，则当初值值 充分接近充分接近 时，牛顿切线法收敛，且至少为二阶时，牛顿切线法收敛，且至少为二阶收敛。并有收敛。并有这里这里单根单根意味着：意味着：第33页，共57页，编辑于2022年，星期二牛顿切线法牛顿切线法证明：证明：牛顿法牛顿法 事实上是一种特殊的不动点迭代事实上是一种特殊的不动点迭代 其中其中 ，则，则收敛收敛由由 Taylor

21、 展开：展开：只要只要f(x*)0在在单根单根 附近收敛快附近收敛快 第35页，共57页，编辑于2022年，星期二牛顿切线法牛顿切线法注：注：注：注：牛顿法收敛性依赖于牛顿法收敛性依赖于x0 的选取。的选取。x*x0 x0 x0具有具有局部恒收敛性局部恒收敛性，收敛性依赖于，收敛性依赖于初值初值 的选取。的选取。收敛性好收敛性好（至少平方收敛）（至少平方收敛）每次计算要计算导数，每次计算要计算导数，效率不高效率不高牛顿法特点：牛顿法特点：第36页，共57页，编辑于2022年，星期二例题例题例1:用Newton法求 的近似解。（取8位有效数字）。解：由零点定理。第37页，共57页，编辑于2022

22、年，星期二例题第38页，共57页，编辑于2022年，星期二例题例2:用Newton法计算 。解：第39页，共57页，编辑于2022年，星期二牛牛顿顿迭迭代代法法算算法法框框图图第40页，共57页，编辑于2022年，星期二Newton迭代法算法迭代法算法第41页，共57页，编辑于2022年，星期二牛顿切线法改进牛顿切线法改进牛顿法的改进与推广牛顿法的改进与推广 改进一：改进一：重根时的收敛速度及改进：重根时的收敛速度及改进：Q1:若若 ，牛顿法牛顿法是否仍收敛？是否仍收敛？设设 x*是是 f 的的 n 重根，则：重根，则：且且 。因为因为牛顿法事实上是一种特殊的不动点迭代，牛顿法事实上是一种特殊

23、的不动点迭代，其中其中 ，则，则A1:有局部收敛性，收敛慢（有局部收敛性，收敛慢（线性收敛线性收敛）。）。Q2:如何加速重根的收敛？如何加速重根的收敛？A2:修正修正迭代格式（迭代格式（平方收敛平方收敛）n n证明过程证明过程见书见书p42第42页，共57页，编辑于2022年，星期二 改进二：改进二：牛顿牛顿下山法下山法扩大初值范围的修正牛顿法扩大初值范围的修正牛顿法：原理原理：若由若由 xk 得到的得到的 xk+1 不能使不能使|f|减小，则在减小，则在 xk 和和 xk+1 之间找一个更好的点之间找一个更好的点 ，使得，使得 。xkxk+1通过适当选取的通过适当选取的 保证函数值能单调下降

24、保证函数值能单调下降牛顿切线法改进牛顿切线法改进下山法：下山法：迭代过程中保证函数值单调下降，即迭代过程中保证函数值单调下降，即牛顿下山法：牛顿下山法：将牛顿法与下山法结合使用的算法将牛顿法与下山法结合使用的算法 下山因子下山因子第43页，共57页，编辑于2022年，星期二牛顿牛顿下山法几点讨论下山法几点讨论实用中从实用中从 =1开始反复将开始反复将 减半计算。一旦单调下降则称减半计算。一旦单调下降则称“下山成下山成功功”。反之则称。反之则称“下山失败下山失败”，需另选初值，需另选初值x0计算。计算。牛顿切线法改进牛顿切线法改进当当 1时。牛顿下山法只有线性收敛速度，但对初值的选取却可放时。牛

25、顿下山法只有线性收敛速度，但对初值的选取却可放的很宽。常用牛顿下山法选取初值。的很宽。常用牛顿下山法选取初值。实用中常用牛顿下山法选取初值。为加快收敛速度，转入牛顿法来求解实用中常用牛顿下山法选取初值。为加快收敛速度，转入牛顿法来求解根的精确值。根的精确值。第44页，共57页，编辑于2022年，星期二牛顿法每一步要计算牛顿法每一步要计算 f 和和 f，相当于，相当于2个函数值，且有些导数难求。个函数值，且有些导数难求。为了避开导数的计算，用为了避开导数的计算，用差商差商代替代替导数。导数。x0切线切线 割线割线 切线斜率切线斜率 割线斜率割线斜率2.42.4弦截法弦截法 ：x2x1第45页，共

26、57页，编辑于2022年，星期二用用割线斜率割线斜率（差商）替换（差商）替换切线斜率切线斜率，代入牛顿法迭代公式：，代入牛顿法迭代公式：上式中，固定弦的一个端点（上式中，固定弦的一个端点（x x0 0,f f(x0)），而另一端点变动，称），而另一端点变动，称为为单点弦法。单点弦法。2.4.1 2.4.1 单点弦法单点弦法：第46页，共57页，编辑于2022年，星期二单点弦法几何意义单点弦法几何意义第47页，共57页，编辑于2022年，星期二因为因为f(x*)f(x*)=0=0，故求导数得，故求导数得所以所以0 0 (x*)(x*)1 1，所以，所以单点弦法单点弦法仅为仅为线性收敛线性收敛。单

27、点弦法收敛速度单点弦法收敛速度：迭代函数迭代函数：当初值当初值x x0 0充分接近充分接近 时时很接近很接近f f(x*)(x*)第48页，共57页，编辑于2022年，星期二2.4.2 2.4.2 双点弦法双点弦法：为了加快收敛速度为了加快收敛速度，弦的两个端点都在变动，称为弦的两个端点都在变动，称为双点双点弦法弦法或称或称快速弦截法。快速弦截法。迭代时需要迭代时需要2个初值个初值 xk 和和 xk1。双点弦法迭代公式双点弦法迭代公式：。第49页，共57页，编辑于2022年，星期二双点弦法几何意义双点弦法几何意义P1P2第50页，共57页，编辑于2022年，星期二双点弦法收敛速度双点弦法收敛速

28、度：双点弦截法的收敛性与牛顿迭代法一样，即在根的某个双点弦截法的收敛性与牛顿迭代法一样，即在根的某个邻域内，邻域内，f(x)f(x)有直至二阶的连续导数，且有直至二阶的连续导数，且f f(x(x*)0 0，具，具有局部收敛性，同时在邻域任取初值有局部收敛性，同时在邻域任取初值x0 x0、x1x1，迭代均收敛。，迭代均收敛。可以证明，双点弦截法具有超线性敛速度，收可以证明，双点弦截法具有超线性敛速度，收敛的阶为：敛的阶为：第51页，共57页，编辑于2022年，星期二 例例例例4.4 4.4 用用Newton法和弦截法解下面方程的根，并比较法和弦截法解下面方程的根，并比较 解解解解:由由Newto

29、n法法由弦截法由弦截法第52页，共57页，编辑于2022年，星期二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第53页，共57页，编辑于2022年，星期二2.5 2.5 各种迭代方法的误差特性总结各种迭代方

30、法的误差特性总结方法的误差特性方法的误差特性即方法的收敛速度即方法的收敛速度。二分法：二分法：线性收敛线性收敛牛顿法：牛顿法：单根：单根：平方收敛平方收敛复根：复根：线性收敛线性收敛改进牛顿法：改进牛顿法：线性收敛线性收敛或或平方收敛平方收敛单点弦截法：单点弦截法：双点弦截法：双点弦截法：超线性收敛超线性收敛线性收敛线性收敛简单迭代法：视迭代函数不同而定简单迭代法：视迭代函数不同而定第54页，共57页，编辑于2022年，星期二掌握如何确定方程的有根区间及用区间二分法确定一个掌握如何确定方程的有根区间及用区间二分法确定一个足够好的近似值。足够好的近似值。掌握简单迭代法收敛性定理，能灵活运用简单迭代法求非掌握简单迭代法收敛性定理，能灵活运用简单迭代法求非线性方程的根，并判断迭代序列的收敛性。线性方程的根，并判断迭代序列的收敛性。掌握收敛阶的定义，能确定迭代法的收敛阶，了解迭掌握收敛阶的定义，能确定迭代法的收敛阶，了解迭代法加速原理和算法。代法加速原理和算法。掌握牛顿法、弦截法求根方法的原理。掌握牛顿法、弦截法求根方法的原理。掌握各种迭代法的误差特性。掌握各种迭代法的误差特性。掌握算法框图的编制方法。掌握算法框图的编制方法。本章要求本章要求第56页，共57页，编辑于2022年，星期二习题（习题（p52）3、6、16、17本章作业本章作业第57页，共57页，编辑于2022年，星期二