当前位置：文档之家 › 5_6+迭代法的收敛阶和AitKen加速方法1

5_6+迭代法的收敛阶和AitKen加速方法1

  • 格式：pdf
  • 大小：52.48 KB
  • 文档页数：4
§6 迭代法的收敛阶和 AitKen 加速方法 一、 迭代法的收敛阶
定义：对于方程 x = g ( x ) ，若迭代过程 xk +1 = g ( xk )（初 值为 x0 ）收敛于 x* ，且
| x* − xk +1 | =c≠0 lim * k →∞ | x − x | p k
其中 p ≥ 1 ，则称迭代过程 p 阶收敛。当 p = 1 （这时 要求 0 < c < 1 ）时称为线性收敛；当 p ≥ 1 时称为超线 。 性收敛；当 p = 2 时称为二次收敛（平方收敛）
( xk +1 − xk +1 ) 2 ⇒ x * ≈ xk − xk + 2 − 2 xk +1 + xk ˆ ⇒ xk ( xk +1 − xk +1 ) 2 xk − xk + 2 − 2 xk +1 + xk
xk 收敛于 x* 的速度要快。 一般说来比
2． AitKen 加速方法
⎧迭代: yk = g ( xk ), zk = g ( xk ) ⎪ ( y k − xk ) 2 ⎨ ⎪加速: xk +1 = xk − z − 2 y + x k k k ⎩
k = 0,1, 2,
注： 1） p 是衡量迭代过程收敛快慢的指标， p 越大， 收敛越快， p 越小，收敛越慢；
g ′( x* ) ≠ 0 时，为线性收敛； 2）一般迭代法，当
3）牛顿法在单根附近为二次收敛。
二、 AitKen 加速方法 1． 推导 设
x* − xk +1 = c (0 < c < 1) lim xk = x* , 且 lim * k →∞ k →∞ x − x k x* − xk +1 ⇒ * ≈c x −ห้องสมุดไป่ตู้xk x* − xk + 2 x* − xk +1 ⇒ * ≈ * x − xk +1 x − xk

合集下载

牛顿迭代的艾特金加速

牛顿迭代的艾特金加速

牛顿迭代的埃特金加摘要：牛顿迭代法是求解非线性方程的一种有效的方法，在通常情况下至少有平方收敛。

运用牛顿迭代法不仅关心它的收敛与否，同时还要关心它的收敛速度。

现存的关于牛顿迭代加速收敛的文献有很多。

参阅本文试图通过用埃特金算法，来加速牛顿迭代的收敛速度。

关键词：牛顿迭代、加速收敛 、特金加速相关知识1. 埃特金算法对于一般的方程()0f x =,将它改写成：()x x ϕ=的形式，式中()x ϕ称为迭代函数。

由此得到的迭代公式：1()k k x x ϕ+=埃特金算法是将迭代1()k x x ϕ+=值再一次进行迭代，即 11()k k x x ϕ++=。

最后得到的公式：2111111()2k k k k k k kx x x x x x x ++++++-=--+。

2. 牛顿迭代法对于一般的方程f(x)=0,在近似根k x 附近用一阶泰勒多项式'()()()()k k k p x f x f x x x =+-来近似代替()f x ;取()0p x =的根作为()0f x =的新的近似根，记着1k x +；可以得到：1'()()k k k k f x x x f x +=-；这就是牛顿迭代公式。

