數值方法導論/線性方程組

目標

• 定義向量和矩陣
• 加、減、乘矩陣
• 求方陣的轉置
• 定義矩陣的逆
• 將聯立線性方程組設定為矩陣形式

資源

• 書本章節
• Python程式設計

向量和矩陣

一個矩陣 是一個矩形的陣列，例如數字、符號或表示式。矩陣通常用來表示線性變換 和線性方程組。

一個三角矩陣 是一種特殊的方陣。如果 A 中主對角線以下的所有元素都為零，則 A 稱為上三角矩陣。

$a_{ij}=0$ 對所有 $i>j$

類似地，如果 A 中主對角線以上的所有元素都為零，則 A 稱為下三角矩陣。

$a_{ij}=0$ 對所有 $i<j$

如果主對角線以外的所有元素都為零，則 A 稱為對角矩陣。

$a_{ij}=0$ 對所有 $i\neq j$

這個矩陣

${\begin{bmatrix}1&4&2\\0&3&4\\0&0&1\\\end{bmatrix}}$

是上三角，這個矩陣

${\begin{bmatrix}1&0&0\\2&8&0\\4&9&7\\\end{bmatrix}}$

是下三角。

大小為 n 的單位矩陣 是一個 n×n 矩陣，其中主對角線上的所有元素都等於 1，其他所有元素都等於 0。

矩陣乘法

矩陣乘法 接受兩個矩陣並生成另一個矩陣。該操作的規則如下所示

${\overset {4\times 2{\text{ matrix}}}{\begin{bmatrix}{\color {Brown}{a_{11}}}&{\color {Brown}{a_{12}}}\\\cdot &\cdot \\{\color {Orange}{a_{31}}}&{\color {Orange}{a_{32}}}\\\cdot &\cdot \\\end{bmatrix}}}{\overset {2\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &{\color {Plum}{b_{12}}}&{\color {Violet}{b_{13}}}\\\cdot &{\color {Plum}{b_{22}}}&{\color {Violet}{b_{23}}}\\\end{bmatrix}}}={\overset {4\times 3{\text{ matrix}}}{\begin{bmatrix}\cdot &x_{12}&x_{13}\\\cdot &\cdot &\cdot \\\cdot &x_{32}&x_{33}\\\cdot &\cdot &\cdot \\\end{bmatrix}}}$

用圓圈標記的交點處的值為

${\begin{aligned}x_{12}&={\color {Brown}{a_{11}}}{\color {Plum}{b_{12}}}+{\color {Brown}{a_{12}}}{\color {Plum}{b_{22}}}\\x_{13}&={\color {Brown}{a_{11}}}{\color {Violet}{b_{13}}}+{\color {Brown}{a_{12}}}{\color {Violet}{b_{23}}}\\x_{32}&={\color {Orange}{a_{31}}}{\color {Plum}{b_{12}}}+{\color {Orange}{a_{32}}}{\color {Plum}{b_{22}}}\\x_{33}&={\color {Orange}{a_{31}}}{\color {Violet}{b_{13}}}+{\color {Orange}{a_{32}}}{\color {Violet}{b_{23}}}\end{aligned}}$

矩陣的轉置

矩陣的轉置定義如下：矩陣A的轉置是另一個矩陣A^T，可以透過以下任何一種等效操作建立

• 沿其主對角線（從左上角到右下角）反射A以獲得A^T
• 將A的行寫為A^T的列
• 將A的列寫為A^T的行

下圖說明了這個概念

矩陣的逆

如果存在一個n×n方陣B，使得

$\mathbf {AB} =\mathbf {BA} =\mathbf {I} _{n}\$

其中I_n表示n×n單位矩陣，使用的乘法是普通的矩陣乘法。B被稱為A的逆，記為A⁻¹。

將線性方程組表示為矩陣形式

