数值分析课件 第六章非线性方程求根.ppt

《数值分析课件 第六章非线性方程求根.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章非线性方程求根/*SolutionsofNonlinearEquations*/§1Introduction科学技术中常遇到高次代数方程或超越方程的求根问题。大于4次的代数方程无求根公式。因此需要研究函数方程求根问题的数值方法。求f(x)=0的根或零点x*求根问题包括下面三个问题：根的存在性：即f(x)=0有没有根？若有，有几个根？哪儿有根？确定有根区间根的精确化：已知一个根的近似值后，能否将它精确到足够精度？本章假设fC[a,b]，且f(a)·f(b)<0，则f在(a,b)上至少有一根，(a,b)即为有根区间。问题1、2得到解决。1.逐步搜索法§2根的搜索1.逐步搜索法设f

2、(a)<0,f(b)>0，有根区间为(a,b)，从x0=a出发，按某个预定步长(例如h=(b-a)/N)一步一步向右跨，每跨一步进行一次根的搜索，即判别f(xk)=f(a+kh)的符号，若f(xk)>0(而f(xk-1)<0),则有根区间缩小为[xk-1,xk](若f(xk)=0，xk即为所求根),然后从xk-1出发，把搜索步长再缩小，重复上面步骤，直到满足精度：

3、xk-xk-1

4、<为止，此时取x*≈(xk+xk-1)/2作为近似根。①无法求复根及偶重根②计算量大，收敛慢①简单;②对f(x)要求不高(只要连续即可).x0=abxk-1xkx*2.BisectionMethod2.二

5、分法/*BisectionMethod*/(逐步搜索法的改进)设f(x)的有根区间为[a,b]=[a0,b0],f(a)<0,f(b)>0.将[a0,b0],对分，中点x0=((a0+b0)/2),计算f(x0),若f(x0)=0,x*=x0<0,有根区间:[a1,b1]=[x0,b]>0,有根区间:[a1,b1]=[a,x0]对[a1,b1]对分，如此反复进行，得到一系列有根区间：f(ak)0,f(bk)0,f(x*)=limf(ak)=limf(bk)abx1x2x*Whentostop?取xk=(ak+bk)/2([ak,bk]的中点)，显然有limxk=x*.——算法和收敛

6、性说明。或不能保证xk的精度abx1x2x*2xkx*2.BisectionMethod第1步产生的有误差第k步产生的xk有误差对于给定的精度,可估计二分法所需的步数k：①简单，总收敛;②对f(x)要求不高(只要连续即可).①无法求复根及偶重根②收敛慢注：用二分法求根，最好先给出f(x)草图以确定根的大概位置。或用搜索程序，将[a,b]分为若干小区间，对每一个满足f(ak)·f(bk)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a)·f(b)<0。误差分析2.BisectionMethod3.比例法（试位法/*RegulaFalsiMethod*/）一

7、般地，设[ak,bk]为有根区间，过(ak,f(ak))、(bk,f(bk))作直线，与x轴交于一点xk,(a+b)/23.RegulaFalsiMethodabx*(a,f(a))(b,f(b))(x,f(x))x那么用什么来逼近解呢？定理设f(a)f(b)<0,且f(x),f(x)在[a,b]内保号，则按比例求根法确定的序列{xk}必收敛到根x*.3.RegulaFalsiMethod证明：不妨设f(a)<0,f(b)>0,f(x)>0,曲线如下图用比例求根法，一切有根区间的右端点均为b,即ak=xk-1,bk=b,k=1,2,…abxkx*xk+1上式两端取极限，有即{xk

8、}收敛到f(x)=0的根x*.#注:x*b,因为f(xk-1)<0,所以f(x*)0,而f(b)>03.RegulaFalsiMethod注：1.试位法每次迭代比二分法多算一次乘法，而且不保证收敛。2.比例法不是通过使求根区间缩小到0来求根，而是在一定条件下直接构造出一个点列（递推公式），使该点列收敛到方程的根。——这正是迭代法的基本思想。3.RegulaFalsiMethodxk=(ak+bk)/2§3迭代法/*Fixed-PointIteration*/f(x)=0x=g(x)，e.g.,g(x)=f(x)+x等价变换f(x)的根g(x)的不动点思路从一个初值x0出发，计算x1

9、=g(x0),x2=g(x1),…,xk+1=g(xk),…若收敛，即存在x*使得，且g连续，则由可知x*=g(x*)，即x*是g的不动点，也就是f的根。Sobasicallywearedone!Ican’tbelieveit’ssosimple!What’stheproblem?Ohyeah?Whotellsyouthatthemethodisconvergent?可用§1中的方法迭代函数§3.Fixed-PointIterationxyy=