不动点迭代法的一般理论(续) 2因 x-x|=((x-)-0x)=(x4-=x511-x 其中§介于x1与x之间,故有 x-x151x1-x15…51x1k=12 因 L<,mxk-x=0,即 lim xk=x,Vxo∈[a,b1 k→0 2004-11-22 16
2004-11-22 16 不动点迭代法的一般理论（续） 2.因 * 1 * 1 * 1 * x x (x ) (x ) ( ) x x L x x k − = Φ k− − Φ = Φ′ ξ k− − ≤ k− − * 1 x x 其中ξ介于 k− 与 之间，故有 xk − x * ≤ L xk−1 − x* ≤ L ≤ Lk x0 − x* , k = 1,2L 因 L 1, lim x x* 0,即 lim xk x*, x0 [a,b]。 k k k < − = = ∀ ∈ →∞ →∞
不动点迭代法的一般理论(续) 3由 x-x|=D(x)-(x-)=(x-xk ≤Lxk-xk15∈(xk,x)c(a,b),k=12,… k+1 =(x-x)-(x1=x k+1-xX ≥x-x k+1-x 由结论2有x1-x≤xk-x 故 -xk+2xk-x k+1-x|≥(1-L)x L k. k+1 1-L k-1 x-x|≤ k-2 证毕 2004-11-22 17
2004-11-22 17 不动点迭代法的一般理论（续） 3.由 , ( , ) ( , ), 1,2,L ( ) ( ) ( )( ) 1 1 1 1 1 ≤ − ∈ ⊂ = − = Φ − Φ Φ′ − − − + L x x x x a b k x x x x x x k k k k k k k k k k ξ － ＝ ξ － * 1 * * 1 * 1 x x (x x ) (x x ) x x x x k+ − k = k − − k+ − ≥ k − − k+ − * * 1 x x L x x 由结论2有 k+ − ≤ k − 故 * * 1 * 1 x x x x x x (1 L) x x k − k+ ≥ k − − k+ − ≥ − k − 即 1 1 * 1 1 1 + − − − − ≤ − k − ≤ k k k k x x L L x x L x x 1 2 1 0 2 * 1 1 x x L L x x L L x x k k k k − − − ≤ ≤ − − ≤ − − L 证毕
不动点迭代法的一般理论(续) Remark1:若(x)为定义在区间[a,b]上的函数, 且wx∈[ab,均有φ(x)∈[a,b],则称(x)为区间a,b] 自身上的一个映射。若(x)为区间[a自身上的一个 映射,且彐0<L<13x,x2∈[a,b 0x)-0(x2)≤Lx-x2 则称φ(x)为区间[a,b上的一个压缩映射,L为 Lipschitz常 数。关于压缩映射有如下结论: (1)若(x)为区间[a,b]上的压缩映射,则称φ(x)必为区 间[anb]上的连续函数 (2)若(x)为区间[ab自身上的映射,φ(x)∈Cab 且(x)L<1,则(x)必是区间[ab上的一个压缩映射 2004-11-22 18
2004-11-22 18 不动点迭代法的一般理论（续） Remark1：若φ(x)为定义在区间[a,b]上的函数， 且 ，均有φ(x)∈ [a,b]，则称φ(x)为区间[a,b] 自身上的一个映射。若φ(x)为区间[a,b]自身上的一个 映射，且 ∀x∈[a,b] 0 1, , [ , ] ∃ < L < ∋ x1 x2 ∈ a b 1 2 1 2 φ(x )−φ(x ) ≤ L x − x 则称φ(x)为区间[a,b]上的一个压缩映射，L为Lipschitz常 数。关于压缩映射有如下结论： （1）若φ(x)为区间[a,b]上的压缩映射，则称φ(x)必为区 间[a,b]上的连续函数。 （2）若φ(x)为区间[a,b]自身上的映射，φ(x)∈C[a,b] 且 ， φ′(x) ≤ L <1 则φ(x)必是区间[a,b]上的一个压缩映射
不动点迭代法的一般理论(续) Remark2:不动点定理还可以叙述为:若φ(x)为定义 在区间[ab上的压缩映射,则φ(x)在区间[a,b]上存在 唯一的不动点。 Remark3:不动点定理的两个误差估计式实际上给出 了迭代收敛的两个准则:事后误差估计与事先误差估 计(利用估计式预先求出迭代次数k) Remark4:由不动点定理知,若L≈1,则{xk}必然收敛 较慢;若L<1,则收敛速度快。 Remark5:不动点定理给出的是区间[an,b]上的收敛性, 称之为全局收敛性。(判定困难) 2004-11-22 19
2004-11-22 19 不动点迭代法的一般理论（续） Remark2：不动点定理还可以叙述为：若φ(x)为定义 在区间[a,b]上的压缩映射，则φ(x)在区间[a,b]上存在 唯一的不动点。 Remark3：不动点定理的两个误差估计式实际上给出 了迭代收敛的两个准则：事后误差估计与事先误差估 计（利用估计式预先求出迭代次数k）。 Remark4：由不动点定理知，若L≈1，则{xk}必然收敛 较慢；若L<<1，则收敛速度快。 Remark5：不动点定理给出的是区间[a,b]上的收敛性， 称之为全局收敛性。（判定困难）
、局部收敛性及收敛阶 1.局部收敛性 (1)定义:若存在φ的不动点x的闭邻域 N(x)=[x-6,x+6(>0)使对任意 x∈N(x)选代xk1=(x,k=012,…产生的迭 代序列{x}均收敛于x,则称求x的迭代法 x1=Φ(x),k=012,…在x附近局部收敛 (2)局部收敛性的判别 定理2.设x为φ(x)的不动点,Φ(x)在x的 某个邻域连续,且Φ(x)≤L<1,则迭代式收敛 2004-11-22 20
2004-11-22 20 三、局部收敛性及收敛阶 1. 局部收敛性 （1）定义：若存在φ的不动点 的闭邻域 使对任意 产生的迭 ( ) [ , ]( 0) * * * N x = x − δ x + δ δ > x0 ∈ N(x* ),迭代xk+1 = Φ(xk ), k = 0,1,2,L * x 代序列 均收敛于 ，则称求 的迭代法 在 附近局部收敛。 { }k x * x * x xk+1 = Φ(xk ), k = 0,1,2,L * x （2）局部收敛性的判别 定理2. 设 为x* φ（x）的不动点，Φ′(x)在 的* x 某个邻域连续，且Φ′(x) ≤ L < 1，则迭代式收敛