線性方程組

<image>

線性方程組是數學方程組的一種，它符合以下的形式：

$$\begin{cases}a_{1,1}x_{1} + a_{1,2}x_{2} + \cdots + a_{1,n}x_{n}= b_{1} \\ <pre> a_{2,1}x_{1} + a_{2,2}x_{2} + \cdots + a_{2,n}x_{n}= b_{2} \\ \vdots \quad \quad \quad \vdots \\ a_{m,1}x_{1} + a_{m,2}x_{2} + \cdots + a_{m,n}x_{n}= b_{m} \end{cases}$$

其中的 $a_{1,1}, \, a_{1,2}$ 以及 $b_{1}, \, b_{2}$ 等等是已知的常數，而 $x_{1}, \, x_{2}$ 等等則是要求的未知數。

如果用線性代數中的概念來表達，則線性方程組可以寫成：

$$\mathbf{A} \mathbf{x} = \mathbf{b}$$

這裡的 $\mathbf A$ 是 $m\times n$ 矩陣，$\mathbf x$ 是含有 $n$ 個元素列向量，$\mathbf b$ 是含有 $m$ 個元素列向量。

$$\mathbf A= \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{bmatrix},\quad \mathbf{x}= \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix},\quad \mathbf{b}= \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix}$$

這是線性方程組的另一種記錄方法。在已知矩陣 $\mathbf A$ 和向量 $\mathbf{b}$ 的情況求得未知向量 $\mathbf{x}$ 是線性代數的基本問題之一。

## 例子

以下是一個由兩個方程構成的線性方程組：

$$\begin{cases}3x_{1} + 5x_{2} = 4 \\ <pre> x_{1} + 2x_{2} = 1 \end{cases}$$

方程組中有兩個未知數。以矩陣表示，這個方程組可以記錄為：

$$\begin{bmatrix} 3 & 5\\ 1 & 2 \end{bmatrix} \cdot \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 4 \\ 1 \end{bmatrix}$$

這個線性方程組有一組解：$x_1 = 3, \, x_2 = -1$。可以直接驗證：

$$\begin{cases}3 \times 3 + 5 \times (-1) = 9 - 5 = 4 \\ <pre> 3 + 2 \times (-1) = 3 -2 = 1 \end{cases}$$

可以證明，這組解也是方程組唯一的解。

不是所有的線性方程組都有解。以下是一個沒有解的例子：

$$\begin{cases}x_{1} + x_{2} = 2\\ <pre> 2x_{1} + 2x_{2} = 1 \end{cases}$$

顯然，如果有 $x_1$ 和 $x_2$ 滿足了第一行的式子的話，它們的和等於 2。而第二行則要求它們的和等於 0.5，這不可能。

也有的線性方程組有不止一組解。例如：

$$\begin{cases}x_{1} + x_{2} = 2 <pre> \end{cases}$$

$x_1 = 1, \, x_2 = 1$ 是一組解，而 $x_1 = 3, \, x_2 = -1$ 也是一組解。事實上，解的個數有無限個。

## 線性方程組的解

<image>

如果有一組數 $x_1, x_2, \cdots, x_n$ 使得方程組的等號都成立，那麼這組數就叫做方程組的解。一個線性方程組的所有的解的集合會被簡稱為解集。根據解的存在情況，線性方程組可以分為三類：

- 有唯一解的恰定方程組。
- 解不存在的超定方程組。
- 有無窮多解的欠定方程組（也被通俗地稱為不定方程組）。

### 幾何解釋

當未知數只有兩個（x和y）的時候，方程組裡面的每一個方程可以看成 Oxy平面（正交直角坐標系）上的一條直線的方程。直線上的點的坐標就是滿足這個方程的一組數。從這個角度看來，方程組的解就是所有這種直線的公共點。而若干條直線的公共部分要麼是一條直線，要麼是一個點，要麼是空集，因此對應的，線性方程組的解要麼有無窮個，要麼恰好有一個，要麼不存在。

如果未知數有三個，那麼每一個方程則代表了三維空間裡面的一個平面，而方程組的解集也就是一些平面的共同部分。所有解的集合可以對應一個平面，一條直線，一個點或空集。

