当前位置：文档之家 › 第6章解线性方程组的迭代法收敛性

第6章解线性方程组的迭代法收敛性

  • 格式：ppt
  • 大小：648.01 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

线性方程组迭代法收敛性分析

线性方程组迭代法收敛性分析
k
lim Ak 0 .
k
(2.27)
由定理 2.5 知，
( A k ) Ak ，
即
( A)
由(2.27) 和(2.28)可得
k
Ak .
(2.28)
lim ( A) 0
k k
再由矩阵谱半径的定义可知一定有 ( A) 1 . （必要性） 若 ( A) 1 ，则有定理 2.5 的推论可知至少存在一个 0 使得一种范数
若有
lim x ( k ) x* , 即 lim xi( k ) xi* ,
k k
则有 lim x ( k ) x*
k 2
0.
常见的向量范数有： ① 1-范数
x 1 xi ；
i 1
n
② ∞-范数
x

max xi ；
1 i n
③ 2-范数
x 2 ( x ) ；
lim x x* lim G k x x* 0 ，
k
0
k


k


再由向量范数的定义可知
lim x k x* 0 ，
k
即迭代过程收敛. （必要性） 若迭代公式(2.20)收敛，即满足
lim x x* 0
k k


由此推论可知当 ( A) 1 时，至少存在一种范数 A 1 .
定 理 2.6 设 A R nn ， 则 lim Ak 0 的 充 要 条 件 为 ( A) 1 . （ 其 中
k
Ak AA A）
k
证明： （充分性） 若 lim Ak 0 ，则由矩阵范数的定义可知

第6章 求解线性代数方程组和计算矩阵特征值的迭代法

第6章 求解线性代数方程组和计算矩阵特征值的迭代法

数值计算与MATLAB1《数值计算与MATLAB 》第6章求解线性代数方程组和计算矩阵特征值的迭代法§1 求解线性代数方程组的迭代法§2 方阵特征值和特征向量的计算§3 矩阵一些特征参数的MATLAB计算《数值计算与MATLAB 》6.1 求解线性代数方程组的迭代法1、迭代法的基本原理如果线性方程组Ax=b的系数矩阵A非奇异，则方程组有唯一解。

把这种方程中的方阵A分解成两个矩阵之差：A=C-D若方阵C是非奇异的，把A它代入方程Ax=b中，得出 (C-D)x=b，两边左乘C-1，并令 M=C-1D，g= C-1b，移项可将方程Ax=b变换成：x=Mx+g据此便可构造出迭代公式： xk+1=Mx k+g，M=C-1D称为迭代矩阵。

