05.矩阵理论与方法-矩阵分解剖析.ppt

《05.矩阵理论与方法-矩阵分解剖析.ppt》由会员分享，可在线阅读，更多相关《05.矩阵理论与方法-矩阵分解剖析.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 1矩阵理论与方法矩阵理论与方法第第4 4章章 矩阵分解矩阵分解庄庄 伯伯 金金BB2 2主要内容n矩阵的矩阵的LULU分解分解n矩阵的矩阵的QRQR分解分解n矩阵的满秩分解矩阵的满秩分解n矩阵的奇异值分解矩阵的奇异值分解3 3线性方程组中的高斯消元法n记线性方程组记线性方程组n若令若令 ，则有，则有n可利用高斯消元法求解线性方程组可利用高斯消元法求解线性方程组4 4高斯自然顺序主元素消元法n考虑一种理想情况，在消元过程中，矩阵对角元素始终不为零，则可以按考虑一种理想情况，在消元过程中，矩阵对角元素始终不为零，则可以按对角元素的自然顺序进行消元，即不用进行行或列交换。对角元素的自然顺序进行消

2、元，即不用进行行或列交换。n记记 ，其中，其中 n令令 ，构造，构造FrobeniusFrobenius矩阵矩阵5 5高斯自然顺序主元素消元法n可得：可得：n因为因为n由最初的假设，应有由最初的假设，应有 ，即，即 的二阶顺序主子式的二阶顺序主子式 。n令令 ，构造，构造FrobeniusFrobenius矩阵矩阵6 6高斯自然顺序主元素消元法n可得：可得：n依次类推，可得依次类推，可得 的的 阶顺序主子式阶顺序主子式 ，以及相应的以及相应的FrobeniusFrobenius矩阵和上三角矩阵。矩阵和上三角矩阵。7 7高斯自然顺序主元素消元法n令令n则有则有8 8矩阵的三角分解n定义：若定义：

3、若 阶矩阵阶矩阵 能够分解为一个下三角矩阵能够分解为一个下三角矩阵 和一个上三角矩阵和一个上三角矩阵 的的乘积，则称其为三角分解或乘积，则称其为三角分解或 LULU分解。分解。n注：矩阵注：矩阵 的的LULU分解不唯一。分解不唯一。n定义：若定义：若 阶矩阵阶矩阵 能够分解为能够分解为 ，其中，其中 为单位下三角矩阵，为单位下三角矩阵，为单位上三角矩阵，为单位上三角矩阵，为对角矩阵，则称其为矩阵的为对角矩阵，则称其为矩阵的LDULDU分解。分解。n定理：定理：阶矩阵阶矩阵 存在唯一的存在唯一的LDULDU分解的充要条件是分解的充要条件是 的前的前 阶顺序主子阶顺序主子式式 。且有。且有n推论：

4、设推论：设 是是 阶非奇异矩阵，阶非奇异矩阵，有三角分解有三角分解 的充要条件是的充要条件是 的顺的顺序主子式序主子式 。9 9矩阵的三角分解n例：求矩阵例：求矩阵 的的LDULDU分解。分解。1010矩阵的CROUT分解算法n定义：若定义：若 阶矩阵阶矩阵 存在分解存在分解 ，令，令 ，则称，则称 为矩阵为矩阵的的CroutCrout分解。分解。n记记n对比矩阵等式对比矩阵等式 两边的元素，可递推得到两边的元素，可递推得到 中各项元素。中各项元素。n第第1 1列列n第第1 1行行n第第 列列1111矩阵的CROUT分解算法n第第 行行 n例：求矩阵例：求矩阵 的的CroutCrout分解。分

5、解。n矩阵矩阵 的的CroutCrout分解中，可将两矩阵分解中，可将两矩阵 合并写在同一个矩阵中，即合并写在同一个矩阵中，即1212矩阵的CROUT分解算法n矩阵矩阵 的的CroutCrout分解的迭代实现分解的迭代实现1.1.计算计算L L矩阵矩阵第第1 1列列元素元素2.2.计算计算U U矩阵第矩阵第1 1行元素行元素3.3.计算计算L L矩阵矩阵第第2 2列列元素元素4.4.计算计算U U矩阵第矩阵第2 2行元素行元素5.5.计算计算L L矩阵矩阵第第3 3列列元素元素6.6.计算计算U U矩阵第矩阵第3 3行元素行元素7.7.计算计算L L矩阵矩阵第第4 4列列元素元素8.8.计算计

