数值计算
高斯消去法和高斯-塞德尔迭代法
摘要
虽然已学过加减消元法、代入消元法、矩阵变换法和Cramer 法则等，但是无法满足实际计算需要，故在此讨论在计算机上实现的有效而实用的解法。线性方程组的解法大致分2类：直接法（高斯消去法）和迭代法（高斯-赛德尔迭代法），在此对着此类算法进行比较分析。
一、算法设计
当计算线性方程组如下时，
⎧a 11x 1+a 12x 2+ +a 1n x n =b 1
⎪a x +a x + +a x =b ⎪2112222n n 2
⎨
⎪
⎪⎩a n 1x 1+a n 2x 2+ +a nn x n =b n
为方便起见，常将线性方程组表示成矩阵形式
Ax =b
(1-1)
⎡b 1⎤⎥ b =⎢ ⎢⎥⎢⎣b n ⎥⎦
其中
⎡a 11 a 1n ⎤
⎢⎥A =⎢ ⎥ ⎢a n 1 a nn ⎥⎣⎦
⎡x 1⎤
⎥ x =⎢ ⎢⎥⎢⎣x n ⎥⎦
并始终假定A 是非奇异的，即方程组的解存在且唯一。
1.1高斯消去法
消去法就是按特定顺序进行的矩阵初等变换法，当消元按自然顺序进行时，称为
高斯顺序消去法。一般情况下的高斯顺序消去法的计算机算法如下，现将方程组（1-1）的增广矩阵记作
(0)⎡a 11 a 1(0)n ⎢
⎢
(0)(0)⎢a n a nn 1⎢⎣
假设经k-1步消元后，增广矩阵化为
(0)⎡a 11⎢⎢⎢⎢⎢⎢⎢⎢⎣
(0)
a 12(1)a 22
⎤a 1(0)n +1⎥ ⎥
(0)⎥a nn +1⎥⎦
a 1(0)n
(1)a 2n
(k -1) (k -1)
a kk a kn
(k -1) (k -1) a nk a nn
⎤a 1(0)n +1
(1)⎥a 2n +1⎥ ⎥
(k -1) ⎥a kn +1⎥ ⎥⎥(k -1)
a nn +1⎦⎥
(s )
其中a ij 的上标表示是由s 步消元得到的植。
(k -1) (k -1)
≠0，以第k 行为基础，将以后各行中的a ik 第k 步消元：设a kk 化为0，为此
先计算
(k -1) (k -1)
l ik =a ik /a kk
然后以第i 行减去第k 行乘以l ik ，即以
(k ) (k -1) (k -1)
a ij =a ij -l ik a kj
(j =k +1, , n +1)
(i =k +1, , n )
a 1(0)n
⎤a 1(0)n +1
⎥ ⎥(k -1) ⎥a kn +1
⎥ (k )
a k +1n +1⎥ ⎥⎥(k )
a nn +1⎥⎦
于是得
(0)
⎡a 11 ⎢
⎢
(k -1) ⎢a kk
⎢⎢⎢⎢⎢⎣
(k -1)
a kk +1
(k -1)
a kn
(k ) (k ) a k a k +1k +1+1n
(k ) a k +1n
(k )
a nn
经n-1步消元后，增广矩阵化为
(0)⎡a 11 a 1(0)n ⎢
⎢
(k -1) (k -1) ⎢a kk a kn
⎢
⎢
(n -1) ⎢a nn ⎣
自下往上逐步回代即可求得其解
(n -1) (n -1)
x n =a nn /a +1nn
n
⎤a 1(0)n +1
⎥ ⎥(k -1) ⎥ a kn +1
⎥ ⎥(n -1) ⎥a nn +1⎦
x k =(a
(k -1)
kn +1
-
j =k +1
∑a
(k -1) kj (k -1)
x j ) /a kk
(k =n -1, n -2, ,1)
由行列式的初等变换和矩阵初等变换的关系可知，顺序消元法的每一步系数行列
(0)(2)(n -1)
a 22 a nn 式之值不变，因此原方程组之系数行列式的值为a 11，可在求解过程中
逐步累乘求得。
1.2高斯消去法Matlab 程序设计
1.3高斯-塞德尔（Gauss-Seidel ）迭代法
由于迭代法能充分避免系数矩阵中零元素的贮存与计算，因此特别适用于系数矩阵阶数很高而非零元极少的线性方程组。 高斯-塞德尔的迭代格式为
1⎧(k +1)
x =(⎪1
a 11
⎪
1⎪(k +1)
=(-a 21x 1(k +1) ⎪x 2
a 22⎨
⎪ ⎪
1⎪(k +1) (k +1)
x =(-a x n 11⎪n
a nn ⎩
或缩写为
x
(k +1) i
(k )
-a 12x 2(k )
-a 13x 3
- -
-
(k )
-a 1n x n
+b 1) +b 2) +b n )
(k )
-a 23x 3(k )
-a 2n x n
(k +1)
-a n 2x 2
(k +1)
-a n 3x 3
(k +1)
- -a nn -1x n -1
i -1n
1(k +1) =(-∑a ij x j -∑a ij x (j k ) +b i ) a 11j =1 j =i +1
(i =1, 2, , n )
将其写成矩阵形式为
x (k +1) =D -1[Lx (k +1) +Ux (k ) ]+D -1b
若把x (k +1) 解出来，则得等价的迭代公式
x (k +1) =(D -L ) -1Ux (k ) +(D -L ) -1b
记
M G =(D -L ) -1U
其中
⎡0⎤⎢-a ⎥0⎥ L =⎢21⎢ ⎥⎢⎥-a -a 0n 2⎣n 1⎦
⎡0-a 12 -a 1n ⎤⎢⎥0 -a 2n ⎥U =⎢ ⎢ ⎥⎢⎥
0⎣⎦⎡a 11⎤⎥ D =⎢ ⎢⎥
⎢a nn ⎥⎣⎦
M G 为高斯-塞德尔的迭代矩阵。
1.4高斯-塞德尔（Gauss-Seidel ）迭代法Matlab 程序设计
二、数值试验
用高斯消去法和高斯-塞德尔迭代法求解方程组
⎡0.00173.85671.10233.1243⎤⎡x 1⎤⎡8.0904⎤⎢0.12341.23432.30441.6257⎥⎢⎥⎢5.2878⎥⎢⎥⎢x 2⎥=⎢⎥ ⎢9.9274-4.92588.5042-3.4253⎥⎢x 3⎥⎢9.4805⎥⎢⎥⎢⎥⎢⎥7.54339.999510.6728-7.014721.2009x ⎢4⎦⎥⎣⎣⎦⎣⎦
2.1高斯消去法在计算机上求解结果如下
2.2高斯-赛德尔迭代法在计算机上求解结果如下
2.3计算机上求解结果分析
有上述结果可知当用直接法可求出线性方程组的解得时候，迭代法却不一定可行。只有当该迭代收敛时才有解，亦即是矩阵M 的谱半径ρ(M ) =max λi
1≤i ≤n
该迭代才收敛，才可用迭代法求解线性方程组的解。
三、参考文献
【1】曹德欣，曹璎珞，计算方法，中国矿业大学出版社，2001。 【2】王正盛，MATLAB 与科学计算，国防工业出版社，2011。
数值计算
高斯消去法和高斯-塞德尔迭代法
摘要
虽然已学过加减消元法、代入消元法、矩阵变换法和Cramer 法则等，但是无法满足实际计算需要，故在此讨论在计算机上实现的有效而实用的解法。线性方程组的解法大致分2类：直接法（高斯消去法）和迭代法（高斯-赛德尔迭代法），在此对着此类算法进行比较分析。
一、算法设计
当计算线性方程组如下时，
⎧a 11x 1+a 12x 2+ +a 1n x n =b 1
⎪a x +a x + +a x =b ⎪2112222n n 2
⎨
⎪
⎪⎩a n 1x 1+a n 2x 2+ +a nn x n =b n
为方便起见，常将线性方程组表示成矩阵形式
Ax =b
(1-1)
⎡b 1⎤⎥ b =⎢ ⎢⎥⎢⎣b n ⎥⎦
其中
⎡a 11 a 1n ⎤
⎢⎥A =⎢ ⎥ ⎢a n 1 a nn ⎥⎣⎦
⎡x 1⎤
⎥ x =⎢ ⎢⎥⎢⎣x n ⎥⎦
并始终假定A 是非奇异的，即方程组的解存在且唯一。
1.1高斯消去法
消去法就是按特定顺序进行的矩阵初等变换法，当消元按自然顺序进行时，称为
高斯顺序消去法。一般情况下的高斯顺序消去法的计算机算法如下，现将方程组（1-1）的增广矩阵记作
(0)⎡a 11 a 1(0)n ⎢
⎢
(0)(0)⎢a n a nn 1⎢⎣
假设经k-1步消元后，增广矩阵化为
(0)⎡a 11⎢⎢⎢⎢⎢⎢⎢⎢⎣
(0)
a 12(1)a 22
⎤a 1(0)n +1⎥ ⎥
(0)⎥a nn +1⎥⎦
a 1(0)n
(1)a 2n
(k -1) (k -1)
a kk a kn
(k -1) (k -1) a nk a nn
⎤a 1(0)n +1
(1)⎥a 2n +1⎥ ⎥
(k -1) ⎥a kn +1⎥ ⎥⎥(k -1)
a nn +1⎦⎥
(s )
其中a ij 的上标表示是由s 步消元得到的植。
(k -1) (k -1)
≠0，以第k 行为基础，将以后各行中的a ik 第k 步消元：设a kk 化为0，为此
先计算
(k -1) (k -1)
l ik =a ik /a kk
然后以第i 行减去第k 行乘以l ik ，即以
(k ) (k -1) (k -1)
a ij =a ij -l ik a kj
(j =k +1, , n +1)
(i =k +1, , n )
a 1(0)n
⎤a 1(0)n +1
⎥ ⎥(k -1) ⎥a kn +1
⎥ (k )
a k +1n +1⎥ ⎥⎥(k )
a nn +1⎥⎦
于是得
(0)
⎡a 11 ⎢
⎢
(k -1) ⎢a kk
⎢⎢⎢⎢⎢⎣
(k -1)
a kk +1
(k -1)
a kn
(k ) (k ) a k a k +1k +1+1n
(k ) a k +1n
(k )
a nn
经n-1步消元后，增广矩阵化为
(0)⎡a 11 a 1(0)n ⎢
⎢
(k -1) (k -1) ⎢a kk a kn
⎢
⎢
(n -1) ⎢a nn ⎣
自下往上逐步回代即可求得其解
(n -1) (n -1)
x n =a nn /a +1nn
n
⎤a 1(0)n +1
⎥ ⎥(k -1) ⎥ a kn +1
⎥ ⎥(n -1) ⎥a nn +1⎦
x k =(a
(k -1)
kn +1
-
j =k +1
∑a
(k -1) kj (k -1)
x j ) /a kk
(k =n -1, n -2, ,1)
由行列式的初等变换和矩阵初等变换的关系可知，顺序消元法的每一步系数行列
(0)(2)(n -1)
a 22 a nn 式之值不变，因此原方程组之系数行列式的值为a 11，可在求解过程中
逐步累乘求得。
1.2高斯消去法Matlab 程序设计
1.3高斯-塞德尔（Gauss-Seidel ）迭代法
由于迭代法能充分避免系数矩阵中零元素的贮存与计算，因此特别适用于系数矩阵阶数很高而非零元极少的线性方程组。 高斯-塞德尔的迭代格式为
1⎧(k +1)
x =(⎪1
a 11
⎪
1⎪(k +1)
=(-a 21x 1(k +1) ⎪x 2
a 22⎨
⎪ ⎪
1⎪(k +1) (k +1)
x =(-a x n 11⎪n
a nn ⎩
或缩写为
x
(k +1) i
(k )
-a 12x 2(k )
-a 13x 3
- -
-
(k )
-a 1n x n
+b 1) +b 2) +b n )
(k )
-a 23x 3(k )
-a 2n x n
(k +1)
-a n 2x 2
(k +1)
-a n 3x 3
(k +1)
- -a nn -1x n -1
i -1n
1(k +1) =(-∑a ij x j -∑a ij x (j k ) +b i ) a 11j =1 j =i +1
(i =1, 2, , n )
将其写成矩阵形式为
x (k +1) =D -1[Lx (k +1) +Ux (k ) ]+D -1b
若把x (k +1) 解出来，则得等价的迭代公式
x (k +1) =(D -L ) -1Ux (k ) +(D -L ) -1b
记
M G =(D -L ) -1U
其中
⎡0⎤⎢-a ⎥0⎥ L =⎢21⎢ ⎥⎢⎥-a -a 0n 2⎣n 1⎦
⎡0-a 12 -a 1n ⎤⎢⎥0 -a 2n ⎥U =⎢ ⎢ ⎥⎢⎥
0⎣⎦⎡a 11⎤⎥ D =⎢ ⎢⎥
⎢a nn ⎥⎣⎦
M G 为高斯-塞德尔的迭代矩阵。
1.4高斯-塞德尔（Gauss-Seidel ）迭代法Matlab 程序设计
二、数值试验
用高斯消去法和高斯-塞德尔迭代法求解方程组
⎡0.00173.85671.10233.1243⎤⎡x 1⎤⎡8.0904⎤⎢0.12341.23432.30441.6257⎥⎢⎥⎢5.2878⎥⎢⎥⎢x 2⎥=⎢⎥ ⎢9.9274-4.92588.5042-3.4253⎥⎢x 3⎥⎢9.4805⎥⎢⎥⎢⎥⎢⎥7.54339.999510.6728-7.014721.2009x ⎢4⎦⎥⎣⎣⎦⎣⎦
2.1高斯消去法在计算机上求解结果如下
2.2高斯-赛德尔迭代法在计算机上求解结果如下
2.3计算机上求解结果分析
有上述结果可知当用直接法可求出线性方程组的解得时候，迭代法却不一定可行。只有当该迭代收敛时才有解，亦即是矩阵M 的谱半径ρ(M ) =max λi
1≤i ≤n
该迭代才收敛，才可用迭代法求解线性方程组的解。
三、参考文献
【1】曹德欣，曹璎珞，计算方法，中国矿业大学出版社，2001。 【2】王正盛，MATLAB 与科学计算，国防工业出版社，2011。