第五章--矩阵分解优秀PPT.ppt

《第五章--矩阵分解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第五章--矩阵分解优秀PPT.ppt（62页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 本节介绍矩阵的本节介绍矩阵的LULU分解。分解。LULU分解可用分解可用于求行列式、逆矩阵、解线性方程组等。于求行列式、逆矩阵、解线性方程组等。5.1 5.1 矩阵的矩阵的LULU分解分解 A A左乘左乘E E，即是对，即是对A A作相应的初等行作相应的初等行变换变换.若用若用GaussGauss消去法将矩阵消去法将矩阵A A转化成转化成一个阶梯形矩阵一个阶梯形矩阵U U，相应的初等变换对，相应的初等变换对应的矩阵为应的矩阵为 ，则，则定理定理5.1.15.1.1设设A A是是 的矩阵，则存在置的矩阵，则存在置换矩阵换矩阵P P使得使得 其中其中L L是是 单位下三角阵，单位下三角阵，U U

2、是是 的的阶梯形矩阵。阶梯形矩阵。定义定义5.1.15.1.1 设设A A是是 的矩阵，如果的矩阵，如果A A（或（或A A的某个排列的某个排列PAPA）可分解为）可分解为 (或或 其中其中L L是单位下三角阵是单位下三角阵,U,U是阶梯是阶梯形矩阵，则称此分解为形矩阵，则称此分解为A A的的DoolittleDoolittle分解。分解。如果如果A(A(或或PA)PA)可分解为可分解为 (或或其中其中L L是下三角矩阵，是下三角矩阵，U U是非零对角元为是非零对角元为1 1的阶梯形矩阵的阶梯形矩阵 ，则此称分解为，则此称分解为A A的的CroutCrout分解。分解。例例 5.1.3 5.1

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

4、有些些时时候候，线线性性方方程程组组的的系系数数矩矩阵阵不不变变而而右右端端项项发发生生了了变变化化，若若此此时时已已经经得得到到了了系系数数矩矩阵阵LULU的的分分解解，则则当当右右端端项项发发生生变变化化时时，只只需需求求解解两两个个三三角角方方程程组组即即可可（,），而而不不必必重重新新进进行行GaussGauss消消去去，这这样样就就可可大大大大节节省省计计算算量。量。若若 是是 的精确解，则的精确解，则 即即 是是 的精确解，从而达到改进的精确解，从而达到改进解的目的。当然很可能还存在误差，得到解的目的。当然很可能还存在误差，得到的是的是 ，而不是，而不是 。此时设。此时设 ，解线性

5、方程组，解线性方程组 ，得到，得到 ，将，将 的解改进为的解改进为 。如此继续下去，可以证明，只要如此继续下去，可以证明，只要condcond（A A）不是太大，序列不是太大，序列 最终会收敛最终会收敛到到 的解，通常只需迭代几步就可以得的解，通常只需迭代几步就可以得到很精确的解。到很精确的解。5.2 QR5.2 QR分解分解 QR QR分解在解决最小二乘问题，特征值的分解在解决最小二乘问题，特征值的计算等方面有特别重要的应用。计算等方面有特别重要的应用。5.2.1 Householder5.2.1 Householder变换变换 在在平平面面解解析析几几何何中中，将将向向量量x x映映射射为

6、为关关于于x x轴轴对对称称的的向向量量y y的的变变换换称称为为关关于于x x轴轴的的镜镜像变换（见图像变换（见图5.2.15.2.1）。设）。设 ，则，则其中其中 ,H ,H是正交矩阵，且是正交矩阵，且detH=-1detH=-1图（图（5.2.1 5.2.1）图（图（5.2.25.2.2）定义定义5.2.15.2.1 设单位列向量设单位列向量 ，称，称矩阵矩阵为为HouseholderHouseholder矩阵，称矩阵，称HouseholderHouseholder矩阵矩阵确定的线性变换为确定的线性变换为Householder Householder 变换。变换。若若u u不是单位向量，

7、则定义不是单位向量，则定义为为HouseholderHouseholder矩阵，对应的变换称为矩阵，对应的变换称为HouseholderHouseholder变换。变换。HouseholderHouseholder变变换换将将向向量量x x映映为为关关于于“与与u u垂垂直直的的子子空空间间 ”对称的向量对称的向量(见图见图5.2.3)5.2.3)图图 5.2.3 5.2.3HouseholderHouseholder矩阵具有如下的性质：矩阵具有如下的性质：(1)(1)（H H是是HermitHermit矩阵）矩阵）(2)(2)（H H是酉矩阵）是酉矩阵）(3)(3)(4)(4)（H H是自逆

8、矩阵）是自逆矩阵）(5)(5)定理定理5.2.15.2.1 设设 是单位列向量，则对是单位列向量，则对 中中的的任任意意向向量量x x，都都存存在在HouseholderHouseholder矩矩阵阵使使得得 ，其其中中 ，且且 为为实实数。数。5.2.2 5.2.2 矩阵的矩阵的QRQR分解分解 下面我们探讨如何利用下面我们探讨如何利用HouseholderHouseholder变变换将矩阵化为上三角矩阵。我们以换将矩阵化为上三角矩阵。我们以n=3n=3的的情形起先探讨情形起先探讨.设设由例由例5.2.15.2.1知存在知存在HouseholderHouseholder矩阵矩阵 使得使得其中

9、其中此时此时接下来可构造接下来可构造H H使得使得其中其中令令 由矩阵分块乘法可知由矩阵分块乘法可知记记 ,则则由于由于 是酉矩阵，则是酉矩阵，则 和和Q Q都是都是酉矩阵。酉矩阵。定理定理5.2.25.2.2 设设 ，则存在酉矩阵，则存在酉矩阵Q Q及及上三角矩阵上三角矩阵R R，使，使 定义定义5.2.25.2.2 设设 ，如果存在，如果存在n n阶酉矩阶酉矩阵阵Q Q和和n n阶上三角矩阵阶上三角矩阵R R，使得，使得 ,则称此分解为则称此分解为A A的的QRQR分解分解(或酉三角分解或酉三角分解)。当当 时称为时称为A A的正交三角分解。的正交三角分解。定理定理5.2.35.2.3 设

10、设 ，则存在酉矩阵，则存在酉矩阵 使得使得 ，其中，其中 是是 阶梯型矩阵。阶梯型矩阵。5.2.3 QR5.2.3 QR分解的应用分解的应用 QR QR分解可用于求解线性方程组分解可用于求解线性方程组 的最小二乘解的最小二乘解.例如例如要求要求 ，使得方程组，使得方程组 5.3.1 5.3.1 奇异值分解奇异值分解 5.3 5.3 奇异值分解奇异值分解 设设A A是是 的非奇异矩阵，由于的非奇异矩阵，由于 是是HermiteHermite矩阵，则由矩阵，则由SchurSchur分解定理知存分解定理知存在酉矩阵在酉矩阵 ，使得，使得 ，其中，其中是是 的特征值。的特征值。由上述分析可知由上述分析

11、可知AVAV的各列是相互正交的，的各列是相互正交的，且且 令令则则因此因此U U是酉矩阵。是酉矩阵。由于由于其中其中 ，于是有，于是有 则称则称 为为A A的奇异值。的奇异值。定定义义5.3.15.3.1 设设A A是是 的的矩矩阵阵，的的特特征征值为值为定理定理 5.3.1 5.3.1 设设A A是是 的矩阵，的矩阵，rank(A)=r,rank(A)=r,则则（1 1）存在酉矩阵）存在酉矩阵 ,使得使得其中其中是是A A的全部非零奇异值。的全部非零奇异值。其中其中(2)(2)（若（若A A可逆）可逆）；定理定理 5.3.2 5.3.2 设设A A是是 的矩阵，其奇异值的矩阵，其奇异值分解为

12、分解为 ，则，则(1)(1)（最大的奇异值）；（最大的奇异值）；(3)(3)。5.3.25.3.2奇异值分解的应用奇异值分解的应用 (1)(1)计算线性方程组的最小二乘解计算线性方程组的最小二乘解 设设A A是是 矩阵，矩阵，b b是是n n维列向量，考维列向量，考虑如下线性方程组虑如下线性方程组 在在很很多多情情形形下下，上上述述方方程程组组没没有有解解，因因此此，我我们们计计算算其其最最小小二二乘乘解解，即即求求x x使使得得 最小。最小。其中其中U,VU,V是酉矩阵。可以证明是酉矩阵。可以证明2-2-范数具范数具有酉不变性，因此有酉不变性，因此 设设 的奇异值分解为的奇异值分解为 ，由此

13、可知由此可知 的最小二乘解即是的最小二乘解即是 的最小二乘解。的最小二乘解。令令则则即即 要使上述方程组的左右两端尽可能相要使上述方程组的左右两端尽可能相等，只需令等，只需令 即可（其实即可（其实 可以是任意数，可以是任意数，它们是自由变量）。那么它们是自由变量）。那么 是线性方程组是线性方程组 的最小二乘解。的最小二乘解。(2)(2)计算矩阵的值空间和零空间计算矩阵的值空间和零空间 设设A A是是 的矩阵，的矩阵，A A的奇异值分解的奇异值分解 为为 由于由于其中其中r r是矩阵是矩阵A A的秩，从而的秩，从而 因此因此(3)(3)数字图像靠近数字图像靠近 设设A A的奇异值分解为的奇异值分

14、解为 ，则，则A A可表示为可表示为 与与A A相距最近的秩为相距最近的秩为k k的矩阵就是将的矩阵就是将上式截断取前上式截断取前k k项项需需k(m+n+1)k(m+n+1)个存储单元个存储单元因因此此我我们们可可以以合合理理地地选选择择k k，使使得得 尽尽量量接接近近于于A A，同同时时存存储储量量又又相相对对较较小小，便便于于储存和传输。储存和传输。图图5.3.25.3.2展示了截取不同前展示了截取不同前k k项的靠近效果。项的靠近效果。原始照片的灰度矩阵是一个原始照片的灰度矩阵是一个320*240320*240的矩阵，的矩阵，从图中可看出取从图中可看出取k=50k=50的靠近效果就已

15、经很的靠近效果就已经很好了。它须要的存储单元是好了。它须要的存储单元是50*(320+240+1)50*(320+240+1)，大大削减了存储量。，大大削减了存储量。（a a）原始照片）原始照片 （320240320240）(b)rank10 靠近靠近（c c）rank30 rank30 靠近靠近(d)rank50(d)rank50 靠近靠近5.4 5.4 矩阵的满秩分解矩阵的满秩分解 定义定义5.4.1 5.4.1 设设A A是是 的矩阵的矩阵 ，rank(A)=r0,rank(A)=r0,如果存在如果存在 的列满秩的列满秩矩阵矩阵F F及及 的行满秩矩阵的行满秩矩阵G G使得使得 则称此分

16、解为矩阵则称此分解为矩阵A A的满秩分解。的满秩分解。定理定理5.4.15.4.1 任意任意 的矩阵的矩阵A A 都有满秩分解。都有满秩分解。(1)H(1)H的前的前r r行中每一行至少含有一个非零行中每一行至少含有一个非零元素，且每行第一个非零元素是元素，且每行第一个非零元素是1 1，而后，而后m-rm-r行元素均为行元素均为0 0；定义定义5.4.25.4.2 设设H H是是 的矩阵，的矩阵，Rank(H)=r Rank(H)=r，满足，满足 则称则称H H为为A A的的HermiteHermite标准形。标准形。(2)(2)设设H H中第中第i i行的第一个非零元素行的第一个非零元素1 1位于位于 第第 列，有列，有(3)(3)H H的第的第 列构成列构成m m阶单位矩阵阶单位矩阵I I(4)(4)的前的前r r列；列；定理定理5.4.25.4.2 设设A A是是 的矩阵，的矩阵，rank(A)=r0,rank(A)=r0,其其HermiteHermite标准形为标准形为H H。则在则在A A的满秩分解中，可取的满秩分解中，可取F F为由为由A A 的的 列构成的列构成的 的矩阵，的矩阵，G G为为H H的前的前r r行构成行构成 的矩阵的矩阵.