第四章 （二）

1. LU分解

在求解线性方程组$Ax=b$时，如果能够通过正交变换，将$m\times n$矩阵$A$分解为$A=LU$，其中，$L$为$m\times m$单位下三角矩阵(对角元素为1的下三角矩阵);并且$U$是$A$的$m\times n$阶梯型矩阵。这样一来，线性方程组$Ax=b$即变为$LUx=b$，它可以简单求解。
为了求解线性方程组$LUx=b$，令$y=Ux$。于是方程组变为$Ly=b$，解之得$y$。再求解$Ux=y$即得方程组的解向量。于是，通过矩阵的$LU$分解，线性矩阵方程$Ax=b$的求解分为两个三角矩阵方程的求解，具体算法如下:
步骤1 计算$A=LU$;
步骤2 用前向回代法求解下三角矩阵方程$Ly=b$;
步骤3 用后向回代法求解上三角矩阵方程$Ux=y$
上面的算法可以推广到线性矩阵方程$AX=B$的求解，其中，$A\in R^{n\times n}$非奇异，$B\in R^{n\times p}$。记$X=[x_1，x_2,\dots ,x_p]，B=[b_1,b_2,\dots ,b_p]$。

以下算法可用于求出未知的矩阵$X$:

其中，$J$是$n\times n$反射矩阵，即$J=[e_n,e_{n-1},\dots ,e_1]$，而$e_k$为基本向量。
因此，关键问题在于矩阵$A$的$LU$分解。

定理 LU分解
如果$A\in R^{n\times n}$非奇异，并且其$LU$分解存在的话，则$A$的$LU$分解是唯一的，且$det(A)=det(LU)=det(L)det(U)=det(U)=u_{11}{u}_{22},\dots ,u_{nn}$

算法 矩阵的LU分解的初等行变换算法
步骤1 利用初等行变换将矩阵$A$化为阶梯型矩阵$U$，即

步骤2 对单位矩阵执行与步骤1相应的初等行逆变换，得到单位下三角矩阵$L$，即

输出 $LU$分解由$A=LU$给出。

关于上述算法，有两点注意事项:
(1) 步骤2的初等行逆变换$E_i^{-1}$是步骤1对应的初等行变换$E_i$的逆变换。
(2) 若在步骤1中定义$\alpha R_p+R_q$为将第$p$行元素乘常数$\alpha$之后，加给第$q$行的初等行变换，则步骤2中相应初等行逆变换$(\alpha R_p+R_p{)}^{-1}$定义为$-\alpha R+p+R_p$

例
用LU算法求矩阵
A = [ 2 4 − 1 5 − 4 − 4 − 5 3 − 8 2 2 − 5 − 4 1 16 − 6 0 7 − 3 2 ] A=

A=⎣ ⎡​2−42−6​4−5−50​−13−47​5−81−3​−42162​⎦ ⎤​
的LU分解。

解
(1)步骤1 使用初等行变换将矩阵$A$变换为阶梯型矩阵$U$:

(2)步骤2 使用初等行逆变换将$4\times 4$单位矩阵变成单位下三角矩阵:


(3)输出 矩阵A的LU分解:

事实上，也可以利用步骤1将$A$变换为阶梯型矩阵$U$过程中的有关矩阵$A,A_1,A_2,U$的主元列构造单位下三角矩阵$L$。具体方法是:
(1)取出$A$的第1个主元所在的列(不失一般性，假定为第1列)，将其归一化(第一个元素为1)后，作为$L$的第1列。
(2)取出$A_{i-1}$的第$i$个主元及下面的同列元素构成的部分组成一个$(n-i)\times 1$向量，将其归一化后，作为$L$的第$i$列的下半部分，其中，$i=2,3,\dots ,n$。
针对上例，矩阵$A,A_1,A_2,A_3$被抽出的主元列及其归一化结果分别为

这与运用初等行逆变换的结果相同。

2. QR分解及其应用

矩阵的QR分解是在工程中应用最广泛的一种矩阵分解。先看QR分解的性质。

2.1 QR分解的性质

定理 QR分解
若$A\in R^{m\times n}$，且$m\ge n$,则存在列正交的矩阵$Q\in R^{m\times m}$和上三角矩阵$R\in R^{m\times n}$使得$A=QR$。当$m=n$时，$Q$是正交矩阵。如果$A$是非奇异的$n\times n$矩阵,则$R$的所有对角线元素均为正，并且在这种情况下$Q$和$R$二者是唯一的。若$A$是复矩阵，则$Q$和$R$取复值。

注意到$A^{T}A=(QR{)}^T(QR)=R^{T}R$，因此可以得出结论:$G=R^T$是$A^{T}A$的下三角Cholesky因子。由于这个原因，在关于估计的文献中，矩阵$R$常称为平方根滤波器(算子)。
下面的引理称为矩阵分解引理，它在矩阵的$QR$分解的应用中是一个有用的结果。

