Linear Algebra – Lesson 4. A的LU分解

Schedule

  • Inverse of AB, A^T
  • Product of elementation matrices
  • $A=LU$ (no row exchanges)

Inverse of AB, A^TABA^T 的逆

假设 A , B 均可逆,那么 AB 的逆是什么?

AB 的逆是 A 的逆和 B 的逆的逆序相乘,也就是 B^{-1}A^{-1} .

这就像是穿袜子,穿鞋子,所以脱下来也得先脱鞋子再脱袜子.

对于某可逆方阵来说,其转置矩阵的逆是?

对于 AA^{-1}=I 同时进行转置,得到 (A^{-1})^T(A)^T=I .

从而得知对于可逆方阵 A来 说,其转置矩阵 A^T 的逆是 (A^{-1})^T .

注意, 这里提到的是方阵, A^{T} 也是方阵, 故 A^{T} 的左逆和右逆相同.

所以才可以说其转置矩阵 A^T 的逆是 (A^{-1})^T .

为什么对于 AA^{-1} 的转置是 (A^{-1})^T(A)^T ?

假设 Am\times n 矩阵, Bn\times p 矩阵,两者均可逆,

则进一步设 AB=C ,其中 C_{ij}=\sum_{k=1}^nA_{ik}B_{kj}.

B^TA^T=D ,其中 D_{ij}=\sum_{k=1}^nB^T_{ik}A^T_{kj}.

因为 B^T_{ik} = B_{ki}, A^T_{kj} = A_{jk}, 所以 D_{ij}=\sum_{k=1}^nB^T_{ik}A^T_{kj} = \sum_{k=1}^nA_{jk}B_{ki} = (AB)^T

从而实现证明 (AB)^T=B^TA^T


Product of elimination matrices – 消元矩阵的乘积

对于主元全部非0的可逆矩阵 A ,经过消元后得到 U , 那么对于 A=LU 如何求解 L ?

e.g. 假设有矩阵 A=\begin{bmatrix}2&1\8&7\end{bmatrix} ,经过转换 E_{21}=\begin{bmatrix}1&0\-4&1\end{bmatrix} ,得到矩阵 U=\begin{bmatrix}2&1\0&3\end{bmatrix} , 即:

\begin{bmatrix}1&0\-4&1\end{bmatrix}*\begin{bmatrix}2&1\8&7\end{bmatrix}=\begin{bmatrix}2&1\0&3\end{bmatrix}

对于想求解的 L ,可以从 A=LU 得知, L=E^{-1} ,所以 L=\begin{bmatrix}1&0\4&1\end{bmatrix}.

这里 U 表示的是上三角(Upper triangular)矩阵,而 L 代表的是下三角(Lower triangular)矩阵.

有时候会将主元单独列出来组合一个矩阵,从而形成 A=LDU 的形式. 这里D指的是对角矩阵(Diagonal Matrix).

\begin{bmatrix}2&1\8&7\end{bmatrix}=\begin{bmatrix}1&0\4&1\end{bmatrix} \cdot \begin{bmatrix}2&1\0&3\end{bmatrix}=\begin{bmatrix}1&0\4&1\end{bmatrix} \cdot \begin{bmatrix}2&0\0&3\end{bmatrix} \cdot \begin{bmatrix}1&\frac{1}{2}\0&1\end{bmatrix}

对于 E_{32}E_{31}E_{21}A=U (no row exchanges)的情况下, 如果想得到 A=LU 中的 L ,则可以得出 L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}

对于3维矩阵来说,假设存在如下的变换使得 EA=U ,同时 E_{31}=I ,那么:

\begin{bmatrix}1&0&0\0&1&0\0&-5&1\end{bmatrix} \cdot \begin{bmatrix}1&0&0\-2&1&0\0&0&1\end{bmatrix}=\begin{bmatrix}1&0&0\-2&1&0\10&-5&1\end{bmatrix}=E\leftarrow(EA=U)\
\begin{bmatrix}1&0&0\2&1&0\0&0&1\end{bmatrix} \cdot \begin{bmatrix}1&0&0\0&1&0\0&5&1\end{bmatrix}=\begin{bmatrix}1&0&0\2&1&0\0&5&1\end{bmatrix}=L\leftarrow(A=LU)

对于 A=LU ,如果不存在行互换,消元乘数(即消元步骤中需要乘以并减去的倍数)可以直接写入 L 中.

If no row exchanges, multipliers go directly into L.

对于大小为 n \times n 的矩阵 A 的消元,其总步骤数共有多少? 消元的总步骤数是否正比于 nn^2n^3 ?

假设 n=100 , 并且矩阵 A 中没有0(如果有很多0的话操作会快很多), 将一次操作定义为针对一个元素的一次乘法和加法.

第一行不变,将其他行的首个元素系数消除,将进行大约100^2次操作(如果第一行也发生变化的话就正好是100^2次,准确的数字应该是100*99),

同样对第二行进行消元,第二行不变,将第二主元下所有其他系数消除,则进行大约99^2次操作,

依次进行下去,最终总操作数为 Count=n^2+(n-1)^2+\cdots+1^2= \frac{1}{3}n^3

同时,对于右侧的常数向量 b ,总共需要进行 n^2 次操作.


Transposes and Permutations – 转置和置换

对于3维矩阵来说,其置换矩阵有限,如下列举(即互换单位阵各行的所有可能情况),共有 6P ,并且 P^{-1}=P^T :

\begin{bmatrix}1&0&0\0&1&0\0&0&1\end{bmatrix}, \begin{bmatrix}0&1&0\1&0&0\0&0&1\end{bmatrix},\begin{bmatrix}0&0&1\0&1&0\1&0&0\end{bmatrix},\begin{bmatrix}1&0&0\0&0&1\0&1&0\end{bmatrix},\begin{bmatrix}0&1&0\0&0&1\1&0&0\end{bmatrix},\begin{bmatrix}0&0&1\1&0&0\0&1&0\end{bmatrix}

发表评论

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据