二分法(对分法)(续) 收敛准则 1.事先误差估计: 利用误差估计定理,令x-x7(b-a)<6 得 k> In(b-a)-Ine In 2 从而得到对分次数k,取xk作为根得近似值x 2事后误差估计: 给定E,每步检查xk-x1|n2(b-a)<s,或(x)<6 若成立,则取x≈x,否则继续对分。 Remark:二分法的优点是方法及相应的程序均简单, 且对fx)性质要求不高,只要连续即可。但二分法不 能用于求复数根和偶数重根 2004-11-22 返回 11
2004-11-22 11 二分法（对分法）（续） 三、收敛准则 1.事先误差估计 ： − ≤ ( − ) < ε 2 * 1 x x b a 利用误差估计定理，令 k k 得 ln 2 ln( − ) − ln ε > b a k 从而得到对分次数 k，取 x k作为根得近似值 x * 。 2.事后误差估计 ： 给定ε，每步检查 ，或 若成立，则取 x ≈ x k，否则继续对分。 * − ≤ − < ε − ( ) 2 1 1 x x b a k k k ( ) < ε k f x Remark：二分法的优点是方法及相应的程序均简单， 且对f(x )性质要求不高，只要连续即可。但二分法不 能用于求复数根和偶数重根。 返回
§7.2迭代法的基本理论 、不动点迭代法 令方程f(x)=0,将其变成一个等价的方程x=Φ(x), 构造x1=(x),k=0,1…, {xk}称为迭代序列,①(x)称为迭代函数, xk=Φ(xk)称为迭代格式或迭代过程(迭代式), 且当(x)连续时,有imxk=lm(xk)=d( ( xk) → 即x=(x)或f(x)=0 即序列{x)极限x为f(x)=0的根 2004-11-22 12
2004-11-22 12 § 7.2 迭代法的基本理论 一、不动点迭代法 令方程 ,将其变成一个等价的方程 , 构造 , f (x) = 0 x = Φ(x) xk+1 = Φ(xk ), k = 0,1,L { }k x 称为迭代序列，Φ(x)称为迭代函数, ( ) k 1 k x = Φ x + 称为迭代格式或迭代过程（迭代式）， lim lim ( ) (lim ) 1 k k k k k k x x x →∞ →∞ + →∞ 且当 连续时，有 = Φ = Φ 或 。 Φ(x) 即 ( ) * * x = Φ x ( ) 0 * f x = 即序列{xk }的极限x*为f (x) = 0的根
不动点迭代法(续) 由于f(x)=0的根x满足x=Φ(x),反之亦然。 也称x为Φ(x)的不动点。即映射关系φ将x映射 到x本身。 求f(x)的零点就等价转化为求中的不动点 也称x1=Φ(x),k=01…为不动点迭代法(也称简 单迭代法或逐次逼近法) Remark:可以通过不同的途径将x)=0化为 x(x)的形式。 问题:如何选取合适的迭代函数(x)? 迭代函数φ(x)应满足什么条件,序列{xk收敛? 怎样加速序列{xk}的收敛? 2004-11-22 13
2004-11-22 13 不动点迭代法（续） 也称 为不动点迭代法（也称简 单迭代法或逐次逼近法） 。 xk+1 = Φ(xk ), k = 0,1,L 求 f (x)的零点就等价转化为求φ的不动点。 由于 f (x) = 0 的根 x* 满足x* = Φ(x* )，反之亦然。 也称 为 的不动点。即映射关系φ将 映射 到 本身。 * x Φ（x） * x * x Remark：可以通过不同的途径将f(x)=0化为 x=φ(x)的形式。 问题：如何选取合适的迭代函数φ(x) ？ 迭代函数φ(x)应满足什么条件，序列{xk}收敛？ 怎样加速序列{xk}的收敛？
、不动点迭代法的一般理论 定理1.(不动点定理)已知x=φ(x),Φ(x)满足 φx)∈C1,bC(a,b),且 1在常数0<L<1,使对任意x∈(ab)有(x)≤L 2.对任意x∈[a,b],有a a≤Φ(x)≤b 则 1.x=(x)在a,b上有唯一的不动点x 2.对任意x∈(a,b.xk+=(xk+),k=0,1,2…产生的序列 {xk}必收敛到φ的不动点x 3.{x有误差估计 x≤ 1}x-x/x-x|≤ 2004-11-22
2004-11-22 14 二、不动点迭代法的一般理论 定理1.（不动点定理）已知 ， 满足 ，且 x = Φ(x) Φ(x) Φ(x)∈C[a,b]∩C′(a,b) x = Φ(x)在[a,b] * 1. 上有唯一的不动点x 则 2. 对任意 x ∈[a,b],有a ≤ Φ(x) ≤ b 1.存在常数0<L<1,使对任意 x∈(a,b)有Φ′(x) ≤ L 1 0 * 1 * 1 , 1 x x L L x x x x L L x x k k k k k − − − − ≤ − − ≤ − { }k 3. x 有误差估计 * x x0 ∈(a,b), xk+1 = Φ(xk+1), k = 0,1,2L { }k x 2. 对任意 产生的序列 必收敛到φ的不动点
不动点迭代法的一般理论(续) 证明: 1由于Φ(x)在[ab上连续,作辅助函数v(x)=0x)-x 则v(x)∈C[a,b且,v(a)=0(a)-a≥0,y(b)=(b)-b≤0 故由连续函数的介值定理,至少存在 x∈{a,b使v(x)=0,即o(x)=x 即存在￠的不动点x 又设Φ(x)有两个不动点x,x2∈[ab]注意Φ(x)∈C(an,b 且(x)≤L<L 故由微分中值定理-x=(x)-x2)=p(x-x -()x-x2=0,得x-x1=0 即x1=x2④(x)有唯一的不动点 2004-11-22 15
2004-11-22 15 不动点迭代法的一般理论（续） 证明： 1.由于Φ(x)在[a,b]上连续，作辅助函数ψ (x) = ϕ(x) − x, 则ψ(x)∈C[a,b]且，ψ(a) =ϕ(a) − a ≥ 0,ψ (b) =ϕ(b) − b ≤ 0 故由连续函数的介值定理，至少存在 即存在φ的不动点 * * * * x ∈[a,b]使ψ (x ) = 0,即ϕ(x ) = x * x 又设 ( ) 1, ( ) , [ , ] ( ) ( , ), *2 *1 Φ′ ≤ < Φ ∈ Φ ∈ x L x x x a b x C a b 且 有两个不动点 。注意 ( ) ( ) ( )( ) *2 *1 *2 *1 *2 *1 x − x = Φ x − Φ x = Φ′ ξ x − x (1 ( )) 0 0 *2 *1 *2 * − Φ′ ξ x1 − x = ，得 x − x = , * 2 * 1 x = x Φ(x) 故由微分中值定理 即 有唯一的不动点