当前位置：文档之家 › 2.2 迭代法的一般形式与收敛性定理

2.2 迭代法的一般形式与收敛性定理

  • 格式：ppt
  • 大小：367.00 KB
  • 文档页数：16

下载文档原格式

  / 16

合集下载

37第七节 迭代法及其收敛性

37第七节 迭代法及其收敛性
x(k) x q x(k) x(k1) 1q
x(k) x qk x(1) x(0) 1q
证 因 (B)||B||=q<1, 所以迭代格式收敛, 且有 设 lim x (k) =x*，由 x(k+1) = Bx(k) + f ， 得 x* = Bx* + f ，则
数学学院 信息与计算科学系
又 || Bk|| ||B||k ，有 lim||Bk||=0 ， 故 lim B k =0，由1）知，迭代格式收敛。
数学学院 信息与计算科学系
三、迭代法的收敛速度
考察误差向量
e(k) =x(k) -x＊=Bk ·e(0)
设B有n个线性无关的特征向量及相应的特征值为
1 ,2 , ,n ,
1 , 2 , , n
数学学院 信息与计算科学系
2） 由1)知，迭代格式收敛 lim Bk=O ， 即lim||Bk||=0 ，从而存在 k ，使 || B k || <1，由谱半径 的性质有
[( B )]k = (B k ) ||B k ||<1，
故得
( B )<1，
因(B)=inf{||B||}且(B)<1，存在 >0及使 || B || ( B )+ <1，
取对数得 定义3 称
k s ln10
ln (B)
R(B) ln (B)
为迭代法 x(k+1) = Bx(k) + f 的收敛速度。 由此看出，当(B)<1愈小，速度R(B)就愈大，
所需要的迭代次数也就愈少。
数学学院 信息与计算科学系
定理 2 若 ||B||=q<1，则对任意x(0) 迭代格式 x(k+1) = Bx(k) + f 收敛 ，且有误差估计式

2.2 迭代法

2.2 迭代法

= ϕ ' (ξ )( x * − x * *) ≤ L x * − x * *
又， L < 1
⇒ x* = x * *
计算方法
② ∀x0 ∈ [a, b] 则 xk +1 − x *= ϕ ( xk ) − ϕ ( x*) = ϕ ' (ξ )( xk − x*)
≤ L xk − x * ≤ L2 xk −1 − x * x k +1 − x *
计算方法
二、收敛性分析
定理2.1 （全局收敛定理） 全局收敛定理） 定理
在区间[a,b]上可导 上可导 设ϕ ( x )在[a, b] 在区间
a （1）当a ≤ x ≤ b时， ≤ ϕ ( x ) ≤ b;
( 2) ∀x ∈ [a, b], | ϕ ' ( x ) |≤ L < 1 ( L为常数） 为常数）
ϕ ′( x ) ≤ L < 1
计算方法
则对于任意的初始值 x0 ∈ S ，由迭代公式 收敛于方程的根。 产生的数列 { xn } 收敛于方程的根。 （这时称迭代法在 α 的S邻域具有局部收敛性。） 邻域具有局部收敛性。）
x n +1 = ϕ ( x n )
Remark1：全局与局部收敛定理中的条件都是充分 Remark1： 条件，条件满足则迭代法收敛，不满足则不能判定， 条件，条件满足则迭代法收敛，不满足则不能判定， 此时可以用试算来判定迭代法的是收敛性。 此时可以用试算来判定迭代法的是收敛性。
p! p!
由迭代公式 xk +1 = ϕ ( xk ) 及 x * = ϕ ( x * ) 有 ϕ ( p ) (ξ ) * * p
′( x* ) = ϕ ′′( x* ) = L = ϕ ( p−1) ( x* ) = 0, ϕ ( p ) ( x* ) ≠ 0 ϕ 邻域是p阶收敛的。 则迭代过程在 x * 邻域是p阶收敛的。

数值分析第四章 解非线性方程的迭代法

数值分析第四章 解非线性方程的迭代法

