主要是想把當下有多記錄的技巧用比較好懂的方式寫出來
所以可能沒有很嚴謹也沒有很完整 QuQ
然後 Rust 系列斷有點久，我盡量不耍廢 QuQ
矩陣可逆性 (Matrix Inversion)
定義：對於 nxn 的矩陣 \$A\$ 若存在一個 nxn 的矩陣 \$B\$，使得 \$AB = BA = I\$
則稱 \$A\$ 為可逆矩陣 (invertible)、也為非奇異矩陣 (nonsingular)
其中 \$I\$ 為單位矩陣 (identity matrix)、\$B\$ 稱作 \$A\$ 的逆矩陣 (inverse of A) 記作 \$A^{-1}\$
定理：若 \$A\$ 可逆，則 \$A^{-1}\$ 唯一
證明：假設 \$A\$ 有兩個相異的逆矩陣 \$B\$、\$C\$
則 \$AB = I\$、\$AC = I\$
使得 \$B = BI = B(AC) = (BA)C = IC = C\$
與假設矛盾，故 \$A\$ 僅有唯一一個逆矩陣
定理：若 \$A\$ 可逆，則 \$Ax = b\$ 的有唯一解 \$x = A^{-1}b\$
證明：\$Ax = b \Leftrightarrow A^{-1}Ax = A^{-1}b \Leftrightarrow Ix = A^{-1}b \Leftrightarrow x = A^{-1}b\$
定理：若 \$Ax = 0\$ 有非零解 \$x\$ 存在，則 \$A\$ 不為可逆
證明：假設 \$A\$ 可逆下 \$x\$ 存在非零解
\$Ax = 0 \Rightarrow A^{-1}Ax = A^{-1}0 \Rightarrow x = 0\$
因為 \$x\$ 必為零解所以矛盾，故假設錯誤，即 \$A\$ 不可逆
定理：若對角矩陣 (diagonal matrix) 可逆，則對角線上元素皆不為 \$0\$
證明：(107.08.28 更正)可以利用上一個定理證明
對角矩陣 \$A = \begin{bmatrix}
a_{11} & 0 & \cdots & 0 \\
0 & a_{22} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{nn} \\
\end{bmatrix}\$
假設 \$a_{11} = 0\$，則可使得 \$Ax = 0\$ 的 \$x\$ 存在非零解，如下 \${\color{Blue}\alpha}\$ 可不為 \$0\$
\$\begin{bmatrix}
{\color{Red} 0 } & 0 & \cdots & 0 \\
0 & a_{22} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{nn} \\
\end{bmatrix}
\begin{bmatrix} {\color{Blue}\alpha} \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix} =
\begin{bmatrix} 0 \\ 0 \\ \vdots \\ 0 \\ \end{bmatrix}\$
由上個定理可知 \$Ax = 0\$ 存在非零解，則 \$A\$ 不可逆，故矛盾，因此 \$a_{11}\$ 不可為 \$0\$
同理可知，\$a_{ii} \neq 0, \forall 1 \leqslant i \leqslant n\$
Note：若對角矩陣 \$A\$ 可逆
\$A = \begin{bmatrix}
a_{11} & 0 & \cdots & 0 \\
0 & a_{22} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & a_{nn} \\
\end{bmatrix}\$ 則逆矩陣 \$A^{-1} = \begin{bmatrix}
\dfrac 1 {a_{11}} & 0 & \cdots & 0 \\
0 & \dfrac 1 {a_{22}} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \dfrac 1 {a_{nn}} \\
\end{bmatrix}\$
\$a_{11}\$ ~ \$a_{nn}\$ 皆不為 \$0\$
定理：若 \$A\$、\$B\$ 為可逆矩陣，則 \$AB\$ 亦為可逆，且 \$(AB)^{-1} = B^{-1}A^{-1}\$
證明：\$(AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = AIA^{-1} = AA^{-1} = I\$
所以 \$B^{-1}A^{-1}\$ 是 \$AB\$ 的逆矩陣
延伸：
\$(A_{1}A_{2} \cdots A_{n})^{-1} = A_{n}^{-1} \cdots A_{2}^{-1}A_{1}^{-1}\$
使用 Gauss-Jordan Elimination 求逆矩陣
Gauss-Jordan Elimination 為求方程式解的列運算 (elementary row operations)Gauss Elimination 為使用 forward elimination 求出上三角矩陣 (strict
triangular form)
Gauss-Jordan Elimination 則包含 back substitution 將左方矩陣進一步化簡成單位矩陣
舉例：
\$A = \begin{bmatrix}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & 2 & 2
\end{bmatrix}\$ 求 \$A^{-1}\$
過程：
從定義知 \$AA^{-1} = I\$，把 \$A^{-1}\$ 拆作三欄方便說明
\$A\begin{bmatrix}
x_1 & x_2 & x_3
\end{bmatrix} = \begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 1
\end{bmatrix} = \begin{bmatrix}
e_1 & e_2 & e_3
\end{bmatrix}\$
則可等價於下方三個方程式，且所求 \$A^{-1}\$ 為求出 \$(x_1 , x_2 , x_3)\$ 的向量解
\$\begin{cases}
Ax_1 = e_1 \Rightarrow A^{-1}Ax_1 = x_1 = A^{-1}e_1\\
Ax_2 = e_2 \\
Ax_3 = e_3
\end{cases}\$
求解可利用增廣矩陣 (augmented matrix) 與列運算把左邊化簡成單位矩陣來同時解三個方程式
\$\left[\begin{array}{ccc|ccc}
2 & -1 & 0 & 1 & 0 & 0 \\
-1 & 2 & -1 & 0 & 1 & 0 \\
0 & -1 & 2 & 0 & 0 & 1 \\
\end{array} \right]
\Rightarrow
\left[\begin{array}{ccc|ccc}
2 & -1 & 0 & 1 & 0 & 0 \\
0 & 2\over 3 & -1 & 1\over 2 & 1 & 0 \\
0 & -1 & 2 & 0 & 0 & 1 \\
\end{array} \right]
\Rightarrow
\left[\begin{array}{ccc|ccc}
2 & -1 & 0 & 1 & 0 & 0 \\
0 & 2\over 3 & -1 & 1\over 2 & 1 & 0 \\
0 & 0 & 4\over 3 & 1\over 3 & 2\over 3 & 1 \\
\end{array} \right]
\Rightarrow \$
\$\left[\begin{array}{ccc|ccc}
2 & -1 & 0 & 1 & 0 & 0 \\
0 & 2\over 3 & 0 & 3\over 4 & 3\over 2 & 3\over 4 \\
0 & 0 & 4\over 3 & 1\over 3 & 2\over 3 & 1 \\
\end{array} \right]
\Rightarrow
\left[\begin{array}{ccc|ccc}
2 & 0 & 0 & 3\over 2 & 1 & 1\over 2 \\
0 & 2\over 3 & 0 & 3\over 4 & 3\over 2 & 3\over 4 \\
0 & 0 & 4\over 3 & 1\over 3 & 2\over 3 & 1 \\
\end{array} \right]
\Rightarrow
\left[\begin{array}{ccc|ccc}
1 & 0 & 0 & 3\over 4 & 1\over 2 & 1\over 4 \\
0 & 1 & 0 & 1\over 2 & 1 & 1\over 2 \\
0 & 0 & 1 & 1\over 4 & 1\over 2 & 3\over 4 \\
\end{array} \right]\$
所求 \$A^{-1}\$ 即為 \$\begin{bmatrix}
3\over 4 & 1\over 2 & 1\over 4 \\
1\over 2 & 1 & 1\over 2\\
1\over 4 & 1\over 2 & 3\over 4
\end{bmatrix}\$
詳細原理如下
\$\left[\begin{array}{c|c}
A & I \\
\end{array} \right]
\overset{G.J.E.}{\Rightarrow}
\left[\begin{array}{c|c}
A^{-1}A & A^{-1}I \\
\end{array} \right]
=
\left[\begin{array}{c|c}
I & A^{-1} \\
\end{array} \right]\$
Q: 為何可以合併運算?
A: 因為左方矩陣化為單位矩陣的列運算相同，且列運算在向量間不會互相干擾
以 \$x_1\$ 向量 \$(a, b, c)\$ 來看
\$\left[\begin{array}{ccc|c}
2 & -1 & 0 & 1 \\
-1 & 2 & -1 & 0 \\
0 & -1 & 2 & 0 \\
\end{array} \right]
\overset{G.J.E.}{\Rightarrow}
\left[\begin{array}{ccc|c}
1 & 0 & 0 & 3\over 4 \\
0 & 1 & 0 & 1\over 2 \\
0 & 0 & 1 & 1\over 4 \\
\end{array} \right]\$
可得 \$\begin{cases}
1a = {3\over 4} \\
1b = {1\over 2} \\
1c = {1\over 4}
\end{cases}
\Rightarrow
x_1 = (a, b, c) =
\begin{bmatrix}
3\over 4 \\
1\over 2 \\
1\over 4
\end{bmatrix}\$，\$x_2\$、\$x_3\$ 同理
參考資料：
Linear Algebra (Chapter 1: Matrices and Systems of Equations) Chao-Chun Chen (NCKU)
沒有留言:
張貼留言