矩阵的分解

2024-01-08 11:47:12

矩阵的分解

怎么计算矩阵又快又准——矩阵的分解

  • 先判断Doolittle分解是否唯一,再进行Doolittle分解

各阶顺序主子式均不为0,Doolittle分解唯一;

特殊的:正定/负定矩阵,Doolittle分解唯一;严格行(列)对角占优矩阵,Doolittle分解唯一;

Doolittle分解的算法

一共 5 种分解

一、Doolittle分解(三角分解 或称 LR分解)

【定义】Doolittle分解

A ∈ C n × n A\in\mathbb C^{n\times n} ACn×n,若存在一个下三角矩阵 L L L 和一个上三角矩阵 R R R,使得 A = L R A=LR A=LR,则称 A = L R A=LR A=LR A A A 的三角分解

特别的,当 L L L 为单位(主对角元全为1)下三角矩阵时,称 A = L R A=LR A=LR A A A 的 Doolittle 分解

【注】

  • 上(下)三角矩阵的逆矩阵是上(下)三角矩阵
  • 单位下三角矩阵的逆矩阵是单位下三角矩阵
【定理】Doolittle分解唯一?各阶顺序主子式均不为0

A ∈ C n × n A\in\mathbb C^{n\times n} ACn×n,为可逆矩阵,则存在唯一的 Doolittle分解 ? \Longleftrightarrow ? 各阶顺序主子式均不为0

【定理】若A为正定或负定Hermite矩阵,则A存在唯一的Doolittle分解
【定义】行(列)对角占优矩阵

A ∈ C n × n A\in\mathbb C^{n\times n} ACn×n,若 A A A 的元满足:
∣ a i i ∣ ≥ ∑ i ≠ j ∣ a i j ∣ , i = 1 , 2 , ? ? , n |a_{ii}|\geq\sum_{i\neq j}|a_{ij}|,i=1,2,\cdots,n aii?i=j?aij?,i=1,2,?,n
则称 A A A 为行对角占优矩阵;

A A A 的元满足:
∣ a i i ∣ > ∑ i ≠ j ∣ a i j ∣ , i = 1 , 2 , ? ? , n |a_{ii}|>\sum_{i\neq j}|a_{ij}|,i=1,2,\cdots,n aii?>i=j?aij?,i=1,2,?,n
则称 A A A 为严格行对角占优矩阵;

A T A^T AT 为(严格)行对角占优矩阵,则称 A A A 为(严格)列对角占优矩阵

【定理】 (严格)行(列)对角占优矩阵的各阶顺序主子阵也是 (严格)行(列)对角占优矩阵
【定理】严格行(列)对角占优矩阵A是可逆矩阵,且A有唯一的Doolittle分解
【算法】Doolittle分解算法

