计算方法非线性方程的数值解法精选文档.ppt

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

1、计算方法非线性方程的数值解法本讲稿第一页，共六十三页第第2 2 章章 非线性方程的数值解法非线性方程的数值解法 2.1 2.1 初始近似值的搜索初始近似值的搜索 2.2 2.2 迭代法迭代法 2.3 2.3 牛顿迭代法（切线法）牛顿迭代法（切线法）2.4 2.4 弦截法（割线法）弦截法（割线法）本讲稿第二页，共六十三页2.1 2.1 初始近似值的搜索初始近似值的搜索2.1.12.1.1方程的根本讲稿第三页，共六十三页单根和重根本讲稿第四页，共六十三页本讲稿第五页，共六十三页本讲稿第六页，共六十三页有根区间 本讲稿第七页，共六十三页假设假设f(x)f(x)在区间在区间 a,ba,b 内有一个实内

2、有一个实根根x x*,若若 b ab a较小，则可在较小，则可在(a,b)(a,b)上任上任取一点取一点x x0 0作为作为初始近似根。初始近似根。一般情形，可用逐步搜索法。一般情形，可用逐步搜索法。2.1.2 逐步搜索法逐步搜索法本讲稿第八页，共六十三页本讲稿第九页，共六十三页例 对方程 搜索有根区间。解解 由于由于f(x)是连续函数，是连续函数，f(0)=-10，故方程，故方程至少有一正实根。设从至少有一正实根。设从x=0 出发，取出发，取h=0.5为步长，逐步为步长，逐步右跨搜索，得右跨搜索，得x00.51.01.5f(x)+所以所以f(x)在区间（在区间（1,1.5）上单调连续，因而在

3、）上单调连续，因而在(1,1.5)内有且内有且仅有一个实根，故可取仅有一个实根，故可取1,1.5上任一点做初始近似根。上任一点做初始近似根。可见在（可见在（1，1.5）内有根。又）内有根。又本讲稿第十页，共六十三页本讲稿第十一页，共六十三页 2.1.3 2.1.3 区间二分法区间二分法 定理定理 函数函数f f(x x)在在 a,ba,b 上单调连续，且上单调连续，且f(a)f(b)f(a)f(b)00，则方程，则方程f(x)=0f(x)=0在区间在区间 a,ba,b 上有且上有且仅有一个实根仅有一个实根x x*。二分法的基本思想二分法的基本思想 将有根的区间二分为两个小区间，然后将有根的区间

4、二分为两个小区间，然后判断根在那个小区间，舍去无根的小区间，而判断根在那个小区间，舍去无根的小区间，而把有根的小区间再一分为二，再判断根属于哪把有根的小区间再一分为二，再判断根属于哪个更小的区间，如此反复个更小的区间，如此反复 ，直到求出满足精度，直到求出满足精度要求的近似根。要求的近似根。本讲稿第十二页，共六十三页令令近似根近似根xk的误差估计的误差估计中点中点这时有三种情况：这时有三种情况：f(x0)=0,x0为所求的根为所求的根.f(x0)和和a0同号，取同号，取x0=a1f(x0)和和b0同号，取同号，取x0=b1x*x*新的有根区间为新的有根区间为(a1,b1)，长度是原来的一半。，

5、长度是原来的一半。本讲稿第十三页，共六十三页如此反复，有如此反复，有(ak,bk),k=0,1,2,.近似根近似根xk的误差估计的误差估计本讲稿第十四页，共六十三页第第2次二分，取中点次二分，取中点若若f(a1)f(x1)0，则，则x*(a1,x1)，令令a2=a1,b2=x1；否则否则令令a2=x1,b2=b1。新的有根区间为新的有根区间为(a2,b2)。本讲稿第十五页，共六十三页由此得由此得二分过程结束的原则：二分过程结束的原则：先给定精度要求先给定精度要求(绝对误差限绝对误差限)，（2）当当|bk+1ak+1|时结束二分计算，取时结束二分计算，取x*xk；（1）事先由）事先由估计出二分的

