上一页 下一页1
第七章 非线性方程的数值解法上一页 下一页2
§ 1 二分法求 f (x) = 0 的根原理,若 f?C[a,b]，且 f (a) · f (b) < 0，则 f 在 (a,b) 上必有一根。
上一页 下一页3
§ 0 多项式基础
§ 1 二分法求 f (x) = 0 的根原理,若 f?C[a,b]，且 f (a) · f (b) < 0，则 f 在 (a,b) 上必有一根。
上一页 下一页4
a
b
x1
x2
a
b
什么时候停止?
11 εxx kk 2)( εxf?或不能保证 x 的精度
x*
2
xx*
上一页 下一页5
误差 分析：
第 1步产生的 21 bax 有误差
21
abx*||x
第 k 步产生的 xk 有误差 kk abx*||x 2
对于给定的精度?,可估计二分法所需的步数 k,
2ln
lnln
2
εabkεab
k
① 简单 ;
② 对 f (x) 要求不高 (只要连续即可 ),
① 无法求复根及偶重根
② 收敛慢注,用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将 [a,b]分为若干小区间，对每一个满足 f (ak)·f (bk) < 0 的区间调用二分法程序，可找出区间 [a,b]内的多个根，且不必要求 f (a)·f (b) < 0 。
上一页 下一页6
§ 2 迭代法
f (x) = 0 x = g (x)
等价变换
f (x) 的根 g (x) 的不动点思路从一个初值 x0 出发，计算 x1 = g(x0),x2 = g(x1),…,
xk+1 = g(xk),… 若 收敛，即存在 x* 使得
，且 g 连续，则由 可知 x* = g(x* )，即 x* 是 g 的不动点，也就是 f 的根。
0kkx
*lim xx kk
kkkk xgx l i ml i m 1
上一页 下一页7
x
y y = x
x
y y = x
x
y y = x
x
y y = x
x* x*
x* x*
y=g(x)
y=g(x)
y=g(x) y=g(x)
x0
p0
x1
p1
x0
p0
x1
p1
x0
p0
x1
p1
x0
p0
x1
p1
上一页 下一页8
定理 考虑方程 x = g(x),g(x)?C[a,b],若
( I ) 当 x?[a,b] 时,g(x)?[a,b]；
( II )? 0? L < 1 使得 | g’(x) |? L < 1 对? x?[a,b] 成立。
则任取 x0?[a,b]，由 xk+1 = g(xk) 得到的序列 收敛于 g(x) 在 [a,b]上的唯一不动点。并且有误差估计式：
0kkx
||1 1|*| 1 kkk xxLxx
||
1|*| 01 xxL
Lxx
k
( k = 1,2,… )
且存在极限*
*
*lim 1 xg
xx
xx
k
k
k
k
上一页 下一页9
证明,① g(x) 在 [a,b]上存在不动点？
令 xxgxf )()( bxga )(?
,0)()( aagaf 0)()( bbgbf
)( xf? 有根
② 不动点唯一？
反证：若不然，设还有,则)~(~ xgx?
),~*()()~(*)( xxξgxgxg xx* ~ 在 和 之间。 *x x~
0))(1)(~( ξgxx* 而 xxξg ~*1|)(|
③ 当 k 时,xk 收敛到 x*？
|*| kxx |*||)(||)(*)(| 111 kkk xxξgxgxg
0|*|......|*| 01 xxLxxL kk
上一页 下一页10
④?||
1
1|*|
1 kkk xxLxx
|*||*||*||*||| 11 kkkkkk xxLxxxxxxxx
||1|*| 01 xxLLxx
k
k
⑤
||.,,,,,||
|))((||)()(|||
011
111
xxLxxL
xxξgxgxgxx
k
kk
kkkkkkk
***lim 1 xgxx xx
k
k
k
⑥
*)(* )*)((l i m**l i m 1 xgxx xxξgxx xx
k
kk
kk
k
k
可用 来控制收敛精度
|| 1 kk xx
L 越 收敛越快小注,定理条件非必要条件，可将 [a,b]缩小，定义 局部收敛性,
若 g(x)在 x* 的某?邻 域 B? = { x | | x? x* | } 内连续可微且 | g’(x*) | < 1,则由?x0?B?开始的迭代收敛。即 调整初值可得到收敛的结果。
上一页 下一页11
算法,简单迭代法给定初始近似值 x0,求 x = g(x)的解,
Input,初始近似值 x0; 误差容限 TOL; 最大迭代次数 Nmax.
Output,近似解 x 或失败信息,
Step 1 Set i = 1;
Step 2 While ( i? Nmax) do steps 3-6
Step 3 Set x = g(x0); /* 计算 xi */
Step 4 If | x? x0 | < TOL then Output (x); /* 成功 */
STOP;
Step 5 Set i ++;
Step 6 Set x0 = x ; /* 更新 x0 */
Step 7 Output (The method failed after Nmax iterations); /* 失败！ */
STOP.
当 x 很大时，此处可改为 T O L
x
xx 0
上一页 下一页12
例,用迭代法求方程 在 内的实根。取
032 24 xxx ]2.1,1[
.10?x
解,对方程进行如下三种变形：
32)(1 241 xxxx?、
建立迭代格式：
),1,0(,32)( 2411 nxxxx nnnn?
743 10495307.8,96 xx
这是一个发散的迭代格式。
上一页 下一页13
4
12
2 )23()(,2 xxxx
建立迭代格式：
),1,0(,)23()( 4/1221 nxxxx nnnn?
,1 2 4 1 2 3.12726 xx 该迭代格式收敛。
14)(,3 3 xxx?
建立迭代格式：
),1,0(,14)(31 nxxx nnn?
1 2 4 1 2 3.176 xx 该迭代格式收敛。
上一页 下一页14
例,用迭代法求方程 在 内的实根。取
032 24 xxx ]2.1,1[
.10?x
解：对方程进行如下三种变形：
32)(1 241 xxxx?、
理论分析：
由上述定理知，迭代格式发散，和计算结果吻合 。
18|44||)(| 131 Lxxx?
4
12
2 )23()(,2 xxxx
理论分析：
由定理知，迭代格式收敛，和计算结果吻合。
187.0)2.1213(4 12.14)23(4 |14||)(| 24/324/322 Lxx xx?
上一页 下一页15
14)(,3 3 xxx?
理论分析：
由定理知，迭代格式收敛，和计算结果吻合。
411414
1
4144
1|)(|
2 xxx?
111.0 3 L
而且，,由（ 5）式知，②和③都收敛，但③
收敛的效果比②好。
23 LL?
上一页 下一页16
例 求 01s i n9 2 xx 在 [0,1]内的一个实根,
将方程化为等价方程,3/1s i n)( xxx?
因为,1)(0 x? 此时定理 1中的条件（ 1）成立，又
,11s in6/c o s)( xxx?
所以定理 1中条件（ 2）也成立，对于 [0,1]中任意初值，迭代序列 }{ nx
,2,1,3 1s i n 1 nxx nn
收敛，计算结果如下表，取,4.00?x
上一页 下一页17
表 7.2
.3 91 84 6 91.0
注,方程 也可化为等价方程 01s i n9 2 xx
)19a r cs i n ( 2 xx
但此时定理、推论条件不成立，迭代序列不能保证收敛。
上一页 下一页18
改进、加速收敛
待定参数法：
若 | g’(x) |? 1,则将 x = g(x) 等价地改造为
)()()1()( xxKgxKxKgKxxx
1|)(1||)(| xgKKx?求 K，使得例,求 在 (1,2) 的实根。013)( 3 xxxf
)()1(31 3 xgxx如果用 进行迭代，则在 (1,2)中有
1|||)(| 2 xxg现令
)1(3)1()()1()( 3 xKxKxKgxKx?
希望 1|1||)(| 2 KxKx? 0
1
2
2
K
x
，即在 (1,2) 上可取任意,例如 K =?0.5,则对应 即产生收敛序列。
032 K
)1(6123 3 xxx
21
上一页 下一页19
定义 若存在根 的邻域? ],[),(S
),,(0Sx使对 迭代法均收敛，
, nn x记如果存在实数 )1(?pp 和非零常数,有c
)(|| || 1 ncp
n
n
则称序列 是阶 收敛的，}{ nx p
p相应的迭代方法称为 阶收敛方法,
局部收敛,
则称此迭代法定义 设迭代序列0}{ nnx 收敛于,?
上一页 下一页20
2
1
10,1
p
p
cp
特别平方收敛超线性收敛线性收敛例 1,1,211 nnn xx
2
1
2
1/
2
1
1
1
nn
n
n
线性收敛,
,2 1,,21,21:1 22 nnyn?~
1)
2
1/(
2
1
~
~ 2
222
1
1
nn
n
n
平方收敛
1,2 11 2 nn yy n例 2：
上一页 下一页21
定理 设,)( 的根是 xx 次可微的邻域于 p )(
),2(?p,0)()( )1( P?又,0)()( p
则只要初始值 选得充分接近0x,? 迭代方法
)0(),(1 nxx nn?
阶收敛，p
!/)()(lim )(1 pxx Pp
n
n
n
且有上一页 下一页22
§ 3 牛顿法原理,将非线性方程线性化
—— Taylor 展开取 x0? x*,将 f (x)在 x0 做一阶 Taylor展开,
2
0000 )(!2
)())(()()( xxfxxxfxfxf,?在 x0 和 x 之间将 (x*? x0)2 看成高阶小量，则有：
)*)(()(*)(0 000 xxxfxfxf
)(
)(*
0
0
0 xf
xfxx
线性
x
y
x*
x0
)(
)(
1
k
kkk
xf
xfxx
只要 f?C1，每一步迭代都有
f ’( xk )? 0,而且,
则 x*就是 f 的根。 *lim xx kk
上一页 下一页23
定理 （ 收敛的充分条件 ）设 f?C2[a,b]，若
(1) f (a) f (b) < 0； (2) 在整个 [a,b]上 f,不变号且 f ’(x)? 0；
(3) 选取 x0? [a,b] 使得 f (x0) f,(x0) > 0；
则 Newton方法产生的序列 { xk } 收敛到 f (x) 在 [a,b] 的唯一根。
有根 根唯一产生的序列单调有界，保证收敛。
定理 （ 局部收敛性 ）设 f?C2[a,b]，若 x* 为 f (x) 在 [a,b]
上的根，且 f ’(x*)? 0，则存在 x* 的邻域 使得任取初值,Newton方法产生的序列 { xk } 收敛到 x*，且满足
*)(xB?
*)(0 xBx
*)(2
*)(
)*(
*lim
2
1
xf
xf
xx
xx
k
k
k?
上一页 下一页24
证明,Newton迭代法 事实上是一种特殊的不动点迭代其中,则
)(
)()(
xf
xfxxg
10*)( *)(*)(*)( 2 xf xfxfxg
收敛由 Taylor 展开：
2)*(
!2
)()*)(()(*)(0
kkkkk xx
fxxxfxfxf
2)*(
)(!2
)(
)(
)(*
k
k
k
k
k
k xxxf
f
xf
xfxx?
1?kx
)(2
)(
)*(
*
2
1
k
k
k
k
xf
f
xx
xx
只要 f ’(x*)? 0，则令可得结论。
k
在 单根 附近收敛快
上一页 下一页25
注,Newton’迭代法的 收敛性依赖于 x0的选取。
x*
x0?x0? x0
上一页 下一页26
例 1
用 Newton法求方程 的根,要求20xxe
51| | 1 0kkxx
1 l n ( 2 )kkxx迭代格式一：
迭代格式二：
1
2
1
k
k
x
k
kk x
xexx
e?
格式一,迭代次数 27,数值解 0.442852706
格式二,迭代次数 3,数值解 0.442854401
上一页 下一页27
例 2
求函数 的正实根精度要求：
32 1 0 1 9,6 8 1 0,9 4 4f x x x x
610
从图形中我们可以看出：
在 x=7和 x=8 之间有一单根；
在 x=1和 x=2 之间有一重根。
上一页 下一页28
初值 x0＝ 8.0 时,计算的是单根,
迭代次数为 28,数值解为 7.600001481
初值 x0＝ 1.0 时,计算的是重根,
迭代次数为 1356,数值解为 1.198631981
取初值 x0＝ 8.0,用牛顿迭代公式计算如下：
取初值 x0＝ 1.0,用牛顿迭代公式计算如下：
上一页 下一页29
改进与推广
重根加速收敛法：
Q1,若,Newton迭代法 是否仍收敛？0*)( xf
设 x* 是 f 的 n 重根，则,且 )(*)()( xqxxxf n 0*)(?xq
因为 Newton迭代法 事实上是一种特殊的不动点迭代，
其中,则
)(
)()(
xf
xfxxg
| ( * ) |gx111
n
A1,有局部收敛性，但重数 n 越高，收敛越慢。
Q2,如何加速重根的收敛？
A2,将求 f 的重根转化为求另一函数的单根。
令,则 f 的重根 =? 的单根。
)(
)()(
xf
xfx
上一页 下一页30
割线法,
Newton迭代法 一步要计算 f 和 f ’，相当于 2个函数值，
比较费时。现用 f 的值近似 f ’，可少算一个函数值。
x0x1
切线割线切线斜率? 割线斜率
1
1 )()()(
kk
kk
k xx
xfxfxf
)()(
))((
1
1
1
kk
kkk
kk xfxf
xxxfxx 需要 2个初值 x0 和 x1。
收敛比 Newton迭代法 慢，
且对初值要求同样高。
上一页 下一页31
下山法
—— Newton迭代法的 局部微调：
原理,若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1
之间找一个更好的点,使得 。
1?kx )()( 1 kk xfxf
xk xk+1
,)1(1 kk xx ]1,0[
)(
)(
)1(]
)(
)(
[1
k
k
k
k
k
k
kk
xf
xf
x
x
xf
xf
xx
注,? = 1 时就是 Newton迭代公式。
当? = 1 代入效果不好时，将?减半计算。
上一页 下一页32
求复根
—— Newton 公式中的自变量可以是复数记 z = x + i y,z0 为初值，同样有
)(
)(
1
k
kkk
zf
zfzz
kkkkkk DiCzfBiAzf )(,)(
设代入公式，令实、虚部对应相等,可得;221
kk
kkkk
kk DC
DBCAxx
.221
kk
kkkk
kk DC
CBDAyy
上一页 下一页33
§ 4 解非线性方程组的牛顿法
1 1 2
2 1 2
12
(,,) 0
(,,) 0
(,,) 0
n
n
nn
f x x x
f x x x
f x x x
( ) 0Fx?记 为,
将非线性方程组线性化，得到：
上一页 下一页34
其中 F?(xk)为 F(x)在 xk处的 Jacobi矩阵：
1 1 1
12
2 2 2
12
12
()
n
n
n n n
n
f f f
x x x
f f f
x x xFx
f f f
x x x
11 ( ) ( )k k k kx x F x F x＝
上一页 下一页35
2
22
1
( ) 2
3
xy
x y z
F x x y z y x
e z e
2
( ) 2
1
xy
y x z
F x y z x z y x z
ee
2
22
1
2
3
xy
x y z
x y z y x
e z e
例：用牛顿法解方程组上一页 下一页36
取初始值（ 1,1,1），计算如下
N x y z
0 1.0000000 1.0000000 1.00000000
1 2.1893260 1.5984751 1.3939006
2 1.8505896 1.4442514 1.2782240
3 1.7801611 1.4244359 1.2392924
4 1.7776747 1.4239609 1.2374738
5 1.7776719 1.4239605 1.2374711
6 1.7776719 1.4239605 1.2374711
第七章 非线性方程的数值解法上一页 下一页2
§ 1 二分法求 f (x) = 0 的根原理,若 f?C[a,b]，且 f (a) · f (b) < 0，则 f 在 (a,b) 上必有一根。
上一页 下一页3
§ 0 多项式基础
§ 1 二分法求 f (x) = 0 的根原理,若 f?C[a,b]，且 f (a) · f (b) < 0，则 f 在 (a,b) 上必有一根。
上一页 下一页4
a
b
x1
x2
a
b
什么时候停止?
11 εxx kk 2)( εxf?或不能保证 x 的精度
x*
2
xx*
上一页 下一页5
误差 分析：
第 1步产生的 21 bax 有误差
21
abx*||x
第 k 步产生的 xk 有误差 kk abx*||x 2
对于给定的精度?,可估计二分法所需的步数 k,
2ln
lnln
2
εabkεab
k
① 简单 ;
② 对 f (x) 要求不高 (只要连续即可 ),
① 无法求复根及偶重根
② 收敛慢注,用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序，将 [a,b]分为若干小区间，对每一个满足 f (ak)·f (bk) < 0 的区间调用二分法程序，可找出区间 [a,b]内的多个根，且不必要求 f (a)·f (b) < 0 。
上一页 下一页6
§ 2 迭代法
f (x) = 0 x = g (x)
等价变换
f (x) 的根 g (x) 的不动点思路从一个初值 x0 出发，计算 x1 = g(x0),x2 = g(x1),…,
xk+1 = g(xk),… 若 收敛，即存在 x* 使得
，且 g 连续，则由 可知 x* = g(x* )，即 x* 是 g 的不动点，也就是 f 的根。
0kkx
*lim xx kk
kkkk xgx l i ml i m 1
上一页 下一页7
x
y y = x
x
y y = x
x
y y = x
x
y y = x
x* x*
x* x*
y=g(x)
y=g(x)
y=g(x) y=g(x)
x0
p0
x1
p1
x0
p0
x1
p1
x0
p0
x1
p1
x0
p0
x1
p1
上一页 下一页8
定理 考虑方程 x = g(x),g(x)?C[a,b],若
( I ) 当 x?[a,b] 时,g(x)?[a,b]；
( II )? 0? L < 1 使得 | g’(x) |? L < 1 对? x?[a,b] 成立。
则任取 x0?[a,b]，由 xk+1 = g(xk) 得到的序列 收敛于 g(x) 在 [a,b]上的唯一不动点。并且有误差估计式：
0kkx
||1 1|*| 1 kkk xxLxx
||
1|*| 01 xxL
Lxx
k
( k = 1,2,… )
且存在极限*
*
*lim 1 xg
xx
xx
k
k
k
k
上一页 下一页9
证明,① g(x) 在 [a,b]上存在不动点？
令 xxgxf )()( bxga )(?
,0)()( aagaf 0)()( bbgbf
)( xf? 有根
② 不动点唯一？
反证：若不然，设还有,则)~(~ xgx?
),~*()()~(*)( xxξgxgxg xx* ~ 在 和 之间。 *x x~
0))(1)(~( ξgxx* 而 xxξg ~*1|)(|
③ 当 k 时,xk 收敛到 x*？
|*| kxx |*||)(||)(*)(| 111 kkk xxξgxgxg
0|*|......|*| 01 xxLxxL kk
上一页 下一页10
④?||
1
1|*|
1 kkk xxLxx
|*||*||*||*||| 11 kkkkkk xxLxxxxxxxx
||1|*| 01 xxLLxx
k
k
⑤
||.,,,,,||
|))((||)()(|||
011
111
xxLxxL
xxξgxgxgxx
k
kk
kkkkkkk
***lim 1 xgxx xx
k
k
k
⑥
*)(* )*)((l i m**l i m 1 xgxx xxξgxx xx
k
kk
kk
k
k
可用 来控制收敛精度
|| 1 kk xx
L 越 收敛越快小注,定理条件非必要条件，可将 [a,b]缩小，定义 局部收敛性,
若 g(x)在 x* 的某?邻 域 B? = { x | | x? x* | } 内连续可微且 | g’(x*) | < 1,则由?x0?B?开始的迭代收敛。即 调整初值可得到收敛的结果。
上一页 下一页11
算法,简单迭代法给定初始近似值 x0,求 x = g(x)的解,
Input,初始近似值 x0; 误差容限 TOL; 最大迭代次数 Nmax.
Output,近似解 x 或失败信息,
Step 1 Set i = 1;
Step 2 While ( i? Nmax) do steps 3-6
Step 3 Set x = g(x0); /* 计算 xi */
Step 4 If | x? x0 | < TOL then Output (x); /* 成功 */
STOP;
Step 5 Set i ++;
Step 6 Set x0 = x ; /* 更新 x0 */
Step 7 Output (The method failed after Nmax iterations); /* 失败！ */
STOP.
当 x 很大时，此处可改为 T O L
x
xx 0
上一页 下一页12
例,用迭代法求方程 在 内的实根。取
032 24 xxx ]2.1,1[
.10?x
解,对方程进行如下三种变形：
32)(1 241 xxxx?、
建立迭代格式：
),1,0(,32)( 2411 nxxxx nnnn?
743 10495307.8,96 xx
这是一个发散的迭代格式。
上一页 下一页13
4
12
2 )23()(,2 xxxx
建立迭代格式：
),1,0(,)23()( 4/1221 nxxxx nnnn?
,1 2 4 1 2 3.12726 xx 该迭代格式收敛。
14)(,3 3 xxx?
建立迭代格式：
),1,0(,14)(31 nxxx nnn?
1 2 4 1 2 3.176 xx 该迭代格式收敛。
上一页 下一页14
例,用迭代法求方程 在 内的实根。取
032 24 xxx ]2.1,1[
.10?x
解：对方程进行如下三种变形：
32)(1 241 xxxx?、
理论分析：
由上述定理知，迭代格式发散，和计算结果吻合 。
18|44||)(| 131 Lxxx?
4
12
2 )23()(,2 xxxx
理论分析：
由定理知，迭代格式收敛，和计算结果吻合。
187.0)2.1213(4 12.14)23(4 |14||)(| 24/324/322 Lxx xx?
上一页 下一页15
14)(,3 3 xxx?
理论分析：
由定理知，迭代格式收敛，和计算结果吻合。
411414
1
4144
1|)(|
2 xxx?
111.0 3 L
而且，,由（ 5）式知，②和③都收敛，但③
收敛的效果比②好。
23 LL?
上一页 下一页16
例 求 01s i n9 2 xx 在 [0,1]内的一个实根,
将方程化为等价方程,3/1s i n)( xxx?
因为,1)(0 x? 此时定理 1中的条件（ 1）成立，又
,11s in6/c o s)( xxx?
所以定理 1中条件（ 2）也成立，对于 [0,1]中任意初值，迭代序列 }{ nx
,2,1,3 1s i n 1 nxx nn
收敛，计算结果如下表，取,4.00?x
上一页 下一页17
表 7.2
.3 91 84 6 91.0
注,方程 也可化为等价方程 01s i n9 2 xx
)19a r cs i n ( 2 xx
但此时定理、推论条件不成立，迭代序列不能保证收敛。
上一页 下一页18
改进、加速收敛
待定参数法：
若 | g’(x) |? 1,则将 x = g(x) 等价地改造为
)()()1()( xxKgxKxKgKxxx
1|)(1||)(| xgKKx?求 K，使得例,求 在 (1,2) 的实根。013)( 3 xxxf
)()1(31 3 xgxx如果用 进行迭代，则在 (1,2)中有
1|||)(| 2 xxg现令
)1(3)1()()1()( 3 xKxKxKgxKx?
希望 1|1||)(| 2 KxKx? 0
1
2
2
K
x
，即在 (1,2) 上可取任意,例如 K =?0.5,则对应 即产生收敛序列。
032 K
)1(6123 3 xxx
21
上一页 下一页19
定义 若存在根 的邻域? ],[),(S
),,(0Sx使对 迭代法均收敛，
, nn x记如果存在实数 )1(?pp 和非零常数,有c
)(|| || 1 ncp
n
n
则称序列 是阶 收敛的，}{ nx p
p相应的迭代方法称为 阶收敛方法,
局部收敛,
则称此迭代法定义 设迭代序列0}{ nnx 收敛于,?
上一页 下一页20
2
1
10,1
p
p
cp
特别平方收敛超线性收敛线性收敛例 1,1,211 nnn xx
2
1
2
1/
2
1
1
1
nn
n
n
线性收敛,
,2 1,,21,21:1 22 nnyn?~
1)
2
1/(
2
1
~
~ 2
222
1
1
nn
n
n
平方收敛
1,2 11 2 nn yy n例 2：
上一页 下一页21
定理 设,)( 的根是 xx 次可微的邻域于 p )(
),2(?p,0)()( )1( P?又,0)()( p
则只要初始值 选得充分接近0x,? 迭代方法
)0(),(1 nxx nn?
阶收敛，p
!/)()(lim )(1 pxx Pp
n
n
n
且有上一页 下一页22
§ 3 牛顿法原理,将非线性方程线性化
—— Taylor 展开取 x0? x*,将 f (x)在 x0 做一阶 Taylor展开,
2
0000 )(!2
)())(()()( xxfxxxfxfxf,?在 x0 和 x 之间将 (x*? x0)2 看成高阶小量，则有：
)*)(()(*)(0 000 xxxfxfxf
)(
)(*
0
0
0 xf
xfxx
线性
x
y
x*
x0
)(
)(
1
k
kkk
xf
xfxx
只要 f?C1，每一步迭代都有
f ’( xk )? 0,而且,
则 x*就是 f 的根。 *lim xx kk
上一页 下一页23
定理 （ 收敛的充分条件 ）设 f?C2[a,b]，若
(1) f (a) f (b) < 0； (2) 在整个 [a,b]上 f,不变号且 f ’(x)? 0；
(3) 选取 x0? [a,b] 使得 f (x0) f,(x0) > 0；
则 Newton方法产生的序列 { xk } 收敛到 f (x) 在 [a,b] 的唯一根。
有根 根唯一产生的序列单调有界，保证收敛。
定理 （ 局部收敛性 ）设 f?C2[a,b]，若 x* 为 f (x) 在 [a,b]
上的根，且 f ’(x*)? 0，则存在 x* 的邻域 使得任取初值,Newton方法产生的序列 { xk } 收敛到 x*，且满足
*)(xB?
*)(0 xBx
*)(2
*)(
)*(
*lim
2
1
xf
xf
xx
xx
k
k
k?
上一页 下一页24
证明,Newton迭代法 事实上是一种特殊的不动点迭代其中,则
)(
)()(
xf
xfxxg
10*)( *)(*)(*)( 2 xf xfxfxg
收敛由 Taylor 展开：
2)*(
!2
)()*)(()(*)(0
kkkkk xx
fxxxfxfxf
2)*(
)(!2
)(
)(
)(*
k
k
k
k
k
k xxxf
f
xf
xfxx?
1?kx
)(2
)(
)*(
*
2
1
k
k
k
k
xf
f
xx
xx
只要 f ’(x*)? 0，则令可得结论。
k
在 单根 附近收敛快
上一页 下一页25
注,Newton’迭代法的 收敛性依赖于 x0的选取。
x*
x0?x0? x0
上一页 下一页26
例 1
用 Newton法求方程 的根,要求20xxe
51| | 1 0kkxx
1 l n ( 2 )kkxx迭代格式一：
迭代格式二：
1
2
1
k
k
x
k
kk x
xexx
e?
格式一,迭代次数 27,数值解 0.442852706
格式二,迭代次数 3,数值解 0.442854401
上一页 下一页27
例 2
求函数 的正实根精度要求：
32 1 0 1 9,6 8 1 0,9 4 4f x x x x
610
从图形中我们可以看出：
在 x=7和 x=8 之间有一单根；
在 x=1和 x=2 之间有一重根。
上一页 下一页28
初值 x0＝ 8.0 时,计算的是单根,
迭代次数为 28,数值解为 7.600001481
初值 x0＝ 1.0 时,计算的是重根,
迭代次数为 1356,数值解为 1.198631981
取初值 x0＝ 8.0,用牛顿迭代公式计算如下：
取初值 x0＝ 1.0,用牛顿迭代公式计算如下：
上一页 下一页29
改进与推广
重根加速收敛法：
Q1,若,Newton迭代法 是否仍收敛？0*)( xf
设 x* 是 f 的 n 重根，则,且 )(*)()( xqxxxf n 0*)(?xq
因为 Newton迭代法 事实上是一种特殊的不动点迭代，
其中,则
)(
)()(
xf
xfxxg
| ( * ) |gx111
n
A1,有局部收敛性，但重数 n 越高，收敛越慢。
Q2,如何加速重根的收敛？
A2,将求 f 的重根转化为求另一函数的单根。
令,则 f 的重根 =? 的单根。
)(
)()(
xf
xfx
上一页 下一页30
割线法,
Newton迭代法 一步要计算 f 和 f ’，相当于 2个函数值，
比较费时。现用 f 的值近似 f ’，可少算一个函数值。
x0x1
切线割线切线斜率? 割线斜率
1
1 )()()(
kk
kk
k xx
xfxfxf
)()(
))((
1
1
1
kk
kkk
kk xfxf
xxxfxx 需要 2个初值 x0 和 x1。
收敛比 Newton迭代法 慢，
且对初值要求同样高。
上一页 下一页31
下山法
—— Newton迭代法的 局部微调：
原理,若由 xk 得到的 xk+1 不能使 | f | 减小，则在 xk 和 xk+1
之间找一个更好的点,使得 。
1?kx )()( 1 kk xfxf
xk xk+1
,)1(1 kk xx ]1,0[
)(
)(
)1(]
)(
)(
[1
k
k
k
k
k
k
kk
xf
xf
x
x
xf
xf
xx
注,? = 1 时就是 Newton迭代公式。
当? = 1 代入效果不好时，将?减半计算。
上一页 下一页32
求复根
—— Newton 公式中的自变量可以是复数记 z = x + i y,z0 为初值，同样有
)(
)(
1
k
kkk
zf
zfzz
kkkkkk DiCzfBiAzf )(,)(
设代入公式，令实、虚部对应相等,可得;221
kk
kkkk
kk DC
DBCAxx
.221
kk
kkkk
kk DC
CBDAyy
上一页 下一页33
§ 4 解非线性方程组的牛顿法
1 1 2
2 1 2
12
(,,) 0
(,,) 0
(,,) 0
n
n
nn
f x x x
f x x x
f x x x
( ) 0Fx?记 为,
将非线性方程组线性化，得到：
上一页 下一页34
其中 F?(xk)为 F(x)在 xk处的 Jacobi矩阵：
1 1 1
12
2 2 2
12
12
()
n
n
n n n
n
f f f
x x x
f f f
x x xFx
f f f
x x x
11 ( ) ( )k k k kx x F x F x＝
上一页 下一页35
2
22
1
( ) 2
3
xy
x y z
F x x y z y x
e z e
2
( ) 2
1
xy
y x z
F x y z x z y x z
ee
2
22
1
2
3
xy
x y z
x y z y x
e z e
例：用牛顿法解方程组上一页 下一页36
取初始值（ 1,1,1），计算如下
N x y z
0 1.0000000 1.0000000 1.00000000
1 2.1893260 1.5984751 1.3939006
2 1.8505896 1.4442514 1.2782240
3 1.7801611 1.4244359 1.2392924
4 1.7776747 1.4239609 1.2374738
5 1.7776719 1.4239605 1.2374711
6 1.7776719 1.4239605 1.2374711
