牛顿迭代法
-
___________________________________________
__________________________________________________
_________________
牛顿迭代法
一、
牛顿迭代法
牛顿迭代法也称为牛顿<
/p>
-
拉夫森
(Newton-Raphso
n)
迭代法，它是数值
分析中最重要的方法之一，
它不仅适用于方程或方程组的求解，
还常
用于微分方
程和积分方程求解。
二、
迭代公式
f
(
x
k
)<
/p>
x
k
1
x
k
,
k
0
,
1
,
2
,...
f
< br>(
x
k
)
用迭代法解非线性方程时，
如何构造迭代函数是非常重要的，
那么怎
样构造的迭代函数才能保证迭代法收敛呢？牛顿迭代法就是常用的
方法之一，
其迭代格式的来源大概有以下几种方式
（主
要是第一种）
：
2
< br>f
(
x
)
C
[
a
,
b
]
，对
f<
/p>
(
x
)
在点
x
0
[
a
,
b
]
作泰勒展开：
1
、设
f
'
'
(
)(
x
x
0
)
2
f
(
x
)
f
(
x
0
)
f
'<
/p>
(
x
0
)(
x
x
0
)
2
!
略去二次项，得到
f
(<
/p>
x
)
的线性近似式：
f
(
x
)
f
(
x
0<
/p>
)
f
'
(
x
0
)(
x
x
0
)
。
由此得到方程
f
(
x
)
0
的近似根
(
假定
f
'
(
x
0
)
0)
，
即可构造出迭代格式
(
假定
f
'
(<
/p>
x
k
)
0)
：
x
k
1
x
k
f
< br>(
x
k
)
f
'
(
x
k
)
x
x
0
f
(
x
0
)
f
'
(
x
0
< br>)
公式
(1)
这就是牛顿迭代公式，若
得到的序列
{
x
k
}
收敛于
，则
< br>
就是非线性
方程的根。
精品资料
__________________________________________________
__________________________________________________
__________
2
、
牛顿迭
代法也称为牛顿切线法，
这是由于
f
(
x
)
的线性化近似函数
l
(
x
)
＝
f
(
x
0
)
f
'<
/p>
(
x
0
)(
x
x
0
)
是曲线
y
＝
f
(
x
)
过点
(
x
0
,
f
(
x
0
))
的切线而得名
的，求
f
(
x
)
的零点代之以求
l
(
x<
/p>
)
的零点，即切
线
l
(
x
)
与
x
轴交点的横坐标，如右图所示，这
就
是牛顿切线法的几何解释。实际上，牛顿
迭代法也可以从几何意义上推出。利用牛顿
迭代公式，由
x
k
得到
x
k
1
，从几何图形上看，就是过点
(
x
k
,
f
(
x
k
))
作函
数
f
(
x
)
的切线
l
k
，
切线
l
k
与
x
轴的交点就是
x
k
1
，
所以有
整理后也能得出牛顿迭代公式：
x
k
1
x
k
f
(
x
k
)
f
'
(
x<
/p>
k
)
f
'
(
x
k
)
f
(
x
k
)
x
k
x
k
1
，
。
3
、
要保证
迭代法收敛，不管非线性方程
f
(
x<
/p>
)
0
的形式如
何，总可
以构造：
x
(
x
)
x
k
(
x
)
f<
/p>
(
x
)
(
k
(
x
)
0
)
作为方程求解的
迭代函数。因为：
'
(
x
)
1
< br>
k
'
(
x
)
f
(
x
)
k
(
x
)
f
'
(
x
)
而且
'
(
x
)
在根
< br>附近越小，其局部收敛速度越快，故可令：
'
(
)
0
若
f
< br>'
(
)
0(
即根
不是
f
(
x
)
0
的重根
)
，
则由
'
(
)
0
得：
因此可令
k
(
x
)
k
(
)
1
f
'
(
)
，
< br>
f
(
x
k
)
1
x
k
1
x
k
f
'
(
x
k
)
f
'
(
x
< br>)
，则也可以得出迭代公式：
。
4
、
迭代法的基本思想是将方程
f
(
x
)
0
改写成等价的迭代形式
精品资料
________________________________________________ __________________________________________________ ____________
x
<
/p>
(
x
)
，
但随之而来的问题却是迭代公式不一定收敛，
或者收敛的速
度较慢。运用前述加速技巧，对于简单迭代过程
x
n
1
x<
/p>
n
f
(
x
n
)
，其加
速公式具有形式：
x
n
1
(
x
n
)
x
n
x
n
1
(
< br>x
n
1
x
n
)
1
1
，其中
x
n
1
(
x
n
)
x
n
< br>1
x
n
f
(
x
n
)
L
记
L
1
，上面两式可以合并写成：
这种迭代公式称作
简单的牛顿公式，其相应的迭代函数是：
(
< br>x
)
x
f
(
x
)
L
。
需要注
意的是，
由于
L
是
'
(
x
)
的估计值，
若取
< br>(
x
)
x
f
(
x
)
，
则
'
(
x
)
实
际上便是
f
'
(
x
)
的估计值。假
设
f
'
(
x<
/p>
)
0
，则可以
用
f
'
(
x<
/p>
)
代替上式中的
L
，就可得到牛顿法的迭代公式：
x
n
1
x
n<
/p>
f
(
x
n
)
f
'
(
x
n
)
。
牛顿迭代法实质上是一种线性化方法，
其基本思想是将非线性方程逐
步归结为某种线性方程来求解。
三、算法描述
用
Newton
法求方程
f
（
x
）
=0
的一个解
输入
<
/p>
初始值
x0
；误差容限
< br>TOL
；最大迭代次数
m
输出
<
/p>
近似解
p
或失败信息
Step1
p
0
x
< br>0
Step2
对
i=1
，
2
，
...
，
m
做
setp3~4
Setp3
p
< br>p
0
f
(
p
0
)
f
(
p
0
)
精品资料
<
/p>
________________________________________
__________________________________________________
____________________
Setp4
Setp5
若
p
< br>
p
0
TOL
，则输出（
p
）
，停机，否则
p
0
p
输出失败信息；停机
注：在第
4
步中的迭代终止准则可用：
p
p
0
< br>p
TOL
< br>或者
p
p
0
p
TOL
且
f
(
p
)
TOL
四、
C
语言代码
求一元四次方程
x
4
3
x
3
1
.
5
x
2
4
0
的解
double
func(double x) //
函数
{
return x*x*x*x-3*x*x*x+1.5*x*x-4.0;
}
double
func1(double x) //
导函数
{
return
4*x*x*x-9*x*x+3*x;
}
int Newton(double *x,double
precision,int maxcyc)
//
初始值，
精度，
迭代次数
{
double x1,x0;
int
k;
x0=*x;
for(k=0;k
{
if(
func1(x0)==0.0)//
若通过初值，函数返回值为
0
{
精品资料
-