第5章 矩阵分解

《第5章 矩阵分解》由会员分享，可在线阅读，更多相关《第5章 矩阵分解（57页珍藏版）》请在金锄头文库上搜索。

1、第第5 5章章 矩阵分解矩阵分解 5.1 5.1 矩阵的矩阵的 分解分解 本本节节介介绍绍矩矩阵阵的的 分分解解。 分分解解可可用用于于求求行行列列式式、逆逆矩矩阵阵、解解线线性性方程组等。方程组等。 首首先先回回顾顾在在线线性性代代数数中中学学的的初初等等矩阵的概念。设矩阵的概念。设 是是 的矩阵，的矩阵， 是是 的的初初等等矩矩阵阵， 左左乘乘 ，即即是是对对 作作相相应应的的初初等等行行变变换换，下下面面以以为例给出初等矩阵的形式。为例给出初等矩阵的形式。 对应的初等矩阵是对应的初等矩阵是 对应的初等矩阵是对应的初等矩阵是对应的初等矩阵是对应的初等矩阵是 初初等等矩矩阵阵都都是是非非奇奇

2、异异的的，且且它它的的逆逆即即是是它它定定义义的的初初等等变变换换的的逆逆变变换换。用上面的例子说明这一点。用上面的例子说明这一点。 的逆变换为的逆变换为 的逆变换为的逆变换为的逆变换为的逆变换为若若用用GaussGauss消消去去法法将将矩矩阵阵 转转化化成成一一个个阶阶梯梯形形矩矩阵阵 ，相相应应的的初初等等变变换换对对应的矩阵为应的矩阵为 ，则，则例例 5.1.15.1.1例例 5.1.25.1.2定理定理5.1.15.1.1设设 是是 的矩阵，则的矩阵，则存在置换矩阵存在置换矩阵 使得使得 其中其中 是是 单位下三角阵，单位下三角阵， 是是 的阶梯形矩阵。的阶梯形矩阵。 例例 5.1.

3、35.1.3定理定理5.1.25.1.2设设 是是 的对称正定的对称正定矩阵，则存在矩阵，则存在 的下三角阵的下三角阵 使得使得 此分解称为矩阵此分解称为矩阵 的的 CholeskyCholesky 分解。分解。例例 5.1.45.1.45.1.2 5.1.2 分解的应用分解的应用 矩阵的矩阵的 分解最常应用于求解线性方分解最常应用于求解线性方程组程组 ，首先我们作分解，首先我们作分解 ，然后求解方程组然后求解方程组 ，求解过程分，求解过程分两步进行：两步进行： (1) (1) 首先解线性方程组首先解线性方程组 ，可得，可得 (2) (2) 接着计算原方程组的解接着计算原方程组的解 ， 即求解

4、方程组即求解方程组 。 例例 5.1.55.1.5例例 5.1.65.1.6例例 5.1.75.1.7看看到到上上面面的的例例题题，大大家家可可能能会会产产生生疑疑问问，既既然然矩矩阵阵的的 分分解解可可由由Gauss消消去去法法得得到到，为为什什么么不不在在消消去去的的过过程程中中直直接接解解方方程程组组呢呢？为为什什么么要要先先进进行行 分分解解，然然后后再解两个三角方程组呢？再解两个三角方程组呢？ 其其原原因因是是在在实实际际工工作作中中，有有时时会会出出现现这这样样的的情情况况：线线性性方方程程组组的的系系数数矩矩阵阵不不变变而而右右端端项项发发生生了了变变化化，若若此此时时已已经经得

5、得到到了了系系数数矩矩阵阵 的的分分解解，则则当当右右端端项项发发生生变变化化时时，只只需需求求解解两两个个三三角角方方程程组组即即可可（ , , ），而而不不必必重重新新进进行行Gauss消去，这样就可大大节省计算量。消去，这样就可大大节省计算量。下面说明在应用迭代法改进线性方程组下面说明在应用迭代法改进线性方程组 的解时的解时 分解的优势。分解的优势。 设设 是满秩矩阵，是满秩矩阵， ， 是由是由数值方法得到的数值方法得到的 的解。由于舍入的解。由于舍入等原因，等原因， 不是不是 的精确解，即的精确解，即 。下面我们通过求解线性。下面我们通过求解线性方程组方程组 得到得到 来改进线性方程来

