当前位置：文档之家 › 第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

第六章 解线性方程组的迭代法.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 *
数值分析课第三作业课后答案answer

数值分析课第三作业课后答案answer


第七章 方程求根 1. 用二分法求方程 x2 − x − 1 的正根，要求误差 < 0.05。 答案：1.609375。
2. 为求方程 x3 − x2 − 1 在 x0 = 1.5 附近的一个根，设将方程改写为下 列等价形式，并建立相应的迭代公式。
（1）x = 1 + 1/x2，迭代公式 xk+1 =√1 + 1/x2k；
4x1 − x2 = 1;
−x1
+ 4x2 − x3 −x2 + 4x3
= 4; = −3.
精确解
x∗
=
(
1 2
,
1,
−
1 2
)。要求当
∥x∗
−
x(k)∥∞
<
5
×
10−6
时迭代终止。并
且对每一个 ω 值确定迭代次数。
答案：ω = 1.03 时迭代 5 次达到精度要求，
1
x(5) = (0.5000043, 1.000001, −0.4999999)T ； ω = 1 时迭代 6 次达到精度要求， x(6) = (0.5000038, 1.000002, −0.4999995)T ； ω = 1.1 时迭代 6 次达到精度要求， x(6) = (0.5000035, 0.9999989, −0.5000003)T 。
4. 用下列方法求 f (x) = x3 − 3x − 1 = 0 在 x0 = 2 附近的根，根的准 确值 x∗ = 1.87938524 · · · ，要求计算结果准确到四位有效数字。
（1）用牛顿法；
（2）用弦截法，取 x0 = 2，x1 = 1.9；
（3）用抛物线法，取 x0 = 1，x1 = 3，x2 = 2；

数值分析第六章线性方程组迭代解法

数值分析第六章线性方程组迭代解法线性方程组是数值分析中的重要内容之一，其求解方法有很多种。

其中一种常用的方法是迭代解法，即通过不断迭代逼近方程组的解。

本文将介绍线性方程组迭代解法的基本思想和常用方法。

线性方程组可以用矩阵形式表示为Ax=b，其中A是系数矩阵，b是常数向量，x是未知向量。

线性方程组的解可以是唯一解，也可以是无穷多个解。

迭代解法的基本思想是通过不断迭代，并利用迭代序列的极限，逼近线性方程组的解。

迭代解法适用于大型的线性方程组，而直接求解法则适用于小型的线性方程组。

常用的迭代解法有雅可比迭代法、高斯-赛德尔迭代法和逐次超松弛迭代法。

雅可比迭代法是最简单的线性方程组迭代解法之一、它的基本思想是将线性方程组的每个方程都单独表示为未知数x的显式函数，然后通过不断迭代求解。

雅可比迭代法的迭代公式为：x(k+1)=D^(-1)(b-(L+U)x(k))其中，D是A的对角元素构成的对角矩阵，L是A的下三角矩阵，U 是A的上三角矩阵，x(k)是第k次迭代的解。

高斯-赛德尔迭代法是雅可比迭代法的改进版。

它的基本思想是将每个方程的解带入到下一个方程中，而不是等到所有方程都迭代完毕后再计算下一组解。

高斯-赛德尔迭代法的迭代公式为：x(k+1)=(D-L)^(-1)(b-Ux(k))其中，D是A的对角矩阵，L是A的下三角矩阵（除去对角线），U是A的上三角矩阵（除去对角线），x(k)是第k次迭代的解。

逐次超松弛迭代法是对高斯-赛德尔迭代法的改进。

它引入了松弛因子w，通过调节松弛因子可以加快收敛速度。

逐次超松弛迭代法的迭代公式为：x(k+1)=(D-wL)^(-1)[(1-w)D+wU]x(k)+w(D-wL)^(-1)b其中，D是A的对角矩阵，L是A的下三角矩阵（除去对角线），U是A的上三角矩阵（除去对角线），w是松弛因子，x(k)是第k次迭代的解。

线性方程组迭代解法需要设置迭代停止准则，通常可以设置迭代次数上限或者设置一个精度要求。

6.3迭代法的收敛定理

det( D L) aii 0
i 1 n
所以矩阵（D-L）为可逆下三角矩阵，其逆也是下三角矩阵， G-S迭代法的迭代矩阵是 BG =(D - L)-1U。
考虑BG的特征值λ ，其特征方程为
det(I-BG) = det(I-(D-L)-1U) = det(D-L)-1det((D-L)-U)=０
易求
BJ

max
1i n
1 j n , j i

aij aii
由严格对角占优定义（定义6.1 ），得 BJ ∞<1,所以, Jacobi 迭代法收敛。
下面证明G-S迭代法的收敛性。对于严格对角占优阵A， 其对角元素 aii ≠ 0 ， i=1,2,,n（定义6.1 ），故
定理6.3的证明
证 首先证明Jacobi 迭代的收敛性。由
0 a 21 B J D 1 ( L U ) a 22 a n1 a nn a12 a11 0 a n2 a nn a1n a11 a2n a 22 , 0 b1 a 11 b2 fJ a 22 b n a nn
返回节
二、Jacobi 迭代法和Gauss-Seidel 迭代法的收敛速度


引子 对角占优矩阵 实例 相关定理 定理3.3的证明
返回节
引子
虽然利用定理6.1和定理6.2可以判定Jacobi 迭代 法和G-S迭代法的收敛性，但其中只有定理6.2对 Jacobi 迭代法使用比较方便，此外，对于大型方程 组，要求出G-S迭代矩阵BG和ρ(BG)以及Jacobi 迭代 矩阵BJ和ρ(BJ)都不是容易的事。

6-3迭代法的收敛性


