数值分析方法中方程求解的直接法和迭代法
第3章 解线性方程组的直接法
一、
消元法
1. 高斯消元法(加减消元)：首先将A 化为上三角阵，再回代求解。
11121121222212n n n n nn
n a a a b a a a b a a a b ⎛⎫
⎪ ⎪
⎪
⎪⎝⎭ (1)(1)(1)(1)(1)11
121311(2)(2)(2)(2)222322
(3)(3)(3)3333()()000
00
n n n
n n nn
n a a a a b a a a b a a b a b ⎛⎫
⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝
⎭
步骤如下：
第一步：1
11
1,2,,i a i i n a -⨯
+=第行第行
11121121222212
n n n n nn
n a a a b a a a b a a a b ⎛⎫
⎪ ⎪
⎪
⎪⎝⎭ 111211(2)(2)(2)2222
(2)(2)(2)2
00n n
n nn
n a a a b a a b a a b ⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭
第二步：(2)2
(2)222,3,
,i a i i n a -⨯+=第行第行 111211(2)(2)(2)2222
(2)(2)(2)200n
n
n nn
n a a a b a a b a a b ⎛⎫
⎪ ⎪ ⎪ ⎪⎝
⎭
111213
11
(2)(2)(2)(2)
222322
(3)(3)(3)
33
33(3)(3)(3)
3
00000n n n n nn n a a a a b a a a b a a b a a b ⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝
⎭
类似的做下去，我们有：
第k 步：()
()k ,1,
,k ik
k kk
a i i k n a -⨯+=+第行第行。
n －1步以后，我们可以得到变换后的矩阵为：
11121311(2)(2)(2)(2)222322
(3)(3)(3)3333()()00000
n n n
n n nn
n a a a a b a a a b a a b a b ⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝
⎭
注意到，计算过程中()
k kk a 处在被除的位置，因此整个计算过程要保证它不为0。 所以，Gauss 消元法的可行条件为：()
0k kk
a ≠。 就是要求A 的所有顺序主子式均不为0，即
11
11
det 0,1,,i i ii a a i n a a ⎛⎫ ⎪
≠= ⎪ ⎪⎝⎭
因此，有些有解的问题，不能用Gauss 消元求解。
另外，如果某个()
k kk a 很小的话，会引入大的误差。
2. 列主元消元法
在Gauss 消元第k 步之前，做如下的事情：
若()()
max ||||k k ik
jk k i n
a a ≤≤=交换k 行和j 行 2134
354
3521316
216
2⎛⎫⎛⎫
⎪ ⎪→ ⎪ ⎪ ⎪ ⎪⎝
⎭⎝
⎭
435435435
1
12132130002244442131130000
44227⎛
⎫⎛
⎫⎛⎫ ⎪ ⎪ ⎪
⎪
⎪ ⎪ ⎪ ⎪ ⎪-
→→ ⎪ ⎪ ⎪ ⎪
⎪ ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭
其实就按行变换，不改变方程组的解，同时又有效地克服了Gauss 消元地缺陷。 3. Gauss-Jordan 消元法
将在Gauss 消元第k 步，变为（遇上11a =0的则需要换一行）：
()
()k ,1,
,1,1,,k ik
k kk
a i i k k n a -⨯+=-+第行第行
将该行上、下三角地部分都变为0，即对角阵，同时主元系数也要消，这样就不用回代了。
10001
00
1⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭
二、
直接分解法
Gauss 消元法的第k 步：
()()k ,1,
,k ik
k kk
a i i k n a -⨯+=+第行第行
从矩阵理论来看，相当于左乘矩阵：
()()()
()1()11
,,1,
,1
1k k ik
ik k k k k
kk
k nk
a l i k n l a l +⎛⎫ ⎪ ⎪
⎪-==+ ⎪ ⎪ ⎪ ⎪ ⎪⎝
⎭
。
因此，整个Gauss 消元法相当于左乘了一个单位下三角阵。
21()
1()
()
1
1
11
1
1k k k
k n n nk
nn l L l l l l +-⎛⎫ ⎪ ⎪ ⎪=
⎪ ⎪ ⎪ ⎪ ⎪⎝
⎭
所以有 LA U =，L 为单位下三角阵，U 为上三角阵。
⇒1 A L U -=
因此Ly b
Ax b LUx b Ux y
=⎧=⇒=⇒⎨=⎩
我们可以通过2次反代过程求解方程组，分解的理论由Gauss 消元得出，因此分解能够进行的条件与Gauss 消元一样。 1. Doolittle 分解
L 为下三角，U 为单位上三角