6、改进线性方程组的解。组的解。 若若 是是 的精确解，则的精确解，则 即即 是是 的的精精确确解解，从从而而达达到到改改进进解解的的目目的的。当当然然很很可可能能还还存存在在误误差差，得得 到到 的的 是是 ， 而而 不不 是是 。 此此 时时 ， 设设 ，解解线线性性方方程程组组 ，得得到到 ，将将 的解改进为的解改进为 如此继续下去，可以证明，只要如此继续下去，可以证明，只要 不不是是太太大大，序序列列 , ,最最终终会会收收敛敛到到 的的解解，通通常常只只需需迭迭代代几步就可以得到很精确的解。几步就可以得到很精确的解。 在在迭迭代代的的过过程程中中，我我们们求求解解了了如如下下一一系列方程

7、组系列方程组若若将将 分分解解成成 ，则则每每次次计计算算只只需需求求解解两两个个三三角角方方程程组组，从从而而达达到到节节省省计计算算量量的目的的目的 。例例 5.1.85.1.85.2 矩阵的矩阵的 QR 分解分解 QR分分解解在在矩矩阵阵计计算算中中占占据据相相当当重重要要的的地地位位。利利用用QR分分解解，可可以以解解决决各各种种应应用用中中（例例如如工工程程力力学学、流流体体力力学学、图图像像压压缩缩处处理理、结结构构分分析析等等）出出现现的的最最小小二二乘乘问问题题、特特征征值值问问题题等等矩矩阵阵计计算算中中的的核核心心问问题题。尤尤其其是是基基于于QR分分解解的的QR算算法法，

8、是是求求解解小小型型稠稠密密矩矩阵阵特特征征值值问问题题的的最最主主要要的的、数数值值稳稳定定的的算算法。法。定义定义5.2.1 5.2.1 设设 为单位列向量，称矩阵为单位列向量，称矩阵求求QR分解的分解的 Householder 变换变换Householder 变换变换是将向量是将向量 变换为关于变换为关于“与单位向量与单位向量 正交的正交的 维子空间维子空间”对称的向量对称的向量 的镜像变换。的镜像变换。为为Householder 矩阵矩阵（初等反射矩阵），对应（初等反射矩阵），对应的变换为的变换为Householder 变换变换（初等反射变换）（初等反射变换） Householder

9、矩阵矩阵 具有下列性质：具有下列性质：（1） 为为 Hermite矩阵，即有矩阵，即有（2） 为酉矩阵，即有为酉矩阵，即有（3） 为为对合矩阵对合矩阵，即有，即有（4） 为自逆矩阵，即有为自逆矩阵，即有（5） 的特征值为的特征值为 ( 重重) 和和 （单重）（单重）（6） 仍是仍是Householder 矩阵矩阵（5 5）证明：）证明：设设 ，则，则设有设有 则则 ，因此，因此设特征值设特征值 与与 的重数分别为的重数分别为 ，则，则解得解得（6 6）证明：）证明：设设 ，则，则显然显然因此结论成立。因此结论成立。其中其中 为标准单位向量。为标准单位向量。定理定理5.2.1 5.2.1 对任意

10、对任意 ，存在，存在 Householder 矩阵矩阵 ，使得，使得Householder变换变换后的像可以取后的像可以取 ，这在几何，这在几何上是显而易见的。从计算上讲，上是显而易见的。从计算上讲， Householder 首次意识到这意味着首次意识到这意味着Householder变换也能变换也能将将非零向量的后非零向量的后 个分量变为零个分量变为零。证明：证明：若若 ，则取与，则取与 正交的单位正交的单位列向量列向量 ，从而，从而 若若 ，令，令注意到注意到从而从而 虽然在数学上，虽然在数学上， 前的两种符号都令人满前的两种符号都令人满意。但为了数值稳定性的目的，希望向量意。但为了数值稳定