A ∈ C n × n A\in\mathbb C^{n\times n} ACn×n 的各阶顺序主子式不为0, A A A 的 Doolittle分解为 A = L R A=LR A=LR,用 l i j l_{ij} lij? r i j r_{ij} rij? 分别表示矩阵 L , R L,R L,R 的元,由于
[ a 11 a 12 ? a 1 n a 21 a 22 ? a 2 n ? ? ? a n 1 a n 2 ? a n n ] = [ 1 l 21 1 ? ? l n 1 ? l n , n ? 1 1 ] [ r 11 r 12 ? r 1 n r 22 ? r 2 n ? ? r n n ] \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \\ \end{bmatrix}= \begin{bmatrix} 1 \\ l_{21} & 1 \\ \vdots &&\ddots \\ l_{n1} & \cdots & l_{n,n-1} & 1 \\ \end{bmatrix} \begin{bmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ & r_{22} & \cdots & r_{2n} \\ && \ddots & \vdots \\ &&& r_{nn} \\ \end{bmatrix} ?a11?a21??an1??a12?a22??an2??????a1n?a2n??ann?? ?= ?1l21??ln1??1???ln,n?1??1? ? ?r11??r12?r22??????r1n?r2n??rnn?? ?
a 1 j = r 1 j a_{1j}=r_{1j} a1j?=r1j?,并且
a i j = { ∑ t = 1 j l i t r t j ? , j < i ∑ t = 1 i ? 1 l i t r t j + r i j ? , j ≥ i ( i = 2 , 3 , ? ? , n ) a_{ij}= \begin{cases} \sum_{t=1}^{j}l_{it}r_{tj}\ , & j<i \\\\ \sum_{t=1}^{i-1}l_{it}r_{tj}+r_{ij}\ ,& j\geq i \\ \end{cases} \quad(i=2,3,\cdots,n) aij?=? ? ??t=1j?lit?rtj??,t=1i?1?lit?rtj?+rij??,?j<iji?(i=2,3,?,n)
利用上式可以得到如下递归式:
r i j = a k j ? ∑ t = 1 k ? 1 l k t r t j ? , ? j = k , k + 1 , ? ? , n r_{ij}=a_{kj}-\sum_{t=1}^{k-1}l_{kt}r_{tj}\ ,\ j=k,k+1,\cdots,n rij?=akj??t=1k?1?lkt?rtj??,?j=k,k+1,?,n

l i k = 1 r k k ( a i k ? ∑ t = 1 k ? 1 l i t r t k ) , i = k + 1 , ? ? , n l_{ik}=\frac1{r_{kk}}\left( a_{ik}-\sum_{t=1}^{k-1} l_{it}r_{tk} \right),\quad i=k+1,\cdots,n lik?=rkk?1?(aik??t=1k?1?lit?rtk?),i=k+1,?,n

按照上述递归式,可以顺次求出第一行、第一列、第二行、第二列……,直到解出全部的元

请添加图片描述

例题:

在这里插入图片描述

在这里插入图片描述

最后将该紧凑形式拆分,得到:
A = [ 1 0 0 0 1 1 0 0 1 3 1 0 1 7 6 1 ] [ 1 2 3 4 0 2 6 12 0 0 6 24 0 0 0 24 ] A= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 3 & 1 & 0 \\ 1 & 7 & 6 & 1 \\ \end{bmatrix} \begin{bmatrix} 1 & 2 & 3 & 4 \\ 0 & 2 & 6 & 12 \\ 0 & 0 & 6 & 24 \\ 0 & 0 & 0 & 24 \\ \end{bmatrix} A= ?1111?0137?0016?0001? ? ?1000?2200?3660?4122424? ?

二、QR分解(施密特正交化)

【定理】满秩方阵QR分解存在

A ∈ R n × n A\in\R^{n\times n} ARn×n 满秩,则存在正交矩阵 Q Q Q 和 正线实上三角矩阵 R R R,使得 A = Q R A=QR A=QR

【定理】列满秩矩阵QR分解存在

A ∈ R m × n A\in\R^{m\times n} ARm×n 列满秩,则有 A = Q R A=QR A=QR ,其中 Q ∈ C m × n Q\in\mathbb C^{m\times n} QCm×n 列满秩, Q H Q = E n Q^HQ=E_n QHQ=En? R ∈ C n × n R\in\mathbb C^{n\times n} RCn×n 为正线上三角矩阵

【定理】矩阵的QR分解存在

A ∈ C m × n A\in\mathbb C^{m\times n} ACm×n,rank A A A= r r r,则存在 B ∈ C m × r B\in\mathbb C^{m\times r} BCm×r C ∈ C r × n C\in\mathbb C^{r\times n} CCr×n,rank B B B=rank C C C= r r r,使得 A = B C A=BC A=BC,这里的 A = B C A=BC A=BC 称为 A A A 的满秩分解

A ∈ C m × n A\in\mathbb C^{m\times n} ACm×n,rank A A A= r r r,则存在 Q ∈ R m × r Q\in\mathbb R^{m\times r} QRm×r C ∈ C r × n C\in\mathbb C^{r\times n} CCr×n,rank Q Q Q=rank R R R= r r r Q H Q = E r Q^HQ=E_r QHQ=Er? 使得 A = Q R A=QR A=QR,这里的 A = Q R A=QR A=QR 称为 A A A 的QR分解

【算法】QR分解算法

先将矩阵进行施密特正交化,过程如图所示,将矩阵的所有列向量化为标准正交基

在这里插入图片描述

可以得到
A = [ α 1 , α 2 , ? ? , α n ] = [ η 1 , η 2 , ? ? , η n ] [ l 11 l 21 ? l n 1 0 l 22 ? l n 2 ? ? ? 0 0 ? l n n ] = U R A=[\alpha_1,\alpha_2,\cdots,\alpha_n]=[\eta_1,\eta_2,\cdots,\eta_n] \begin{bmatrix} l_{11} & l_{21} & \cdots & l_{n1} \\ 0 & l_{22} & \cdots & l_{n2} \\ \vdots & \vdots && \vdots & \\ 0 & 0 & \cdots & l_{nn} \\ \end{bmatrix}=UR A=[α1?,α2?,?,αn?]=[η1?,η2?,?,ηn?] ?l11?0?0?l21?l22??0?????ln1?ln2??lnn??? ?=UR
其中 U U U 为酉矩阵, R R R 为正线上三角矩阵

三、谱分解

【定义】谱分解

A = P Λ P ? 1 = [ ξ 1 , ξ 2 , ? ? , ξ n ] [ λ 1 λ 2 ? λ n ] [ η 1 T η 2 T ? η n T ] = λ 1 ξ 1 η 1 T + λ 2 ξ 2 η 2 T + ? + λ n ξ n η n T A=P\Lambda P^{-1}=[\xi_1,\xi_2,\cdots,\xi_n] \begin{bmatrix} \lambda_1 \\ & \lambda_2 \\ && \ddots \\ &&& \lambda_n \\ \end{bmatrix} \begin{bmatrix} \eta_1^T \\ \eta_2^T \\ \vdots \\ \eta_n^T \\ \end{bmatrix}= \lambda_1\xi_1\eta_1^T + \lambda_2\xi_2\eta_2^T + \cdots + \lambda_n\xi_n\eta_n^T A=PΛP?1=[ξ1?,ξ2?,?,ξn?] ?λ1??λ2????λn?? ? ?η1T?η2T??ηnT?? ?=λ1?ξ1?η1T?+λ2?ξ2?η2T?+?+λn?ξn?ηnT?

G i = ξ i η i T G_i=\xi_i\eta_i^T Gi?=ξi?ηiT?,则 A = ∑ λ i G i A=\sum\lambda_iG_i A=λi?Gi? 为矩阵的谱分解

【定理】谱分解唯一性

A ∈ C n × n A\in\mathbb C^{n\times n} ACn×n A A A 存在 n 个线性无关的特征向量, λ 1 , λ 2 , ? ? , λ r \lambda_1,\lambda_2,\cdots,\lambda_r λ1?,λ2?,?,λr?,为 A A A 的全部相异特征值,则 A A A 可以进行满足下列性质的谱分解:

  • A = ∑ j = 1 r λ j E j A=\sum_{j=1}^r\lambda_jE_j A=j=1r?λj?Ej?
  • E j 2 = E j E_j^2=E_j Ej2?=Ej? ( j = 1 , 2 , ? ? , r ) (j=1,2,\cdots,r) (j=1,2,?,r)
  • E i E j = 0 E_iE_j=0 Ei?Ej?=0 ( i ≠ j , i , j = 1 , 2 , ? ? , r ) (i\neq j,i,j=1,2,\cdots,r) (i=j,i,j=1,2,?,r)
  • ∑ j = 1 r E j = E \sum_{j=1}^rE_j=E j=1r?Ej?=E
  • rank E j = n j E_j=n_j Ej?=nj?,这里 n j n_j nj? λ j \lambda_j λj? 的代数重数

满足上述性质的 E j E_j Ej? 唯一确定

注: E i = ξ i 1 η i 1 T + ξ i 2 η i 2 T + ? + ξ i r η i r T E_i=\xi_{i1}\eta_{i1}^T + \xi_{i2}\eta_{i2}^T + \cdots + \xi_{ir}\eta_{ir}^T Ei?=ξi1?ηi1T?+ξi2?ηi2T?+?+ξir?ηirT?

【算法】谱分解算法

求谱分解方法1

请添加图片描述
在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

求谱分解方法2

在这里插入图片描述

四、奇异值分解

【定理】AAH、AHA与特征值

A ∈ C m × n A\in\mathbb C^{m\times n} ACm×n,则

  1. r a n k ( A A H ) = r a n k ( A H A ) = r a n k A rank(AA^H)=rank(A^HA)=rankA rank(AAH)=rank(AHA)=rankA
  2. A H A A^HA AHA A A H AA^H AAH 均为半正定 Hermite 矩阵
  3. r a n k A = r rankA=r rankA=r λ 1 ≥ λ 2 ≥ ? ≥ λ r \lambda_1\geq\lambda_2\geq\cdots\geq\lambda_r λ1?λ2??λr? A A H AA^H AAH 的全部正特征值
  4. r a n k A = r rankA=r rankA=r μ 1 ≥ μ 2 ≥ ? ≥ μ r \mu_1\geq\mu_2\geq\cdots\geq\mu_r μ1?μ2??μr? A H A A^HA AHA 的全部正特征值
  5. 3、4 中 λ i = μ i \lambda_i=\mu_i λi?=μi? i = 1 , 2 , ? ? , r i=1,2,\cdots,r i=1,2,?,r A A H AA^H AAH A H A A^HA AHA 的正特征值一样,只是 0 特征值的数量不一样
【定义】奇异值

A ∈ C m × n A\in\mathbb C^{m\times n} ACm×n,rank A = r A=r A=r λ 1 , λ 2 , ? ? , λ r \lambda_1,\lambda_2,\cdots,\lambda_r λ1?,λ2?,?,λr? A A H AA^H AAH 的正特征值

σ i = λ i \sigma_i=\sqrt\lambda_i σi?=λ ?i? i = 1 , 2 , ? ? , r i=1,2,\cdots,r i=1,2,?,r)为 A A A 的奇异值

注:

  • A A A A H A^H AH 具有相同的奇异值
  • A A A 为 Hermite 矩阵,则 A A A 的奇异值等于 A A A 的非零特征值的绝对值
【定义】奇异值分解

A ∈ C m × n A\in\mathbb C^{m\times n} ACm×n,rank A = r A=r A=r σ 1 ≥ σ 2 ≥ ? ≥ σ r \sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r σ1?σ2??σr? A A A 的奇异值,则

存在 m 阶酉矩阵 U U U 和 n 阶酉矩阵 V V V 使得:
U H A V = D = [ Δ 0 0 0 ] m × n U^HAV=D= \begin{bmatrix} \Delta & 0 \\ 0 & 0 \\ \end{bmatrix}_{m\times n} UHAV=D=[Δ0?00?]m×n?
其中 Δ = d i a g ( σ 1 , σ 2 , ? ? , σ r ) \Delta=diag(\sigma_1,\sigma_2,\cdots,\sigma_r) Δ=diag(σ1?,σ2?,?,σr?) ,称 A = U H A V A=U^HAV A=UHAV A A A 的奇异值分解

【算法】奇异值分解算法

在这里插入图片描述

在这里插入图片描述

文章来源:https://blog.csdn.net/xzy3150787/article/details/135450379
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。