(行 系 数 i,k ) l
1.2.2
For j=k+1,…, n
aij- aik akj aij(新) bi - aik bk bi (新)
*常用|akk|≤
步骤 2. 步骤 3.
bn /ann xn For k=n-1,…,1 3.1 3.2
(回代)
bk s For j=k+1,…,n
b1( 0 ) (1) b2 (1) bn
注意：若a11（0） ＝0，因为 det（A）0，在A的第1列元素中至 少有某ai1（0） 0将i行与第1行交换，再作第1步 。
(0 a11 ) 假定已完成k－1步消元， ( 0) ( 0) ( A( k 1) , b( k 1) ) ( A ,b ) (0 a12 ) (1 a22)
迭代法：从一个初始向量出发，按照一定的迭代格 式，构造出一个趋向于真解的无穷序列。
举例
x 2 x2 2 x3 2 例：直接法解线性方程组 1 2 x1 3 x2 3 x3 4 4 x1 x2 6 x3 3
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 11
x3 1 x2 8 7 x3 1 x1 2 2x2 2x3 2
第四章 解线性方程组的直接法
a11 x1 a12 x 2 a1n x n b1 a x a x a x b 21 1 22 2 2n n 2 a n1 x1 a n 2 x 2 a nn x n bn
回代公式
( xn annn)1 , ( xk ak kn)1 ,
j k 1
( akjk ) x j k n 1, ,1
n
1 1 2 求解一个三角形方程组 n个除法与 i 1) n(n 1) n 需 （ 2 2 i 1 次加法与乘法。
引言
快速、高效地求解线性方程组是数值线性代数研究中 的核心问题，也是目前科学计算中的重大研究课题之一。 各种各样的科学和工程问题，往往最终都要归结为求 解一个线性方程组。 线性方程组的数值解法有：直接法和迭代法。
直接法：在假定没有舍入误差的情况下，经过有限次 运算可以求得方程组的精确解；
(i k 1, n)
(3.3)
当经过 n 1步后, ( A(0) , b (0) )将化为 k
( A(0) , b(0) )
(0 a11 ) ( n 1) ( n 1) (A ,b ) (0 a12 ) (1 a 22) (0 a1n ) ( a 21) n
基本思想：通过对（4.1）消元，逐步将（4.1）简化为同解的上三 角方程组（---消元过程），再由下而上地解此方程组，求得解 x（ ---回代过程）。
若det（A）0，记其增广矩阵
A ( A, b) ( A( 0) , b ( 0) )

