实验名称非线性方程求根方法111

1、探索实验1 非线性方程求根方法 一、 实验目的 理解非线性方程求根的过程和算法，学习用计算机求根的一些科学计算方法和简单的编程技术。 二、概念与结论1. 零点定理：设f(x)在区间a,b连续,且f(a)f(b)<0, 则至少存在一点x Îa,b,使得f(x )=0。2. 非线性方程: 函数方程f（x）= 0 中若f(x)不是x的线性函数, 则称f（x）= 0 为非线性方程, 特别若f(x)是n次多项式，则称f（x）= 0为n次多项式方程或代数方程；若f(x)是超越函数，则称f（x）= 0为超越方程。3. 方程¦(x)=0 的根： 使方程¦(x)=0成立的x值

2、称为方程¦(x)=0的根或函数¦(x)的零点，特别地，如果函数¦(x)可分解为 ¦(x)=（x-a）mg(x) 且g(a )¹0, 则称a是¦(x)的m重零点或¦(x)=0的m重根。 当m=1时，称a是¦(x)的单根 或单零点。4. 简单迭代法收敛定理：定理1：假定迭代函数j(x) 满足下列条件：1. 对任意 xa,b时,有j(x) a,b 2. 存在正常数 L<1，使对任意x1,x2 a,b 有 | j(x1) - j(x2 )|£L| x1 - x2 | 则j(x)在a,b内有唯一的不动点x*，

3、且对于任意初值 x0 a,b 由迭代公式 xk+1= j(xk)产生的数列xk均收敛于方程根x*。 如果将条件2改为| j¢(x) |£L ， x a,b，也有同样的收敛结果。定理2：设x*是迭代函数j(x)的不动点，m为正整数，且j（m）(x)在x*的邻域N(x*)内连续,并有如下关系 j（k）(x*) = 0 ,k=0,1,m-1,j（m）(x*) ¹0则由 xk+1= j(xk)产生的数列xk在邻域N(x*)内是m阶收敛的，且有极限 k®µ 时 （ x* - xk+1 )/ （ x* - xk ) m Þ j（m）(x*) /m

4、!5. 简单迭代法误差定理： 在简单迭代法收敛定理的条件下，有如下误差估计式1) | x* - xk | £ | xk - xk-1 | L /(1-L)2) | x* - xk | £ | x1 - x0 | Lk /(1-L)6Newton迭代法收敛定理： 假定函数f (x)在 xa,b时满足下列条件：1. f(a)f(b)<0 2.f¢(x ) ¹0, xa,b3. f¢¢ (x ) 存在且不变号, xa,b则对于任意初值 x0 a,b ，只要f(x0)f¢¢ (x0 )³0,那么由Newto

5、n 迭代公式产生的数列xk一定收敛于方程根x*。三、程序中Mathematica语句解释：1. fx_=Input“键入函数f(x)=” 从键盘上输入函数f(x)2. 变量= Input 从键盘上给变量赋值3.N精确数x 或 精确数x /N 将精确数x 转化成近似实数4.N精确数x, 正整数n 将精确数x 转化成具有n位有效数字的近似实数5.Print表达式1,表达式2, , 表达式n 在屏幕某一行上依次输出表达式1,表达式2, 表达式n的值6. Dfx,x 求函数f(x)对x的偏导数f¢(x)。7. If 条件, 语句1 如果条件成立,则执行对应的语句1，并将语句执行结果作为If语

6、句的值，如果条件不成立，不执行语句1。8.If 条件, 语句1, 语句2 根据条件的成立与否确定执行哪一个语句，具体执行为:条件成立时，执行语句1，否则，执行语句2，并将语句执行结果作为If语句的值。9. Whiletest,body 当test为True时,计算body,重复对test的判断和body的计算,直到test不为True时终止 。这里test为条件, body为循环体,通常由body控制test值的变化。如果test不为True,则循环体不做任何工作.四、方法与程序 非线性方程 f(x)=0求根的方法有区间法和迭代法两大类，二分法、弦位法就是区间法；简单迭代法和Newton迭代法