即
(xk+1-α)2≈(xk-α)(xk+2-α) xk+12-2xk+1α+α2≈xkxk+2-(xk+xk+2)α+α2
解得
x k x k + 2 x k2+1 α≈ x k + 2 2 x k +1 + x k
( x k +1 x k ) 2 = xk x k + 2 2 x k +1 + x k
可见,|xk-xk-1|充分小可保证|xk-α|充分小, 而且对任 一ε>0,要使|xk-α|<ε, 只要 k > ln ε (1 L) ÷ ln L x1 x 0
证 记(x)=(x)-x,则(a)=(a)-a≥0, (b)=(b)b≤0, 由(x)的连续性,必存在α∈[a,b]使(α)=(α)-α=0, 即α=(α), 又′(x)=′(x)-1<0, 所以x=(x)的根唯一. |xk+1-xk|=|(xk)-(xk-1)| =|′(ξ)(xk-xk-1)|≤L|xk-xk-1| |xk+1-α|=|(xk)-(α)|=|′(ξ)(xk-α)|≤L|xk-α| |xk-α|=|(xk-xk+1)+(xk+1-α)| ≤|xk-xk+1|+|xk+1-α|≤L|xk-xk-1|+L|xk-α| 于是有:
k 0 1 2 3 4 5 xk 0.5 0.60653 0.54524 0.57970 0.56006 0.57117 |xk-xk-1| 0.10653 0.06129 0.03446 0.01964 0.01111 k 6 7 8 9 10 xk 0.56486 0.56844 0.56641 0.56756 0.56691 |xk-xk-1| 0.00631 0.00358 0.00203 0.00115 0.00065

迭代法和收敛性

迭代法和收敛性

