《矩阵计算》课程教学资源（讲义）第一讲 线性代数基础

矩阵计算讲义

矩阵计算讲义

目录第零讲引言10.1计算数学介绍240.2数值线性代数5第一讲线性代数基础51.1线性空间与内积空间1.1.1线性空间。51.1.2内积空间81.1.3正交与正交补91.2矩阵与投影101.2.1矩阵的秩101.2.2特征值与特征向量12141.2.3特征值的粗略估计151.2.4不变子空间1.2.5投影变换161.3向量范数与矩阵范数19向量范数1.3.1191.3.2矩阵范数211.3.3谱半径与范数231.3.4最佳逼近与正交投影241.4矩阵标准型251.4.1Jordan标准型251.4.2Schur分解261.5几类特殊矩阵271.5.1对称正定矩阵271.5.2对角占优矩阵28291.5.3不可约矩阵1.6Kronecker积32341.7课后习题ili

目 录 第零讲 引言 1 0.1 计算数学介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0.2 数值线性代数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 第一讲 线性代数基础 5 1.1 线性空间与内积空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.1 线性空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.2 内积空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.3 正交与正交补 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 矩阵与投影 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 矩阵的秩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2 特征值与特征向量 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2.3 特征值的粗略估计 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2.4 不变子空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2.5 投影变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.3 向量范数与矩阵范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.1 向量范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.2 矩阵范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.3.3 谱半径与范数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3.4 最佳逼近与正交投影 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.4 矩阵标准型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.1 Jordan 标准型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.2 Schur 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.5 几类特殊矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.5.1 对称正定矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.5.2 对角占优矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.5.3 不可约矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.6 Kronecker 积 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.7 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 iii

目录-iv.第二讲线性方程组直接方法382.1LU分解与Gauss消去法392.1.1LU分解392.1.2LU分解的实现40432.1.3Gauss消去法2.1.4选主元LU分解46矩阵求逆2.1.5472.1.6分块LU分解482.2特殊方程组的求解492.2.1对称正定线性方程组492.2.251对称不定线性方程组2.2.3三对角线性方程组53552.2.4带状线性方程组2.2.5Toeplitz线性方程组562.3扰动分析61矩阵条件数2.3.1612.3.2r与的关系62622.3.38与的关系2.3.4与残量的关系63642.3.5相对扰动分析2.4误差分析*66662.4.1LU分解的舍入误差分析2.4.2Gauss消去法的舍人误差分析662.5解的改进*682.5.1高精度运算682.5.2矩阵元素缩放或平衡(Scalingorequilibration)682.5.3送代改进法682.6课后习题70第三讲线性最小二乘问题733.1问题介绍733.1.1超定方程组73欠定方程组743.1.23.2几类重要的矩阵变换75

· iv · 目 录 第二讲 线性方程组直接方法 38 2.1 LU 分解与 Gauss 消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.1 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.1.2 LU 分解的实现 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.1.3 Gauss 消去法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.4 选主元 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.1.5 矩阵求逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.1.6 分块 LU 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.2 特殊方程组的求解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.1 对称正定线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.2 对称不定线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.2.3 三对角线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.4 带状线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.5 Toeplitz 线性方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.3 扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.1 矩阵条件数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.2 δx 与 xˆ 的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.3.3 δx 与 x∗ 的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2.3.4 δx 与残量的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.3.5 相对扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 2.4 误差分析 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.4.1 LU 分解的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.4.2 Gauss 消去法的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 66 2.5 解的改进 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.5.1 高精度运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.5.2 矩阵元素缩放或平衡 (Scaling or equilibration) . . . . . . . . . . . . . . . . . . 68 2.5.3 迭代改进法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 2.6 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 第三讲 线性最小二乘问题 73 3.1 问题介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.1.1 超定方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.1.2 欠定方程组 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.2 几类重要的矩阵变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