${\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (L_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (L_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (L_{3})\end{alignedat}}$

我們可以將這個線性方程組表示成矩陣形式，如下所示

${\begin{bmatrix}2x&+&y&-&z\\-3x&-&y&+&2z\\-2x&+&y&+&2z\end{bmatrix}}={\begin{bmatrix}8\\-11\\-3\end{bmatrix}}$

然後我們可以使用矩陣乘法來分離變數。

${\begin{bmatrix}2&1&-1\\-3&-1&2\\-2&1&2\end{bmatrix}}{\begin{bmatrix}x\\y\\z\end{bmatrix}}={\begin{bmatrix}8\\-11\\-3\end{bmatrix}}$

${\begin{bmatrix}25&5&1\\64&8&1\\144&12&1\end{bmatrix}}{\begin{bmatrix}a_{1}\\a_{2}\\a_{3}\end{bmatrix}}={\begin{bmatrix}106.8\\177.2\\279.2\end{bmatrix}}$

線性方程組的一般矩陣形式如下所示

$A_{n\times n}X_{n\times 1}=C_{n\times 1}$

矩陣A是係數矩陣。X是解向量（矩陣），C是右側向量。如果我們在兩邊乘以A的逆矩陣，我們可以看到解與A的逆矩陣密切相關。

${\begin{alignedat}{3}A^{-1}AX&&\;=\;&&A^{-1}C\\IX&&\;=\;&&A^{-1}C\\X&&\;=\;&&A^{-1}C\end{alignedat}}$

高斯消元法

來源

• 書本章節

高斯消元法 是一個用來求解線性方程組的演算法，類似於求一個可逆方陣的逆矩陣。該演算法包含一系列對係數矩陣進行的行變換操作。共有三種基本行變換：

• 交換兩行
• 將一行乘以一個非零常數
• 將一行乘以一個常數加到另一行上。

例如，第一個線性方程 (L₁，主元方程) 可以用來消去 $x$ 從接下來的兩個方程中：

${\begin{alignedat}{7}2x&&\;+\;&&y&&\;-\;&&z&&\;=\;&&8&\qquad (L_{1})\\-3x&&\;-\;&&y&&\;+\;&&2z&&\;=\;&&-11&\qquad (L_{2})\\-2x&&\;+\;&&y&&\;+\;&&2z&&\;=\;&&-3&\qquad (L_{3})\end{alignedat}}$

然後 L₂ (主元方程) 可以用來消去 $y$ 從 L₃ 中。這個過程被稱為**前向消元**。現在 L₃ 中只有一個未知量 $z$，可以用來將 $z$ 代入 L₂ 中求解 $y$。這個過程被稱為**後向代入**。

高斯消元法的演算法可以這樣實現：

''' 
x = gauss_elimin(a, b)
Solves [a][x] = [b] by Gauss elimination.
'''
from numpy import dot, array

def gauss_elimin(a, b):
  (rows, cols) = a.shape
  # elimination phase
  for row in range(0, rows-1): # pivot equation/row
    for i in range(row+1, rows):
      if a[i, row] != 0.0:
        factor = a[i, row]/a[row, row]
        a[i, row+1:rows] = a[i, row+1:rows] - factor*a[row, row+1:rows]
        b[i] = b[i] - factor*b[row]
  # back substitution 
  for k in range(rows-1,-1,-1):
    b[k] = (b[k] - dot(a[k, k+1:rows],b[k+1:rows]))/a[k, k]
  return b

a = array([[3, 2.0], [-6, 6]])
b = array([7, 6])
print gauss_elimin(a, b)

帶部分主元選擇的高斯消元法

高斯消元法容易受到舍入誤差的影響，特別是當方程數量很大時，誤差會累積。另一個問題是除零錯誤。例如，以下矩陣會導致該方法失效，因為第二個主元元素為零，而該方法要求主元元素非零。

$\left[{\begin{array}{ccc|c}1&-1&2&8\\0&0&-1&-11\\0&2&-1&-3\end{array}}\right]$

帶部分主元選擇的高斯消元法類似於高斯消元法，只是在 $i$ 次前向消元步驟中，找出 $|a_{i,i}|,|a_{i+1,i}|,...,|a_{n,i}|$ 的最大值，並將包含最大值的所在行與主元行進行交換。交換後，之前的係數矩陣如下所示。

$\left[{\begin{array}{ccc|c}1&-1&2&8\\0&2&-1&-3\\0&0&-1&-11\end{array}}\right]$

高斯-賽德爾法

高斯消元法是一種直接（直接）方法，它將原始方程轉化為等價的更容易求解的方程。一些方程組沒有解，例如，方程數量少於未知量，或者一個方程與另一個方程矛盾。

高斯-賽德爾法 是一種迭代（或間接）方法，它從對解的猜測開始，並反覆改進猜測，直到它收斂（收斂條件得到滿足）。這種方法的優點是，當係數矩陣很大且稀疏時，它在計算上更有效率，並且可以透過調整誤差容限來控制舍入誤差。

該演算法包含以下步驟：

1. 將每個方程改寫為對應未知量的形式，例如，將第一個方程寫成 $x_{1}$ 在左側，將第二個方程寫成 $x_{2}$ 在左側

$x_{i}={\frac {c_{i}-\sum _{j=1,j\neq i}^{n}a_{ij}x_{j}}{a_{ii}}},i=1,2,3,...,n.$

1. 找到 $x_{i}$ 的初始猜測。
2. 使用重寫的方程計算新的估計值 - 始終使用最新的估計值。
3. 重複上一步，直到所有 $x_{i}$ 中最大的絕對相對近似誤差小於指定的容差。

大多數迭代方法的缺點是，當方程組的係數矩陣不是 對角佔優 時，它可能不會收斂。係數矩陣對角佔優的方程組總是收斂的。矩陣 A 對角佔優，如果

$|a_{ii}|\geq \sum _{j\neq i}|a_{ij}|\quad {\text{for all }}i,$

以及

$|a_{ii}|>\sum _{j\neq i}|a_{ij}|\quad {\text{for at least one }}i.$

一個 使用 numpy 的 Python 實現 只需迭代即可生成解向量。

LU 分解

LU 分解 將係數矩陣 A 分解為下三角矩陣和上三角矩陣的乘積：A = LU。從 A 中匯出 L 和 U 的過程稱為 LU 分解或 LU 分解，類似於 高斯消元法。

完成 LU 分解後，我們可以使用前向和後向替換來求解由 A 表示的線性方程組。

${\begin{alignedat}{3}AX&&\;=\;&&C\\LUX&&\;=\;&&C\\L^{-1}LUX&&\;=\;&&L^{-1}C\\UX&&\;=\;&&L^{-1}C\\\end{alignedat}}$

令 $L^{-1}C=Z$，這意味著 $LZ=C$ 和 $Z$ 可以透過前向消元法求解。從 $UX=Z$ 中，我們可以使用後向消元法求解 X。

LU 分解的一種方法類似於高斯消元法。對於一個 $3\times 3$

$A={\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\\\end{bmatrix}}={\begin{bmatrix}1&0&0\\l_{21}&1&0\\l_{31}&l_{32}&1\\\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}&u_{13}\\0&u_{22}&u_{23}\\0&0&u_{33}\\\end{bmatrix}}.$

$A={\begin{bmatrix}u_{11}&u_{12}&u_{13}\\u_{11}l_{21}&u_{12}l_{21}+u_{22}&u_{13}l_{21}+u_{23}\\u_{11}l_{31}&u_{12}l_{31}+u_{22}l_{32}&u_{13}l_{31}+u_{23}l_{32}+u_{33}\\\end{bmatrix}}$

從最後一個矩陣中，我們可以看到為了消除 $a_{21}$，我們需要將 A 的第一行乘以 $l_{21}$，類似地，為了消除 $a_{31}$，需要將第一行乘以 $l_{31}$。為了計算 L，我們可以簡單地記錄正向消元步驟中使用的乘數，矩陣 U 與正向消元得到的最終上三角矩陣相同。

Python 示例程式碼

求矩陣的逆

求矩陣的逆是一個與求解線性方程組相關的過程。如果找到了係數矩陣的逆，那麼由係數矩陣表示的方程組也就被解出來了。

${\begin{alignedat}{3}AX&&\;=\;&&C\\A^{-1}AX&&\;=\;&&A^{-1}C\\X&&\;=\;&&A^{-1}C\\\end{alignedat}}$

求矩陣的逆的一種方法是透過解一組線性方程組分別求出逆矩陣的每一列。如果 $AB=I$ 並且

$A={\begin{bmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{bmatrix}}\ B={\begin{bmatrix}b_{11}&b_{12}&b_{13}\\b_{21}&b_{22}&b_{23}\\b_{31}&b_{32}&b_{33}\end{bmatrix}}$

那麼

$A{\begin{bmatrix}b_{11}\\b_{21}\\b_{31}\end{bmatrix}}=LU{\begin{bmatrix}b_{11}\\b_{21}\\b_{31}\end{bmatrix}}={\begin{bmatrix}1\\0\\0\end{bmatrix}}$.

我們可以透過使用 LU 分解方法求解方程組來計算 $B$ 的第一列。其餘的列可以以類似的方式計算。正如你所看到的，LU 分解方法的優勢在於 LU 分解只執行一次，結果被多次使用，這降低了整個解決方案的計算複雜度。