求线性方程组的解
直接法
高斯顺序消去法
过程
高斯顺序消去法的过程如下：
- 高斯消去过程
对 k = 1 , 2 , . . . , n − 1 k = 1, 2, ..., n-1 k=1,2,...,n−1，如果 A [ k ] [ k ] ≠ 0 A[k][k] \neq 0 A[k][k]=0,
则对 i = k + 1 , k + 2 , . . . , n i = k+1, k+2, ..., n i=k+1,k+2,...,n，计算 l i k = A [ i ] [ k ] A [ k ] [ k ] l_{ik} = \frac{A[i][k]}{A[k][k]} lik=A[k][k]A[i][k]；
之后对 j = k , k + 1 , . . . , n j = k, k+1, ..., n j=k,k+1,...,n，计算 A [ i ] [ j ] = A [ i ] [ j ] − l i k × A [ k ] [ j ] A[i][j] = A[i][j] - l_{ik} \times A[k][j] A[i][j]=A[i][j]−lik×A[k][j]以及 B [ i ] = B [ i ] − B [ k ] × l i k B[i] = B[i] - B[k] \times l_{ik} B[i]=B[i]−B[k]×lik - 回代过程
- 计算 X [ n ] = B [ n ] A [ n ] [ n ] X[n] = \frac{B[n]}{A[n][n]} X[n]=A[n][n]B[n]
- 对 k = n − 1 , . . . , 1 k = n-1,..., 1 k=n−1,...,1，计算 X [ k ] = 1 A [ k ] [ k ] × ( B [ k ] − ∑ j = k + 1 n A [ k ] [ j ] × X [ j ] ) X[k] = \frac{1}{A[k][k]} \times (B[k] - \sum_{j=k+1}^{n}A[k][j] \times X[j]) X[k]=A[k][k]1×(B[k]−∑j=k+1nA[k][j]×X[j])
运算次数
消元过程所需乘除运算次数为
1
3
n
3
+
1
2
n
2
−
5
6
n
\frac{1}{3}n^{3}+\frac{1}{2}n^{2}-\frac{5}{6}n
31n3+21n2−65n
回代过程所需乘除运算次数为
1
2
n
(
n
+
1
)
\frac{1}{2}n(n+1)
21n(n+1)
因此，高斯顺序消元法总的乘除运算次数为
1
3
n
3
+
n
2
−
1
3
n
\frac{1}{3}n^{3}+n^{2}-\frac{1}{3}n
31n3+n2−31n
优缺点
优点：相较于Cramer法则，二者计算次数有天壤之别，其速度比Cramer法则快很多
缺点：高斯顺序消元过程能进行下去的充要条件是系数矩阵
A
A
A的
k
k
k阶顺序主子式
Δ
k
≠
0
(
k
=
1
,
2
,
.
.
.
,
n
−
1
)
\Delta_{k} \neq 0(k=1, 2, ..., n-1)
Δk=0(k=1,2,...,n−1)，即
Δ
k
=
∣
a
11
⋯
a
1
k
⋮
⋮
a
k
1
⋯
a
k
k
∣
≠
0.
\Delta_{k} = \left | \begin{matrix} a_{11} & \cdots & a_{1k}\\ \vdots & & \vdots\\ a_{k1} & \cdots & a_{kk} \end{matrix} \right | \neq 0.
Δk=∣∣∣∣∣∣∣a11⋮ak1⋯⋯a1k⋮akk∣∣∣∣∣∣∣=0.
但是，当
∣
a
k
k
(
k
)
∣
≈
0
\left | a_{kk}^{(k)} \right | \approx 0
∣∣∣akk(k)∣∣∣≈0或
∣
a
k
k
(
k
)
∣
\left | a_{kk}^{(k)} \right |
∣∣∣akk(k)∣∣∣相对于
∣
a
i
k
(
k
)
∣
(
i
=
k
+
1
,
k
+
2
,
⋯
,
n
)
\left | a_{ik}^{(k)} \right |(i = k+1, k+2,\cdots, n)
∣∣∣aik(k)∣∣∣(i=k+1,k+2,⋯,n)比较小时，消元过程在计算机计算时产生的舍入误差将可能导致计算结果误差较大（
a
k
k
(
k
)
a_{kk}^{(k)}
akk(k)是第k次消元前，系数矩阵
A
A
A第
k
k
k行
k
k
k列的元素，
a
i
k
(
k
)
a_{ik}^{(k)}
aik(k)同理）。
代码实现
// 求AX = B的解
// A ---- n × n矩阵
// 消元过程
for (int k = 0; k < n - 1; k++)
{
if (A[k][k])
{
for (int i = k + 1; i < n; i++)
{
double lik = A[i][k] / A[k][k];
for (int j = k; j < n; j++)
{
A[i][j] = A[i][j] - lik * A[k][j];
}
B[i] = B[i] - lik * B[k];
}
}
}
// 回代过程
X[n - 1] = B[n - 1] / A[n - 1][n - 1];
for (int k = n - 2; k >= 0; k--)
{
double sum = 0.0;
for (int j = k + 1; j < n; j++)
{
sum += A[k][j] * X[j];
}
X[k] = (B[k] - sum) / A[k][k];
}