第六讲.LU分解
LU分解
對矩陣(A)，有(E_{21}A = U)：
[egin{pmatrix}
1 & 0 \
-4 & 1
end{pmatrix}
egin{pmatrix}
2 & 1 \
8 & 7
end{pmatrix}
=
egin{pmatrix}
2 & 1 \
0 & 3
end{pmatrix}
]
現在要轉換成(A = LU)的形式，這里的(L)即為(E_{21}^{-1})。
[egin{pmatrix}
2 & 1 \
8 & 7
end{pmatrix}
=
egin{pmatrix}
1 & 0 \
4 & 1
end{pmatrix}
egin{pmatrix}
2 & 1 \
0 & 3
end{pmatrix}
]
這種分解形式相當于將一個矩陣分解為一個對角線全為(1)的下三角矩陣與一個對角線為主元的上三角矩陣的乘積。
另外一種分解方式是(A = LDU)，其中(D)是一個對角線為主元的對角矩陣（diagonal），如：
[egin{pmatrix}
2 & 1 \
8 & 7
end{pmatrix}
=
egin{pmatrix}
1 & 0 \
4 & 1
end{pmatrix}
egin{pmatrix}
2 & 0 \
0 & 3
end{pmatrix}
egin{pmatrix}
1 & frac{1}{2} \
0 & 1
end{pmatrix}
]
為什么用(A = LU)，而不是(U = EA)？
答：(L)容易計算，(E)不易計算：(L)是將消元的系數直接寫到單位陣上得到的。因此，(L)只包含消去信息，(E)包含其他信息。
LU分解求線性方程組與計算量
(LU)分解一個比較重要的意義在于加速（多個）線性方程組的求解。首先將(A)分解為(LU)的形式，然后再計算(LUx = b)。計算(LUx = b)，可以分為兩步，即：(Ly = b, Ux = y)。這兩個線性方程組的求解都是(O(n^2))的。
將(n)階矩陣(A)通過初等行變換，變為(U)，總共大概需要(n^2 +(n - 1)^2 + dots ,1^2 approx frac{1}{3}n^3)次操作。
LU分解的存在性和唯一性
存在性定理：設可逆矩陣(A)的順序主子陣(A_k(k = 1, dots, n))均為可逆矩陣，則(A)有(LU)分解。
證明：對(A)的階數(n)用數學歸納法。當(n = 1)時，(L = (1), U = A = (a_{11})
eq 0)，定理成立！設(n = k)時定理成立，則(n = k + 1)時，設(A = pmatrix{A_k & eta \ alpha^T & a_{nn}})，其中(eta)是(k)維列向量，(alpha^T)是(k)維行向量。由(A_k)可逆，對(A)做消元：(pmatrix{I_k & 0 \ -alpha^TA_k^{-1} & 1}A = pmatrix{A_k & eta \ 0 & a_{nn} - alpha^TA_k^{-1}eta})，即：(A = pmatrix{I_k & 0 \ alpha^TA_k^{-1} & 1}pmatrix{A_k & eta \ 0 & a_{nn} - alpha^TA_k^{-1}eta})。因為此時右側矩陣還未達到(U)的形式，因此需要繼續分解。由歸納假設，(A_k = L_kU_k)。故：(A = pmatrix{I_k & 0 \ alpha^TA_k^{-1} & 1}pmatrix{L_k & 0 \ 0 & 1}pmatrix{U_k & L_k^{-1}eta \ 0 & a_{nn} - alpha^TA_k^{-1}eta} = LU)。定理得證！
唯一性定理：設(n)階可逆陣(A = LU)，其中(L)為下三角矩陣，(U)為上三角矩陣，且(l_{ii} = 1， u_{ii}
eq 0(1 leq i leq n))，則分解唯一。
證明：設可逆陣(A)有兩個(LU)分解：(A = L_1U_1 = L_2U_2)，則(L_1^{-1}L_2 = U_1U_2^{-1})，因為上（下）三角矩陣乘以上（下）三角矩陣也為上（下）三角矩陣，兩者相等說明都為對角陣。因為(L_1, L_2)的對角元為(1)，故(L_1^{-1}L_2)對角元全為(1)，故(L_1^{-1}L_2 = U_1U_2^{-1} = I)，即(L_1 = L_2, U_1 = U_2)
對稱矩陣的(LDL^T)分解
設可逆對稱矩陣(A)不需換行，只通過消元能化成上三角矩陣(U)，有(A = LDU)，則(A = A^T = U^TDL^T)。由(LDU)分解唯一性知(U = L^T)，故(A = LDL^T)
置換矩陣
一個(n)元置換是(1, 2, dots, n)的一個排列，這誘導了(n)階單位矩陣行的一個重排。單位陣行重排后得到的矩陣稱為置換矩陣。
總共有(n!)個(n)階置換陣。置換陣的逆還是置換陣，置換陣的乘積仍是置換陣。置換矩陣(P)滿足(P^{-1} = P^T)。
(PA = LU)分解
設(A)是一個(n)階可逆陣，則存在置換陣(P)，使得(PA = LU)。
證明：對矩陣(A)的階數(n)用數學歸納法。當(n = 1)時定理顯然成立，假設(n = k)時定理成立。當(n = k + 1)時，(A)的第一列有非零元，否則(A)不可逆。設(a_{i1}
eq 0)，則調換第(1)行和第(i)行，得矩陣(A')，于是(A' = P_{i1}A)也可逆，對(A')作消元得(A'' = pmatrix{a_{i1} & * \ 0 & A_1})，且(A' = pmatrix{1 & 0 \ t & I}A'')。(A_1)為(n - 1)階可逆陣，由歸納假設知，存在(n - 1)階置換陣(P_1)使得(P_1A_1 = L_1U_1)，于是：
[egin{aligned}
P_{i1}A = A' &= pmatrix{1 & 0 \ t & I}pmatrix{a_{i1} & * \ 0 & A_1} \
&= pmatrix{1 & 0 \ t & I}pmatrix{1 & \ & P_1^{-1}}pmatrix{1 & \ & L_1}pmatrix{a_{i1} & * \ 0 & U_1} \
&= pmatrix{1 & \ & P_1^{-1}}pmatrix{1 & 0 \ P_1t & I}pmatrix{1 & \ & L_1}pmatrix{a_{i1} & * \ 0 & U_1} \
end{aligned}
]
（注：最后一步的變換是為了湊出形式）
故，(pmatrix{1 & \ & P_1}P_{i1}A = pmatrix{1 & 0 \ P_1t & L_1}pmatrix{a_{i1} & * \ 0 & U_1} = LU)
最后令(P = pmatrix{1 & \ & P_1}P_{i1})，則(PA = LU)
總結
