第三讲 线性最小二乘问题 1 问题介绍 2 初等变换矩阵 3 QR分解 4 奇异值分解 5 线性最小二乘问题的求解方法 6 最小二乘问题的推广及其应用* 现代数位分析（数值线性代数），潘建瑜 http://math.ecnu.edu.cn/~jypan
第三讲 线性最小二乘问题 1 问题介绍 2 初等变换矩阵 3 QR 分解 4 奇异值分解 5 线性最小二乘问题的求解方法 6 最小二乘问题的推广及其应用 ∗ 现代数值分析（数值线性代数）, 潘建瑜 http://math.ecnu.edu.cn/~jypan
4‖ 秦 奇异值分解 4.1奇异值，奇异向量和奇异值分解 4.2奇异值基本性质 4.3奇异值更多性质* http://math.ecnu.edu.cn/~jypan 2/38
4 奇异值分解 4.1 奇异值，奇异向量和奇异值分解 4.2 奇异值基本性质 4.3 奇异值更多性质 ∗ http://math.ecnu.edu.cn/~jypan 2/38
秦 4.1 奇异值，奇异向量和奇异值分解 奇异值分解(SVD)分解是矩阵计算中非常有用的工具之一 定理(SVD)设A∈Cmxn(m≥n),则存在酉矩阵U∈Cmxm和V∈Cnxn 使得 UAV= 或A=U V* 其中∑=diag(o1,o2,,0n)∈Rnxn,且o1≥.…≥on≥0. 上述分解称为A的奇异值分解(SVD),O1,02,,0n称为A的奇异值，它们 是矩阵AA的特征值的平方根， (板书) 西在不做特别说明的情况下，我们总是假定o1≥02≥··≥0n≥0. 西如果A∈Rm×n是实矩阵，则U,V也都可以是实矩阵 http://math.ecnu.edu.cn/~jypan 3/38
4.1 奇异值，奇异向量和奇异值分解 奇异值分解 (SVD) 分解是矩阵计算中非常有用的工具之一. 定理 (SVD) 设 A ∈ C m×n (m ≥ n), 则存在酉矩阵 U ∈ C m×m 和 V ∈ C n×n 使得 U ∗AV = Σ 0 或 A = U Σ 0 V ∗ , 其中 Σ = diag(σ1, σ2, . . . , σn) ∈ R n×n , 且 σ1 ≥ . . . ≥ σn ≥ 0. 上述分解称为 A 的奇异值分解 (SVD) , σ1, σ2, . . . , σn 称为 A 的奇异值, 它们 是矩阵 A∗A 的特征值的平方根. (板书) ✍ 在不做特别说明的情况下, 我们总是假定 σ1 ≥ σ2 ≥ · · · ≥ σn ≥ 0. ✍ 如果 A ∈ R m×n 是实矩阵, 则 U, V 也都可以是实矩阵. http://math.ecnu.edu.cn/~jypan 3/38
秦 奇异向量 矩阵U=[u1,2,,um和V=[y1,2,,vn的列向量分别称为A的 左奇异向量和右奇异向量，即存在关系式 A=0ii,i=1,2,.,n, A*u=0Ui,i=1,2,..,n A*i=0,i=n+1,n+2,..,m. http://math.ecnu.edu.cn/~jypan 4/38
奇异向量 矩阵 U = [u1, u2, . . . , um] 和 V = [v1, v2, . . . , vn] 的列向量分别称为 A 的 左奇异向量 和 右奇异向量 , 即存在关系式 Avi = σiui , i = 1, 2, . . . , n, A ∗ui = σivi , i = 1, 2, . . . , n, A ∗ui = 0, i = n + 1, n + 2, . . . , m. http://math.ecnu.edu.cn/~jypan 4/38
秦 SVD的其他形式 A=U V*=01山1v1+2u2v吃+十OnUnV晴 记Un=[u1,2,…,unJ∈Cmxm,则Un是单位列正交矩阵，且 A=UnEV* (3.1) 这就是所谓的细SVD (thin SVD)或 降阶SVD (reduced SVD),有的文献 将(3.1)称为奇异值分解。 当k<n时，我们称 Ak=01山11+02u2陵+·+0kukW 为A的截断SVD (truncated SVD). http://math.ecnu.edu.cn/~jypan 5/38
SVD 的其他形式 A = U Σ 0 V ∗ = σ1u1v ∗ 1 + σ2u2v ∗ 2 + · · · + σnunv ∗ n 记 Un = [u1, u2, . . . , un] ∈ C m×n , 则 Un 是单位列正交矩阵, 且 A = UnΣV ∗ (3.1) 这就是所谓的 细 SVD (thin SVD ) 或 降阶 SVD (reduced SVD ), 有的文献 将 (3.1) 称为奇异值分解. 当 k < n 时, 我们称 Ak = σ1u1v ∗ 1 + σ2u2v ∗ 2 + · · · + σkukv ∗ k 为 A 的 截断 SVD (truncated SVD ). http://math.ecnu.edu.cn/~jypan 5/38
秦 4.2 奇异值基本性质 定理设A= V* 是A∈Cmxn(m≥n)的奇异值分解，则 (1)A*A的特征值是σ？，对应的特征向量是5 (2)AA*的特征值是a和m-n个零，对应的特征向量是 (3)|A2=01,AlF=V0+o吃+·+o (4若rank(A=r≤n,则Ran(A)=span{u1,u2,,ur} Ker(A)=span{ur+1,Ur+2,...,Un (⑤)设x∈Cn且xll2=1,则on≤‖Az2≤o1 (⑥（酉不变性）设X∈Cmxm和Y∈Cnxn是酉矩阵，则o(X*AY)=o(A). (证明留作练习) http://math.ecnu.edu.cn/~jypan 6/38
4.2 奇异值基本性质 定理 设 A = U " Σ 0 # V ∗ 是 A ∈ C m×n (m ≥ n) 的奇异值分解, 则 (1) A∗A 的特征值是 σ 2 i , 对应的特征向量是 vi (2) AA∗ 的特征值是 σ 2 i 和 m − n 个零, 对应的特征向量是 ui (3) ∥A∥2 = σ1, ∥A∥F = p σ 2 1 + σ 2 2 + · · · + σ 2 n ; (4) 若 rank(A) = r ≤ n, 则 Ran(A) = span{u1, u2, . . . , ur}, Ker(A) = span{vr+1, vr+2, . . . , vn} (5) 设 x ∈ C n 且 ∥x∥2 = 1, 则 σn ≤ ∥Ax∥2 ≤ σ1; (6) (酉不变性) 设 X ∈ C m×m 和 Y ∈ C n×n 是酉矩阵, 则 σi(X∗AY ) = σi(A). (证明留作练习) http://math.ecnu.edu.cn/~jypan 6/38
秦 定理设A=UV*是A∈Cnxn的奇异值分解，则： (1)|det(A)川=o12…0n (2)若A非奇异，则A-12=om1,2(A)=o1/an (3)若A是Hermite的，且A=UAU*是A的酉特征值分解，设A≥ |2≥·≥入，则A=UV是A的奇异值分解，其中o=A, =sign(i)u,若入i=0,则取=u: 0A* Vi (4)矩阵 的特征值是士，对应单位特征向量 0 士ui (证明留作练习) 西矩阵条件数取决于奇异值，不是特征值，见讲义上的例子 (特征值都是1，但其谱条件数却随着矩阵规模的增长而快速变大). http://math.ecnu.edu.cn/~jypan 7/38
定理 设 A = UΣV ∗ 是 A ∈ C n×n 的奇异值分解, 则: (1) | det(A)| = σ1σ2 · · · σn; (2) 若 A 非奇异, 则 ∥A−1∥2 = σ −1 n , κ2(A) = σ1/σn; (3) 若 A 是 Hermite 的, 且 A = UΛU ∗ 是 A 的酉特征值分解, 设 |λ1| ≥ |λ2| ≥ · · · ≥ |λn|, 则 A = UΣV 是 A 的奇异值分解, 其中 σi = |λi |, vi = sign(λi)ui , 若 λi = 0, 则取 vi = ui ; (4) 矩阵 0 A∗ A 0 的特征值是 ±σi , 对应单位特征向量 1 √ 2 vi ±ui . (证明留作练习) ✍ 矩阵条件数取决于奇异值, 不是特征值, 见讲义上的例子 (特征值都是 1, 但其谱条件数却随着矩阵规模的增长而快速变大). http://math.ecnu.edu.cn/~jypan 7/38
秦 4.3 奇异值更多性质 定理（低秩逼近）设A=Um∑V*是A∈Cmxn的细奇异值分解.令 Ak=∑0u i=1 则A是 min A-Bll2 B∈Cmxn,rank(B)=k 的一个解，且 IA-Akll2=0k+1. 此时，我们称Ak是A的一个秩k逼近 对于Frobenius范数，我们有类似的结论。 *本小节内容只需了解 http://math.ecnu.edu.cn/~jypan 8/38
4.3 奇异值更多性质 ∗ 定理 (低秩逼近) 设 A = UnΣV ∗ 是 A ∈ C m×n 的细奇异值分解. 令 Ak = X k i=1 σiuiv ∗ i , 则 Ak 是 min B∈Cm×n, rank(B)=k ∥A − B∥2 的一个解, 且 ∥A − Ak∥2 = σk+1. 此时, 我们称 Ak 是 A 的一个秩 k 逼近. ✍ 对于 Frobenius 范数, 我们有类似的结论。 ∗ 本小节内容只需了解 http://math.ecnu.edu.cn/~jypan 8/38
秦 引理（交错不等式）设A∈Cmxn,A,是由A去除r列（或r行）后得到的子 矩阵，则 o(A)≥o(Ar)≥o+r(A),i=1,2,,min{m,n} 这里，当下标k大于矩阵的维数时，我们令σk=0. 更进一步，如果B∈Cm-r)×(n-)是A的子矩阵，则 0(A)20(B)≥0+r+s(A): http://math.ecnu.edu.cn/~jypan 9/38
引理 (交错不等式) 设 A ∈ C m×n , Ar 是由 A 去除 r 列 (或 r 行) 后得到的子 矩阵, 则 σi(A) ≥ σi(Ar) ≥ σi+r(A), i = 1, 2, . . . , min{m, n}. 这里, 当下标 k 大于矩阵的维数时, 我们令 σk = 0. 更进一步, 如果 B ∈ C (m−r)×(n−s) 是 A 的子矩阵, 则 σi(A) ≥ σi(B) ≥ σi+r+s(A). http://math.ecnu.edu.cn/~jypan 9/38
秦 引理设A∈Cnxm,1≤k≤n,则对任意的单位列正交矩阵U∈Cnxk和 V∈Cnxk,有 oi(UAVk)<i(A),i=1,2,...,k. (3.2) 因此， |det(UA)引≤(A)o2(A)·ok(A) (3.3) 定理(Wel不等式，1949)设A∈Cnx”,其奇异值和特征值分别为o1≥02≥ …2on≥0和l入l≥l2l≥…≥|入nl.则 |入1入2…k|≤0102…0k,k=1,2,,n 且当k=n时，等号成立. http://math.ecnu.edu.cn/~jypan 10/38
引理 设 A ∈ C n×n , 1 ≤ k ≤ n, 则对任意的单位列正交矩阵 Uk ∈ C n×k 和 Vk ∈ C n×k , 有 σi(U ∗ kAVk) ≤ σi(A), i = 1, 2, . . . , k. (3.2) 因此, | det(U ∗ kAVk)| ≤ σ1(A)σ2(A)· · · σk(A). (3.3) 定理 (Weyl 不等式, 1949) 设 A ∈ C n×n , 其奇异值和特征值分别为 σ1 ≥ σ2 ≥ · · · ≥ σn ≥ 0 和 |λ1| ≥ |λ2| ≥ · · · ≥ |λn|. 则 |λ1λ2 · · · λk| ≤ σ1σ2 · · · σk, k = 1, 2, . . . , n 且当 k = n 时, 等号成立. http://math.ecnu.edu.cn/~jypan 10/38