MIT線性代數(shù)總結(jié)筆記——LU分解

矩陣分解

矩陣分解（Matrix Factorizations）就是將一個矩陣用兩個以上的矩陣相乘的等式來表達剧辐。而矩陣乘法涉及到數(shù)據(jù)的合成(即將兩個或多個線性變換的效果組合成一個矩陣)咨察，因此可以說，矩陣分解是對數(shù)據(jù)的一種分析亮曹。

矩陣分解	LU分解
分解形式	$A=LU$ ( $L$ 代表下三角矩陣缀棍， $U$ 代表上三角矩陣)
目的	提高計算效率
前提	(1)矩陣是方陣（ $LU$ 分解主要是針對方陣）朴上； (2)矩陣是可逆的，也就是該矩陣是滿秩矩陣懂鸵，每一行都是獨立向量偏螺； (3)消元過程中沒有 $0$ 主元出現(xiàn)，也就是消元過程中不能出現(xiàn)行交換的初等變換匆光。

LU分解

分解形式

$A = LU = \left[\begin{matrix} 1 & 0 & 0 & 0 \\ l_{21} & 1 & 0 & 0 \\ l_{31} & l_{32} & 1 & 0 \\ l_{41} & l_{42} & l_{43} & 1\end{matrix}\right]\left[\begin{matrix} u_{11} & u_{12} & u_{13} & u_{14} \\ 0 & u_{22} & u_{23} & u_{24} \\ 0 & 0 & u_{33} & u_{34} \\ 0 & 0 & 0 & u_{44}\end{matrix}\right]$

簡述

$LU$ 分解常用于求解工業(yè)和商業(yè)問題中的序列方程套像。它是最常見的求解線性系統(tǒng) $Ax=b$ 的方法，主要思路是：把 $A$ 分解成一個下三角矩陣（Lower Triangular Matrix）和一個上三角矩陣（Upper Triangular Matrix）终息，簡稱 $LU$ 夺巩。分解后，等式 $Ax=b$ 可以寫成 $L(Ux)=b$ 周崭，這樣我們令 $y=Ux$ 柳譬，這樣就可以通過分開求解兩個等式來得到 $x$ ：

$Ly=b \\ Ux=y$

即可以先通過 $Ly=b$ 求出 $y$ ，最后再用 $Ux=y$ 续镇，求出 $x$ 美澳。

本質(zhì)上， $LU$ 分解是高斯消元法的一種表達方式，為了更好地理解 $LU$ 分解人柿，我們需要解釋一下高斯消元法柴墩。

高斯消元法（Gaussian Elimination）

簡述

為了求解線性系統(tǒng)忙厌，我們基本的策略是用相等的式子去替代要求解的式子凫岖，來讓求解變得更容易。對于一個線性系統(tǒng)中有若干個未知數(shù)逢净，我們需要將方程組中的一方程的未知數(shù)用含有另一未知數(shù)的代數(shù)式表示哥放，并將其代入到另一方程中，這就消去了一未知數(shù)爹土，得到一解甥雕；或?qū)⒎匠探M中的一方程倍乘某個常數(shù)加到另外一方程中去，也可達到消去一未知數(shù)的目的胀茵，并最終得到線性系統(tǒng)的解社露。這一求解算法稱之為高斯消元法（Gaussian Elimination）。

示例

下文將展示高斯消元法的求解過程琼娘，設(shè)需求解的線性方程組如下：

$\begin{cases} x_1-2x_2+x_3=0 \\ 2x_2-8x_3=8\\5x_1-5x_3=10 \end{cases}$

將其表達為矩陣形式為：

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

為了將多余的未知數(shù) $x_1$ 消除峭弟，我們需要將第三行的 $5$ 消除，矩陣的第一行乘 $-5$ 倍再和第三行相加脱拼，得到：

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

接著再進行對多余的未知數(shù) $x_2$ 的消除瞒瘸，這里將第二行乘 $-5$ 倍再與第三行相加，得到：

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