這個問題的一般情況可以從線性空間的角度去分析，即我們可以將線性方程組的求解問題看成向量 $\mathbf{b}$ 在矩陣 $\mathbf A$ 所張成的線性空間裡面的投影的問題。未知數的個數如果是一般的n個的話，可以想像每個方程代表了n維空間裡面的一個超平面。而方程組的解就是所有超平面的公共點。

### 齊次線性方程組

齊次的線性方程組是指向量 $\mathbf{b}=\mathbf 0$ 的情況。這時候方程變成：

$\mathbf A \mathbf{x}=\mathbf 0$ 這個方程肯定會有一組解：$\mathbf{x}=\mathbf 0$。實際上，方程的解就是矩陣$\mathbf A$對應的線性變換的零空間。一般來說，當方程的個數小於未知數的個數時，方程組會有除 $\mathbf{x}=\mathbf 0$ 以外的解。當方程組個數變多時，則要看其中「有效」的方程的個數。有時候某一個方程可以表示成另外幾個方程的線性組合。比如方程組：

$\begin{cases}3x_{1} + x_{2} + 2 x_{3} = 0 \\ <pre> x_{1} - x_{2} + 4 x_{3} = 0\\ 2x_{1} + 3x_{3} = 0 \end{cases}$

之中，第三個方程就可以表示為前兩個方程的線性組合：

$2x_{1} + 3x_{3} = \frac{1}{2}(3x_{1} + x_{2} + 2 x_{3}) + \frac{1}{2}(x_{1} - x_{2} + 4 x_{3})$ 這時第三個方程組就可以不必考慮了。用線性代數的詞彙表達，「有效」的方程的個數就是矩陣 $\mathbf A$ 中線性無關的行向量的個數，或者說行向量線性張成的空間的維數。這個數也被稱為矩陣的秩。當矩陣 $\mathbf A$ 的秩 $r$ 小於未知數的個數$n$時，方程組的解會有無窮多個，構成一個 $n-r$ 維的線性空間。而當 $r$ 等於未知數的個數 $n$ 時，方程組有唯一零解，$r$ 不可能大於 $n$。

### 鬆弛求解

在實驗數據處理和曲線擬合問題中，求解超定方程組非常普遍。這時常常需要退一步，將線性方程組的求解問題改變為求最小誤差的問題。形象的說，就是在無法完全滿足給定的這些條件的情況下，求一個最接近的解。比較常用的方法是最小二乘法。最小二乘法求解超定問題等價於一個優化問題，或者說最小值問題，即，在不存在$\mathbf{x}$使得$\mathbf{b} -\mathbf A \mathbf{x} = \mathbf 0$的情況下，我們試圖找到這樣的$\mathbf{x}$使得$\left| \mathbf{b} - \mathbf A \mathbf{x} \right|$最小，其中$\left| \cdot \right|$表示範數。

## 求解

### 克萊姆法則

基於線性方程組的解空間理論，線性方程組有唯一解若且唯若有效方程數等於未知數的個數。這時，可以運用各種方法具體求出唯一存在的解。克萊姆法則是一種求解線性方程組的方法，大多數線性代數教材都會提到。例如對於如下的線性方程組：

$\begin{cases}a_1 x + b_1 y = c_1 \\ a_2 x + b_2 y = c_2 \end{cases}$

運用克萊姆法則，這個方程組的解可以如下：

$x = \frac{D_x}{D}, \qquad y = \frac{D_y}{D}$

其中，$D_x, D_y, D$分別是如下三個行列式：

$D = \left| \begin{matrix} a_1 & b_1 \\ a_2 & b_2 \end{matrix} \right| ,$ $D_x = \left| \begin{matrix} c_1 & b_1 \\ c_2 & b_2 \end{matrix} \right| ,$ $D_y = \left| \begin{matrix} a_1 & c_1 \\ a_2 & c_2 \end{matrix} \right|$

對於更一般的情況：

$$\mathbf{A} \mathbf{x} = \mathbf{b}$$

解可以由同樣的公式給出：

$\begin{cases}x_1 = \frac{D_1}{D} \\ <pre> x_2 = \frac{D_2}{D} \\ \vdots \qquad \vdots \\ x_n = \frac{D_n}{D}\end{cases}$

其中的

$$D = \det (\mathbf A)$$

