解x=g(x)的简单迭代法

若等号成立,则表示a是根或者b是根,[a,b]上已有根存在了, 若等号成立,则表示a是根或者b是根,[a,b]上已有根存在了,对于 上已有根存在了 一般情况,由根的存在定理 由根的存在定理， 一般情况 由根的存在定理， h( x) = 0在 [a , b] 上至少存在一个根 x*, 即x = g(x) 在[a,b]上至少存在一个根 x*, 即 h( x* ) = g( x* ) − x* = 0. [a,b]上至少存在一个根 * * * * * 设 [a,b]上另一根 上另一根, 下证唯一性， y 为 x = g(x)在[a,b]上另一根,则 y = g( y ),x = g(x ), 下证唯一性， y* − x* = g( y* ) − g( x* ) ≤ L y* − x*， ∴ y * = x *。 从而 20 由条件(1)知 { xk } 适定的，另外 适定的， 由条件(1)知
定理3 (压缩不动点定理或压缩映象定理) 若迭代函数g(x)满足 定理3 压缩不动点定理或压缩映象定理) 若迭代函数g(x)满足 g(x) (1) g( x ) ∈ [a , b], ∀x ∈ [a , b] (3.3) ( 2)∃0 < L < 1, 使∀x′, x′′ ∈[a, b] 有g( x′) − g( x′′) ≤ L x′ − x′′ (3.4)
k →∞
k ←∞
即 x * 是 ( 3 . 2 )的解 。g(x)把定义域的每个 映成了 把定义域的每个x 把定义域的每个 映成了g(x)，因此 ( 3 .2 ) ， 的不动点。 的解也称 g ( x ) 的不动点。 也可理解成： 是映射， 也可理解成：g(x ) 是映射，若 x* 满足 x* = g( x* ), 则 x * 称为 g ( x )的不动点。 的不动点。 适定是收敛必要条件 即不适定则一定不收敛 必要条件， 适定则一定不收敛。 注: 适定是收敛必要条件，即不适定则一定不收敛。
a ≤ x ≤b
x ∈[ a , b ]
邻近讨论， 因此有局部收敛定理4 实际计算中往往只在根 x 邻近讨论， 因此有局部收敛定理4： 若 （ 定理4 局部收敛定理） 定理4 局部收敛定理） g ( x ) 在不动点 x * 的 δ 邻域满足 ∀x ∈ [ x* − δ , x* + δ ], 有 g ( x ) − g ( x * ) ≤ L x − x * ,( 3 . 7 ) 0 < L < 1, * ∀x0 ∈ [ x* − δ , x* + δ ], 由 xk +1 = g( xk ) 产生的序列{ x k } 收敛于 x , 则 x* − xk ≤ Lk x* − x0 , k = 0,1,⋯. ( 3 .8 ) 且有误差估计： 且有误差估计： 证明： 证明：∀k ≥ 1, x* − xk = g( x* ) − g( xk −1 ) ≤ L x* − xk −1 ∴ x* − x1 ≤ L x* − x0 ≤ Lδ < δ，
0
1 Lk ( 30 有误差估计 : x * − xk ≤ xk + 1 − xk ≤ x1 − x0 ； 3.5 ) 1− L 1− L * x − xk + 1 0 * 4 若g′( x )存在, 则 lim * = g′( x* ) k →∞ x − x k (3.4) g( x′) − g( x′′) ≤ L x′ − x′′ * g(x ) g(xk ) 证明： 证明：
几何意义 x=g(x)的根 求x=g(x)的根
⇔ 求
0 < g′(x*) <1 y
p0
p1
p2
y=x
y = g ( x)
y
− 1 < g ′( x ) < 0
*
p0
p2
→
xk → x* ⇔ 迭代法收敛 ←
xx*p1来自y=xy = g(x)
* 0 x 0 x1 x 2 x
g ′( x ) > 1
*
h(a ) = g(a ) − a ≥ 0, h(b) = g(b) − b ≤ 0,
x* − xk +1 = g( x* ) − g( xk ) ≤ L x* − xk , k = 0,1,⋯， * ⇒ x* − xk ≤ Lk x* − x0 → 0， ∴ lim x k = x 。 k→∞
k →∞
1 0 x = g ( x ) 在 [ a , b ]内有唯一解 x *； 则 0 2 对∀xo ∈ [a , b]由xk + 1 = g( xk )得到的{ xk } ⊂ [a , b], 且 lim xk = x *； k →∞ 0 证明：1 作 h( x ) = g ( x ) − x ,由(1), 得 h( x ) ∈ C [a , b ], 且 证明：
问题: 由g ( x k ) = x k + 1 , 求 x k + 1，然而 x k 是否是g(x)定义域上的值? 问题: 是否是g(x)定义域上的值? g(x)定义域上的值 定义4 保持有界, 且全在g(x)定义域内, g(x)定义域内 定义4 若迭代序列 { x k } 保持有界, 且全在g(x)定义域内,则 lim xk = x* . 则简单迭代 简单迭代法(3.2)称为适定 (3.2)称为适定的 若进一步有 k → ∞ 简单迭代法(3.2)称为适定的； 称为收敛 法(3.2)称为收敛的。 称为收敛的 迭代公式 x k + 1 = g ( x k ), k = 0,1,⋯ ( 3 . 2 ) 当迭代(3.2)收敛时, 又是g(x)的连续点, g(x)的连续点 当迭代(3.2)收敛时,极限点 x * 又是g(x)的连续点,则 (3.2)收敛时 * = g( lim xk ) = g( x * ) x = limxk +1 = lim g ( xk ) k →∞
x* − xk ≤ x* − xk +1 + xk +1 − xk ≤ L x* − xk + xk +1 − xk 3 ∀ k ≥ 0， 1 * xk+1 − xk . (3.4) ∴ x − xk ≤ 1− L xk +1 − xk = g( xk ) − g( xk −1 ) ≤ L xk − xk −1 ≤ ⋯ ≤ Lk x1 − x0 , 又 Lk ∴ x* − xk ≤ x1 − x0 . 导数的定义） 1− L （导数的定义） * * x − xk +1 g( x ) − g( xk ) 0 lim * = lim = g′( x* ). 4 k ＃ * k →∞ →∞ x − x x − xk k 注： 从定理的结论3知，L越小收敛越快，L叫做渐进收敛因子。 (1)从定理的结论 越小收敛越快， 叫做渐进收敛因子 渐进收敛因子。 (1)从定理的结论3
§3 解x=g(x)的简单迭代法 x=g(x)的简单迭代法
3.1 简单迭代法公式
问题: f(x)实函数 实函数. f(x)=0的近似值 的近似值。 问题: f(x)实函数.求f(x)=0的近似值。 基本思想方法： 基本思想方法： ( 3 .1 ) x = g( x ) (1)先将f(x)=0化为等价方程 (1)先将f(x)=0化为等价方程 先将f(x)=0 (2) 从某 x 0 出发,作序列 { x k } : 出发, 初始近似 x = g ( x ), k = 0,1,⋯ 迭代公式) (迭代公式) ( 3 . 2 ) k +1 k k+1次近似 次 f(x)=0的根 的根。 若 { x k } 收敛于 x* 且 g ( x ) 连续,则 x * 是f(x)=0的根。 连续, 称 (3.2)式称为简单迭代法或单点迭代法或单步迭代法。 g(x)称 (3.2)式称为简单迭代法或单点迭代法或单步迭代法。 式称为简单迭代法 迭代函数。 为迭代函数。 说明: f(x)=0化成等价方程x=g(x)的化法有很多种 化成等价方程x=g(x)的化法有很多种。 说明: 由f(x)=0化成等价方程x=g(x)的化法有很多种。 讨论的问题: 如何选取迭代函数g(x)？ 迭代函数g(x) 讨论的问题: (1) 如何选取迭代函数g(x)？ g(x)满足什么条件 迭代序列收敛？收敛速度是多少？ 满足什么条件， (2) g(x)满足什么条件，迭代序列收敛？收敛速度是多少？ 如何加速迭代序列的收敛速度 迭代序列的收敛速度？ (3) 如何加速迭代序列的收敛速度？
分析: 结论(1) (1)中 有唯一根,因此想到根的存在性定理, 分析: 结论(1)中 x = g(x)有唯一根,因此想到根的存在性定理, 连续条件。 (3.4)实际是 (3.4)实际是Lip .z .连续条件。
1 0 x = g ( x ) 在 [ a , b ]内有唯一解 x *； 20 对∀xo ∈ [a , b]由xk + 1 = g( xk )得到的{ xk } ⊂ [a , b], 且 lim xk = x *； k →∞ 1 Lk 0 * ( 3 有误差估计 : x − xk ≤ xk + 1 − xk ≤ x1 − x0 ； 3.5 ) 1− L 1− L x * − xk + 1 收敛程度） （收敛程度） 0 ′( x* )存在, 则 lim * ′( x* ) 4 若g =g 收敛速度） （收敛速度） k →∞ x − x k
注： 1 3 3 3 ′( x) = x2在 −1 1] (2)定理 不是必要条件, 定理3 [ ， (2)定理3不是必要条件,如 x − 2x = 0 ⇔ x = x ⇒ g 2 2 是解， 只要 x0 取在0 上不满足定理3的条件（ ），实际上 取在0 上不满足定理3的条件（2），实际上 x = 0 是解， 可以满足。 附近， （－1 附近，把（－1，1）缩小使 g′( x ) ≤ L < 1可以满足。 3.4)式的条件较难验证，常采用导数来代替。即有推论1 (3.4)式的条件较难验证，常采用导数来代替。即有推论1 ： 3.4） 推论1 定理3 推论1 定理3 中（3.4）可用下式替代 max g ′( x ) ≤ L < 1 ( 3.4)′ 证明： 证明： 只证 (3.4)′ ⇒ (3.4), 因 ∀x′, x′′ ∈ [a , b], g( x′) − g( x′′) ≤ g′(ξ ) x′ − x′′ ≤ max g′( x ) x′ − x′′ ≤ L x′ − x′′ . ＃ 思考： 思考：3.4)′不成立时结论是否成立 ？ 不一定 ( 因此该推论是充分条件但不是必要条件。 若 ( 3 . 4 )′ 不成立时,则 因此该推论是充分条件但不是必要条件。 不成立时 则 需要判断(3.4) (3.4)。 需要判断(3.4)。