( a110 ) (0) a21 (0) a n1 ( 0 a120 ) a1(n ) (0 ( a22 ) a20 ) n ( (0 an0 ) ann ) 2
det() 0
1. 计算行系数
lik
(k aik 1) (k akk 1)
(i k 1, n)
(3.2)
2. 第 i行 第 k行 lik , 则 ( ( (k aijk ) aijk 1) lik akj 1)
( bi(k ) bi(k 1) lik bkk 1) ( j k 1, n)
n
例1 用Gauss消元法解线性方程组
2 x1 2 x2 3 x3 3 4 x1＋7 x2＋7 x3＝1 2 x ＋4 x ＋5 x ＝－7 － 1 2 3
解:(略)
算法组织 将增广矩阵(A,b)放入一个二维数组.消去每一步算出的aij( k)放入 aij的位置,bi ( k) 放入bi ,lik放在aik上.消去完毕后,数组各位置上的数据 如下示: (0 (0 (0 a11 ) a12 ) a1n ) b1(0) (1 ( ( l 21 a22) a 21) b21) n (n ( l l n 2 a nn1) bnn 1) n1 A 回代过程的计算没有数据组织问题. b
“回代”过程较简单.上三角方程(3.4)有唯一解,其解可由下至 上得出: ( ( xn bnn 1) / ann (3.5) xn bnn 1) / ann (3.5) n n ( k 1) ( k 1) x (b ( k 1) ( k 1) (k (k aik 1) xk ) / akk 1) (k n 1,1) aik xk ) / akk (k n 1,1) xk (bk k k j i 1 j i 1 此即Gauss消去法.
( bi(1) bi(0) li1b1 0) , ( j 2, n)
这样,
( A( 0) , b( 0) )
( a110 ) 0 (1) (1) ( A ,b ) 0
( a120 ) (1 a22) ( an12)
0 a1(n ) ( a21n) (1 ann)
算法 Guass消去法 输入 n, aij ,bi ,(i,j=1,..,n)
说明:系数矩阵存放于数组 A中,右端向量放于数组b中
输出 解
x1, x2 …, xn
k=1,2,…,n-1 if akk=0* 1.2.1 (消元) 1.1 1.2 Then 输出”不能消元” stop
步骤1. For
for i=k+1,…,n aik/akk aik 1.2.2.1 1.2.3
3.2.1
3.3 步骤 4. End
s- akj xj s
s / akk xk
高斯消去法的计算量分析
高斯消去法的乘除总运算(由于计算机作乘除运算所需时间远大于作加减运 算所需时间,故我们只讨论乘除运算量)分析为
消元次数k 1 2 . . . k . . n-1
消元乘法次数 消元除法次数 n(n-1) n-1 (n-1)(n-2) n-2
（4.1）
§1 高斯消去法
1．三角形方程组的解法
b1 a11 x1 a x a x b2 21 1 22 2 a n1 x1 an 2 x2 ann xn bn
（4.2）
a11 x1 a12 x2 a1n xn b1 a 22 x2 a 2 n xn b2 a nn xn bn
消元公式
( ( k ) akjk 1) j k , k 1, , n 1 akj ( k 1) akk (k ) ( k 1) ( k 1) (k ) aij aij aik akj j k 1, , n 1 i k 1, n
AX = b
a11 a12 a 21 a 22 A a n1 a n 2 a1n a2n a nn x1 x2 X x n b1 b2 b b n

综述:若A非奇,总可通过带有行交换或不带有行交换的消元过
程,将A化成非奇三角矩阵A(n-1).因此, 回代求解过程也可进行到底. 但实际中,A是否非奇异难以判定.算法应考虑: 1.消元过程某一步找不到非零元,于是计算中断. 2.消元可进行到底,但ann(n-1) = 0,回代求解过程无法进行.
故算法设计要考虑以上情况,给出计算中断的信息.
（4.3）
2．高斯消去法
a11 x1 a12 x2 a13 x3 a1n xn a1, n 1 a 21 x1 a 22 x2 a 23 x3 a 2 n xn a 2, n 1 a n1 x1 a n 2 x2 a n 3 x3 a nn xn a n , n 1
而每个乘积是n个元素相乘，因此共需乘法次 数 ( n + 1）·n!( n － 1)= ( n + 1) ! ( n － 1)
当n=20时( n + 1) ! ( n － 1)≈9.7×1020。
要完成这么多次乘法，在每秒做一亿次乘法 运算的计算机上，也需30.8万年。因此克莱 姆法则在实际计算中不适用。
从这个表可以看出用计 算机解含有 个未知量的线性方程组 100 是一件很简单
Gauss消元法是解线性方程组 的基本方法，它是直接 法的基础，具有计算简
2.1.2
高斯消去法的运算量
高斯消去法比起克莱姆法则和约当消去法，
主要长处就是运算量较少。
用克莱姆法则求解n阶线性方程组，需计算
n+1个行列式；每个行列式是n!个乘积之和，


(n a nn1)
b1(0) (1) b2 ( bnn 1)
且 akk（k-1） ≠0(i=1,…, n) ,∣A∣=a11(0)a22(1)…ann(n-1).于是,得到上三 角方程组 A( n 1) x b ( n 1) (3.4)
这 就 完 成 了消 去" 过 程. "
b1( 0 ) (0) b2 (0) bn
设k=1，第1步消元。假定a11（0） 0，从（4.1）中用第1个方 程消去下面n-1个方程的未知数x1。对 ( A(0) , b(0) )作如下计算： ai(10 ) 1. 计算行系数 li1 ( 0 ) i 2, n a11 2. 第 i行 第 1行 l , 则 ( ( aij1) aij0 ) li1 a1( 0 ) (i 2, n ) i1 j