文档介绍：第五章非线性方程求根
/* Solutions of Nonlinear Equations */
求 f (x) = 0 的根
:
则称为 f (x) = 0 的 m 重根,当m=1时称为单根,
此时有:
1
§ 二分法(对分法) /* Bisection Method */
原理:若 f C[a, b],且 f (a) · f (b) < 0,则 f 在(a, b) 上必有一根。
:先利用零点定理确定根的存在区间,然后将含根的区间对分,通过判别对分点函数值的符号,,将根的存在区间缩到充分小,从而求出满足精度要求的根的近似值.
When to stop?
2
a
b
x1
x2
a
b
When to stop?
或
不能保证 x 的精度
2
x
3
具体做法如下:
计算区间[a, b]的中点函数值
(2)若,则 :
当取
当取
此时的(a1, b1)必是根的存在区间,重复此过程就得到一个包含根的区间套,满足
(1)若,是预先给定的误差精度,则为
所求根的近似值.
4
当 n 充分大时就有:
算法(二分法)
2.
3.
N 的信息,停机。
输入,区间,精度,最大的迭代次数N
,则输出停机
5
误差分析:
第1步产生的
有误差
第 k 步产生的 xk 有误差
对于给定的精度,可估计二分法所需的步数 k :
①简单;
②对f (x) 要求不高(只要连续即可) .
①无法求复根及偶重根
②收敛慢
注:用二分法求根,最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序,将[a, b]分为若干小区间,对每一个满足 f (ak)·f (bk) < 0 的区间调用二分法程序,可找出区间[a, b]内的多个根,且不必要求 f (a)·f (b) < 0 。
6
例1 求x3-3x+1=0的实根分布情况,要求区间长度不大于1,并求出最小正根的近似值,精度
x
-4
-3
-2
-1
0
1
2
3
4
f(x)
-51
-17
-1
3
1
-1
3
19
53
表5-1
可见,在(-2,-1)区间、(0,1)区间、(1,2)区间各有一实根,
下面求(0,1)区间上的实根,列表如教材表5-2:
k
ak
bk
xk
f(xk)
1
0
1
-
2
0
3
-
4
5
6
--3171
7
可见x[,]
若取=,,当k=13时,
bk-ak=<,此时过程结束,取
xk=(+)/2=
7
的两端函数值符号,从而判断根的存在区间.
从二分法的原理引出逐步扫描法,即,选取适当的步长h对区间[a, b]从左到右逐步扫描,检查小区间
注:在实际应用中常用二分法来判别根的存在区间,如区间较大可用二分法适当收缩区间,,迭代计算求根.
注:在逐步扫描法中,步长h 选择应适当,h 过大可能漏掉根,h 过小将会增加计算的工作量. .
8
试位法/* Regula Falsi Method */
a
b
(a+b)/2
(a, f (a))
(b, f (b))
Is it really better than
Bisection Method?
注:试位法每次迭代比二分法多算一次乘法,而且不保证收敛。
9
§ 迭代法/* Fixed-Point Iteration */
f (x) = 0
x = g (x)
等价变换
f (x) 的根
g (x) 的不动点
思路
从一个初值 x0 出发,计算 x1 = g(x0), x2 = g(x1), …, xk+1 = g(xk), …若收敛,即存在使得
,且