第五章矩阵分解PPT讲稿.ppt

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

1、第五章矩阵分解第1页，共63页，编辑于2022年，星期三 本节介绍矩阵的本节介绍矩阵的LULU分解。分解。LULU分解可用于求分解可用于求行列式、逆矩阵、解线性方程组等。行列式、逆矩阵、解线性方程组等。5.1 5.1 矩阵的矩阵的LULU分解分解第2页，共63页，编辑于2022年，星期三 A A左乘左乘E E，即是对，即是对A A作相应的初等行作相应的初等行变换变换.若用若用GaussGauss消去法将矩阵消去法将矩阵A A转化成转化成一个阶梯形矩阵一个阶梯形矩阵U U，相应的初等变换对，相应的初等变换对应的矩阵为应的矩阵为 ，则，则第3页，共63页，编辑于2022年，星期三第4页，共63页，

2、编辑于2022年，星期三第5页，共63页，编辑于2022年，星期三定理定理5.1.15.1.1设设A A是是 的矩阵，则存在置的矩阵，则存在置换矩阵换矩阵P P使得使得 其中其中L L是是 单位下三角阵，单位下三角阵，U U是是 的的阶梯形矩阵。阶梯形矩阵。第6页，共63页，编辑于2022年，星期三 定义定义5.1.15.1.1 设设A A是是 的矩阵，如果的矩阵，如果A A（或（或A A的某个排列的某个排列PAPA）可分解为）可分解为 (或或 其中其中L L是单位下三角阵是单位下三角阵,U,U是阶梯形是阶梯形矩阵，则称此分解为矩阵，则称此分解为A A的的DoolittleDoolittle分

3、解。分解。如果如果A(A(或或PA)PA)可分解为可分解为 (或或其中其中L L是下三角矩阵，是下三角矩阵，U U是非零对角元为是非零对角元为1 1的阶梯形矩阵的阶梯形矩阵 ，则此称分解为，则此称分解为A A的的CroutCrout分分解。解。例例 5.1.3 5.1.3第7页，共63页，编辑于2022年，星期三例例 5.1.4 5.1.4 定理定理5.1.25.1.2设设A A是是 的正定矩阵，则的正定矩阵，则存在存在 的下三角阵的下三角阵L L使得使得 此分解称为矩阵此分解称为矩阵A A的的CholeskyCholesky分解。分解。第8页，共63页，编辑于2022年，星期三5.1.2 L

4、U5.1.2 LU分解的应用分解的应用 矩阵的矩阵的LULU分解最常应用于求解线性方分解最常应用于求解线性方程组程组 ，首先我们作分解，首先我们作分解 ，然后，然后求解方程组求解方程组 ，求解过程分两步进行，求解过程分两步进行：第9页，共63页，编辑于2022年，星期三(1)(1)首先解线性方程组首先解线性方程组 ，可得，可得 .例例 5.1.5 5.1.5例例 5.1.6 5.1.6例例 5.1.7 5.1.7(2)(2)接着计算原方程组的解接着计算原方程组的解 ，即，即求解方程组求解方程组 。第10页，共63页，编辑于2022年，星期三 有有些些时时候候，线线性性方方程程组组的的系系数数矩

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

6、，解线性方程组 ，得到，得到 ，将，将 的解改进为的解改进为 。第12页，共63页，编辑于2022年，星期三如此继续下去，可以证明，只要如此继续下去，可以证明，只要condcond（A A）不是太大，序列不是太大，序列 最终会收敛最终会收敛到到 的解，通常只需迭代几步就可以得的解，通常只需迭代几步就可以得到很精确的解。到很精确的解。第13页，共63页，编辑于2022年，星期三5.2 QR5.2 QR分解分解 QR QR分解在解决最小二乘问题，特征值的计分解在解决最小二乘问题，特征值的计算等方面有十分重要的应用。算等方面有十分重要的应用。第14页，共63页，编辑于2022年，星期三5.2.1 H

7、ouseholder5.2.1 Householder变换变换 在在平平面面解解析析几几何何中中，将将向向量量x x映映射射为为关关于于x x轴轴对对称称的的向向量量y y的的变变换换称称为为关关于于x x轴轴的的镜镜像变换（见图像变换（见图5.2.15.2.1）。设）。设 ，则，则第15页，共63页，编辑于2022年，星期三其中其中 ,H ,H是正交矩阵，且是正交矩阵，且detH=-1detH=-1第16页，共63页，编辑于2022年，星期三图（图（5.2.1 5.2.1）图（图（5.2.25.2.2）第17页，共63页，编辑于2022年，星期三定义定义5.2.15.2.1 设单位列向量设单

8、位列向量 ，称，称矩阵矩阵为为HouseholderHouseholder矩阵，称矩阵，称HouseholderHouseholder矩阵矩阵确定的线性变换为确定的线性变换为Householder Householder 变换。变换。第18页，共63页，编辑于2022年，星期三 若若u u不是单位向量，则定义不是单位向量，则定义为为HouseholderHouseholder矩阵，对应的变换称为矩阵，对应的变换称为HouseholderHouseholder变换。变换。HouseholderHouseholder变变换换将将向向量量x x映映为为关关于于“与与u u垂垂直直的的子子空空间间 ”

9、对称的向量对称的向量(见图见图5.2.3)5.2.3)第19页，共63页，编辑于2022年，星期三图图 5.2.3 5.2.3第20页，共63页，编辑于2022年，星期三HouseholderHouseholder矩阵具有如下的性质：矩阵具有如下的性质：(1)(1)（H H是是HermitHermit矩阵）矩阵）(2)(2)（H H是酉矩阵）是酉矩阵）(3)(3)(4)(4)（H H是自逆矩阵）是自逆矩阵）(5)(5)第21页，共63页，编辑于2022年，星期三例例 5.2.1 5.2.1例例 5.2.2 5.2.2定理定理5.2.15.2.1 设设 是单位列向量，则对是单位列向量，则对 中中

10、的的任任意意向向量量x x，都都存存在在HouseholderHouseholder矩矩阵阵使使得得 ，其其中中 ，且且 为为实实数。数。第22页，共63页，编辑于2022年，星期三5.2.2 5.2.2 矩阵的矩阵的QRQR分解分解 下面我们探讨如何利用下面我们探讨如何利用HouseholderHouseholder变换将变换将矩阵化为上三角矩阵。我们以矩阵化为上三角矩阵。我们以n=3n=3的情形开始讨的情形开始讨论论.设设第23页，共63页，编辑于2022年，星期三由例由例5.2.15.2.1知存在知存在HouseholderHouseholder矩阵矩阵 使得使得其中其中第24页，共63

11、页，编辑于2022年，星期三此时此时接下来可构造接下来可构造H H使得使得其中其中第25页，共63页，编辑于2022年，星期三令令 由矩阵分块乘法可知由矩阵分块乘法可知第26页，共63页，编辑于2022年，星期三记记 ,则则由于由于 是酉矩阵，则是酉矩阵，则 和和Q Q都是都是酉矩阵。酉矩阵。第27页，共63页，编辑于2022年，星期三定理定理5.2.25.2.2 设设 ，则存在酉矩阵，则存在酉矩阵Q Q及及上三角矩阵上三角矩阵R R，使，使 第28页，共63页，编辑于2022年，星期三例例 5.2.3 5.2.3定义定义5.2.25.2.2 设设 ，如果存在，如果存在n n阶酉矩阶酉矩阵阵Q

12、 Q和和n n阶上三角矩阵阶上三角矩阵R R，使得，使得 ,则称此分解为则称此分解为A A的的QRQR分解分解(或酉三角分解或酉三角分解)。当当 时称为时称为A A的正交三角分解。的正交三角分解。第29页，共63页，编辑于2022年，星期三例例 5.2.4 5.2.4定理定理5.2.35.2.3 设设 ，则存在酉矩阵，则存在酉矩阵 使得使得 ，其中，其中 是是 阶梯型矩阵。阶梯型矩阵。第30页，共63页，编辑于2022年，星期三5.2.3 QR5.2.3 QR分解的应用分解的应用 QR QR分解可用于求解线性方程组分解可用于求解线性方程组 的最小二乘解的最小二乘解.第31页，共63页，编辑于2

13、022年，星期三例如例如要求要求 ，使得方程组，使得方程组 第32页，共63页，编辑于2022年，星期三5.3.1 5.3.1 奇异值分解奇异值分解 5.3 5.3 奇异值分解奇异值分解 设设A A是是 的非奇异矩阵，由于的非奇异矩阵，由于 是是HermiteHermite矩阵，则由矩阵，则由SchurSchur分解定理知存分解定理知存在酉矩阵在酉矩阵 ，使得，使得 ，其中，其中是是 的特征值。的特征值。第33页，共63页，编辑于2022年，星期三第34页，共63页，编辑于2022年，星期三由上述分析可知由上述分析可知AVAV的各列是相互正交的，的各列是相互正交的，且且 令令第35页，共63页

14、，编辑于2022年，星期三则则因此因此U U是酉矩阵。是酉矩阵。第36页，共63页，编辑于2022年，星期三由于由于其中其中 ，于是有，于是有 第37页，共63页，编辑于2022年，星期三则称则称 为为A A的奇异值。的奇异值。定定义义5.3.15.3.1 设设A A是是 的的矩矩阵阵，的的特特征征值为值为第38页，共63页，编辑于2022年，星期三定理定理 5.3.1 5.3.1 设设A A是是 的矩阵，的矩阵，rank(A)=r,rank(A)=r,则则（1 1）存在酉矩阵）存在酉矩阵 ,使得使得其中其中是是A A的全部非零奇异值。的全部非零奇异值。第39页，共63页，编辑于2022年，星

15、期三例例 5.3.1 5.3.1例例 5.3.2 5.3.2其中其中第40页，共63页，编辑于2022年，星期三(2)(2)（若（若A A可逆）可逆）；定理定理 5.3.2 5.3.2 设设A A是是 的矩阵，其奇异值的矩阵，其奇异值分解为分解为 ，则，则(1)(1)（最大的奇异值）；（最大的奇异值）；(3)(3)。第41页，共63页，编辑于2022年，星期三5.3.25.3.2奇异值分解的应用奇异值分解的应用 (1)(1)计算线性方程组的最小二乘解计算线性方程组的最小二乘解 设设A A是是 矩阵，矩阵，b b是是n n维列向量，考虑维列向量，考虑如下线性方程组如下线性方程组 第42页，共63

16、页，编辑于2022年，星期三 在在很很多多情情形形下下，上上述述方方程程组组没没有有解解，因因此此，我我们们计计算算其其最最小小二二乘乘解解，即即求求x x使使得得 最小。最小。第43页，共63页，编辑于2022年，星期三 其中其中U,VU,V是酉矩阵。可以证明是酉矩阵。可以证明2-2-范数具范数具有酉不变性，因此有酉不变性，因此 设设 的奇异值分解为的奇异值分解为 ，第44页，共63页，编辑于2022年，星期三由此可知由此可知 的最小二乘解即是的最小二乘解即是 的最小二乘解。的最小二乘解。第45页，共63页，编辑于2022年，星期三令令则则第46页，共63页，编辑于2022年，星期三即即第4

17、7页，共63页，编辑于2022年，星期三 要使上述方程组的左右两端尽可能相要使上述方程组的左右两端尽可能相等，只需令等，只需令 第48页，共63页，编辑于2022年，星期三即可（其实即可（其实 可以是任意数，可以是任意数，它们是自由变量）。那么它们是自由变量）。那么 是线性方程组是线性方程组 的最小二乘解。的最小二乘解。第49页，共63页，编辑于2022年，星期三(2)(2)计算矩阵的值空间和零空间计算矩阵的值空间和零空间 设设A A是是 的矩阵，的矩阵，A A的奇异值分解的奇异值分解 为为 第50页，共63页，编辑于2022年，星期三由于由于第51页，共63页，编辑于2022年，星期三其中其

18、中r r是矩阵是矩阵A A的秩，从而的秩，从而 第52页，共63页，编辑于2022年，星期三因此因此例例 5.3.4 5.3.4第53页，共63页，编辑于2022年，星期三(3)(3)数字图像逼近数字图像逼近 设设A A的奇异值分解为的奇异值分解为 ，则，则A A可表示为可表示为 与与A A相距最近的秩为相距最近的秩为k k的矩阵就是将的矩阵就是将上式截断取前上式截断取前k k项项需需k(m+n+1)k(m+n+1)个存储单元个存储单元第54页，共63页，编辑于2022年，星期三因因此此我我们们可可以以合合理理地地选选择择k k，使使得得 尽尽量量接接近近于于A A，同同时时存存储储量量又又相

19、相对对较较小小，便便于于储存和传输。储存和传输。第55页，共63页，编辑于2022年，星期三图图5.3.25.3.2展示了截取不同前展示了截取不同前k k项的逼近效果。原项的逼近效果。原始照片的灰度矩阵是一个始照片的灰度矩阵是一个320*240320*240的矩阵，从图的矩阵，从图中可看出取中可看出取k=50k=50的逼近效果就已经很好了。它的逼近效果就已经很好了。它需要的存储单元是需要的存储单元是50*(320+240+1)50*(320+240+1)，大大减少，大大减少了存储量。了存储量。第56页，共63页，编辑于2022年，星期三（a a）原始照片）原始照片 （320240320240）

20、(b)rank10 逼近逼近第57页，共63页，编辑于2022年，星期三（c c）rank30 rank30 逼近逼近(d)rank50(d)rank50 逼近逼近第58页，共63页，编辑于2022年，星期三5.4 5.4 矩阵的满秩分解矩阵的满秩分解 定义定义5.4.1 5.4.1 设设A A是是 的矩阵的矩阵 ，rank(A)=r0,rank(A)=r0,如果存在如果存在 的列满秩的列满秩矩阵矩阵F F及及 的行满秩矩阵的行满秩矩阵G G使得使得 则称此分解为矩阵则称此分解为矩阵A A的满秩分解。的满秩分解。第59页，共63页，编辑于2022年，星期三例例 5.4.1 5.4.1定理定理5

21、.4.15.4.1 任意任意 的矩阵的矩阵A A 都有满秩分解。都有满秩分解。第60页，共63页，编辑于2022年，星期三(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，满足，满足 第61页，共63页，编辑于2022年，星期三则称则称H H为为A A的的HermiteHermite标准形。标准形。(2)(2)设设H H中第中第i i行的第一个非零元

22、素行的第一个非零元素1 1位于位于 第第 列，有列，有(3)(3)H H的第的第 列构成列构成m m阶单位矩阵阶单位矩阵I I(4)(4)的前的前r r列；列；第62页，共63页，编辑于2022年，星期三例例 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行构成行构成 的矩阵的矩阵.第63页，共63页，编辑于2022年，星期三