Bisection Methoda+h误差分析有误差一第1步产生的x=2第 k 步产生的 x, 有误差 k,-xsb-a2k对于给定的精度8，可估计二分法所需的步数k<e= k>[n(b-a)-lna]b-a2kIn 2①简单；对f（x）要求不高（只要连续即可）②无法求复根，收敛慢注：用二分法求根，最好先给出f(x）草图以确定根的大概位置。或用搜索程序，将[a,bl分为若千小区间，对每一个满足f(a)f(b)<0的区间调用二分法程序，可找出区间[a,b]内的多个根，且不必要求f(a);f(b)<0
Bisection Method 误差分析 第1步产生的 2 1 a b x 有误差 2 1 b a |x x*| 第 k 步产生的 xk 有误差 k k b a |x x*| 2 对于给定的精度 ,可估计二分法所需的步数 k ： ln 2 ln ln 2 b a ε ε k b a k ①简单; 对f (x) 要求不高(只要连续即可) . ②无法求复根，收敛慢 注：用二分法求根，最好先给出 f (x) 草图以确定根的大 概位置。或用搜索程序，将[a, b]分为若干小区间，对每一 个满足 f (ak )·f (bk ) < 0 的区间调用二分法程序，可找出区 间[a, b]内的多个根，且不必要求 f (a)·f (b) < 0
82不动点迭代法问题一设f(x)连续，求方程f(x)=0的根二基本思想转化为不动点求解等价变形f(x)= 0x = p(x)如果三x*,使x*=p(x*),则称x*为p(x)的一个不动点
§2 不动点迭代法 f (x) 0 x (x) 等价变形 一 问题 设f (x)连续，求方程f (x) 0的根。 二 基本思想 , ( ), ( ) . 如果x * 使x * x * 则称x *为 x 的一个不动点 转化为不动点求解
三基本思想与选代格式任取xo(一般≠x )，构造迭代:Xk+1 = Φ(xk)xi = p(xo), x2 = (xi), : : : 得到一序列[x}.如果(x}的极限存在,设 lim xk= x,则显然有k→>8x*= p(x*)即x是p的不动点，此时称迭代xk+1=β(x)收敛x* = lim Xk = lim p(Xk-1) = p( lim Xk-1) = p(x )k-→80k->878
三 基本思想与迭代格式 ( ), * 0 任取x 一般 x 构造迭代: ( ), 1 0 x x ( ), x2 x1 ( ) xk1 xk . k 得到一序列 x , k 如果 的极限存在 x 设 lim xk x * ,则显然有 k ( ) * * x x ( ) . 1 即x *是的不动点，此时称迭代xk xk 收敛( ) * k x k x x lim * lim ( ) 1 k k x ( lim ) 1 k k x
基本迭代格式Xk+1 = p(x))迭代函数p(x)选代收敛lim x, = x k->00lim x,不存在迭代发散k-→00
基本迭代格式 迭代函数 迭代收敛 迭代发散 ( ) k 1 k x x (x) lim . * x x k k k 不存在 k x lim
例1 建立迭代格式求x3 -x2-1=0在[1.3,1.6内的根区方案l： x3-x2-1=0x3 = x2 +1 x=3(1+x2):建立选代格式：xk+1=(1+x)1/3取迭代初值xo =1.3,可算得：k = 0 : x1 =(1 + x)1/3 = (1 +1.32)1/3 = 1.3907k =1: x2 = (1 + x)1/3 = (1 + 1.39072)1/3 = 1.4316k = 2 : x3 =(1 + x3)/3 = (1+ 1.43162)1/3 = 1.4501x7 = ..· = 1.4649k = 6:
1 1 0 [1.3,1.6] . 例 建立迭代格式求x 3 x 2 在 内的根 方案1: 2 1/ 3 1 (1 ) xk xk 1 0 3 2 x x 1 3 2 x x 3 2 x (1 x ) 建立迭代格式： 取迭代初值x0 1.3,可算得： k 0 : (1 ) (1 1.3 ) 1.3907 2 1/ 3 2 1/ 3 x1 x0 k 1: (1 ) (1 1.3907 ) 1.4316 2 1/ 3 2 1/ 3 x2 x1 k 2 : (1 ) (1 1.4316 ) 1.4501 2 1/ 3 2 1/ 3 x3 x2 k 6 : x7 1.4649