至此熄浓，我們得到了一個新的三角形矩陣情臭，轉(zhuǎn)換為線性方程組的形式為：

$\begin{cases} x_1-2x_2+x_3=0 \\ x_2-4x_3=4\\x_3=-1 \end{cases}$

通過簡單的回代，我們最終可以得到線性方程組的解：

$\begin{cases} x_1=1 \\ x_2=0\\x_3=-1 \end{cases} \quad\quad\quad \left[\begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{array}\right]$

高斯消元法與LU分解之間的聯(lián)系

那么為什么說 $LU$ 分解其實就是高斯消元法的一種表達方式呢赌蔑？這是因為我們可以將上述示例中每一步的操作用矩陣相乘的形式（行變換的本質(zhì)就是左乘矩陣）表達出來俯在。

例如上文示例中的第一步：“為了將多余的未知數(shù) $x_1$ 消除，我們需要將第三行的 $5$ 消除娃惯，矩陣的第一行乘 $-5$ 倍再和第三行相加” 跷乐，可以表達為：

$\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -5 & 0 & 1 \end{matrix}\right] \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 &10 \end{array}\right]=\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 10 & -10 & 10 \end{array}\right]$

同樣地，第二步：“繼續(xù)進行對多余的未知數(shù) $x_2$ 的消除石景，這里將第二行乘 $-5$ 倍再與第三行相加” 可以表達為：

$\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -5 & 1 \end{matrix}\right] \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 10 & -10 & 10 \end{array}\right] = \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 0 & 30 & -30 \end{array}\right]$

因此劈猿，我們可以用一個矩陣相乘的等式來記錄整個高斯消元的過程：

$\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -5 & 1 \end{matrix}\right]\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -5 & 0 & 1 \end{matrix}\right]\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 &10 \end{array}\right]=\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 0 & 30 & -30 \end{array}\right]$

將三個消元矩陣合并，用 $E$ 表示則為：

$EA =\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -5 & -5 & 1 \end{matrix}\right]\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 &10 \end{array}\right]=\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 0 & 30 & -30 \end{array}\right] = U$

那么我們可以得到關(guān)于 $A$ 的表達式：

$A = \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 &10 \end{array}\right] = E^{-1}U = \left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 5 & 5 & 1 \end{matrix}\right]\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 0 & 30 & -30 \end{array}\right] = LU$

這樣一來我們就得到了 $A$ 的 $LU$ 分解潮孽，即將矩陣A分解為一個下三角矩陣（ $L$ ）和一個上三角矩陣（ $U$ ）的乘積揪荣。

偽代碼

U = A, L = I
for j = 1 : n - 1 do
    for i = j + 1 : n do
        l_ij = u_ij / u_jj
        for k = j : n do
            u_ik = u_ik - l_ij * u_jk
        end for
    end for
end for

此處是矩陣index從1開始計數(shù)。
Credit to http://iacs-courses.seas.harvard.edu/courses/am205/slides/am205_lec07.pdf

算法效率

接下來我們來思考一下算法效率的問題往史，假如我們有一個 $100*100$ 的矩陣仗颈，并且各項均非 $0$ ，那我們需要計算多少次才能得到矩陣 $U$ 呢？

對于這個問題我們先從列的角度來考慮挨决，第一列消元運算結(jié)束以后请祖，矩陣變?yōu)椋?/p>

$\left[\begin{matrix} 1 & \cdots & \cdots & \cdots \\ 0 & \ddots & \cdots & \cdots \\ \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & \cdots & \ddots\end{matrix}\right]$

這一步中，第一列的元素運算了 $100$ 次脖祈，而第一行共有 $100$ 個元素肆捕，于是僅第一行與第一列消元結(jié)束后，我們就計算了 $100^2$ 次盖高。之后我們要研究剩下的 $99*99$ 的矩陣慎陵，以此類推可知，最后的計算量為 $\sum^{n}_{k=1}{k^2}$ 喻奥。