《数值计算与MATLAB 》2. 雅可比（Jacobi）迭代法如果方程组Ax=b的系数矩阵A非奇异，aii≠0，若可以把A 分解成： A=D-L-U=D+(-L)+(-U)，D=diag(a11,a22,…,a nn)；-L是严格下三角阵；-U是严格上三角矩阵；x= D-1((L+U)x +b)=D-1(L+U)x+ D-1bx k+1=D-1((L+U)x k+b)= D-1(L+U)x k + D-1bMM=D-1(L+U)称为雅可比迭代矩阵《数值计算与MATLAB 》⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=67-4121-26-3-115-12A⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=61-3-2D⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=74-1-2-1-L⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=2-61-51-UM=D-1(L+U)=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡7/62/3-1/6-222-1/31/2-5/21/2-《数值计算与MATLAB 》雅可比迭代公式的向量形式x k=[( x k) 1,( x k) 2, …,(x k) n]T, k=0,1,2,……，D-1=diag( , ,… ,)，11a122a1nna1))((1)(11∑≠=++-=nijjijijiiikbxaaxk《数值计算与MATLAB》3. 赛德尔（Seidel）迭代法))((1)(11∑≠=++-=nijjijijiiikbxaaxkM= (D-L)-1U称为赛德尔迭代矩阵《数值计算与MATLAB 》4. 迭代法的敛散性方阵的谱半径《数值计算与MATLAB 》向量范数非负性：||x||≥0齐次性：||ax||=|a|||x||；三角不等式：||x||+||y||≥||x+y||。

高斯—塞德尔迭代法

高斯—塞德尔迭代法
（2）按行弱对角占优：
上式至少有一个不等号严格成立。
*定义 每行每列只有一个元素是1,其余 元素是零的方阵称为置换阵(或排列阵).
定理8(对角占优定理)若矩阵A按行(或列)严格对角占优 或按行(或列)弱对角占优且不可约；则矩阵A非奇异。
定理9 若矩阵A按行(或列)严格对角占优,或按行(或列) 对角占优不可约；则Jacobi迭代、Gauss-Seidel迭代都 收敛。
高斯—塞德尔迭代法又等价于：对k=0,1,…,
三、逐次超松驰(SOR)迭代法
SOR迭代法的计算公式:对k=0,1,…,
说明:1)ω=1,GS; 2)ω>1超松驰,ω<1低松驰;
3)控制迭代终止的条件: 例3 用上述迭代法解线性代数方程组
初值x(0)=0，写出计算格式。
四、三种迭代法的收敛性
定理7 对线性方程组Ax=b，A，D非奇异，则 Jacobi迭代法收敛的充要条件是 GS迭代法收敛的充要条件是 SOR迭代法收敛的充要条件是 定义6 （1）按行严格对角占优：
证明 若矩阵A按行严格对角占优，或按行(或列)弱对角占优不可
则GS迭代收敛。假若不然，ρ(BG)≥1，即迭代矩阵BG的某一特征 值λ使得|λ|≥1，并且
类似地，若矩阵A按行严格对角占优，或按行(或列)弱对角占优不
可约，则Jacobi迭代收敛。假若不然，ρ(BJ)≥1，即迭代矩阵BJ 的某一特征值λ使得|λ|≥1，并且
定理10 对线性方程组Ax=b，若A为对称正定矩阵，则 1）GS迭代法收敛. 2）若2D-A也是对称正定矩阵，则Jacobi迭代法收敛。
例8 见书上
定理12 对于线性方程组Ax=b，若A为对称正定矩阵，则
当0<ω<2时，SOR迭代收敛. 证明 只需证明λ<1（其中λ为Lω的任一特征值） .

第六章习题

第六章习题


,

BG

=
3 ab 100
故高斯—赛德尔迭代法收敛的充要条件是 ab < 100。 3
5、对线性方程组13
2 2


x1 x2

=

3 -1
若用迭代法x(k+1)
=x(k)
+
Ax(k) -b ,
k=0,1L 求解。问在什么范围内取值可使迭代收敛，取什么值可
第6章 解线性方程组的迭代解法
5x1+2x2 +x3=-12 1、对方程组 -x1+4x2 +2x3=20，试判断雅克比迭代法，
2x1-3x2 +10x3=3
高斯 — 赛德尔迭代法解此方程组的敛散性。
5 2 1
解:因A=

-1
4
2 ，
2 -3 10
5>2+1=3 , 4>1+2=3,10>2+3=5,
使迭代收敛最快？
解：所给迭代公式的迭代矩阵为B=I+ A=
1+3


其特征方程为
I -B
=
-（1+3） -
-2 -（1+2）=0
2
1+2

即2 -（2+5）+4 2 +5 +1= 2 -（2+5）+ +14 +1 = - +1 -4 +1 =0
-a

0
0
-a 10
0


解：雅可比法的迭代矩阵BJ
=

第六章6.3迭代法的收敛性

第六章6.3迭代法的收敛性

4 2 1
1 5 1
1
2
3
问题：该矩阵具有怎样的特点？ 结论：该矩阵是严格对角占优阵
定义：如果矩阵A的元素满足
jn
| aii | | aij | i 1,2,3,, n j 1 ji
则称A为严格对角占优矩阵。
9
特殊方程组迭代法的收敛性
定理：若线性方程组AX=b的系数矩阵A为 严格对角占优矩阵，则解该方程组的Jacobi 迭代法和G-S迭代法均收敛。
则: (k1) B (k ) B2 (k 1) Bk1 (0)
注意 (0) x(0) x * 为非零常数向量
因此迭代法收敛的充要条件
lim (k1) lim( x(k1) x*) 0
k
k
可转变为
lim Bk1 0
k

