第五章矩阵分解精选文档.ppt

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

1、第五章矩阵分解本讲稿第一页，共六十三页 本节介绍矩阵的本节介绍矩阵的LULU分解。分解。LULU分解可用于分解可用于求行列式、逆矩阵、解线性方程组等。求行列式、逆矩阵、解线性方程组等。5.1 5.1 矩阵的矩阵的LULU分解分解本讲稿第二页，共六十三页 A A左乘左乘E E，即是对，即是对A A作相应的初等行作相应的初等行变换变换.若用若用GaussGauss消去法将矩阵消去法将矩阵A A转化成转化成一个阶梯形矩阵一个阶梯形矩阵U U，相应的初等变换对，相应的初等变换对应的矩阵为应的矩阵为 ，则，则本讲稿第三页，共六十三页本讲稿第四页，共六十三页本讲稿第五页，共六十三页定理定理5.1.15.1

2、.1设设A A是是 的矩阵，则存在置的矩阵，则存在置换矩阵换矩阵P P使得使得 其中其中L L是是 单位下三角阵，单位下三角阵，U U是是 的的阶梯形矩阵。阶梯形矩阵。本讲稿第六页，共六十三页 定义定义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是下三角矩阵，是下三角矩阵，

3、U U是非零对角元为是非零对角元为1 1的阶梯形矩阵的阶梯形矩阵 ，则此称分解为，则此称分解为A A的的CroutCrout分分解。解。例例 5.1.3 5.1.3本讲稿第七页，共六十三页例例 5.1.4 5.1.4 定理定理5.1.25.1.2设设A A是是 的正定矩阵，则的正定矩阵，则存在存在 的下三角阵的下三角阵L L使得使得 此分解称为矩阵此分解称为矩阵A A的的CholeskyCholesky分解。分解。本讲稿第八页，共六十三页5.1.2 LU5.1.2 LU分解的应用分解的应用 矩阵的矩阵的LULU分解最常应用于求解线性方分解最常应用于求解线性方程组程组 ，首先我们作分解，首先我们

4、作分解 ，然后，然后求解方程组求解方程组 ，求解过程分两步进行，求解过程分两步进行：本讲稿第九页，共六十三页(1)(1)首先解线性方程组首先解线性方程组 ，可得，可得 .例例 5.1.5 5.1.5例例 5.1.6 5.1.6例例 5.1.7 5.1.7(2)(2)接着计算原方程组的解接着计算原方程组的解 ，即，即求解方程组求解方程组 。本讲稿第十页，共六十三页 有有些些时时候候，线线性性方方程程组组的的系系数数矩矩阵阵不不变变而而右右端端项项发发生生了了变变化化，若若此此时时已已经经得得到到了了系系数数矩矩阵阵LULU的的分分解解，则则当当右右端端项项发发生生变变化化时时，只只需需求求解解两

5、两个个三三角角方方程程组组即即可可（,），而而不不必必重重新新进进行行GaussGauss消消去去，这这样样就就可可大大大大节节省省计计算算量。量。本讲稿第十一页，共六十三页若若 是是 的精确解，则的精确解，则 即即 是是 的精确解，从而达到改进的精确解，从而达到改进解的目的。当然很可能还存在误差，得到解的目的。当然很可能还存在误差，得到的是的是 ，而不是，而不是 。此时设。此时设 ，解线性方程组，解线性方程组 ，得到，得到 ，将，将 的解改进为的解改进为 。本讲稿第十二页，共六十三页如此继续下去，可以证明，只要如此继续下去，可以证明，只要condcond（A A）不是太大，序列不是太大，序列

