第3章 线性代数方程组的解法

回代： Xn= ann+1(n)/ann(n) 编程时，
为节省内存将Xn放在a nn+1(n)
同理X i 放在 a in+1(i) 第i次回代公式（i=n-1…..1) Xi(即a in+1(i))=(a in+1(i) ）/aii(i)
二、算法描述
1、消元
对k=1…..n-1
消元因子： C= aik(k)/ akk(k) ( i= k+1….n ）
从求解过程可以看出，在第一种解法中，乘以的系数为 m=5.291/0.0030，第二种解法中，乘以的系数为 m=0.0030/5.291。我们希望m尽量小，希望主元尽可能大， 就有了列主元消去法（按列）。
i2
(1)
1n ( 2) 2n ( 3) 3n ( 3) nn
(2)
，b
(3)
b b b b
(1)
1 ( 2) 2 ( 3) 3 ( 3) n



a
b
(3) ij
a ij m i2a 2 j
bi b2 mi2
(2) (2)
m
i, j
a i2
a
(2) 22
(3) i
3, 4 , ,n
→
(1)
a
(1)
(1) ij
,
bi →
(1) (1)
b
(1) i
T
A
(1)
X b : A [ a ij ] , b
( b( 1 ),, b( 1 ) ) n 1
第一步消元：
(1) 若 a11 ≠0 : 1) (1) (第二行 ) （第一行） a(21 a11 → (新第二行 )
1) (1) (第三行 ) (第一行 ) a( a 31 11 → (新第三行 )
直接法：在假定没有舍入误差的情况下，经过有限次 运算可以求得方程组的精确解；(快速有效)
迭代法：从一个初始向量出发，按照一定的迭代格 式，构造出一个趋向于真解的无穷序列(节省内存)。
第二节 高斯消去法
高斯消去法是解线性方程组最常用的方法之一，
它的基本思想是通过逐步消元，把方程组化为系数矩
阵为三角形矩阵的同解方程组，然后用回代法解此三
系数矩阵与常数项：
(1) a 11 0 (n) A 0 0
a a a a 0 a
12 (2) 22
(1)
(1) 13 (2) 23 (3) 33

0
0
a1n (2) a 2n (n) (3) ，b a 3n (n) a nn
x1 2 2 x2 2 x3 2
考虑 一般n 阶线性方程组：
a11 x 1 a21 x 1 an1 x1 a x ... 1a n xn 1 b 1 2 2 a x ... 2a n xn 2 b 矩阵形式 2 2 2 an 2 x 2 ... ann xn bn
得到新同解方程组：
A
（2）
x b
(1)
（2）
a
其中 A
( 2)
(1)
11
0 0
a a a
(1)
(1)
12 ( 2) 22

a a a
1n ( 2) 2n

( 2) n2 ( 2) nn
b ，b b
(2)
(1)
1 ( 2) 2
b
(1) i1
( 2) n
这里
a
(2) ij
aij mi1 a1 j
(1)
m a a
i1
(1)
11
第二步消元： 若
a
a a a a
(2) 22
0 ，对除第一行第一列外

的子阵作上计算：
a A
( 3)
(1)
11
0 0 0
a a
(1)
(1)
12 ( 2) 22
13 ( 2) 23 ( 3) 33 ( 3) n3
(2)
0 0
(2)
a a a a
如果将两个方程互换，再采用高斯消去法解方程组
5.291x1 6.130x2 46.78 0.0030x1 59.14x2 59.17
消元后得59.14x2=59.14，则x2=1.000
将x2代入第一个方程中，得 x1=10.000
ቤተ መጻሕፍቲ ባይዱ
此时，利用高斯消去法得到的结果与精确解一致。
Ax b
高斯消去法的主要思路：
将系数矩阵 A 经过消元过程化为上三角矩阵，然后回代 求解。
=
即:
a11 x1 a12 x2 ... a1n xn b1 a21 x1 a22 x2 ... a2n xn b2 an1 x1 an2 x2 ... ann xn bn
系数变化：
① aij(k+1) = aij(k) （i≤ k) ② aij(k+1) = aij(k) - C. akj(k) ( i > k , j=k+1,…,n+1 )
2、回代
第 i次回代公式 （ i=n,n-1….1) Xi(即a in+1(i))=(a in+1(i) ）/aii(i)
三、特点
所以，第K次消元时（后）（K=1….n-1)
消元因子： M = aik(k)/ akk(k) ( i= k+1,n ） 系数变化：
① aij(k+1) = aij(k) （i≤ k)
② aij(k+1) = aij(k) - M. akj(k) (i>k , j=k+1…n+1) 最后得到：
[A(n) | b(n)] (n-1 次消元后）其增广矩阵为：
1 2 2 2 ( A, b) 2 3 3 4 4 1 6 3 2 2 1 2 0 1 7 8 0 0 6 1 6 1
解：
2 2 1 2 0 1 7 8 0 9 2 11
x3 1
x2 8 7 x3 1
角形方程组可得方程组的解。
我们知道，下面有3种方程的解我们可以直接求出：
①
bi A diag(a11, a22 ,, ann ) xi , i 1,, n aii
②上三角
n u11 u12 u1n bi uij x j u22 u2 n j i 1 A x , i n,,1 i uii u nn
对方程组，作如下的变换，解不变 ①交换两个方程的次序 ②一个方程的两边同时乘以一个非0的数 ③一个方程的两边同时乘以一个非0数，加到另一个方程 因此，对应的对增广矩阵(A,b)，作如下的变换，解不变。 ①交换矩阵的两行
②某一行乘以一个非0的数
③某一行乘以一个非0数，加到另一行
举例（一）
x1 2 x2 2 x3 2 例：直接法解线性方程组 2 x1 3 x2 3 x3 4 4 x1 x2 6 x3 3
(第n行) （第一行） a n1
(1)
a → ( 新第n行 )
11
(1)
相当于第i个方程-第一个方程×数→新的第i方程 同解！第一方程不动！
上述消元过程除第一个方程不变以外,第2—第 n
个方程全消去了变量 1，而系数和常数项全得到新值：
(1) (1) (1) (1) (1) a1n x n b1 a 11 x1 a 12 x 2 a 13 x 3 (2) (2) (2) (2) a 23 x 3 a 2 n x n b 2 a 22 x 2 (2) (2) (2) (2) a 32 x 2 a 33 x 3 a 3n x n b 3 (2) (2) (2) (2) a n 3 x 3 a nn x n b n a n2 x 2
其绝对值很小时，在高斯消去法中，因为M
= aik(k)/ akk(k) ，所以不是因为M数值过大，就 是舍入误差过大，与实际的解相差很远。
零主元或小主元问题
例如：求解下列方程组
0.0030x1 59.14x2 59.17 5.291x1 6.130x2 46.78
此方程组的准确解为：x1=10.00；x2=1.00 下面采用高斯消去法解方程组（取四位有效数字）， 消元后得-1043x2=-1044，则x2=1.001. 将x2代入第一个方程中，得 x1=-9.713 显而易见，利用高斯消去法得到的结果与精确解相差太悬殊了 从求解过程可以看出，在第一种解法中，乘以的系数为 m=5.291/0.0030
a11 a12 ( 2) 0 a22 0 0 0 0
a13 a a
( 2) 23 ( 3) 33

a1n
( 2) 2n ( 3) 3n
a a
a
0

(n) nn
b1 ( 2) b2 ( 3) b3 (n) bn
③下三角
i 1 l11 bi lij x j l21 l22 j 1 A x , i 1,, n i lii l l l nn n1 n 2
消元法就是对方程组做些等价的变换，变为我们已知的3种类型 之一，而后求根。
3 ) ≠0 ，则此消去过程可依次进行下去。 若 a( 33
第 n 1 步消去过程后， 得到等价三角方程组。
A
(n)
x b
(n)