程序员的数学：线性代数和概率统计

本书以计算机科学的视角，介绍了线性代数和概率论，并包括一些基本的统计知识。书中有很多应用实例，它们来自广泛的计算机科学领域，包括计算机图形学?计算机视觉?机器人?自然语言处理?搜索引擎?机器学习?统计分析?博弈论?图论?科学计算?决策论?编码学?密码学?网络分析?数据压缩和信号处理。本书还对MATLAB 进行了深入的讨论，包括大量的MATLAB 练习和程序设计作业。
本书既适合作为计算机相关专业的数学基础课教材，又可作为程序员?数学教师和感兴趣读者的参考书。

前 言
自从50 年前计算机科学(CS)首次成为一门学科以来，始终存在一个核心的问题: “一名计算机科研人员需要了解哪些大学水平的数学知识以及到什么程度呢?”正如所有的学科一样，正确的回答是对所有的相关知识应该无所不知。然而实际的情况是，如果与计算机专业的教授们共进午餐时提出这个问题，很快就会听到他们熟悉的抱怨: 如今的学生不知道笛沙格定理以及从未听说过p 进制数。鉴于学位课的学时有限，对CS 专业的学生来说，每增加一门数学课程，实质上就要减少一门CS 课程。传统上是安排两门数学必修课，第一学期的微积分，另外一个学期的本专业必备的“ 离散数学” 课程———由逻辑?集合论和组合数学构成的?令人愉快的大杂烩。在这两门数学课程之外，更多的数学课成了选修课。
我无意背离传统。我认为离散数学课程的确为数据库?编译器?操作系统?架构，以及网络等“核心”领域中工作的人提供了足够的数学背景。在这些领域，许多职业生涯非常成功的人对数学知之不多，他们经常会遇到数学问题，但都是次要的非系统性问题，而当这些问题出现时，他们可以补上所需要的数学知识。
然而，CS 的其他领域，包括人工智能?图形学?机器学习?优化?数据挖掘?计算金融?计算生物学?生物信息学?计算机视觉?信息检索?网络搜索等，需要不同的数学背景。在过去20 年里，这些领域在CS 中越来越重要。这些领域及其子领域在数学方面到底需要哪些知识，以及需要到什么深度，有着很大的差异。线性代数?概率论和多变量微积分这三个数学科目脱颖而出，它们在上述全部或绝大部分领域中显得尤为重要。
计算机科学专业的本科生要学习大约32 门学位课程，要求他们学习由数学系讲授的线性代数?多变量微积分和概率论课程是合理的。然而，对于只有10 或12 门的硕士课程，同样的要求是行不通的。许多的硕士生数学背景较弱，他们又急于开始学习具有大量数学背景的计算机课程，要求他们先学习3 到4 门的数学课程后再学习计算机课程是不可能的。另外他们学习本科的数学课程也拿不到研究生的学分，即使数学系能够提供研究生的课程，但对于他们来说无疑是非常困难的。
为了填补这一空缺，我为纽约大学( NYU) 的硕士生开设了一门新课程，权且称为“ 数学技术在计算机科学中的应用”，该课程特别针对数学背景薄弱的学生，集中介绍了线性代数和概率论。从2009 年开始，本课程每年在秋季学期开设一次，这本教材即为本课程所写。
在纽约大学计算机科学系的硕士课程里，本课程一个学期上14 次，每周上一次，每次两个小时。在2010 年我的课程里，第1 章和第2 章合在一起讲一次课，第6 章和第9 章每章各需要两次课，第3?4?5?7?8?10?11?12?13 章每章各一次课，第14 章省略掉了。课上到一半时，我决定每周必须增加一小时的复习课，当然我推荐这种做法。
多变量微积分仍然是一个空白，我还没有找到任何切实可行的办法。显然，不可能将所有三个科目都挤到一个学期，但建议硕士生上两个学期的“数学技术”课也许是可行的。
我教的课程广泛涉及MATLAB 编程。这本书里有专门一章介绍了MATLAB，其他每一章都讨论了相关的MATLAB 功能和特性，并包括许多MATLAB 程序设计作业。
图1 说明了各章之间的相互关系(相互关系较弱的，例如后一章中的某一节和此前某章中的内容有联系的没有列出)。
现在已经有很多概率论和线性代数教材，那为什么我还要写一本新教材? 首先，我想把这两个科目编写在同一本书里，我看过的唯一一本这样做的书是Stuart Hoggar 所著的?数字图像中的数学?(2006)。其次，也更为重要的是，这本书是写给计算机科研人员的，而不是数学家?物理学家或工程师。这一点会影响到预设的背景?主题的选择?举例以及表述。
图1 各章之间的关系
背景
在教材里，我设法采用尽可能少的数学背景。这本书的大部分内容只采用了高中数学，并且没有使用复数。线性代数部分除了对雅可比行列式进行了可以选学的简短讨论，其他地方完全避免了使用微积分。然而对于概率论，这种做法行不通。但我极大程度上将那些需要使用微积分的部分独立出来。对积分的基本了解是学习连续型随机变量概率密度的不可或缺的先决条件，了解多重积分是学习多维连续型随机变量联合分布的先决条件。
在这种课程中，数学证明是一个难点。本书绝大部分定理给出了证明，其中几个证明有点冗长。我把第4 章向量空间分成了两部分: 第一部分包含后续章节所需的最少内容，几乎没有证明；第二部分给出更多抽象的材料和证明。我的教学实践是在课堂上只讲一些有启发性的证明。我努力记住一点，无论教师对证明做何想象，而即使是对喜欢数学的学生来说，证明不同于解释，对讨厌数学的学生而言，证明和解释根本毫无关联。本书包括许多需要学生证明的习题。不过在教学中，我不布置需要证明的习题。我的经验是，由数学背景薄弱的学生给出的“证明”往往是随机排列的句子。

