非线性方程求根的数值算法分析.doc

非线性方程求根的数值算法分析 摘 要众所周知，代数方程求根问题是一个古老的数学问题。早在16世纪就找到了三次、四次方程的求根公式。但直到19世纪才证明了次的一般代数方程是不能用代数公式求解的，或者求解非常复杂。因此需要研究用数值方法求得满足一定精度的代数方程的近似解。在工程和科学技术中许多问题常归结为求解非线性方程的问题。正因为非线性方程求根问题是如此重要的基础，因此它的求根问题很早就引起了人们的兴趣，并得到了许多成熟的求解方法。本课题主要介绍非线性方程的数值解法是直接从方程出发，逐步缩小根的存在区间，或逐步将根的近似值精确化，直到满足问题对精度的要求，主要的方法有逐步搜索法、二分法，迭代法，并写出这几种非线性方程的数值解法的算法步骤和例题，最后通过一个实际问题建立数学模型，用三种方法进行计算，得出结果并进行比较。 关键词： 非线性方程；寻根搜索法；二分法;迭代法；近似解THE ANALYSIS ABOUT NUMERICAL FOR SOLVING NONLINEAR EQUATIONABSTRACTAs we all know, it is an ancient problem about finding roots of algebraic equations. As early as 16th century ,people have found extract roots formulas of cubic equation and quartic equation. But it was not until the 19th century general algebraic equation is pr oved that time cannot use algebraic formula,or solving very complex.Therefore need to be studied using numerical methods to obtain approximate solutions to meet certain precision algebraic equations.There are many problems in engineering and science and technology often attributed to the problem of solving nonlinear equations. Because roots of non-linearequations on the basis of the problem is so important, so its the root problem have long attracted the interest of the people, and got many mature solu-tion.This topic mainly introduces the numerical solution of nonlinear equation that i-sdirectly from the equation, gradually reduce the existence of root range, or ro-ot of approximation will be accurate, until meet the requirements of the proble-m of accuracy. There are three methods, the method of step searching, dichoto-myie and the method of iterative, and then I will write this several algorithm steps and examples of numerical methods for solution of nonlinear equation, fi-nally, I will establish a practical problem, and use three problems to solve the problem, at last, I will make a comparison of these three kinds of method. Key words: Nonlinear equations；Roots search method; Dichotomy; Iteration method; The approximate solutions目 录1 问题背景介绍12 问题的分析12.1 数值算法理论分析22.1.1逐步搜索法22.1.2二分法32.1.3 迭代法43 实际问题的提出及建模73.1实际问题的提出73.2 建立模型84 模型求解84.1逐步搜索法求解94.2二分法求解94.3迭代法求解105 求解结果分析比较.105.1模型结果105.2模型结果分析106课程设计的总结与体会12参 考 文 献13附 录14 1 问题背景介绍我们都会解一元一次方程，对于二次方程，我们可以用熟悉的求根公式，而对于三次以上方程就不会解了。事实上，三次和四次方程的求根公式很复杂，五次以上代数方程一般无求根公式，至于一般的超越方程，更没有求根公式。因此，为求解一个非线性方程，我们必须依靠某种数值方法来求其近似解。2 问题的分析对于一个非线性方程，在求其根时，必须考虑两个问题（1）方程是否有根；（2）方程的根的个数，首先我们需要知道非线性方程根的定义：设有一个非线性方程，其中为实变量的非线性函数。（1）如果有使，则称为方程的根，或为的零点。（2）当为多项式，即则称为次代数方程。当包含指数函数或者三角函数等特殊函数时，则称为特殊方程。根的重数的定义（3）如果，其中。为正整数，则称为的重根。当时，称为的单根。其次，根的存在由于零点定理密不可分，零点定理的意义：设在连续，且，则存在，使得，即在内存在零点。2.1 数值算法理论分析2.1.1逐步搜索法对于方程，为简明起见，设，从区间左端点出发按某个预定步长（如取，为正整数），一段一段地向右跨，每跨一步进行一次根的搜索。即检查节点上的函数值的符号，若，则即为方程解；若，则方程根在区间中，其宽度为。例 考察方程的根。解 注意到 则在内至少有一个根，设从出发，以为步长向右进行根的搜索。列表记录各节点函数值的符号, 如表4.2.1所示。可见方程在内必有一根。表2.1的符号00.51.01.5的符号-+易见，此方法应用关键在步长的选择上。很明显，只要步长取得足够小，利用此法就可以得到任意精度的根，但缩小，搜索步数增多，从而使计算量增大，用此方法对高精度要求不简便。2.1.2二分法对非线性方程： (2.1) 其中在上连续且设，不妨设在内仅有一个零点。求方程的实根的二分法的过程，就是将逐步分半，检查函数值符号的变化，以便确定包含根的充分小区间。二分法的步骤如下：记，第1步：分半计算，即将分半。计算中点及。若，则根必在内，否则必在内（若，则），于是得到长度一半的区间含根，即，且。第2步： . . .第步：（分半计算）重复上述过程。设已完成第1步第步，分半计算得到含根区间，且满足，即，则第步的分半计算：，且有： (2.2)确定新的含根区间，即如果，则根必在内，否则必在内，且有：。总之，由上述二分法得到序列，由(2.2)有：。可用二分法求方程的实根的近似值到任意指定的精度，这是因为：设为给定精度要求，则由，可得分半计算次数应满足： (2.3) 二分法的优点是方法简单，且只要求连续即可。可用二分法求出在内的全部实根，但二分法不能求复根及偶数重根，且收敛较慢，函数值计算次数较多。例 用二分法求在内一个实根，且要求精确到小数点后第三位。（即）解 由代入式(2.3)，其中，可确定所需分半次数为，计算结果部分如表2.2所示（显然）。表2.2部分计算结果81.1328131.1406251.1367190.02061991.1328131.1367191.1347660.4268415101.1328131.1347661.133789111.1337891.1347661.1342772.1.3 迭代法 迭代法是一种逐次逼近法。它是求解代数方程、超越方程及方程组的一种基本方法，但存在是否收敛及收敛快慢的问题。 用迭代法求解的近似根，首先需将此方程化为等价的方程： (2.4)然而将化为等价方程的方法是很多的。迭代法步骤：设方程为（1）取方程根的一个初始近似，且按下述逐次代入法，构造一个近似解序列： （2.5）这种方法称为迭代法（或称为单点迭代法），称为迭代函数。（2）若由迭代法产生序列有极限存在，即，称为收敛或迭代过程（2.5）收敛，否则称迭代法不收敛。若连续，且，则即为方程（2.4）的解（称为函数的不动点），显然在由方程转化为等价方程时，选择不同的迭代函数，就会产生不同的序列（即使初值选择一样）且这些序列的收敛情况也不一定相同。如下图所示，解方程f(x)=0可以等价地变换成求解 x=g(x)，图 2.3 方程求根迭代法原理示意图在几何上，就等价求曲线yx和yg(x）交点P*的坐标x*。从图中x0点出发，由函数yg(x0）得出yP0，代入函数yx中得出Q1，再把Q1的x坐标 x1代入方程y=g(x)得出P1，如此继续下去，便可在曲线yg(x)上得到一系列的点P0，P1， ，Pk， ，这些点的x坐标便是迭代数列 xl , x2 ， ， xk， 它趋向于方程的根 x*，数列的元素就是方程根的近似值。数列的收敛就等价于曲线yx和y=(x)能够相交于一点。关于收敛性，从几何上观察知道在（1），（2）情况下收敛于，在(3)，(4)情况不收敛于。图2.4 收敛性与几何意义迭代法的收敛定理 设有方程，（1） 设于一阶导数存在，（2） 当时，有，（3） 满足条件：则有： 在上有唯一解， 对任意选取初始值，迭代过程收敛即， ， 误差估计式：。选取的g(x )必须满足: (1) 两方程同解；(2) 迭代序列收敛于其根。例 对方程求解.解 可用不同的方法将其化为等价方程：（1） （2）化为如下迭代函数：由计算可以看出，我们选取的两个函数，分别构造序列收敛情形不一样（初值都取为1），在中收敛且，在中计算出无定义。部分计算结果如下表2.5：01.01.011.3414710.52359921.4738200.02360131.049530-0.49655541.497152-1.48776151.49728961.49730071.497300表2.5 部分计算结果3 实际问题的提出及建模3.1实际问题的提出有一块边长为30 的正方形铁皮, 将其四个角各截去一个边长为x 的小正方形, 然后折成一个无盖的盒子, 如图所示. 如果要做成一个容积是1200 的无盖盒子, 那么截去的小正方形的边长x是多少厘米 (精确到0.00001 ).3.2 建立模型设盒子的体积为y, 所以x为自变量的函数解析式为,0x15.由容积是1200, 则 ,令,则求X的值即为求的根，如此，建立了上述数学模型.4 模型求解首先确定的根的大致位置，在matlab上绘制的函数，使函数展现在方格图中，便于大致确定跟的范围，输入相关命令后得到下图2从图中我们可以得出，函数有两个根，分别位于和之内，方便起见，下面我们只对间的那个根进行详尽的描述。4.1逐步搜索法求解由于我们之前确定了根的范围，因此搜索区间限定在(1, 2)之间，我们选定步长为0.0001，当精度达到0.0001的时候停止，运行程序1后，分别计算f(1)、f(1.0001)的值，得，继续计算f(1.0002)，得,继续计算f(1.0003) ,f(1.0004)的值这么下去,最终得到输出结果是k = 10001，r =1.6950即搜索点的个数为10001个，根的近似值为,达到精度要求。同理可得另一个根为.4.2二分法求解由于我们之前确定了根的范围，因此设定a=1,b=2,计算得，因此根在（1,2）之间，再计算，可以得出根的范围在（1.5,2）之间，再次计算的值以此类推，设定精确值依旧为0.0001，后得到输出结果k =9，x =1.6946，表明进行了9次计算，便得到符合精确值要求的结果为.同理可得另一根为.4.3迭代法求解我们首先要选择合适的迭代函数，所谓合适就是指该函数是收敛的，随着迭代次数的增加迭代的结果会逐渐稳定下来，直到达到精确值为止，这次迭代法中我选择的是进行迭代，精度同样选择为0.0001，发现迭代了7次就得到了，同理得到.5 求解结果分析比较.5.1模型结果如果要做成一个容积是无盖盒子时, 截去的小正方形的边长大约是或.5.2模型结果分析把上述得到的结果汇总，得到如下列表：计算方法计算次数计算结果逐步搜索法100011.6950二分法91.6946迭代法71.6946从表中可以明显看出，在同一精度的要求下，得到的结果却不相同，可以看出逐步搜索法的精度取决于步长的大小，而步长的大小又决定了计算量的大小，逐步搜索法明显没有二分法和迭代法的精度高，但是运算次数却是两者的上千倍，因此逐步搜索法只适用于那些对精度不高的计算；而二分法比较容易理解，每计算一次都会使精度变化为，比较容易达到所要求的精度；对于迭代法来说，首先需要判断迭代函数是否收敛，迭代序列是否收敛于，如果不收敛还需要更换新的迭代函数，甚至有的函数无法进行这种方式的计算，因此迭代法对函数的要求比较高，但我们可以看到它的计算次数比二分法还要少，计算的速度更快，也是一种较为理想的计算方法。6课程设计的总结与体会这次数值分析课程设计我们虽然只经历了两周，但是受益匪浅。在这次课程设计中，我们运用到了以前所学的数值分析、数学分析、常微分方程等相关专业课的知识，如逐步搜索法、二分法、迭代法以及matlab汇编语言等。虽然过去都将这些知识用于解题中，只是独立应用过它们去做题，但在这次课程设计中，把这么多方法拿到一起，去解决同一个问题，并对它们的运算过程和结果进行比较，才发现其中大有奥秘，因此在学习中，注意那些一题多解的例子，要善于分析和比较，不同方法的各有千秋，有的虽然简便，但对精度要求不高，有的虽然复杂还是精度却很高，要善于对不同的方法根据实际需要进行取舍，才能使计算既好又快，同时我还发现，有目的性的带着问题去学习，学习的效率很高。一个课程设计过程，好比我们的成长历程，常有一些不如意，难免会遇到各种各样的问题。这也激发了我今后努力学习的兴趣，通过这次设计，我懂得了学习的重要性，了解到理论知识与实践结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作打下基础。参 考 文 献1 李庆杨，王能超，易大义编数值分析（第4版）M：华中科技大学出版社，2006：13-24. 2 姜启源，谢金星，叶俊编数学模型（第三版）M：高等教育出版社，2005：106-1443 奚梅成.数值分析方法 M：中国科技技术大学出版社，2007：34-474 薛毅.数值分析与实验 M：北京理工大学出版社，2005：78-895 汪卉琴，刘目楼.数值分析 M：冶金工业出版社，2004：64-786 丁丽娟，程杞元.数值计算方法 M：北京理工大学出版社，2005：32-40附 录程序1： 逐步搜索法(1)function k,r=zbss(a,b,h,tol)X=a:h:b;Y=funs(X); n=fix(b-a)/h)+1;m=0;X(n+1)=X(n);Y(n+1)=Y(n);for k=2:nX(k)=a+k*h;Y(k)=funs(X(k); sk=Y(k)*Y(k-1);if sk=0,m=m+1;r(m)=X(k);endxielv=(Y(k+1)-Y(k)*(Y(k)-Y(k-1);if (abs(Y(k)tol)&( xielv0,disp(请重新调整