x1(k x2(k
1) 1)
0.2x2(k) 0.1x3(k) 0.3
0.2x1(k )
0.1x3(k) 1.5 , k
0,1, 2,
x3(k
1)
0.2x1(k )
0.4x2(k )
2
迭代计算
x(0) 0 [0, 0, 0]T
x(1) 1
0.3
x(1) 2
1.5
x1(k x2(k
其中系数矩阵非奇异，且主对角元aii≠0，(i
=1,2,…,n)，由第i 个方程解出xi，有
x1
1 a11
(b1
a12 x2
a13 x3
x2
1 a22
(b2
a21x1
a23x3
xn
1 ann
(bn
an1x1
an2 x2
a1n xn ) a2n xn )
ann1xn1)
建立迭代格式
aij
x
( j
k
)
)
j i 1
加速
x ( k 1) i
( k 1)
xi
(1 ) xi(k )
i 1, 2, , n
或合起来写成迭代加速的形式
x (k 1) i
aii
(bi
i 1
a x (k 1) ij j j 1
n
aij
x
(k j
)
)
(1
)
xi( k
)
j i1
参数 称为松弛因子， 1 时迭代格式就是高斯-
x (k1) i
1 aii
(bi
n
aij x j(k ) ),
j1
(i 1,2,, n)

迭代法的收敛性

迭代法的收敛性
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,由迭代

迭代法的收敛性

迭代法的收敛性

即
det[I (D L)1U ] 0
从而 det(D L)1 det[(D L) U ] 0
所以
det[(D L) U ] 0
可得
因为
|aii| |aij | ji
i1
n
|||aii||| |aij ||| |aij |
j1
j i 1
i1
n
n
|| |aij| |aij| (||1) |aij|
(1)写出解该方程组旳Jacobi迭代旳迭代
阵，并讨论迭代收敛旳条件；
(2)写出解该方程组旳G-S迭代旳迭代阵， 并讨论迭代收敛旳条件。
17
补充例题
例：AX=b为二元线性方程组， 证明：解该方程组旳Jacobi迭代与G-S迭 代同步收敛或同步发散。
18
9
特殊方程组迭代法旳收敛性
4 1 1 问题：该矩阵具有怎样旳特点？
2 5 1 1
2
3
结论：该矩阵是严格对角占优阵
定义：假如矩阵A旳元素满足
jn
| aii | | aij | i 1,2,3,, n j 1 ji
则称A为严格对角占优矩阵。
10
特殊方程组迭代法旳收敛性
定理：若线性方程组AX=b旳系数矩阵A为 严格对角占优矩阵，则解该方程组旳Jacobi 迭代法和G-S迭代法均收敛。
2
一阶定常迭代法旳收敛性
则: (k 1) B (k ) B 2 (k 1) B k 1 (0)
注意 (0) x(0) x * 为非零常数向量
所以迭代法收敛旳充要条件
lim (k1) lim( x(k1) x*) 0
k
k
可转变为
lim Bk1 0

2.2 迭代法

* lim | x xk | 0 要证结论(1)成立，即要证 k
首先用归纳假设证明如下不等式
| x* xk | Lk | x* x1 |
38
当k=1时 x x1 L x x0 ，已证成立。
k 1 x x L x x0 成立，可得 假设 k 1
不动点迭代的几何解释 y=f(x)=x y=g(x)
38
不动点判定定理
设g是一连续函数，且 { pn } 是由不动点迭代 n 0
生成的序列。若 lim pn p ，则p是g(x)的不动点
n
pn 1 p pn p ，则 lim 证：lim n n
g ( p ) g (lim pn ) lim g( pn ) lim pn1 p
1 1 x xk x k 1 x k ( x k ) ( x k 1 ) 1 L 1 L L Lk x k x k 1 x1 x0 1 L 1 L

L越小，收敛越快
38
不动点迭代的图形解释
一般来说从 f ( x ) 0 , 构造 ( x )不止一种，有的
38
由介值定理，存在 x [a , b] 使 f ( x ) 0


即
x ( x ).
②设方程 x ( x ) 还有一根 , 即 a (a ). 则由微分中值定理有
x ( x ) ( ) ( )( x ) L x
x4 2x 2 x 3 0 x 2 ( x)
x 4 1
x 3 ( x) x4 2x2 3
(其中第二式 x4 2 x 2 1=x 4 )

迭代解法全章


向量-矩阵范数旳相容性，得到
|λ| || x ||＝||λx|| =|| Ax|| ≤ || A || ||x||
从而，对A旳任何特征值λ均成立 |λ|≤|| A ||
（6.1）
设n阶矩阵A旳n个特征值为λ1,λ2，…λn。称
(
A)
max
1i n
i
为矩阵A旳谱半径，从（6.1）式得知，对矩阵A旳任何一
称(3)为求解(1)旳近似解旳迭代解法，称{x(k)}为(1)近
似解序列，称B为迭代矩阵。
假如 lim x (k ) x* 则有 k x*= Bx*+F
（4）
我们称迭代法(3)收敛，不然为发散。下面分析迭代格 式(3)收敛旳条件.
12/29/2023
19
x(k+1)= Bx(k)+F , k=0 ,1 , … , x*= Bx*+F
及向量
x*
( x1* ,
x2* ,,
x
* n
)T
假如
lim x(k) x* 0
k
则称向量序列 x(k) 收敛于向量 x* 。记作
lim x(k ) x* 或 x(k ) x*
k
向量序列 {x(k)} 收敛于向量 x*，当且仅当它旳每一 种分量序列收敛于x*旳相应分量，即
x(k)
x*
x(k) i
1
求解线性方程组旳数值解除了使用直接解法，迭代解 法也是经常采用旳一种措施，这种措施更有利于编程计 算，本章将简介这种措施。
§1 向量和矩阵旳范数
为了对线性方程组数值解旳精确程度，以及方程组 本身旳性态进行分析，需要对向量和矩阵旳“大小”引 进某种度量，范数就是一种度量尺度，向量和矩阵旳范 数在线性方程组数值措施旳研究中起着主要旳作用。

Ch2.2 一般迭代法


10 1.3247180
近似解 x9 x10 1.3247180 。 (8位有效)
思考：取 x x 3 1 构造迭代， 结果如何？
问题：如何构造迭代函数，可以保证迭代既
收敛，敛速还快？误差如何估计？
一个好的迭代法需要考虑：

迭代函数的构造； 收敛性、敛速； 误差估计。
迭代法的几何意义
(2) g ( x) x 3 1 , x [ 1 , 2 ] ， g ( x) 3x 2 1 ； 由Th 2 ， 该迭代发散。
2、局部收敛
Th3： 设方程x g ( x)有根x *， 且在x *的某个邻域U ( x * , )内
具有一阶连续导数 ， 则 (1) g ( x * ) 1 ， 局部收敛； (2) g ( x * ) 1， 发散。
y
yx
y g ( x)
o
x
*
x2
x1
x0
x
收敛的情形
y
yx
y g ( x)
o
x0 x 2 x 4
x
*
x3 x1
x
收敛的情形
ห้องสมุดไป่ตู้
y
y g ( x)
yx
x2
o
x1
x0 x *
x
发散的情形
迭代法的收敛条件
1、大范围收敛
Th1：（压缩映象原理）
若g ( x)在 [ a , b ] 上具有一阶连续导数 ， 且满足： 1、 x [ a , b] ， 有g ( x) [ a , b ]； 2 、 常数0 L 1 ， 对x ， y [ a , b ] ， 有 | g ( x) g ( y ) | L x y ；

迭代法

迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法(或者称为一次解法)，即一次性解决问题。

迭代算法是用计算机解决问题的一种基本方法，它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令(或一定步骤)进行重复执行，在每次执行这组指令(或这些步骤)时，都从变量的原值推出它的一个新值，迭代法又分为精确迭代和近似迭代。

比较典型的迭代法如“二分法”和"牛顿迭代法”属于近似迭代法。

方法介绍迭代法是一类利用递推公式或循环算法通过构造序列来求问题近似解的方法。

例如，对非线性方程，利用递推关系式，从开始依次计算，来逼近方程的根的方法，若仅与有关，即，则称此迭代法为单步迭代法，一般称为多步迭代法；对于线性方程组，由关系从开始依次计算来过近方程的解的方法。

若对某一正整数，当时，与k 无关，称该迭代法为定常迭代法，否则称之为非定常迭代法。

称所构造的序列为迭代序列。

迭代法应用迭代法的主要研究课题是对所论问题构造收敛的迭代格式，分析它们的收敛速度及收敛范围。

迭代法的收敛性定理可分成下列三类：①局部收敛性定理：假设问题解存在，断定当初始近似与解充分接近时迭代法收敛；②半局部收敛性定理：在不假定解存在的情况下，根据迭代法在初始近似处满足的条件，断定迭代法收敛于问题的解；③大范围收敛性定理：在不假定初始近似与解充分接近的条件下，断定迭代法收敛于问题的解。

迭代法在线性和非线性方程组求解，最优化计算及特征值计算等问题中被广泛应用。

迭代法算法迭代是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题（一般是解方程或者方程组）的过程，为实现这一过程所使用的方法统称为迭代法（Iterative Method）。

一般可以做如下定义：对于给定的线性方程组（这里的x、B、f同为矩阵，任意线性方程组都可以变换成此形式），用公式（代表迭代k次得到的x，初始时k=0)逐步带入求近似解的方法称为迭代法（或称一阶定常迭代法）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

