矩阵分解及其应用

Ln=⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜10⋱1ln+1,n⋮lN,n⋱⋱01⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟ L n = ( 1 0 ⋱ 1 l n + 1 , n ⋱ ⋮ ⋱ 0 l N , n 1 )

​ 于是，定义： An=LnAn−1 A n = L n A n − 1 ，其中

li,n=−an−1i,nan−1n,n,i=n+1,n+2,⋯,N l i , n = − a i , n n − 1 a n , n n − 1 , i = n + 1 , n + 2 , ⋯ , N

​ 经过 N−1 N − 1 轮操作后，所有在主对角线下的系数都为 0 了，于是我们得到了一个上三

​ 角矩阵： AN−1 A N − 1 ，这时就有：

A=L−11L1A0=L−11A1=L−11L−12L2A1=L−11L−12A2=⋯=L−11⋯L−1N−1AN−1 A = L 1 − 1 L 1 A 0 = L 1 − 1 A 1 = L 1 − 1 L 2 − 1 L 2 A 1 = L 1 − 1 L 2 − 1 A 2 = ⋯ = L 1 − 1 ⋯ L N − 1 − 1 A N − 1

​ 令 L=L−11⋯L−1N−1,U=AN−1 L = L 1 − 1 ⋯ L N − 1 − 1 , U = A N − 1 ,则分解得证。显然能正常分解一般要求

an−1n,n≠0,n=1,2,⋯,N−1 a n , n n − 1 ≠ 0 , n = 1 , 2 , ⋯ , N − 1

​ 即前 N−1 N − 1 个顺序主子式不等于零（否则消元后主对角还为零则需要交换两行——对应

​ 着另外一种置换初等矩阵，这种初等矩阵可不是下三角的哦~）

​ 这类算法的复杂度一般在 2n33 2 n 3 3 左右，对充分消元的分解则不然。

应用

首先最为简单直白的遍历自然是行列式的求解：

det(A)=det(L)det(U)=∏i=1nLiiUii d e t ( A ) = d e t ( L ) d e t ( U ) = ∏ i = 1 n L i i U i i

实际上还可以引申出高斯约当消去法来求解矩阵的逆，实际上 matlab 就是利用这个原理来求解大部分矩阵的逆的。

QR Q R 分解

基本概念

矩阵的 QR Q R 分解是指，如果实非奇异矩阵 A A 可以表示为

A=QRA=QR

其中 Q Q 为正交矩阵，RR 为实非奇异上三角矩阵。其实际算法多种多样，有 Schmidt 正交方法，Givens 方法和 Household 方法，各有优劣。下面简单介绍Household 方法的 QR Q R 分解

此方法利用反射矩阵，即 Householder 矩阵

H=E−2uuT H = E − 2 u u T

其中 u u 是单位向量，HH 是正交矩阵， det(A)=−1 d e t ( A ) = − 1 。可以证明两个 H H 矩阵的乘积就是 Givens 矩阵，并且任何实非奇异矩阵 AA 可以通过连乘 H H 阵化为上三角矩阵 RR 。则 A=QR A = Q R 。

应用

矩阵的 QR Q R 分解可以用来解决线性最小二乘问题，也可以用来降低矩阵求逆的代价。因为正交矩阵的转置就是其逆 ，这是其他的矩阵分解无法比拟的。

可以看到上述两种分解都要求是方阵，这便使得下面的满秩分解与奇异值分解有了特殊的意义。

满秩分解

基本概念

满秩分解也称为最大秩分解。满秩分解是指：把秩为 r r 的 m×nm×n 的矩阵 A A 分解为 A=FGA=FG ，其中 F F 为秩为 rr 的 m×r m × r 阶矩阵， G G 为秩为 rr 的 r×n r × n 阶矩阵。这由初等变换是很显然的。

应用

其最有用的一个结论是：对于任意的非奇异矩阵 Q Q 和置换矩阵 PP ，使得

QAP=(Er000) Q A P = ( E r 0 0 0 )

奇异值分解

基本概念

矩阵的奇异值分解是在线性代数中一种重要的矩阵分解，在最优化问题、特征值问题、最小二乘问题、广义逆问题以及统计学问题，中都有重要应用

对秩为 r r 的 m×nm×n 的矩阵 A A 进行奇异值分解的步骤依次是：

Step 1: 求得 ATAATA 的特征值 γ1,γ2,⋯,γn γ 1 , γ 2 , ⋯ , γ n 及对应的特征向量并正交单位化得到矩阵 V V 使得

VT(ATA)V=(M2000)VT(ATA)V=(M2000)

其中 M=diag(γ1,γ2,⋯,γn) M = d i a g ( γ 1 , γ 2 , ⋯ , γ n ) 。

一般矩阵 A A 做不到总是可逆，但是复矩阵 ATAATA 总是可逆的，也可以做特征值分解。可以说奇异值分解一定程度上推广了特征值分解

Step 2: 将 V V 的前 rr 列作为 V1 V 1 ，令 U=A(VT1)−1 U = A ( V 1 T ) − 1 ，再扩张 U1 U 1 成 m m 阶的矩阵 UU 。

Step 3: 那么

A=U(M000)VT A = U ( M 0 0 0 ) V T

应用

实例上线中，未完待续~