数值分析方法中方程求解的直接法和迭代法第3章 解线性方程组的直接法一、消元法1. 高斯消元法(加减消元)：首先将A 化为上三角阵，再回代求解。

11121121222212n n n n nnn a a a b a a a b a a a b ⎛⎫⎪ ⎪⎪⎪⎝⎭ (1)(1)(1)(1)(1)11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()00000n n nn n nnn a a a a b a a a b a a b a b ⎛⎫⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭步骤如下：第一步：1111,2,,i a i i n a -⨯+=第行第行11121121222212n n n n nnn a a a b a a a b a a a b ⎛⎫⎪ ⎪⎪⎪⎝⎭ 111211(2)(2)(2)2222(2)(2)(2)200n nn nnn 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)200nnn nnn a a a b a a b a a b ⎛⎫⎪ ⎪ ⎪ ⎪⎝⎭11121311(2)(2)(2)(2)222322(3)(3)(3)3333(3)(3)(3)300000n n n n nn n a a a a b a a a b a a b a a b ⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭类似的做下去，我们有：第k 步：()()k ,1,,k ikk kka i i k n a -⨯+=+第行第行。

n －1步以后，我们可以得到变换后的矩阵为：11121311(2)(2)(2)(2)222322(3)(3)(3)3333()()00000n n nn n nnn a a a a b a a a b a a b a b ⎛⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭注意到，计算过程中()k kk a 处在被除的位置，因此整个计算过程要保证它不为0。

所以，Gauss 消元法的可行条件为：()0k kka ≠。

就是要求A 的所有顺序主子式均不为0，即1111det 0,1,,i i ii a a i n a a ⎛⎫ ⎪≠= ⎪ ⎪⎝⎭因此，有些有解的问题，不能用Gauss 消元求解。

另外，如果某个()k kk a 很小的话，会引入大的误差。

2. 列主元消元法在Gauss 消元第k 步之前，做如下的事情：若()()max ||||k k ikjk k i na a ≤≤=交换k 行和j 行 213435435213162162⎛⎫⎛⎫⎪ ⎪→ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭43543543511213213000224444213113000044227⎛⎫⎛⎫⎛⎫ ⎪ ⎪ ⎪⎪⎪ ⎪ ⎪ ⎪ ⎪-→→ ⎪ ⎪ ⎪ ⎪⎪ ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭⎝⎭其实就按行变换，不改变方程组的解，同时又有效地克服了Gauss 消元地缺陷。

3. Gauss-Jordan 消元法将在Gauss 消元第k 步，变为（遇上11a =0的则需要换一行）：()()k ,1,,1,1,,k ikk kka i i k k n a -⨯+=-+第行第行将该行上、下三角地部分都变为0，即对角阵，同时主元系数也要消，这样就不用回代了。

10001001⎛⎫ ⎪ ⎪ ⎪ ⎪⎝⎭二、直接分解法Gauss 消元法的第k 步：()()k ,1,,k ikk kka i i k n a -⨯+=+第行第行从矩阵理论来看，相当于左乘矩阵：()()()()1()11,,1,,11k k ikik k k k kkkk nka l i k n l a l +⎛⎫ ⎪ ⎪⎪-==+ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭。

因此，整个Gauss 消元法相当于左乘了一个单位下三角阵。

21()1()()111111k k kk n n nknn l L l l l l +-⎛⎫ ⎪ ⎪ ⎪=⎪ ⎪ ⎪ ⎪ ⎪⎝⎭所以有 LA U =，L 为单位下三角阵，U 为上三角阵。

⇒1 A L U -=因此Ly bAx b LUx b Ux y=⎧=⇒=⇒⎨=⎩我们可以通过2次反代过程求解方程组，分解的理论由Gauss 消元得出，因此分解能够进行的条件与Gauss 消元一样。

1. Doolittle 分解L 为下三角，U 为单位上三角111211112121222212221212111n n n n n n nn n n nn a a a u u u a a a l u u a a a l l u ⎛⎫⎛⎫⎛⎫⎪⎪⎪ ⎪ ⎪⎪= ⎪ ⎪⎪⎪⎪⎪⎝⎭⎝⎭⎝⎭比较第1行：1111 1,, j j j j a u j n u a ==⇒=比较第1列：11111111u 2,, i i i i a a l i n l u ==⇒=比较第2行：2211221211 2,, j j j j j j a l u u j n u a l u =+=⇒=-比较第2列：21122112222222u u u 3,, i i i i i i a l a l l i n l u -=+=⇒=111211112121222212221212111n n n n n n nn n n nn a a a u u u a a a l u u a a a l l u ⎛⎫⎛⎫⎛⎫⎪⎪⎪ ⎪ ⎪⎪= ⎪ ⎪⎪⎪⎪⎪⎝⎭⎝⎭⎝⎭比较第k 行：1111,, k k kj kr rj kj kj kj kr rj r r a l u u j k n u a l u --===+=⇒=-∑∑比较第k 列：11111,, k ik ir rkk r ik ir rk ik kk ik r kka l u a l u l u i k n l u --==-=+=+⇒=∑∑分解过程完毕，加上两次反代过程：111, 1,, , ,,1i i i ij j j n i ij jj i i iiy b l y i ny u x x i n u -==+=-=-==∑∑这里我们举个例子说明一下快速求解简单方程组的方法：213213213151151121222222243150121--⎛⎫⎛⎫-⎛⎫ ⎪⎪⎪ ⎪ ⎪→-→- ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭⎝⎭⎝⎭10021315110,022********L U ⎛⎫ ⎪-⎛⎫⎪ ⎪⎪ ⎪==- ⎪ ⎪ ⎪ ⎪⎝⎭ ⎪⎝⎭然后通过Ux y =，得x 的解。