设aii0 (i=1,2,,n)，并将A写成三部分
0 a11 a 21 0 a 22 A a n 1 ,1 a n 1 , 2 0 a nn a n 2 a n , n 1 a n1 0 a12 a1,n1 a1n 0 a 2 , n 1 a 2 n 0 a n 1, n 0 D LU. 0
则
k
B ( H )
k
两边取对数得: k ln ( H ) ln k
ln ln ( H )
定义:
ln ( H )
为迭代法(2.2.3)的渐近收敛速 度。
解线性方程组的迭代法
线性方程组
a11 x1 a12 x2 a x a x 21 1 22 2 an1 x1 an 2 x2 a1n xn b1 a2 n xn b2 ann xn bn
复习：矩阵的谱半径 设λ是矩阵A相应于特征向量x的特征值，即 Ax＝λx 向量-矩阵范数的相容性，得到 |λ| || x ||=||λx|| =|| Ax|| ≤ || A || ||x|| 从而，对A的任何特征值λ均成立 |λ|≤|| A || （ 3）
设n阶矩阵A的n个特征值为λ1,λ2，…λn，称 ( A) max i
x ( k 1) x* H ( x ( k ) x* )
由此递推：x ( k 1) x* H k 1 ( x ( 0) x* ), k 0,1,2,
x 是线性方程组Ax=b的解
x* Hx* g
x
k 1
*
Hx
k
f
0 x 引理2.1：迭代法对任何初始近似 均收敛的
等价变换
迭代矩 阵
x(k+1)=Hx(k) +f
H 并不是 唯一的, 因此迭代 格式也不 是唯一的!
e. g. A I A I x I A x b
A D A D x I D 1 A x D 1b x D 1 (b Ax ) a ii 0 A L D U x D 1 L U x D 1b aii 0
H
p k
q 1 x R n , lim x x and
0 k k p
x x*
q k k 1 x x 1 q qk 1 0 x x 1 q
p
p
后验估计 Posterior error – estimated 先验估计 Prior error— estimated
0 a12 0 U
a1n a2 n 0
k
0.1 0.5 f , 其中 H ， 0.8 0.1
讨论该迭代法的收敛性。
例2 设 x
k 1
Hx
k
0.9 0 f , 其中 H ， 0.3 0.8
讨论该迭代法的收敛性。
2.2.3 迭代法的收敛速度
定理2.5 当 H 1 时，由迭代法式所定义的 序列 {x( k ) } 满足如下估计式：
x
(k )
x
*
H 1 H
k
x( k ) x( k 1)
x
(k )
H x x (1) x (0) 1 H
*
现在讨论使误差减少初始误差的 倍所需的最 少迭代次数
x
(k )
x H x (0) x *
*
k
(k ) * (0) * x x x x 若要求
kk 1 ， ， k
lim k lim
k k k
k

