05.矩阵理论与方法-矩阵分解剖析优秀PPT

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,信息与通信工程学院 庄伯金 ,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,矩阵理论与方法,第4章 矩阵分解,庄 伯 金,Bjzhuangbupt.edu,2,主要内容,矩阵的,LU,分解,矩阵的,QR,分解,矩阵的满秩分解,矩阵的奇异值分解,3,线性方程组中的高斯消元法,记线性方程组,若令 ，则有,可利用高斯消元法求解线性方程组,4,高斯自然依次主元素消元法,考虑一种志向状况，在消元过程中，矩阵对角元素始终不为零，则可以按对角元素的自然依次进行消元，即不用进行行或列交换。,记 ，其中,令 ，构造Frobenius矩阵,5,高斯自然依次主元素消元法,可得：,因为,由最初的假设，应有 ，即 的二阶依次主子式 。,令 ，构造Frobenius矩阵,6,高斯自然依次主元素消元法,可得：,依次类推，可得 的 阶依次主子式 ，以及相应的Frobenius矩阵和上三角矩阵。,7,高斯自然依次主元素消元法,令,则有,8,矩阵的三角分解,定义：若 阶矩阵 能够分解为一个下三角矩阵 和一个上三角矩阵 的乘积，则称其为三角分解或 LU分解。,注：矩阵 的LU分解不唯一。,定义：若 阶矩阵 能够分解为 ，其中 为单位下三角矩阵，为单位上三角矩阵，为对角矩阵，则称其为矩阵的LDU分解。,定理：阶矩阵 存在唯一的LDU分解的充要条件是 的前 阶依次主子式 。且有,推论：设 是 阶非奇异矩阵，有三角分解 的充要条件是 的依次主子式 。,9,矩阵的三角分解,例：求矩阵 的,LDU,分解。,10,矩阵的,CROUT,分解算法,定义：若 阶矩阵 存在分解 ，令 ，则称 为矩阵的,Crout,分解。,记,对比矩阵等式 两边的元素，可递推得到 中各项元素。,第,1,列,第,1,行,第 列,11,矩阵的,CROUT,分解算法,第 行,例：求矩阵 的,Crout,分解。,矩阵 的,Crout,分解中，可将两矩阵 合并写在同一个矩阵中，即,12,矩阵的,CROUT,分解算法,矩阵 的,Crout,分解的迭代实现,1.,计算,L,矩阵第,1,列元素,2.,计算,U,矩阵第,1,行元素,3.,计算,L,矩阵第,2,列元素,4.,计算,U,矩阵第,2,行元素,5.,计算,L,矩阵第,3,列元素,6.,计算,U,矩阵第,3,行元素,7.,计算,L,矩阵第,4,列元素,8.,计算,U,矩阵第,4,行元素,13,矩阵的,Doolittle,分解算法,定义：若 阶矩阵 存在分解 ，令 ，则称 为矩阵的Doolittle分解。,Doolittle分解算法与Crout分解算法类似，只是将其中的行和列的计算依次和公式对调。,14,矩阵的三角分解,矩阵 的LDU分解和LU分解都须要 满足前 阶依次主子式非零。若不满足该条件，则可对 进行初等行（列）变换，使之满足条件。,定理：设 是 阶非奇异矩阵，则存在置换矩阵 ，使得 的 个依次主子式非零。,推论：设 是 阶非奇异矩阵，则存在置换矩阵 ，使得,其中 为单位下三角矩阵，为上三角矩阵，为对角矩阵，而 为单位上三角矩阵。,15,Givens,矩阵与,Givens,变换,定义：设实数 满足 ，称,为Givens矩阵（初等旋转矩阵），也可记作 。由Givens矩阵确定的线性变换称为Givens变换（初等旋转变换）。,注：存在角度 ，使得 。,16,Givens,矩阵与,Givens,变换,性质：Givens矩阵是正交矩阵，且满足：,1.,2.,性质：设 ，则有,当 时，取,则有 。,17,Givens,矩阵与,Givens,变换,定理：设 ，则存在有限个Givens矩阵的乘积，记作 ，使得 。,推论：设随意非零列向量 和单位列向量 ，则存在有限个Givens矩阵的乘积 ，使得 。,例：设 ，用Givens变换将 转换为与 同方向的向量；用Givens变换将 转换为与 同方向的向量。,18,Householder,矩阵与,Householder,变换,定义：设单位列向量 ，称矩阵,为,HouseHolder,矩阵（初等反射矩阵），由,Householder,矩阵确定的线性变换称为,Householder,变换（初等反射变换）。,注：,Householder,变换将列向量 映射为关于“与 正交的 维超平面空间”对称的向量 。,性质：,1.,2.,3.,4.,5.,19,Householder,矩阵与,Householder,变换,定理：设随意非零列向量 和单位列向量 ，则存在Householder矩阵 ，使得 。,例：设 ，用Householder变换将 转化为与 同方向的向量。,定理：Givens矩阵是两个Householder矩阵的乘积。,20,矩阵的,QR,（正交三角）分解,定义：假照实（复）非奇异矩阵 能够化成正交（酉）矩阵 与实（复）非奇异上三角矩阵 的乘积，即,则称 为 的QR分解。,定理：设 是 阶实（复）非奇异矩阵，则 存在QR分解 ，且除去一个对角元素的确定值（模）为1的对角矩阵因子外，QR分解式唯一。,定理：设 是 实（复）矩阵，且其 个列向量线性无关，则 有分解,其中 是 实（复）矩阵，且满足 ，是 阶实（复）非奇异上三角矩阵。该分解除去相差一个对角元素的确定值（模）为1的对角矩阵因子外是唯一的。,21,矩阵的,QR,（正交三角）分解,定理：任何实非奇异矩阵可通过左连乘,Givens,矩阵转化为非奇异上三角矩阵。（,QR,分解的,Givens,方法）,注：复数矩阵也存在相应的复初等旋转矩阵和相应的结论。,定理：任何实非奇异矩阵可通过左连乘,Householder,矩阵转化为非奇异上三角矩阵。（,QR,分解的,Householder,方法）,例：设矩阵 ，用各种方法求矩阵的,QR,分解,22,Hessenberg,矩阵,定义：若矩阵 的元素满足 ，即,则称 为上Hessenberg矩阵。相应的，若矩阵 满足 ，则称 为下Hessenberg矩阵。若矩阵 既是上Hessenberg矩阵又是下Hessenberg矩阵，则称 为三对角矩阵。,23,矩阵与Hessenberg矩阵的正交相像,定理：任何实方阵 都可以通过初等旋转变换正交相像于上Hessenberg矩阵。,推论：任何实方阵 都可以通过初等旋转变换正交相像于下Hessenberg矩阵。,定理：任何实方阵 都可以通过初等反射变换正交相像于上Hessenberg矩阵。,推论：任何实方阵 都可以通过初等反射变换正交相像于下Hessenberg矩阵。,推论：任何实对称方阵 都可以通过初等旋转变换（初等反射变换）正交相像于实对称三对角矩阵。,24,矩阵与Hessenberg矩阵的正交相像,例：将实对称矩阵 正交相像于三对角矩阵。,25,矩阵的满秩分解,定义：设 ，假如存在矩阵 ，使得,则称 为矩阵 的满秩分解。,定理：设 ，则 有满秩分解 。,例：求矩阵,的满秩分解,26,Hermite,标准形,定义：设 ，且满足：,1.的前 行中，每一行至少含一个非零元素，且第一个非零元素是1，而后 行元素均为零。,2.若 中第 行的第一个非零元素1在第 列 ，则 。,3.中的 列为单位矩阵 的前 列。,则称 为Hermite标准形。,例：,结论：随意非零矩阵 可通过初等行变换化为Hermite标准形 ，且 的前 行线性无关。,27,Hermite,标准形,定义：以 阶单位矩阵 的 个列向量 为列构成的 阶矩阵,称为置换矩阵，这里 是,的一个排列。,定理：设 的,Hermite,标准形为,，则 的满秩分解中，可取 为 的 列构成的 矩阵，为 的前 行构成的 矩阵。,例：求矩阵,的满秩分解。,28,矩阵的正交对角分解,实对称矩阵 存在正交对角分解，即存在正交矩阵 ，满足,其中 为矩阵 的特征值。,定理：设 非奇异，则存在正交矩阵 和 ，使得,其中 。,29,矩阵的奇异值,对于复数域的矩阵 ，有如下结论成立：,1.,设,，则 是,Hermite,矩阵，且其特征值均是非负实数。,2.,。,3.,设 ，则 的充要条件是 。,定义：设 ，的特征值为,则称 为 的奇异值。当 为零矩阵时，它的奇异值都是,0,。,30,矩阵的奇异值分解,定理：设 ，则存在 阶酉矩阵 和 阶酉矩阵 ，使得,其中 ，而 为矩阵 的全部非零奇异值。,称 为矩阵 的奇异值分解。,例：求矩阵 的奇异值分解。,证明：设矩阵 的奇异值分解为 ，求证：的列向量是 的特征向量，而 的列向量是 的特征向量。,31,矩阵的奇异值分解,定理：在矩阵 的奇异值分解中，记 和 的列向量分别为 和 ，则有,32,矩阵正交相抵,定义：设 ，假如存在 阶正交矩阵 和 阶正交矩阵 ，使得 ，则称 和 正交相抵。,注：正交相抵关系是一种等价关系。,定理：正交相抵矩阵具有相同的奇异值。,33,应用,-,数据降维,假设有一组数据 ,通常自然界获得的数据在不同维之间具备确定的相关性。,可以通过消退数据在不同维度之间的相关性，将n维数据降到r维，降低数据存储和处理的困难度。,如何降维？,降维后的数据应当保持数据的主要特性，尽量不丢失信息。,降维后数据不同维度间尽量不相关，保持确定的独立性。,34,应用,-,数据降维,问题的本质：重新建立新的坐标体系，让能量集中。,35,应用,-,数据降维,假设原坐标系为自然标架 ，新坐标系为 ，为标准正交基。过渡矩阵为 （正交矩阵），即,数据在新坐标系下的向量分别为 ，则有,数据的能量集中度以及相关性可以用协方差矩阵来描述。即令,协方差矩阵,则有,36,应用,-,数据降维,令矩阵 的奇异值分解为,则当 时，新坐标系可以满足数据降维的要求。,37,练习,P195 1,、,2,、,3,、,4,P219 1,、,2,、,4,、,7,P220 8,、,9,P225 1,、,2,、,3,、,4,P233 1,P234 2,、,4,