当前位置:文档之家› 第四章线性代数方程组迭代解法

第四章线性代数方程组迭代解法


a11x1 a12 x2 a1n xn b1
a21 x1
a22 x2
a2n xn
b2
an1x1 an2 x2 ann xn bn
n
写据成此建立迭ai代j x公j 式 bi
i 1,2,, n
若上xia(式xkiii1称)0为ja(1解a1i1iiii方((1bb,程2ii , 组jj的,njnn1i )1Jaaa,ijc分xijo(xjbk离)ij)迭)出代变i公i量式1,。21x,,2i , n , n ji
第四章 解线性方程组的迭代法
在第二章中我们知道,凡是迭代法都有 一个收敛问题,有时某种方法对一类方程组 迭代收敛,而对另一类方程组进行迭代时就 会发散。一个收敛的迭代法不仅具有程序设 计简单,适于自动计算,而且较直接法更少 的计算量就可获得满意的解。因此,迭代法 亦是求解线性方程组,尤其是求解具有大型 稀疏矩阵的线性方程组的重要方法之一。
就改用新值
x (k 1) i
替代老值
x (k ) i
进行这一步剩下的计算。
高斯-塞德尔迭代算法的程序实现 ( 见附录A A-7 用高斯—塞德尔迭代法求解线
性方程组 )
4.5 超松弛迭代法(SOR方法) 使用迭代法的困难在于难以估计其计算
量。有时迭代过程虽然收敛,但由于收敛速 度缓慢,使计算量变得很大而失去使用价值 。因此,迭代过程的加速具有重要意义。逐 次超松弛迭代(Successive Over relaxatic Method,简称SOR方法)法,可 以看作是带参数的高斯—塞德尔迭代法,实 质上是高斯-塞德尔迭代的一种加速方法。
式中系数ω 称为松弛因子,当ω =1时,便为高斯塞德尔迭代法。为了保证迭代过程收敛,要求 0<ω < 2。 当0<ω < 1时,低松弛法;当1<ω < 2时 称为超松弛法。但通常统称为超松弛法(SOR)。

33 33,
迭代解离精确解 x1 1, x2 1 越来越远迭代不收敛
4.3 雅可比(Jacobi)迭代法
4.3.1雅可比迭代法算法构造
例4.2 用雅可比迭代法求解方程组
8x1 3x2 2x3 20 4x1 11x2 x3 33 6x1 3x2 12x3 36
解建:立从迭方代程公组式的三个方程中分离出 x1, x2 和 x3
x1x( k 11) xxxx32(( kk 3211))

3 8
x2(k )
8314xx23(k)
51 24
1411x41(1k) x1

1 11
x3(k) 31 11
0




ann


a12 0
a13 a23 0
a1n

a2n



an1n

0
记作 A = L + D + U
则 Ax b 等价于 (L D U )x b
即 Dx (L U )x b
因为 aii 0(i 1,2,, n) ,则
4.5.1超松弛迭代法的基本思想
超松弛迭代法目的是为了提高迭代法的收敛速
度,在高斯—塞德尔迭代公式的基础上作一些修改
。这种方法是将前一步的结果
x
( i
k
)
与高斯-塞德尔
迭代方法的迭代值 ~xi(k1) 适当加权平均,期望获得更
好的近似值 xi(k1)。是解大型稀疏矩阵方程组的有效
方法之一,有着广泛的应用。
1
2
x11(k 2
)
x114x2(k
1) 4
3
x2
x3 x3

3
5 2
3
取初始向量
x (0)

( x1(0)
,
x
(0 2
)
,
x3(0)
)T
(0,0,0)T
进行迭代, 可以逐步得出一个近似解的序列:
(x1(k ) , x2(k ) , x3(k ) ) (k=1, 2, …) 直到求得的近似解能达到预先要求的精度,
1 4
x2(k1)32
03

雅可比迭代矩阵表示法,主要是用来讨论其收敛 性,实际计算中,要用雅可比迭代法公式的分量 形式。即

x1(
k
1)


