第三讲线性最小二乘问题最小二乘问题（LeastSquares）包括线性最小二乘问题，总体最小二乘问题，等式约束最小二乘问题，刚性加权最小二乘问题等等.它在统计学，最优化问题，材料与结构力学，信号与图像处理等方面都有着广泛的应用，是计算数学的一个重要研究分支，也是一个活跃的研究领域本讲主要介绍求解线性最小二乘问题的三种常用方法：正规方程法（也称法方程法），QR分解法和SVD分解法，一般来说，正规方程法是最快的，特别是当A的条件数较小时，正规方程法几乎与其他方法一样精确.而SVD分解法是最慢的，但结果最可靠为了方便起见，我们有时将线性最小二乘问题（3.1）简称为最小二乘问题关于最小二乘问题的相关参考资料AkeBjorck,Numerical MethodsforLeastSquaresProblems,1996[16]魏木生，李莹，赵建立，广义最小二乘问题的理论与计算（第二版),2020[149]3.1问题介绍考虑线性最小二乘问题min I/Ar - bll2(3.1)其中ARmxn，beRm.问题(3.1)的解称为最小二乘解当m=n且A非奇异时，这就是一个线性方程组，解为r*=A-1b;·当m>n时，约束个数大于未知量个数，此时我们称问题（3.1)为超定的·当m<n时，未知量个数大于约束个数，此时我们称问题(3.1)为欠定(或亚定)的.为了讨论方便，本讲假定A是满秩的3.1.1超定方程组当m>n时，线性方程组Ar=b的解可能不存在.此时一般考虑求解最小二乘问题（3.1).记J(r)≤Ar-b易知J）是关于的二次函数，而且是凸函数（当A满秩时，J(a）的Hessen阵是正定的).因此由凸函数的性质可知，是问题(3.1)的解当且仅当是J(）的稳定点。令其一阶导数为零，可得AT AT - ATb = 0.于是将最小二乘问题转化为一个线性方程组，这就是后面的正规方程82
第三讲 线性最小二乘问题 最小二乘问题 (Least Squares ) 包括线性最小二乘问题, 总体最小二乘问题, 等式约束最小二 乘问题, 刚性加权最小二乘问题等等. 它在统计学, 最优化问题, 材料与结构力学, 信号与图像处理 等方面都有着广泛的应用, 是计算数学的一个重要研究分支, 也是一个活跃的研究领域. 本讲主要介绍求解线性最小二乘问题的三种常用方法: 正规方程法 (也称法方程法), QR 分解 法和 SVD 分解法. 一般来说, 正规方程法是最快的, 特别是当 A 的条件数较小时, 正规方程法几 乎与其他方法一样精确. 而 SVD 分解法是最慢的, 但结果最可靠. 为了方便起见, 我们有时将线性最小二乘问题 (3.1) 简称为最小二乘问题. 关于最小二乘问题的相关参考资料 ▶ Åke Björck, Numerical Methods for Least Squares Problems, 1996 [16] ▶ 魏木生, 李莹, 赵建立, 广义最小二乘问题的理论与计算 (第二版), 2020 [149] 3.1 问题介绍 考虑线性最小二乘问题 min x∈Rn ∥Ax − b∥ 2 2 , (3.1) 其中 A ∈ R m×n , b ∈ R m. 问题 (3.1) 的解称为最小二乘解. • 当 m = n 且 A 非奇异时, 这就是一个线性方程组, 解为 x∗ = A−1 b; • 当 m > n 时, 约束个数大于未知量个数, 此时我们称问题 (3.1) 为超定的; • 当 m < n 时, 未知量个数大于约束个数, 此时我们称问题 (3.1) 为欠定 (或亚定) 的. b 为了讨论方便, 本讲假定 A 是满秩的. 3.1.1 超定方程组 当 m > n 时, 线性方程组 Ax = b 的解可能不存在. 此时一般考虑求解最小二乘问题 (3.1). 记 J(x) ≜ ∥Ax − b∥ 2 2 . 易知 J(x) 是关于 x 的二次函数, 而且是凸函数 (当 A 满秩时, J(x) 的 Hessen 阵是正定的). 因此, 由凸函数的性质可知, x∗ 是问题 (3.1) 的解当且仅当 x∗ 是 J(x) 的稳定点. 令其一阶导数为零, 可 得 A TAx − A T b = 0. 于是将最小二乘问题转化为一个线性方程组, 这就是后面的正规方程. 82
3.1问题介绍·83.如果 A不是满秩,则 ATA半正定,此时解不唯一3.1.2欠定方程组若m<n，则线性方程组Ar=b存在无穷多个解（假定A满秩）.这时我们通常寻求最小范数解，即所有解中范数最小的解.于是原问题就转化为下面的约束优化问题(3.2)对应的Lagrange函数为C(a, ) =,llal2 + T(Ar - b),其中入=[△1,入2,….,入m]T是Lagrange乘子.此时优化问题(3.2)的解就是C(α,)的鞍点，即下面方程组的解：acac=T+AT=0,=Ar-b=0.drx写成矩阵形式为[ -如果A满秩，即rank(A)=m，则系数矩阵非奇异（见练习3.1)，上述方程组存在唯一解本讲主要讨论超定线性最小二乘问题的求解
3.1 问题介绍 · 83 · b 如果 A 不是满秩, 则 ATA 半正定, 此时解不唯一. 3.1.2 欠定方程组 若 m < n, 则线性方程组 Ax = b 存在无穷多个解 (假定 A 满秩). 这时我们通常寻求最小范 数解, 即所有解中范数最小的解. 于是原问题就转化为下面的约束优化问题 min Ax=b 1 2 ∥x∥ 2 2 (3.2) 对应的 Lagrange 函数为 L(x, λ) = 1 2 ∥x∥ 2 2 + λ T (Ax − b), 其中 λ = [λ1, λ2, . . . , λm] T 是 Lagrange 乘子. 此时优化问题 (3.2) 的解就是 L(x, λ) 的鞍点, 即下 面方程组的解: ∂L ∂x = x + A Tλ = 0, ∂L ∂λ = Ax − b = 0. 写成矩阵形式为 " I AT A 0 # "x λ # = " 0 b # . 如果 A 满秩, 即 rank(A) = m, 则系数矩阵非奇异 (见练习 3.1), 上述方程组存在唯一解. 本讲主要讨论超定线性最小二乘问题的求解
-84第三讲线性最小二乘问题3.2几类重要的矩阵变换矩阵计算的一个基本思想就是把复杂的问题转化为等价的且易于求解的问题.完成这个转化的基本工具就是矩阵变换，除了高等代数（或线性代数）中提到的三类初等变换以外，在矩阵计算中常用的矩阵变换还有：Gauss变换，Householder变换和Givens变换，其中Gauss变换主要用于矩阵的LU分解，Householder变换和Givens变换是正交变换，可用于计算线性最小二乘问题、矩阵特征值和奇异值问题等3.2.1初等矩阵变换本科高等代数教材中介绍了三类初等矩阵变换，这里将其推广到更一般的情形我们称E(u, V, T) = I - Tuu*(3.3)为初等矩阵变换或初等矩阵，其中u.uECn是非零向量，T是一个非零复数.因此.初等矩阵是单位矩阵的一个秩1修正高等代数中介绍的三类初等变换(elementarytransformation）分别是（以行变换为例)：（1）交换两行；(2)某行乘以一个非零常数；（3）某行乘以一个常数后加到另外一行.这三类变换所对应的矩阵为（简单示例）110Ei =, E2 =E3=1可以验证，它们都可以表示为（3.3）形式，留作练习.下面的定理给出了初等矩阵的基本性质定理3.1设E(u,U,T）是一个初等矩阵，我们有(1) det(E(u,v, T)) = 1 - Tu*u;(2)若1-Tu*u≠0,则E(u,U,T)非奇异,且(E(u,U, T)-1=E(u, U,), 其中 =TU*u-1(3)对任意非零向量a,yECn,存在u,ECn和TEC,使得E(u,u, T)r = y(板书)证明.(1)易知[3 [- ][ [ ]由行列式的乘法可知d( ) ([- ]) ([) ([β - )
· 84 · 第三讲 线性最小二乘问题 3.2 几类重要的矩阵变换 矩阵计算的一个基本思想就是把复杂的问题转化为等价的且易于求解的问题. 完成这个转化 的基本工具就是矩阵变换, 除了高等代数 (或线性代数) 中提到的三类初等变换以外, 在矩阵计算 中常用的矩阵变换还有: Gauss 变换, Householder 变换和 Givens 变换, 其中 Gauss 变换主要用于矩 阵的 LU 分解, Householder 变换和 Givens 变换是正交变换, 可用于计算线性最小二乘问题、矩阵 特征值和奇异值问题等. 3.2.1 初等矩阵变换 本科高等代数教材中介绍了三类初等矩阵变换, 这里将其推广到更一般的情形. 我们称 E(u, v, τ ) = I − τuv∗ (3.3) 为初等矩阵变换或初等矩阵, 其中 u, v ∈ C n 是非零向量, τ 是一个非零复数. 因此, 初等矩阵是单 位矩阵的一个秩 1 修正. b 高等代数中介绍的三类初等变换 (elementary transformation) 分别是 (以行变换为例): (1) 交 换两行; (2) 某行乘以一个非零常数; (3) 某行乘以一个常数后加到另外一行. 这三类变换所 对应的矩阵为 (简单示例) E1 = 1 . . . 0 1 . . . 1 0 . . . 1 , E2 = 1 . . . 1 c 1 . . . 1 , E3 = 1 . . . 1 . . . c 1 . . . 1 . 可以验证, 它们都可以表示为 (3.3) 形式, 留作练习. 下面的定理给出了初等矩阵的基本性质. 定理 3.1 设 E(u, v, τ ) 是一个初等矩阵, 我们有 (1) det(E(u, v, τ )) = 1 − τv∗u; (2) 若 1 − τv∗u ̸= 0, 则 E(u, v, τ ) 非奇异, 且 (E(u, v, τ ))−1 = E(u, v, γ), 其中 γ = τ τv∗u − 1 . (3) 对任意非零向量 x, y ∈ C n , 存在 u, v ∈ C n 和 τ ∈ C, 使得 E(u, v, τ )x = y. (板书) 证明. (1) 易知 " I 0 v ∗ 1 # "I − τuv∗ −τu 0 1 # " I 0 −v ∗ 1 # = " I −τu 0 1 − τv∗u # . 由行列式的乘法可知 det " I 0 v ∗ 1 #! · det "I − τuv∗ −τu 0 1 #! · det " I 0 −v ∗ 1 #! = det "I −τu 0 1 − τv∗u #!
3.2几类重要的矩阵变换·85.所以det (E(u, v, T) = det(I - Tuu*) = 1 - Tu*u(2)若1-Tu*u≠0,则 det(E(u,U,T)≠0,所以E(u,U,T)非奇异.通过直接计算可知E(u,V,T)E(u, V,) = I - Tu* -(1 - Tu*u)u*(1 -Tu*u)u*= I - Tuv*-TU*u-1= 1.(3)留作练习.更一般地，我们有下面的结论Sylverster降幂公式设 AE Cmxn,BE Cnxm,其中m≥n,则有det(^I - AB) = ^m-n det(^I - BA)(3.4)因此AB和BA具有相同的非零特征值（留作练习）定理3.2设AECnxn，则A非奇异当且仅当A可以分解成若干个初等矩阵的乘积3.2.2Gauss变换设lj=[0,..,0,lj+1j,.,lnj]j=1,2,n,则Gauss变换定义为1L(t) ≤ E(lj,ej, -1) = I + lje, :li+1j1..In.j1显然,Gauss变换也属于初等矩阵变换.向量l,称为Gauss向量[57].由定理3.1可知det(L(,)) = 1, (L(,)-1 = E(lj,ej,1) = E(-lj,ej -1) = L(-lj)Gauss变换是对单位矩阵的秩1修正，主要功能是消零，即将指定的某些元素变为零Gauss变换有时也称为初等下三角矩阵3.2.3Householder变换
3.2 几类重要的矩阵变换 · 85 · 所以 det E(u, v, τ ) = det(I − τuv∗ ) = 1 − τv∗u. (2) 若 1 − τv∗u ̸= 0, 则 det E(u, v, τ ) ̸= 0, 所以 E(u, v, τ ) 非奇异. 通过直接计算可知 E(u, v, τ )E(u, v, γ) = I − τuv∗ − γ(1 − τv∗u)uv∗ = I − τuv∗ − τ τv∗u − 1 (1 − τv∗u)uv∗ = I. (3) 留作练习. □ 更一般地, 我们有下面的结论. Sylverster 降幂公式 设 A ∈ C m×n , B ∈ C n×m, 其中 m ≥ n, 则有 det(λI − AB) = λ m−n det(λI − BA). (3.4) 因此 AB 和 BA 具有相同的非零特征值. (留作练习) 定理 3.2 设 A ∈ C n×n , 则 A 非奇异当且仅当 A 可以分解成若干个初等矩阵的乘积. 3.2.2 Gauss 变换 设 lj = [0, . . . , 0, lj+1,j , . . . , ln,j ] T, j = 1, 2, . . . , n, 则 Gauss 变换 定义为 L(lj ) ≜ E(lj , ej , −1) = I + lje T j = 1 . . . 1 lj+1,j 1 . . . . . . ln,j 1 . 显然, Gauss 变换也属于初等矩阵变换. 向量 lj 称为 Gauss 向量 [57]. 由定理 3.1 可知 det(L(lj )) = 1, (L(lj ))−1 = E(lj , ej , 1) = E(−lj , ej , −1) = L(−lj ). b Gauss 变换是对单位矩阵的秩 1 修正, 主要功能是消零, 即将指定的某些元素变为零. b Gauss 变换有时也称为初等下三角矩阵. 3.2.3 Householder 变换
-86第三讲线性最小二乘问题定义3.1我们称矩阵H=1-βot, 0#vec", β=2(3.5)*1为Householder矩阵或Householder变换，向量称为Householder向量.我们通常将矩阵(3.5)记为 H(u).Householder矩阵也是初等矩阵有时也将Householder变换定义为H=I-2v*,wCn且lvl2=1白Householder矩阵有时也称为初等Hermite矩阵[151]从几何上看，一个Householder变换是一个关于超平面span[u]+的反射.由于Cn=span[u]④span[u]+,因此对任意向量rECn,都可写为r=au+au+,其中auEspan[u],u+Espan(u].易知=于是20*rU*rHa=T-Buu=U=U+T-ru+KlU*yU*y即Ha与&在span[u}方向有着相同的分量，而在方向的分量正好相差一个符号.也就是说，Ha是关于超平面span[u]+的镜面反射，见图3.1.因此，Householder变换也称为Householder反射或反射变换spanv)1Hx图3.1.Householder变换的几何意义下面是关于Householder矩阵的几个基本性质定理3.3设HECnxn是一个Householder矩阵，则(1)H*=H,即H是Hermite的;(2)H*H=I,即H是酉矩阵；(3)H2=I,所以H-1=H;(4) det(H) = -1;(5)H有两个互异的特征值：入=1和入=-1,其中入=1的代数重数为n-1
· 86 · 第三讲 线性最小二乘问题 定义 3.1 我们称矩阵 H = I − βvv∗ , 0 ̸= v ∈ C n , β = 2 v ∗v (3.5) 为 Householder 矩阵 或 Householder 变换, 向量 v 称为 Householder 向量. 我们通常将矩阵 (3.5) 记为 H(v). b Householder 矩阵也是初等矩阵. b 有时也将 Householder 变换定义为 H = I − 2vv∗ , v ∈ C n 且 ∥v∥2 = 1. b Householder 矩阵有时也称为初等 Hermite 矩阵 [151]. 从几何上看, 一个 Householder 变换是一个关于超平面 span{v} ⊥ 的反射. 由于 C n = span{v}⊕ span{v} ⊥, 因此对任意向量 x ∈ C n , 都可写为 x = xv + xv⊥ , 其中 xv ∈ span{v}, xv⊥ ∈ span{v} ⊥. 易知 xv = v ∗x v ∗v v. 于是 Hx = x − βvv∗x = x − 2v ∗x v ∗v v = − v ∗x v ∗v v + xv⊥ = −xv + xv⊥ , 即 Hx 与 x 在 span{v} ⊥ 方向有着相同的分量, 而在 v 方向的分量正好相差一个符号. 也就是说, Hx 是 x 关于超平面 span{v} ⊥ 的镜面反射, 见图 3.1. 因此, Householder 变换也称为Householder 反射或反射变换. 图 3.1. Householder 变换的几何意义 下面是关于 Householder 矩阵的几个基本性质. 定理 3.3 设 H ∈ C n×n 是一个 Householder 矩阵, 则 (1) H∗ = H, 即 H 是 Hermite 的; (2) H∗H = I, 即 H 是酉矩阵; (3) H2 = I, 所以 H−1 = H ; (4) det(H) = −1; (5) H 有两个互异的特征值: λ = 1 和 λ = −1, 其中 λ = 1 的代数重数为 n − 1