2. Courant 分解L 为下三角，U 为单位上三角111211112121222212221212111n n n n n n nn n n nn a a a l u u a a a l l u a a a l l l ⎛⎫⎛⎫⎛⎫⎪⎪⎪ ⎪ ⎪⎪= ⎪ ⎪⎪⎪⎪⎪⎝⎭⎝⎭⎝⎭ 比较第k 列：1111,, k k ik ir rk ik ik ik ir rk r r a l u l i k n l a l u --===+=⇒=-∑∑比较第k 行：11111,, k kj kr rjk r kj kr rj kk kj kj r kka l u a l u l u j k n u l --==-=+=+⇒=∑∑两次反代过程：111, 1,, , ,,1i i ij jj i iini i ijjj i b l y y i n l x y u x i n -==+-===-=∑∑这里我们也举个例子说明上述快速求解简单方程组的方法：11121112112112 1.50.511011********* 1.5 2.5--⎛⎫⎛⎫ ⎪ ⎪--- ⎪ ⎪→ ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭ 1001112120001 1.50.5,1220001011 1.5 2.50001L U -⎛⎫⎛⎫ ⎪ ⎪--⎪⎪== ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭ 下面，我们对一下特殊的矩阵，提出一些特定的分解法3. 三对角阵的追赶法1111222211111n n nn n n a b c a b c a αβγαβγα--⎛⎫⎛⎫⎛⎫⎪ ⎪⎪ ⎪ ⎪⎪= ⎪⎪⎪⎪ ⎪⎪⎝⎭⎝⎭⎝⎭ 11 , 2,, , 1,, , 0 , 1,,i i i i i i i i i c i n a c i n c bi nγαββα-⎧==⎪⎪=-==⎨⎪==⎪⎩11() , 1,, , ,,1 (0)i i i ii i i i i n f c y y i nx y x i n αββ-+-⎧==⎪⎨⎪=-==⎩ 所以，有计算过程如下：11 1,,()i i i i i i ii i i i i a c bi n f c y y αββαα--⎧⎪=-⎪⎪==⎨⎪-⎪=⎪⎩4. 平方根法（对称正定阵的LDLT 分解）若A 对称正定，则有下三角整L ，使得1112111112112122221222221212Tn n n n n n nn n n nn nn A LL a a a l l l l a a a l l l l a a a l l l l =⎛⎫⎛⎫⎛⎫⎪⎪⎪ ⎪ ⎪⎪= ⎪ ⎪⎪⎪⎪⎪⎝⎭⎝⎭⎝⎭所以有：1122111()(),1,,k kk kkkr r k ik ik kr r ik kk l a l a l l l i k nl -=-=⎧=-∑⎪⎪⎨-∑⎪==+⎪⎩又11112122212212121'1''1n n nn n n nn l l l l l l l l l l l l ⎛⎫⎛⎫⎛⎫⎪⎪⎪ ⎪ ⎪⎪= ⎪ ⎪⎪⎪⎪⎪⎝⎭⎝⎭⎝⎭则有T T T A LDD L LDL == 12121211 1n n n d l d L D l l d ⎛⎫⎛⎫⎪⎪ ⎪ ⎪== ⎪ ⎪⎪ ⎪⎝⎭⎝⎭1112111211121222212221212111n n n n n n nn n n n a a a d d l d l a a a l d d l a a a l l d ⎛⎫⎛⎫⎛⎫⎪⎪⎪ ⎪ ⎪⎪= ⎪ ⎪⎪⎪⎪⎪⎝⎭⎝⎭⎝⎭比较等号两边后，有12111(),1,,k k kk kr r r k ik ik kr r r ik k d a l d a l l d l i k nd -=-=⎧=-∑⎪⎪⎨-∑⎪==+⎪⎩为了提高数值稳定性, 可考虑列主元三角分解法, 设已完成A=LU 的k-1步分解计算, 矩阵分解成1112112122221112111212kn k n k k k k k n k k kk kn n n nknn u u u u u u u u u a a a a ----⎛⎫⎪ ⎪⎪⎪ ⎪ ⎪⎪ ⎪ ⎪⎝⎭l l l l l l l 设1111max()k k ik ij jk tk tj jk k t nj j a u a u --≤≤==-=-∑∑l l相当于取11k kk ik ij jk j u a u -==-∑l 为第k 步分解的主元素.但要注意方程组的常数项也要相应变换.第4章 解线性方程组的迭代法直接法得到的解是理论上准确的，但是我们可以看得出，它们的计算量都是3n 数量级，存储量为2n 量级，这在n 比较小的时候还比较合适（n<400），但是对L D于现在的很多实际问题，往往要我们求解很大的n 的矩阵，而且这些矩阵往往是系数矩阵就是这些矩阵含有大量的0元素。