$$\forall 1 \leqslant i \leqslant n, \, \, D_i = \det (\mathbf{A_i})$$

$\mathbf{A_i}$是將矩陣$\mathbf A$的第i縱列換成向量b之後得到的矩陣。

可以看出，這些表達式只有在$D = \det (\mathbf A)$存在並且不等於0的時候才是有意義的，這點只有在有效方程數等於未知數的個數的時候才能得到保證。

### 數值方法

在實際運算中，當矩陣的維數較高時，計算行列式是非常繁複的。也就是說，計算行列式的計算複雜度隨維數的增長非常快，對於一個$n \times n$的矩陣，用初等的方法計算其行列式，需要的計算時間是$O(n!)$（n的階乘）。因此，克萊姆法則在現實問題求解幾乎不會被採用，而其重要性在於證明某些線性問題的解答會自然而然是整數解答，因而存在有效率的解法。換言之，克萊姆法則的重要性是在於理論證明的應用，而非問題的實際求解。

經典的求解線性方程組的方法一般分為兩類：直接法和迭代法。前者例如高斯消去法, LU分解等，後者的例子包括共軛梯度法等。這些方法的計算複雜度在可以接受的範圍內，因此被廣泛採用。例如，高斯消去法的複雜度為$O(n^3)$ 一般來說，直接法對於階數比較低的方程組（少於20000至30000個未知數）比較有效；而後者對於比較大的方程組更有效。在實際計算中，幾十萬甚至幾百萬個未知數的方程組並不少見。在這些情況下，迭代法有無可比擬的優勢。另外，使用迭代法可以根據不同的精度要求選擇終止時間，因此比較靈活。在問題特別大的時候，電腦記憶體可能無法容納被操作的矩陣，這給直接法帶來很大的挑戰。而對於迭代法，則可以將矩陣的某一部分讀入記憶體進行操作，然後再操作另外部分。

## 應用

現實中的問題大多數是連續的，例如工程中求解結構受力後的變形，空氣動力學中計算機翼周圍的流場，氣象預報中計算大氣的流動。這些現象大多是用若干個微分方程描述。用數值方法求解微分方程（組），不論是差分方法還是有限元方法，通常都是通過對微分方程（連續的問題，未知數的維數是無限的）進行離散，得到線性方程組（離散問題，因為未知數的維數是有限的）。因此線性方程組的求解在科學與工程中的應用非常廣泛。

許多具體的應用會得到結構比較特別的線性方程組，比如用差分方法和有限元方法離散微分方程後通常會得到三對角或五對角的方程組，網路問題有時會得到對稱的線性方程組（$\mathbf A = \mathbf A^T$），因此除了通用的線性方程組求解器，在一些專業領域，研究人員們也開發了適用於特定問題的求解器，比如適用於稀疏矩陣的求解器，適用於三對角矩陣的求解器，適用於對稱矩陣的求解器等。

## 相關軟體

由於線性方程組的求解是一個非常普遍的問題，在多年的科學與工程實踐中，科學家和工程師們積累很多高效率的線性方程組求解器，例如：LAPACK、BLAS等。這些軟體中，許多可以可以在 NetLib 免費獲得。LAPACK和BLAS在大多數Linux的發行版本中都已經預裝。目前LAPACK有Fortran（包括90和77版本）、C、C++等幾個語言的版本。利用LAPACK和BLAS中的子程序， Matlab 對這些線性方程組求解器進行封裝。使用者不需要選擇求解器的類型和問題的類型，Matlab可以根據對矩陣的分析自動選擇合適的求解器。

## 其他方法與軟體

上面講的是線性方程組的數值解法。對於比較小的線性方程組，求得符號解是可能的。常用的軟體有Mathematica, Maple等。在某些領域的研究中，這種需要並且可能求符號解（精確解）的情況偶爾會遇到。未知數的個數一般限制在幾十個左右。顯然，符號解在對於實際中遇到的有幾百萬個未知數的問題是無能為力的，比如，大型結構，天氣預報，湍流模擬等問題中得到的線性方程組。

## 外部連結

- Mathway，使用電腦解決絕大部分的數學問題。
- Simultaneous Linear Equations Calculator，一個簡單的線性方程組求解器