11、性的目的，希望向量 在在大小和方向上都不要太接近大小和方向上都不要太接近 ，否则，否则 就很接近零就很接近零 ，这在几何上是显然的。因此算法，这在几何上是显然的。因此算法实现时应取实现时应取 前的符号与前的符号与 的第一个分量的第一个分量 的符号相同，即的符号相同，即并可加上规定：当并可加上规定：当 时，时，例例5.2.1 用用Householder变换化向量变换化向量 与与e1共线共线解：令解：令此时此时 从而从而根据定理，可用一组根据定理，可用一组 Householder 变换将任意方阵变换将任意方阵 变换为上三角矩阵变换为上三角矩阵第一步第一步，当，当 时，存在时，存在Household

12、er 矩阵矩阵 ，使得（为方便说明，不妨取负号）使得（为方便说明，不妨取负号）如果如果 ，则，则 ，直接进行下一步。，直接进行下一步。矩阵的矩阵的QR分解分解从而从而第二步第二步，对，对 ，当，当 时，时，存在存在 Householder 矩阵矩阵 ，使得，使得使得使得即有即有如果如果 ，则，则 ，直接进行下一步。，直接进行下一步。使得使得第三步第三步，对，对 继续类似的变换，如此最多继续类似的变换，如此最多 步，也即至多可以找到步，也即至多可以找到 个矩阵个矩阵令令 ，则，则 为酉矩阵，为酉矩阵，从而上述算法确实得到从而上述算法确实得到QR分解分解例例5.2.25.2.2 利用利用House

13、holder变换将下列矩变换将下列矩阵进行阵进行QR分解：分解：对向量对向量 ，令，令解解：从而得从而得Householder 矩阵矩阵（ 实际上是平面实际上是平面 的法向量）的法向量）使得使得对向量对向量 ，令，令（ 实际上是平面实际上是平面 的法向量）的法向量）可得可得 Householder 矩阵矩阵因此取因此取从而有从而有则则特征值问题的特征值问题的QR算法算法QR算法算法是二十世纪十大算法之一，其基本是二十世纪十大算法之一，其基本思想基于思想基于QR迭代迭代: (1) 令令 ； (2) 对对 ，重复，重复 对对 做做QR分解：分解： 令令直至直至 收敛。收敛。由由 知知 ，因此，因此

14、因此迭代序列因此迭代序列 保持特征值不变保持特征值不变其中其中可以证明，在一定条件下，迭代序列可以证明，在一定条件下，迭代序列 收收敛到上三角矩阵敛到上三角矩阵 T 。这也说明这也说明QR迭代也可看成是对迭代也可看成是对 作作 Schur 分解。分解。特别地，如果特别地，如果 是是Hermite矩阵，那么上三角矩阵，那么上三角矩阵矩阵 变成对角矩阵。变成对角矩阵。由于计算成本的缘故，数值实现时一般先将矩由于计算成本的缘故，数值实现时一般先将矩阵阵 变换成上变换成上Hessenberg矩阵矩阵 (第一条次对角第一条次对角线以下均为零的矩阵线以下均为零的矩阵)，然后再使用，然后再使用QR迭代。迭代

15、。5.3 矩阵的奇异值分解矩阵的奇异值分解 从从Beltrami (1873)和和Jordan (1874)提提出出奇奇异异值值分分解解(SVD, Singular value decomposition)至至今今，SVD及及其其推推广广已已经经成成为为矩矩阵阵计计算算最最有有用用和和最最有有效效的的工工具具之之一一，在在最最小小二二乘乘问问题题、最最优优化化、统统计计分分析析、信信号号与与图图像像处处理理、系系统统理理论论与与控制等领域被广泛使用。控制等领域被广泛使用。一、从几何观测说起一、从几何观测说起 圆圆 经过变换经过变换 ，变成椭圆，变成椭圆 。圆的正交方。圆的正交方向向 变成椭圆的

