华东师范大学：《数值分析》课程教学资源（课件讲义）第三讲 线性最小二乘问题——问题介绍与 Householder、Givens变换

数值分析 第三讲线性最小二乘问题 问题介绍。 Householder/Givens变换 目录 3.1问题介绍 3.2 Householder变换和Givens变换 3.3QR分解 3.4奇异值分解 3.5线性最小二乘问题的求解方法 https://math.ecnu.edu.cn/-jypan/Teaching/NA

数值分析 第三讲 线性最小二乘问题 问题介绍 • Householder/Givens 变换 3.1 问题介绍 3.2 Householder 变换和 Givens 变换 3.3 QR 分解 3.4 奇异值分解 3.5 线性最小二乘问题的求解方法 目录 https://math.ecnu.edu.cn/~jypan/Teaching/NA

3-11问题介绍 3.1问题介绍 3.1.1超定方程组 3.1.2欠定方程组 潘建瑜@MATH.ECNU https://math.ecnu.edu.cn/-jypan/Teaching/NA

3-1 问题介绍 3.1 问题介绍 3.1.1 超定方程组 3.1.2 欠定方程组 潘建瑜 @MATH.ECNU https://math.ecnu.edu.cn/~jypan/Teaching/NA

线性最小二乘问题 线性最小二乘问题就是求解下面的最值问题： Il.Aa-bll3 (3.1) 其中A∈Rmxn,b∈Rm.问题(3.1)的解称为最小二乘解 http://aath.ecnu.edu.cn/-jypan 3/26

线性最小二乘问题 线性最小二乘问题 就是求解下面的最值问题: min x∈Rn ∥Ax − b∥ 2 2 (3.1) 其中 A ∈ R m×n , b ∈ R m. 问题 (3.1) 的解称为最小二乘解.  当 m = n 且 A 非奇异时, 这就是一个线性方程组  当 m > n 时, 约束个数大于未知量个数, 问题为 超定的;  当 m < n 时, 未知量个数大于约束个数, 问题 (3.1) 为 欠定 (或亚定) 的. 为了讨论方便, 除非特别说明, 本讲总是假定 A 是满秩的. http://math.ecnu.edu.cn/~jypan 3/26

线性最小二乘问题 线性最小二乘问题就是求解下面的最值问题： 川A- (3.1) 其中A∈Rmxn,b∈Rm.问题(3.1)的解称为最小二乘解 ⊙当m=n且A非奇异时，这就是一个线性方程组 )当m>n时，约束个数大于未知量个数，问题为超定的； 0 当m<n时，未知量个数大于约束个数，问题(3.1)为欠定（或亚定）的. 为了讨论方便，除非特别说明，本讲总是假定A是满秩的 http://math.ecnu.edu.cn/-jypan 3/26

线性最小二乘问题 线性最小二乘问题 就是求解下面的最值问题: min x∈Rn ∥Ax − b∥ 2 2 (3.1) 其中 A ∈ R m×n , b ∈ R m. 问题 (3.1) 的解称为最小二乘解.  当 m = n 且 A 非奇异时, 这就是一个线性方程组  当 m > n 时, 约束个数大于未知量个数, 问题为 超定的;  当 m < n 时, 未知量个数大于约束个数, 问题 (3.1) 为 欠定 (或亚定) 的. 为了讨论方便, 除非特别说明, 本讲总是假定 A 是满秩的. http://math.ecnu.edu.cn/~jypan 3/26

3-1-1 超定方程组 当m>n时，方程个数大于未知量个数，Ax=b的解可能不存在 http://nath.ecnu.edu.cn/-Jypan 4/26

3-1-1 超定方程组 当 m > n 时, 方程个数大于未知量个数, Ax = b 的解可能不存在. 记目标函数: J(x) ≜ ∥Ax − b∥ 2 2  易知: J(x) 是关于 x 的二次函数, 而且是凸函数. 因此, x∗ 是问题 (3.1) 的解当且仅当 x∗ 是 J(x) 的稳定点, 即满足 ∂J ∂x = 0 ⇐⇒ A ⊺ Ax − A ⊺ b = 0 ✍ 如果 A 不是满秩, 则 A ⊺A 半正定, 此时解不唯一. http://math.ecnu.edu.cn/~jypan 4/26

