班 级 020991 学 号 02099037 计算方法大作业 题 目 基于牛顿插值法一种新型非线性方程求根解法及算法分析 学 院 电子工程学院 班 级 020991 学生姓名 杜凡 02099037 摘要非线性方程，就是因变量与自变量之间的关系不是线性的关系，如平方关系、对数关系、指数关系、三角函数关系等等。求解此类方程往往很难得到精确解，经常需要求近似解问题。相应的求近似解的方法也逐渐得到大家的重视。求解非线性方程的方法很多，以迭代法为主，主要有二分法，牛顿迭代法，牛顿下山法，割线法，等等，本文旨在突破传统思维，以新的角度介绍一种非线性方程的解法，牛顿插值解非线性方程。评价一个迭代公式的优劣，除去收敛条件之外，主要是看它的效能指标，即达到规定的精确度所花费的代价。因此如何构造收敛的迭代公式，分析公式的收敛速度和收敛条件，以及加快收敛的技术，这些都是迭代法研究的课题。本文主要对牛顿插值法进行改造，通过对函数的逆函数进行牛顿插值多项式插值从而求出处对应的值，即所需的根，通过对方程f(x)=x.2-exp(x)的求解分别比较了二分法和牛顿插值拓展法两种方式下的求解异同从而得出结论：在误差允许的范围内，牛顿逆插解方程的改进解法已经能够得到相当高精度的解。【关键字】 非线性方程 二分 牛顿插值 一、算法思路根据对牛顿插值法的学习，我们受到启发，牛顿插值可以实现由（x,y）矩阵数据得到牛顿插值多项式，从而获得任意xi值处对应的函数值。我们可以再任意单调的区间，由（y，x）矩阵求出牛顿插值多项式，进而求得yi处对应的xi值，当我们令yi=0时，即可对任意线性和非线性方程求解。用牛顿插值求f(x)的反函数在0点的值f(0)，即为f(x)=0的解。用牛顿插值多项式对y,x进行逆插值得到y=f(x)的f(0),即xi=chashangnewton(y,x,0); xi就是f(x)=0的解二、 未改进的算法matlab程序1)逆插值求解算法%main.mclc;clear;x=-1:0.1:0;y=fc(x); 这里f(x)= x.2-exp(x) xi=chashangnewton(y,x,0);：function N=chashangnewton(x,y,xi) 牛顿插值子程序%Newtonn=length(x);m=length(y);if m=n error(x or y );endA=zeros(n);Z=1.0;A(:,1)=y;N=A(1,1);for k=2:n % k for i=k:n % i A(i,k)=(A(i-1,k-1)-A(i,k-1)/(x(i+1-k)-x(i); end Z=Z*(xi-x(k-1); N=N+Z*A(k,k);endfprintf(Newton10 %.10fn,N);function f=fc(x)f=x.2-exp(x);下面我们以x.2-exp(x)=0的求解为例介绍非线性方程的新解法方程x.2-exp(x)=0为非线性方程，其曲线图如下图4 函数曲线图首先以二分法方程求解，通过matlab程序运算可得结果如下：迭代次数:0 根:-0.500000 误差:0.500000迭代次数:1 根:-0.750000 误差:0.250000迭代次数:2 根:-0.625000 误差:0.125000迭代次数:3 根:-0.687500 误差:0.062500迭代次数:4 根:-0.718750 误差:0.031250迭代次数:5 根:-0.703125 误差:0.015625迭代次数:6 根:-0.710938 误差:0.007813迭代次数:7 根:-0.707031 误差:0.003906迭代次数:8 根:-0.705078 误差:0.001953迭代次数:9 根:-0.704102 误差:0.000977迭代次数:10 根:-0.703613 误差:0.000488迭代次数:11 根:-0.703369 误差:0.000244迭代次数:12 根:-0.703491 误差:0.000122迭代次数:13 根:-0.703430 误差:0.000061迭代次数:14 根:-0.703461 误差:0.000031迭代次数:15 根:-0.703476 误差:0.000015迭代次数:16 根:-0.703468 误差:0.000008迭代次数:17 根:-0.703465 误差:0.000004迭代次数:18 根:-0.703466 误差:0.000002二分法结果为-0.703467通过我们的新型非线性方程解法：牛顿插值拓展解法可得结果如下Newton插值的结果保留6位小数是 -0.703467三、算法检验及误差分析：比较明显可以看出牛顿插值多项式插值的结果已经达到并超过了同比情况下二分法的迭代至5位小数的情况，所以可以得出结论：在误差允许的范围内，牛顿插值多项式的拓展解法已经能够得到相当高精度的解，完全可以满足对一般非线性方程的求解。对于方程x.2-exp(x)=0，用牛顿插值求f(x)=x.2-exp(x)的反函数在0点的值f(0)，发现当牛顿插值公式在x=-1，0区间插值，所求方程的解精度达到小数点后六位有效数字，如下图但如果扩大插值区间例如在-1,1区间插值，结果将会变得相当相当大，如下图上面这个结果很有趣。我试着把步长改为0.1，发现结果又变得比较准确，精度达到小数点后三位有效数字，当令x=-1:0.1:0即缩小根的区间，结果精确到了六位有效数字。可见插值得到解的精度与插值横坐标的区间即步长有很大关系。利用插值余项进行误差分析其中 设插值区间是a,b，b-a1且设置的步长h较小，xn-x0有很大概率大于1，如果使xn有几百几千个，累乘的值相当大，则插值多项式的误差就相当大。四、算法的改进为了提高牛顿逆插法的精度，可以结合二分法缩小根的范围，使,在a,b间的数据进行逆插值，得到方程的解。二分法缩小根区间的程序function q w=boundtwodivi(a,b)eps=0.4;while(b-a)eps) c=(a+b)/2; y=f(c); if(y*f(a)0) b=c; else a=c; endendq=a;w=b;主程序clc;clear;a=-10;b=10;q w=boundtwodivi(-2,2); 二分法缩小根区间x=q:0.01:w;y=f(x);x0=chashangnewton(y,x,0); 牛顿逆插fprintf(x=%.10fn,x0)【参考资料】1、李庆扬，王能超，易大义. 数值分析第4版. 清华大学出版社. 2001.ISBN7-302-04561-5.2、冯有前. 数值分析. 清华大学出版社. 2001.ISBN7-810-82495-33、计算方法与实习-孙志忠 东南大学出版社【附录】1、概论1.1 非线性方程所谓非线性方程，就是因变量与自变量之间的关系不是线性的关系，这类方程很多，例如平方关系、对数关系、指数关系、三角函数关系等等。2.相关算法的介绍：非线性方程数值解法（numerical method of nonlinear equation）解法概论当f(x)是超越函数或高次多项式时，f(x)=0称为非线性方程，此类方程除少数情形外，只能求近似解。求解非线性方程的主要方法是迭代法。使用这一方法一般至少要知道根的一个近似值x0，然后将原方程f(x)=0改变成与它同解但便于迭代的形式x=j(x)，利用迭代公式xk+1=j(xk)，k=0，1，2，就能求出一系列逐步精确的近似值。例如常用的迭代法有：牛顿迭代公式 割线迭代公式此外还有二次插值法、切比雪夫迭代法及艾特肯加速法等。评价一个迭代公式的优劣，除去收敛条件之外，主要是看它的效能指标，即达到规定的精确度所花费的代价。因此如何构造收敛的迭代公式，分析公式的收敛速度和收敛条件，以及加快收敛的技术，这些都是迭代法研究的课题。 非线性方程以高精度算术为支持，可以差商型导数为指导，可计通用求解方法。迭代法首先要求所构造的迭代公式收敛，即导数的绝对值小于1，且值越小收敛速度越快，此法用的比较广泛，速度基本上很快的。迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程,跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。迭代算法是用计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。加速迭代法可以加快迭代的速度，甚至一些不收敛的迭代函数经加速后一般也能获得收敛。二分法及其程序代码一般地，对于函数f(x),如果存在实数c,当x=c时，若f(c)=0,那么把x=c叫做函数f(x)的零点。假定f(x)在区间（x，y）上连续先找到a、b属于区间（x，y），使f(a)，f(b)异号，说明在区间(a,b)内一定有零点，然后求f(a+b)/2现在假设f(a)0,ab; 如果f(a+b)/2=0，该点就是零点，如果f(a+b)/20,则在区间（(a+b)/2，b)内有零点， a=(a+b)/2，从开始继续使用中点函数值判断。如果f(a+b)/20，则在区间(a,(a+b)/2)内有零点，b=(a+b)/2，从开始继续使用中点函数值判断。这样就可以不断接近零点。通过每次把f(x)的零点所在小区间收缩一半的方法，使区间的两个端点逐步迫近函数的零点，以求得零点的近似值，这种方法叫做二分法。从以上可以看出，每次运算后，区间长度减少一半，是线形收敛。另外，二分法不能计算复根和重根。图2 二分法求函数零点给定精确度,用二分法求函数f(x)零点近似值的步骤如下:1. 确定区间a,b,验证f(a)f(b)0,给定精确度.2. 求区间(a,b)的中点c.3. 计算f(c).(1) 若f(c)=0,则c就是函数的零点;(2) 若f(a)f(c)0,则令b=c;(3) 若f(c)