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

1、第第5 5章章 矩阵分解矩阵分解 5.1 5.1 矩阵的矩阵的 分解分解 LU 本节介绍矩阵的本节介绍矩阵的 分解。分解。 分分解可用于求行列式、逆矩阵、解线性解可用于求行列式、逆矩阵、解线性方程组等。方程组等。 LULU 首先回顾在线性代数中学的初等首先回顾在线性代数中学的初等矩阵的概念。设矩阵的概念。设 是是 的矩阵，的矩阵， 是是 的初等矩阵，的初等矩阵， 左乘左乘 ，即，即是对是对 作相应的初等行变换，下面作相应的初等行变换，下面以以AEmm AEA2m 为例给出初等矩阵的形式。为例给出初等矩阵的形式。 mn 对应的初等矩阵是对应的初等矩阵是 12rr0110E 1r 001E 21r

2、r 101E 对应的初等矩阵对应的初等矩阵是是对应的初等矩阵对应的初等矩阵是是 初等矩阵都是非奇异的，且它的初等矩阵都是非奇异的，且它的逆即是它定义的初等变换的逆变换。逆即是它定义的初等变换的逆变换。用上面的例子说明这一点。用上面的例子说明这一点。 的逆变换为的逆变换为 12rr21rr10110E 1r 11r 11001E 的逆变换为的逆变换为21rr 的逆变换为的逆变换为21rr 1101E 若用若用GaussGauss消去法将矩阵消去法将矩阵 转化成一转化成一个阶梯形矩阵个阶梯形矩阵 ，相应的初等变换对，相应的初等变换对应的矩阵为应的矩阵为 ，则，则AU1,rEE1rEE AU 例例

3、5.1.15.1.1例例 5.1.25.1.2定理定理5.1.15.1.1设设 是是 的矩阵，则的矩阵，则存在置换矩阵存在置换矩阵 使得使得 Amn PLUPA 其中其中 是是 单位下三角阵，单位下三角阵， 是是 的阶梯形矩阵。的阶梯形矩阵。 Lmm Umn 例例 5.1.35.1.3分分解解. . 的的此此分分解解为为阶阶梯梯形形矩矩阵阵，则则称称是是非非零零对对角角元元均均为为1 1的的矩矩阵阵，是是下下三三角角），其其中中（或或可可分分解解为为）（或或分分解解，如如果果 的的此此分分解解为为是是阶阶梯梯形形矩矩阵阵，则则称称是是单单位位下下三三角角阵阵，其其中中），（或或）可可分分解解为

4、为的的某某个个排排列列（或或的的矩矩阵阵，如如果果是是 设设 5 5. .1 1. .1 1 定定义义CroutAULLUPALUAPAADoolittleAULLUPALUAPAAAnmA 定理定理5.1.25.1.2设设 是是 的对称正定的对称正定矩阵，则存在矩阵，则存在 的下三角阵的下三角阵 使得使得 An n n n LTALL A此分解称为矩阵此分解称为矩阵 的的 CholeskyCholesky 分解。分解。例例 5.1.45.1.45.1.2 5.1.2 分解的应用分解的应用 矩阵的矩阵的 分解最常应用于求解线性分解最常应用于求解线性方程组方程组 ，首先我们作分解，首先我们作分解

5、 ，然后求解方程组然后求解方程组 ，求解过程分，求解过程分两步进行：两步进行： LUPA PbLUx bAx LULU(1) (1) 首先解线性方程组首先解线性方程组 ，可得，可得 PbLy PbLy1(2) (2) 接着计算原方程组的解接着计算原方程组的解 ， 即求解方程组即求解方程组 。 1xUy Uxy 例例 5.1.55.1.5例例 5.1.65.1.6例例 5.1.75.1.7看到上面的例题，大家可能会产生疑问，看到上面的例题，大家可能会产生疑问，既然矩阵的既然矩阵的 分解可由分解可由Gauss消去法得消去法得到，为什么不在消去的过程中直接解方到，为什么不在消去的过程中直接解方程组呢

