解线性方程组的迭代法
x (k1) i
1 aii
(bi
n
aij
x
(k j
)
)
j 1
ji
i 1,2,n
上式称为解方程组的Jacobi迭代公式。
13
雅可比(Jacobi)迭代法
2. 雅可比迭代法的矩阵表示
设方程组 Ax b 的系数矩阵A非奇异,且主对
角元素 aii 0(i 1,2,, n) ,则可将A分裂成
0 a21 A a31 an1
第6章 解线性方程组的迭代法
§6.1 迭代法的基本概念 §6.2 雅可比迭代法与高斯-赛德尔迭代法
1
6.1 迭代法的基本概念
1 引言
我们知道,凡是迭代法都有一个收敛问题,有 时某种方法对一类方程组迭代收敛,而对另一类方 程组进行迭代时就会发散。一个收敛的迭代法不仅 具有程序设计简单,适于自动计算,而且较直接法 更少的计算量就可获得满意的解。因此,迭代法亦 是求解线性方程组,尤其是求解具有大型稀疏矩阵 的线性方程组的重要方法之一。
0 a32
an2
0
ann1
a11 0
a22
0
ann
a12 0
a13 a23 0
a1n
a2n
an1n
0
记作 A = L + D + U
14
雅可比(Jacobi)迭代法
则 Ax b等价于 (L D U )x b
即 Dx (L U )x b
因为 aii 0(i 1,2,, n) ,则
(
x (10) 1
,
x (10) 2
,
x (10) 3
)T
(3.000032,
1.999838,
0.9998813)T
计算结果表明,此迭代过程收敛于方程组的精
确解x*= (3, 2, 1)T。
11
例题
考察一般的方程组,将n元线性方程组
a11x1 a12 x2 a1n xn b1
a
21
x1
a22 x2
a2n xn
b2
an1x1 an2 x2 ann xn bn
写成
n
aij x j bi
j 1
i 1,2,, n
12
例题
若 aii 0 (i 1,2,, n) ,分离出变量 xi
1
n
xi
aii
(bi
aij x j )
j 1
ji
i 1,2,, n
据此建立迭代公式
11
11
6 12
3 12
0
雅可比迭代矩阵表示法,主要是用来讨论其收敛
性,实际计算中,要用雅可比迭代法公式的分量
形式。即 17
称为雅可比迭代公式, B称为雅可比迭代矩阵
其中
0
B
(I
D 1 A)
a21 a22
a12 a11 0
a1n
a11 a2n
a22
an1
an2
0
ann
ann
16
雅可比(Jacobi)迭代法
在例2中,由迭代公式写出雅可比迭代矩阵为
0
B
I
D 1 A
4
3 8 0
2 8 1
(
x (0) 1
,
x (0) 2
,
x (0) 3
)
T
(0,0,0)T
进行迭代, 可以逐步得出一个近似解的序列:
(x1(k )
,
x2(k ) ,
x(k) 3
)
(k=1,
2,
…)
10
例题
直到求得的近似解能达到预先要求的精度,则迭代
过程终止,以最后得到的近似解作为线性方程组的
解。当迭代到第10次有
x (10)
x D1(L U )x D1b 这样便得到一个迭代公式
x(k1) D1 (L U )x(k) D1b
D1 ( A D)x(k) D1b
(I D1 A)x(k ) D1b
15
雅可比(Jacobi)迭代法
令
B (I D1 A) f D1b
则有 x(k1) Bx (k ) f (k = 0,1,2…)
, 故 x* 是方程组 Ax b 的解。
对于给定的方程组可以构造各种迭代公式。 并非全部收敛
5
例题
例1 用迭代法求解线性方程组
2x1 2x1
x2 5x2
3
3
解 构造方程组的等价方程组
xx21
x1 x2 3 2x1 4x2 3
据此建立迭代公式
x (k 1) 1
x (k 1) 2
度要求为止。这种方法称为迭代法
如果 x(k) x1(k ) , x2(k) ,, xn(k) T 存在极限 x* x1* , x2* ,, xn* T 则称迭代法是收敛的,否则就
是发散的。
4
迭代法的基本思想
收敛时,在迭代公式
x(k1) Gx(k) d (k 0,1,)
中当 k 时,x(k) x* , 则 x* Gx* d
x1
x2
4 11 x1
3 8
x2
1 4
x3
5 2
1 11 x3 3
x3
1 2
x1
1 4
x2
3
9
例题
建立迭代公式
2
)
1 4
x3(k )
5 2
x
(k 2
1)
4 11
x1(
k
)
1 11
x3(k )
3
x3(k
1)
1 2
x1(k )
1 4
x2(k )
3
取初始向量
x (0)
2
迭代法的基本思想
2 迭代法的基本思想
迭代法的基本思想是将线性方程组转化为便于
迭代的等价方程组,对任选一组初始值
x (0) i
(i
1,2,,
n)
,按某种计算规则,不断地对所得到的值进行修正
,最终获得满足精度要求的方程组的近似解。
设 A Rnn非奇异,b Rn,则线性方程组 Ax b
有惟一解 x A1b ,经过变换构造出一个等价
7
6.2 雅可比迭代法与高斯-赛德尔迭代法 1 雅可比(Jacobi)迭代法
1.雅可比迭代法算法构造
例2 用雅可比迭代法求解方程组
8x1 3x2 2x3 20 4x1 11x2 x3 33 6x1 3x2 12x3 36
8
例题
解:从方程组的三个方程中分离出 x1, x2 和 x3
同解方程组 x Gx d
3
迭代法的基本思想
x(k)
x1(
k
)
,
x
(k 2
)
,,
x n( k
)
T
将上式改写成迭代式 x(k1) Gx(k) d (k 0,1,)
选定初始向量
x(0)
x(0) 1
,
x(0) 2
,,
x(0) n
T
,反复不断地
使用迭代式逐步逼近方程组的精确解,直到满足精
x1(k 2x1(k)
)
x2(k ) 4x2(k)
3 3
取
x(0) 1
x(0) 2
0
计算得
6
例题
xx2(1(11))
3 3,
xx2(1(22))
3 3,
xx2(1(33))
9 9,
xx2(1(44))
15 15,
xx2(1(55))
33 33,
迭代解离精确解 x1 1, x2 1 越来越远迭代不收敛