2
一阶定常迭代法的收敛性
定理：迭代格式 x(k1) Bx(k ) f 收敛 的充要条件为：lim Bk 0
k
lim Bk 0
k
即: (B) 1
B的所有特征值的绝对值小于1
B的谱半径
根据矩阵与其Jordan标准形及特征值的关系
3
一阶定常迭代法的收敛性
定理：设B为n阶实矩阵，则 lim Bk 0 k
的充要条件是 (B) 1
定理：迭代格式 x(k1) Bx(k ) f 收敛 的充要条件为：(B) 1
4
一阶定常迭代法的收敛性
例：判别下列方程组用Jacobi迭代法和G-S 法求解是否收敛。
1 2 2 x1 1 1 1 1 x2 1 2 2 1 x3 1
5
一阶定常迭代法的收敛性
解: (1) 求Jacobi法的迭代矩阵
1 0 0 0 2 2

迭代法和收敛性

迭代法和收敛性

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)

_第六章_线性方程组的数值解法迭代法


b 1
a 11
b2
f
a 22 bn
a nn
x(k1) B0x(k)f
--------(5)
第四节 解线性方程组的迭代法
令：
0 0 0
L
a 21
0
0 A的下三角部分矩阵
a n1 a n 2 0
0
U
0
a12 0
a1n a2n
A的上三角部分矩阵
第三节 向量范数和矩阵范数
（2）范数的另一个简单例子是二维欧氏空间的长度
0M x2 y2
欧氏范数也满足三个条件：
（勾股定理）
设x = (x1, x2) ① x 0 x >0 ② ax = a x a为常数 ③ x+ y ≤ x + y 前两个条件显然，第三个条件在几何上解释为三角形一边的长度不大于其它 两边长度之和。因此，称之三角不等式。
满足：
① A0,且A0,当且A 仅 0当
，若 A
正定
② A A,为任意实数
奇次
③ ABAB,A和 B为任意 n阶两 方个 三阵 角不等
则称 A 为矩阵A的范数。
第三节 向量范数和矩阵范数
2、矩阵范数与向量范数的相容性 对于任意的n维向量x，都有：
Ax A x
这一性质称为矩阵范数与向量范数的相容性。
n
A
max
1in
j1
aij
A的每行绝对值之和的最大值, 又称A的行范数
第三节 向量范数和矩阵范数
（3）矩阵的2范数
2范数 ||A|2 | ： (AT A )
(AAT) ?
矩阵的谱半径：
矩阵B的诸特征值为： i(i1,2, ,n)

第六章 解线性方程组的迭代法.ppt


称 J 为解 Ax b的雅可比迭代法的迭代阵.
（2.5）
15
研究雅可比迭代法(2.5)的分量计算公式.
记 x(k ) ( x1(k ) ,, xi(k ) ,, xn(k ) )T ,
由雅可比迭代公式(2.5), 有
Dx(k1) (L U )x(k ) b,
或
i1
n
aii
9
定义1 (1) 对于给定的方程组 x Bx f，用公式(1.6) 逐步代入求近似解的方法称为迭代法(或称为一阶定常迭代 法，这里 B与 k无关).
(2) 如果 lim x(k) 存在(记为 x * )，称此迭代法收敛， k
显然 x *就是方程组的解，否则称此迭代法发散. 研究 {x(k )}的收敛性. 引进误差向量
22
例2 用高斯-塞德尔迭代法解线性方程组(1.2).

8x1 3x2 2x3 4x1 11x2 x3

20, 33,
6x1 3x2 12x3 36.
（1.2）
取 x(0) (0, 0, 0)T， 按高斯-塞德尔迭代公式

x ( k 1) 1

记为 Ax b , 其中
（1.2）
8 A4
6
3 2 11 1, 3 12
x1 x x2 ,
x3
20 b 33 .
36
方程组的精确解是 x* (3, 2, 1)T . 现将(1.2)改写为
4

12
于是，求解 Ax b转化为求解 Mx Nx b，即求解
Ax b 求解x M 1Nx M 1b.
可构造一阶定常迭代法

线性方程组的迭代解法及收敛分析

