牛顿-拉夫森(Newton-Raphson)迭代法
-
§
3.4
牛顿迭代法
牛顿迭代法也称为牛顿<
/p>
-
拉夫森
(Newton-Raphso
n)
迭代法，它是数值分析中最重要的方法
之一，它不仅适用于
方程或方程组的求解，还常用于微分方程和积分方程求解。
3.4.1
牛顿迭代法
用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才< p>
能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方
式：
2
f
(
x
)
C
[
a
,
< br>b
]
，对
f
(
x
)
在点
x
0
[
a
,
b
]
作泰勒
展开：
1
设
2
!
f
(<
/p>
x
)
f
(
x
0
)
f
'
(
x
0
)(
x
< br>
x
0
)
略去二次项，得到
f
(
x
)
的线性近似式：
。
<
/p>
f
'
(
x
0
)
由此得到方程
f
(
x
)
0
的近似根
(<
/p>
假定
0)
，
f<
/p>
'
(
x
k
)
f
(
x
)
f
(
x
0
)
f
'
(
x
0
)(
x
x
0
)
f
'
'
(
)(
x
x
0
)
2
x
x
0
f
(
x
k
)
f
(
x<
/p>
0
)
f
'
(
x
0
)
x
k
1
x
k
即可构造出迭代格式
(
假定
0)
：
x
k
f
'
(
x
k
)
公式
(3.4.1)
这就是牛顿迭代公式，若得到的序列
{
}
收敛于
，则
就是非线性方程的根。
2
牛顿迭代法也称为牛顿切线法，这是由于
f
(
x
)
的线
f
(
x
0
)
f
'
(
x
0
)(
x
x
0
)
性
化
近
似
函
数
l
(
x
)
＝
是
曲
< br>线
y
＝
f
(
x
)
过点
(
x
0
,
f<
/p>
(
x
0
))
的切线而得名的，求
f
(
< br>x
)
的零点代之
以求
l
(
x
)
的零点，即切线
l
(
x
)
与
x
轴交点的横坐
标，如右图
所示，这就是牛顿切线法的几何解释。实际上，牛顿迭代法
< br>也可以从几何意义上推出。利用牛顿迭代公式，由
(
x<
/p>
k
,
f
(
x
k
))
x
k
得到
x
k
1
，从几何图形上看，就是过点
l
l
x
作
函
数
f
(
x
)
的
切
线<
/p>
k
，
切
线
k
与
x
轴
的
交
点
就
是
k
1
，
所
以
有
f
'
(
x
k<
/p>
)
f
(
x
k
)
x
k
x
k
1
，整理后也能得出牛顿迭代公式：
x
k
1
x
k
f
(
x
k<
/p>
)
f
'
(
x
k
)
。
3
要保证迭代法收敛，不管非线性方程
f
(
x
)
0
的形式如何，总可以构造：
< br>
x
(
x
)
x
k
(
x
)
f
(
x
)
(
k
(
x
)
0
)
作为方程求解的迭代
函数。因为：
'
(
< br>x
)
1
k
'
(
x
)
f
(
x
)
k
(
x
)
f
'
(
x
)
< br>而且
'
(
x
)
在根
附近越小，其局部收敛速度越快，故可令：
'
(
)
< br>0
若
f
'
(
)
0(
即根
不
是
f
(
x
)<
/p>
0
的重根
)<
/p>
，则由
'
(<
/p>
)
0
得：
k
(
x
)
1
x
k
1
< br>x
k
k
(
)
1
f
'
(
)
，
f
(
x
k
)
因此可令
f
'
(
x
k
)
。
f
'
(
x
)
，则也可以得出迭代公式：
4
迭代法的基本思想是将方程
f
(
x
)
0
改写成等价的迭代形式
x
(
x
)
，
但随之而来的
问题却是迭代公式不一定收敛，或者收敛的速度较慢。运用前述加速技巧，
对于简单迭代过程
x
n
1
x
n
< br>
f
(
x
n
)
，其加速公式具有形式：
(
x
n
)
x
n
1
< br>
x
n
1
x
n
1
1
(
x
n
1
x
n
)
f
< br>(
x
n
)
L
，其中
x
n
1
(
x
n
)
记
L
1
，上面两式可以合并写成：
x
n
1
x
n
(
x
)
x
f
(
x
)
L
。
这种迭代公式称作简单的牛顿公式，其相应的迭
代函数是：
需要注意的是，由于
L
是<
/p>
'
(
x
)
的估计值，若取
(
x
)
x<
/p>
f
(
x
)
，则
'
(
x
)
实际上便是
f
'
(
x
)
的估计值。假设
f
'
(
x
)
0
，则可以用
f
'
(
x
)
代替上
式中的
L
，就可得到牛顿法的迭代
f<
/p>
'
(
x
n
)
。
公式：
牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方
程来求解。
x
n<
/p>
1
x
n
f
(
x
n
)
3.4.2
牛顿迭代法的收敛性
f
'
(
x
)
< br>而获得的不动点迭代格式。这样就可以应用
牛顿迭代公式可以看成是由
不
动
点
迭
代
的
收
敛
原
则
，
只
须
证
明
在
根<
/p>
附
近
的
迭
代
函
数
是
一
个
压
缩
映
象
。
由
于
：
(
x
)
x<
/p>
f
(
x
)
'
(
x
)
1
[
f
'
(
x
)]
f
(
x
)
f
(
x
)
[
f
'
(
x
)]
2
2
f
(
x
< br>)
f
(
x
)
[
f
'<
/p>
(
x
)]
2
，
0
2
f
(
)
0
f
< br>'
(
)
0
[
f
'
(
)]
这里
的根
是单根，即
且
< br>，于是：
。
那么由
'
(
x
)
的连续性可知，存在一个邻域
(
,
)
，对
这个邻域内的一切
x
，有：
'
(
)
f
(
< br>)
f
(
)
'
(<
/p>
x
)
q
结论：
，其中
O<
/p>
＜
q
＜
1
，因此
(
x
)
为区间
(
,
)
上的一个压缩映象
，于是有以下
2
定理
3.4.1
< br>设
f
(
x
)
C
[
a
,
b
]
，
x
*
是
f
(
x
)
0
的精确解，且
f
'
(
x
*)
0
，则存在
x
*
x
(
x
*
,
x
*
)
{
x
}
的
邻域
(
x
*
,
x
*
)
，对于任何迭代初值
0
，迭代序列
n
收敛于
x
*
。
牛顿迭代法具有较高
的收敛速度，它的
收敛阶数
为
p
＝
2
；而牛顿迭代法的局部收敛性较
强，只有初值充分地接近
x
*
< br>，才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制，
必须再增加条件建
立以下收敛的充分条件。
定理
3.4.2
设
f
(
x
)
C
[
a
,
b<
/p>
]
，且满足：在区间
[
< br>a
,
b
]
上，
⑴
f
(
a
)
f<
/p>
(
b
)
0
；⑵
f
'
(
x
)
0
；
⑶
f
(
x
)
不变号；⑷<
/p>
x
0
[
a
,
b
]
，满足条件：
f
(
x
0
)
f
(
x
0
)
0
则牛顿迭代序列
{
x
n
}
，单调地收敛于方程
f
(
x
)
0<
/p>
的唯一解
x
*
。
由条件⑴至条件⑷可归结为四种情形：
①
f
(
a
)
<
/p>
0
，
f
(
b
)
0
，
f
'
(
x
)
0
，
f
(
x
)
0
；
②
f
(
a
)
0
，
f
(
< br>b
)
0
，
f
'
(
x
)
0
，
f
(
x
)
0
；
③
f
(
a
)
0
，
f
(
b<
/p>
)
0
，
f
'
(
x
)
0
，
f
(
x
)
0
；
④
f
(
a
)
0
，
f
(
b
)
0
，
< br>f
'
(
x
)
0
，
f
(
x
)
0
。
对定理的几何意义作如下说明：条件⑴保证了根的存在性；条件⑵表明函数单调变化，在< p>
区间
[
a
,
b
]
内有惟一的根；条件⑶表示函数图形在区间
[
a
,
b
]
上的凹向不变。条件⑶和条件⑷一
起保证了每
一次迭代值都界于区间
[
a
,
b
]
内。
2
在不满足上述收敛充分条件时，有
可能导致迭代值远离所求根的情况或死循环的情况
(
如
下图所示
)
。