6、算U U矩阵第矩阵第4 4行元行元素素1313矩阵的Doolittle分解算法n定义：若定义：若 阶矩阵阶矩阵 存在分解存在分解 ，令，令 ，则称，则称 为矩为矩阵的阵的DoolittleDoolittle分解。分解。nDoolittleDoolittle分解算法与分解算法与CroutCrout分解算法类似，只是将其中的行和列的计算顺分解算法类似，只是将其中的行和列的计算顺序和公式对调。序和公式对调。1414矩阵的三角分解n矩阵矩阵 的的LDULDU分解和分解和LULU分解都需要分解都需要 满足前满足前 阶顺序主子式非零。若不阶顺序主子式非零。若不满足该条件，则可对满足该条件，则可对 进行初等

7、行（列）变换，使之满足条件。进行初等行（列）变换，使之满足条件。n定理：设定理：设 是是 阶非奇异矩阵，则存在置换矩阵阶非奇异矩阵，则存在置换矩阵 ，使得，使得 的的 个顺序个顺序主子式非零。主子式非零。n推论：设推论：设 是是 阶非奇异矩阵，则存在置换矩阵阶非奇异矩阵，则存在置换矩阵 ，使得，使得 其中其中 为单位下三角矩阵，为单位下三角矩阵，为上三角矩阵，为上三角矩阵，为对角矩阵，而为对角矩阵，而 为单为单位上三角矩阵。位上三角矩阵。1515Givens矩阵与Givens变换n定义：设实数定义：设实数 满足满足 ，称，称 为为GivensGivens矩阵（初等旋转矩阵），也可记作矩阵（初等

8、旋转矩阵），也可记作 。由。由GivensGivens矩阵矩阵确定的线性变换称为确定的线性变换称为GivensGivens变换（初等旋转变换）。变换（初等旋转变换）。n注：存在角度注：存在角度 ，使得，使得 。1616Givens矩阵与Givens变换n性质：性质：GivensGivens矩阵是正交矩阵，且满足：矩阵是正交矩阵，且满足：n1.1.n2.2.n性质：设性质：设 ，则有，则有 当当 时，取时，取 则有则有 。1717Givens矩阵与Givens变换n定理：设定理：设 ，则存在有限个，则存在有限个GivensGivens矩阵的乘积，记作矩阵的乘积，记作 ，使得使得 。n推论：设任意

9、非零列向量推论：设任意非零列向量 和单位列向量和单位列向量 ，则存在有限个，则存在有限个GivensGivens矩阵的矩阵的乘积乘积 ，使得，使得 。n例：设例：设 ，用，用GivensGivens变换将变换将 转换为与转换为与 同方向的向量；用同方向的向量；用GivensGivens变换将变换将 转换为与转换为与 同方向的向量。同方向的向量。1818Householder矩阵与Householder变换n定义：设单位列向量定义：设单位列向量 ，称矩阵，称矩阵 为为HouseHolderHouseHolder矩阵（初等反射矩阵），由矩阵（初等反射矩阵），由HouseholderHousehol

10、der矩阵确定的线性变矩阵确定的线性变换称为换称为HouseholderHouseholder变换（初等反射变换）。变换（初等反射变换）。n注：注：HouseholderHouseholder变换将列向量变换将列向量 映射为关于映射为关于“与与 正交的正交的 维超平面空维超平面空间间”对称的向量对称的向量 。n性质：性质：n1.1.n2.2.n3.3.n4.4.n5.5.1919Householder矩阵与Householder变换n定理：设任意非零列向量定理：设任意非零列向量 和单位列向量和单位列向量 ，则存在，则存在HouseholderHouseholder矩阵矩阵 ，使得，使得 。n例

11、：设例：设 ，用，用HouseholderHouseholder变换将变换将 转化为与转化为与 同方向的向量。同方向的向量。n定理：定理：GivensGivens矩阵是两个矩阵是两个HouseholderHouseholder矩阵的乘积。矩阵的乘积。2020矩阵的QR（正交三角）分解n定义：如果实（复）非奇异矩阵定义：如果实（复）非奇异矩阵 能够化成正交（酉）矩阵能够化成正交（酉）矩阵 与实（复）与实（复）非奇异上三角矩阵非奇异上三角矩阵 的乘积，即的乘积，即 则称则称 为为 的的QRQR分解。分解。n定理：设定理：设 是是 阶实（复）非奇异矩阵，则阶实（复）非奇异矩阵，则 存在存在QRQR分

