毕业论文开题报1

毕业论文开题报告

论文题目:

newton迭代法在解非线性方程组的应用

院系名称: 数学系

专业班级: 信科08-1班

学生姓名: 李明乾

导师姓名: 袁海燕

开题时间: 2012年3月8日指导委员会审查意见：

开题报告撰写要求

一、“开题报告”参考提纲

1. 课题研究目的和意义；

2. 文献综述（课题研究现状及分析）3500字以上；

3. 基本内容、拟解决的主要问题；

4. 技术路线或研究方法；

5. 进度安排；

6. 主要参考文献。

二、“开题报告”撰写规范

请参照《黑龙江工程学院本科生毕业设计说明书及毕业论文撰写规范》要求。字数应在4000字以上，文字要精练通顺，条理分明，文字图表要工整清楚。

一、绪论

牛顿迭代法产生的背景： 牛顿迭代法（Newton's method ）又称为牛顿-拉夫逊方法（Newton-Raphson method ），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根,此时线性收敛，但是可通过一些方法变成超线性收敛。另外该方法广泛用于计算机编程中。

二、本课题的目的和意义

非线性方程组的数值解法在实际中有广泛的应用，特别是在各种非线性问题的科学计算中更显出它的重要性．而且，随着计算机的广泛应用，有更多的领域涉及到非线性方程组的求解问题，例如，动力系统，非线性有限元问题，非线性力学问题，还有非线性最优化与非线性规划问题等．因此，研究非线性方程组的解法就具有重要的实际意义．由于非线性方程组的复杂性，在解法上除了极特殊的非线性方程组外，直接法几乎是不能使用的，这需借助于迭代法来求解，课题研究的就是能否用牛顿迭代法或者更好的算法来求解非线性方程组

三、什么是牛顿迭代法、非线性方程、非线性方程组、如何用牛顿迭代法解非线性方程

(一)、牛顿迭代法：设已知方程f(x)=0有近似根x k (假定f ′(x)≠0),将函数f(x)在x k 处展开有f(x)≈f(x k )+f ′(x k )(x-x k ),于是方程f(x)=0可以近似的表示成f(x k )+f(x k )(x-x k )=0.这是个线性方程，记其根为x k+1,则x k+1=的计算公式为x k+1=x k -f(x k )/f ′(x k ),这就是牛顿法

牛顿法的几何意义：牛顿法具有明显的几何解释.方程f(x)=0的根x * 可解释为曲线y=f(x)与x 轴交点的横坐标(如图).设x k 是根x *的某个近似值，过曲线y=f(x)上横坐标为x k 的点P k 引切线，并将该切线与x 轴的交点的横坐标x k+1作为x *的新的近似值其切线方程为y=f(x k )+f ′(x k )(x-x k ),这样的求得的x k+1牛顿公式的计算结果，因此牛顿法也被叫做切线法

牛顿法的基本计算步骤：

步骤1 准备 选定初始近似值x 0,计算f 0=f(x 0),f 0′=f ′(x 0)

步骤2 迭代 按公式x 1=x =- f 0/f 0′迭代一次，得新的近似值x 1，计算f 1=f(x 1),f 1′=f ′(x 1)

步骤3 控制 如果x 1满足|δ|＜ε1或 |f 1|＜ε2,则终止迭代，以x 1作为所求的根；否则转步骤4.此处ε1,ε2是允许误差，而 δ= |x 1-x 0| ， 当|x 1|＜ C 时 |x 1-x 0|/|x 1|,当|x 1|≥C 时，

其中C 是取绝对误差和相对误差的控制常数，一般可取C=1.

步骤4 修改 如果迭代达到预先指定的次数N ，或者f 1′=0,则方程失败；否则以(x 1,f 1,f 1′) 代替(x 0,f 0,f 0′) 转步骤2继续迭代 例1:用牛顿法求下面方程的根 解 因 ,所以迭代公式为 选

取 ,计算结果列于下表

n 1 2 3 4 x n

1.411764706

1.369336471

1.368808189

1.368808108

从计算结果可以看出,牛顿法的收敛速度是很快的,进行了四次迭代就得到了较满意的结果.

例2 计算 的近似值。 ε=10-6 x0=0.88

解： 令x= 问题转化为求?(x)= x2-0.78265=0的正根 0.782650.78265

32()21020

f x x x x =++-2()3410f x x x '=++3221(21020)/(3410)

n n n n n n n x x x x x x x +=-++-++01x =

由牛顿迭代公式

xk+1= xk-?(xk)/?'(xk)= xk/2+0.78265/2x k

迭代结果

k 0 1 2 3 xk 0.880000 0.884688 0.884675 0.884675 满足了精度要求 =0.884675

简化牛顿法与牛顿下山法：

牛顿法的优点是收敛块，缺点是每步迭代要计算f(x

k )和f′(x

k

),计算量较大且

