第２章 解线性方程组的直接解法§0 引言11112211211222221122n n n n n n nn n na x a x a xb a x a x a x b a x a x a x b +++=⎧⎪+++=⎪⎨⎪⎪+++=⎩L L L L111212122212112,(,,,),()n n T T n nn n nn a a a a a a A x x x x b b b a a a ⎡⎤⎢⎥⎢⎥===⎢⎥⎢⎥⎢⎥⎣⎦LL L L L L LAx b =若A 非奇异，即det()0A ≠，方程组Ax b =有唯一解。

由 Cramer 法则，其解det(),1,2,,det()i i A x i n A ==L其中i A 为用b 代替A 中第i 列所得的矩阵。

当n 大时，1n +个行列式计算量相当大，实际计算不现实。

121212(,)12det()(1)n n ni i i i i i n i i i A a a a τ=-∑L L L§1 Gauss 消去法（I ）Gauss 消去法的例子（1）1231123212336()123315()18315()x x x E x x x E x x x E ++=⎧⎪-+=⎨⎪-+-=-⎩2131()12(),()(18)()E E E E -⨯--⨯（2）12312342356()15957()211793()x x x E x x E x x E ++=⎧⎪--=-⎨⎪+=⎩方程组13()()E E -与方程组145(),(),()E E E 同解541()21()()15E E --得 （3）1231234366()15957()3()x x x E x x E x E ++=⎧⎪--=-⎨⎪=⎩由（3）得3213,2,1x x x ===123(,,)(1,2,3)T T x x x =（3）的系数矩阵为1110159001⎡⎤⎢⎥--⎢⎥⎢⎥⎣⎦，上三角 矩阵。

（II ）Gauss 消去法，矩阵三角分解Ax b =111211,1212222,112,1n n n n n n nnn n a a a a aa a a Ab a a a a +++⎡⎤⎢⎥⎢⎥⎡⎤=⎣⎦⎢⎥⎢⎥⎢⎥⎣⎦LM L M LL M M LM 令(1),1,2,,;1,2,,,1ij ij a a i n j n n ===+L L(1)(1)A b A b ⎡⎤=⎡⎤⎣⎦⎣⎦ 第1次消去(1)110a ≠,令(1)11(1)11,2,3,,i i a l i n a ==L作运算：11()()i i i l E E E -+→ i E 表示第i 个方程（第i 行）2,3,,i n =L(2)(1)(1)1111102,3,,i i i a a l a i n =-==L(2)(1)(1)11,2,3,,,1ij ij i j a a l a j n n =-=+L(1)(1)(1)(1)111211,1(2)(2)(2)2222,1(2)(2)(2)(2)(2)2,1nn nn n nnn n a a a a a a a A b a a a +++⎡⎤⎢⎥⎢⎥⎡⎤=⎣⎦⎢⎥⎢⎥⎢⎥⎣⎦L L L L L 如果令211131111011n lL l l -⎡⎤⎢⎥-⎢⎥⎢⎥=-⎢⎥⎢⎥⎢⎥-⎣⎦MO 1(1)(2)1(1)(1)(2)(2)11;L A A L A b A b --⎡⎤⎡⎤==⎣⎦⎣⎦令1232210111n L l l -⎡⎤⎢⎥⎢⎥⎢⎥=-⎢⎥⎢⎥⎢⎥-⎣⎦M O(2)22(2)22,3,4,,.i i a l i n a ==L(1)(1)(1)(1)1112131(2)(2)(2)222321(2)(3)(3)(3)2333()(3)3nn nn n nn a a a a a a a L AA a a a a -⎡⎤⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎣⎦L L LL L 1(2)(2)(3)(3)2L A b A b -⎡⎤⎡⎤=⎣⎦⎣⎦进行k-1步后，得 ()()k k Ax b =,1(1)(1)(1)(1)111211,1(2)(2)(2)2222,1()()()()(),1()()()nn nn nn k k k k k kkknk n k k k nknna a a a a a a Ab a a a a a a ++++⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎡⎤=⎢⎥⎣⎦⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦L L L L LLLL LL L11,,1111kk kn kL l l -+⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥-⎢⎥⎢⎥⎢⎥-⎢⎥⎣⎦OM O1()()(1)(1)k k k k k L A b A b -++⎡⎤⎡⎤=⎣⎦⎣⎦M1(1)(1)()()1n n n n n L A b A b ----⎡⎤⎡⎤=⎣⎦⎣⎦(1)(1)(1)(1)111211,1(2)(2)(2)2222,1()(),1n n nn n n nnn n a a a a a a a a a +++⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦L LLL 以上完成了消去过程，A 非奇异()0n nn a ⇒≠；倒着求解11,,,n n x x x -L 这称为回代过程。

消去过程和回代过程结合起来称为（顺序）Gauss 消去法，从消去过程可以得出。

