第五章解线性方程组的迭代法PPT课件

x0 x
xR n
又 : E AE A 1 E E A 1 AE A 1 E E A 1 E AE A 1
E A 1 1 AE A 1 1 A E A 1
E A 1 1
1 A
4）Rnn 上旳范数均等价,即对Rnn上旳两个范数
及
s
t ,存在常数
C1>0,C2>0.使 C1
阵P使P•A=L•U。
③Gauss消元法旳改善 Gauss消元法旳缺陷：
对给定的Ax b, A 0, 欲求Ax b x ?
1)为使主元
a
k
kk
0, 需Dk
0k
1,2,, n 1, 但前提条件
只有Dn 0， A 0.
2)在Dn 0的条件下，可通过交换 两个方程使主元非零， 但仍
有问题存在：可能违反 运算规则（除法） 非常小的数做分母。
n 1 n 2n 1 n n 1
6
1 n3 1 n2 5 n 326
回代：N回 1 2
n n 1
n
2
N总
N消
N回
1 3
n3
1 2
n2
5 6
n
n n 1
2
1 3
n3
n2
1 3
n
o
1 3
n3
§3 三角求解求法
一、基本思想
已知：Ax b, 且A的顺序主子式Dk 0(k 1,2,..., n). 则A有D分解A LU；L为单位矩阵，U为上三角阵. 于是Ax b即为LUx b, 令Ux y，Ly b. 先求Ly b y Ux y x. 即先求解Ly b，得y，再求解Ux y，得x. 此即为LU分解法的基本思路.
(单位下三角矩阵旳逆为单位下三角矩阵，乘积也为单位下三角矩阵) 由此引进如下更一般旳三角分解旳概念：

a13 L a23 L 0L
O
a1n a2n
a3n M
0
0
a12 a11
a13 L a11
a1n a11
a21 a22
0
a23 L a22
a2 n a22
BJ
a31 a33
a32 a33
0
L
a3n a33
M
M
M
OM
an1 ann
an2 ann
an3 ann
j 1
n
aij x(jk )
j i1
bi )
x ( k 1) 1
1 a11
(a12 x2(k)
a13 x3(k )
a14 x4(k )
a1n xn(k )
b1 )
x ( k 1) 2
1 a22
(a21 x1(k1)
a23 x3(k )
a24 x4(k )
a2n xn(k )
b2 )
x ( k 1) 2
2
得 x(1) = ( 0.5000, 2.8333, -1.0833 )T
M
x(9) = ( 2.0000, 3.0000, -1.0000 )T
举例（续）
SOR 迭代格式
x1( k x2( k
1) 1)
x(k) 1
x(k) 2
1
2 x1(k)
x(k) 2
2
8
x ( k 1) 1
Jacobi 迭代
令 A = D - L- U， 其中 D diag(a11, a22,K , ann),
0
L
a21
M
an1
0 a12 L
0 OO
,

i 1 n 1 xi = [bi ∑ aij x j ∑ aij x j ] , i = 1, 2,, n. （*） ） aii j =1 j = i +1
定义迭代法为： 定义迭代法为：
x ( k + 1) = G J x ( k ) + g
其中Jacobi迭代矩阵：GJ = D1 ( L + U ) 迭代矩阵： 其中 迭代矩阵
g = D 1b = (7.2, 8.3, 8.4)T 取 x ( 0 ) = (0, 0, 0)T , 代入迭代式，得x(1) = Bx ( 0 ) + g = (7.2, 8.3, 8.4)T x ( 2 ) = Bx (1) + g = (9.71,10.70,11.5)T x (9 ) = (10.9994,11.9994,12.9992) 精确解为 x = (11,12,13)T .
记
A = D L U
其中 D = diag (a11 ,, ann ) , L, U 分别为 A 的 严格下、上三角形部分元素构成的三角阵 严格下、上三角形部分元素构成的三角阵. Gauss-Seidel方法的矩阵形式为 方法的矩阵形式为
x ( k +1) = D1 ( Lx ( k +1) + Ux ( k ) + b)
或者
x ( k +1) = ( D L)1Ux ( k ) + ( D L)1 b
( 这说明Gauss-Seidel方法的迭代矩阵为 D L)1U 方法的迭代矩阵为 这说明
从而有
定理5.2 定理5.2 Gauss-Seidel方法收敛的充分必要条件为 方法收敛的充分必要条件为
ρ (GG ) < 1 或

(
简单，而更易求解.
L+D+U
)x
=
b
( D L ) x U x b
则高斯—塞德尔迭代过程 2 Gauss—Seidel 迭代法的矩阵表示
步对角化或三角化，即将线性方程组的求解过
单位下三角矩阵
；
(D L )x U x b 解 Gauss Seidel 迭代格式为
取初始值为零，计算结果如下： 所以对于任给的初值， 迭代收敛于方程组
a11 x1 b1
思考题
a
2
1
x1１ a．22 x2写 b出2 上三角方程组的求解公式．
ai1 x1
2a．i2x2矩利阵用 a求三ii xi逆角 b的i方计程aii算组0公的式求xx1i ．解(bb1i公/a11i式j11a导ijxj出)/a三ii,i角2,
,n
a n1 x1 a n 2 x 2
8x1 3x2 2 x3 20
4
x1
11x2
x3
33
x
1
3 8
x2
1 4
x3
5 2
x2
4 11
x1
1 11
x3
3
解：从方程6组x1 的3三x2 个12方x3程 中36分离 x出3
建立迭代公式
1 2
x1
x1
, x2
1 4
x2
和
3
x
3
x
1
x
2
x
3
x1(
k
1)
3 8
x
3 28
§3 迭代法的设计技术
(k 1)
(k)
因为 D 0 ,所以 §5 超松弛迭代法（SOR方法）