2.8098
1.9583
0.8468
0.2974
9
1.0975
2.0954
2.8217
1.9788
0.8847
0.2533
10
1.0850
2.0738
2.8671
1.9735
0.8969
0.2041
11
1.0673
2.0645
2.8802
1.9843
0.9200
0.1723
12
1.0577
2.0509
2.9077
1.9828
0.9303
0.1400
13
1.0463
2.0437
2.9191
1.9887
0.9448
0.1174
14
1.0392
2.0350
2.9363
1.9886
0.9527
0.0959
15
1.0318
2.0297
2.9451
1.9920
0.9620
0.0801
16
1.0267
2.0241
Keywords：MATLAB,Mathematical model,Iterative method,ConvergenceSystem of linear equations
1
在实际生活中，存在着大量求解线性方程组的问题。这些方程组具有数据量大，系数矩阵稀疏，在一定精度保证下，只需要求解近似解等特点。线性方程组的迭代解法特别适合于这类方程组的求解，它具有程序设计简单，需要计算机的贮存单元少等特点，但也有收敛性与收敛速度问题。因此，研究线性方程组的迭代解法及收敛分析对于解决实际问题具有非常重要的作用。

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


迭代法xk 1 ( xk )就收敛
|xk x*| 对于预先给定的误差限 即要求
由(6)式,只要
L xk xk 1 1 L 1 L xk xk 1 --------(8) L
因此,当

迭代就可以终止, xk可以作为方程的近似解
定义1：如果存在 x * 的某个邻域 R : x x * ，使迭代过程
x n1

xn
f ( xn ) f ' ( xn )
Newton迭代法又称切线法.
4. Newton迭代法收敛定理
' f ( x*) 0 ,且在 x* 的邻域 定理 设 f(x*)=0, '' 上 f 存在, 连续, 则可得
（1）Newton迭代公式在单根情况下至少2阶收敛;
( xn1 x* ) f '' ( x* ) c （2）lim * 2 ' * 2 f (x ) n ( xn x )
p
即迭代法xk 1 ( xk )的收敛阶是 p
定理3. 如果迭代法迭代函数 ( x)在根x * 附近满足：
p! ( p 1)! ( p ) ( x*) , ( k ) p!

( p ) ( x *) ( p 1) ( x *)