7、及其变形是迭代法。这里只给出二分法、简单迭代法和Newton迭代法构造过程及程序。1二分法 二分法是最简单的求根方法，它是利用连续函数的零点定理，将含根区间逐此减半缩小，取区间的中点构造收敛点列xk来逼近根 x* 的。1.1 二分法构造过程： 设方程f(x)=0在(a,b)内只有一实根，取a,b区间二等分的中点x0 =(a+b)/2。 若f(x0)=0,则x0是f(x)=0的实根 x* ，输出近似根x0，终止；否则如果f(a)f(x0)<0 成立,则根x* 必在区间(a, x0)内,取a1=a,b1= x0；否则根x* 必在区间(x0,b)内,取a1= x0, b1=b。这样,得到新区间

8、a1,b1,其长度为a,b的一半,如此继续下去,进行k次等分后,得到一组不断缩小的区间序列： a,b,a1,b1,.,ak,bk,和对应区间的中点数列：x k = (ak+ bk )/2，k=0,1,2,.。其中每个区间都含有根x*，满足： a,b É a1,b1 É.É ak,bk É且每个区间都是前一个区间长度的一半。由于 ak,bk的长度为(b-a)/2k，当k不断变大时,则有这些区间将收敛于一个点x* ,该点即为所求的根。 当做到第k步时，有 e为给定精度，此时x k »x * 即为满足要求的近似根。1.2 二分法算法： 1 计算a,b

9、区间的中点存放在变量x0中：x0 Ü(a+b)/22 如果函数值f(x0)=0,则x0是f(x)=0的实根 x* ，输出根x0,终止3 如果函数值f(a)f(x0)<0,则b Ü x0 ，否则a Ü x04 如果b-a£e（e为给定的精度）,则输出根的近似值(a+b)/2,终止，否则转1。1.3 二分法程序：Clearxfx_=Input“键入函数f(x)=”;a= Input“键入左端点a=”;b=Input“键入右端点b=”;Print“a=”,a, “ b=”,b, “ f(x)=”,fxe1=10(-10);eps=Input“键入根的误差

10、限eps=”;n=0;Whileb-a>eps,x=(a+b)/2;n=n+1;w=fx;IfAbsw<e1,Print“n=”,n, “ x=”,x, “ fx=”,w;Break;p=fa*w/N; Ifp<0,b=x,a=x;Print“n=”,n, “ x=”,x/N, “ eps=”,b-a/N说明：本程序用于求非线性方程f(x)=0在区间a,b内的根，这里要求f(x)在区间a,b连续,且f(a)f(b)<0。程序执行后，先通过键盘输入函数f(x)和区间左端点a和右端点b及根的精度要求e，程序即可给出每次二分的次数和对应的点列x k，其中最后输出的结果即为所求

11、的根。程序中变量说明：x：存放初值x 0和二分法中的x ka: 存放含根区间的左端点akb: 存放含根区间的右端点bke1:描述f(xk)=0的微小值,这里用|f(xk)|<e1表示f(xk)=0n: 存放二分次数注：语句Ifp<0,b=x,a=x中p的一定要是算出的数值，否则会出现错误。本程序中用“p=fa*w/N”而不用“p=fa*w”就是这个原因。 1.4 例题与实验1.用二分法求方程x ex =1 在0，1内的根，要求误差不超过0.001。解：令f(x)= xex 1，因为f(0)=-1<0,f(1)=e-1>0,所以可以用二分法。 执行二分法程序后，在输入的四

12、个窗口中按提示分别输入x*Expx-1、0、1、0.001，每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果： a=0 b=1 f(x)=-1 + Ex xn=1 x=0.5 e=0.5n=2 x=0.75 e=0.25n=3 x=0.625 e=0.125n=4 x=0.5625 e=0.0625n=5 x=0.59375 e=0.03125n=6 x=0.578125 e=0.015625n=7 x=0.570312 e=0.0078125n=8 x=0.566406 e=0.00390625n=9 x=0.568359 e=0.00195312n=10 x=0.567383 e=0

13、.000976562此结果说明共二分10次，求得的近似根为x=0.567383，其误差为e=0.000976562。2. 简单迭代法 简单迭代法也称逐次代换法，是非线性方程求根中各类迭代法的基础，其涉及的处理方法、概念、和理论都易于推广。2.1 简单迭代法构造过程： 由于对方程做等价变换根不发生变化，将方程f(x)=0等价变形为x=j(x)，构造迭代计算公式 xk+1= j(xk)取定初值x0，算出数列xk。如果xk收敛于x*，则有： 这说明x*就是方程f(x)=0的根。 上面 x= j (x)称为不动点方程， j (x)称为迭代函数。相的数列xk称为迭代数列。 2.2 简单迭代法算法： 1.

