· ii ·
纸上得来终觉浅,绝知此事要躬行。
目 录
第一讲 线性代数基础 1
1.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 数值线性代数的研究内容 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.2 一些记号 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 线性空间与内积空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.1 线性空间与子空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 内积空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 正交与正交补 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3 向量范数与矩阵范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 向量范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 矩阵范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.3 序列的收敛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 矩阵与投影 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.1 特征值与特征向量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4.2 投影变换与投影矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.3 不变子空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5 矩阵标准型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5.1 Jordan 标准型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.5.2 Schur 标准型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6 几类特殊矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6.1 对称正定矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.6.2 对角占优 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6.3 不可约 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.6.4 其它常见特殊矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.7 Kronecker 积 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.8 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
第二讲 线性方程组的直接解法 29
2.1 Gauss 消去法和 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.1 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.1.2 LU 分解的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
iii
· iv · 目 录
2.1.3 IKJ 型 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.1.4 待定系数法计算 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.1.5 三角方程求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.1.6 选主元 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.7 矩阵求逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2 特殊方程组的求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.2.1 对称正定线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.2.2 对称不定线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.2.3 三对角线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.2.4 带状线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.2.5 Toeplitz 线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.3 扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3.1 δx 与 ˆx 的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.3.2 δx 与 x
∗
的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.3.3 δx 与残量的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
2.3.4 相对扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.4 误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.4.1 LU 分解的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.4.2 Gauss 消去法的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.5 解的改进和条件数估计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.5.1 高精度运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.5.2 矩阵元素缩放 (Scaling) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2.5.3 迭代改进法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.6 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
第三讲 线性最小二乘问题 63
3.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.1.1 超定方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.1.2 欠定方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.2 初等变换矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.1 初等矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.2 Gauss 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2.3 Householder 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2.4 Givens 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.2.5 正交矩阵舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.1 QR 分解的存在性与唯一性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
目 录 · v ·
3.3.2 基于 MGS 的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.3.3 基于 Householder 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
3.3.4 列主元 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.3.5 基于 Givens 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.3.6 QR 分解的稳定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.4 奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.4.1 奇异值基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.4.2 奇异值更多性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.4.3 奇异值扰动 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.5 线性最小二乘问题的求解方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.5.1 正规方程法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.5.2 QR 分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.5.3 奇异值分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.6 广义逆与最小二乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.6.1 广义逆基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.6.2 广义逆的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
3.6.3 广义逆与线性最小二乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.7 最小二乘扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.8 最小二乘问题的推广及其应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.8.1 正则化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.8.2 加权正则化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.8.3 约束最小二乘问题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.8.4 应用: 多项式数据拟合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.8.5 应用: 线性预测 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.8.6 应用: 信号光滑 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
3.8.7 应用: 反卷积 Deconvolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.8.8 应用: 采样信号补全 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.9 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
第四讲 非对称特征值问题 99
4.1 幂迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
4.2 反迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.2.1 反迭代算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.2.2 Rayleigh 商迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.3 正交迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
4.4 QR 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4.4.1 QR 迭代与幂迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104