§ 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 ’，可少算一个函数值。
x0 x1
切线
/* 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.00000????0.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 ’，可少算一个函数值。
x0 x1
切线
/* 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.00000????0.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
?
???
?
?
?
??
?
??
?
?,
