iphone做网站服务器,建设网站网站名,注册公司需要登录的网址,能制作网页的软件是一、奇异值分解
奇异值分解#xff08;SVD#xff09;是线性代数的高光时刻。 A A A 是一个 m n m\times n mn 的矩阵#xff0c;可以是方阵或者长方形矩阵#xff0c;秩为 r r r。我们要对角化 A A A#xff0c;但并不是把它化成 X − 1 A X X^{-1}A X X−1AX 的形…一、奇异值分解
奇异值分解SVD是线性代数的高光时刻。 A A A 是一个 m × n m\times n m×n 的矩阵可以是方阵或者长方形矩阵秩为 r r r。我们要对角化 A A A但并不是把它化成 X − 1 A X X^{-1}A X X−1AX 的形式。这是因为 X X X 中的特征向量有三个大问题它们通常并不正交并不总是有足够数量的特征向量并且 A x λ x A\boldsymbol x\lambda\boldsymbol x Axλx 要求 A A A 是方阵。 A A A 的奇异值向量Singular vectors完美的解决了这些问题。 由 SVD 我们可以得到四个基本子空间合适的基。下面是按照基向量的重要性顺序来求得这些基向量的步骤。 我们需要有两组奇异值向量 u i \boldsymbol u_i ui 和 v i \boldsymbol v_i vi其中 u i \boldsymbol u_i ui 在 R m \pmb {\textrm R}^m Rm 中 v i \boldsymbol v_i vi 在 R n \textrm{\pmb R}^n Rn 中它们将分别是 m × m m\times m m×m 的矩阵 U \pmb U U 和 n × n n\times n n×n 的矩阵 V \pmb V V 的列。下面会先根据这些基向量来描述 SVD然后再根据正交矩阵 U U U 和 V V V 来描述 SVD。其基本思想是在行空间中找到一组基标准交向量 v i \boldsymbol v_i vi然后通过 A v i σ i u i A\boldsymbol v_i\sigma_i\boldsymbol u_i Aviσiui 映射到列空间中的 u i \boldsymbol u_i ui我们的目标是 v i \boldsymbol v_i vi 是特殊的标准正交向量映射到 u i \boldsymbol u_i ui 也是标准正交。 向量角度 u i \boldsymbol u_i ui 和 v j \boldsymbol v_j vj 给出了 A A A 的四个基本子空间的基 u 1 , u 2 , ⋯ , u r 是 列空间 的标准正交基 u r 1 , u r 2 , ⋯ , u m 是 左零空间 N ( A T ) 的标准正交基 v 1 , v 2 , ⋯ , v r 是 行空间 的标准正交基 v r 1 , v r 2 , ⋯ , v n 是 零空间 N ( A ) 的标准正交基 \begin{array}{ll}\boldsymbol u_1,\boldsymbol u_2,\cdots,\boldsymbol u_r是\pmb{列空间}的标准正交基\\\boldsymbol u_{r1},\boldsymbol u_{r2},\cdots,\boldsymbol u_m是\pmb{左零空间\,N(A^T)\,}的标准正交基\\\boldsymbol v_1,\boldsymbol v_2,\cdots,\boldsymbol v_r是\pmb{行空间}的标准正交基\\\boldsymbol v_{r1},\boldsymbol v_{r2},\cdots,\boldsymbol v_n是\pmb{零空间}\,N(A)\,的标准正交基\end{array} u1,u2,⋯,urur1,ur2,⋯,umv1,v2,⋯,vrvr1,vr2,⋯,vn是列空间的标准正交基是左零空间N(AT)的标准正交基是行空间的标准正交基是零空间N(A)的标准正交基 这些基向量不仅正交而且可以对角化矩阵 A A A “对角化 A \pmb A A” \kern 20pt A v 1 σ 1 u 1 , A v 2 σ 2 u 2 , ⋯ , A v r σ r u r ( 7.2.1 ) {\color{blue}A\boldsymbol v_1\sigma_1\boldsymbol u_1,\kern 5ptA\boldsymbol v_2\sigma_2\boldsymbol u_2,\kern 5pt\cdots,\kern 5ptA\boldsymbol v_r\sigma_r\boldsymbol u_r}\kern 20pt(7.2.1) Av1σ1u1,Av2σ2u2,⋯,Avrσrur(7.2.1) 这些奇异值 σ 1 , σ 2 , ⋯ , σ r \pmb{\sigma_1,\sigma_2,\cdots,\sigma_r} σ1,σ2,⋯,σr 都是正数 σ i \sigma_i σi 是 A v i A\boldsymbol v_i Avi 的长度。对角矩阵 Σ \Sigma Σ 的对角元素除了奇异值 σ i \sigma_i σi 外都是零。 矩阵角度由于 u i \boldsymbol u_i ui 是标准正交的所以由 r r r 个列向量组成的矩阵 U r U_r Ur 有 U r T U r I U_r^TU_rI UrTUrI而 v i \boldsymbol v_i vi 也是标准正交的所以矩阵 V r V_r Vr 有 V r T V r I V_r^TV_rI VrTVrI。则由方程 A v i σ i u i A\boldsymbol v_i\sigma_i\boldsymbol u_i Aviσiui 推出 A V r U r Σ r \pmb{AV_rU_r\Sigma_r} AVrUrΣr 的各列成立 ( m × n ) ( n × r ) A V r U r Σ r ( m × r ) ( r × r ) A [ v 1 v 2 ⋯ v r ] [ u 1 u 2 ⋯ u r ] [ σ 1 σ 2 ⋱ σ r ] ( 7.2.2 ) \begin{array}{l}(m\times n)(n\times r)\\\pmb{AV_rU_r\Sigma_r}\\(m\times r)(r\times r)\end{array}\kern 10ptA\begin{bmatrix}\boldsymbol v_1\boldsymbol v_2\cdots\boldsymbol v_r\end{bmatrix}\begin{bmatrix}\boldsymbol u_1\boldsymbol u_2\cdots\boldsymbol u_r\end{bmatrix}\begin{bmatrix}\sigma_1\\\sigma_2\\\ddots\\\sigma_r\end{bmatrix}\kern 15pt(7.2.2) (m×n)(n×r)AVrUrΣr(m×r)(r×r)A[v1v2⋯vr][u1u2⋯ur] σ1σ2⋱σr (7.2.2)这个是 SVD 的核心但是 SVD 并不是只有这些内容。这些 v i \boldsymbol v_i vi 和 u i \boldsymbol u_i ui 可以生成 A A A 的行空间和列空间还可以从零空间 N ( A ) \pmb N(A) N(A) 和左零空间 N ( A T ) \pmb N(A^T) N(AT) 得到 n − r n-r n−r 个 v j \boldsymbol v_j vj 和 m − r m-r m−r 个 u i \boldsymbol u_i ui它们也和前面的 v i \boldsymbol v_i vi 和 u i \boldsymbol u_i ui 正交这是因为四个基本子空间配对正交。我们现在在 V V V 和 U U U 中包含所有的 v j \boldsymbol v_j vj 和 u i \boldsymbol u_i ui这两个矩阵就变成了方阵仍然有 A V U Σ \pmb{AVU\Sigma} AVUΣ。 ( m × n ) ( n × n ) A V U Σ ( m × m ) ( m × n ) A [ v 1 ⋯ v r ⋯ v n ] [ u 1 ⋯ u r ⋯ u m ] [ σ 1 σ 2 ⋱ σ r ] ( 7.2.3 ) \begin{array}{l}(m\times n)(n\times n)\\\pmb{AVU\Sigma}\\(m\times m)(m\times n)\end{array}\kern 10ptA\begin{bmatrix}\boldsymbol v_1\cdots\boldsymbol v_r\cdots\boldsymbol v_n\end{bmatrix}\begin{bmatrix}\boldsymbol u_1\cdots\boldsymbol u_r\cdots\boldsymbol u_m\end{bmatrix}\begin{bmatrix}\sigma_1\\\sigma_2\\\ddots\\\sigma_r\\\end{bmatrix}\kern 15pt(7.2.3) (m×n)(n×n)AVUΣ(m×m)(m×n)A[v1⋯vr⋯vn][u1⋯ur⋯um] σ1σ2⋱σr (7.2.3)新的 Σ \Sigma Σ 是 m × n m\times n m×n 的矩阵它是7.3.2中的 r × r r\times r r×r 矩阵下面添加 m − r m-r m−r 个零行右侧添加 n − r n-r n−r 个零列。真正的变化是 U U U 和 V V V 的形状它们变成了方阵并且有 V − 1 V T V^{-1}V^T V−1VT所以 A V U Σ AVU\Sigma AVUΣ 就变成了 A U Σ V T \pmb{AU\Sigma V^T} AUΣVT这个就是奇异值分解Singular Value Decompositon可以用 U Σ U\Sigma UΣ 中的列 u i σ i \boldsymbol u_i\sigma_i uiσi 乘上 V T V^T VT 的行 SVD A U Σ V T u 1 σ 1 v 1 T u 2 σ 2 v 2 T ⋯ u r σ r v r T ( 7.2.4 ) \kern 30pt{\color{blue}AU\Sigma V^T\boldsymbol u_1\sigma_1\boldsymbol v_1^T\boldsymbol u_2\sigma_2\boldsymbol v_2^T\cdots\boldsymbol u_r\sigma_r\boldsymbol v_r^T}\kern 20pt(7.2.4) AUΣVTu1σ1v1Tu2σ2v2T⋯urσrvrT(7.2.4) 式7.3.2是 “缩略版的 SVDreduced SVD”它只包含行空间和列空间的基式7.3.3是完整版的 SVD它将零空间的基也包含了进去。这两个式子都是将 A A A 分解成同样的 r r r 个秩一矩阵 u i σ r v i T \boldsymbol u_i\sigma_r\boldsymbol v_i^T uiσrviT 的和。列乘行是矩阵乘法的第四种方式。 我们后面能够看到每个 σ i 2 \sigma_i^2 σi2 既是 A T A A^TA ATA 的特征值也是 A A T AA^T AAT 的特征值。我们将奇异值按照降序排列 σ 1 ≥ σ 2 ≥ ⋯ ≥ σ r 0 \sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r0 σ1≥σ2≥⋯≥σr0式7.2.4中的分解就是按照重要性顺序得到的 A A A 的 r r r 个秩一项这一点非常重要。
【例1】什么时候 A U Σ V T AU\Sigma V^T AUΣVT奇异值和 X Λ X − 1 X\Lambda X^{-1} XΛX−1 相同特征值 解 A A A 的特征向量需要标准正交才有 X U V XUV XUV如果 A Σ A\Sigma AΣ也需要特征值 λ ≥ 0 \lambda\geq0 λ≥0所以 A A A 必须是一个半正定或正定的对称矩阵。只有这样才会有 A X Λ X − 1 AX\Lambda X^{-1} AXΛX−1就是 Q Λ Q T Q\Lambda Q^{T} QΛQT 和 A U Σ V T AU\Sigma V^{T} AUΣVT 一致。
【例2】如果 A x y T A\boldsymbol x \boldsymbol y^T AxyT秩一其中 x \boldsymbol x x 和 y \boldsymbol y y 都是单位向量那么 A A A 的 SVD 是什么 解 式7.2.2中缩略版的 SVD 就是 x y T \boldsymbol x\boldsymbol y^T xyT秩为 r 1 r1 r1其中 u 1 x \boldsymbol u_1\boldsymbol x u1x v 1 y \boldsymbol v_1\boldsymbol y v1y 且 σ 1 1 \sigma_11 σ11。完全版的 SVD要将 u 1 x \boldsymbol u_1\boldsymbol x u1x 扩充为标准正交基 u i \boldsymbol u_i ui然后将 v 1 y \boldsymbol v_1\boldsymbol y v1y 扩充为标准正交基 v j \boldsymbol v_j vj没有新的 σ \sigma σ只有一个 σ 1 1 \sigma_11 σ11。
二、SVD 的证明
我们需要知道这令人惊叹的 u i \boldsymbol u_i ui 和 v j \boldsymbol v_j vj 是如何构造出来的。 v j \boldsymbol v_j vj 是 A T A \pmb{A^TA} ATA 的特征向量这个一定是正确的因为我们的目标是 A T A ( U Σ V T ) T ( U Σ V T ) V Σ T U T U Σ V T V Σ T Σ V T ( 7.2.5 ) \pmb{A^TA}(U\Sigma V^T)^T(U\Sigma V^T)V\Sigma^TU^TU\Sigma V^T\pmb{V\Sigma^T\Sigma V^T}\kern 20pt(7.2.5) ATA(UΣVT)T(UΣVT)VΣTUTUΣVTVΣTΣVT(7.2.5)右侧包含了对称半正定矩阵 A T A A^TA ATA 的特征向量矩阵 V V V并且 ( Σ T Σ ) (\Sigma^T\Sigma) (ΣTΣ) 是 ( A T A ) (A^TA) (ATA) 的特征值矩阵每个 σ 2 \sigma^2 σ2 就是 ( A T A ) (A^TA) (ATA) 特征值 λ ( A T A ) \lambda(A^TA) λ(ATA) 现在由 A v i σ i u i A\boldsymbol v_i\sigma_i\boldsymbol u_i Aviσiui 可以得到单位向量 u 1 , u 2 , ⋯ , u r \boldsymbol u_1,\boldsymbol u_2,\cdots,\boldsymbol u_r u1,u2,⋯,ur这就是关键的式7.2.1核心点也就是 SVD 成功的全部原因是这些单位向量 u 1 , u 2 , ⋯ , u r \boldsymbol u_1,\boldsymbol u_2,\cdots,\boldsymbol u_r u1,u2,⋯,ur 一定是两两正交因为 v i \boldsymbol v_i vi 是正交的 关键步骤 i ≠ j u i T u j ( A v i σ i ) T ( A v j σ j ) v i T A T A v j σ i σ j σ j 2 σ i σ j v i T v j 0 ( 7.2.6 ) \begin{array}{}\pmb{关键步骤}\\\pmb{i\neq j}\end{array}\kern 20pt\boldsymbol u_i^T\boldsymbol u_j(\frac{A\boldsymbol v_i}{\sigma_i})^T(\frac{A\boldsymbol v_j}{\sigma_j})\frac{\boldsymbol v_i^TA^TA\boldsymbol v_j}{\sigma_i\sigma_j}\frac{\sigma_j^2}{\sigma_i\sigma_j}\boldsymbol v_i^T\boldsymbol v_j0\kern 20pt(7.2.6) 关键步骤ijuiTuj(σiAvi)T(σjAvj)σiσjviTATAvjσiσjσj2viTvj0(7.2.6) v i \boldsymbol v_i vi 是 A T A A^TA ATA对称的特征向量它们是正交的并且得到 u i \boldsymbol u_i ui 也是正交的。实际上 u i \boldsymbol u_i ui 是 A A T AA^T AAT 的特征向量。 最终在 v j \boldsymbol v_j vj 和 u i \boldsymbol u_i ui 的基础上分别构造出了零空间 N ( A ) \pmb N(A) N(A) 和 左零空间 N ( A T ) \pmb N(A^T) N(AT) 的标准正交基得到 n n n 个 v j \boldsymbol v_j vj 和 m m m 个 u i \boldsymbol u_i ui得到 A U Σ V T AU\Sigma V^T AUΣVT 中的 V , Σ V,\Sigma V,Σ 和 U U U。
三、SVD 的一个例子
下例演示了 A U Σ V T AU\Sigma V^T AUΣVT 中全部三个矩阵的计算过程。
【例3】矩阵 A [ 3 0 4 5 ] A\begin{bmatrix}30\\45\end{bmatrix} A[3405]秩为 r 2 r2 r2求出对应的矩阵 U , Σ , V U,\Sigma,V U,Σ,V。 解 由于秩 r 2 r2 r2所以 A A A 有两个正的奇异值 σ 1 \sigma_1 σ1 和 σ 2 \sigma_2 σ2下面会看到 σ 1 \sigma_1 σ1 比特征值 λ m a x 5 \lambda_{max}5 λmax5 更大 σ 2 \sigma_2 σ2 比特征值 λ m i n 3 \lambda_{min}3 λmin3 要更小先从 A T A A^TA ATA 和 A A T AA^T AAT 开始 A T A [ 25 20 20 25 ] A A T [ 9 12 12 41 ] A^TA\begin{bmatrix}2520\\2025\end{bmatrix}\kern 20ptAA^T\begin{bmatrix}\kern 4pt912\\1241\end{bmatrix} ATA[25202025]AAT[9121241]它们有相同的迹 ( 50 ) (50) (50) 和相同的特征值 σ 1 2 45 \sigma_1^245 σ1245 和 σ 2 2 5 \sigma_2^25 σ225取算术平方根得 σ 1 45 \sigma_1\pmb{\sqrt{45}} σ145 和 σ 2 5 \sigma_2\pmb{\sqrt5} σ25 则 σ 1 σ 2 15 \sigma_1\sigma_215 σ1σ215也就是 A A A 的行列式。 关键步骤是求 A T A A^TA ATA 的特征向量分别对应特征值 45 45 45 和 5 5 5 [ 25 20 20 25 ] [ 1 1 ] 45 [ 1 1 ] [ 25 20 20 25 ] [ − 1 1 ] 5 [ − 1 1 ] \begin{bmatrix}2520\\2025\end{bmatrix}\begin{bmatrix}1\\1\end{bmatrix}\pmb{45}\begin{bmatrix}1\\1\end{bmatrix}\kern 20pt\begin{bmatrix}2520\\2025\end{bmatrix}\begin{bmatrix}-1\\\kern 7pt1\end{bmatrix}\pmb5\begin{bmatrix}-1\\\kern 7pt1\end{bmatrix} [25202025][11]45[11][25202025][−11]5[−11]然后将这些正交特征向量单位化都除以 2 \sqrt2 2 即得到 v 1 \boldsymbol v_1 v1 和 v 2 \boldsymbol v_2 v2。 右奇异向量 v 1 1 2 [ 1 1 ] v 2 1 2 [ − 1 1 ] 左奇异向量 u i A v i σ i \pmb{右奇异向量}\kern 10pt\boldsymbol v_1\frac{1}{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}\kern 5pt\boldsymbol v_2\frac{1}{\sqrt2}\begin{bmatrix}-1\\\kern 7pt1\end{bmatrix}\kern 10pt\pmb{左奇异向量}\kern 5pt\boldsymbol u_i\frac{A\boldsymbol v_i}{\sigma_i} 右奇异向量v12 1[11]v22 1[−11]左奇异向量uiσiAvi现在计算 A v 1 A\boldsymbol v_1 Av1 和 A v 2 A\boldsymbol v_2 Av2它们分别是 σ 1 u 1 45 u 1 \sigma_1\boldsymbol u_1\sqrt{45}\boldsymbol u_1 σ1u145 u1 和 σ 2 u 2 5 u 2 \sigma_2\boldsymbol u_2\sqrt5\boldsymbol u_2 σ2u25 u2 A v 1 3 2 [ 1 3 ] 45 1 10 [ 1 3 ] σ 1 u 1 A v 2 1 2 [ − 3 1 ] 5 1 10 [ − 3 1 ] σ 2 u 2 \begin{array}{l}A\boldsymbol v_1\displaystyle\frac{3}{\sqrt2}\begin{bmatrix}1\\3\end{bmatrix}\sqrt{45}\pmb{\frac{1}{\sqrt{10}}\begin{bmatrix}1\\3\end{bmatrix}}\sigma_1\boldsymbol u_1\\\\A\boldsymbol v_2\displaystyle\frac{1}{\sqrt2}\begin{bmatrix}-3\\\kern 7pt1\end{bmatrix}\sqrt5\pmb{\frac{1}{\sqrt{10}}\begin{bmatrix}-3\\\kern 7pt1\end{bmatrix}}\sigma_2\boldsymbol u_2\end{array} Av12 3[13]45 10 1[13]σ1u1Av22 1[−31]5 10 1[−31]σ2u2除以 10 \sqrt{10} 10 使得 u 1 \boldsymbol u_1 u1 和 u 2 \boldsymbol u_2 u2 标准正交然后可以得到预期的 σ 1 45 \sigma_1\sqrt{45} σ145 和 σ 2 5 \sigma_2\sqrt5 σ25 。 A A A 的奇异值分解就是 U Σ V T U\Sigma V^T UΣVT。 U 1 10 [ 1 − 3 3 1 ] Σ [ 45 5 ] V 1 2 [ 1 − 1 1 1 ] ( 7.2.7 ) \pmb U\frac{1}{\sqrt{10}}\begin{bmatrix}1-3\\3\kern 7pt1\end{bmatrix}\kern 15pt\pmb\Sigma\begin{bmatrix}\sqrt{45}\\\sqrt5\end{bmatrix}\kern 15pt\pmb V\frac{1}{\sqrt2}\begin{bmatrix}1-1\\1\kern 7pt1\end{bmatrix}\kern 20pt(7.2.7) U10 1[13−31]Σ[45 5 ]V2 1[11−11](7.2.7) U U U 和 V V V 包含列空间和行空间两个空间都是 R 2 \pmb{\textrm R}^2 R2的标准正交基。真正要做的是使用两组基对角化 A A A A V U Σ AVU\Sigma AVUΣ。矩阵 A A A 分解成了两个秩一矩阵列乘行的组合 σ 1 u 1 v 1 T σ 2 u 2 v 2 T 45 20 [ 1 1 3 3 ] 5 20 [ 3 − 3 − 1 1 ] [ 3 0 4 5 ] A \sigma_1\boldsymbol u_1\boldsymbol v_1^T\sigma_2\boldsymbol u_2\boldsymbol v_2^T\pmb{\frac{\sqrt{45}}{\sqrt{20}}\begin{bmatrix}11\\33\end{bmatrix}\frac{\sqrt5}{\sqrt{20}}\begin{bmatrix}\kern 7pt3-3\\-1\kern 7pt1\end{bmatrix}}\begin{bmatrix}30\\45\end{bmatrix}A σ1u1v1Tσ2u2v2T20 45 [1313]20 5 [3−1−31][3405]A
四、一个极端的矩阵
下面是一个阶数更大的矩阵的例子它的 u i \boldsymbol u_i ui 和 v i \boldsymbol v_i vi 都是单位矩阵的列所以计算很简单但是要注意列的顺序。矩阵 A A A 非常的不平衡它是一个严格的三角形矩阵它所有的特征值都为零 A A T AA^T AAT 和 A T A A^TA ATA 并不接近矩阵 U U U 和 V V V 是置换矩阵可以弥补这些问题。 A [ 0 1 0 0 0 0 2 0 0 0 0 3 0 0 0 0 ] 特征值 λ 0 , 0 , 0 , 0 全是零 只有一个特征向量 ( 1 , 0 , 0 , 0 ) 奇异值 σ 3 , 2 , 1 奇异向量是 I 的列 A\begin{bmatrix}0\pmb100\\00\pmb20\\000\pmb3\\0000\end{bmatrix}\kern 20pt\begin{array}{l}特征值\,\lambda0,0,0,0\,全是零\\只有一个特征向量\,(1,0,0,0)\\奇异值\,\sigma\pmb3,\pmb2,\pmb1\\奇异向量是\,I\,的列\end{array} A 0000100002000030 特征值λ0,0,0,0全是零只有一个特征向量(1,0,0,0)奇异值σ3,2,1奇异向量是I的列 A T A A^TA ATA 和 A A T AA^T AAT 都是对角矩阵有简单的特征向量但是顺序不同 A T A [ 0 0 0 0 0 1 0 0 0 0 4 0 0 0 0 9 ] A A T [ 1 0 0 0 0 4 0 0 0 0 9 0 0 0 0 0 ] A^TA\begin{bmatrix}\pmb0000\\0\pmb100\\00\pmb40\\000\pmb9\end{bmatrix}\kern 20ptAA^T\begin{bmatrix}\pmb1000\\0\pmb400\\00\pmb90\\000\pmb0\end{bmatrix} ATA 0000010000400009 AAT 1000040000900000 它们的特征向量 u i \boldsymbol u_i ui 对应 A A T AA^T AAT v i \boldsymbol v_i vi 对应 A T A A^TA ATA按照特征值减小的顺序 σ 1 2 σ 2 2 σ 3 2 \sigma_1^2\sigma_2^2\sigma_3^2 σ12σ22σ32 排列这些特征值是 9 , 4 , 1 9,4,1 9,4,1。 U [ 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 ] Σ [ 3 2 1 0 ] V [ 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 ] \pmb U\begin{bmatrix}00\pmb10\\0\pmb100\\\pmb1000\\000\pmb1\end{bmatrix}\kern 15pt\Sigma\begin{bmatrix}\pmb3\\\pmb2\\\pmb1\\0\end{bmatrix}\kern 15pt\pmb V\begin{bmatrix}000\pmb1\\00\pmb10\\0\pmb100\\\pmb1000\end{bmatrix} U 0010010010000001 Σ 3210 V 0001001001001000 U \pmb U U 和 V \pmb V V 的第一列 u 1 \boldsymbol u_1 u1 和 v 1 \boldsymbol v_1 v1 的分量 1 1 1 在第 3 3 3 位和第 4 4 4 位则 u 1 σ 1 v 1 T \boldsymbol u_1\sigma_1\boldsymbol v_1^T u1σ1v1T 就表示矩阵 A A A 中最大的数 A 34 A_{34} A34对于这个极端的例子SVD 的三个秩一矩阵恰好来自于 A A A 中的数字 3 , 2 , 1 3,2,1 3,2,1。 A U Σ V T 3 u 1 v 1 T 2 u 2 v 2 T 1 u 3 v 3 T \pmb{AU\Sigma V^T3\boldsymbol u_1\boldsymbol v_1^T2\boldsymbol u_2\boldsymbol v_2^T1\boldsymbol u_3\boldsymbol v_3^T} AUΣVT3u1v1T2u2v2T1u3v3T 注假设将 A A A 的最后一行全零行去掉则 A A A 是一个 3 × 4 3\times4 3×4 的矩阵 A A T AA^T AAT 是 3 × 3 3\times3 3×3 的矩阵 —— 它的第四行和第四列都会消失 A T A A^TA ATA 和 A A T AA^T AAT 的特征值仍然是 λ 1 , 4 , 9 \lambda1,4,9 λ1,4,9也会在 Σ \Sigma Σ 中得到相同的奇异值 σ 3 , 2 , 1 \sigma3,2,1 σ3,2,1。 A A A 的最后一行的全零行移除后现在变成了 3 × 4 3\times4 3×4 的矩阵也会移除 Σ \Sigma Σ 的最后一行和 U U U 的最后一列。则 ( 3 × 4 ) U Σ V T ( 3 × 3 ) ( 3 × 4 ) ( 4 × 4 ) (3\times4)U\Sigma V^T(3\times3)(3\times4)(4\times4) (3×4)UΣVT(3×3)(3×4)(4×4)SVD 完全适用于长方形矩阵。 一件好的事情是由于矩阵 A A A 的行和列经常有完全不同的含义如电子表格如果要统计所有课程的成绩那么可以用各列表示每个学生的情况而各行表示每个课程的情况则元素 a i j a_{ij} aij 就表示成绩。那么 σ 1 u 1 v 1 T \sigma_1\boldsymbol u_1\boldsymbol v_1^T σ1u1v1T 中 u 1 \boldsymbol u_1 u1 课程组合 v 1 \boldsymbol v_1 v1 学生组合而 σ 1 \sigma_1 σ1 就是这些组合的成绩最高成绩。 矩阵 A A A 也可以对一本杂志中关键词的出现频率计数 A A A 的列是不同的文章每一行代表不同的词那么 A A A 就是整个杂志的索引其中最重要的信息就是 σ 1 u 1 v 1 T \sigma_1\boldsymbol u_1\boldsymbol v_1^T σ1u1v1T σ 1 \sigma_1 σ1 就是高频词 u 1 \boldsymbol u_1 u1 在高频文章 v 1 \boldsymbol v_1 v1 出现的最高的频率。
五、奇异值的稳定性对比特征值的不稳定性
通过 4 × 4 4\times4 4×4 的矩阵 A A A 这个例子一个极端情况我们可以构造出一个特征值不稳定的例子。假设 ( 4 , 1 ) (4,1) (4,1) 元素从零变为 1 / 60000 1/60000 1/60000这个几乎没有变化秩变成了 4 4 4。 A [ 0 1 0 0 0 0 2 0 0 0 0 3 1 60000 0 0 0 ] 仅仅是 1 / 60000 的微小改变 A 的特征值就发生了很大的变化 λ 0 , 0 , 0 , 0 变为了 λ 1 10 , i 10 , − 1 10 , − i 10 A\begin{bmatrix}0100\\0020\\0003\\\displaystyle\frac{1}{60000}000\end{bmatrix}\kern 20pt\begin{array}{l}仅仅是\,1/60000\,的微小改变A\\的特征值就发生了很大的变化\\\lambda0,0,0,0\,变为了\,\pmb{\lambda\displaystyle\frac{1}{10},\frac{i}{10},\frac{-1}{10},\frac{-i}{10}}\end{array} A 000600001100002000030 仅仅是1/60000的微小改变A的特征值就发生了很大的变化λ0,0,0,0变为了λ101,10i,10−1,10−i新元素仅仅变化了 1 / 60000 1/60000 1/60000四个特征值就从零变化到了在复平面上以原点为圆心半径为 1 10 \displaystyle\frac{1}{10} 101 的圆上这表明当 A T A A^TA ATA 远离 A A T AA^T AAT 时特征值严重的不稳定性在另外的极端情况下如果 A T A A A T A^TAAA^T ATAAAT“正规矩阵”那么 A A A 的特征向量正交且 A A A 的特征值完全稳定。 对比之下任意矩阵的奇异值都是稳定的它们不会超过 A A A 的变化。在这个例子中新的奇异值是 3 , 2 , 1 \pmb{3,2,1} 3,2,1 和 1 / 60000 \pmb{1/60000} 1/60000矩阵 U U U 和 V V V 保持不变 A A A 的 SVD 中的第四项是 σ 4 u 4 v 4 T \sigma_4\boldsymbol u_4\boldsymbol v_4^T σ4u4v4T它有十五个零元素和一个小的元素 σ 4 1 / 60000 \sigma_41/60000 σ41/60000。
六、A 的奇异向量和 S A T A SA^TA SATA 的特征向量
式7.2.5-7.2.6同时证明了 SVD奇异向量 v i \boldsymbol v_i vi 是 S A T A SA^TA SATA 的特征向量 q i \boldsymbol q_i qi。 S S S 的特征值 λ i \lambda_i λi 和 A A A 相应的奇异值的平方 σ i 2 \sigma_i^2 σi2 相等 S S S 的秩 r r r 等于 A A A 的秩。特征向量和奇异向量的展开式是完美对应的。 对称矩阵 S S Q Λ Q T λ 1 q 1 q 1 T λ 2 q 2 q 2 T ⋯ λ r q r q r T 任意矩阵 A A U Σ V T σ 1 u 1 v 1 T σ 2 u 2 v 2 T ⋯ σ r u r v r T \begin{array}{l}\pmb{对称矩阵\,S}\kern 25pt\color{blue}SQ\Lambda Q^T\lambda_1\boldsymbol q_1\boldsymbol q_1^T\lambda_2\boldsymbol q_2\boldsymbol q_2^T\cdots\lambda_r\boldsymbol q_r\boldsymbol q_r^T\\\pmb{任意矩阵\,A}\kern 23pt\color{blue}AU\Sigma V^T\sigma_1\boldsymbol u_1\boldsymbol v_1^T\sigma_2\boldsymbol u_2\boldsymbol v_2^T\cdots\sigma_r\boldsymbol u_r\boldsymbol v_r^T\end{array} 对称矩阵SSQΛQTλ1q1q1Tλ2q2q2T⋯λrqrqrT任意矩阵AAUΣVTσ1u1v1Tσ2u2v2T⋯σrurvrT 各个 q i \boldsymbol q_i qi 是正交的各个 u i \boldsymbol u_i ui 是正交的各个 v i \boldsymbol v_i vi 也是正交的非常漂亮 但是还要更深入理解有以下两个原因其一是要弥补特征值部分的短板 如果 λ \lambda λ 是 S S S 的二重特征值我们能够且一定可以找出两个标准正交的向量。另一个原因是要明白 SVD 是如何选出在 σ 2 u 2 v 2 T \sigma_2\boldsymbol u_2\boldsymbol v_2^T σ2u2v2T 之前的最大项 σ 1 u 1 v 1 T \sigma_1\boldsymbol u_1\boldsymbol v_1^T σ1u1v1T。需要理解的是 S S S 的特征值 λ \lambda λ 和 A A A 的奇异值 σ \sigma σ而不只是求出它们。 从 S S S 最大的特征值 λ 1 \lambda_1 λ1 开始它解决了下面的这个问题 λ 1 max x T S x x T x \pmb{\lambda_1\textrm{max}\,\displaystyle\frac{\boldsymbol x^TS\boldsymbol x}{\boldsymbol x^T\boldsymbol x}} λ1maxxTxxTSx这个向量是 x q 1 \boldsymbol x\boldsymbol q_1 xq1且 S q 1 λ 1 q 1 S\boldsymbol q_1\lambda_1\boldsymbol q_1\kern 20pt Sq1λ1q1(7.2.8) \, 对比 A A A 最大的奇异值 σ 1 \sigma_1 σ1它解决的这个问题是 σ 1 max ∣ ∣ A x ∣ ∣ ∣ ∣ x ∣ ∣ \pmb{\sigma_1\max\displaystyle\frac{||A\boldsymbol x||}{||\boldsymbol x||}} σ1max∣∣x∣∣∣∣Ax∣∣这个向量是 x v 1 \boldsymbol x\boldsymbol v_1 xv1 且 A v 1 σ 1 u 1 A\boldsymbol v_1\sigma_1\boldsymbol u_1\kern 20pt Av1σ1u17.2.9 从式7.2.8可以推出7.2.9由于 S A T A SA^TA SATA所以 x T S x x T x x T A T A x x T x ( A x ) T ( A x ) x T x ∣ ∣ A x ∣ ∣ 2 ∣ ∣ x ∣ ∣ 2 σ 2 \displaystyle\frac{\boldsymbol x^TS\boldsymbol x}{\boldsymbol x^T\boldsymbol x}\frac{\boldsymbol x^TA^TA\boldsymbol x}{\boldsymbol x^T\boldsymbol x}\frac{(A\boldsymbol x)^T(A\boldsymbol x)}{\boldsymbol x^T\boldsymbol x}\frac{||A\boldsymbol x||^2}{||\boldsymbol x||^2}\sigma^2 xTxxTSxxTxxTATAxxTx(Ax)T(Ax)∣∣x∣∣2∣∣Ax∣∣2σ2。 这个一次找到一个值的方法也可以适用于 λ 2 \lambda_2 λ2 和 σ 2 \sigma_2 σ2但是并不是任意的 x \boldsymbol x x 都可以 λ 2 max x T S x x T x \pmb{\lambda_2\max\displaystyle\frac{\boldsymbol x^TS\boldsymbol x}{\boldsymbol x^T\boldsymbol x}} λ2maxxTxxTSx其中 x \boldsymbol x x 满足 q 1 T x 0 \boldsymbol q_1^T\boldsymbol x0 q1Tx0最大的是 x q 2 \boldsymbol x\boldsymbol q_2\kern 20pt xq27.2.10 \, σ 2 max ∣ ∣ A x ∣ ∣ ∣ ∣ x ∣ ∣ \pmb{\sigma_2\max\displaystyle\frac{||A\boldsymbol x||}{||\boldsymbol x||}} σ2max∣∣x∣∣∣∣Ax∣∣其中 x \boldsymbol x x 满足 v 1 T x 0 \boldsymbol v_1^T\boldsymbol x0 v1Tx0最大的是 x v 2 \boldsymbol x\boldsymbol v_2\kern 20pt xv27.2.11 当 S A T A SA^TA SATA 时可以得到 λ 1 σ 1 2 \lambda_1\sigma_1^2 λ1σ12 和 λ 2 σ 2 2 \lambda_2\sigma_2^2 λ2σ22为什么这个方法会成功呢 从比值 r ( x ) x T S x x T x r(\boldsymbol x)\displaystyle\frac{\boldsymbol x^TS\boldsymbol x}{\boldsymbol x^T\boldsymbol x} r(x)xTxxTSx 开始这个称为瑞利商Rayleigh quotient要求 r ( x ) r(\boldsymbol x) r(x) 的最大值要令其偏导数为零 ∂ r ∂ x i 0 i 1 , 2 , ⋯ , n \displaystyle\frac{\partial r}{\partial x_i}0i1,2,\cdots,n ∂xi∂r0i1,2,⋯,n。这些导数的求解比较困难下面是结果瑞利商最大时的向量 x \boldsymbol x x 当 S x r ( x ) x 时 r ( x ) x T S x x T x 的偏导数全为零 ( 7.2.12 ) 当\,S\boldsymbol xr(\boldsymbol x)\boldsymbol x\,时\pmb{r(\boldsymbol x)\frac{\boldsymbol x^TS\boldsymbol x}{\boldsymbol x^T\boldsymbol x}\,的偏导数全为零}\kern 20pt(7.2.12) 当Sxr(x)x时r(x)xTxxTSx的偏导数全为零(7.2.12)所以向量 x \boldsymbol x x 是 S S S 的特征向量最大的比值 r ( x ) r(\boldsymbol x) r(x) 就是 S S S 最大的特征值 λ 1 \lambda_1 λ1。下面转而讨论 A A A —— 注意它和 S A T A SA^TA SATA 的联系 最大化 ∣ ∣ A x ∣ ∣ ∣ ∣ x ∣ ∣ 也会最大化 ( ∣ ∣ A x ∣ ∣ ∣ ∣ x ∣ ∣ ) 2 x T A T A x x T x x T S x x x 最大化\,\frac{||A\boldsymbol x||}{||\boldsymbol x||}也会最大化\,\Big(\frac{||A\boldsymbol x||}{||\boldsymbol x||}\Big)^2\frac{\boldsymbol x^TA^TA\boldsymbol x}{\boldsymbol x^T\boldsymbol x}\frac{\boldsymbol x^TS\boldsymbol x}{\boldsymbol x\boldsymbol x} 最大化∣∣x∣∣∣∣Ax∣∣也会最大化(∣∣x∣∣∣∣Ax∣∣)2xTxxTATAxxxxTSx所以式7.2.9中 x v 1 \boldsymbol x\boldsymbol v_1 xv1 与式7.2.8中 S A T A SA^TA SATA 最前面的特征向量 q 1 \boldsymbol q_1 q1 相同。 下面解释为什么式7.2.10和7.2.11中的向量为什么是 q 2 \boldsymbol q_2 q2 和 v 2 \boldsymbol v_2 v2。它们分别与 q 1 \boldsymbol q_1 q1 和 v 1 \boldsymbol v_1 v1 正交因此是在考虑范围内。 任意的正交向量 Q 1 Q_1 Q1 的首列是 q 1 \boldsymbol q_1 q1剩余的 n − 1 n-1 n−1 个标准正交列都与 q 1 \boldsymbol q_1 q1 正交使用 S q 1 λ 1 q 1 S\boldsymbol q_1\lambda_1\boldsymbol q_1 Sq1λ1q1 S Q 1 S [ q 1 q 2 ⋯ q n ] [ q 1 q 2 ⋯ q n ] [ λ 1 w T 0 S n − 1 ] Q 1 [ λ 1 w T 0 S n − 1 ] ( 7.2.13 ) SQ_1S\begin{bmatrix}\boldsymbol q_1\boldsymbol q_2\cdots\boldsymbol q_n\end{bmatrix}\begin{bmatrix}\boldsymbol q_1\boldsymbol q_2\cdots\boldsymbol q_n\end{bmatrix}\begin{bmatrix}\lambda_1\boldsymbol w^T\\\boldsymbol 0S_{n-1}\end{bmatrix}Q_1\begin{bmatrix}\lambda_1\boldsymbol w^T\\\boldsymbol 0S_{n-1}\end{bmatrix}\kern 15pt(7.2.13) SQ1S[q1q2⋯qn][q1q2⋯qn][λ10wTSn−1]Q1[λ10wTSn−1](7.2.13)其中 w T \boldsymbol w^T wT 表示的是 S S S 作用于 q 1 \boldsymbol q_1 q1 S n − 1 S_{n-1} Sn−1 是降维后的矩阵利用矩阵的乘法将它们乘开第一列即 λ 1 q 1 \lambda_1\boldsymbol q_1 λ1q1后面的即为 w T q 1 S n − 1 [ q 2 ⋯ q n ] \boldsymbol w^T\boldsymbol q_1S_{n-1}\begin{bmatrix}\boldsymbol q_2\cdots\boldsymbol q_n\end{bmatrix} wTq1Sn−1[q2⋯qn]。再用 Q 1 T Q_1^T Q1T 左乘上式注意到 Q 1 T Q 1 I Q_1^TQ_1I Q1TQ1I且 Q 1 T S Q 1 Q_1^TSQ_1 Q1TSQ1 是像 S S S 一样的对称矩阵 对称矩阵 Q 1 T S Q 1 [ λ 1 w T 0 S n − 1 ] 将强制 w 0 且 S n − 1 T S n − 1 对称矩阵\,Q_1^TSQ_1\begin{bmatrix}\lambda_1\boldsymbol w^T\\\boldsymbol 0S_{n-1}\end{bmatrix}将强制\,\boldsymbol w\boldsymbol 0\,且\,S^T_{n-1}S_{n-1} 对称矩阵Q1TSQ1[λ10wTSn−1]将强制w0且Sn−1TSn−1根据条件 q 1 T x 0 \boldsymbol q_1^T\boldsymbol x0 q1Tx0 将问题7.2.10的最大值问题简化成了 n − 1 n-1 n−1 阶的情况 S n − 1 S_{n-1} Sn−1 最大的特征值将是 S S S 的第二大特征值就是 λ 2 \lambda_2 λ2式7.2.10中的向量是特征向量 q 2 \boldsymbol q_2 q2 且 S q 2 λ 2 q 2 S\boldsymbol q_2\lambda_2\boldsymbol q_2 Sq2λ2q2。 继续下去或者使用数学归纳法就可以得到所有的特征向量 q 1 , q 2 , ⋯ , q 2 \boldsymbol q_1,\boldsymbol q_2,\cdots,\boldsymbol q_2 q1,q2,⋯,q2 和它们对应的特征值 λ 1 , λ 2 , ⋯ λ n \lambda_1,\lambda_2,\cdots\,\lambda_n λ1,λ2,⋯λn即使存在重复的特征值谱定理 S Q Λ Q T SQ\Lambda Q^T SQΛQT 也可以被证明。所有的对称矩阵都可被对角化。 类似的SVD 可以从式7.2.9和7.2.11中一步一步的得到。下面有一个很重要的问题实际情况中如何计算 λ \lambda λ 和 σ \sigma σ 呢
七、计算 S 的特征值和 A 的奇异值 A A A 的奇异值 σ i \sigma_i σi 是 S A T A SA^TA SATA 特征值 λ i \lambda_i λi 的算术平方根这个将 SVD 和对称矩阵的特征值问题联系了起来这个很好但是我们不想使用 A T A A^TA ATA 乘 A A A因为这个运算非常耗时这个很不好。 首先想到的是尽可能将 A A A 和 S S S 的元素都变成零而不改变任何的 σ \sigma σ 和 λ \lambda λ。奇异向量和特征向量会改变 —— 这个没有问题。相似矩阵 Q − 1 S Q Q^{-1}SQ Q−1SQ 和 S S S 的特征值 λ \lambda λ 相同如果 S S S 正交那么这个矩阵就是 Q T S Q Q^TSQ QTSQ 也是对称的。 对于二阶的对称矩阵可以构造出 2 × 2 2\times2 2×2 的旋转矩阵 Q Q Q使得 Q T S Q Q^TSQ QTSQ 是对称的三对角矩阵symmetric and tridiagonal matrix它含有大量的零元素但是旋转无法保证总能得到对角矩阵所以要想求得 S S S 所有的特征值需要新的方法。 对于 SVD和 Q T S Q Q^TSQ QTSQ 相对应的是什么我们不想改变 A A A 任何的奇异值那么就是在 A A A 的两边分别乘上不同的正交矩阵 Q 1 Q_1 Q1 和 Q 2 Q_2 Q2利用这两个在矩阵 Q 1 T A Q 2 Q_1^TAQ_2 Q1TAQ2 中生成零元素而 σ \sigma σ 不会改变 ( Q 1 T A Q 2 ) T ( Q 1 T A Q 2 ) Q 2 T A T A Q 2 Q 2 T S Q 2 得到相同的 σ ( A ) 和 λ ( S ) (Q_1^TAQ_2)^T(Q_1^TAQ_2)Q_2^TA^TAQ_2Q_2^TSQ_2\kern 10pt得到相同的\,\sigma(A)\,和\,\lambda(S) (Q1TAQ2)T(Q1TAQ2)Q2TATAQ2Q2TSQ2得到相同的σ(A)和λ(S)两个自由选取的 Q Q Q 将可以使得 Q 1 T A Q 2 Q_1^TAQ_2 Q1TAQ2 为两对角矩阵bidiagonal matrix这个完美对应了 Q T S Q Q^TSQ QTSQ 是三对角矩阵它们之间的联系是 ( 两对角矩阵 ) T ( 两对角矩阵 ) 三对角矩阵 (两对角矩阵)^T(两对角矩阵)三对角矩阵 (两对角矩阵)T(两对角矩阵)三对角矩阵。 最后要算出对角矩阵 Λ \Lambda Λ 和对角矩阵 Σ \Sigma Σ 的步骤需要更多的新思路这个也不简单因为有些要解的 det ( S − λ I ) 0 \det(S-\lambda I)0 det(S−λI)0 是 n 100 n100 n100 或 1000 1000 1000 甚至是更多次数的多项式而我们不可能去求解这些多项式 LAPACK 中求解 λ \lambda λ 和 σ \sigma σ 是使用简单的正交矩阵来逼近 Q T S Q Λ Q^TSQ\Lambda QTSQΛ 和 U T A V Σ U^TAV\Sigma UTAVΣ当很接近 Λ \Lambda Λ 和 Σ \Sigma Σ 时就停止。 这两步先是零元素方法在指令 eig(S) 和 svd(A) 中内置了。
八、主要内容总结
SVD 将 A A A 分解成 U Σ V T U\Sigma V^T UΣVT共有 r r r 个奇异值 σ 1 ≥ σ 2 ≥ ⋯ ≥ σ r 0 \sigma_1\geq\sigma_2\geq\cdots\geq\sigma_r0 σ1≥σ2≥⋯≥σr0.数值 σ 1 2 , σ 2 2 , ⋯ , σ r 2 \sigma_1^2,\sigma_2^2,\cdots,\sigma_r^2 σ12,σ22,⋯,σr2 是 A A T AA^T AAT 和 A T A A^TA ATA 非零的特征值。 U U U 和 V V V 的标准正交列是 A A T AA^T AAT 和 A T A A^TA ATA 的特征向量。这些列包含了矩阵 A A A 四个基本子空间的标准正交基。这些基对角化矩阵 A A A A v i σ i u i , i ≤ r A\boldsymbol v_i\sigma_i\boldsymbol u_i,\,i\leq r Aviσiui,i≤r即是 A V U Σ \pmb{AVU\Sigma} AVUΣ. A σ 1 u 1 v 1 T σ 2 u 2 v 2 T ⋯ σ r u r v r T A\sigma_1\boldsymbol u_1\boldsymbol v_1^T\sigma_2\boldsymbol u_2\boldsymbol v_2^T\cdots\sigma_r\boldsymbol u_r\boldsymbol v_r^T Aσ1u1v1Tσ2u2v2T⋯σrurvrT其中 σ 1 \sigma_1 σ1 是比值 ∣ ∣ A x ∣ ∣ ∣ ∣ x ∣ ∣ \displaystyle\frac{||A\boldsymbol x||}{||\boldsymbol x||} ∣∣x∣∣∣∣Ax∣∣ 的最大值。
九、例题
【例4】识别出下列将 A A A 分解成列乘行的和的分解方式的类型 1. 正交列 u 1 σ 1 , u 2 σ 2 , ⋯ , u r σ r 乘 标准正交行 v 1 T , v 2 T , ⋯ , v r T 2. 标准正交列 q 1 , q 2 , ⋯ , q r 乘 三角形矩阵的行 r 1 T , r 2 T , ⋯ , r r T 3. 三角形矩阵的列 l 1 , l 2 , ⋯ , l r 乘 三角形矩阵的行 u 1 T , u 2 T ⋯ , u r T \begin{array}{llll}1.\,正交列\boldsymbol u_1\sigma_1,\boldsymbol u_2\sigma_2,\cdots,\boldsymbol u_r\sigma_r乘标准正交行\boldsymbol v_1^T,\boldsymbol v_2^T,\cdots,\boldsymbol v_r^T\\2.\,标准正交列\boldsymbol q_1,\boldsymbol q_2,\cdots,\boldsymbol q_r乘三角形矩阵的行\boldsymbol r_1^T,\boldsymbol r_2^T,\cdots,\boldsymbol r_r^T\\3.\,三角形矩阵的列\boldsymbol l_1,\boldsymbol l_2,\cdots,\boldsymbol l_r乘三角形矩阵的行\boldsymbol u_1^T,\boldsymbol u_2^T\cdots,\boldsymbol u_r^T\end{array} 1.正交列2.标准正交列3.三角形矩阵的列u1σ1,u2σ2,⋯,urσrq1,q2,⋯,qrl1,l2,⋯,lr乘乘乘标准正交行三角形矩阵的行三角形矩阵的行v1T,v2T,⋯,vrTr1T,r2T,⋯,rrTu1T,u2T⋯,urT A A A 的秩、主元和奇异值在上述分解中的哪里出现 解 这三种分解不管是对理论数学还是应用数学中的线性代数都是基础
奇异值分解 Singular Value Decompositon A U Σ V T \pmb{AU\Sigma V^T} AUΣVT格拉姆-施密特正交化 Gram-Schmidt Orthogonalization A Q R \pmb{AQR} AQR高斯消元法 Gaussian Elimination A L U \pmb{ALU} ALU
可以将奇异值 σ i \pmb{\sigma_i} σi、高度 h i \pmb{h_i} hi 和主元 d i \pmb{d_i} di 单独表示 A U Σ V T AU\Sigma V^T AUΣVT其中 U U U 和 V V V 的列都是单位向量 r r r 个奇异值 σ i \sigma_i σi 在 Σ \Sigma Σ 中. A Q H R AQHR AQHR其中 Q Q Q 的列是单位向量 R R R 中的对角元素都是 1 1 1 r r r 个高度 h i h_i hi 在 H H H 中. A L D U ALDU ALDU其中 L L L 和 U U U 的对角元素都是 1 1 1 r r r 个主元在 D D D 中.
每个 h i h_i hi 表示第 i i i 列到由第 1 , 2 , ⋯ , i − 1 1,2,\cdots,i-1 1,2,⋯,i−1 列所形成平面的高度当 r m n rmn rmn 时 n n n 维的 “平行多面体”以 A A A 各列为同一顶点处的棱的体积可以由 A U Σ V T L D U Q H R AU\Sigma V^TLDUQHR AUΣVTLDUQHR 求得 ∣ det A ∣ ∣ σ i 的乘积 ∣ ∣ d i 的乘积 ∣ ∣ h i 的乘积 ∣ \pmb{|\det A||\sigma_i 的乘积||d_i\,的乘积||h_i\,的乘积|} ∣detA∣∣σi的乘积∣∣di的乘积∣∣hi的乘积∣【例5】证明 σ 1 ≥ ∣ λ ∣ max \pmb{\sigma_1\ge|\lambda|_{\textrm{max}}} σ1≥∣λ∣max最大的奇异值大于或等于所有的特征值。 证明 由 A U Σ V T AU\Sigma V^T AUΣVT注意到左乘一个正交矩阵并不改变这个向量的长度 ∣ ∣ Q x ∣ ∣ ∣ ∣ x ∣ ∣ ||Q\boldsymbol x||||\boldsymbol x|| ∣∣Qx∣∣∣∣x∣∣这是因为 ∣ ∣ Q x ∣ ∣ 2 x T Q T Q x x T x ∣ ∣ x ∣ ∣ 2 ||Q\boldsymbol x||^2\boldsymbol x^TQ^TQ\boldsymbol x\boldsymbol x^T\boldsymbol x||\boldsymbol x||^2 ∣∣Qx∣∣2xTQTQxxTx∣∣x∣∣2这个也适用于 Q U QU QU 和 Q V T QV^T QVT这两个矩阵的中间是对角矩阵 Σ \Sigma Σ ∣ ∣ A x ∣ ∣ ∣ ∣ U Σ V T x ∣ ∣ ∣ ∣ Σ V T x ∣ ∣ ≤ σ 1 ∣ ∣ V T x ∣ ∣ σ 1 ∣ ∣ x ∣ ∣ ( 7.2.14 ) ||A\boldsymbol x||||U\Sigma V^T\boldsymbol x||||\Sigma V^T\boldsymbol x||\le\sigma_1||V^T\boldsymbol x||\sigma_1||\boldsymbol x||\kern 20pt(7.2.14) ∣∣Ax∣∣∣∣UΣVTx∣∣∣∣ΣVTx∣∣≤σ1∣∣VTx∣∣σ1∣∣x∣∣(7.2.14)特征向量满足 ∣ ∣ A x ∣ ∣ ∣ λ ∣ ∣ ∣ x ∣ ∣ ||A\boldsymbol x|||\lambda|||\boldsymbol x|| ∣∣Ax∣∣∣λ∣∣∣x∣∣所以式7.2.14表明 ∣ λ ∣ ∣ ∣ x ∣ ∣ ≤ σ 1 ∣ ∣ x ∣ ∣ |\lambda|||\boldsymbol x||\le\sigma_1||\boldsymbol x|| ∣λ∣∣∣x∣∣≤σ1∣∣x∣∣所以 ∣ λ ∣ ≤ σ 1 \pmb{|\lambda|\le\sigma_1} ∣λ∣≤σ1. 取 x ( 1 , 0 , ⋯ , 0 ) \boldsymbol x(1,0,\cdots,0) x(1,0,⋯,0) 为单位向量则 A x A\boldsymbol x Ax 就是 A A A 的第一列然后由不等式7.2.14可得这列的长度小于或等于 σ 1 \sigma_1 σ1。所以 A A A 的每个元素都有 ∣ a i j ∣ ≤ σ 1 |a_{ij}|\le\sigma_1 ∣aij∣≤σ1. 式7.2.14再次证明了 ∣ ∣ A x ∣ ∣ ∣ ∣ x ∣ ∣ \displaystyle\frac{||A\boldsymbol x||}{||\boldsymbol x||} ∣∣x∣∣∣∣Ax∣∣ 的最大值等于 σ 1 \sigma_1 σ1. 在求解 A x b A\boldsymbol x\boldsymbol b Axb 时条件数condition number σ max σ min \displaystyle\frac{\sigma_{\textrm{max}}}{\sigma_{\textrm{min}}} σminσmax 控制舍入的误差如果条件数太大那么 MATLAB 会警告此时的 x \boldsymbol x x 不可靠。
