华东师范大学：《现代数值分析》课程教学课件（数值线性代数）第三讲 线性最小二乘问题（一）初等变换矩阵、QR分解

第三讲 线性最小二乘问题 问题介绍 2 初等变换矩阵 3 QR分解 奇异值分解 5 线性最小二乘问题的求解方法 6 最小二乘问题的推广及其应用* 现代数值分析（数值线性代数），潘建瑜 http://math.ecnu.edu.cn/~jypan

第三讲 线性最小二乘问题 1 问题介绍 2 初等变换矩阵 3 QR 分解 4 奇异值分解 5 线性最小二乘问题的求解方法 6 最小二乘问题的推广及其应用 ∗ 现代数值分析（数值线性代数）, 潘建瑜 http://math.ecnu.edu.cn/~jypan

最小二乘问题 最小二乘问题有着广泛的应用背景，如数据拟合，最优控制，信号与图像处理， 压缩感知，机器学习，数据科学等，是计算数学的一个重要研究分支，也是一个 非常活跃的研究领域， 最小二乘问题 线性最小二乘问题，总体最小二乘问题，约束最小二乘问题，.··… 本讲主要介绍求解线性最小二乘问题的三种直接法

最小二乘问题 最小二乘问题有着广泛的应用背景，如数据拟合，最优控制，信号与图像处理， 压缩感知，机器学习，数据科学等, 是计算数学的一个重要研究分支, 也是一个 非常活跃的研究领域. 最小二乘问题 线性最小二乘问题, 总体最小二乘问题, 约束最小二乘问题, . . . . . . 本讲主要介绍求解线性最小二乘问题的三种直接法

1 秦 问题介绍 考虑线性最小二乘问题 min llAx -bl2 (3.1) EE比" 其中A∈Rm×n,b∈Rm.问题(3.1)的解称为最小二乘解 ·当m=n且A非奇异时，这就是一个线性方程组，解为x=A-1b; ·当mn时，约束个数大于未知量个数，超定方程组 http://math.ecnu.edu.cn/~jypan 3/54

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 时, 约束个数大于未知量个数, 超定方程组 http://math.ecnu.edu.cn/~jypan 3/54

类 白为了讨论方便，本讲总是假定A是满秩的 一本讲我们主要讨论超定线性最小二乘问题的求解， http://math.ecnu.edu.cn/~jypan 4/54

✍ 为了讨论方便, 本讲总是假定 A 是满秩的. ✍ 本讲我们主要讨论超定线性最小二乘问题的求解. http://math.ecnu.edu.cn/~jypan 4/54

秦 2 初等变换矩阵 2.1基本变换矩阵 2.2 Householder变换 2.3 Givens变换 2.4正交变换的舍入误差分析 http://math.ecnu.edu.cn/~jypan 5/54

2 初等变换矩阵 2.1 基本变换矩阵 2.2 Householder 变换 2.3 Givens 变换 2.4 正交变换的舍入误差分析 ∗ http://math.ecnu.edu.cn/~jypan 5/54

秦 解决问题的基本思想 把复杂的问题转化为等价的较简单的且易于求解问题 矩阵变换 完成这个转化的基本工具就是矩阵变换 一除了三类初等变换外，矩阵计算中常用的矩阵变换还有： Householder变换和Givens变换 http://math.ecnu.edu.cn/~jypan 6/54

解决问题的基本思想 把复杂的问题转化为等价的较简单的且易于求解问题 矩阵变换 ✍ 完成这个转化的基本工具就是矩阵变换 ✍ 除了三类初等变换外, 矩阵计算中常用的矩阵变换还有: Householder 变换 和 Givens 变换 http://math.ecnu.edu.cn/~jypan 6/54

秦 2.1 基本变换矩阵 我们称矩阵 E(u,v,T）=I-Tuw* 为基本变换矩阵，其中山，v∈C”是非零向量，T是一个非零复数。 白基本变换矩阵是单位矩阵的一个秩1扰动/修正。 白三类初等矩阵都是基本变换矩阵。 http://math.ecnu.edu.cn/~jypan 7/54

2.1 基本变换矩阵 我们称矩阵 E(u, v, τ ) = I − τuv∗ 为基本变换矩阵，其中 u, v ∈ C n 是非零向量，τ 是一个非零复数。 ✍ 基本变换矩阵是单位矩阵的一个秩 1 扰动/修正。 ✍ 三类初等矩阵都是基本变换矩阵。 http://math.ecnu.edu.cn/~jypan 7/54

秦 定理设E(u,v,T）是一个基本变换矩阵，我们有 (1)det(E(u,v,T))=1-rv*u; (2)若1-Tu*u≠0，则E(u,u,T）非奇异，且 (E(,u,T)-1=E(u,v,Y),其中y= 入 Tv*u-1 (板书) http://math.ecnu.edu.cn/~jypan 8/54

定理 设 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 . (板书) http://math.ecnu.edu.cn/~jypan 8/54

秦 2.2 Householder变换 定义我们称矩阵 2 2 H=I- o=1- 0≠v∈Cm (3.2) U*U 8， 为Householder矩阵（或Householder变换，或Householder反射），向量v称为 Householder向量.我们通常将矩阵(3.2)记为H(u). http://math.ecnu.edu.cn/~jypan 9/54

2.2 Householder 变换 定义 我们称矩阵 H = I − 2 v ∗v vv∗ = I − 2 ∥v∥ 2 2 vv∗ , 0 ̸= v ∈ C n , (3.2) 为 Householder 矩阵 (或 Householder 变换, 或 Householder 反射), 向量 v 称为 Householder 向量. 我们通常将矩阵 (3.2) 记为 H(v). http://math.ecnu.edu.cn/~jypan 9/54

秦 几何意义 从几何上看，Householder变换就是一个关于超平面span{v}1的反射. 对任意一个向量x∈C”,可将其写为 I=Qv+y, with a= U*U 其中av∈span{v,y∈span{v}.则 2 Hx=x- ow'=:-2av=-0v+y 即Hx与x在span{u}十方向有相同分量，而在v方向的分量相差一个符号. http://math.ecnu.edu.cn/~jypan 10/54

几何意义 从几何上看, Householder 变换就是一个关于超平面 span{v} ⊥ 的反射. 对任意一个向量 x ∈ C n , 可将其写为 x = αv + y, ( with α = v ∗x v ∗v ) 其中 αv ∈ span{v}, y ∈ span{v} ⊥. 则 Hx = x − 2 v ∗v vv∗x = x − 2αv = −αv + y, 即 Hx 与 x 在 span{v} ⊥ 方向有相同分量, 而在 v 方向的分量相差一个符号. http://math.ecnu.edu.cn/~jypan 10/54