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