6、最小次数估计出二分的最小次数k，取取x*xk本讲稿第十六页，共六十三页本讲稿第十七页，共六十三页本讲稿第十八页，共六十三页本讲稿第十九页，共六十三页本讲稿第二十页，共六十三页本讲稿第二十一页，共六十三页本讲稿第二十二页，共六十三页本讲稿第二十三页，共六十三页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 迭代的加速迭代的加速本讲稿第二十四页，共六十三页预备定理本讲稿第二十五页，共六十三页2.2.1 迭代原理迭代原理本讲稿第二十六页，共六十三页计算结果见

7、下表计算结果见下表本讲稿第二十七页，共六十三页方程方程f(x)=0化为等价形式的方程化为等价形式的方程 x=(x)，构造迭代公式构造迭代公式 xk+1=(xk),k=0,1,2,取初始近似根取初始近似根x0,进行迭代计算进行迭代计算 x1=(x0),x2=(x1),.则有则有x1,x2,.,xk,.,得到迭代序列得到迭代序列xk.如果这个序列有如果这个序列有极限，则迭代公式是收敛的。这时极限，则迭代公式是收敛的。这时 则则 ，x*为不动点，等价地有为不动点，等价地有 f(x*)=0,x*即为方程的即为方程的根。连续函数根。连续函数(x)称为迭代函数。称为迭代函数。实际计算到实际计算到|xkxk

8、-1|（是预定的精度），取是预定的精度），取x*xk。本讲稿第二十八页，共六十三页迭代公式收敛迭代公式收敛指迭代序列指迭代序列xk 收敛，收敛，迭代公式发散迭代公式发散指迭代序列指迭代序列xk不收敛，即发散。迭代公式不一定总是收敛。不收敛，即发散。迭代公式不一定总是收敛。例如求方程例如求方程f(x)=x3-x-1=0的一个根的一个根。对应的迭代公式为对应的迭代公式为取初值取初值迭代序列迭代序列xk发散发散.本讲稿第二十九页，共六十三页本讲稿第三十页，共六十三页x1=(x0)x2=(x1)迭代法收敛与发散的图示迭代法收敛与发散的图示本讲稿第三十一页，共六十三页迭代法的收敛与发散 收敛的情形 发散

9、的情形本讲稿第三十二页，共六十三页2.2.2 迭代的收敛性迭代的收敛性 迭代法的收敛条件及误差估计式迭代法的收敛条件及误差估计式定理（充分性条件）定理（充分性条件）设函数设函数(x)在在a,b上连续，且上连续，且 (1)对对 xa,b,有有(x)a,b (2)存在存在0L1，使对任意，使对任意 xa,b有有|(x)|L1则方程则方程x=(x)在在 a,b上的根上的根x*存在且唯一；对初值存在且唯一；对初值 x0 a,b,迭代过程迭代过程 xk+1=(xk)均收敛于方程的根均收敛于方程的根x*。定理中的定理中的(1)对对xa,b,有有(x)a,b，称为适定性（映内性）。，称为适定性（映内性）。本

10、讲稿第三十三页，共六十三页证明证明 先证根的存在性。先证根的存在性。作连续函数作连续函数(x)=x-(x),由条件（由条件（1）xa,b,(x)a,b，即，即a(x)、xb,于是于是(a)=a-(a)0(b)=b-(b)0由于由于(x)是连续函数，故必存在是连续函数，故必存在x*a,b使使(x*)=0.即即(x*)=x*-(x*)=0.于是于是x*=(x*)即即x*为方程为方程x=(x)的根。的根。其次，证根的唯一性其次，证根的唯一性。设设y*也是方程的根，则也是方程的根，则x*=(x*),y*=(y*),x*-y*=(x*)(y*)=()(x*-y*)x*-y*()(x*-y*)=0，（x*

11、-y*）1-()=0由条件（由条件（2）|(x)|L1，故有故有x*-y*=0，即即x*=y*所以方程在所以方程在a,b的根唯一的根唯一。本讲稿第三十四页，共六十三页再证迭代的收敛性再证迭代的收敛性。由由xk=(xk-1),x*=(x*),有有|xk-x*|=|()(xk-1-x*)|L|xk-1-x*|L2|xk-2-x*|L3|xk-3-x*|Lk|x0-x*|0（k）所以，对所以，对a,b上任取的上任取的x0,迭代公式迭代公式xk+1=(xk)都收敛于都收敛于x*。L越小收敛得越快。越小收敛得越快。定理是充分性条件定理是充分性条件xk-x*=(xk-1)(x*)=()(xk-1-x*)本

