第二章 非线性方程(组)的迭代解法(11)

2
North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
1、二分法
设 f (x) 在区间 [a, b] 上连续且有 f (a) f (b) 0 ，则 f (x) 在区间 [a, b] 内有解，不妨设解唯一！ 算法构造原理:
找[a,b] [a0 ,b0 ] [a1,b1] [an ,bn ] ,满足: (1) f (an ) f (bn ) 0, x* [an ,bn ]; 即 有根区间 1 1 (2) bn an (bn 1 an 1 ) n b0 a0 2 2 an bn 1 1 令 xn , 则 xn x * (bn an ) n1 (b a); 2 2 2
(2) 二分法线性收敛; (3) 二分法可用来细化有根区间，这是它的一大优点! 故二分法可以用来确定迭代法的迭代初值!
返回主目录
School of Math. & Phys. 6 North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
7
North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
例2 用一般迭代法计算f ( x) x3 4 x 2 10在[1 2]的实根。 ，
方法1：x ( x) x x 3 4 x 2 10; 1 方法2： x 10 x x ( x) 4 10 x 3 ; 2 10 3 2 2 方法3：x 4 x 10 x 4 x; x 10 x ( x) 4x x
10
① ②
North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
(1)
令F ( x) x ( x),
由条件(1)可得解的存在性； 由条件(2)可证解的唯一性！
(2) 由条件(1)可知{xn } [a, b];
xn x * ( xn 1 ) ( x*) (n ) xn 1 x* L xn 1 x*
其中 ε,为容许误差！
School of Math. & Phys.
4
North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
综合上述，得到如下算法，
(1)
ab , f f ( x); (2) 计算x 2 (3) 若 f , 则x为所求根，结束！ 否则 若f f 0, 则b x, f f ; a b
方法4
1.5000 1.3484 1.3674
6次
0.8165
2.9969
0-2.9412i 1.3650 不收敛 1.3653 1.3652 1.3652
15次
*收敛与否，以及收敛快 慢，取决于迭代函数
*精度控制的表达式？？
1.3652
1.3651
1.3653 1.3652
School of Math. & Phys. 9 North China Elec. P.U.
2、一般迭代法
(一) 构造方法
(1)
f ( x) 0 x ( x)，( x)称为迭代函数。
x0 U δ( x*),构造迭代格式
(1)
(2) 在解的邻域内选定初值
xn 1 ( xn ) (n 0,1, 2,)
(3)
讨论xn 的收敛性及收敛速度（收敛阶）。
School of Math. & Phys.
2 3
方法4：x 2 ( x 4) 10 x ( x) 10 /( x 4) ;
取初值x0 1.5, 104 , 用以上四种方法算，结果如下：
School of Math. & Phys. 8 North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
方法1
1.5000 -0.8750 6.7324 -69.7200 1.0275e+8 不收敛
方法2
1.5000 1.2870 1.4025 1.3455 1.3752 1.3601 1.3678 1.3639 1.3659 1.3649 1.3654
方法3
1.5000
事实上，
设x * 为f ( x)的m重根，即f ( x) ( x x*)m ( x） ( x)连续且( x*) 0)。 (
不妨设( x*) 0, ( x)的连续性，则δ 0, x x * δ时，( x) 0。 由 当
当n充分大以后，[an ,bn ] ( x * δ,x * δ ),于是当m为偶数时， x [an ,bn ], f ( x) 0,不变号了！(??)
①得证；
进而可证②!
School of Math. & Phys. 11 North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
(三) 局部收敛定理 设
x* ( x*), ' ( x) 在包含x*某个开区间内连续，
若 ' ( x*) L 1, 则 0, 使得 x0 [ x * , x * ], 由迭代(1)产生的序列 {xn } [ x * , x * ] , lim xn x * n 且有与前一定理完全相同的不等式成立！
lim xn x * .
n
School of Math. & Phys.
3
North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
算法停止的条件 什么时候停止？
a
a x1
x* x2 b
b
x
或
ba ε
f ( xk 1 )
可得 x* 1.36523, 共计算21次！ 取 10 9， 10 6，
School of Math. & Phys.

5
North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
关于二分法的讨论
(1) 二分法只能求有根区间中的奇数重的实根;
15
North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
例3 1 a 3 a2 1、证明xk 1 ( xk )和xk 1 xk 3 分别是求 2 xk 4 4 xk
a的平方收敛的迭代格式。
解： 迭代函数为
同理对xk 1 2 ( xk )证明！
L 1
L x0 x * lim xn x*;
n
n
(3) xn 1 xn xn 1 x * x * xn xn x * xn 1 x *
xn x * L xn x * (1 L) xn x *
xn1 xn L xn xn1
则 0, 使得 x0 [ x * , x * ]但x0 x*,
由迭代
xn1 ( xn ) 产生的序列 { xn } 以m阶收敛速度收敛到x* 。
证明：由泰勒公式和收敛阶定义可证！ 注: 1、给出了由迭代函数判断收敛速度的方法；
2、给出了提高收敛速度的方法!
School of Math. & Phys.
输入，，计算f a f (a), fb f (b);
注： 其中 , 为 精度控制参数!
若f f a 0, 则a x, f a f ; ab 为所求根，结束！ (4) 若 b a , 则x
否则，转(2)；
2
例1
计算f ( x) x3 4 x 2 10 0在[1，]内的实根。 2
School of Math. & Phys.
14
North China Elec. P.U.
Numerical Analysis
2013-12-12
J. G. Liu
定理（简单迭代算法m阶收敛的充分条件）
( m) 设 x* ( x*), ( x)( m 2) 在包含x*某个开区间内连续， 若 (i ) ( x*) 0 (i 1,2,, m 1), ( m) ( x*) 0,
则 (1)
x ( x)在[a, b]内有唯一的根x *；
且 lim xn x*;
n
(2) x0 [a, b]，由迭代xn 1 = ( xn )产生的序列{xn } [ a, b]
(3)
下面看证明过程，
School of Math. & Phys.
L xn x * xn xn 1 1 n L L xn x * x1 x0 1 L
Numerical Analysis
2013-12-12
1
J. G. Liu
(二) 大范围收敛定理
设 ( x) C [a, b]， (1) x [a, b], ( x) [a, b], 即 (x) 是自映射； (2) ' ( x) L 1, x ( a, b)
证明:略!
注： 当定理条件成立时， 只要x0充分接近x*，就能保证迭代序列{xn}收敛于x*！