目 录
前 言
第1 章 MATLAB 1
1.1 桌面计算器操作 1
1.2 布尔运算 2
1.3 非标准数 3
1.4 循环与条件 4
1.5 脚本文件 6
1.6 函数 7
1.7 变量作用域与参数传递 8
思考题 10
程序设计作业 11
第1 篇 线性代数
第2 章 向量 14
2.1 向量的定义 14
2.2 向量的应用 14
2.2.1 关于应用的几点说明 16
2.3 向量的基本运算 17
2.3.1 向量运算的代数性质 18
2.3.2 基本运算的应用 18
2.4 点积 19
2.4.1 点积的代数性质 19
2.4.2 点积的应用: 加权和 19
2.4.3 点积的几何性质 20
2.4.4 元评论: 如何阅读公式推导 22
2.4.5 点积的应用: 两个向量的
相似性 23
2.4.6 点积和线性变换 25
2.5 MATLAB 中向量的基本运算 26
2.5.1 生成一个向量及索引 26
2.5.2 生成一个以等差数列为元素的
向量 26
2.5.3 基本运算 28
2.5.4 元素对元素的运算 28
2.5.5 有用的向量函数 29
2.5.6 随机向量 30
2.5.7 字符串: 字符数组 31
2.5.8 稀疏向量 31
2.6 在MATLAB 中绘制向量 32
2.7 编程语言中的向量 35
练习题 36
思考题 36
程序设计作业 36
第3 章 矩阵 40
3.1 矩阵的定义 40
3.2 矩阵的应用 40
3.3 矩阵的简单运算 42
3.4 矩阵和向量的乘积 42
3.4.1 矩阵和向量乘积的应用 43
3.5 线性变换 47
3.6 线性方程组 48
3.6.1 线性方程组的应用 49
3.7 矩阵乘法 53
3.8 把向量视为矩阵 56
3.9 矩阵乘法的代数性质 57
3.9.1 矩阵的幂 58
3.10 MATLAB 中的矩阵 59
3.10.1 矩阵的输入 59
3.10.2 提取子矩阵 60
3.10.3 矩阵的运算 61
3.10.4 稀疏矩阵 63
3.10.5 元胞数组 65
练习题 66
思考题 67
程序设计作业 67
第4 章 向量空间 71
4.1 向量空间的基本理论 71
4.1.1 子空间 71
4.1.2 坐标?基?线性无关 73
4.1.3 正交基和标准正交基 76
4.1.4 向量空间的运算 77
4.1.5 零核空间?像空间和秩 78
4.1.6 线性方程组 80
4.1.7 线性变换的逆变换和矩阵的逆 81
4.1.8 MATLAB 中的零核空间及秩 82
4.2 证明及其他抽象数学
(选学) 82
4.2.1 向量空间 83
4.2.2 线性无关和基 83
4.2.3 线性空间的和 86
4.2.4 正交 87
4.2.5 函数 89
4.2.6 线性变换 92
4.2.7 线性变换和矩阵的逆 93
4.2.8 线性方程组 93
4.3 一般的向量空间(选学) 95
4.3.1 向量空间的一般定义 95
练习题 97
思考题 98
程序设计作业 98
第5 章 算法 100
5.1 高斯消去法: 例子 100
5.2 高斯消去法: 讨论 101
5.2.1 矩阵上的高斯消去法 105
5.2.2 最大元素行交换 105
5.2.3 零检测 106
5.3 计算矩阵的逆 107
5.4 MATLAB 中的逆矩阵和线性
方程组 110
5.5 病态矩阵 114
5.6 计算复杂性 117
5.6.1 对数值计算的理解 117
5.6.2 运行时间 118
练习题 119
程序设计作业 120
第6 章 几何 123
6.1 矢量 123
6.2 坐标系 124
6.3 简单几何运算 126
6.3.1 距离与角度 126
6.3.2 单位矢量 126
6.3.3 二维空间的直线 127
6.3.4 三维空间的直线与面 129
6.3.5 同一性，关联，平行与相交 131
6.3.6 射影 132
6.4 几何变换 133
6.4.1 平移 134
6.4.2 绕原点旋转 135
6.4.3 刚体运动和齐次坐标表示 138
6.4.4 相似变换 142
6.4.5 仿射变换 143
6.4.6 物体的像 145
6.4.7 行列式 146
6.4.8 图像矩阵上的坐标变换 148
练习题 149
思考题 150
程序设计作业 150
第7 章 基变换，DFT 和SVD 154
7.1 坐标系变换 154
7.1.1 仿射坐标系 155
7.1.2 几何变换和坐标变换的关系及
坐标系的旋向 156
7.1.3 应用: 机器臂 157
7.2 基变换 161
7.3 概念混淆及如何避免 162
7.4 非几何的基变换 162
7.5 色图 163
7.6 离散的傅里叶变换(选学) 163
7.6.1 傅里叶变换的其他应用 167
7.6.2 复傅里叶变换 168
7.7 奇异值分解 169
7.7.1 矩阵分解 170
7.7.2 定理7.4 的证明(选学) 172
7.8 SVD 的进一步讨论 173
7.8.1 对称矩阵的特征值 176
7.9 SVD 的应用 176
7.9.1 条件数 176
7.9.2 存在舍入误差时如何计算秩 177
7.9.3 有损压缩 178
7.10 MATLAB 179
7.10.1 SVD 在MATLAB 中的使用 179
7.10.2 DFT 在MATLAB 中的应用 180
练习题 183
思考题 184
程序设计作业 186
第2 篇 概 率 论
第8 章 概率 188
8.1 概率论的解释 188
8.2 有限样本空间 189
8.3 基本组合公式 190
8.3.1 指数 190
8.3.2 n 个个体的排列 191
8.3.3 n 取k 的排列 191
8.3.4 n 取k 的组合 192
8.3.5 多组组合 192
8.3.6 中心二项式的近似 193
8.3.7 组合数学的例子 193
8.4 概率论的公理 194
8.5 条件概率 195
8.6 可能性解释 196