第二章 非线性方程求根
/* Solutions of Nonlinear Equations */
§ 1 多项式基础 /* Polynomials */ （自习）
§ 2 二分法 /* Bisection Method */
求 f (x) = 0 的根原理,若 f?C[a,b]，且 f (a) · f (b) < 0，则 f 在 (a,b) 上必有一根。
§ 2 Bisection Method
a
b
x1
x2
a
b
When to stop?
11 εxx kk 2)( εxf?或不能保证 x 的精度
x*
2
xx*
§ 2 Bisection Method
误差 分析：
第 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 。
HW,p.16 #1
§ 2 Bisection Method
Lab 02,Bisection Method
Use the Bisection method to find on m given intervals the m real roots of a
given polynomial of degree 5? n? m,.
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 an integer Max and two real numbers eps1
and eps2,where Max is the maximum number of iterations,eps1 is the
accuracy bound for x and eps2 is the accuracy bound for p(x).
The 4th line contains an integer m (n? m? 0),followed by m pairs
of real numbers a1 b1 … am bm which are the end points of the intervals
[ a1,b1 ] … [ am,bm ].
0111,..)( cxcxcxcxp nnnn
01..,ccc n
Output
Each root is to be printed as in the C fprintf:
fprintf(outfile,"%12.7f?",root ); /* here?represents a space */
If there is no root found in an interval,simply print,no?root?”,
The output of the next set must be printed in a new line.
Sample Input (?represents a space)
2
1?01
1000?0.00000001?0.00000001
220.5?0.5?2
3
1?0?01
1000?0.00000001?0.00000001
21?0?0?2
1
Sample Output (?represents a space)
1.00000001.0000000?
no?root1.0000000?
§ 2 Bisection Method
试位法 /* Regula Falsi Method */
a
b
(a+b)/2
x*
(a,f (a))
(b,f (b))
abafbf afax )()( )(
Is it really better than
Bisection Method?
注,试位法每次迭代比 二分法多算一次乘法，而且不保证收敛 。
§ 2 Bisection Method
§ 3 迭代法 /* Fixed-Point Iteration */
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 limlim 1
So basically we are
done! I can’t believe
it’s so simple!
What’s the problem?
Oh yeah? Who tells
you that the method
is convergent?
§ 3 Fixed-Point Iteration
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
§ 3 Fixed-Point Iteration
定理 考虑方程 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
§ 3 Fixed-Point Iteration
证明,① 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
§ 3 Fixed-Point Iteration
④?||
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
⑥
*)(* )*)((lim**lim 1 xgxx xxξgxx xx
k
kk
kk
k
k
可用 来控制收敛精度
|| 1 kk xx
L 越 收敛越快小注,定理条件非必要条件，可将 [a,b]缩小，定义 局部收敛性,若在 x* 的某?领域 B? = { x | | x? x* | } 有
g?C1[a,b] 且 | g’(x*) | < 1,则由?x0?B?开始的迭代收敛。即 调整初值可得到收敛的结果。
§ 3 Fixed-Point Iteration
Algorithm,Fixed-Point Iteration
Find a solution to x = g(x) given an initial approximation x0.
Input,initial approximation x0; tolerance TOL; maximum number of
iterations Nmax.
Output,approximate solution x or message of failure.
Step 1 Set i = 1;
Step 2 While ( i? Nmax) do steps 3-6
Step 3 Set x = g(x0); /* compute xi */
Step 4 If | x? x0 | < TOL then Output (x); /* successful */
STOP;
Step 5 Set i ++;
Step 6 Set x0 = x ; /* update x0 */
Step 7 Output (The method failed after Nmax iterations); /* unsuccessful */
STOP.
当 x 很大时，此处可改为 T O L
x
xx 0
§ 3 Fixed-Point Iteration
改进、加速收敛 /* accelerating convergence */
待定参数法：
若 | 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
Aitken 加速：
§ 3 Fixed-Point Iteration
x
y
y = xy = g(x)
x* x0
P(x0,x1)
x1 x2
x?
P(x1,x2)
210
2
01
0 2
)(?
xxx
xxxx
一般地，有：
21
2
1
2
)(?
KKK
KKKK
xxx
xxxx
.,,.,,
),(,?
),(,?
),(),(,
341
230
12010
xgxx
xgxx
xgxxgxx
比 收敛得略快。?KxKx
Steffensen 加速：
......,
),(),?(,?
),(),(,
0
12010
12010
x
xgxxgxx
xgxxgxx
HW,p.21-22
#1,#5
Lab 03,Steffensen’s Method
Use Steffensen’ s method to approximate the solutions of
x=10.0*(sinx+cosx+1.0)near m given points to some given accuracy.
Input
The 1st line contains an integer m which is the number of solutions
to be found,and an integer Nmax which is the maximum number of
iterations.
The 2nd line contains a real number eps which is the absolute
accuracy bound for each solution.
The 3rd line contains m real numbers which are the initial guesses
of the solutions,The numbers are separated by spaces.
Output
Each root is to be printed as in the C fprintf:
fprintf(outfile,"%10.5f\n",root );
If there is no root found near a given point simply print,no?root\n”
(here?represents a space).
§ 3 Fixed-Point Iteration
Sample Input (?represents a space)
1?1000
0,0000005
3.00
Sample Output (?represents a space)
2.88351
§ 3 Fixed-Point Iteration
/* Solutions of Nonlinear Equations */
§ 1 多项式基础 /* Polynomials */ （自习）
§ 2 二分法 /* Bisection Method */
求 f (x) = 0 的根原理,若 f?C[a,b]，且 f (a) · f (b) < 0，则 f 在 (a,b) 上必有一根。
§ 2 Bisection Method
a
b
x1
x2
a
b
When to stop?
11 εxx kk 2)( εxf?或不能保证 x 的精度
x*
2
xx*
§ 2 Bisection Method
误差 分析：
第 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 。
HW,p.16 #1
§ 2 Bisection Method
Lab 02,Bisection Method
Use the Bisection method to find on m given intervals the m real roots of a
given polynomial of degree 5? n? m,.
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 an integer Max and two real numbers eps1
and eps2,where Max is the maximum number of iterations,eps1 is the
accuracy bound for x and eps2 is the accuracy bound for p(x).
The 4th line contains an integer m (n? m? 0),followed by m pairs
of real numbers a1 b1 … am bm which are the end points of the intervals
[ a1,b1 ] … [ am,bm ].
0111,..)( cxcxcxcxp nnnn
01..,ccc n
Output
Each root is to be printed as in the C fprintf:
fprintf(outfile,"%12.7f?",root ); /* here?represents a space */
If there is no root found in an interval,simply print,no?root?”,
The output of the next set must be printed in a new line.
Sample Input (?represents a space)
2
1?01
1000?0.00000001?0.00000001
220.5?0.5?2
3
1?0?01
1000?0.00000001?0.00000001
21?0?0?2
1
Sample Output (?represents a space)
1.00000001.0000000?
no?root1.0000000?
§ 2 Bisection Method
试位法 /* Regula Falsi Method */
a
b
(a+b)/2
x*
(a,f (a))
(b,f (b))
abafbf afax )()( )(
Is it really better than
Bisection Method?
注,试位法每次迭代比 二分法多算一次乘法，而且不保证收敛 。
§ 2 Bisection Method
§ 3 迭代法 /* Fixed-Point Iteration */
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 limlim 1
So basically we are
done! I can’t believe
it’s so simple!
What’s the problem?
Oh yeah? Who tells
you that the method
is convergent?
§ 3 Fixed-Point Iteration
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
§ 3 Fixed-Point Iteration
定理 考虑方程 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
§ 3 Fixed-Point Iteration
证明,① 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
§ 3 Fixed-Point Iteration
④?||
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
⑥
*)(* )*)((lim**lim 1 xgxx xxξgxx xx
k
kk
kk
k
k
可用 来控制收敛精度
|| 1 kk xx
L 越 收敛越快小注,定理条件非必要条件，可将 [a,b]缩小，定义 局部收敛性,若在 x* 的某?领域 B? = { x | | x? x* | } 有
g?C1[a,b] 且 | g’(x*) | < 1,则由?x0?B?开始的迭代收敛。即 调整初值可得到收敛的结果。
§ 3 Fixed-Point Iteration
Algorithm,Fixed-Point Iteration
Find a solution to x = g(x) given an initial approximation x0.
Input,initial approximation x0; tolerance TOL; maximum number of
iterations Nmax.
Output,approximate solution x or message of failure.
Step 1 Set i = 1;
Step 2 While ( i? Nmax) do steps 3-6
Step 3 Set x = g(x0); /* compute xi */
Step 4 If | x? x0 | < TOL then Output (x); /* successful */
STOP;
Step 5 Set i ++;
Step 6 Set x0 = x ; /* update x0 */
Step 7 Output (The method failed after Nmax iterations); /* unsuccessful */
STOP.
当 x 很大时，此处可改为 T O L
x
xx 0
§ 3 Fixed-Point Iteration
改进、加速收敛 /* accelerating convergence */
待定参数法：
若 | 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
Aitken 加速：
§ 3 Fixed-Point Iteration
x
y
y = xy = g(x)
x* x0
P(x0,x1)
x1 x2
x?
P(x1,x2)
210
2
01
0 2
)(?
xxx
xxxx
一般地，有：
21
2
1
2
)(?
KKK
KKKK
xxx
xxxx
.,,.,,
),(,?
),(,?
),(),(,
341
230
12010
xgxx
xgxx
xgxxgxx
比 收敛得略快。?KxKx
Steffensen 加速：
......,
),(),?(,?
),(),(,
0
12010
12010
x
xgxxgxx
xgxxgxx
HW,p.21-22
#1,#5
Lab 03,Steffensen’s Method
Use Steffensen’ s method to approximate the solutions of
x=10.0*(sinx+cosx+1.0)near m given points to some given accuracy.
Input
The 1st line contains an integer m which is the number of solutions
to be found,and an integer Nmax which is the maximum number of
iterations.
The 2nd line contains a real number eps which is the absolute
accuracy bound for each solution.
The 3rd line contains m real numbers which are the initial guesses
of the solutions,The numbers are separated by spaces.
Output
Each root is to be printed as in the C fprintf:
fprintf(outfile,"%10.5f\n",root );
If there is no root found near a given point simply print,no?root\n”
(here?represents a space).
§ 3 Fixed-Point Iteration
Sample Input (?represents a space)
1?1000
0,0000005
3.00
Sample Output (?represents a space)
2.88351
§ 3 Fixed-Point Iteration