14、 输入初值x0、迭代精度eps、迭代函数g(x)和迭代最大次数Nmax2. For k=1,2,Nmax2.1 x Üg(x0)2.2 如果|x-x0|<eps ,则输出根x ，终止2.3 x0 Ü x3. 输出迭代失败，终止。2.3 简单迭代法程序：Clearx；nmax=500;gx_=Input"输入迭代函数"x0=Input"输入迭代初值"；eps=Input"输入根的精度"Do x=Ngx0,10; t=Absx-x0/N; Print"x=",x," n="

15、,n," eps=",t;Ift<eps,Break;x0=x, n,1,nmax;Ift>eps,Print"迭代失败"说明：本程序用于求非线性方程f(x)=0在x0附近的根。程序执行后，先通过键盘输入迭代函数g(x)和迭代初值x0及根的精度要求eps，程序即可给出每次迭代的次数和对应的点列x k，其中最后输出的结果即为所求的根。如果迭代超出500次还没有求出满足精度的根则输出迭代失败提示。程序中变量说明：x0：存放初值和迭代过程中的x kx: 存放迭代过程中的x k+1 nmax:存放迭代允许的最大次数注：迭代最大次数可以修改为其他数字。

16、 2.4例题与实验 2用迭代法求方程x3+2x2 +10x-20=0 在x=1附近的根，要求误差不超过10-6。解：变换方程后获得如下迭代格式：在输入的四个窗口中按提示分别输入x/(x2+2x+10)、1、0.0000001，每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果： x=1.538461538 n=1 eps=0.538462x=1.295019157 n=2 eps=0.243442x=1.401825309 n=3 eps=0.106806x=1.35420939 n=4 eps=0.0476159x=1.375298092 n=5 eps=0.0210887x=1.365

17、929788 n=6 eps=0.0093683x=1.370086003 n=7 eps=0.00415622x=1.368241024 n=8 eps=0.00184498x=1.369059812 n=9 eps=0.000818788x=1.368696398 n=10 eps=0.000363414x=1.368857689 n=11 eps=0.000161291x=1.368786103 n=12 eps=0.0000715861x=1.368817874 n=13 eps=0.0000317718x=1.368803773 n=14 eps=0.0000141013x=1.36

18、8810032 n=15 eps=6.25853 10-6x=1.368807254 n=16 eps=2.77771´10-6x=1.368808487 n=17 eps=1.23283´10-6x=1.36880794 n=18 eps=5.47164´10-7此结果说明迭代18次，求得的近似根为x=1.36880794，其误差为eps=5.47164´10-7。3用迭代法求x3-2x-5=0的正根，下面有三种不动点方程:用计算实验的方法判定它们在 x=2附近各自的收敛情况，选择收敛的方法求此根，精确到6位小数。解：对第一种不动点方程，在输入的四个窗

19、口中按提示分别输入(x3-5)/2、2、0.000001，每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果： x=6. n=1 eps=4.x=422. n=2 eps=416.x=1.50302886´108 n=3 eps=1.50302´108 x=6.790972232´1024 n=4 eps=6.79097´1024x=6.263626597´1074 n=5 eps=6.26363´1074x=4.914819518´10224 n=6 eps=4.91482´10224x=2.37439363

20、05´10674 n=7 eps=2.3743936305´10674x=2.677245217´102023 n=8 eps=2.677245217´102023x=Overflow迭代失败 通过计算结果可以看到迭代数列和误差都在不断变大，以至后来产生益出错误，因此，第一种迭代方法不收敛。 对第二种不动点方程，在输入的四个窗口中按提示分别输入5/(x2-2)、2、0.000001，每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果： x=2.5 n=1 eps=0.5x=1.176470588 n=2 eps=1.32353x=-8.1179775

21、28 n=3 eps=9.29445x=0.07824535218 n=4 eps=8.19622x=-2.507676418 n=5 eps=2.58592x=1.165924862 n=6 eps=3.6736x=-7.804948517 n=7 eps=8.97087x=0.08486483045 n=8 eps=7.88981x=-2.509035085 n=9 eps=2.5939x=1.164074684 n=10 eps=3.67311x=-7.7527778 n=11 eps=8.91685x=0.08605027968 n=12 eps=7.83883x=-2.5092902