1 a11
(a12 x2(k )

a13 x3(k )

a1n xn(k )

b1 )

x2(k
1)


1 a22
(a21 x1(k )
x1(k 2x1(k)
) x2(k ) 4x2(k )
3 3

x (0) 1

x (0) 2

0
计算得
xx2(1(11))

3 3,
xx2(1(22))

3 3,
xx2(1(33))

9 9,
xx2(1(44))

15 15,
xx2(1(55))

a23 x3(k )

a2n
x
(k n
)

b2 )



xn(k
1)


1 ann
(an1 x1(k )

an2 x2(k )

an
n1 xn(k)1
bn )
(k=0,1,2,…)
4.3.3
雅 可 比 迭 代 法 的 算 法 实 现
输入 aij,bi,和 方程阶数 n,ε (x2(k ) x3(k ) (2x1(k1)
1) / 8 x3(k) 4) /10
x3(k 1)
( x1(k 1)

x (k 1) 2
3) / 5
取初始迭代向量 x(0) (0 ,0 ,0)T ,迭代结果为:
4.4.2 Gauss—Seidel 迭代法的矩阵表示
将A分裂成A =L+D+U,则 Ax b 等价于 ( L+D+U )x = b
于是,则高斯—塞德尔迭代过程
Dx(k1) Lx(k1) Ux(k) b
因为 D 0 ,所以 D L D 0

(D L)x(k1) Ux (k) b
x(k1) (D L)1Ux (k) (D L)1b
令 G1 (D L)1U , d1 (D L)1b
则高斯-塞德尔迭代形式为:
x (k 1) G1 x (k ) d1
4.4.3 高斯—塞德尔迭代算法实现
高斯-塞德尔迭代算法的计算步骤与流程图
与雅可比迭代法大致相同,只是一旦求出变元 xi
的某个新值
后, x (k1) i

0

在例4.2中,由迭代公式写出雅可比迭代矩阵为
B

I

x1(
k
1)



D x (k 11) 2
A

141x10(1k4)183
x 2( k
)
3

1
84
0 1
11
xx33((kk1))1182352

x3( k
1)

12x1(k1)62
如果 x(k ) x1(k ) , x2(k ) ,, xn(k ) T
存在极限 x* x1* , x2* ,, xn* T
则称迭代法是收敛的,否则就是发散的。
收敛时,在迭代公式
x(k1) Gx (k) d (k 0,1,) 中当 k 时,x(k) x* , 则 x* Gx* d
x D1 (L U )x D 1b 这样便得到一个迭代公式
x(k1) D 1 (L U )x (k) D 1b
D 1 ( A D)x (k ) D 1b (I D 1 A)x (k ) D 1b
令 则有
B (I D 1 A) f D 1b
出一个等价同解方程组 x Gx d 将上式改写成迭代式
x (k 1) Gx (k ) d (k 0,1,)
选定初始向量 x(0) x1(0) , x2(0) ,, xn(0) T ,反复不断
地使用迭代式逐步逼近方程组的精确解,直 到满足精度要求为止。这种方法称为迭代法
则迭代过程终止,以最后得到的近似解作为线
性方程组的解。
当迭代到第10次有
x (10)

(
x (10) 1
,
x (10) 2
,
x (10) 3
)T
(3.000032 ,
1.999838 ,
0.9998813 )T
计算结果表明,此迭代过程收敛于方程组的精
确解x*= (3, 2, 1)T。
考察一般的方程组,将n元线性方程组
4.2 迭代法的基本思想
迭代法的基本思想是将线性方程组转化
为便于迭代的等价方程组,对任选一组初始

x (0) i
(i

1,2,,
n)
,按某种计算规则,不断地
对所得到的值进行修正,最终获得满足精度
要求的方程组的近似解。
设 A Rnn 非奇异,b Rn ,则线性方程组
Ax b 有惟一解 x A1b,经过变换构造
4.3.2 雅可比迭代法的矩阵表示
设方程组 Ax b 的系数矩阵A非奇异,且主对
角元素 aii 0(i 1,2,, n) ,则可将A分裂成
相关主题