计算方法7173

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第七章 非线性方程的解法,数值计算方法,1,2024/11/12,2024/11/12,2,7.1,隔根区间的确定,第七章 非线性方程的解法,7.3,迭代,法,7.2,对分法,7.5,迭代法的收敛速度,7.4,牛顿,(Newton),迭代法,7.6,弦截法,2,7.7,非线性方程组的解法,在科学研究和工程设计中,经常会遇到的一大类问题是非线性方程,-(1),2024/11/12,3,当,f(x),不是,x,的线性函数时，称对应的函数方程为非线性方程。如果,f(x),是多项式函数，则称为代数方程，否则称为超越方程（三角方程，指数、对数方程等）。一般称,n,次多项式构成的方程,为,n,次代数方程,当,n1,时,方程显然是非线性的,一般稍微复杂的3次以上的代数方程或超越方程,很难甚至无法求得精确解。本章将介绍常用的求解非线性方程的近似根的几种数值解法,2024/11/12,4,通常方程根的数值解法大致分为三个步骤进行：,判定根的存在性。即方程有没有根？如果有根，有几个根？,确定根的分布范围。即将每一个根用区间隔离开来，这个过程实际上是获得方程各根的初始近似值。,根的精确化。将根的初始近似值按某种方法逐步精确化，直到满足预先要求的精度为止。,2024/11/12,5,本章介绍方程的迭代解法，它既可以用来求解代数方程，也可以用来解超越方程，并且仅限于求方程的实根。,运用迭代法求解方程的根应解决以下两个问题：,确定根的初值;,将进一步精确化到所需要的精度。,2024/11/12,6,为了确定根的初值，首先必须圈定根所在的范围，,称为,圈定根或根的隔离,。,在上述基础上，采取适当的数值方法确定具有一定,精度要求的初值。,对于代数方程，其根的个数（实或复的）与其次数,相同。至于超越方程，其根可能是一个、几个或无,解，并没有什么固定的圈根方法,求方程根的问题，就几何上讲,是求曲线,y=f(x),与,x,轴交点的横坐标。,7.1,隔根区间的确定,2024/11/12,7,由高等数学知识知,设,f(x),为区间,a,b,上的单值连续,如果,f(a)f(b)0,则,a,b,中至少有一个实根。如果,f(x),在,a,b,上还是单调地递增或递减，则仅有一个实根。,由此可大体确定根所在子区间，方法有：,(1)画图法,(2)逐步搜索法,y=f(x),a,b,y,x,2024/11/12,8,(1)画图法,画出,y=f(x),的略图，从而看出曲线与,x,轴交点的大致位置。,也可将,f(x)=0,分解为,1,(,x)=,2,(x),的形式，,1,(,x),与,2,(,x),两曲线交点的横坐标所在的子区间即为含根区间。,例如,x,lg,x,-1=0,可以改写为,lg,x=1/x,画出对数曲线,y=,lg,x,与双曲线,y=1/x,它们交点的横坐标位于区间2,3内,2,3,0,y,x,2024/11/12,9,对于某些看不清根的函数，可以扩大一下曲线,y,0,x,y=f(x),y=kf(x),2024/11/12,10,y,0,x,A,B,a,1,b,1,a,2,b,2,(2)搜索法,对于给定的,f(x),设有根区间为,A,B,从,x,0,=A,出发,以步长,h=(B-A)/n,(,n,是正整数),在,A,B,内取定节点:,x,i,=x,0,ih,(,i=0,1,2,n,),从左至右检查,f(x,i,),的符号,如发现,x,i,与端点,x,0,的函数值异号,则得到一个缩小的有根子区间,x,i-1,x,i,。,2024/11/12,11,运用零点定理可以得到如下逐步搜索法：,先确定方程,f,(,x,)=0,的所有实根所在的区间为,a,b,从,x,0,=,a,出发,以步长,h=,(,b-a,),/,n,其中,n,是正整数，在,a,b,内取定节点：,x,i,=,x,0,ih,(,i,=0,1,2,，,，,n,),计算,f,(,x,i,),的值,依据函数值异号及实根的个数确定隔根区间,通过调整步长，总可找到所有隔根区间。,2024/11/12,12,例,求方程,x,3,-3.2,x,2,+1.9,x,+0.8=0,的隔根区间。,解：设方程的根为,，,=,max,1,，,|,-3.2,|,，,|,1.9,|,=,max,|,-3.2,|,|,1.9,|,|,0.8,|=,3.2,故,即有根区间为,(,-4.2,-0.2,),和,(,0.2,4.2,),对于,m,次代数方程,f,(,x,)=,x,m,+,a,m-,1,x,m-,1,+,+,a,1,x,+,a,0,=0,其根的模的上下界有如下结论：,(1),若,=,max,|,a,m-,1,|,|,a,1,|,|,a,0,|,，,则方程根的模小于,+1,(2),若,=,max,1,，,|,a,m-,1,|,|,a,1,|,则方程根的模大于,2024/11/12,13,例1 方程,f(x)=x,3,-x-1=0,确定其有根区间,解：用试凑的方法，不难发现,f(0)0,在区间（0，2）内至少有一个实根,设从,x=0,出发,取,h=0.5,为步长向右进行根的,搜索,列表如下,x,f(x),0 0.5 1.0 1.5 2,+,可以看出，在1.0,1.5,内必有一根,2024/11/12,14,用逐步搜索法进行实根隔离的关键是选取步长,h,要选择适当,h,，使之既能把根隔离开来，工作量,又不太大。,为获取指定精度要求的初值,可在以上隔离根的,基础上采用对分法继续缩小该含根子区间,二分法可以看作是搜索法的一种改进,2024/11/12,15,对分法又称二分区间法,是求解方程(1)的近似根的一种常用的简单方法。,设函数,f(x),在闭区间,a,b,上连续,且,f(a)f(b)0,根据连续函数的性质可知,f(x)=0,在(,a,b,),内必有实根,称区间,a,b,为有根区间。为明确起见,假定方程,f(x)=0,在区间,a,b,内有惟一实根,x,*,。,二分法的基本思想:,首先确定有根区间,将区间二等分,通过判断,f(x),的符号,逐步将有根区间缩小,直至有根区间足够地小,便可求出满足精度要求的近似根。,7.2,对分法,2024/11/12,16,取有根区间,a,b,之中点,将它分为两半,分点 ,这样就可缩小有根区间；,二分法求根过程,设方程,f(x)=0,在区间,a,b,内有根,二分法就是逐步收缩有根区间，最后得出所求的根。具体过程如下,:,2024/11/12,17,对压缩了的有根区间 重复,的步骤,即取中点,将区间 再分为两半,然后再确定有,根区间 ,其长度是 的二分之一；,如此反复下去,若不出现 ,即可得出一系列有,根区间序列：,上述每个区间都是前一个区间的一半,因此 的长,度,:,当,k,时趋于零,这些区间最终收敛于一点,x,*,即为所求的根,a x,*,x,0,b,a,1,b,1,2024/11/12,18,每次二分后,取有根区间 的中点,作为根的近似值，得到一个近似根的序列,该序列以根,x,*,为极限,只要二分足够多次(即,k,足够大),便有,这里,为给定精度,由于 ,则,2024/11/12,19,当给定精度,0,后,要想 成立,只要,取,k,满足 即可，亦即当:,时,做到第,k+1,次二分,计算得到的 就是满足精度要求的近似根。,在程序中通常用相邻的 与 的差的绝对值或 与 的差的绝对值是否小于,来决定二分区间的次数。,2024/11/12,20,例,1,求方程,f(x)=x,3,-x-1=0,在区间1.0,1.5,内 的一,个实根,使误差不超过0.510,-2,。,例,2,证明方程 在区间2,3内有一个根,使用二分法求误差不超过0.510,-3,的根要二,分多少次？,证明 令,且,f(x),在2,3上连续,故方程,f(x)=0,在2,3内至少有一个根。又 ，当时 时,故,f(x),在,2,3,上是单调递增函数,从而,f(x),在,2,3,上有且仅有一根。,2024/11/12,21,误差限为 只要取,k,满足,即可，亦即,给定误差限,0.510,-3,使用二分法时,所以需二分10次便可达到要求。,2024/11/12,22,二分法的优点是不管有根区间,a,b,多大,总能求出满足精度要求的根,且对函数,f(x),的要求不高,只要连续即可,计算简单;它的局限性是只能用于求函数的实根,不能用于求复根及重根,它的收敛速度与比值为,1/2,的等比级数相同，,不算太快，因此一般在求方程近似根时，不太单独使用，常用它来为其它方法求方程近似根提供好的初始值。,2024/11/12,23,对于一般的非线性方程,没有通常所说的求根公式求其精确解,需要设计近似求解方法,即迭代法。它是一种逐次逼近的方法,用某个固定公式反复校正根的近似值,使之逐步精确化，最后得到满足精度要求的结果。,迭代法的基本思想,为求解非线性方程,f(x)=0,的根，先将其写成便于迭代的等价方程,其中 为,x,的连续函数,7.3,迭代法,-(2),2024/11/12,24,2024/11/12,25,-(3),称,(3),式为求解非线性方程,(2),的,简单迭代法,再将 代入式 的右端，得到,依此类推,得到一个数列,其一般表示,2024/11/12,26,则称迭代法,(3),收敛,否则称为发散,-(4),将,(2),式表示为,收敛,2024/11/12,27,例,3.,解,:,(1),将原方程化为等价方程,发散,2024/11/12,28,显然迭代法发散,(2),如果将原方程化为等价方程,2024/11/12,29,仍取初值,x,2,=0.9644,x,3,=0.9940,x,4,=0.9990,x,5,=0.9998,x,6,=1.0000,x,7,=1.0000,依此类推,得,已经收敛,故原方程的解为,迭代法的几何意义,通常将方程,f(x)=0,化为与它同解的方程,的方法不止一种,有的收敛,有的不收敛,这取决于 的性态,方程 的求根问题在几何上就是确定曲线,y=,与直线,y=x,的交点,P,*,的横坐标。,对方程,f(x)=0,可以构造不同的迭代公式,但迭代公式 并非总是收敛。那么,当迭代函数 满足什么条件时，相应的迭代公式才收敛呢？,2024/11/12,30,2024/11/12,31,定理,1.,且有误差估计式,1.,迭代法收敛的条件,这是事后估计，也就是停机标准。,L,越小，收敛速度越快,这是事前估计。选取,n,，预先估计迭代次数,2024/11/12,32,例,4.,用迭代法求方程的近似解,精确到小数点后,6,位,解,:,本题迭代函数有两种构造形式,因此采用迭代函数,2024/11/12,33,d,1,=0.1000000,d,2,=-0.0105171,d,3,=0.1156e-2,d,4,=-0.1265e-3,d,5,=0.1390e-4,d,6,=-0.1500e-5,d,7,=0.1000e-6,由于,|d,7,|=0.1000e-0061e-6,因此原方程的解为,x,7,=0.090525,x,1,=0.1000000,x,2,=0.0894829,x,3,=0.0906391,x,4,=0.0905126,x,5,=0.0905265,x,6,=0.0905250,x,7,=0.0905251,2.,迭代法的加速,一个具有实用价值的迭代法，不仅要求它收敛，而且还要求它收敛比较快。迭代收敛的速度是指迭代误差的下降速度。在定理,1,中我们知道,L,越小或 迭代法收敛越快。,若迭代过程收敛缓慢，就会增加计算量，因此，需要设法提高迭代速度。,2024/11/12,34,当 范围不大时,设 变化不大,其估计值为,L,则有,（1）加速迭代法,设 是根 的某个近似值,用迭代公式校正一次得,又 根据微分中值定理有,其中,2024/11/12,35,令,可见,若将误差值 补偿到 ,则可,得到的比 更好的近似值,得到加速迭代公式,2024/11/12,36,例,