b11x1 b12 x2
b22 x2
b1,n x 1 n1 b1n xn g1 b2,n1xn1 b2n xn g2
b x n1,n1 n1 bn1,n xn gn1
bnn xn gn
这个过程称为消元过程。 由此可逐个求出xn，xn-1 ，… ，x1 ，这个过程称为回代过程
a(0) 11
l21
a(0) 12
a(1) 22
a(0) 13
a (1) 23
l31
l32
a(2) 33
ln1 ln2 ln3
A的行列式的值为
|
A
|
a a a (0) (1) (2) 11 22 33
2020/9/29
a(0) 1n
a (1) 2n
a(2) 3n
a ( n 1) nn
n
a(n1) nn
在每一次消元前，都进行上述的列选主元的过程 。这样的
解可由线性方程组
得到。
A(n)x=b(n)
2020/9/29
27
3.2 高斯消去法
以上消元过程中，对角线上的
a(k) kk
称为主元素。
这就是列选主元素方法的消元过程。
列选主元素方法中要多次交换系数矩阵的行，若共进行了m 次 ，则行列式
n
| A | (1)m
bk( k
)
b( k ) k 1
bn( k
)
11
3.2 高斯消去法
a(k) kk
0
计算因子
消元得到
a (1) 11
a (1) 12
a(2) 22
(
A(k 1) , b(k 1)
)
2020/9/29
lik
a(k) ik
/
a(k kk
)
(i k 1,
,n)
a (1) 1k
a(2) 1k
3.2 高斯消去法
其中
baii((jkk11))
a(k) ij
b(k ) i
lik
a(k kj
)
likbi(k )
(i, j k 1, k 2,
, n)
按上述做法，完成n-1次消元后，方程组化 成同解的上三角方程
A(n)x = b(n)
a (1) 11
( A(n) , b(n) )
a (1) 12
取五位有效数字，进行高斯消元计算，把第二个方程中的x1 消去，得到
0.0003x1
3.0000x2 9999.0x2
2.0001 6666.0
从第二个方程解得x2=0.6667，再代入第一个方程得x1=0。可 见，直接利用高斯消元法得到的结果与准确解相差较大。
2020/9/29
25
3.2 高斯消去法
a11x1 a12 x2 a21x1 a22 x2
a1n xn b1 a2n xn b2
an1x1 an2 x2 ann xn bn
用矩阵和向量的记号来表示，可写成 Ax b
a11 a12 A a21 a22
an1 an2
a1n
a2n
ann
x1
x
x2
高斯消去法的特点：消元和回代不同步！
2020/9/29
14
3.2 高斯消去法
消元过程可写为
[ A(n) , b(n) ] Ln1[ A(n1) , b(n1) ]
Ln L 1 n2 L2 L1[ A(0) , b(0) ]
Ln L 1 n2 L2L1[ A, b]
分开，有
A(n) Ln1Ln2 L2 L1 A
2020/9/29
21
3.2 高斯消去法
计算量：n阶行列式有n！项，每项计算n-1次乘法， 总乘法次数
Sn=(n+1)×n! ×(n-1)= (n+1)! ×(n-1) 当n=20时，乘法次数为9.7×1020次。若用每秒运 算10亿次乘法的计算机计算，约需3.08万年，这是无 法实现的。
若用Gauss消去法求解，其乘除法运算次数只需 3060次。
可分析两种解法不同结果的原因。
2020/9/29
26
3.2 高斯消去法
选主元 列选主元素方法
第一步时
在A(1)的第一列元素
ai(11)(i=1,2,
…,n)中，选主元素
a(1) i11
，使
a(1) i11
max
1in
|
a(1) i1
|
并交换(A(1)，b(1))的第一行与第i1行。元素记号保持不变。
a (1) 1,k 1
a(k) 1,k 1
a(k) kk
a(k) k ,k 1
a(k 1) k 1,k 1
a(k 1) n,k 1
a (1) 1n
a(2) 2n
a(k) kn
a(k 1) k 1,n
a(k 1) n,n
b(1) 1
b(2) 2
b(k ) k
bk(
k 1) 1
bn( k
1)
12
注意：右端的A(n)是一个上三角矩阵。
由于
Lk I lk ekT
因此
Lk1 I lk ekT
仍为单位下三角矩阵
2020/9/29
15
3.2 高斯消去法
令
L (Ln1Ln2
L2 L1)1 L11L21
L L 1 1 n2 n1
为如下形式的单位下三角矩阵
1
l21
L
l31
ln1,1 ln1
A LA(n) LU
即，一个方阵可以分解为一个单位下三角矩阵与一个
上三角矩阵的乘积。称为矩阵的LU分解，也称为 Doolittle分解。
方程
Ax=b
可以写成
LUx=b
等价于两个方程
Ly=b
Ux=y
2020/9/29
17
3.2 高斯消去法
存储上的特点。由于L是单位下三角矩阵，其对角元 素为 1，是已知量，可以不存储。因此可将L存于U空出的下三 角部分。即利用矩阵A的存储空间 ，有
xn
b1
b
b2
bn
设|A|≠0，则方程组有唯一解
2020/9/29
3
3.1 引言
直接法 将Ax=b化为等价的上三角形方程
Ux=L-1b 其中，U是上三角矩阵，L是下三角形矩阵。可用高斯消去 法得到 直接三角分解法：将A做三角分解
A=LU
然后求解下列两个三角形方程 Ly=b Ux=y
2020/9/29
4
3.1 引言
中小规模代数方程组，常选用直接法 如果右端项有多个，多采用直接法 大型稀疏矩阵，有些用迭代法
2020/9/29
5
3.2 高斯消去法
3.2.1 顺序消去过程和矩阵的LU三角分解 3.2.2 可行性和计算量 3.2.3 数值稳定性：选主元
2020/9/29
6
3.2 高斯消去法
3.2.1 顺序消去过程和矩阵的LU三角分解 高斯消去法把方程组转化为一个等价的三角形方程组
Summer Grass Fade
Arial Font Family
3 线性代数方程组的数值解法
• 3.1 引言 • 3.2 高斯消去法 • 3.3 矩阵的直接三角分解 • 3.4 方程组的形态、条件数 • 3.5 大型方程组的迭代法
2020/9/29
2
3.1 引言
本章研究的对象是n阶线性代数方程组
定理3.2.3 若A严格对角占优，则
a(k) kk
0
(k 1, 2,
,n)
2020/9/29
19
3.2 高斯消去法
高斯消去法的计算量
把A(1)化为等价的A(n)所需要的乘法运算量是
n (k 2 k) n (n2 1)
k 1
3
除法运算量是
n1
n
k (n 1)
k 1
2
回代过程需要的乘除法总运算量是n(n1)/2
b(1) 1
b(2) 2
a(2) nn
b(2) n
9
3.2 高斯消去法
第i行的消元公式为
baii((j22))
a(1) ij
b(1) i
li1a1(1j) li1b1(1)
(i, j 2,3,
, n)
矩阵表示
初等矩阵 其中
L1=I-l1e1T l1=(0,l21, l21, …, ln1)T
a ( i 1) ii
i 1
2020/9/29
28
3.2 高斯消去法
完全选主元方法
如果将选主元的范围扩大到余下的全部元素，即在
0
3
3
9
1 4 5 14 0 3 3 9 0 0 2 2
可以继续计算了
2020/9/29
24
3.2 高斯消去法
2) 主元过小，导致计算过程不稳定
例3.2.2 设有线性方程组
10..00000003xx11
3.0000x2 1.0000x2
2.0001 1.0000
该方程组的准确解为x1=1/3，x2=2/3。
2020/9/29
7
3.2 高斯消去法
记
a11 a12
(
A,
b)
a21
a22
an1
an2
且把(A，b)记为(A(1)，b(1))，即
(
A,
b)
(
A(1)
,
b(1)
)
a (1) 11
a (1) 21
a (1) 12
a (1) 22
a (1) n1
a (1) n2
2020/9/29