算法 Gauss(A,a,b,n,x)
1. 消元 For k=1,2, … , n-1 1.1 if akk=0 , stop; 1.2 For i=k+1,k+2, …, n 1.2.1 l ik=aik /akk => aik 1.2.2 For j=k+1，k+2, … ,n ai j -aik ak j =>aij 1.2.3 bi -aik bk=> bi 2. 回代 2.1 bn / an=>xn; 2.2 For i=n-1,n-2, …, 2,1 2.2.1 bk => S 2.2.2 For j=k+1，k+2, … ,n S –akj xj =>S 2.2.3 S/ akk => xk a1 1 a1 2 a13 a2 1 a2 2 a23
线性方程组的直接解法
刘 斌
线性方程组的直接解法
§1 Gauss消去法 1.1 顺序Gauss消去法
1.2
§2 2.1 2.2 2.3
列主元Gauss消去法
Gauss消去法的矩阵运算 Doolittle分解法 平方根法
直接三角分解方法
2.4
追赶法
引入
在科学计算中，经常需要求解含有n个未知量 的n个方程构成的线性方程组 a11 x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2 n xn b2 (1) an1 x1 an 2 x2 ann xn bn
(1) a12 ( 2) a22 0
(1) (1) a13 a1 n ( 2) ( 2) a23 a2 n ( 3) ( 3) a33 a3 n
0



( 3) ( 3) an a 3 nn
b1(1) ( 2) b2 ( 3) b3 ( 3) bn
方程组还可以用矩阵形式表示为: Ax=b
a11 a 21 A a n1 a12 a22 an 2 a1n x1 b1 x b a2 n , x 2 , b 2 ann x n bn
…
… …
a1 n b1 a2 n b2
a3 1 a3 2 a33 an 1 an 2 an3
a3 n b3 an n bn
…………………………
…
a1 1 a1 2 a13 a22 a23 l
21
.
.
a1 n b1 a2n b2
l31 l32 a33 . a 3n b3 l41 l42 l43 . a b 4 4n . . . . . . . l n1 l n2 l n3 . a b
nn
n
一、顺序Gauss消去法
用Gauss消去法解方程组，应注意：
1. 适用条件： 原方程组系数矩阵的各阶顺序主子 式不等于零。 2 . 运算量小：共有乘除法次数为
1 3 n(n 1) 1 3 n n 2 n ( n 3n 2 n ) 3 2 3


而Gramer 法则的乘除法次数为: (n2 -1) n！
(1) a11 (1) a 21 (1) a 31 a (1) n1 (1) a12 (1) a 22 (1) a 32
或者
Ax=b
我们用增广矩阵表示，并给出gauss消去法的具体算法
(1) a13 (1) a 23 (1) a 33

(1) a1 n (1) a2 n (1) a3 n

(1) a1 n (1) a2 n (1) a3 n

(1) an 2

(1) an 3
(Leabharlann ) a nn(1) b1 (1) b2 (1) b3 (1) bn
第一步，设 a11(1)≠ 0 ，将第一列a11(1)以下各元素消成零
即依次用
li1
A, b A(1) , b(1)

(1) an 2

(1) an 3

(1) a nn
(1) b1 (1) b2 (1) b3 (1) bn
一、顺序Gauss消去法
A, b A(1) , b(1)
(1) a11 (1) a 21 (1) a 31 a (1) n1 (1) a12 (1) a 22 (1) a 32 (1) a13 (1) a 23 (1) a 33
这是与原线性方程组（1）等价的方程组.
一、顺序Gauss消去法
对于等价方程组
(1) (1) (1) (1) a11 x1 a12 x 2 a1 x b n n 1 ( 2) ( 2) ( 2) a x a x b 22 2 2n n 2 ( n 1 ) ( n 1 ) ( n 1 ) an x a x b 1 n 1 n 1 n 1 n n n 1 ( n) ( n) a x b nn n n

( 2) an 2