6、 最终会收敛最终会收敛到到 的解，通常只需迭代几步就可以得的解，通常只需迭代几步就可以得到很精确的解。到很精确的解。本讲稿第十三页，共六十三页5.2 QR5.2 QR分解分解 QR QR分解在解决最小二乘问题，特征值的分解在解决最小二乘问题，特征值的计算等方面有十分重要的应用。计算等方面有十分重要的应用。本讲稿第十四页，共六十三页5.2.1 Householder5.2.1 Householder变换变换 在在平平面面解解析析几几何何中中，将将向向量量x x映映射射为为关关于于x x轴轴对对称称的的向向量量y y的的变变换换称称为为关关于于x x轴轴的的镜镜像变换（见图像变换（见图5.2.15

7、.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不是单位向量，则定义不是单位向量，则

8、定义为为HouseholderHouseholder矩阵，对应的变换称为矩阵，对应的变换称为HouseholderHouseholder变换。变换。HouseholderHouseholder变变换换将将向向量量x x映映为为关关于于“与与u u垂垂直直的的子子空空间间 ”对称的向量对称的向量(见图见图5.2.3)5.2.3)本讲稿第十九页，共六十三页图图 5.2.3 5.2.3本讲稿第二十页，共六十三页HouseholderHouseholder矩阵具有如下的性质：矩阵具有如下的性质：(1)(1)（H H是是HermitHermit矩阵）矩阵）(2)(2)（H H是酉矩阵）是酉矩阵）(3)(

9、3)(4)(4)（H H是自逆矩阵）是自逆矩阵）(5)(5)本讲稿第二十一页，共六十三页例例 5.2.1 5.2.1例例 5.2.2 5.2.2定理定理5.2.15.2.1 设设 是单位列向量，则对是单位列向量，则对 中中的的任任意意向向量量x x，都都存存在在HouseholderHouseholder矩矩阵阵使使得得 ，其其中中 ，且且 为为实实数。数。本讲稿第二十二页，共六十三页5.2.2 5.2.2 矩阵的矩阵的QRQR分解分解 下面我们探讨如何利用下面我们探讨如何利用HouseholderHouseholder变变换将矩阵化为上三角矩阵。我们以换将矩阵化为上三角矩阵。我们以n=3n=

10、3的情的情形开始讨论形开始讨论.设设本讲稿第二十三页，共六十三页由例由例5.2.15.2.1知存在知存在HouseholderHouseholder矩阵矩阵 使得使得其中其中本讲稿第二十四页，共六十三页此时此时接下来可构造接下来可构造H H使得使得其中其中本讲稿第二十五页，共六十三页令令 由矩阵分块乘法可知由矩阵分块乘法可知本讲稿第二十六页，共六十三页记记 ,则则由于由于 是酉矩阵，则是酉矩阵，则 和和Q Q都是都是酉矩阵。酉矩阵。本讲稿第二十七页，共六十三页定理定理5.2.25.2.2 设设 ，则存在酉矩阵，则存在酉矩阵Q Q及及上三角矩阵上三角矩阵R R，使，使 本讲稿第二十八页，共六十三

11、页例例 5.2.3 5.2.3定义定义5.2.25.2.2 设设 ，如果存在，如果存在n n阶酉矩阶酉矩阵阵Q Q和和n n阶上三角矩阵阶上三角矩阵R R，使得，使得 ,则称此分解为则称此分解为A A的的QRQR分解分解(或酉三角分解或酉三角分解)。当当 时称为时称为A A的正交三角分解。的正交三角分解。本讲稿第二十九页，共六十三页例例 5.2.4 5.2.4定理定理5.2.35.2.3 设设 ，则存在酉矩阵，则存在酉矩阵 使得使得 ，其中，其中 是是 阶梯型矩阵。阶梯型矩阵。本讲稿第三十页，共六十三页5.2.3 QR5.2.3 QR分解的应用分解的应用 QR QR分解可用于求解线性方程组分解