111(1)()121n n n L L L AA -----=L 其中()n A是一个上三角阵。

(1)1111()121()n n n A A L L L A------==L ()121n n n L L L A --=L1,,1111k k k n kL l l +⎡⎤⎢⎥⎢⎥⎢⎥≡⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦O M O记213132122112,111111n n n n n n l l l L L L L L l l l ---⎡⎤⎢⎥⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦L OM M L此矩阵是对角线元素为1的下三角矩阵，称其为单位下三角 阵。

定义1.1 设 ()ij n n A a ⨯= 令111212122212,1,2,,i i i i i iia a a a a a i n a a a ∆==LL L L L L12,,,n ∆∆∆L 是1至n 阶行列式，称为A 的顺序主子式。

Gauss 消去过程能进行下去的条件应为()0,1,2,,1i ii a i n ≠=-L ，而此条件必在消去过程中才能知道。

定理1.2()(1,2,,)i ii a i k =L 全不为零的充分必要条件是A 的顺序主子式0,1,2,,i i k ∆≠=L ，其中k n ≤证明“⇒”（必要性）设()0,1,2,,i ii a i k ≠=L ，则可进行消去过程的1k -步，每步()m A由A 逐次实行()()ij j i i l E E E -+→的运算得到，这些运算不改变相应顺序主子式的值，所以有(1)(1)(1)11121(2)(2)(1)(2)()2221122()mm mm mmm mma a a a a a a a a ∆==L L L L0,1,2,,m m k ⇒∆≠=L“充分性”设命题对于k-1成立，现设110,,0,0k k -∆≠∆≠∆≠L 。

由归纳假设有(1)(1)111,10,0k k k a a ---≠≠L ，Gauss 消去可以进行k-1步。

(1)A A =化为()()()1112()220k k k k A A AA ⎡⎤=⎢⎥⎣⎦ 其中()11k A 为对角元为(1)(1)111,1k k k a a ---L 的上三角阵。

由于()k A 是 由A 经“一行（方程）乘一数加至另一行（方程）”逐步得 到的，因此A 的k 阶顺序主子式等于()k A 的k 阶顺序主子式， 即(1)(2)(1)()1111221,1,()*det 0kk k k k k k k k kk A a a a a a ---⎡⎤∆==⎢⎥⎣⎦L 由 ()00k k kk a ∆≠⇒≠。

Gauss 消去过程()n A LA =其中L 为单位下三角阵，()n A 为上三角阵。

以后记为U ，那么A=LU定理1.3非奇异矩阵n n A R⨯∈，若其顺序主子式0,1,2,,1i i n ∆≠=-L ，那么存在唯一的单位下三角阵L和上三角阵U ，使得A=LU 。

证明 Gauss 消去过程已给出L ，U 。

下面证明唯一性设A 有两个分解，1122A LU L U ==其中12,L L 为单位下三角阵，12,U U 为上三角阵，因A非奇异1212,,,L L U U ⇒都可逆。

111212U U L L --=12U -仍为上三角阵，112U U -也是上三角阵，112L L -为单位下三角阵111212U U L L I--⇒==1212,U U L L ⇒==可以证明，当A 为奇异阵时，定理仍成立，A 的LU 分解 ，L 为单位下三角阵，U 为上三角阵，此分解称Doolittle 分解。

若将上三角阵U DU =%，其中D 为对角阵，U%为单位 上三角阵，并记L LD =% 那么有A LU=%% 其中L %为下三角阵，U%为单位上三角阵，此分解称为 Crout 分解。

A LDU =其中L 为单位下三角阵，D 为对角阵，U 为单位上三角阵，此称为A 的LDU 分解。

定理1.4 非奇异阵n n A R ⨯∈有唯一的LDU 分解（D 为 对角阵，L 为单位下三角阵，U 为单位上三角阵）的充分必 要条件是A 的顺序主子式121,,,n -∆∆∆L 皆是非零。

如果A 奇异，上述定理也成立。

§2 列主元Gauss 消去法例2.1 用三位十进制浮点运算求解512121.0010 1.00 1.001.00 1.002.00x x x x -⎧⨯+=⎨+=⎩ 解 用（顺序）Gauss 消去法52121111.0010a l a ==⨯(2)522222112 1.00 1.0010a a l a =-=-⨯ (2)52,3 2.00 1.0010a =-⨯在3位十进制运算的限制下，得(2)2,32(2)221.00a x a ==代回第一个方程得10x =，此解不对 求解不对的原因是 用小数11a 作除数，使21l 是个大数，在计算(2)2222a a 中的值完 全被掩盖了：如果对方程组先作变换12()()E E ↔， 再用Gauss 消去法可以得121.00, 1.00x x ==。

列主元消去法 进行第1步消去之前，在A 的第1列 中选出绝对值最大的元素11,i a 即1111max i i i na a ≤≤=，其中11i ≥。