当前位置:
文档之家› 方程求根的迭代法(19-20).
方程求根的迭代法(19-20).
xk
1.25 1.375 1.3125 1.3438
f (xk)的符号
+ +
4
5 6
1.3125
1.3125 1.3203
1.3438
1.3281 1.3281
1.3281
1.3203 1.3242
+
-
二分法程序流程图
输入
定义f (x)
a, b,
k=0
f (a) f (b)>0 否 否 m=(a+b)/2 |a-b|< 是 a=m 是 打印m, k 结束 f (a) f (b)=0
f (x) = 0
等价变换
x ( x)
把根的某个猜测值 x0 代入迭代函数得
x1 ( x0 )
x12 x ( x2 = 0 1) 3
一般地:
xk 1 ( xk )
得到序列 {xk }
则若 {xk }收敛就必收敛到 f ( x) 0的根:
lim xk 1 lim ( xk ) ( lim xk )
由于:
lim
k
xk x*
所以,二分法可以求得任意精度的根。 对于任意给定的精度要求: 0
1 (b a) 由 k 2 得: k ln(b a) ln ln 2 | x* xk |
即:只要二分K次,就可得到指定精度的根。
例: 求方程在
解:
f ( x) x x 1 0 区间[1, 1.5]内的 实根。要求准确到小数点后第2位。
3.判断若f (x1) = 0,则x1即是根,否则检验:
(1)若f (x1)与f (a)异号,则知解位于区间[a, x1],
b1=x1, a1=a; (2)若f (x1)与f (a)同号,则知解位于区间[x1, b], a1=x1, b1=b。 反复执行步骤2、3,便可得到一系列有根区间: (a, b), (a1, b1), …, (ak, bk), …
§ 4、 0
二 分 法
二分法的基本思想是:
逐步将有根区间分半,通过判别函数值的符号, 进一步搜索有根区间,将有根区间缩小到充分小,从 而求出满足给定精度的根的近似值。
执行步骤
1.计算f (x)在有解区间[a, b]端点处的值,f (a),f (b)。
2.计算f (x)在区间中点处的值f (x1)。
在中学时,我们很熟悉一次、二次代数方程以及某些特殊的 高次方程或超越方程的解法。这些方法都是代数解法,也是精确 法。但在实际中,有许多方程问题无法求出公式解。例如超越方 程
tgx x 0
0.25 tgx 4.8889sin x 0
看起来很简单,却不容易求得精确解。至于解三次、四次代 数方程,尽管存在着求解公式,却不实用,而对一般的五次或五 次以上的代数方程,根本没有求根公式。另一方面,在实际应用 中,只要能获得具有预先给定的误差限内的近似值就可以了。因 此,需要引进能够达到一定精度要求的求方程近似值的方法。
k k k
x (x ( x) :
yx y (x )
yx
Q1
交点即真根。
y
y ( x)
P 0
Q2
P*
O
P 1
P 2
x1 x0 x
x* x2
例:求方程
的一个根
f ( x) x 10x 2 0
解: 10x x 2
求方程 f ( x) 0 的根也叫求函数 f ( x) 的零点。 需要解决的几个问题:
1.根的存在性。方程有没有根?如果有根,有几个根? 2.这些根大致在哪里?如何把根隔离开来? 3.根的精确化 定理1:设函数 f (x) 在区间[a, b]上连续,如果f (a) f (b) < 0,
则方程 f (x) = 0 在[a, b]内至少有一实根x*。
重庆大学数理学院
数值分析
第十讲
主讲教师: 谭 宏
第四章
1.教学内容:
非线性方程求根
二分法、迭代法的一般原理 、NEWTON迭代法
2.重点难点:
重点:牛顿迭代法及局部收敛性 难点:迭代法及收敛性定理
3.教学目标:
掌握迭代法的一般原理、对给出的方程球根问题,能 利用一般迭代法或者牛顿迭代法进行数值求解
| x* xk | 1 (b a) k 2
得:
1 ln(0.5) ln 102 ln(b a) ln 2 k ln 2 ln 2
解得k = 6,即只要二分6次,即达所求精度。
k
0 1 2 3
ak
1 1.25 1.25 1.3125
bk
1.5 1.5 1.375 1.375
是
是 是
f (a) =0
否
否 f(a)f(b)>0 否 b=m
打印b, k
结束
打印a, k
k=K+1
§ 4、 1
迭代过程的收敛性
1、迭代法的设计思想 迭代法是一种逐次逼近法,这种方法使用某个固 定公式-所谓迭代公式反复校正根的近似值,使之逐 步精确化,直至满足精度要求的结果。 迭代法的求根过程分成两步,第一步先提供根的 某个猜测值,即所谓迭代初值,然后将迭代初值逐步 加工成满足精度要求的根。 迭代函数 迭代法的设计思想是:
4、当
5、则
bk 1 ak 1
xk 1 1 ( a k bk ) 2
时 即为根的近似
①简单; ② 对f (x) 要求不高(只要连续即可) .
①无法求复根及偶重根 ② 收敛慢
Y
y f ( x)
x1 ab 2
x*
0 a
x2
b1
b
x
a1
Y
0
a
x*
b x
误差估计:
| x* xk | 1 (b a) k 2
3
用二分法,这里a = 1, b = 1.5, 且f (a) < 0, f (b) > 0。取区间[a, b]的中点x0 = 1.25将区间二等分, 由于f (x0)< 0,即f (x0)与f (a)同号,故所求的根必在x0 的右侧,这里应令a1 = x0 = 1.25,b1 = b = 1.5,而得到 新的有根区间(a1, b1)。 对区间(a1, b1)再用中点x1 = 1.375二分,并进行 根的隔离,重复上述步骤,如此反复二分下去。 我们预先估计一下二分的次数:按误差估计式
迭代格式
等价变换
x lg( x 2)
xk 1 lg( xk 2)
x1 = 0.4771
x2 = 0.3939 … x6 = 0.3758 x7 =0.3758