6、？为什么要先进行程组呢？为什么要先进行 分解，然后分解，然后再解两个三角方程组呢？再解两个三角方程组呢？ LULU其原因是在实际工作中，有时会出现这其原因是在实际工作中，有时会出现这样的情况：线性方程组的系数矩阵不变样的情况：线性方程组的系数矩阵不变而右端项发生了变化，若此时已经得到而右端项发生了变化，若此时已经得到了系数矩阵了系数矩阵 的分解，则当右端项发生的分解，则当右端项发生变化时，只需求解两个三角方程组即可变化时，只需求解两个三角方程组即可（ , , ），而不必重新进行），而不必重新进行Gauss消去，这样就可大大节省计算量。消去，这样就可大大节省计算量。LUPbLy yUx 下面说明

7、在应用迭代法改进线性方程组下面说明在应用迭代法改进线性方程组 的解时的解时 分解的优势。分解的优势。 Axb LU 设设 是满秩矩阵，是满秩矩阵， ， 是由是由数值方法得到的数值方法得到的 的解。由于舍入的解。由于舍入等原因，等原因， 不是不是 的精确解，即的精确解，即 。下面我们通过求解线性。下面我们通过求解线性方程组方程组 得到得到 来改进线性方程来改进线性方程组的解。组的解。 n nAR nbR x bAx x bAx 01xAbr1Axr 1a若若 是是 的精确解，则的精确解，则1a1Axr brrbAaxAaxA1111)( 即即 是是 的精确解，从而达到的精确解，从而达到改进解的目

8、的。当然很可能还存在误差，改进解的目的。当然很可能还存在误差，得 到 的 是得 到 的 是 ， 而 不 是， 而 不 是 。 此 时 ，。 此 时 ，设设 ，解线性方程组，解线性方程组 ，得到得到 ，将，将 的解改进为的解改进为 1 xa 1Axr 1 a1a2rAx 2 a21aaxAxb 12axAbr 如此继续下去，可以证明，只要如此继续下去，可以证明，只要 不是太大，序列不是太大，序列 , ,最最终会收敛到终会收敛到 的解，通常只需迭代的解，通常只需迭代几步就可以得到很精确的解。几步就可以得到很精确的解。 )(Acond, 211aaxaxxbAx 在迭代的过程中，我们求解了如下一在迭

9、代的过程中，我们求解了如下一系列方程组系列方程组1AxbAxr 若将若将 分解成分解成 ，则每次计算只需求解，则每次计算只需求解两个三角方程组，从而达到节省计算量两个三角方程组，从而达到节省计算量的目的的目的 。ALU例例 5.1.85.1.85.2 矩阵的矩阵的 QR 分解分解 QR分解在矩阵计算中占据相当重要的地位。利分解在矩阵计算中占据相当重要的地位。利用用QR分解，可以解决各种应用中（例如工程力学、分解，可以解决各种应用中（例如工程力学、流体力学、图像压缩处理、结构分析等）出现的流体力学、图像压缩处理、结构分析等）出现的最小二乘问题、特征值问题等矩阵计算中的核心最小二乘问题、特征值问题

10、等矩阵计算中的核心问题。尤其是基于问题。尤其是基于QR分解的分解的QR算法，是求解小型算法，是求解小型稠密矩阵特征值问题的最主要的、数值稳定的算稠密矩阵特征值问题的最主要的、数值稳定的算法。法。设设 为单位列向量，称矩阵为单位列向量，称矩阵nuC 2HHIuu求求QR分解的分解的 Householder 变换变换是将向量是将向量 变换为关于变换为关于“与单位向量与单位向量 正交的正交的 维子空间维子空间”对称的向量对称的向量 的镜像变换。的镜像变换。nuF nxF nyF 1n ()FRor C 为为（初等反射矩阵），对应（初等反射矩阵），对应的变换为的变换为（初等反射变换）（初等反射变换）

11、Householder 矩阵矩阵 具有下列性质：具有下列性质：（1） 为为 Hermite矩阵，即有矩阵，即有（2） 为酉矩阵，即有为酉矩阵，即有（3） 为为，即有，即有（4） 为自逆矩阵，即有为自逆矩阵，即有（5） 的特征值为的特征值为 ( 重重) 和和 （单重）（单重）（6） 仍是仍是Householder 矩阵矩阵1HHHH1 1n TrIOHOH 2HI HHH HIHHHHHHHHH 1设设 ，则，则2HHIuu()( )2 ()2Htr Htr Itr uun 设有设有 则则 ，因此，因此H 22H 1 设特征值设特征值 与与 的重数分别为的重数分别为 ，则，则12kk、11 12

12、12+= ,=()=2kkn kktr Hn 解得解得121,=1knk 设设 ，则，则2HHIuu显然显然22TTTrrHHnIOIOOOHOIOIuuOuu 2(,)2HHn rnHruIuIuu ,n ruF (,)1HHHHuuuuuu 因此结论成立。因此结论成立。其中其中 为标准单位向量。为标准单位向量。21|H xxe 对任意对任意 ，存在，存在 Householder 矩阵矩阵 ，使得，使得HHouseholder变换变换后的像可以取后的像可以取 ，这在几何，这在几何上是显而易见的。从计算上讲，上是显而易见的。从计算上讲， Householder 首次意识到这意味着首次意识到这意

13、味着Householder变换也能变换也能将将非零向量的后非零向量的后 个分量变为零个分量变为零。1n 1enRx 1e若若 ，则取与，则取与 正交的单正交的单位列向量位列向量 ，从而，从而 u21|xxe1e若若 ，令，令21|xxe注意到注意到从而从而0),( uxxuH12),(22exxuxuxxuuxHxH 12exxu xuuxxexxexxuH2),(2 ),(212221222 12222222 2)2(exuxxuxuuxuxuuxxuuuIHxHHHH 虽然在数学上，虽然在数学上， 前的两种符号都令人满前的两种符号都令人满意。但为了数值稳定性的目的，希望向量意。但为了数值稳

14、定性的目的，希望向量 在在大小和方向上都不要太接近大小和方向上都不要太接近 ，否则，否则 就很接近零就很接近零 ，这在几何上是显然的。因此算法，这在几何上是显然的。因此算法实现时应取实现时应取 前的符号与前的符号与 的第一个分量的第一个分量 的符号相同，即的符号相同，即并可加上规定：当并可加上规定：当 时，时，2| |xx21| |xe121sgn( )|uxxe 121sgn()|uxxe 1 2| |xx10 1sgn()1 例例5.2.1 用用Householder变换化向量变换化向量 与与e1共线共线 Tx4 , 0 , 3 6008001080060 4084088021000100

15、01240800154032212.uuuIHexxuT THx005 解：令解：令此时此时 从而从而111111, |Ha ea 根据定理，可用一组根据定理，可用一组 Householder 变换将任意方阵变换将任意方阵 变换为上三角矩阵变换为上三角矩阵12,nA 第一步第一步，当，当 时，存在时，存在Householder 矩阵矩阵 ，使得（为方便说明，不妨取负号）使得（为方便说明，不妨取负号）1 1H111111*(,)nnaH AHHA 如果如果 ，则，则 ，直接进行下一步。，直接进行下一步。1 1HI 矩阵的矩阵的QR分解分解从而从而1222 1221, |,nHa eaeF 221

16、2222*(,)nnnaH AHHA 第二步第二步，对，对 ，当，当 时，时，存在存在 Householder 矩阵矩阵 ，使得，使得2 2H12,nnA 使得使得即有即有12122*naH H AaA 221HHH 如果如果 ，则，则 ，直接进行下一步。，直接进行下一步。2 2HI 使得使得121,nHHH 121nHH H AR AQR 第三步第三步，对，对 继续类似的变换，如此最多继续类似的变换，如此最多 步，也即至多可以找到步，也即至多可以找到 个矩阵个矩阵1n 2nA 1n 令令 ，则，则 为酉矩阵，为酉矩阵，从而上述算法确实得到从而上述算法确实得到QR分解分解1121()nQHH

17、H Q031216042A 利用利用Householder变换将下列矩变换将下列矩阵进行阵进行QR分解：分解：对向量对向量 ，令，令1(0,2,0)T 解解：1121112112|1(1,1,0)|2Teeu 从而得从而得Householder 矩阵矩阵1110102100001HHIu u （ 实际上是平面实际上是平面 的法向量）的法向量）1u0 xy使得使得1216031042H A 对向量对向量 ，令，令2(3,4)T 21(2,1)5Tu （ 实际上是平面实际上是平面 的法向量）的法向量）2u 20yz可得可得 Householder 矩阵矩阵222345524355HHIu u 因此

18、取因此取21165102200H H AR 从而有从而有221001034055043055THH 6 . 08 . 000018 . 06 . 00 211211112HHHHHHQ则则特征值问题的特征值问题的QR算法算法是二十世纪十大算法之一，其基本是二十世纪十大算法之一，其基本思想基于思想基于: (1) 令令 ； (2) 对对 ，重复，重复 对对 做做QR分解：分解： 令令直至直至 收敛。收敛。1AA 1,2,k kAkkkAQ R 1kkkAR Q kA1HkkkkkkAR QQ A Q 由由 知知 ，因此，因此kkkAQ R HkkkQ AR 111HkkHkkkQAQQQ11111

19、HHHkkkkQ QQ A QQQ 因此迭代序列因此迭代序列 保持特征值不变保持特征值不变kAkkHQQQQAQQ11 其中其中可以证明，在一定条件下，迭代序列可以证明，在一定条件下，迭代序列 收收敛到上三角矩阵敛到上三角矩阵 T 。kA这也说明这也说明QR迭代也可看成是对迭代也可看成是对 作作 Schur 分解。分解。特别地，如果特别地，如果 是是Hermite矩阵，那么上三角矩阵，那么上三角矩阵矩阵 变成对角矩阵。变成对角矩阵。AAT由于计算成本的缘故，数值实现时一般先将矩由于计算成本的缘故，数值实现时一般先将矩阵阵 变换成上变换成上Hessenberg矩阵矩阵 (第一条次对角第一条次对角

20、线以下均为零的矩阵线以下均为零的矩阵)，然后再使用，然后再使用QR迭代。迭代。AH5.3 矩阵的奇异值分解矩阵的奇异值分解 从从Beltrami (1873)和和Jordan (1874)提出奇异提出奇异值分解值分解(SVD, Singular value decomposition)至至今，今，SVD及其推广已经成为矩阵计算最有用和及其推广已经成为矩阵计算最有用和最有效的工具之一，在最小二乘问题、最优化、最有效的工具之一，在最小二乘问题、最优化、统计分析、信号与图像处理、系统理论与控制统计分析、信号与图像处理、系统理论与控制等领域被广泛使用。等领域被广泛使用。一、从几何观测说起一、从几何观测

21、说起 圆圆 经过变换经过变换 ，变成椭圆，变成椭圆 。圆的正交方。圆的正交方向向 变成椭圆的长、短轴方向变成椭圆的长、短轴方向12vv、SAAS1 122uu 、 假定矩阵假定矩阵 是列满秩矩阵。是列满秩矩阵。()mnnACm 一般地，一般地， 维空间中的维空间中的 经过变换经过变换 变成变成 。正交方向。正交方向 变成超椭变成超椭圆的主半轴方向圆的主半轴方向 。称。称 的的 个主个主半轴的长度半轴的长度 为为 的的， 对应的单位向量对应的单位向量 为为 的的，对应的原象，对应的原象 为为 的的。相应的空间称为。相应的空间称为1nvv、 、SAAS1 1nnuu 、 、n1nuu、 、A11(

22、)nn 、 、1nvv、 、ASnAAA二、矩阵的奇异值分解二、矩阵的奇异值分解 前面已经指出前面已经指出：(1)jjjAvujn 121212(,)(,)(,)nnnA v vvu uu diag 矩阵形式为矩阵形式为 AVU 这里矩阵这里矩阵 是列正交矩阵，是列正交矩阵， 是酉矩阵。是酉矩阵。UV* AUV这样就得到这样就得到 的的A 同样地，将矩阵同样地，将矩阵 扩充为扩充为 阶酉矩阵阶酉矩阵 ， 并令并令 ，则得，则得 的的UAO Um*AVU 对任意矩阵对任意矩阵 ，矩阵，矩阵 的的非零非零奇异值奇异值 就是矩阵就是矩阵 或或 的的非零非零特征值的平方根。特征值的平方根。HA Am

23、nAC AHAA10r 矩阵矩阵 在多元统计分析中称为在多元统计分析中称为，这说明这说明SVD会在其中被广泛使用，事实上也确实会在其中被广泛使用，事实上也确实如此。如此。HA A对任意矩阵对任意矩阵 ，都存在一个完，都存在一个完全奇异值分解全奇异值分解 。并且奇异值。并且奇异值 是是唯一确定的。也就是唯一确定的。也就是任意矩阵酉等价于对角阵任意矩阵酉等价于对角阵j m nAC *AU V对矩阵对矩阵 ， 表示矩阵表示矩阵 的的 个个非零非零奇异值，则奇异值，则 2222112|, |FrAAm nAC (min(, )rrm n 1r对任意矩阵对任意矩阵 ，矩阵，矩阵 的的非零非零奇异值数目为

24、奇异值数目为 ， 为为矩阵矩阵 的的SVD分解，则分解，则 A*AU Vm nAC (min(, )rrm n A12(,() ,)rRspanAu uu 12(,.()rrnNspanvAvv 112112rHm rHHOVAUUUVOOrnVr 将将 的的SVD分解分块为分解分块为A于是有于是有111()() | |()Hy yAxy yUVxARRU从而从而1111 | |()()y yU zy yA VR UR Az 121,(),()rspaR UAu uuRn11|()()(Hx AxxxN AUV12|Hx xVx Vx 12,rrnspan vvv 第二步第二步：令：令 为为

25、的非负对角的平方根，计算的非负对角的平方根，计算 三、矩阵三、矩阵SVD分解的算法分解的算法111UAV 由定理由定理4和和5，任意矩阵，任意矩阵 的的SVD分解的算法为：分解的算法为：A第一步第一步： 形成形成 ，并计算特征值分解，并计算特征值分解HA A12, ,HHA A V VVV V 第三步第三步: 通过求通过求 的解空间的单位正交的解空间的单位正交基，得基，得 ，从而得，从而得HAA y 2U12(,)UU U 1 0 1(1)0 1 1 ;0 0 0A 求下列矩阵的（完全）求下列矩阵的（完全）SVD分解：分解：1 0(2)0 1 .1 0A 101210011 ,12011200

26、0TTA AAA解解：（1）矩阵矩阵 的特征值为的特征值为 ，对应的特征向，对应的特征向量为量为123(1,1,2) ,(1, 1,0) ,(1,1, 1)TTT3,1,0TA A从而从而12111623111623216330(,),010VV V 计算计算解解 ，得其基础解系为，得其基础解系为TAA y 1111122112200UAV 3(0,0,1)T 从而从而200 ,1U 12112211220(,)0001UU U 因此所求（完全）因此所求（完全）SVD为为000030010TAUV 由于是方阵，约化由于是方阵，约化SVD同上面的结果一样。同上面的结果一样。10020,01001101TTA AAA解解：（2）矩阵矩阵 的特征值为的特征值为 ，对应的特征向量为，对应的特征向量为12(1,0) ,(0,1)TT2,1TA A从而从而11020,0101VV 计算计算解解 ，得其基础解系为，得其基础解系为TAA y 11112120010UAV 3( 1,0,1)T 从而从而212120,U 12112211220(,)0100UU U 因此所求（完全）因此所求（完全）SVD为为200100TAUV 显然约化显然约化SVD为为111212010001011200TAUV