12、解分解 ，且除，且除去一个对角元素的绝对值（模）为去一个对角元素的绝对值（模）为1 1的对角矩阵因子外，的对角矩阵因子外，QRQR分解式唯一。分解式唯一。n定理：设定理：设 是是 实（复）矩阵，且其实（复）矩阵，且其 个列向量线性无关，则个列向量线性无关，则 有分解有分解 其中其中 是是 实（复）矩阵，且满足实（复）矩阵，且满足 ，是是 阶实阶实（复）非奇异上三角矩阵。该分解除去相差一个对角元素的绝对值（模）（复）非奇异上三角矩阵。该分解除去相差一个对角元素的绝对值（模）为为1 1的对角矩阵因子外是唯一的。的对角矩阵因子外是唯一的。2121矩阵的QR（正交三角）分解n定理：任何实非奇异矩阵可通

13、过左连乘定理：任何实非奇异矩阵可通过左连乘GivensGivens矩阵转化为非奇异上三角矩矩阵转化为非奇异上三角矩阵。（阵。（QRQR分解的分解的GivensGivens方法）方法）n注：复数矩阵也存在相应的复初等旋转矩阵和相应的结论。注：复数矩阵也存在相应的复初等旋转矩阵和相应的结论。n定理：任何实非奇异矩阵可通过左连乘定理：任何实非奇异矩阵可通过左连乘HouseholderHouseholder矩阵转化为非奇异上三矩阵转化为非奇异上三角矩阵。（角矩阵。（QRQR分解的分解的HouseholderHouseholder方法）方法）n例：设矩阵例：设矩阵 ，用各种方法求矩阵的，用各种方法求矩阵

14、的QRQR分解分解2222Hessenberg矩阵n定义：若矩阵定义：若矩阵 的元素满足的元素满足 ，即，即 则称则称 为上为上HessenbergHessenberg矩阵。相应的，若矩阵矩阵。相应的，若矩阵 满足满足 ，则，则称称 为下为下HessenbergHessenberg矩阵。若矩阵矩阵。若矩阵 既是上既是上HessenbergHessenberg矩阵又是下矩阵又是下HessenbergHessenberg矩阵，则称矩阵，则称 为三对角矩阵。为三对角矩阵。2323矩阵与Hessenberg矩阵的正交相似n定理：任何实方阵定理：任何实方阵 都可以通过初等旋转变换正交相似于上都可以通过初

15、等旋转变换正交相似于上HessenbergHessenberg矩矩阵。阵。n推论：任何实方阵推论：任何实方阵 都可以通过初等旋转变换正交相似于下都可以通过初等旋转变换正交相似于下HessenbergHessenberg矩矩阵。阵。n定理：任何实方阵定理：任何实方阵 都可以通过初等反射变换正交相似于上都可以通过初等反射变换正交相似于上HessenbergHessenberg矩矩阵。阵。n推论：任何实方阵推论：任何实方阵 都可以通过初等反射变换正交相似于下都可以通过初等反射变换正交相似于下HessenbergHessenberg矩矩阵。阵。n推论：任何实对称方阵推论：任何实对称方阵 都可以通过初等

16、旋转变换（初等反射变换）正交都可以通过初等旋转变换（初等反射变换）正交相似于实对称三对角矩阵。相似于实对称三对角矩阵。2424矩阵与Hessenberg矩阵的正交相似n例：将实对称矩阵例：将实对称矩阵 正交相似于三对角矩阵。正交相似于三对角矩阵。2525矩阵的满秩分解n定义：设定义：设 ，如果存在矩阵，如果存在矩阵 ，使得，使得 则称则称 为矩阵为矩阵 的满秩分解。的满秩分解。n定理：设定理：设 ，则，则 有满秩分解有满秩分解 。n例：求矩阵例：求矩阵 的满秩分解的满秩分解2626Hermite标准形n定义：设定义：设 ，且满足：，且满足：n1.1.的前的前 行中，每一行至少含一个非零元素，且

17、第一个非零元素是行中，每一行至少含一个非零元素，且第一个非零元素是1 1，而后，而后 行元素均为零。行元素均为零。n2.2.若若 中第中第 行的第一个非零元素行的第一个非零元素1 1在第在第 列列 ，则，则 。n3.3.中的中的 列为单位矩阵列为单位矩阵 的前的前 列。列。则称则称 为为HermiteHermite标准形。标准形。n例：例：n结论：任意非零矩阵结论：任意非零矩阵 可通过初等行变换化为可通过初等行变换化为HermiteHermite标准形标准形 ，且，且 的前的前 行线性无关。行线性无关。2727Hermite标准形n定义：以定义：以 阶单位矩阵阶单位矩阵 的的 个列向量个列向量

