2-1高斯（ Gauss）消去法
一、消元过程
),( bAA ?
?
?
?
?
?
?
?
?
?
?
?
?
?
)1()1()1(
2
)1(
1
)1(
2
)1(
2
)1(
22
)1(
21
)1(
1
)1(
1
)1(
12
)1(
11
nnnnn
n
n
baaa
baaa
baaa
?
????
?
?
),( )1()1( bA记?
bAx ?对线性方程组
对其增广矩阵施行行初等变换,
0)d e t ( ?A如果
0)1(11 ?a假定
定义行乘数
ni
a
am i
i,,3,2)1(
11
)1(
1
1 ???
?
?
?
?
?
?
?
?
?
?
?
?
?
)2()2()2(
2
)2(
2
)2(
2
)2(
22
)1(
1
)1(
1
)1(
12
)1(
11
0
0
nnnn
n
n
baa
baa
baaa
?
????
?
?
),( )2()2( bA
则行第行第,1 1imi ??
)1(11)1()2( jiijij amaa ??
)1(11)1()2( bmbb iii ??
nji,,3,2,??
ni,,3,2 ??
),( )1()1( bA
0)1(11 ?a如果 0)d e t ( ?A由于
元素不为零的第一列中至少有一个则 A
交换后消元
行的第一行与第则将如 1)1()1()1( 1 ),(,0
1
ibAa i ?
?
?
?
?
?
?
?
?
?
?
?
?
)2()2()2(
2
)2(
2
)2(
2
)2(
22
)1(
1
)1(
1
)1(
12
)1(
11
0
0
nnnn
n
n
baa
baa
baaa
?
????
?
?
且
将化为步后第因此 ),(,1,)1()1( bAk ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
)()()(
)()()(
)2(
2
)2(
2
)2(
22
)1(
1
)1(
1
)1(
12
)1(
11
k
n
k
nn
k
nk
k
k
k
kn
k
kk
n
n
baa
baa
baa
baaa
?
???
?
???
??
??
),( )()( kk bA
),( )1()1( bA
nkiaam k
kk
k
ik
ik,,1)(
)(
????
则行第行第,ikmki ??
)()()1( kkjikkijkij amaa ???
)()()1( kkikkiki bmbb ???
nkji,,1,???
nki,,1 ???
),( )()( nn bA
?
?
?
?
?
?
?
?
?
?
?
?
?
)()(
)2(
2
)2(
2
)2(
22
)1(
1
)1(
1
)1(
12
)1(
11
n
n
n
nn
n
n
ba
baa
baaa
???
?
?
),( )1()1( bA
将化为步后当经过 ),(,1 )1()1( bAnk ??
0)d e t ( ?A由于
nia iii,,2,10)( ???可知
有唯一解上三角形方程组因此 )()(,nn bxA ?
二、回代过程
)(
)(
n
nn
n
n
n a
bx ?
1,2,,2,1 ???? nni?
?
?
?
?
?
?
)(
1
)()(
i
ii
n
ij
j
i
ij
i
i
i
a
xab
x
?
??
?
?
nia iii,,2,10)( ???由于
的解因此得到线性方程组 bAx ?
所以
三、高斯消去法的计算量
步消元时作第 k
乘法次数,次)1)(( ??? knkn
除法次数,次)( kn ?
数为步消元乘除法运算总次作第 k
次)2)(( ??? knkn
总次数为步消元需作乘除法运算完成全部 1?n
?
?
?
???
1
1
)2)((
n
k
knkn
于是 Gauss消去法的乘除法运算总的次数为
MD
33
2
3 n
nn ??? )(3 2
3
nOn ??
很大时当 n
33
2
3 n
nn ???MD
3
3n
?
全部回代过程需作乘除法的总次数为
?
?
??
n
i
in
1
)1( 22
2 nn
??
四、高斯消去算法
输入：
输出
步骤
? ? 11,1,,????? njniabAn ij的元素；增广矩阵方程组的阶数
或方法失败的信息方程组的解 n21 x,,x,x ?
S1 对 k=1,2,…,n-1 做 S11~S12
S11,,0 ；停机则输出方法失败的信息若 ?
kka
S12
.
1,...,1;/
,...,1
kjikijij
kkikik
aaaa
nkj
aaa
nki
??
???
?
??
置
对
置
对
S2,,0 ；停机则输出方法失败的信息若 ?
nnaS3
ii
n
ij
jijni
i
nnnnn
a
xaa
x
nni
aax
?
?
?
?
?
?
?
?
?
?
???
?
?
??
?
?
1
1,
1,
1,...,2,1;/
置
对
置
S4 ? ?,;,...,,
21 停机输出 nxxx
作业：
P49 习题 1