k
lim
k
1 k
k 1
0.
x 是线性方程组Ax=b的解
x* Hx* g
x
k 1
*
Hx
k
f
0 引理2.1：迭代法对任何初始近似 x 均收敛的 充分必要条件是 H k 0 k
k
2.2.2 迭代法的收敛性
定义 利用迭代公式构造序列 x ( k ) , 以求 得方程组 的近似解的算法称为解式的简单迭代法。 若迭代序列 x ( k ) 收敛，则称此迭代法是收敛的。
x
k 1
Hx
k
f,
x Hx f
* *
k * x x 两式相减，知误差向量 满足下列迭代关系：
充分必要条件是
H k 0k
k H 引理2.2： 0 k 的充要条件是 ( H ) 1
定理2.4：迭代法对任何初始近似均收敛的充分 必要条件是迭代矩阵H的谱半径
( H ) 1
(k ) 定义 设矩阵序列A k (a ij ) R nn , A (a ij ) R nn，若 (k ) lim a a ij ij k
1 i n
为矩阵A的谱半径。
2.2 迭代法的一般形式 与收敛性定理
2.2.1 迭代法的一般形式
已知线性代数方程组
Ax b
首先将方程组改写成等价的形式
x Hx g
从而建立迭代式：
称
x
xபைடு நூலகம்
k 1
为迭代序列，并称H为迭代矩阵。
Hx g k 0,1,2
H k 0 k 的充要条件是 ( H ) 1 引理2.2：
定理2.4：迭代法对任何初始近似均收敛的充分 必要条件是迭代矩阵H的谱半径 ( H ) 1
推论：若 H 1 ( 允许为任何一种相容的矩阵范 数) ，则迭代法收敛。
例1 设 x
k 1
Hx
迭代法思想： 第一步 第二步
将Ax b转化为等价方程组： x Hx f 设x * 为精确解，x* Hx * f
构造迭代格式，任取初 始向量x ( 0 ) , 按逐次代
H 与k无关，称为 入方法构造 { x(k ) } 一阶定常迭代法
x
( k 1 )
Hx
(k )
f
收敛？发散？
( i , j 1,2, , n)
k
则称{ A k }收敛于A，记为lim A k A .
例 设矩阵序列 1 2 2 A 0 , A 0 且 | | 1，考查其极限 .
k 2 k ， , A 2 0
若 lim x ( k ) x*,则称迭代法收敛，且 x * 为方程的解。
k
否则此迭代法发散。
判断收敛的方法：
(k ) (k ) 若 lim || x x * || ＝ lim || || 0, 则此迭代法收敛。 k k
( k 1 )＝x ( k 1 ) x* Hx ( k ) f Hx * f H ( x ( k ) x*) H ( k ) H k 1 ( 0 ) 即有 ( k ) 0, H k 0
即
A=D-L-U
a11 a 21 A a n1 0 a L 21 a n1
a12 a22 an 2
a1n a2 n ann 0
a11 D
a22
ann
0 an 2
计算中判断迭代终止条件的方法：
|| x ( k 1) x ( k ) || , x* x ( k 1)
如何判断迭代法是收敛 的？？
收敛条件
1. lim x k x* lim H k 0
k k
2.
lim H k 0 H 1
x
3.
a11 a12 a a 21 22 an1 an 2
a1n x1 b1 x b a2 n 2 2 ann xn bn
Ax=b
怎样设计迭代格 式? Ax=b x=Hx+f