12、讲稿第三十五页，共六十三页推论：在定理的条件下，有误差估计式推论：在定理的条件下，有误差估计式 验后误差估计式验后误差估计式 验前误差估计式验前误差估计式证明：证明：|xk-x*|L|xk-1-x*|=L|xk-1-xk+xk-x*|L（|xk-x*|+|xk-1-xk|）（1-L)|xk-x*|L|xk-1-xk|迭代法的终点判断：只要相邻两次迭代值的偏差充迭代法的终点判断：只要相邻两次迭代值的偏差充分小，就能保证迭代值足够准确，因而用分小，就能保证迭代值足够准确，因而用|xk-xk-1|控制迭代过程的结束。控制迭代过程的结束。本讲稿第三十六页，共六十三页 定理定理 设在区间设在区间a,b上

13、方程上方程 x=(x)有根有根x*,且对一切且对一切xa,b 都有都有|(x)|1，则对于该区间上任意，则对于该区间上任意x0(x*),迭代公式迭代公式xk+1=(xk)一定发散。一定发散。证明证明不可能收敛于不可能收敛于0。本讲稿第三十七页，共六十三页本讲稿第三十八页，共六十三页本讲稿第三十九页，共六十三页计算结果见下表计算结果见下表取方程的根取方程的根 2.0946。本讲稿第四十页，共六十三页本讲稿第四十一页，共六十三页由于 ，故取 本讲稿第四十二页，共六十三页迭代法的迭代法的局部收敛性局部收敛性本讲稿第四十三页，共六十三页由于在实际应用中根由于在实际应用中根x*事先不知道，故条件事先不知

14、道，故条件|(x*)|1无法验证。但已知根的初值无法验证。但已知根的初值x0在根在根x*邻域，又根据邻域，又根据(x)的连续的连续性，则可采用性，则可采用|(x0)|1来代替来代替|(x*)|1，判断迭代的收敛性。，判断迭代的收敛性。本讲稿第四十四页，共六十三页例例求方程求方程x=ex在在x=0.5附近的一个根，按附近的一个根，按5位小数计算，位小数计算，结果的精度要求为结果的精度要求为=103.解解迭代公式迭代公式xk+1=exk，取取(x)=ex,迭代公式迭代公式xk+1=exk收敛。收敛。本讲稿第四十五页，共六十三页迭代结果迭代结果:0123450.50.606530.545240.57

15、9700.560070.571170.106530.061290.034460.019630.011106789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065kxkxkxk-1xkxk-1kxk|x10-x9|=0.00065，故故x*x100.567x0=0.5,x2=ex1=0.54524,.x1=e x0=0.60653,xk+1=exk本讲稿第四十六页，共六十三页本讲稿第四十七页，共六十三页迭代的计算步骤 本讲稿第四十八页，共六十三页迭代法计算框图的说明本讲稿第四十九页，共六十三页本讲稿第五十页，共六十三页本讲稿第五十一页，共六十三页2.2.3 迭代过程的收敛速度本讲稿第五十二页，共六十三页本讲稿第五十三页，共六十三页本讲稿第五十四页，共六十三页本讲稿第五十五页，共六十三页本讲稿第五十六页，共六十三页本讲稿第五十七页，共六十三页2.2.4 迭代的加速本讲稿第五十八页，共六十三页2 埃特金加速与斯蒂芬森迭代法本讲稿第五十九页，共六十三页埃特金迭代埃特金迭代将不动点迭代法与埃特金加速结合即得斯蒂芬森迭代法将不动点迭代法与埃特金加速结合即得斯蒂芬森迭代法本讲稿第六十页，共六十三页本讲稿第六十一页，共六十三页本讲稿第六十二页，共六十三页本讲稿第六十三页，共六十三页