22、09 n=13 eps=2.59534x=1.163727809 n=14 eps=3.67302x=-7.743083432 n=15 eps=8.90681x=0.08627332547 n=16 eps=7.82936x=-2.509349974 n=45 eps=2.59568x=1.163646575 n=46 eps=3.673x=-7.740817031 n=47 eps=8.90446x=0.08632559676 n=48 eps=7.82714x=-2.509349974 n=49 eps=2.59568x=1.163646575 n=50 eps=3.673.迭代失败通过

23、计算结果可以看到迭代数列没有收敛的趋势，且误差虽然没有不断变大并具有震荡特点，但不是不断变小趋于零的。因此，第二种迭代方法不收敛。 对第三种不动点方程，在输入的四个窗口中按提示分别输入(2x+5)(1/3）、2、0.000001，每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果： x=2.080083823 n=1 eps=0.0800838x=2.092350678 n=2 eps=0.0122669x=2.094216996 n=3 eps=0.00186632x=2.094500652 n=4 eps=0.000283656x=2.094543758 n=5 eps=0.00004

24、31053x=2.094550308 n=6 eps=6.55028´10-6x=2.094551303 n=7 eps=9.95374´10-7 计算结果可以看到迭代数列的收敛趋势。结果说明迭代7次，求得的近似根为x=2.094551303，其误差为eps=59.95374´10-7。因此，第三种迭代方法收敛。 本实验说明不是每种迭代都是收敛的。3. Newton迭代法 Newton迭代法也称切线法，是非线性方程求根方法中收敛的最快的方法，其涉及的近似处理方法很有代表性。 3.1 Newton迭代法构造过程： 将方程f(x)=0 线性化处理为近似方程，然后用近似

25、方程获得求根的迭代计算公式。具体为：设xk是f(x) = 0的一个近似根，把f(x)在 xk 处作泰勒展开，得：取前两项来近似代替f(x)(称为f(x)的线性化)，则得近似线性方程：设 f¢(xk ) ¹0 ,令其解为 xk+1 ,得:上式称为求f(x)=0根的Newton(牛顿)迭代格式。 3.2 Newton迭代法算法： 1.输入初值x0、迭代精度eps、函数f(x) 和迭代最大次数Nmax2.For k=1,2,Nmax1.1 如果|f¢(x0)|<eps1,则输出“迭代失败”提示并终止1.2 x Üx0-f (x0)/f¢ (x0

26、)1.3 如果|x-x0|<eps ,则输出根x ，终止1.4 x0 Ü x2 输出迭代失败，终止。3.3 Newton迭代法程序：Clearx,f,g;fx_=Input"fx="gx_=Dfx,x;x0=Input"输入迭代初值"eps1=0.00000000001;nmax=500;eps=Input"输入精度控制eps="Dou1=gx0; IfAbsu1/N<eps1,Print"迭代法失效"Break; x=x0-fx0/u1; u1=Absx-x0/N; Print"x

27、=",x," n=",n," eps=",u1; Ifu1<eps,Break,x0=x, n,1,nmax;Ifu1>eps,Print"迭代失败 "说明：本程序用于求非线性方程f(x)=0在x0附近的根。程序执行后，先通过键盘输入迭代函数f(x)和迭代初值x0及根的精度要求eps，程序即可给出每次迭代的次数和对应的点列x k，其中最后输出的结果即为所求的根。如果迭代超出500次还没有求出满足精度的根则输出迭代失败提示。程序中变量说明：x0：存放初值和迭代过程中的x kx: 存放迭代过程中的x k+1 nmax

28、:存放迭代允许的最大次数u1:临时变量注：迭代最大次数可以修改为其他数字。 3.4例题与实验 4. 用Newton迭代法求方程x ex 1=0=0 在x=0.5附近的根，要求误差不超过10-6。解：执行Newton迭代法程序后在输入的四个窗口中按提示分别输入x*Expx-1、0.5、0.0000001，每次输入后用鼠标点击窗口的“OK”按扭，得如下输出结果： x=0.57102 n=1 eps=0.0710204x=0.567156 n=2 eps=0.00386487x=0.567143 n=3 eps=0.0000122782x=0.567143 n=4 eps=1.23477 10-10此结果说明迭代4次，求得误差为e=1.23477´10-10的近似根，最后显示的近似根结果为x=0.567143，它只是部分表示，要看该近似根更详细的表示（如看其中前10位数）可以再键入命令 Nx,10后有近似根的为0.5671432904。五、 思考1.如果方程f(x)=0在a,b上有多个根，怎样用二分法求