LU、奇異值分解與偽逆

矩陣分解把矩陣拆成較簡單的運算。LU 記錄消元過程，適合反覆求解方陣系統。奇異值分解（SVD）也適用於矩形矩陣和奇異矩陣：它把伸縮與旋轉或反射分開，並指出丟失信息及逆運算不穩定的方向。

1 用 LU 表示消元

若高斯消元不需要交換行，可把消元乘數存入單位下三角矩陣 $L$，得到 $A=LU$，其中 $U$ 為上三角矩陣。例如

$$A=\begin{pmatrix}2&1\\4&5\end{pmatrix},\quad L=\begin{pmatrix}1&0\\2&1\end{pmatrix},\quad U=\begin{pmatrix}2&1\\0&3\end{pmatrix}.$$

求解 $Ax=b$ 時先解 $Ly=b$，再解 $Ux=y$。若 $b=(5,13)$，則 $y=(5,3)$，$x=(2,1)$。面對多個右端向量時可以重複使用這些因子。若主元為零，可能需要交換行；此時應寫成 $PA=LU$，其中 $P$ 為置換矩陣。即使主元非零，太小的主元也可能使選主元對數值計算很重要。聲稱每個可逆矩陣都有不交換行的 LU 分解是不正確的。

實內積、誘導範數與所需不等式

實向量空間上的內積是取值於實數的映射 $\langle u,v\rangle$，它對稱、對每個變量線性，並且正定：$v\ne0$ 時 $\langle v,v\rangle>0$。線性性給出 $\langle0,v\rangle=0$。定義 $\|v\|=\sqrt{\langle v,v\rangle}$，則範數恰在零向量處為零，且 $\|cv\|=|c|\|v\|$。$\mathbb R^m$ 上的標準例子是 $\langle u,v\rangle=\sum_{i=1}^mu_iv_i$。內積為零的向量稱為正交；不同成員互相正交且每個成員範數為一的列表稱為正交規範列表。

若 $v\ne0$，將 $t=\langle u,v\rangle/\|v\|^2$ 代入非負平方 $\|u-tv\|^2$，以雙線性展開得 $\|u\|^2-\langle u,v\rangle^2/\|v\|^2\ge0$，故 $|\langle u,v\rangle|\le\|u\|\|v\|$。若 $v=0$，該不等式直接成立。對 $v\ne0$，等號意味着 $\|u-tv\|=0$，等價於 $u=tv$；零向量情形也取等。最後展開 $\|u+v\|^2$ 並對交叉項使用該界，得到 $\|u+v\|^2\le(\|u\|+\|v\|)^2$。待開方的兩邊非負，因此得到三角不等式。這確實定義了範數，任何非零向量的歸一化都只除以正實數；這裏不使用複雙線性的約定。

不預設計數結論的有限基存在與擴充

設實向量空間 $V$ 已給定有限生成列表 $t_1,\ldots,t_N$。先證明任何線性無關列表 $u_1,\ldots,u_k$ 的長度不超過 $N$。插入 $j$ 個向量後，維持一個由 $u_1,\ldots,u_j$ 與 $N-j$ 個剩餘舊向量組成的生成列表。將 $u_{j+1}$ 按此列表展開，至少一個剩餘舊向量的係數非零；否則它在先前 $u_i$ 的張成空間中，與無關性矛盾。解出這個舊向量，再以 $u_{j+1}$ 取代它。新列表仍張成同一空間，而且保留全部先前插入向量。若 $k>N$，則 $N$ 步後前 $N$ 個向量已張成 $V$，與 $u_{N+1}$ 的無關性矛盾。此即所需上界，也包括 $N=0$。

每個子空間 $W$ 都有有限基。從空的無關列表開始；若當前張成空間尚不是 $W$，就在 $W$ 中取一個不在該張成空間內的向量。若新向量在某關係中的係數非零，就能由舊向量表示它，矛盾，故新列表仍無關。已證上界允許至多添加 $N$ 次，所以過程必停止於 $W$ 的無關生成列表。若 $W=\{0\}$，立即得到空基。改從 $W$ 內任意給定無關列表開始，同樣證明該列表可擴充為 $W$ 的基；只需有界有限次選擇。最後，若兩組基的長度為 $p,q$，分別把它們用作上界證明中的有限生成列表，得到 $p\le q$ 與 $q\le p$。故基的長度有良定義，稱為維數。這些論證補足秩–零度定理所用的基存在、擴充與維數事實。