18、 为列构成的为列构成的 阶矩阵阶矩阵 称为置换矩阵，这里称为置换矩阵，这里 是是 的一个排列。的一个排列。n定理：设定理：设 的的HermiteHermite标准形为标准形为 ，则，则 的满秩分解中，可的满秩分解中，可取取 为为 的的 列构成的列构成的 矩阵，矩阵，为为 的前的前 行构成的行构成的 矩阵。矩阵。n例：求矩阵例：求矩阵 的满秩分解。的满秩分解。2828矩阵的正交对角分解n实对称矩阵实对称矩阵 存在正交对角分解，即存在正交矩阵存在正交对角分解，即存在正交矩阵 ，满足，满足 其中其中 为矩阵为矩阵 的特征值。的特征值。n定理：设定理：设 非奇异，则存在正交矩阵非奇异，则存在正交矩阵

19、和和 ，使得，使得 其中其中 。2929矩阵的奇异值n对于复数域的矩阵对于复数域的矩阵 ，有如下结论成立：，有如下结论成立：n1.1.设设 ，则，则 是是HermiteHermite矩阵，且其特征值均是非负矩阵，且其特征值均是非负实数。实数。n2.2.。n3.3.设设 ，则，则 的充要条件是的充要条件是 。n定义：设定义：设 ，的特征值为的特征值为 则称则称 为为 的奇异值。当的奇异值。当 为零矩阵时，它的奇异值都是为零矩阵时，它的奇异值都是0 0。3030矩阵的奇异值分解n定理：设定理：设 ，则存在，则存在 阶酉矩阵阶酉矩阵 和和 阶酉矩阵阶酉矩阵 ，使得，使得 其中其中 ，而，而 为矩阵为

20、矩阵 的全部非零奇异值。的全部非零奇异值。n称称 为矩阵为矩阵 的奇异值分解。的奇异值分解。n例：求矩阵例：求矩阵 的奇异值分解。的奇异值分解。n证明：设矩阵证明：设矩阵 的奇异值分解为的奇异值分解为 ，求证：，求证：的列向量是的列向量是 的特征向量，而的特征向量，而 的的列列向量是向量是 的特征向量。的特征向量。3131矩阵的奇异值分解n定理：在矩阵定理：在矩阵 的奇异值分解中，记的奇异值分解中，记 和和 的列向量分别为的列向量分别为 和和 ，则有，则有 3232矩阵正交相抵n定义：设定义：设 ，如果存在，如果存在 阶正交矩阵阶正交矩阵 和和 阶正交矩阵阶正交矩阵 ，使，使得得 ，则称，则称

21、 和和 正交相抵。正交相抵。n注：正交相抵关系是一种等价关系。注：正交相抵关系是一种等价关系。n定理：正交相抵矩阵具有相同的奇异值。定理：正交相抵矩阵具有相同的奇异值。3333应用-数据降维n假设有一组数据假设有一组数据 ,通常自然界获取的数据在不同维之间具通常自然界获取的数据在不同维之间具备一定的相关性。备一定的相关性。n可以通过消除数据在不同维可以通过消除数据在不同维度之间的相关性，将度之间的相关性，将n n维数据维数据降到降到r r维，降低数据存储和处维，降低数据存储和处理的复杂度。理的复杂度。n如何降维？如何降维？n降降维后的数据应该保持数维后的数据应该保持数据的主要特性，尽量不丢据的

22、主要特性，尽量不丢失信息。失信息。n降维后数据不同维度间尽降维后数据不同维度间尽量不相关，保持一定的独量不相关，保持一定的独立性。立性。3434应用-数据降维n问题的本质：重新建立新的坐标体系，让能量集中。问题的本质：重新建立新的坐标体系，让能量集中。3535应用-数据降维n假设原坐标系为自然标架假设原坐标系为自然标架 ，新坐标系为，新坐标系为 ，为标准正交基。，为标准正交基。过渡矩阵为过渡矩阵为 （正交矩阵），即（正交矩阵），即n数据在新坐标系下的向量分别为数据在新坐标系下的向量分别为 ，则有，则有n数据的能量集中度以及相关性可以用协方差矩阵来描述。即令数据的能量集中度以及相关性可以用协方差矩阵来描述。即令n协方差矩阵协方差矩阵n则有则有3636应用-数据降维n令矩阵令矩阵 的奇异值分解为的奇异值分解为n则当则当 时，新坐标系可以满足数据降维的要求。时，新坐标系可以满足数据降维的要求。3737练习nP195 1P195 1、2 2、3 3、4 4nP219 1P219 1、2 2、4 4、7 7nP220 8P220 8、9 9nP225 1P225 1、2 2、3 3、4 4nP233 1P233 1nP234 2P234 2、4 4