mik
b(k ) k
(i, j k 1, ..., n)
共进行 n？ 步1
mik
a(k) ik
/ ak(kk )
a1(11)
a(1) 12
a(2) 22
... ...
...
(i k 1, ..., n)
a(1) 1n
a(2) 2n ...
a(n) nn
x1
x2 ... xn
➢ 选主元消去法
例：单精度解方程组
109
x1
x2
1
x1 x2 2
/*
精确解为
x1
1 1 109
8个
1.00...0100...和
x2 2
x1
8个
0.99 ...9899...*/
用Gaussian Elimination计算：
m21 a21 / a11 109 8个 a22 1 m21 1 0.0 ...01109 109 109
b2 2 m21 1 109
109 1
1
0
109
109
小主元 /* Small pivot element */ 可能导致计
算失败。
x2 1, x1 0
全主元消去法 /* Complete Pivoting */
每一步选绝对值最大的元素为主元素，保证 | mik | 。1
Step k:
b(1) ]
a(1) 11
...
a(1) 1n
b1(1)
A b (2) (2)
1
Step n 1:
Ln1Ln2 ... L1
Ab
a1(11)
a(1) 12
a(2) 22
...
a(1) 1n
...
a(2) 2n
... ...
b(1) 1
b(2) 2
...
1
其中
Lk =
a(n) nn
b(n) n
1
mk1,k ...
mn,k
1
1
Lk1
1
mk 1,k ...
mn,k
§2 Matrix Factorization – Matrix Form of G.E.
1
L11
L21
...
L1 n1
1
mi, j
记为 L
1
1
a(1) 11
记U=
A LU a(1) 12
a(2) 22
seHo...nd...lesdFs...ovCfiyyfooWasebu/foUs*rcaealphmgIuvtht12tr(u(...eewaehx1h2nenoleea))vndcsmaornnthteiinirvhfyttzsreisiya’exoeeyctaioryAm,uLGtydfbsAwuoop..aypEbl单yirlohfscktyelemihegwatohnra位esmv?iueostaevmtre??ewr,eoib下foa-!?itnrtfxnhnoiWeroate三ilmegsrayndhnunedh角ylgaaurv阵leartomatrix
b
b1(1) ...
bn(1)
Step 1：设a1(11) ，0计算因子
mi1
a (1) i1
/
a (1) 11
(i 2, ..., n)
将增广矩阵/* augmented matrix */ 第 i 行 mi1 第1行，
得到
a (1) 11
a (1) 12
...
a (1) 1n
A( 2 )
ank
注：稳定性介于列主元法和全主元法之间。
§2 三角分解法 /* Matrix Factorization */
➢ 高斯消元法的矩阵形式 /* Matrix Form of G.E. */：
Step 1: mi1 ai1 / a11 (a11 0)
1
记 L1 =
m21 ...
1
mn1
，则 L1[ A(1)
b1(1) b (2)
其中
a(2) ij
b(2) i
a (1) ij
b(1) i
m
i
a (1)
1 1j
mi1b1(1)
(i, j 2, ...,n)
Step
k：设
a
(k kk
)
， 0计算因子
且计算
a ( k 1) ij
b( k 1) i
a(k) ij
b(k ) i
mik
a(k kj
)
s若ubAm的at所ric有eWWtsshas顺mhesh*ko( ii/oaaa)lN序fku均iltltN-nolutteiiio主hdfft0o不suioanautrs,n子onni为n(uia(iiennniqwnic)e)xtq式u0hdexiuwesg，ikiest0i0ne/stt*?hrt则s.??ed.ktreh高ctehei斯ariwm-ntih消gitnhea元nt无of需le换adi行ng即可
省去换列的步骤，每次仅选一列中最大的元。
| aik ,k
|
max
kin
|
aik
|
0
§1 Gaussian Elimination – Pivoting Strategies
例：
109
1
1 1
1 2
1 109
1 1
2 1
1 0
1 1
2 1
x2 1 , x1 1 ✓
注：列主元法没有全主元法稳定。
优选数值分析第三章解线性方 程组的直接方法
求解
A
x
b
➢ 高斯消元法：
思 首先将A化为上三角阵 /* upper-triangular matrix */， 路 再回代求解 /* backward substitution */。
=
消元
记
A(1) A (ai(j1) )nn ,
b (1)
① 选取 | aik jk源自|maxki, jn
|
aij
|
0;
② If ik k then 交换第 k 行与第 ik 行; If jk k then 交换第 k 列与第 jk 列;
③ 消元
注：列交换改变了 xi 的顺序，须记录交换次序，解完后再 换回来。
列主元消去法 /* Partial Pivoting, or maximal column pivoting */
bb12((12))
...
bn(n)
§1 Gaussian Elimination – The Method
回代
xn
b(n) n
/
a(n) nn
n
b( i ) i
a(i ij
)
x
j
xi
j i 1
a(i) ii
(i n 1, ...,1)
定理
principal
TWhheantwifewmeucsatnf’itnd the
进行到底，得到唯r一ow解. 。
注：消事元实及上行，交只换要d，eAt(将A非i 方)奇程异a.1.组1.，化即.. .. ..为Aa.三.1.i1 角存形在方，程则组可，通求过出逐唯次
一解。
ai1 ... aii
定理（矩阵的 LU分解） 设A为n阶矩阵，如果A的顺序主子式Di 0(i 1, 2, , n 1)， 则A可分解为一个下三角矩阵L和一个上三角矩阵U的乘积， 且这种分解是唯一的.
例：11
109 1
109
2
1 0
109 109
109
109
x2 1 ,
x1
0
标度化列主元消去法 /* Scaled Partial Pivoting */
对算每一一次行。计以算后每s注i一意数步m1：学考ja这上x虑n |两严子a个格ij列|方等。a程价为...kk 组。省中在时as间iik 最，s大i 只的在ai初k 为始主时元计。