正交規範基，以及保留指定向量的擴充

再設 $V$ 具有實正定內積。對無關列表 $v_1,\ldots,v_s$，逐次定義

$$w_j=v_j-\sum_{i<j}\langle v_j,q_i\rangle q_i,\qquad q_j=w_j/\|w_j\|.$$

歸納假設先前 $q_i$ 正交規範。對 $l<j$ 與 $q_l$ 取內積，得 $\langle w_j,q_l\rangle=\langle v_j,q_l\rangle-\langle v_j,q_l\rangle=0$。若 $w_j=0$，則 $v_j$ 在先前張成空間中，矛盾，因此可合法除以它的正範數。所列公式及其移項式說明前 $j$ 個新舊向量張成相同空間，歸納完成。用於一組基就得到正交規範基，子空間亦然。若要擴充一組指定的正交規範向量，先由已證定理將它擴充為普通基，再按此順序進行上述構造。原先指定的向量沒有分量被減去，範數又為一，所以全都精確保留。空列表與零子空間無需相除。這證明了 SVD 及投影存在性所用的正交規範擴充。

固定整數 $n\ge1$，在 $\mathbb R^n$ 上使用歐幾里得範數。集合若包含在某個有限半徑的球內，就稱為有界；若補集是開集，就稱為閉集；若它的每個由 $\mathbb R^n$ 中開集組成的覆蓋都有有限子覆蓋，就稱為緊集。我們使用實數完備性，包括閉區間套性質。

有限維歐幾里得空間的 Heine–Borel 定理

定理。 集合 $K\subseteq\mathbb R^n$ 緊致，當且僅當它閉且有界。空集具有這三種性質。

緊致推出有界。 開球 $B(0,m)$（整數 $m\ge1$）覆蓋 $K$。取有限子覆蓋後，$K$ 包含在其中最大的球內。

緊致推出閉。 設 $K\ne\varnothing$ 且 $y\notin K$。開球 $B(x,\|x-y\|/2)$（$x\in K$）覆蓋 $K$。取中心為 $x_1,\ldots,x_r$ 的有限子覆蓋，令 $\delta=\min_i\|x_i-y\|/2>0$。若 $z$ 在以 $x_i$ 為中心的所選球內，三角不等式給出 $\|z-y\|>\|x_i-y\|/2\ge\delta$。所以 $B(y,\delta)$ 不與 $K$ 相交，補集是開集。

閉且有界推出緊致。 設非空的 $K$ 閉且有界，把它包含在閉立方體 $Q_0=[-M,M]^n$ 內，其中 $M>0$。假設 $K$ 的某個開覆蓋沒有有限子覆蓋。把每個坐標區間分成兩個閉半區間，所得 $2^n$ 個閉子立方體覆蓋 $Q_0$。至少一個子立方體與 $K$ 的交集不能由給定覆蓋族有限覆蓋；否則把有限多個有限子覆蓋合併，就能覆蓋 $K$。選取這樣的子立方體並重複，得到閉立方體套 $Q_j$，其邊長為 $2M/2^j$，且 $K\cap Q_j$ 不能被有限覆蓋，因而非空。

對每個坐標使用閉區間套性質，得到公共坐標值；合起來得到 $p\in\bigcap_jQ_j$。$Q_j$ 中任意兩點的距離不超過 $2M\sqrt n/2^j$，所以交集中只有 $p$。選取 $x_j\in K\cap Q_j$，則 $\|x_j-p\|\le2M\sqrt n/2^j\to0$。閉集包含這種極限：若 $p$ 在開補集中，$p$ 周圍某個開球就會使最終的 $x_j$ 落在 $K$ 外，矛盾。因此 $p\in K$。

覆蓋中有一個成員 $O$ 含 $p$，由開放性，存在 $\varepsilon>0$ 使 $B(p,\varepsilon)\subseteq O$。當 $j$ 足夠大時，$Q_j$ 的每點到 $p$ 的距離都小於 $\varepsilon$，於是單個 $O$ 就覆蓋 $K\cap Q_j$，與 $Q_j$ 的選取矛盾。因此每個開覆蓋都有有限子覆蓋。這裏 $2^n$ 是有限數；若改成無限多個子塊，這個論證就不再成立。