3-1-1超定方程组 当m>n时，方程个数大于未知量个数，Ax=b的解可能不存在 记目标函数： J(z)≌‖Ax-b3 全易知：J)是关于x的二次函数，而且是凸函数 多因此，，是问题(31)的解当且仅当，是Jc)的稳定点，即满足 8J =0 ←→ATAx-Ab=0 如果A不是满秩，则A「A半正定，此时解不唯一 http://math.ecnu.edu.cn/-jypan 4/26

3-1-1 超定方程组 当 m > n 时, 方程个数大于未知量个数, Ax = b 的解可能不存在. 记目标函数: J(x) ≜ ∥Ax − b∥ 2 2  易知: J(x) 是关于 x 的二次函数, 而且是凸函数. 因此, x∗ 是问题 (3.1) 的解当且仅当 x∗ 是 J(x) 的稳定点, 即满足 ∂J ∂x = 0 ⇐⇒ A ⊺ Ax − A ⊺ b = 0 ✍ 如果 A 不是满秩, 则 A ⊺A 半正定, 此时解不唯一. http://math.ecnu.edu.cn/~jypan 4/26

3-1-2欠定方程组 当m<n时，方程个数小于未知量个数，存在无穷多个解（假定A满秩），是不适定问题 http://math.ecnu.edu.cn/-jypan 5/26

3-1-2 欠定方程组 当 m < n 时, 方程个数小于未知量个数, 存在无穷多个解 (假定 A 满秩), 是不适定问题. 这时我们通常寻求最小范数解, 于是原问题就转化为下面的 约束优化问题 min Ax=b 1 2 ∥x∥ 2 2 (3.2) 对应的 Lagrange 函数为 L(x, λ) = 1 2 ∥x∥ 2 2 + λ ⊺ (Ax − b), 其中 λ = [λ1, . . . , λm] ⊺ 是 Lagrange 乘子. 问题 (3.2) 的解就是 L(x, λ) 的鞍点, 即: ∂L ∂x = x + A ⊺ λ = 0, ∂L ∂λ = Ax − b = 0. 写成矩阵形式为 [ I A ⊺ A 0 ] [ x λ ] = [ 0 b ] . 如果 A 满秩则存在唯一解. http://math.ecnu.edu.cn/~jypan 5/26

3-1-2欠定方程组 当m<时，方程个数小于未知量个数，存在无穷多个解（假定A满秩），是不适定问题 花这时我们通常寻求最小范数解，于是原问题就转化为下面的约束优化问题 盟2暇 (3.2) 对应的Lagrange函数为 C(红，)=z吃+T(Ar-), 其中入=[A1,,入mJ「是Lagrange乘子.问题(3.2)的解就是C(z,的鞍点，即： ∂c ac =Ax-b=0. Ox =E+Aλ=0， ax 写成矩阵形式为 如果A满秩则存在唯一解 http://math.ecnu.edu.cn/-jyp 5/26

3-1-2 欠定方程组 当 m < n 时, 方程个数小于未知量个数, 存在无穷多个解 (假定 A 满秩), 是不适定问题. 这时我们通常寻求最小范数解, 于是原问题就转化为下面的 约束优化问题 min Ax=b 1 2 ∥x∥ 2 2 (3.2) 对应的 Lagrange 函数为 L(x, λ) = 1 2 ∥x∥ 2 2 + λ ⊺ (Ax − b), 其中 λ = [λ1, . . . , λm] ⊺ 是 Lagrange 乘子. 问题 (3.2) 的解就是 L(x, λ) 的鞍点, 即: ∂L ∂x = x + A ⊺ λ = 0, ∂L ∂λ = Ax − b = 0. 写成矩阵形式为 [ I A⊺ A 0 ] [x λ ] = [ 0 b ] . 如果 A 满秩则存在唯一解. http://math.ecnu.edu.cn/~jypan 5/26

本课程主要讨论超定问题 http://math.ecnu.edu.cn/-jypan 6/26

本课程主要讨论 超定问题 http://math.ecnu.edu.cn/~jypan 6/26

应用：多项式数据拟合 多已知m个数据样本{(x,f)}沿1，寻找一个低次多项式来拟合这些数据. X X y=ax+b y=ax2+bx+c http://nath.ecnu.edu.cn/-jypan 7/26

应用: 多项式数据拟合 已知 m 个数据样本 {(xi , fi)} m i=1, 寻找一个低次多项式来拟合这些数据. http://math.ecnu.edu.cn/~jypan 7/26