haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 初中数学初中数学

第二章 方程求根2

发布时间:2014-07-05 13:39:27  

§4 迭代收敛的加速方法 /* Accelerating Method*/
Def 1

(收敛阶/*the order of Convergence*/)

? ? e ? x ? x x 设序列? k ? 收敛到 x , k ,若存在实数 p ? 1 及常 k ek ?1 ? c ,则称序列 ? xk ?是 p 阶收敛的, 数 c ? 0 ,使 lim p k ?? ek c 称为渐近误差常数。当 p ? 1, ? xk ? 称为线性收敛,

p ? 1 为超线性收敛,p ? 2 时为平方或二次收敛.
注:

p

的大小反映了迭代法收敛的快慢,是收敛速度的一 种

度量。

( p) 定理2:设迭代法的迭代函数 g 的高阶导数 g ( x )( p ? 1) 在不 ? 动点 x 的邻域里连续,则式(*)是 p 阶收敛的充要条件



g( x? ) ? x? , g( l ) ( x? ) ? 0, l ? 1, 2,
ek ?1 1 ( p ) ? lim p ? g (x ) ? 0 k ?? e p! k

, p ? 1, g( p ) ( x? ) ? 0



证明:

充分性

由Taylor公式:

g( xk ) ? g( x? ) ? g?( x ? )( xk ? x ? ) ? 1 1 ( p) ( p ?1) ? ? p ?1 ? g ( x )( xk ? x ) ? g (? )( xk ? x? ) p ( p ? 1)! p!

1 ( p) ? ? xk ?1 ? x ? g (? )( xk ? x ? ) p p!
取极限得

? 介于 xk、x 之间
?

ek ?1 1 ( p ) ? lim p ? g (x ) ? 0 k ?? e p! k

必要性
k ??

? 设迭代式(*)是 p 阶收敛的,则有 lim xk ? x k ??

即 lim ek ? 0

且 x ? g( x )

?

?

(反证法)设结论不成立

则存在最小正整数

p0 (? p) 满足

g( l ) ( x? ) ? 0, l ? 1, 2, , p0 ? 1, g( p0 ) ( x? ) ? 0 情形一 p0 ? p ? 1 由充分性证明知,迭代式(*)是 p0 阶收敛的 ek ?1 1 ( p0 ) ? g ( x ) ( p0 ? p ? 1) 即 lim p ? 0 k ?? e ( p0 )! k


ek ?1 ek ?1 1 ? p0 ? p ? p0 p ek ek ek

的极限不存在

与 p 阶收敛矛盾

情形二 p0 ? p ? 1

证明方法与情形一类似(自己练习)

本节讨论迭代法加速收敛问题,常用于线性收敛迭代法 一、使用两个迭代值的组合方法:

当?

1 [ g( xk ) ? ? xk ], k ? 0,1, 2, 相应的迭代公式为 xk ?1 ? 1? ?
或者 xk ?1 ? g ( xk ) ?

将 x = g(x) 等价地改造为 (1 ? ? ) x ? g( x ) ? ? x 1 g( x ) ? ? x ? , ? ? 0 和 ? ? 1 时,有 x ? 1? ?

?

1? ?

[ g( xk ) ? xk ], k ? 0,1, 2,

选取特殊的 ? ,有可能使迭代加速。

如: ? ? ?1

1 迭代公式为 xk ?1 ? [ g ( xk ) ? xk ] k ? 0,1, 2, 2
y

几何意义如图示

y = g(x)

y=x

注: 这种迭代对原 迭代公式(*)的各近 ? x 似值在根 的两侧 ? 往复地趋于 x 时较 为有效;
xk
x* xk ?1
中 点

x

g( xk )

又如: ? ? g?( x )
?

x?

1 ? ? g ( x ) ? ? [ g ( x ) ? g ( x ) x] 新的迭代函数为 ? 1 ? g?( x )
? 当 g?( x ) ? 1时 g?( x ) ? 0 ?

1 g( x ) ? ? x ? ? g ( x ) ? 1? ?

根据定理知,迭代法至少是二阶的。
? ? ? 但由于 x 不知道,故 g?( x ) 也得不到,因此

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com