引理
若$A$和$B$是任意两个$m\times n$矩阵，则
$$A^{H}A=B^{H}B$$
当且仅当存在一个$m\times m$酉矩阵$Q$，使得
$$QA=B$$

2.2 采用修正Gram-Schmidt法的QR分解

矩阵$A$的QR分解可以利用Gram-Schmidt正交化方法实现。
Gram-Schmidt正交化方法原本是一种由$n$个向量$a_1,a_2,\dots ,a_n$构造互相正交且范数为1的向量$q_1,q_2,\dots ,q_n$的方法。将向量$a_1$标准正交化的结果取作$q_1$，即
$$R_{11}=||a_1||$$
$$q_1=q_1/R_{11})$$
然后，从$a_2$中除去与$a_1$平行的分量，再进行标准正交化，并将结果取作$q_2$，则有
$$R_{12}=q_1^H{a}_2$$
$$R_{22}=||a_2-q_1{R}_{12}||$$
$$q_2=(a_2-q_1{R}_{12})/R_{22}$$

进而，又从$a_3$除去与$a_1$和$a_2$平行的两个分量，再进行标准正交化，并使用该结果作$q_3$，即有
$$R_{13}=q_1^H{a}_3$$
$$R_{23}=q_2^H{a}_3$$
$$R_{33}=||a+3-q_1{R}_{13}-q_2{R}_{23}||$$
$$q_3=(a_3-q_1{R}_{13}-q_2{R}_{23})/R_{33}$$
如此继续，则对于$q_k(2\le k\le n)$有
$$R_{jk}=q_j^H{a}_k，1\le j\le k-1$$
$$R_{kk}=||a_k-\sum _{j=1}^{k-1}{q}_j{R}_{jk}||$$
$$q_k=(a_k-\sum _{j=1}^{k-1}{q}_j{R}_{jk})/R_{kk}$$
容易验证，$q_i$是标准正交基，即满足
$$q_i^H{q}_j={\delta }_{ij}$$
其中，${\delta }_{ij}$为Kronecker $\delta$函数。如果令$m\times n$矩阵$A$的列向量为$a_1,a_2,\dots ,a_n$，则以$q_1,q_2,\dots ,q_n$为列向量的矩阵$Q$与$A$之间有下列关系:
$$A=QR$$
又由于$q_i$组成标准正交基，所以
$$Q^{H}Q=I_n$$
将$A$和$Q$重写在同一矩阵，应用以上Gram-Schmidt正交化的方法叫做经典Gram Schmidt正交化法，其过程可以用图4.7.1说明。

Björck发现，对经典Gram-Schmidt正交化法加以修正，使上三角矩阵R的元素不是按列，而是按行计算时，舍入误差将变小。
这样一种修正方法叫做修正Gram-Schmidt正交化算法。具体说来，$a_1$的标准正交化结果取作$q_1$(这与经典Gram-Schmidt正交化法相同)，但同时需要从$a_2,a_3,\dots ,a_n$预先减去与$a_1$平行的分量，即
$$R_{11}=||a_1||，q_1=a_1/R_{11}$$
$$R_{1j}=q_1^H{a}_j，a_j^{(1)}=a_j-q_1{R}_{1j}，2\le j\le n$$
经过以上运算后，向量$a_2^{(1)},a_3^{(1)},\dots ,a_n^{(1)})$与$q_1$正交。
然后，将$a_2^{(1)}$标准正交化，并从$a_3^{(1)},a_4^{(1)},...,a_n^{(1)}$减去与$a_2^{(1)}$平行的分量，得
$$R_{22}=||a_2^{(1)}||，q_2=a_2/R_{22}$$
$$R_{2j}=q_2^H{a}_j^{(1)}，a_j^{(2)}=a_j^{(1)}-q_2{R}_{2j},3\le j\le n$$
这样构造的向量$a_3^{(2)},a_4^{(2)},\dots ,a_n^{(2)})$与$q_1,q_2$均正交。重复这一过程，就可以将$A$和$Q$重写在同一矩阵。图47.2示出了修正Gram-Schmidt正交化算法的运算过程。

为了分析误差的情况，假定$q_2$包含有少量与$q_1$平行的分量，即$q_2+ϵq_1$。应用经典Gram-Schmidt法，求$q_2$和$a_3$的内积$R_{23}$时，具体计算如下:
$$(q_2^H+ϵq_1^H)a_3=q_2^H{a}_3+ϵq_1^H{a}_3\text{\hspace{1em}(1)}$$
而在修正Gram-Schmidt法中，求$R_{23}$时计算的是$q_2$和$a_2^{(1)}=a_3-R_{13}{q}_1$的内积，即
$$(q_2^H+ϵq_1^H)(a_3-R_{13}{q}_1)=q_2^H{a}_3+ϵq_1^H{a}_3-ϵR_{13}=q_2^H{a}_3\text{\hspace{1em}(2)}$$
比较式(1)与式(2)，可以看出，经典方法比修正方法多第二项误差。尤其是当$||R_{23}||\ll |R_{13}|$时，修正Gram-Schmidt法减小误差的效果将更明显。