LU 分解

Some concepts

We suppose $v \in \mathbb{R}^n$ with $v_k \neq0$ .If

$\tag{3.2.3} \tau^T=[0,\cdots,0,\tau_{k+1},\cdots,\tau_n],\tau_i=\dfrac{v_i}{v_k},i=k+1,\cdots,n,$

and we difine

$M_k=I_n-\tau e_k^T,$

then

$\left.M_kv = \left[\begin{array}{cccccc}1&\cdots&0&0&\cdots&0\\\vdots&\ddots&\vdots&\vdots&&\vdots\\0&&1&0&&0\\0&&-\tau_{k+1}&1&&0\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&\cdots&-\tau_n&0&\cdots&1\end{array}\right.\right]\left[\begin{array}{c}v_1\\\vdots\\v_k\\v_{k+1}\\\vdots\\v_n\end{array}\right] = \left[\begin{array}{c}v_1\\\vdots\\v_k\\0\\\vdots\\0\end{array}\right]$

A matrix of the form $M_k = I_n - \tau e_k^T\in \mathbb{R}^{nxn}$ is a Gauss transformation if the first $k$ components of $\tau \in \mathbb{R}^n$ are zero. Such a matrix is unit lower triangular. The components of $\tau(k +1:n)$ are called multipliers. The vector $\tau$ is called the Gauss vector.

LU Factorization

If no zero pivots are encountered in (3.2.3), then Gauss transformations $M1,M_2,\cdots,M{n-1}$ are generated such that $M{n-1}\cdots M_2M_1 A = U$ is upper triangular. It is easy to check that if $M_k = I_n - \tau^{(k)}e_k^T$ , then its inverse is prescribed by $M{k}^{-1}=I_n+\tau^{(k)}e_k^T$ and so

$\tag{3.2.4} A=LU$

where

$\tag{3.2.5} L=M_1^{-1}\cdots M_{n-1}^{-1}$

It is clear that L is a unit lower triangular matrix because each $M_k^{-1}$ is unit lower triangular. The factorization (3.2.4) is called the LU factorization.

Theorem 3.2.1 (LU Factorization)

If $A \in \mathbb{R}^{n\times n}$ and $det(A(1:k,1:k))\neq 0$ for $k = 1:n-1$ , then there exists a unit lower triangular $L \in \mathbb{R}^{n\times n}$ and an upper triangular $U \in \mathbb{R}^{n\times n}$ such that $A = LU$. If this is the case and $A$ is nonsingular, then the factorization is unique and $det(A) = u{11}\cdots u{nn}$

存在的充要条件

矩阵 $A$ 的顺序主子阵 $A_i$ 均非奇异
$\Leftrightarrow$
矩阵 $A$ 的主元 $a_{ii}^{(i-1)}(i=1,\cdots,k)$ 均不为$0$
$\Leftrightarrow$
存在唯一的单位下三角阵 $L\in \mathbb{R}^{n\times n}$和下三角阵$U\in \mathbb{R}^{n\times n}$使得 $A=LU$

算法

第二行中的 $A(k+1:n,k)$ 就是高斯变换中的乘子。

需要进行的浮点数运算(包含加减和乘除)一共是:

$\sum_{i=1}^{n-1}[(n-i)+2(n-i)^2] =\frac{2}{3} n^3+O(n)$

全主元高斯消去

目的

为了解决两个问题

主元值较小
主元值为 $0$

初等置换矩阵

将单位矩阵$I$的第$p,q$两列交换得到的矩阵记为初等置换矩阵$I_{pq}$,即

$I_{pq}=\begin{bmatrix}1&&&&&&&\\&\ddots&&&&&&\\&&0_{pp}&&&1_{pq}&&&\\&&&\ddots&&&&\\&&&1_{qp}&&0_{qq}&&&\\&&&&&\ddots&&\\&&&&&&1\end{bmatrix}$

有如下的性质:

$I{pq}=I{pq}^T=I_{qp}^{-1}$
$\det{(I_{pq})}=-1$

定理

设 $A \in \mathbb{R}^{n\times n}$ ,则存在排列矩阵 $P,Q\in \mathbb{R}^{n\times n}$ ,以及单位下三角矩阵 $L \in \mathbb{L}^{n\times n}$ 和上三角矩阵 $U \in \mathbb{R}^{n\times n}$ ,使得
$PAQ=LU$
且$L$ 的所有元素均满足 $|a_{ij}|<1$ ,$U$的非零对角元的个数恰好等于矩阵 $A$ 的秩。