计算方法迭代法.ppt

文档介绍：§ 二分法
§ 迭代法原理
§ Newton迭代法和迭代加速
§ 解线性方程组的迭代法
.
1
§ 二分法
根的估计
二分法
.
2
根的估计
（连续函数的介值定理） 设f(x)在[a,b]上连续，且f(a)f(b)<0，则存在x*(a,b)使f(x*)=0。
证明x33x1 = 0 有且仅有3个实根，并确定根的大致位置使误差不超过 =。
解:
单调性分析和解的位置
选步长h=2, 扫描节点函数值
异号区间内有根
.
3
f(x)= x33x1
.
4
二分法
条件: 设f(x)在[a,b]上连续，f(x)=0在[a,b]上存在唯一解，且f(a)f(b)<0。记
Step 1: If f(a0)f(x0)<0, then x*(a0,x0) let a1=a0, b1=x0; Else x*(x0,b0) let a1=x0, b1=b0; Let x1=(a1+b1)/2.
Step k: If f(ak-1)f(xk-1)<0, then x*(ak-1,xk-1) let ak=ak-1, bk=xk-1; Else x*(xk-1,bk-1) let ak=xk-1, bk=bk-1; Let xk=(ak+bk)/2.
收敛性及截断误差分析:
.
5
x33x1 = 0, [1,2], -1
.
6
二分法
优点
算法简单
收敛有保证
只要f(x)连续
缺点
对区间两端点选取条件苛刻
收敛速度慢
.
7
§ 迭代法原理
迭代法的思想
不动点原理
局部收敛性
收敛性的阶
.
8
迭代法的思想
条件: f(x)=0 在x0附近有且仅有一个根
设计同解变形 x=g(x)
迭代式 xk=g(xk-1), k=1,2,…
如果收敛 xk x*, 则x*是f(x)=0 的根
.
9
不动点原理(迭代过程收敛)
(不动点原理) 设映射g(x)在[a,b]上有连续的一阶导数且满足
1o 封闭性：x  [a,b], g(x)  [a,b] ,
2o 压缩性： L (0,1)使对x  [a,b], |g'(x)|L,
则在[a,b]上存在唯一的不动点x*，且对x0  [a,b], xk=g(xk-1)收敛于x* 。进一步，有误差估计式
后验估计
先验估计
算法设计中迭代结束条件: 近似使用|xk-xk-1|<
.
10