目录.V.初等矩阵变换3.2.1753.2.2Gauss 变换763.2.3Householder 变换763.2.4Givens变换793.2.5正交变换的舍入误差分析813.3QR分解83QR分解的存在性与唯一性833.3.13.3.2基于MGS的QR分解85863.3.3基于Householder变换的OR分解893.3.4列主元QR分解3.3.5基于Givens变换的QR分解90913.3.6QR分解的稳定性943.4奇异值分解943.4.1奇异值，奇异向量和奇异值分解3.4.2奇异值基本性质953.4.3奇异值更多性质973.4.4奇异值扰动分析993.5线性最小二乘问题的求解方法1003.5.1正规方程.1001003.5.2Cholesky分解法3.5.3QR分解法1011023.5.4奇异值分解法3.6广义逆与最小二乘*.103广义逆3.6.11033.6.2广义逆基本性质：1033.6.3广义逆的计算1043.6.4广义逆与线性最小二乘:1053.6.5左逆和右逆105最小二乘扰动分析*3.7.1063.8推广与应用*107最小二乘问题的推广:1073.8.13.8.2最小二乘问题的应用1083.9课后习题111

目 录 · v · 3.2.1 初等矩阵变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.2.2 Gauss 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.2.3 Householder 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.2.4 Givens 变换 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.2.5 正交变换的舍入误差分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.3 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.3.1 QR 分解的存在性与唯一性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.3.2 基于 MGS 的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 3.3.3 基于 Householder 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . 86 3.3.4 列主元 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 3.3.5 基于 Givens 变换的 QR 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.3.6 QR 分解的稳定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 3.4 奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 3.4.1 奇异值，奇异向量和奇异值分解 . . . . . . . . . . . . . . . . . . . . . . . . 94 3.4.2 奇异值基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.4.3 奇异值更多性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 3.4.4 奇异值扰动分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3.5 线性最小二乘问题的求解方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.5.1 正规方程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.5.2 Cholesky 分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 3.5.3 QR 分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 3.5.4 奇异值分解法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 3.6 广义逆与最小二乘 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.6.1 广义逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.6.2 广义逆基本性质 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 3.6.3 广义逆的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 3.6.4 广义逆与线性最小二乘 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.6.5 左逆和右逆 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.7 最小二乘扰动分析 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 3.8 推广与应用 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 3.8.1 最小二乘问题的推广 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 3.8.2 最小二乘问题的应用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 3.9 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

目录+vi.第四讲非对称特征值问题1144.1幕迭代法1144.1.1算法介绍1144.1.2收敛性分析115:1164.1.3位移策略4.2反迭代法1174.2.1算法介绍:1174.2.2Rayleigh商送代1174.3正交选代法.1194.4QR送代法.121.1214.4.1QR送代与幕选代的关系4.4.2QR选代与反选代的关系1224.4.3QR选代与正交选代的关系1224.4.4QR选代的收敛性1224.4.5带位移的QR送代法1234.5带位移的隐式QR选代法1254.5.1上Hessenberg矩阵1254.5.2隐式QR送代1274.5.3位移的选取1294.5.4收缩1334.6特征向量的计算1344.7广义特征值问题*：1354.7.1广义特征值基本理论135广义Schur分解4.7.21354.7.3QZ选代法1364.8应用*137多项式求根4.8.11374.8.2Goolge网页排名：PageRank138.4.9课后习题139141第五讲对称特征值问题5.1Jacobi送代法1415.2Rayleigh商送代法1465.3对称QR选代法147

· vi · 目 录 第四讲 非对称特征值问题 114 4.1 幂迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.1.1 算法介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 4.1.2 收敛性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 4.1.3 位移策略 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 4.2 反迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.2.1 算法介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.2.2 Rayleigh 商迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 4.3 正交迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 4.4 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.4.1 QR 迭代与幂迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 4.4.2 QR 迭代与反迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.4.3 QR 迭代与正交迭代的关系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.4.4 QR 迭代的收敛性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 4.4.5 带位移的 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 4.5 带位移的隐式 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.5.1 上 Hessenberg 矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 4.5.2 隐式 QR 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.5.3 位移的选取 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 4.5.4 收缩 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.6 特征向量的计算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 4.7 广义特征值问题 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7.1 广义特征值基本理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7.2 广义 Schur 分解 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 4.7.3 QZ 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 4.8 应用 * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 4.8.1 多项式求根 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 4.8.2 Goolge 网页排名：PageRank . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 4.9 课后习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 第五讲 对称特征值问题 141 5.1 Jacobi 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 5.2 Rayleigh 商迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 5.3 对称 QR 迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147