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

考虑 一般n 阶线性方程组：
x ... 1a n xn 1 b a11 x 1 a 1 2 2 x ... 2a n xn 2 b 矩阵形式 a21 x 1 a 2 2 2 an1 x1 an 2 x 2 ... ann x n bn
a 2n b 2 a 3n b 3
(3)
(3)
a nn b n
(3)
3 ) ≠0 ，则此消去过程可依次进行下去。 若 a( 33
第 n 1 步消去过程后， 得到等价三角方程组。
A
(n)
x b
(n)
(1) (1) (1) a 11 x1 a 12 x 2 a 13 x 3 (2) (2) a 23 x 3 a 22 x 2 (3) a 33 x 3
1、优点： 公式简明，容易程序化
2、缺点： 第k次消元时， 必须 a kk ≠ 0 , 且当
a kk 0 时 ，误差很大， 数值不稳定
(p35 N-S图）
第三节 GAUSS列主元消去法
一、高斯消去法的缺点
在简单的高斯消去法中，如果遇到 a（k）kk =0,
则消去过程就会中断，如果a（k）kk ≠ 0 ，但

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 ，对除第一行第一列外
直接法：在假定没有舍入误差的情况下，经过有限次 运算可以求得方程组的精确解；(快速有效)
迭代法：从一个初始向量出发，按照一定的迭代格 式，构造出一个趋向于真解的无穷序列(节省内存)。
第二节 高斯消去法
高斯消去法是解线性方程组最常用的方法之一，
它的基本思想是通过逐步消元，把方程组化为系数矩
阵为三角形矩阵的同解方程组，然后用回代法解此三
1 2 2 2 ( A, b) 2 3 3 4 4 1 6 3 2 2 1 2 0 1 7 8 0 0 61 61
解：
2 2 1 2 0 1 7 8 0 9 2 1 1
x3 1 x2 8 7 x3 1 x1 2 2x2 2x3 2
Ax b
高斯消去法的主要思路：
将系数矩阵 A 经过消元过程化为上三角矩阵，然后回代 求解。
=
即:
a11 x1 a12 x2 ... a1n xn b1 a21 x1 a22 x2 ... a2n xn b2 an1 x1 an2 x2 ... ann xn bn
讨论第K次消元，得到消元公式 第K次消元目的：aik(k)=0 (i=k+1….n), 设akk(k) ≠ 0 ,为使aik(k)=0 (i=k+1….n）选取适当因子M使 aik(k)- M akk(k) =0 可求出 M = aik(k)/ akk(k) 第i个方程其他系数的变化为 （ Ri aij(k+1) = aij(k) – M. akj(k) ( i= k+1….n , j=k+1…..n+1) - M.Rk )
第四章 线性代数方程组的解法
引言 高斯消去法 高斯列主元消去法 矩阵分解法 向量和矩阵范数 解线性代数方程组的迭代法
第一节 引言
快速、高效地求解线性方程组是数值线性代数研究中 的核心问题，也是目前科学计算中的重大研究课题之一。 各种各样的科学和工程问题，往往最终都要归结为求 解一个线性方程组。 线性方程组的数值解法有：直接法和迭代法。
所以，第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 次消元后）其增广矩阵为：

的子阵作上计算：
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
i2
(1)
1n ( 2) 2n ( 3) 3n ( 3) nn
(2) (2) 22
，b
(3)
b b b b
其绝对值很小时，在高斯消去法中，因为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 0 0 0
a12 a
( 2) 22
a13 a a
( 2) 23 ( 3) 33

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

(n) nn
b1 ( 2) b2 ( 3) b3 (n) bn
回代： 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 ）
(1)
1 ( 2) 2 ( 3) 3 ( 3) n



a
b
(3) ij
a ij mi2a 2 j
b i b 2 mi 2
(2) (2)
m a a
i2
(3) i
i, j
3, 4,
,n
每步消元，先计算系数，然后计算矩阵新元素及右端项
得到同解方程组
( 3 ) ( 3 ) x = b A
如果将两个方程互换，再采用高斯消去法解方程组
5.291x1 6.130x2 46.78 0.0030x1 59.14x2 59.17
消元后得59.14x2=59.14，则x2=1.000
将x2代入第一个方程中，得 x1=10.000
此时，利用高斯消去法得到的结果与精确解一致。
a 1n x n b 1
(2) (3)
(1)
(1) (2)
a 2n x n b 2 a 3n x n b 3
(3)
a x b
nn n
(n)
(n) n
系数矩阵与常数项：
(1) a 11 0 (n) A 0 0
a a a a 0 a
12 (2) 22

) (第n行) （第一行） a(n1 1
a → ( 新第n行 )
11
(1)
相当于第i个方程-第一个方程×数→新的第i方程 同解！第一方程不动！
上述消元过程除第一个方程不变以外,第2—第 n
个方程全消去了变量 1，而系数和常数项全得到新值：
(1) (1) (1) a 11 x1 a 12 x 2 a 13 x 3 (2) (2) a 23 x 3 a 22 x 2 (2) (2) a 32 x 2 a 33 x 3 (2) (2) a n3 x 3 a n2 x 2
对方程组，作如下的变换，解不变 ①交换两个方程的次序 ②一个方程的两边同时乘以一个非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
从求解过程可以看出，在第一种解法中，乘以的系数为 m=5.291/0.0030，第二种解法中，乘以的系数为 m=0.0030/5.291。我们希望m尽量小，希望主元尽可能大， 就有了列主元消去法（按列）。
二、列主元消去法
a1n b1
(2) (3) (1) (1) (2)
(1) (1) (1) a11 x1 a12 x 2 a13 x 3 (2) (2) a 23 x 3 a 22 x 2 (3) a 33 x 3 (3) a x n 3 3
系数变化：
① aij(k+1) = aij(k) （i≤ k) ② aij(k+1) = aij(k) - C. akj(k) ( i > k , j=k+1,…,n+1 )