12、可用于求解线性方程组 的最小二乘解的最小二乘解.本讲稿第三十一页，共六十三页例如例如要求要求 ，使得方程组，使得方程组 本讲稿第三十二页，共六十三页5.3.1 5.3.1 奇异值分解奇异值分解 5.3 5.3 奇异值分解奇异值分解 设设A A是是 的非奇异矩阵，由于的非奇异矩阵，由于 是是HermiteHermite矩阵，则由矩阵，则由SchurSchur分解定理知存分解定理知存在酉矩阵在酉矩阵 ，使得，使得 ，其中，其中是是 的特征值。的特征值。本讲稿第三十三页，共六十三页本讲稿第三十四页，共六十三页由上述分析可知由上述分析可知AVAV的各列是相互正交的，的各列是相互正交的，且且 令令本讲稿

13、第三十五页，共六十三页则则因此因此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的全部非零奇异值。的全部非零奇异值。本讲稿第三十九页，共六十三页例例 5.3.1 5.3.1例例 5.3.2 5.3.2其中其中

14、本讲稿第四十页，共六十三页(2)(2)（若（若A A可逆）可逆）；定理定理 5.3.2 5.3.2 设设A A是是 的矩阵，其奇异值的矩阵，其奇异值分解为分解为 ，则，则(1)(1)（最大的奇异值）；（最大的奇异值）；(3)(3)。本讲稿第四十一页，共六十三页5.3.25.3.2奇异值分解的应用奇异值分解的应用 (1)(1)计算线性方程组的最小二乘解计算线性方程组的最小二乘解 设设A A是是 矩阵，矩阵，b b是是n n维列向量，考虑维列向量，考虑如下线性方程组如下线性方程组 本讲稿第四十二页，共六十三页 在在很很多多情情形形下下，上上述述方方程程组组没没有有解解，因因此此，我我们们计计算算其

15、其最最小小二二乘乘解解，即即求求x x使使得得 最小。最小。本讲稿第四十三页，共六十三页 其中其中U,VU,V是酉矩阵。可以证明是酉矩阵。可以证明2-2-范数具范数具有酉不变性，因此有酉不变性，因此 设设 的奇异值分解为的奇异值分解为 ，本讲稿第四十四页，共六十三页由此可知由此可知 的最小二乘解即是的最小二乘解即是 的最小二乘解。的最小二乘解。本讲稿第四十五页，共六十三页令令则则本讲稿第四十六页，共六十三页即即本讲稿第四十七页，共六十三页 要使上述方程组的左右两端尽可能相要使上述方程组的左右两端尽可能相等，只需令等，只需令 本讲稿第四十八页，共六十三页即可（其实即可（其实 可以是任意数，可以是

16、任意数，它们是自由变量）。那么它们是自由变量）。那么 是线性方程组是线性方程组 的最小二乘解。的最小二乘解。本讲稿第四十九页，共六十三页(2)(2)计算矩阵的值空间和零空间计算矩阵的值空间和零空间 设设A A是是 的矩阵，的矩阵，A A的奇异值分解的奇异值分解 为为 本讲稿第五十页，共六十三页由于由于本讲稿第五十一页，共六十三页其中其中r r是矩阵是矩阵A A的秩，从而的秩，从而 本讲稿第五十二页，共六十三页因此因此例例 5.3.4 5.3.4本讲稿第五十三页，共六十三页(3)(3)数字图像逼近数字图像逼近 设设A A的奇异值分解为的奇异值分解为 ，则，则A A可表示为可表示为 与与A A相距

17、最近的秩为相距最近的秩为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的逼近效果

18、就已经很好的逼近效果就已经很好了。它需要的存储单元是了。它需要的存储单元是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,如果存在如果存

19、在 的列满秩的列满秩矩阵矩阵F F及及 的行满秩矩阵的行满秩矩阵G G使得使得 则称此分解为矩阵则称此分解为矩阵A A的满秩分解。的满秩分解。本讲稿第五十九页，共六十三页例例 5.4.1 5.4.1定理定理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(

20、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.2 5.4.2 定理定理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行构成行构成 的矩阵的矩阵.本讲稿第六十三页，共六十三页