連續像與極值

定理。 若 $K\subseteq\mathbb R^n$ 緊致，且 $F:K\to\mathbb R^m$ 相對於 $K$ 連續，則 $F(K)$ 緊致。特別地，非空緊集 $K$ 上的連續函數 $f:K\to\mathbb R$ 有界，並達到最大值和最小值。

證明。 $F(K)$ 的開覆蓋 $(O_i)$ 的原像是相對開集 $F^{-1}(O_i)=K\cap U_i$，其中 $U_i$ 在 $\mathbb R^n$ 中開。這些 $U_i$ 覆蓋 $K$，所以有限多個足夠。對應的 $O_i$ 覆蓋 $F(K)$，證明了像的緊致性。對標量函數 $f$，由已證明定理的一維情形，其像非空、閉且有界。令 $a=\sup f(K)$。對每個 $j\ge1$，由上確界定義，可取 $y_j\in f(K)$ 使 $a-1/j<y_j\le a$。於是 $y_j\to a$，閉性使 $a$ 屬於像，所以最大值可達。對 $-f$ 使用同一論證即得最小值。該結論證明存在性，而不提供極大點的計算公式。

不暗用求導法則的「極大點產生特徵向量」步驟

設 $S=S^T$ 為實矩陣，$\|u\|_2=1$，且 $u^TSu$ 是二次型在單位球面上的最大值。對 $w\perp u$，記 $a=u^TSu$、$b=w^TSu$、$c=w^TSw$、$d=\|w\|_2^2$。譜定理證明中的歸一化曲線對應二次型值為

$$G(t)=\frac{a+2bt+ct^2}{1+dt^2},\qquad \frac{G(t)-G(0)}t=\frac{2b+t(c-ad)}{1+dt^2}\quad(t\ne0).$$

最後的差商在 $t\to0$ 時趨於 $2b$。極大性使它在 $t>0$ 時非正、$t<0$ 時非負，所以共同的雙側極限為零，故 $w^TSu=b=0$。這裏使用明確的有理差商，不暗中調用多元梯度或鏈式法則。已證明的正交規範擴充將 $u^\perp$ 與少一維的實坐標空間對應起來；在此坐標中，其不變限制的矩陣對稱，因為 $x^TSy=(Sx)^Ty$。這就說明維數歸納的合法性，也包括最後的零維正交補。

2 實對稱矩陣譜定理

定理。 對 $n\ge1$，每個實對稱矩陣 $S\in\mathbb R^{n\times n}$ 都有正交規範特徵向量基，且特徵值均為實數。

證明。 當 $n=1$ 時，矩陣是實標量，標準單位向量構成正交規範特徵向量基。設 $n\ge2$。連續函數 $v^TSv$ 在緊的單位球面上取得最大值。設 $u$ 是達到最大值的單位向量。對任意 $w\perp u$，令 $\gamma(t)=(u+tw)/\|u+tw\|$。因為 $\|u+tw\|^2=1+t^2\|w\|^2>0$，分母對每個實數 $t$ 均非零。函數 $\gamma(t)^TS\gamma(t)$ 在 $t=0$ 取得最大值，求導得 $2w^TSu=0$。取 $w=Su-(u^TSu)u$，則 $w\perp u$ 且 $w^TSu=\|w\|^2=0$，所以 $Su=(u^TSu)u$。因此 $u$ 是特徵向量，其特徵值 $u^TSu$ 為實數。由於 $u^TSw=(Su)^Tw=0$ 對 $w\perp u$ 成立，其正交補是不變子空間。把 $S$ 限制在該正交補上仍得到對稱算子，對維數歸納即可。$\square$

對於 $S=A^TA$，因為 $v^TSv=\|Av\|^2\ge0$，所有特徵值均非負。

3 奇異值分解

取 $A^TA$ 的一組正交規範特徵向量基 $v_i$，使正特徵值排在前面。將這些特徵值寫成 $\sigma_i^2$，其中 $\sigma_i>0$，$1\le i\le r$。令 $u_i=Av_i/\sigma_i$，則

$$u_i^Tu_j=\frac{v_i^TA^TAv_j}{\sigma_i\sigma_j}=\delta_{ij}.$$

將這些向量擴充成 $\mathbb R^m$ 的正交規範基。特徵值為零的特徵向量滿足 $Av_i=0$，因此

