線性方程組(1)-從一開始

02-22

第一次開專欄，主要想整理知識，督促自己學習。儘可能通俗易懂，但仍然預設讀者有一定線性代數基礎（具體來說，上完理工科大一的線性代數課），所以並非從零開始。有些複雜的證明和推導過程會略去。

會用到MATLAB做演示，為了保持一致，相應的矩陣下標也是從1開始。同時，用大寫字母表示矩陣，帶箭頭的小寫字母表示向量，不帶箭頭的小寫字母表示標量。

解線性方程組，用一句話來說就是，已知 $n imes n$ 的可逆矩陣 $A$ 和 $n$ 維列向量 $vec{b}$ ，求 $n$ 維列向量 $vec{x}$ 使得

$Avec{x}=vec{b}$

成立。

通常我們把解記為 $A^{-1}vec{b}$ 。實際上求 $A$ 的逆矩陣本質上也是解 $n$ 個線性方程組

$AX=I$

所以在不必要時通常不會求一個矩陣的逆。

直接解法：LU分解與QR分解

先吃顆定心丸：一般的線性方程組是可以直接求解的。

這兩種直接解法的主要目標就是，將分解為兩個容易求解的矩陣之積，於是原方程變為

$MNvec{x}=vec{b}$

求解過程變為先求解 $M$ ，然後求解 $N$ 。即

$vec{x}=N^{-1}M^{-1}vec{b}$

通常 $M$ 是一系列變換矩陣之積，在對 $A$ 做變換時，可以同時將變換作用於 $vec{b}$ ；但是如果要對同一個A解多個不同的 $vec{b}$ 時，也可以預先將 $M$ 或 $M^{-1}$ 計算出來，之後每輸入一個 $vec{b}$ 都可以將該變換直接作用到 $vec{b}$ 上。

對於LU分解來說，這個過程是高斯消元

$left(egin{matrix} a_{11} & a_{12} & cdots & a_{1n} \ a_{21} & a_{22} & cdots & a_{2n} \ vdots & vdots & ddots & vdots\ a_{n1} & a_{n2} & cdots & a_{nn} end{matrix} ight)=left(I+frac{1}{a_{11}}vec{a_{l1}}vec{e_1}^T ight)left(egin{matrix} a_{11} & a_{12} & cdots & a_{1n} \ 0 & * & cdots & * \ vdots & vdots & ddots & vdots\ 0 & * & cdots & * end{matrix} ight)$

其中

$vec{a_{l1}}=left(egin{matrix} 0\ a_{21}\ vdots\ a_{n1} end{matrix} ight)$ ， $vec{e_1}=left(egin{matrix} 1\ 0\ vdots\ 0 end{matrix} ight)$ ， $left(I+frac{1}{a_{11}}vec{a_{l1}}vec{e_1}^T ight)^{-1}=I-frac{1}{a_{11}}vec{a_{l1}}vec{e_1}^T$

隨後對右下星號塊繼續進行這一過程，最後得到

$A=LU$

其中 $L$ 為下三角矩陣， $U$ 為上三角矩陣。

對於QR分解來說，這個過程是豪斯霍爾德（Householder）變換

$left(egin{matrix} a_{11} & a_{12} & cdots & a_{1n} \ a_{21} & a_{22} & cdots & a_{2n} \ vdots & vdots & ddots & vdots\ a_{n1} & a_{n2} & cdots & a_{nn} end{matrix} ight)=left(I-frac{2}{lVert vec{w} Vert^2}vec{w} vec{w}^T ight)left(egin{matrix} * & * & cdots & * \ 0 & * & cdots & * \ vdots & vdots & ddots & vdots\ 0 & * & cdots & * end{matrix} ight)$

其中

$vec{w}= vec{a_1}-lVert vec{a_1} Vertvec{e_1}$ ， $vec{a_1}=left(egin{matrix} a_{11}\ a_{21}\ vdots\ a_{n1} end{matrix} ight)$ ， $left(I-frac{2}{lVert vec{w} Vert^2}vec{w} vec{w}^T ight)^{-1}=I-frac{2}{lVert vec{w} Vert^2}vec{w} vec{w}^T$

隨後對右下星號塊繼續進行這一過程，最後得到

$A=QR$

其中 $Q$ 為正交矩陣， $R$ 為上三角矩陣。

正交矩陣的求解即為矩陣向量乘

$Qvec{x}=vec{b}$ ， $vec{x} = Q^Tvec{b}$

對於上三角矩陣

$left(egin{matrix} u_{11} & u_{12} & cdots & u_{1n} \ 0 & u_{22} & cdots & u_{2n} \ vdots & vdots & ddots & vdots\ 0 & 0 & cdots & u_{nn} end{matrix} ight)left(egin{matrix} x_1\ x_2\ vdots\ x_n end{matrix} ight)=left(egin{matrix} b_1\ b_2\ vdots\ b_n end{matrix} ight)$

可直接求解

$x_n = frac{b_n}{u_{nn}}$

$cdots$

$x_2 = frac{b_2-sum_{i=3}^{n}u_{2i}x_{i}}{u_{22}}$

$x_1 = frac{b_1-sum_{i=2}^{n}u_{1i}x_{i}}{u_{11}}$

下三角矩陣同理。