( 2) ( 2) an a 3 nn
b1(1) ( 2) b2 ( 2) b3 ( 2) bn
其中
( 2) (1) (1) a ij a ij l i 1a1 j , i , j 2, 3, , n (1) bi( 2 ) bi(1 ) l i 1b1 , i 2,3, , n
进行回代求解，可以得到： (n) bn xn ( n ) a nn
xk
1 (k ) (k ) (k ) (k ) b a x a x L a k kk 1 k 1 kk 2 k 2 kn xn (k ) akk


n 1 (k ) (k ) ( k ) bk akj x j , k n 1,L , 2,1 akk j k 1
第二步，设 a22(2)≠ 0 ，将第二列a22(2)以下各元素消成零，
2) a i(2 即依次用 li 2 ( 2) （i＝3，4，…，n） a 22 乘以矩阵[A（2），b（2）]的第二行再加到第i行，得到矩阵
一、顺序Gauss消去法
A
( 2)
, b( 2)

(1) a11 0 0 0
akk(k)≠ 0 ，消去过程能够进行，但若|akk(k)| 过小，也会造 成舍入误差积累很大导致计算解的精度下降。 例2 在四位十进制的限制下，试用顺序Gauss消去法求解 如下方程组
0.012 x1 0.01 x2 0.167 x3 0.6781 x1 0.8334 x2 5.91 x3 12.1 3200 x 1200 x 4.2 x 981 1 2 3
a a
(1) i1 (1) 11
(i＝2，3，…，n)
乘以矩阵[A（1），b（1）]的第一行再加到第i 行，得到矩阵
一、顺序Gauss消去法
A
( 2)
, b( 2)

(1) a11 0 0 0
(1) a12 ( 2) a22 ( 2) a32
(1) (1) a13 a1 n ( 2) ( 2) a23 a2 n ( 2) ( 2) a33 a3 n
2 x1 4 x 2 2 x 3 2 4 x2 2 x3 2 12 x 3 8
x3 2 3 x2 1 6 x1 2 3
x3 2 3 , x2 1 / 6, x1 2 / 3
一、顺序Gauss消去法
a11 x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2 n xn b2 an1 x1 an 2 x2 ann xn bn
引入
求解线性方程组的数值方法可分为两大类：直接方法和 迭代方法。本章讨论直接方法，迭代方法将在下一章中讨论。
直接方法的特点是，如果不考虑计算过程中的舍入误 差，运用此类方法经过有限次算术运算就能求出线性方程 组的精确解。
需要指出，由于实际计算中舍入误差的存在，用直接方 法一般也只能求得方程组的近似值。
2 0 0
4 2 2
4 4 8
4 4 0
2 3 5
2 2 8
2 2 12
2 3 1
2 2 1
2 2 8
2 x1 4 x 2 2 x 3 2 4 x2 2 x3 2 8 x2 8 x3 4
一、顺序Gauss消去法
例1. 用Gauss消去法解方程组
2 x1 4 x 2 2 x 3 2 x1 2 x 2 3 x 3 3 3 x 2 x 5 x 1 1 2 3
用增广矩阵进行进算
2 A, b 1 3
2 0 0
引入
若系数矩阵A非奇异，即 det (A)≠0，则方程组有惟一解 x =( x1, x2, …, xn )T . 根据 Gramer（克莱姆）法则，求解方程组（1）时，要计 算大量的行列式，所需乘法次数大约为
N=(n2-1)n!
当 n 较大时,这个计算量是惊人的。例 如，当 n= 20 时， 约需乘法次数为 N=9.7×1020 如果用每秒一亿次的计算机来计算，需要三十万年时间。 可见Gramer法则不是一种实用的方法。 因此，必须构造出适合于计算机使用的线性方程组的求解 方法。
(1) (1) (1) (1) a11 x1 a12 x 2 a1 x b n n 1 ( 2) ( 2) ( 2) a x a x b 22 2 2n n 2 ( n) ( n) a x b nn n n