§ 4 牛顿法 /* Newton - Raphson Method */
原理,将非线性方程线性化
—— Taylor 展开 /* Taylor’s expansion */
取 x0? x*,将 f (x)在 x0 做一阶 Taylor展开,
2
0000 )(!2
)())(()()( xxfxxxfxfxf,?在 x0 和 x 之间。
将 (x*? x0)2 看成高阶小量，则有：
)*)(()(*)(0 000 xxxfxfxf
)(
)(*
0
0
0 xf
xfxx
线性 /* linear */
x
y
x*
x0
)(
)(
1
k
kkk
xf
xfxx
只要 f?C1，每一步迭代都有
f ’( xk )? 0,而且,
则 x*就是 f 的根。 *lim xx kk
§ 4 Newton - Raphson Method
定理 （ 收敛的充分条件 ）设 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’s Method产生的序列 { xk } 收敛到 f (x) 在 [a,b] 的唯一根。
有根 根唯一 产生的序列单调有界，保证收敛。定理 （ 局部收敛性 ）设 f?C2[a,b]，若 x* 为 f (x) 在 [a,b]
上的根，且 f ’(x*)? 0，则存在 x* 的邻域 使得任取初值,Newton’s Method产生的序列 { xk } 收敛到 x*，
且满足
*)(xB?
*)(0 xBx
*)(2
*)(
)*(
*lim
2
1
xf
xf
xx
xx
k
k
k?
§ 4 Newton - Raphson Method
证明,Newton’s Method 事实上是一种特殊的不动点迭代其中,则
)(
)()(
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
在 单根 /*simple root */
附近收敛快
§ 4 Newton - Raphson Method
注,Newton’s Method 收敛性依赖于 x0 的选取。
x*
x0?x0? x0
HW,p.27 #3,#4
Excuses for not
doing homework
I have the proof,but there
isn't room to write it in
this margin.
§ 4 Newton - Raphson Method
改进与推广 /* improvement and generalization */
重根 /* multiple root */ 加速收敛法：
Q1,若,Newton’s Method 是否仍收敛？0*)( xf
设 x* 是 f 的 n 重根，则,且 。)(*)()( xqxxxf n 0*)(?xq
因为 Newton’s Method 事实上是一种特殊的不动点迭代，
其中,则
)(
)()(
xf
xfxxg
2
2
*)(
*)(*)(*)(1|*)(|
xf
xfxfxfxg 111
n
A1,有局部收敛性，但重数 n 越高，收敛越慢。
Q2,如何加速重根的收敛？
A2,将求 f 的重根转化为求另一函数的单根。
令,则 f 的重根 =? 的单根。
)(
)()(
xf
xfx
§ 4 Newton - Raphson Method
正割法 /* Secant Method */,
Newton’s Method 一步要计算 f 和 f ’，相当于 2个函数值，
比较费时。现用 f 的值近似 f ’，可少算一个函数值。
x0x1
切线
/* tangent line */
割线
/* secant line */
切线斜率? 割线斜率
1
1 )()()(
kk
kk
k xx
xfxfxf
)()(
))((
1
1
1
kk
kkk
kk xfxf
xxxfxx 需要 2个初值 x0 和 x1。
收敛比 Newton’s Method
慢，且对初值要求同样高。
§ 4 Newton - Raphson Method
下山法 /* Descent Method */
—— Newton’s Method 局部微调：
原理,若由 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’s Method 公式。
当? = 1 代入效果不好时，将?减半计算。
§ 4 Newton - Raphson Method
Algorithm,Newton’s Descent Method
Find a solution to f (x) = 0 given an initial approximation x0.
Input,initial approximation x0; f (x) and f ’(x); minimum step size of xmin;
tolerance TOL1 for x ; tolerance TOL2 for? ; maximum number of
iterations Nmax.
Output,approximate solution x or message of failure.
Step 1 Set k = 1;
Step 2 While ( k? Nmax) do steps 3-10
Step 3 Set? = 1;
Step 4 Set ; /* compute xk */
Step 5 If | x? x0 | < TOL1 then Output (x); STOP; /* successful */
Step 6 If then x0 = x ; GOTO Step 10 ; /* update x0 */
Step 7 Set? =? / 2 ; /* update? to descend */
Step 8 If? > TOL2 then GOTO Step 4 ; /* compute a better xi */
Step 9 Set x0 = x0 + xmin ; /* move forward anyway to avoid deadlock */
Step 10 Set k ++;
Step 11 Output (Method failed after Nmax iterations); STOP,/* unsuccessful */
)(
)(
0
00 xf xfxx
)()( 0xfxf?
计算量未见得减小
§ 4 Newton - Raphson Method
求复根 /* Finding Complex Roots */
—— Newton 公式中的自变量可以是复数记 z = x + i y,z0 为初值，同样有
)(
)(
1
k
kkk
zf
zfzz
kkkkkk DiCzfBiAzf )(,)(
设
HW,p.28 #10
代入公式，令实、虚部对应相等,可得;221
kk
kkkk
kk DC
DBCAxx
.221
kk
kkkk
kk DC
CBDAyy
§ 4 Newton - Raphson Method
Lab 04,Newton’s Method
Use Newton’ s method to approximate the m complex roots of a
given polynomial of degree 5? n? m,,near
m given points to a given accuracy.
Input
There are several sets of inputs,For each set:
The 1st line contains an integer n which is the degree of a
polynomial,n =?1 signals the end of file.
The 2nd line contains n+1 real numbers which are the
coefficients of the polynomial,The numbers are separated by spaces.
The 3rd line contains a real number eps which is the absolute
accuracy bound for each solution.
The 4th line contains an integer n? m? 0,followed by m pairs of
real numbers which correspond to the initial complex
guesses,
0111,..)( cxcxcxcxp nnnn
01..,ccc n
mm baba,..11
mm biabia,,,,,11
§ 4 Newton - Raphson Method
Output (?represents a space)
Each root is to be printed as in the C fprintf:
fprintf(outfile,"%10.5f+%10.5f?i\n",real,imag );
Or,if the imaginary part is negative
fprintf(outfile,"%10.5f?%10.5f?i\n",real,fabs(imag) );
If there is no root found near a given point simply print,no?root\n”
The outputs of two test cases must be seperated by a blank line.
Sample Input
(?represents a space)
4
1?–3?20?44?54
0.0001
1?2.5?4.5
2
1?0?0.9
0.0001
2?0?–1.0?0?1.0
–1
Sample Output
(?represents a space)
2.47064+4.64053?i
0.000000.94868?i
0.00000+0.94868?i
§ 5 迭代法的收敛阶 /* Order of Convergence */
定义 设迭代 xk+1 = g(xk) 收敛到 g(x) 的不动点 x*。
设 ek = xk? x*,若,则称该迭代为 p 阶收敛,
其中 C 称为 渐进误差常数 。 /* { xk } converges to x* of order p,
with asymptotic error constant C > 0 */
0|| ||lim 1 Cee p
k
k
k
一般 Fixed-Point Iteration 有,称为 线性收敛 /* linear convergence */，这时 p = 1,0 < C < 1。
0|*)(||| ||l i m 1 xgee
k
k
k
注,超线性收敛不一定有 p > 1。
例如 xn = 1/nn 超线性收敛到 0，但对任何 p > 1 都没有
p 阶收敛。
Aitken 加速有 。 称为 超线性收敛
/* superlinear convergence */。
0**?l i m xx xx
k
k
k 0||
||lim 1
k
k
k e
e
§ 5 Order of Convergence
Steffensen 加速 有 p = 2，条件是,称为 平方收敛
/* quadratic convergence */。
1*)( xg
Newton’s Method 有,只要,
就有 p? 2。重根是线性收敛的。
*)(2
*)(
||
||l i m
2
1
xf
xf
e
e
k
k
k?
0*)( xf
Q,如何实际确定收敛阶和 渐进误差常数？
定理 设 x* 为 x = g(x) 的不动点,若,p? 2；
，且,则 xk+1 = g(xk) 在内 p 阶收敛。
* ) )(( xBCg p
0*)(...*)( )1( xgxg p 0*)()(?xg p
*)(xB?
证明：
p
k
k
p
kkk xxp
gxxxgxgxgx *)(
!
)(.,,*)* ) ((*)()( )(
1
x* k
C
This is a one line proof...if we
start sufficiently far to the left.
HW,p.29 #1
§ 6 劈因子法 /* Splitting Method */
求多项式的根从 f (x)中分离出一个 2 次因子。即：
)* ) (*(
)(
23
3
1
2
0
2
1
1
10
nn
nn
nn
nn
bxbxbxbvxux
axaxaxaxf
通过 可解出一对共轭复根。 0**2 vxux
思路从一对初值 ( u,v ) 出发，则有
)()()()( 2 sxrxPvxuxxf
其中 ( r,s )取决于 u 和 v，可以看作是 ( u,v )的函数，即
r = r ( u,v ),s = s ( u,v ) 。
目标,r = r ( u*,v* ) = 0,s = s ( u*,v* ) = 0。
§ 6 Splitting Method
将 r 和 s 在初值点 ( u,v )做一阶 Taylor展开，并代入 ( u*,v*)：
)*()*(),(*)*,(0
)*()*(),(*)*,(0
vv
v
s
uu
u
s
vusvus
vv
v
r
uu
u
r
vurvur
从中解出 vvvuuu *,* vvuu,，以 更新
u 和 v 再迭代，直到 r 和 s 充分接近 0。
每步迭代须计算
.,,,,,vsusvrursr
§ 6 Splitting Method
计算 r 和 s,
nnnnnn axaxaxaxaxaxf 12222110,..)(
)()(
)(...)()(
)...)(()(
232
2
432
2
012
1
010
2
2
0
2
svbxrvbub
xvbubbxvbubbxubbxb
srxbxbvuxxxf
nnn
nnn
nnn
n
n
2
321
21
011
00
)2.,,,,3,2(
nn
nnn
iiii
vbas
vbubar
nivbubab
ubab
ab
可记为 bn?1
21 nnnn vbubab若令,则,1 nn ubbs
§ 6 Splitting Method
计算,
v
s
v
r
,
vrxxPvuxx
axaxaxaxf nnnn
)()(
)(
2
1
1
10?
v
sx
v
r
v
PvuxxxPv
f
)()(
0
2
v
sx
v
r
v
PvuxxxP
)()( 2
n?2 阶多项式 n?4 阶多项式与前一步同理，可导出 和 的公式。
v
s
v
r
,
v
P
§ 6 Splitting Method
计算,
u
s
u
r
,
vrxxPvuxx
axaxaxaxf nnnn
)()(
)(
2
1
1
10?
u
sx
u
r
u
PvuxxxxPu
f
)()(
0
2
u
sx
u
r
u
PvuxxxxP
)()( 2
而前一步得到
v
sx
v
r
v
PvuxxxP
)()( 2
v
r
vx
v
r
u
v
s
v
r
v
P
xvuxx
x
v
s
x
v
r
v
P
vuxxxxxP
)(
)()(
2
22
可见
v
rv
u
s
v
ru
v
s
u
r
,
原理,将非线性方程线性化
—— Taylor 展开 /* Taylor’s expansion */
取 x0? x*,将 f (x)在 x0 做一阶 Taylor展开,
2
0000 )(!2
)())(()()( xxfxxxfxfxf,?在 x0 和 x 之间。
将 (x*? x0)2 看成高阶小量，则有：
)*)(()(*)(0 000 xxxfxfxf
)(
)(*
0
0
0 xf
xfxx
线性 /* linear */
x
y
x*
x0
)(
)(
1
k
kkk
xf
xfxx
只要 f?C1，每一步迭代都有
f ’( xk )? 0,而且,
则 x*就是 f 的根。 *lim xx kk
§ 4 Newton - Raphson Method
定理 （ 收敛的充分条件 ）设 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’s Method产生的序列 { xk } 收敛到 f (x) 在 [a,b] 的唯一根。
有根 根唯一 产生的序列单调有界，保证收敛。定理 （ 局部收敛性 ）设 f?C2[a,b]，若 x* 为 f (x) 在 [a,b]
上的根，且 f ’(x*)? 0，则存在 x* 的邻域 使得任取初值,Newton’s Method产生的序列 { xk } 收敛到 x*，
且满足
*)(xB?
*)(0 xBx
*)(2
*)(
)*(
*lim
2
1
xf
xf
xx
xx
k
k
k?
§ 4 Newton - Raphson Method
证明,Newton’s Method 事实上是一种特殊的不动点迭代其中,则
)(
)()(
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
在 单根 /*simple root */
附近收敛快
§ 4 Newton - Raphson Method
注,Newton’s Method 收敛性依赖于 x0 的选取。
x*
x0?x0? x0
HW,p.27 #3,#4
Excuses for not
doing homework
I have the proof,but there
isn't room to write it in
this margin.
§ 4 Newton - Raphson Method
改进与推广 /* improvement and generalization */
重根 /* multiple root */ 加速收敛法：
Q1,若,Newton’s Method 是否仍收敛？0*)( xf
设 x* 是 f 的 n 重根，则,且 。)(*)()( xqxxxf n 0*)(?xq
因为 Newton’s Method 事实上是一种特殊的不动点迭代，
其中,则
)(
)()(
xf
xfxxg
2
2
*)(
*)(*)(*)(1|*)(|
xf
xfxfxfxg 111
n
A1,有局部收敛性，但重数 n 越高，收敛越慢。
Q2,如何加速重根的收敛？
A2,将求 f 的重根转化为求另一函数的单根。
令,则 f 的重根 =? 的单根。
)(
)()(
xf
xfx
§ 4 Newton - Raphson Method
正割法 /* Secant Method */,
Newton’s Method 一步要计算 f 和 f ’，相当于 2个函数值，
比较费时。现用 f 的值近似 f ’，可少算一个函数值。
x0x1
切线
/* tangent line */
割线
/* secant line */
切线斜率? 割线斜率
1
1 )()()(
kk
kk
k xx
xfxfxf
)()(
))((
1
1
1
kk
kkk
kk xfxf
xxxfxx 需要 2个初值 x0 和 x1。
收敛比 Newton’s Method
慢，且对初值要求同样高。
§ 4 Newton - Raphson Method
下山法 /* Descent Method */
—— Newton’s Method 局部微调：
原理,若由 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’s Method 公式。
当? = 1 代入效果不好时，将?减半计算。
§ 4 Newton - Raphson Method
Algorithm,Newton’s Descent Method
Find a solution to f (x) = 0 given an initial approximation x0.
Input,initial approximation x0; f (x) and f ’(x); minimum step size of xmin;
tolerance TOL1 for x ; tolerance TOL2 for? ; maximum number of
iterations Nmax.
Output,approximate solution x or message of failure.
Step 1 Set k = 1;
Step 2 While ( k? Nmax) do steps 3-10
Step 3 Set? = 1;
Step 4 Set ; /* compute xk */
Step 5 If | x? x0 | < TOL1 then Output (x); STOP; /* successful */
Step 6 If then x0 = x ; GOTO Step 10 ; /* update x0 */
Step 7 Set? =? / 2 ; /* update? to descend */
Step 8 If? > TOL2 then GOTO Step 4 ; /* compute a better xi */
Step 9 Set x0 = x0 + xmin ; /* move forward anyway to avoid deadlock */
Step 10 Set k ++;
Step 11 Output (Method failed after Nmax iterations); STOP,/* unsuccessful */
)(
)(
0
00 xf xfxx
)()( 0xfxf?
计算量未见得减小
§ 4 Newton - Raphson Method
求复根 /* Finding Complex Roots */
—— Newton 公式中的自变量可以是复数记 z = x + i y,z0 为初值，同样有
)(
)(
1
k
kkk
zf
zfzz
kkkkkk DiCzfBiAzf )(,)(
设
HW,p.28 #10
代入公式，令实、虚部对应相等,可得;221
kk
kkkk
kk DC
DBCAxx
.221
kk
kkkk
kk DC
CBDAyy
§ 4 Newton - Raphson Method
Lab 04,Newton’s Method
Use Newton’ s method to approximate the m complex roots of a
given polynomial of degree 5? n? m,,near
m given points to a given accuracy.
Input
There are several sets of inputs,For each set:
The 1st line contains an integer n which is the degree of a
polynomial,n =?1 signals the end of file.
The 2nd line contains n+1 real numbers which are the
coefficients of the polynomial,The numbers are separated by spaces.
The 3rd line contains a real number eps which is the absolute
accuracy bound for each solution.
The 4th line contains an integer n? m? 0,followed by m pairs of
real numbers which correspond to the initial complex
guesses,
0111,..)( cxcxcxcxp nnnn
01..,ccc n
mm baba,..11
mm biabia,,,,,11
§ 4 Newton - Raphson Method
Output (?represents a space)
Each root is to be printed as in the C fprintf:
fprintf(outfile,"%10.5f+%10.5f?i\n",real,imag );
Or,if the imaginary part is negative
fprintf(outfile,"%10.5f?%10.5f?i\n",real,fabs(imag) );
If there is no root found near a given point simply print,no?root\n”
The outputs of two test cases must be seperated by a blank line.
Sample Input
(?represents a space)
4
1?–3?20?44?54
0.0001
1?2.5?4.5
2
1?0?0.9
0.0001
2?0?–1.0?0?1.0
–1
Sample Output
(?represents a space)
2.47064+4.64053?i
0.000000.94868?i
0.00000+0.94868?i
§ 5 迭代法的收敛阶 /* Order of Convergence */
定义 设迭代 xk+1 = g(xk) 收敛到 g(x) 的不动点 x*。
设 ek = xk? x*,若,则称该迭代为 p 阶收敛,
其中 C 称为 渐进误差常数 。 /* { xk } converges to x* of order p,
with asymptotic error constant C > 0 */
0|| ||lim 1 Cee p
k
k
k
一般 Fixed-Point Iteration 有,称为 线性收敛 /* linear convergence */，这时 p = 1,0 < C < 1。
0|*)(||| ||l i m 1 xgee
k
k
k
注,超线性收敛不一定有 p > 1。
例如 xn = 1/nn 超线性收敛到 0，但对任何 p > 1 都没有
p 阶收敛。
Aitken 加速有 。 称为 超线性收敛
/* superlinear convergence */。
0**?l i m xx xx
k
k
k 0||
||lim 1
k
k
k e
e
§ 5 Order of Convergence
Steffensen 加速 有 p = 2，条件是,称为 平方收敛
/* quadratic convergence */。
1*)( xg
Newton’s Method 有,只要,
就有 p? 2。重根是线性收敛的。
*)(2
*)(
||
||l i m
2
1
xf
xf
e
e
k
k
k?
0*)( xf
Q,如何实际确定收敛阶和 渐进误差常数？
定理 设 x* 为 x = g(x) 的不动点,若,p? 2；
，且,则 xk+1 = g(xk) 在内 p 阶收敛。
* ) )(( xBCg p
0*)(...*)( )1( xgxg p 0*)()(?xg p
*)(xB?
证明：
p
k
k
p
kkk xxp
gxxxgxgxgx *)(
!
)(.,,*)* ) ((*)()( )(
1
x* k
C
This is a one line proof...if we
start sufficiently far to the left.
HW,p.29 #1
§ 6 劈因子法 /* Splitting Method */
求多项式的根从 f (x)中分离出一个 2 次因子。即：
)* ) (*(
)(
23
3
1
2
0
2
1
1
10
nn
nn
nn
nn
bxbxbxbvxux
axaxaxaxf
通过 可解出一对共轭复根。 0**2 vxux
思路从一对初值 ( u,v ) 出发，则有
)()()()( 2 sxrxPvxuxxf
其中 ( r,s )取决于 u 和 v，可以看作是 ( u,v )的函数，即
r = r ( u,v ),s = s ( u,v ) 。
目标,r = r ( u*,v* ) = 0,s = s ( u*,v* ) = 0。
§ 6 Splitting Method
将 r 和 s 在初值点 ( u,v )做一阶 Taylor展开，并代入 ( u*,v*)：
)*()*(),(*)*,(0
)*()*(),(*)*,(0
vv
v
s
uu
u
s
vusvus
vv
v
r
uu
u
r
vurvur
从中解出 vvvuuu *,* vvuu,，以 更新
u 和 v 再迭代，直到 r 和 s 充分接近 0。
每步迭代须计算
.,,,,,vsusvrursr
§ 6 Splitting Method
计算 r 和 s,
nnnnnn axaxaxaxaxaxf 12222110,..)(
)()(
)(...)()(
)...)(()(
232
2
432
2
012
1
010
2
2
0
2
svbxrvbub
xvbubbxvbubbxubbxb
srxbxbvuxxxf
nnn
nnn
nnn
n
n
2
321
21
011
00
)2.,,,,3,2(
nn
nnn
iiii
vbas
vbubar
nivbubab
ubab
ab
可记为 bn?1
21 nnnn vbubab若令,则,1 nn ubbs
§ 6 Splitting Method
计算,
v
s
v
r
,
vrxxPvuxx
axaxaxaxf nnnn
)()(
)(
2
1
1
10?
v
sx
v
r
v
PvuxxxPv
f
)()(
0
2
v
sx
v
r
v
PvuxxxP
)()( 2
n?2 阶多项式 n?4 阶多项式与前一步同理，可导出 和 的公式。
v
s
v
r
,
v
P
§ 6 Splitting Method
计算,
u
s
u
r
,
vrxxPvuxx
axaxaxaxf nnnn
)()(
)(
2
1
1
10?
u
sx
u
r
u
PvuxxxxPu
f
)()(
0
2
u
sx
u
r
u
PvuxxxxP
)()( 2
而前一步得到
v
sx
v
r
v
PvuxxxP
)()( 2
v
r
vx
v
r
u
v
s
v
r
v
P
xvuxx
x
v
s
x
v
r
v
P
vuxxxxxP
)(
)()(
2
22
可见
v
rv
u
s
v
ru
v
s
u
r
,