接著席纽，我們可以利用微積分計算得到， $A$ 的操作次數(shù)為 $\frac{1}{3}n^3$ 撞蚕， $b$ 的操作次數(shù)為 $n^2$ 次润梯。

結(jié)合上文偽代碼，因為有三重循環(huán)嵌套甥厦，因此 $LU$ 分解的復(fù)雜度為 $O(n^3)$ 纺铭，其中加法操作為 $\frac{1}{3}n^3$ ，乘法操作為 $\frac{1}{3}n^3$ 矫渔，總共為 $\frac{2}{3}n^3$ 次彤蔽，求解 $b$ 和 $y$ 各需要 $n^2$ 次

前提條件

(1)矩陣是方陣（LU分解主要是針對方陣）；
(2)矩陣是可逆的庙洼，也就是該矩陣是滿秩矩陣顿痪，每一行都是獨立向量；
(3)消元過程中沒有0主元出現(xiàn)油够，也就是消元過程中不能出現(xiàn)行交換的初等變換蚁袭。

LUD分解（LDU Decomposition）

上文中我們已經(jīng)得到了 $A=LU$ ，我們還可以繼續(xù)分解下去得到 $A=LDU$ 石咬， $D$ 為對角矩陣(Diagonal Matrix)揩悄，矩陣的 $LDU$ 分解是在 $LU$ 分解之后，把 $U$ 再次分解鬼悠，目的是把 $U$ 的對角線元素都化為 $1$ 删性，上文示例中我們得到的 $A=LU$ 如下

$A = \left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 &10 \end{array}\right] = LU = \left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 5 & 5 & 1 \end{matrix}\right]\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 0 & 30 & -30 \end{array}\right]$

接下來，讓 $U$ 矩陣中位于對角線上的元素都為 $1$ 焕窝，就可以提出一個對角矩陣 $D$

$LU = \left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 5 & 5 & 1 \end{matrix}\right]\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 0 & 30 & -30 \end{array}\right] =\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 5 & 5 & 1 \end{matrix}\right]\left[\begin{matrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 30 \end{matrix}\right]\left[\begin{array}{ccc|c} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 1 & -1 \end{array}\right]=LDU$

LUP分解（LU Decomposition with Partial Pivoting）

我們來考慮一個矩陣 $A=\left[\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}\right]$ 蹬挺，盡管矩陣 $A$ 非奇異，并且很簡單它掂，但是使用 $LU$ 分解的算法會失敗巴帮，因為第一個主元 $A_{0,0} = 0$ 。在高斯消元法中，我們常常通過人為的行變換來消除主元為 $0$ 時的影響榕茧。例如我們需要把矩陣A的第一行和第二行進行交換得到 $A=\left[\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}\right]$ 垃沦，這樣我們就能將消元進行下去。這樣的操作也可以用矩陣相乘的方法來表達用押，那么在該示例中肢簿，即為 $PA=\left[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}\right]\left[\begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix}\right]=\left[\begin{matrix} 1 & 1 \\ 0 & 1 \end{matrix}\right]$ ，這里的矩陣 $P$ 稱為置換矩陣（Permutation Matrix）只恨。那么就有了LUP分解（LU decomposition with partial pivoting）： $PA = LU$ 译仗。這一算法的出現(xiàn)顯著改善了 $LU$ 分解算法的穩(wěn)定性。

偽代碼

U = A, L = I, P = I
for j = 1 : n - 1 do
    Select i (>= j) that maximizes |u_ij|
    Interchange rows of U: u_(j,j:n) <-> u_(i,j:n)
    Interchange rows of L: l_(j,1:j-1) <-> l_(i,1:j-1)
    Interchange rows of P: p_(j,:) <-> p_(i,:)
    for i = j + 1 : n do
        l_ij = u_ij / u_jj
        for k = j : n do
            u_ik = u_ik - l_ij * u_jk
        end for
    end for
end for