有时f′(x

k )计算较困难；二是初始近似x

指在根x*附近才能保证收敛，如x

给

的不合适可能不收敛

简化牛顿法也称平行弦法，其迭代公式为x

k+1=x

k

-Cf(x

k

),C≠0,k=0,1,….

迭代函数ψ(x)=x-Cf(x).

若|ψ′(x)|=|1-Cf′(x)|<1,及取0

（二）、非线性方程，就是因变量与自变量之间的关系不是线性的关系，这类方程很多，例如平方关系、对数关系、指数关系、三角函数关系等等。求解此类方程往往很难得到精确解，经常需要求近似解问题。相应的求近似解的方法也逐渐得到大家的重视。

非线性方程的求解:

如何求解第一类多项式方程，现在已经有了比较成熟的理论和方法。现在比较常用的一种数值方法是迭代法，他能够通过迭代次数的增加，而越来越接近方程的解。至于如何求解第二类非多项式方程，是现在数学领域中的一个重点研究方向。一般来说，求解此类方程是采用随机搜索的办法。

0.78265

(三)、牛顿法解非线性方程牛顿法的基本计算步骤：

步骤1 准备选定初始近似值x

0,计算f

=f(x

),f

′=f′(x

)

步骤2 迭代按公式x

1=x

=

- f

/f

′迭代一次，得新的近似值x

1

，计算f

1

=f(x

1

),f

1

′

=f′(x

1

)

步骤3 控制如果x

1满足|δ|＜ε

1

或 |f

1

|＜ε

2

,则终止迭代，以x

1

作为所求的

根；否则转步骤4.此处ε

1,ε

2

是允许误差，而

|x

1-x

| ，当|x

1

|＜ C时

δ=

|x

1-x

|/|x

1

|,当|x

1

|≥C时，

其中C是取绝对误差和相对误差的控制常数，一般可取C=1.

步骤4 修改如果迭代达到预先指定的次数N，或者f

1

′=0,则方程失败；否则以

(x

1,f

1

,f

1

′) 代替(x

,f

,f

′) 转步骤2继续迭代

例用Newton法求解方程f(x)=x3+3x-1的正根解：次方程仅有[0,1]区间的唯一的正根，利用迭代公式有x k+1=x k-f(x)/f′(x)=2x k3+1/3x k2+3

给定初值x0=0 计算结果如表所示

表

k x k

0 1 2 3 4 0.000 000 000 0.333 333 333 0.322 222 222 0.322 185 355 0.322 185 355

迭代3次所得x3 已具有9位精确的有效数字，由此可见，Newton法比对分法收敛速度快得多。

附：牛顿迭代法的matlab语言代码：

matlab代码

1.定义函数

function y=f(x)

y=f(x)；%函数f(x)的表达式

function y=z(x)

y=z(x)；%函数z(x)的表达式

2.主程序

x=X；%迭代初值

i=0；%迭代次数计算

while i<= I；%迭代次数

y=x-y(x)/z(x)；%牛顿迭代格式

if abs(y-x)>ε；%收敛判断

x=y；

else break

end

i=i+1；

end

fprintf('\n%s%.4f\t%s%d'，'x='，x，'i='，i) %输出结果（四）非线性方程组

非线性方程组是非线性科学的重要组成部分

考虑方程组

f

1(x

1,

,x

2,

,…,x

n

)=0

f

2(x

1,

,x

2,

,…,x

n

)=0

┊

f

n (x

1,

,x

2,

,…,x

n

)=0

其中f

1,f

2

,…,f

n

均为(x

1

,x

2

,…,x

n

)的多元函数.若用向量记号记x=

(x

1,,x

2,

,…,x

n

)T∈R n,F=(f1,f2,…,f n)T,方程组就可以写成F(x)=0.

当n≥2，且f

i (i=1,2,…,n)中至少有一个是自变量x

i

(i=1,2,…,n)的非线性函

数时则称方程组为非线性方程组

在matlab7.0语言中，使用fsolve来求解非线性方程组f(x)=0,其中f和x可以是向量或者矩阵。其使用方法如下

◆x=fslove(fun,x0)命令以x0为初始矩阵来求解方程fun，fun接受输入量x 并返回一个向量（矩阵），使得f=fun(x)。

◆x=fsolve(fun,x0,options)命令以options为选择参数的输入变量

◆x=fsolcve(fun,x0,options,p1,p1,…)命令将问题定性参数p1,p2,p3等直接赋值给函数fun(x,p1,p2,p3,…).而当options为默认值时，该命令返回一个空矩阵

◆[x,feval]=fsolve(fun,x0,…)命令返回客观方程在x处的值

◆[x,feval,exitflag]=fsolve(fun,x0)命令返回一个描述fsolve溢出情况的字符串exitflag