( xk x *)
(1) ( x)存在p阶导数切连续； ( p 1) ( x*) 0, (2) ( x*) ( x*) ( p) 而 ( x*) 0 则迭代法 xk 1 ( xk )的收敛阶是 p
| ( x )| L
--------(5)
则1o. 方程x ( x)在[a, b] 内有唯一解x *
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
令BG ( D L)1U , fG ( L)1 b
则GS迭 代 矩 阵 为 ：x BG x fG
Gauss-Seidel 迭代阵
迭代法的收敛性 / Convergence of Iterative methods /
x
(
k
1)
Bx
(
k
)
f
的收敛条件
e
(k
1)
x (k1)
x*
0 xk1 x* r qk1 x0 x* r
又0 < q < 1 k , xk x*
注：
判 断 迭 代 是 否 收 敛 的 一种 充 分 条 件 是 ：
某种范数B < 1 (B) < 1 r
特 别 考 虑1, 范 数
定理 （充分条件）若A 为严格对角占 优阵 / strictly
迭代法的收敛性
邹昌文
迭代法的矩阵写法
1.Jacobi迭代法（J法）
Ax b
令A D L U
0
其
中D
a11
ann
,
L
a21
an1
U
0
0 0
a12
0 0
a1n
an1n 0
A=
0 0
0 0
an2 0
-U
D
-L
(D LU)x b
Dx (L U )x b
定理 Bk 0 ( B ) < 1
证明：“” 若 是 B 的eigenvalue, 则J1k 是 B k 的eigenvalue 。
证明：则对 A[做(BJ)o]rkd=an[分m解ax，|有 |P]k1A=P|mk |... (B，k其) 中 || Bk || 0
i (1B)0< 1
(B)<1
定T理h2.若 迭 代 过 程xk1 Bxk f中 迭 代 矩 阵 的 某
范 数 B < q < 1,则 r
1）x0 Rn ,方 程x Bx f存 在 唯 一 解 ， 且
xk x* , x*为 解
2）xk
x*
r
1 1q
xk1 xk
r
3)
xk
x*
r
qk 1q
x1 x0
r
证：下只证（1），x Bx f存在唯一解
diagonally dominant matrix / 则解 Ax b的Jacobi 和 Gauss -
Seidel 迭代均收敛。
证明：首先需要一个引理 / Lemma /
显然
若A 为SDD阵，则det(A) 0，且所有的 aii 0。
我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别
a
ij
ann
| D| am1(m与xDm此|类L 似Ua)m|i x|iD1| x||mD| |LamiU| |
x D1(L U )x D1b
令BJ D1 (L U ), fJ D1b
则 矩 阵 迭 代 格 式 为 ：x BJ x fJ
Jacobi 迭代阵
Gauss Seidel迭代法（GS法）
Dx k1 Lxk1 Ux k b (D L)xk1 Uxk b
xk1 ( D L)1Ux k ( D L)1 b
)
f
收敛
Bk 0
证明： Bk 0 || Bk || 0
max x0
||
Bk
x
||
|| x ||
0
||
B
k
x
||
0
对任意非零向量
x
成立
B
k
x
那0什收么对敛条任呢件意？可非保零证 向Bk量
x
成立
{从ex(任k()k意) }Bx收k(e0敛)(0出) “则“发xb0”i，(jk”：有)：a记取s对||0|Bk|ex任xk((x0i||))意||第非(|x0|i.B(位零.0.k)1|.向|..0x量)*0T，则
n1
|| Bk || || B ||k 0 as k
Bk 0
r
易证：|| A || || D1P 1 APD ||1 max( | i | ) ( A)
迭代从是 所任由以意只|| x向要 ||取v量 |出| (<P发D，)收1就x敛有||1 导|| A出||的 <算子B1(Ak范i)r 数 。0。
1 i n
i
定T理h1.矩阵A的谱半径不超过任一范数 A r
证 ： 设为A的 任 一 特 征 向 量 对 应 的特 征 值
Ax x ( x 0)
Ax x x A x
r
r
r
rr
A r
(A) A r
定理
设
x
Bx
f
存在唯一解，则从任意
x
(
0)
出发，
迭代
x
(
k
1)
Bx
(
k
定义 设：A (aij )nn , Ak (ai(jk) )nn Rnn .
lim
k
Ak
A 是指
lkimai(jk ) aij
对所有 1 i, j n 成立。
定定义义：谱半 径 矩阵A Rnn的所 有特征值i
(i 1,n)的模的最大值称为A的谱半径，记作( A)
即( A)
max
由Th1，i
(B)
B r
q<1
1不可能是B的特征值 det( E B) 0
(E B)x f有唯一解
xk1 x* Bxk f (Bx* f) B( xk x* )
xk1 x*
r
B( xk x* ) r
B r
xk x*
r
q xk x* r q2 xk1 x* r
(
Bx
(
k
)
f ) (Bx *
f)
B(
x
(
k
)
x*)
Be
(
k
)
e(k ) Bke(0)
||
e
(k
)
||
||
B
||
||
e
(k
1)
||
...
||
B
||k
||
e
(0)
||
充分条件: ||B|| < 1 || B ||k 0 as k
必要条件:
e
(
k
)
0
as
||任e(何k)等|算| 价子0于范对数有 k|| Ak A || 0 aBs kk ？
证证明明：：若任不何然一，个即| de|t(A1) 都= 0不，可则能A是是对奇应异迭阵代。阵的
特征根存，在即非|零I向量B
|
x0
0
。
( x1 ,
x2 ,
xn )T使得 Aa1x10
a0 .ij
|JaIco关bBi记:于| B|G| xJamI=u|ssDDm-1Si1a1e((nxiLdL| ex+li迭U|U)代|) 的i证n1 am明i xi 0
Jr
✓ “Ji ”
首先1需i n要i，ni 一i个r1 n引i 理n
，/ Leim为mAa
的/ eigen
1
value。
对任意1 > 0,
存在算 子范数
|| ·||
使得 || A ||
(A)
。
令
由
D(B )
<1
可2 知存 ，在则算有子D范1P数1AP||D· ||
1
使得
||
Br
||<
1。