第五章-矩阵分解课件.ppt

1、 本节介绍矩阵的本节介绍矩阵的LULU分解。分解。LULU分解可用分解可用于求行列式、逆矩阵、解线性方程组等。于求行列式、逆矩阵、解线性方程组等。 5.1 5.1 矩阵的矩阵的LULU分解分解 A A左乘左乘E E，即是对，即是对A A作相应的初等行作相应的初等行变换变换. .若用若用GaussGauss消去法将矩阵消去法将矩阵A A转化成转化成一个阶梯形矩阵一个阶梯形矩阵U U，相应的初等变换对，相应的初等变换对应的矩阵为应的矩阵为 ，则，则r1E,E UAEE1r .EEEEE1r1ri也也是是下下三三角角阵阵阵阵，且且也也是是下下三三角角都都是是下下三三角角阵阵，作作行行变变换换，则则若

2、若在在计计算算过过程程中中不不 梯梯形形矩矩阵阵阶阶三三角角矩矩阵阵所所以以，下下得得到到。在在方方阵阵对对应应的的位位置置即即可可换换对对应应的的乘乘子子放放只只需需将将做做初初等等变变矩矩阵阵的的求求法法：定理定理5.1.15.1.1设设A A是是 的矩阵，则存在置的矩阵，则存在置换矩阵换矩阵P P使得使得 其中其中L L是是 单位下三角阵，单位下三角阵，U U是是 的的阶梯形矩阵。阶梯形矩阵。 nm LUPA mm nm 定义定义5.1.15.1.1 设设A A是是 的矩阵，如果的矩阵，如果A A（或（或A A的某个排列的某个排列PAPA）可分解为）可分解为 ( (或或 其中其中L L是

3、单位下三角阵是单位下三角阵,U,U是阶梯是阶梯形矩阵，则称此分解为形矩阵，则称此分解为A A的的DoolittleDoolittle分解。分解。 如果如果A(A(或或PA)PA)可分解为可分解为 ( (或或其中其中L L是下三角矩阵，是下三角矩阵，U U是非零对角元为是非零对角元为1 1的阶梯形矩阵的阶梯形矩阵 ，则此称分解为，则此称分解为A A的的CroutCrout分解。分解。LUA )LUPA 例例 5.1.35.1.3nm LUA )LUPA 例例 5.1.45.1.4 定理定理5.1.25.1.2设设A A是是 的正定矩阵，则的正定矩阵，则存在存在 的下三角阵的下三角阵L L使得使得

4、 此分解称为矩阵此分解称为矩阵A A的的CholeskyCholesky分解。分解。nn nn TLLA 5.1.2 LU5.1.2 LU分解的应用分解的应用 矩阵的矩阵的LULU分解最常应用于求解线性方分解最常应用于求解线性方程组程组 ，首先我们作分解，首先我们作分解 ，然，然后求解方程组后求解方程组 ，求解过程分两步，求解过程分两步进行：进行： bAx LUPA PbLUx (1)(1)首先解线性方程组首先解线性方程组 ，可得，可得 . . PbLy PbLy1 例例 5.1.55.1.5例例 5.1.65.1.6例例 5.1.75.1.7(2) (2) 接着计算原方程组的解接着计算原方程

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

6、能还存在误差，得到解的目的。当然很可能还存在误差，得到的是的是 ，而不是，而不是 。此时设。此时设 ，解线性方程组解线性方程组 ，得到，得到 ，将，将 的的解改进为解改进为 。2a21aax 12ax Abr 1rAx 1a1abrrbAax A)ax (A1111 1ax 1rAx 2rAx bAx 如此继续下去，可以证明，只要如此继续下去，可以证明，只要condcond（A A） 不是太大，序列不是太大，序列 最终会收最终会收敛到敛到 的解，通常只需迭代几步就可的解，通常只需迭代几步就可以得到很精确的解。以得到很精确的解。 ,aax ,ax , x 211 bAx 5.2 QR5.2 QR

7、分解分解 QR QR分解在解决最小二乘问题，特征值分解在解决最小二乘问题，特征值的计算等方面有十分重要的应用。的计算等方面有十分重要的应用。5.2.1 Householder5.2.1 Householder变换变换 在平面解析几何中，将向量在平面解析几何中，将向量x x映射为关映射为关于于x x轴对称的向量轴对称的向量y y的变换称为关于的变换称为关于x x轴的镜轴的镜像变换（见图像变换（见图5.2.15.2.1）。设）。设 ，则，则T21)x,x(x 其中其中 ,H,H是正交矩阵，且是正交矩阵，且detH=-1detH=-1Hxx)ee2I (xx1001)x,x(yT2221T21 T2

8、)1 , 0(e 2e1exy1x2x图（图（5.2.1 5.2.1 ） 1e2eu1x2x图（图（5.2.25.2.2）定义定义5.2.15.2.1 设单位列向量设单位列向量 ，称，称矩阵矩阵为为HouseholderHouseholder矩阵，称矩阵，称HouseholderHouseholder矩阵矩阵确定的线性变换为确定的线性变换为Householder Householder 变换。变换。 Huu2IH nCu 若若u u不是单位向量，则定义不是单位向量，则定义为为HouseholderHouseholder矩阵，对应的变换称为矩阵，对应的变换称为HouseholderHouseho

9、lder变换。变换。H22uuu2IH Householder Householder变换将向量变换将向量x x映为关映为关于于“与与u u垂直的子空间垂直的子空间 ” ”对称的向量对称的向量( (见图见图5.2.3) 5.2.3) 0)x,y(yW uWHx图图 5.2.35.2.3HouseholderHouseholder矩阵具有如下的性质：矩阵具有如下的性质： (1) (1) （H H是是HermitHermit矩阵）矩阵） HHH (2) (2) （H H是酉矩阵）是酉矩阵） IHHH (3)(3)IH2 (4) (4) （H H是自逆矩阵）是自逆矩阵） HH1 (5) (5) 1)

10、Hdet( 例例 5.2.15.2.1例例 5.2.25.2.2定理定理5.2.15.2.1 设设 是单位列向量，则对是单位列向量，则对 中的任意向量中的任意向量x x，都存在，都存在HouseholderHouseholder矩矩阵使得阵使得 ，其中，其中 ，且，且 为实为实数。数。nCz nCzHx 2x zxH 5.2.2 5.2.2 矩阵的矩阵的QRQR分解分解 下面我们探讨如何利用下面我们探讨如何利用HouseholderHouseholder变变换将矩阵化为上三角矩阵。我们以换将矩阵化为上三角矩阵。我们以n=3n=3的的情形开始讨论情形开始讨论 . .设设 333222111zyx

11、zyxzyxA由例由例5.2.15.2.1知存在知存在HouseholderHouseholder矩阵矩阵 使得使得1H 00lxxxH13211其中其中23211xxxl 此时此时 33221111wv0wv0wvlAH接下来可构造接下来可构造H H使得使得 0lvvH232其中其中 322vvl令令 由矩阵分块乘法可知由矩阵分块乘法可知 H001H2 3221113322111212r00rl0wvlwv0wv0wvlHAHH记记 , 322111r00rl0wvlR112)HH(Q 则则QRA 由于由于 是酉矩阵，则是酉矩阵，则 和和Q Q都是都是酉矩阵。酉矩阵。 21H,H1211H,

12、H 定理定理5.2.25.2.2 设设 ，则存在酉矩阵，则存在酉矩阵Q Q及及上三角矩阵上三角矩阵R R，使，使 QRA nnCA 例例 5.2.35.2.3定义定义5.2.25.2.2 设设 ，如果存在，如果存在n n阶酉矩阶酉矩阵阵Q Q和和n n阶上三角矩阵阶上三角矩阵R R，使得，使得 , ,则称此分解为则称此分解为A A的的QRQR分解分解( (或酉三角分解或酉三角分解) )。当当 时称为时称为A A的正交三角分解。的正交三角分解。 nnCA QRA nnRA 例例 5.2.45.2.4定理定理5.2.35.2.3 设设 ，则存在酉矩阵，则存在酉矩阵 使得使得 ，其中，其中 是是 阶

13、梯型矩阵。阶梯型矩阵。nmCA mmCQ QRA nmCR 5.2.3 QR5.2.3 QR分解的应用分解的应用 bAx QR QR分解可用于求解线性方程组分解可用于求解线性方程组 的最小二乘解的最小二乘解. .的的最最小小二二乘乘解解即即求求为为正正交交矩矩阵阵，则则设设bQRxQbQRxQRAT 例如例如 321T221211cccbQc00r0rrR要求要求 ，使得方程组，使得方程组 )2 , 1i (xi 322221212111ccxrcxrxr5.3.1 5.3.1 奇异值分解奇异值分解 5.3 5.3 奇异值分解奇异值分解 设设A A是是 的非奇异矩阵，由于的非奇异矩阵，由于 是

14、是HermiteHermite矩阵，则由矩阵，则由SchurSchur分解定理知存分解定理知存在酉矩阵在酉矩阵 ，使得，使得 ，其中，其中nn AAHnnCV DAVAVHH )n, 1i ( 0),(diagDin1 是是 的特征值。的特征值。 i AAH，则则设设)v,v(Vn1 ）（ ji0ji)Av()Av()Av,Av()Av,Av(DAVAVijHin1n1Hn1H 由上述分析可知由上述分析可知AVAV的各列是相互正交的，的各列是相互正交的，且且 )n, 1i (Avi2i 令令)n, 1i (i1 )u,u()Av,Av(Un1nn11 则则因此因此U U是酉矩阵。是酉矩阵。 j

15、i0ji1)u()u(jHi由于由于其中其中 ，于是有，于是有 U)Av,Av()Av,Av(AVn1nn11n1 ),(diagn1 HVUA则称则称 为为A A的奇异值。的奇异值。定义定义5.3.15.3.1 设设A A是是 的矩阵，的矩阵， 的特征的特征值为值为nm AAH0n1rr21 ) r , 1i (i1 定理定理 5.3.15.3.1 设设A A是是 的矩阵，的矩阵，rank(A)=r,rank(A)=r,则则（1 1）存在酉矩阵）存在酉矩阵 , , 使得使得其中其中是是A A的全部非零奇异值。的全部非零奇异值。 nm mmCU nnCV nrV000UA ),(diagr1

16、r1, 例例 5.3.15.3.1例例 5.3.25.3.2其中其中HrrrH111vuvuA)2( )v,v(V),u,u(Un1m1 (2) (2) （若（若A A可逆）可逆）； n12)A(cond 定理定理 5.3.25.3.2 设设A A是是 的矩阵，其奇异值的矩阵，其奇异值分解为分解为 ，则，则nm nrV000U (1) (1) （最大的奇异值）；（最大的奇异值）； 12A (3) (3) 。 2/1r1i2FiA 5.3.25.3.2奇异值分解的应用奇异值分解的应用 (1) (1) 计算线性方程组的最小二乘解计算线性方程组的最小二乘解 设设A A是是 矩阵，矩阵，b b是是n

17、n维列向量，考维列向量，考虑如下线性方程组虑如下线性方程组 nm bAx 在很多情形下，上述方程组没有解，在很多情形下，上述方程组没有解，因此，我们计算其最小二乘解，即求因此，我们计算其最小二乘解，即求x x使使得得 最小。最小。2bAx bUxV000bxV000UbAxHHrHr2 其中其中U,VU,V是酉矩阵。可以证明是酉矩阵。可以证明2-2-范数具范数具有酉不变性，因此有酉不变性，因此 设设 的奇异值分解为的奇异值分解为 ，AnrV000UA 由此可知由此可知 的最小二乘解即是的最小二乘解即是 的最小二乘解。的最小二乘解。 bAx bUxV000HHr 令令bUc , xVyHH 则则

18、cy000r 即即m1rrrr222111c0c0cycycy 要使上述方程组的左右两端尽可能相要使上述方程组的左右两端尽可能相等，只需令等，只需令 0y0y/cy/cy/cym1rrrrr22221111 即可（其实即可（其实 可以是任意数，可以是任意数，它们是自由变量）。那么它们是自由变量）。那么 是线性方程组是线性方程组 的最小二乘解。的最小二乘解。 n1ry,y 00/c/c/cxVrr2211H 00/c/c/cVxrr2211 bAx x(2) (2) 计算矩阵的值空间和零空间计算矩阵的值空间和零空间 设设A A是是 的矩阵，的矩阵，A A的奇异值分解的奇异值分解 为为 nm Hr

19、V000UA )v,v(V),u,u(Un1m1 设设由于由于 00000)u,u()v,v(rm1n1 其中其中r r是矩阵是矩阵A A的秩，从而的秩，从而 r , 1iuviii n, 1ri0vi r1u,uSpan)A(R n1rv,vSpan)A(N r1Hv,vSpan)A(R m1rHu,uSpan)A(N 因此因此例例 5.3.45.3.4(3) (3) 数字图像逼近数字图像逼近 设设A A的奇异值分解为的奇异值分解为 ，则，则A A可表示为可表示为 与与A A相距最近的秩为相距最近的秩为k k的矩阵就是将的矩阵就是将上式截断取前上式截断取前k k项项HrV000UA Hrrr

20、H111vuvuA HkkkH111kvuvuA 需需k(m+n+1) k(m+n+1) 个存储单元个存储单元kA因此我们可以合理地选择因此我们可以合理地选择k k，使得，使得 尽量尽量接近于接近于A A，同时存储量又相对较小，便于，同时存储量又相对较小，便于储存和传输。储存和传输。kA图图5.3.25.3.2展示了截取不同前展示了截取不同前k k项的逼近效果。项的逼近效果。原始照片的灰度矩阵是一个原始照片的灰度矩阵是一个320320* *240240的矩的矩阵，从图中可看出取阵，从图中可看出取k=50k=50的逼近效果就已的逼近效果就已经很好了。它需要的存储单元是经很好了。它需要的存储单元是

21、5050* *(320+240+1) (320+240+1) ，大大减少了存储量。，大大减少了存储量。（a a）原始照片）原始照片 （320320240240）(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使得使得 则称此分解为矩阵则称此分解为矩阵A A的满秩分解。的满秩分解。

22、nm rm nr FGA 例例 5.4.15.4.1定理定理5.4.15.4.1 任意任意 的矩阵的矩阵A A 都有满秩分解。都有满秩分解。 nm 0A (1) H(1) H的前的前r r行中每一行至少含有一个非零行中每一行至少含有一个非零元素，且每行第一个非零元素是元素，且每行第一个非零元素是1 1，而后，而后m-rm-r行元素均为行元素均为0 0； 定义定义5.4.25.4.2 设设H H是是 的矩阵，的矩阵， Rank(H)=rRank(H)=r，满足，满足 nm 则称则称H H为为A A的的HermiteHermite标准形。标准形。 (2) (2) 设设H H中第中第i i行的第一个

23、非零元素行的第一个非零元素1 1位于位于 第第 列，有列，有 ) r , 1i (ji r21jjj (3)(3) H H的第的第 列构成列构成m m阶单位矩阵阶单位矩阵I I 的前的前r r列；列； r21j ,j ,j例例 5.4.25.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行构成行构成 的矩阵的矩阵. .nm r21j ,j ,jrm nr