$$A=U\Sigma V^T,$$

其中 $U,V$ 是正交矩陣，$\Sigma$ 是矩形對角矩陣，其正對角元滿足 $\sigma_1\ge\cdots\ge\sigma_r$。這些數稱為奇異值。它們不一定是 $A$ 的特徵值；它甚至可能不是方陣。

公式顯示 $Av_i=\sigma_i u_i$：先用 $V^T$ 旋轉坐標，沿各個有效坐標伸縮，再用 $U$ 旋轉。矩陣的秩為 $r$，核由其餘 $v_i$ 張成。

4 偽逆與最小範數

定義 $A^+=V\Sigma^+U^T$，把每個正奇異值換成其倒數，並轉置矩形形狀。於是

$$x_*=A^+b=\sum_{i=1}^r\frac{u_i^Tb}{\sigma_i}v_i.$$

定理。 $x_*$ 使 $\|Ax-b\|$ 最小；在所有使殘差最小的向量中，它的歐氏範數最小，且唯一。

證明。 寫成 $x=\sum z_iv_i$ 和 $b=\sum c_iu_i$。由正交性，殘差平方為 $\sum_{i\le r}(\sigma_iz_i-c_i)^2+\sum_{i>r}c_i^2$。取得最小值要求有效坐標滿足 $z_i=c_i/\sigma_i$。核方向的坐標不影響殘差，卻對 $\|x\|^2$ 貢獻 $\sum_{i>r}z_i^2$，該項唯一的最小值在這些坐標全為零時取得。$\square$

對 $A=\begin{pmatrix}1&1\\0&0\end{pmatrix}$，一個正奇異值為 $\sqrt2$，相應向量為 $v_1=(1,1)/\sqrt2$ 和 $u_1=(1,0)$。若 $b=(4,3)$，則 $x_*=(2,2)$，預測向量為 $(4,0)$，殘差為 $(0,3)$。所有最小化向量均滿足 $x_1+x_2=4$，但 $(2,2)$ 的範數最小。

小奇異值會放大逆運算系數中的誤差：擾動 $\varepsilon u_i$ 使 $A^+b$ 改變 $(\varepsilon/\sigma_i)v_i$。截斷或正則化會改變問題，必須明確說明，不能稱為精確求逆。

5 分級練習

E1 基礎。 求 $A=\begin{pmatrix}1&2\\3&8\end{pmatrix}$ 的 LU 分解，並解 $Ax=(5,17)^T$。

E2 奇異值分解。 給出 $D=\begin{pmatrix}3&0\\0&0\\0&0\end{pmatrix}$ 的奇異值及一個偽逆。

E3 最小範數。 對行矩陣 $A=(1\;2)$ 和目標 $b=5$，求範數最小的精確解並證明其最小性。

E4 選主元。 給出一個可逆 $2\times2$ 矩陣，使其在不交換行的情況下不能寫成 $A=LU$，其中 $L$ 是單位下三角矩陣，$U$ 是上三角矩陣。

6 完整解答

S1. $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$，$U=\begin{pmatrix}1&2\\0&2\end{pmatrix}$。前代得 $y=(5,2)$，回代得 $x=(3,1)$。

S2. 正奇異值是 3，另一個奇異值是 0。$D^+=\begin{pmatrix}1/3&0&0\\0&0&0\end{pmatrix}$。它把第一個觀測坐標除以 3，並將未確定的定義域坐標設為零。

S3. $A^+=\binom12/5$，所以 $x_*=(1,2)$。每個精確解都形如 $(1,2)+t(-2,1)$。這兩個向量正交，因此範數平方為 $5+5t^2$，在零處唯一地取得最小值。

S4. 取 $A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$。若 $L=\begin{pmatrix}1&0\\\ell&1\end{pmatrix}$ 且 $U=\begin{pmatrix}u&v\\0&w\end{pmatrix}$，則左上角元素迫使 $u=0$，從而左下角元素 $\ell u=0$，與 $a_{21}=1$ 矛盾。交換行可解決這個主元障礙。

總結

LU 封裝消元，SVD 封裝幾何，即使矩陣是矩形或奇異的也適用。偽逆選出唯一的最小範數最小二乘解。使用分解時應始終注意其假設、秩的信息和數值影響。