1
2 x1 2 x2 x3 3
讨论Jacobi法与Gauss-Seidel法旳收敛性。
解：由定理，迭代法是否收敛等价于迭代矩阵 旳谱半径是否＜１，故应先求迭代矩阵。而
1 2 2
A 1 1
1
2 2 1
故A裂解后旳各矩阵分别为
1
D
1
1
0 0 0
L
1
0
0
2 2 0
0 2 2
| I
B |
1/a
2 / a 0
3 / a 2 / a
得
1 0 ,
2,3
|
4 a
|
故 (B) 4
|a|
由 (B) 1 得 | a | 4
故当 | a | 4 时，Jacobi迭代法收敛。
作业： 习题 1，2（2）
1 1 5
2 矩阵 B 1
1 2
0 1
不严格对角占优， 是弱对角占优
0 1 2
定义：假如矩阵A不能经过行旳互换和相应列 旳互换成为形式
A11 A12
0
A22
其中A11，A22为方阵，则称A为不可约.
例如：判断下列矩阵是否可约？
1 1 0
2 1 0
矩阵 A 1 1 0 是可约旳。 0 1 1
9 3
4 10
显然Aˊ是严格对角占优阵，所以对方程组
Ax b 用Jacobi法和Gauss-Seidel法均收敛。
例3*：设A=(aij)是二阶方阵，且a11a22≠0.试证 求解方程组Ax=b旳Jacobi法与Gauss-Seidel法 同步收敛或发散。
证明：Jacobi迭代矩阵为
0
BJ
a
21

迭代法的收敛性


谱半径分别是 ρ ( B ) =
30 15 , ρ ( M ) = 。均不收敛。 2 2
若交换方程的次序，得 Ax = b的同解方程组 Ax=b,
' '
3 − 10 9 −4 ' A= → A = 3 −10 9 −4 A '为严格对角占优阵，因而对方程组 A ' x = b '用 Jacobi与 Gauss − Seidel 迭代求解均收敛。
k →∞
x* = Mx* + g 由迭代公式有 x ( k ) − x* = Mx ( k −1) + g − Mx* − g = M ( x ( k −1) − x* ) = M 2 ( x ( k − 2) − x* ) = M k ( x (0) − x* ) 于是有 lim M k ( x (0) − x* ) = lim( x ( k ) − x* ) = 0
其特征方程
λ
1 λI − B = 2 1 2
1 2
λ
1 2 1 3 1 3 = λ − λ + 2 4 4
1 λ 2 1 2 = ( λ − ) ( λ + 1) = 0 2
1 , λ 3 = − 1, 因 而 ρ ( B ) = 1 得λ1 = λ 2 = 2 ⇒ J a c o b i迭 代 法 不 收 敛 。
移项得 代入得
(I − M ) x (k ) − x*
−1
1 ≤ 1− M
k
M ≤ 1− M
x (1 ) − x ( 0 ) 。
由误差估计式 x
(k )
−x
*
≤
M
k
1− M
x (1) − x ( 0 )

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

k k
有 lim || Ak x || 0.所以就有定理的右边成 立。
k
反之，若定理的右边成 立，取x为第j个坐标向量e j， 则 lim Ak e j 0, 表示Ak的第j列元素极限均为零，当
k
j 1,2, , n时就证明了lim Ak 0，证毕。
k
给出的迭代法
( ( x1( k 1) (3x2k ) 2 x3k ) 20) / 8 ( k 1) (k ) (k ) x2 (4 x1 x3 33) / 11 的收敛性。 ( ( x3k 1) (6 x1( k ) 3x2k ) 36) / 12
第6章
解线性代数方程组的迭代法
§1 引言
考虑线性方程组
a11x1 a12 x2 a1n xn b1 a x a x a x b 21 1 22 2 2n n 2 an1x1 an2 x2 ann xn bn
(1.4)
即
x(k+1)=B0x(k)+f， (k=0,1,2,„)
x (10 ) (3.0000321.999838 0.9998813T , , , ) ε
(10 )
0.000187其中ε ,
(k )
(10 )
x
(10 )
x *.
从此例可以看出，由迭 代法产生的向量 序列x 逐步逼近此方程的精确 解。
3 8
0
3 12
2 8 1 11 0
20 x1 8 x 33 . 2 11 x3 36 12
任取初值,如x(0)=(0,0,0)T,代入(1.3)得到x(1)= (2.5,3,3)T. 反复迭代

(数值分析)第六章 解线性方程组的迭代法

* r * * *
华长生制作
1
定义1 设 中的向量序列，若有向 k n x 量 x R ，使 lim x x 0 ，则称 k lim x x 收敛于 x ，记为 k
x
k
是R
n
(k)

k
nn A R 定义2 设 是 中的矩阵序列，若有矩 n n lim A A 0 A A R 阵 ，使 ，则称 lim A A 收敛于A，记为
k 1 k x B x f
华长生制作
17
定理5.
设 方 程 x = B x + f 有 惟 一 解 x , 若 B 1 , 则 由
简 单 迭 代 法 产 生 的 向 量 序 列 x 满 足
x x
(k )
x x


B 1 B B
k

k
x( k ) x( k 1) x1 x 0
( 0 ) 取初始向量 x ,代入 ( 2 ), 可得
( 1 ) ( 0 ) x Bx f
依此类推
华长生制作 11
(2 ) ( 1 ) x Bx f

(k) x(k1) Bx f
--------(3)
( k 0 , 1 , 2 , )
这种方式就称为迭代法 ,以上过程称为迭代过程
k
k n l i m Ax 0 , x R 0 的 充要条件是
lim Ak 0.
k
R 定理 4 设矩阵 B ，则 k 的充分 m a x B B . 必要条件是 B 的谱半径 (B) 1 ，其中 i 1 i n
( n n )
  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。