牛顿法逆插值法解方程及其分析.docx

牛顿法逆插值法解方程及其分析.docx

《牛顿法逆插值法解方程及其分析.docx》由会员分享，可在线阅读，更多相关《牛顿法逆插值法解方程及其分析.docx（12页珍藏版）》请在冰点文库上搜索。

牛顿法逆插值法解方程及其分析

班级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.m

clc;clear;

x=-1:

0.1:

0;

y=fc（x）;这里f（x）=x.^2-exp（x）

xi=chashangnewton（y,x,0）;

：

functionN=chashangnewton（x,y,xi）牛顿插值子程序

%Newton»ù±¾²åÖµ·½·¨

n=length（x）;

m=length（y）;

ifm~=n

error（'xoryÊäÈëÓÐÎó£¬ÔÙÀ´~'）;

end

A=zeros（n）;

Z=1.0;

A（:

1）=y;

N=A（1,1）;

fork=2:

n%kΪÁбê

fori=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）;

end

fprintf（'Newton²åÖµµÄ½á¹û±£Áô10λСÊýÊÇ%.10f\n',N）;

functionf=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-a>1且设置的步长h较小，xn-x0有很大概率大于1，如果使xn有几百几千个，

累乘的值相当大，则插值多项式的误差就相当大。

四、算法的改进

为了提高牛顿逆插法的精度，可以结合二分法缩小根的范围，使

在[a,b]间的数据进行逆插值，得到方程的解。

二分法缩小根区间的程序

function[qw]=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;

end

end

q=a;

w=b;

主程序

clc;clear;

a=-10;

b=10;

[qw]=boundtwodivi（-2,2）;二分法缩小根区间

x=q:

0.01:

w;

y=f（x）;

x0=chashangnewton（y,x,0）;牛顿逆插

fprintf（'·½³ÌµÄ¸ùx=%.10f\n',x0）

【参考资料】

1、李庆扬，王能超，易大义.《数值分析》第4版.清华大学出版社.2001. ISBN 7-302-04561-5.

2、冯有前.《数值分析》.清华大学出版社.2001. ISBN 7-810-82495-3

3、《计算方法与实习》- 孙志忠东南大学出版社

【附录】

1、概论

1.1非线性方程

所谓非线性方程，就是因变量与自变量之间的关系不是线性的关系，这类方程很多，例如平方关系、对数关系、指数关系、三角函数关系等等。

2.相关算法的介绍：

非线性方程数值解法（numericalmethodofnonlinearequation）

解法概论

当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,f（b）>0,a

<1>如果f[（a+b）/2]=0，该点就是零点，

<2.1>如果f[（a+b）/2]<0,则在区间（（a+b）/2，b）内有零点，a=（a+b）/2，从<1>开始继续使用中点函数值判断。

<2.2>如果f[（a+b）/2]>0，则在区间（a,（a+b）/2）内有零点，b=（a+b）/2，从<1>开始继续使用中点函数值判断。

这样就可以不断接近零点。

　　通过每次把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）·f（b）<0,则令a=c.

（4）判断是否达到精确度ξ:

即若|a-b|<ξ,则得到零点近似值a（或b）,否则从2开始重复；

二分法的优点是简单，对f（x）只要求连续，它的收敛速度与比值为1/2的等比级数相同，它的局限性是只能用于求实根，不能用于求复根及偶数重根。

二分法：

%main.m

functiontwodivi（a,b）

eps=5e-10;%Îó²î¾«¶È

delta=1e-6;%×Ô±äÁ¿

n=0;%µü´ú´ÎÊý

while

（1）

if（fc（a）*fc（b）>0）%ÎÞ¸ùÔòÌø³ö

break

end

c=（a+b）/2;%È¡ÖÐÖµ

w=fc（c）;

if（abs（w）

break;

elseif（fc（a）*w<0）%¸üÐÂbµã

b=c;

else%¸üÐÂaµã

a=c;

end

fprintf（'µü´ú´ÎÊý:

%d¸ù:

%fÎó²î:

%f\n',n,c,（b-a））

if（b-a

break;

end

n=n+1;

end

fprintf（'¶þ·Ö·¨½á¹ûΪ%.6f\t¾«¶ÈԼΪ%.6f\n',c）;

牛顿插值法

　　插值法利用函数f（x）在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f（x）的近似值。

如果这特定函数是多项式，就称它为插值多项式。

利用插值基函数很容易得到拉格朗日插值多项式，公式结构紧凑，在理论分析中甚为方便，但当插值节点增减时全部插值基函数均要随之变化，整个公式也将发生变化，这在实际计算中是很不方便的，为了克服这一缺点，提出了牛顿插值。

　　牛顿插值通过求各阶差商，递推得到的一个公式：

　　f（x）=f[x0]+f[x0,x1]（x-x0）+f[x0,x1,x2]（x-x0）（x-x1）+...f[x0,...xn]（x-x0）...（x-xn-1）+Rn（x）