当exitflag>0时，fsolve的解收敛到x

当exitflag=0时，将取得方程的最大解数

当exitflag<0时,fsolve的解在x处不收敛

◆[x,feval,exitflag，output，jacob]=fsolve(fun,x0,…)命令返回函数fun 在x处的jacobian解

四、用牛顿迭代法解非线性方程组

和非线性方程的情况一样，牛顿迭代法也是求解非线性方程组的一种方法，求解非线性方程组的牛顿迭代公式为

x(k+1)=x(k)-[DF(x(k))]-1F(x(k)),k=0,1,2…

当n=1的时候上式就化为求解非线性方程的Newton迭代法公式.在实际计算时，并不需要求F(x)的jacobi矩阵的逆阵[DF(x(k))]-1，而是按照下列公式计算

DF(x(k))y(k)=- F(x(k))

x(k+1)=x(k)+y(k)

即由x(k)计算x(k+1)分两步进行，首先通过求解式中第一个方程组借出y（k）,然后代入到第二个式子中去得到x(k+1)，每迭代一步需求解一个方程组，而方程组

的系数矩阵依赖于x(k)的值，显然是用一系列线性方程组的解去逼近非线性方程组的解

牛顿迭代法解非线性方程组的收敛性和收敛速度

1.局部收敛性：设x*是方程组F(x)=0的解，f i(x)(i=1,2,…,n)在D上均具有连续的偏导数，DF(x*)非奇异，则存在S r=｛x|‖x-x*‖

2.收敛速度：设x*是方程组F(x)=0的解，f i(x)(i=1,2,…,n)在D上均具有连续的偏导数，DF(x*)非奇异，并且对任意x∈D,存在常数L，有下式成立：‖DF(x)- DF(x*)‖≤L‖x-x*‖

则存在开球S r=｛x|‖x-x*‖

‖x(k+1)-x*‖≤C‖x(k)- x*‖2

例用牛顿法解非线性方程组

f1(x1,x2)=x12-20x1+x2+40=0

f2(x1,x2)=x22-20x2+x1+40=0

解： 2x1-20 1

DF(x)=

12x2-20

Newton法的计算公式为

(2x1(k)-20)y1(k)+ y2(k)=-[(x1(k))-20x1(k)+x2(k)+40]

y1(k)+ (2x2(k)-20)y2(k)=-[(x2(k))-20x2(k)+x1(k)+40]

x1(k+1)= x1(k)+ y1(k)

x2(k+1) = x2(k)+ y2(k)

去初值x1(0)= x2(0)=0，利用上边迭代公式计算结果如表所示

表

k

x1(k)X2(k)y1(k)y1(k)

0 1 2 3 4 5 0.000 000 000

2.055 137 845

2.326 203 880

2.331 035 068

2.331 035 597

2.331 035 597

0.000 000 000

1.102 756 892

1.186 329 904

1.187 000 205

1.187 000 318

1.187 000 318

2.055 137 845

0.271 066 035

0.004 831 188

0.000 001 526

-4.2234×10-10

1.102 756 892

0.083 573 102

0.000 670 301

0.000 000 113

-4.7784×10-10

有上面计算结果来看，Newton法收敛很快但是Newton法每迭代一次就需要计算

n2+n个函数值，并且还要做O(n3)次算术运算，计算量十分大，和非线性方程情况一样，可对newton法进行修正，比如可用常矩阵近似代替DF(x（k）),就是一

种修正方案，这样做可以达到减少函数值的计算，但是计算量的减小是以牺牲收敛速度为代价的

五、课题的优缺点以及展望

1、优点：牛顿迭代法具有平方收敛的速度，所以在迭代过程中只要迭代几次就会得到很精确的解。这是牛顿迭代法比简单迭代法优越的地方。

缺点：尽管牛顿迭代法是一种经典的求解非线性方程组的方法，但是在牛顿迭代法中每步迭代都需要计算雅可比矩阵及其逆或解线性的牛顿方程组，当自变

量个数比较多时，其计算量是非常大的，而且当牛顿迭代法中的DF(x（k）)奇异

或病态时，迭代过程无法进行或虽能进行但难以得到较好的数值解．特别是当

x(k)远离方程组的解x*时，用直接消去法高精度地求解牛顿方程组得到的迭代点，往往有不小的盲目性，有时甚至无法迭代，得不到方程组的解

2、展望：利用一些矩阵代替DF(x（k）),从而改进Newton法解线性方程组的缺点，使得收敛速度不慢，计算量相对不大

六、参考文献

[1]李庆扬、王能超、易大义数值分析（第五版）北京清华大学出版社

[2] 刘长安数值分析教程 [O] 西安工业大学出版社

[3] 孙祥、徐流美、吴清 matlab7.0基础教程 [TP] 北京清华大学出版社