16、长、短轴方向变成椭圆的长、短轴方向 假定矩阵假定矩阵 是列满秩矩阵。是列满秩矩阵。 一般地，一般地， 维空间中的维空间中的单位球面单位球面 经过变换经过变换 变成变成超椭圆超椭圆 。正交方向。正交方向 变成超椭变成超椭圆的主半轴方向圆的主半轴方向 。称。称 的的 个主个主半轴的长度半轴的长度 为为 的的奇异值奇异值， 对应的单位向量对应的单位向量 为为 的的左奇异向量左奇异向量(left singular vector)，对应的原象，对应的原象 为为 的的右奇异向量右奇异向量。相应的空间称为。相应的空间称为奇异空间奇异空间二、矩阵的奇异值分解二、矩阵的奇异值分解 前面已经指出前面已经指出：矩阵

17、形式为矩阵形式为 这里矩阵这里矩阵 是列正交矩阵，是列正交矩阵， 是酉矩阵。是酉矩阵。这样就得到这样就得到 的的约化奇异值分解约化奇异值分解 同样地，将矩阵同样地，将矩阵 扩充为扩充为 阶酉矩阵阶酉矩阵 ， 并令并令 ，则得，则得 的的完全奇异值分解完全奇异值分解定义定义1 1对任意矩阵对任意矩阵 ，矩阵，矩阵 的的非零非零奇异值奇异值 就是矩阵就是矩阵 或或 的的非零非零特征值的平方根。特征值的平方根。矩阵矩阵 在多元统计分析中称为在多元统计分析中称为协方差矩阵协方差矩阵，这说明这说明SVD会在其中被广泛使用，事实上也确实会在其中被广泛使用，事实上也确实如此。如此。定理定理1 1对任意矩阵对

18、任意矩阵 ，都存在一个完全，都存在一个完全奇异值分解奇异值分解 。并且奇异值。并且奇异值 是唯是唯一确定的。也就是一确定的。也就是任意矩阵酉等价于对角阵任意矩阵酉等价于对角阵定理定理2 2对矩阵对矩阵 ， 表示矩阵表示矩阵 的的 个个非零非零奇异值，则奇异值，则 定理定理3 3对任意矩阵对任意矩阵 ，矩阵，矩阵 的的非零非零奇异值数目为奇异值数目为 ， 为为矩阵矩阵 的的SVD分解，则分解，则 证明：证明：将将 的的SVD分解分块为分解分块为于是有于是有从而从而第二步第二步：令：令 为为 的非负对角的平方根，计算的非负对角的平方根，计算三、矩阵三、矩阵SVD分解的算法分解的算法由定理由定理4和

19、和5，任意矩阵，任意矩阵 的的SVD分解的算法为：分解的算法为：第一步第一步： 形成形成 ，并计算特征值分解，并计算特征值分解第三步第三步: 通过求通过求 的解空间的单位正交的解空间的单位正交基，得基，得 ，从而得，从而得例例 5.3.1 求下列矩阵的（完全）求下列矩阵的（完全）SVD分解：分解：解解：（1）矩阵矩阵 的特征值为的特征值为 ，对应的特征向，对应的特征向量为量为从而从而计算计算解解 ，得其基础解系为，得其基础解系为从而从而因此所求（完全）因此所求（完全）SVD为为由于是方阵，约化由于是方阵，约化SVD同上面的结果一样。同上面的结果一样。解解：（2）矩阵矩阵 的特征值为的特征值为 ，对应的特征向量为，对应的特征向量为从而从而计算计算解解 ，得其基础解系为，得其基础解系为从而从而因此所求（完全）因此所求（完全）SVD为为显然约化显然约化SVD为为