牛顿迭代的埃特金加速 在这里用'()()()k k k f x x x f x ϕ=-来代替埃特金算法中的()x ϕ，即可得到 1'()()k k k k f x x x f x +=- （1）'1'''()()()()()()()()k k k k k k k k k k f x f x f x f x x x f x f x f x f x +-=--- （2）2111111()2k k k k k k kx x x x x x x ++++++-=--+（3）分别把（1）、（2）式代入（3）式中，这样就得到了牛顿迭代的埃特金加速格式：'1'''()()()()()()()()k k k k k k k k k k f x f x f x f x x x f x f x f x f x +-=----2''''''''''()()()()()()()()()()()()()()()2()()()()()k k k k k k k k k k k k k k k k k k k kk k k k k f x f x f x f x f x x x f x f x f x f x f x f x f x f x f x f x x x x f x f x f x f x f x ⎛⎫⎛⎫- ⎪ ⎪⎛⎫ ⎪ ⎪---- ⎪ ⎪ ⎪⎝⎭- ⎪ ⎪⎝⎭⎝⎭⎛⎫- ⎪⎛⎫⎪----+ ⎪ ⎪⎝⎭- ⎪⎝⎭ 数值验证求方程3270x -=我们知道此方程的精确解为3。

§4迭代法的加速法

§4迭代法的加速法

§4 迭代法的加速法(加速收敛技巧)
4.1 Aitken(埃特金)加速方法
设
假1)设x简k 单klxi迭m*,代kxxkk序10列x,x1*{*,xkc,}(线,若性0等收号c敛成 1于立x,*则, 即xk
(4.1)
x* ,是精确解)
2) xk2 2xk1 xk 0,k 0,1,. (若等号成立,则{ xk }不收敛.因为
x0 x1
x1 x* x3 x2 x0
从图中可以看出 x3
x
~x0
比 x2 更接近于 x*.
说明: (1)这里的 x3 并不是简单收敛列 {xk }k 0 中的 x3.
(2)对某些不收敛的情况,用埃特金方法“加速”也有可能收敛.
4.2 Steffenson迭代方法
在埃特金加速法中, 只要有三个相邻点就可以进行加速,把 简单迭代与埃特金加速方法结合起来可建立Steffenso迭代方法.
x* x*
0.
比x：*原klim简 x单xkk序1列xx*{*xk }c更, 快0 地c收敛1 于x*.
(4.3)
ek2 ek2 ek ek ek 1 ek＋1
分析: 该定理的证明用数学分析中证明极限的技巧.
证明: 记ek xk x* ,
由 (4.2) 得
x* x*
则有
lim ek1 c, lim ek2 c2.k xk
则
x~k x*
x* 2x*
x~k xk
x* x*
xk
x*
( xk1 xk )2 xk2 2xk1
( ek 1 1)2
xk
1
ek 2
ek 2 ek1
1
x*
1
ek
(ek1 ek ek2 2ek1
62不动点迭代法及其收敛定理

62不动点迭代法及其收敛定理


)
xk 1
x
*
( xk
x*)( 1
mg (xk
)
g(xk ) (xk x*)g(xk
) )
lim xk 1 x * k xk x *
lim(1
g(xk )
)
k mg ( xk ) ( xk x*)g( xk )
1 1 m
m 2时,1 1 0 m
由定义1
该迭代法对 m( 2)重根是线性收敛的
x4 = 0.9990
同样的方程
不同的迭代格式
有不同的结果
x5 = 0.9998 x6 = 1.0000
迭代函数的构造有关
x7 = 1.0000 已经收敛,故原方程的解为
x 1.0000
什么形式的迭代法
能够收敛呢?
如果将(2)式表示为 yx
yx
y (x)
与方程(2)同解
yx
y (x)
收敛
则f (x)在[a,b]上单调递增 , f (x) 0在[a,b]上仅有一个根
所以 1o. 方程x (x)在[a,b]内有唯一解 x *
2o. 对于迭代法 xk 1 ( xk ),
由微分中值定理
xk 1 x * (xk ) (x*) ( )( xk x*)
xk 1 xk (xk ) (xk 1 ) ( )( xk xk 1 )
定理3. 如果迭代法迭代函数 (x)在根x * 附近满足：
(1) (x)存在p阶导数切连续；
(2) (x*) (x*) ( p1)(x*) 0,
而 ( p)( x*) 0
则迭代法 xk 1 (xk )的收敛阶是 p
例 用迭代法求解方程 2x3 x 1 0
解:本题迭代函数有两种构造形式
迭代法的收敛性

迭代法的收敛性

k
x* Mx* g 由迭代公式有 M (x
k k
x ( k ) x* Mx ( k 1) g Mx* g
( k 1)
x ) M (x
* 2 * k
( k 2) (k )
x ) M (x
* k
(0)
x )
*
于是有 lim M ( x
1 1 例：Ax b, A 2 1 2
1 2 1 1 讨论用三种迭代法求解的收敛性。 2 1 1 2 解：因A为对称且其各阶主子式皆大于零，故A为对称正定矩 1 2 阵。由判别条件3，Gauss-Seidel迭代法与松弛法(0 2) 均收敛。A不是弱对角占优阵，故不能用条件1判断。 0 1 -1 Jacobi迭代法的迭代矩阵为B I - D A 2 1 2 1 2 0 1 2 1 2 1 2 0

1,
1,由推论1无法判别收敛性。
对一些特殊的系数矩阵可给出几个常用的判 别收敛条件
设有线性方程组Ax b, 下列结论成立（收敛充分条件） 1.若A为严格对角占优阵或不可约弱对角占优阵，则 Jacobi迭代法和Gauss-Seidel迭代法均收敛。 2.若A为严格对角占优阵， 0 1, 则松弛法收敛。 3.若A为对称正定阵，则松弛法收敛的充要条件为 0 2。 10 1 2 2 1 0 B 1 2 1 上两例中： A 1 10 2 1 1 5 0 1 2 A为严格对角占优阵，故Jacobi与Gauss-Seidel迭 代均收敛。B为非严格对角占优阵，但为对称正定 阵， =1.4故松弛法收敛。
推论1 对任意初始向量x 和右端项g，若 M 1,由迭代