动态规划

本文内容参考《算法导论》,OI Wiki

基础知识

动态规划方法通常用来求解最优化问题。这类问题可以有很多可行解,每个解都有一个值,我们希望寻找具有最优值(最小值或最大值)的解。

适合应用动态规划方法求解的最优化问题应该具备两个要素:最优子结构重叠子问题

  • 最优子结构:问题的最优解由相关子问题的最优解组合而成,而这些子问题可以独立求解。
  • 重叠子问题:如果问题的递归算法会反复求解相同的子问题,我们就称最优化问题具有重叠子问题性质。

子问题图

子问题图是一个有向图,每个顶点唯一的对应一个子问题。若求子问题 \(x\) 的最优解时需要直接用到子问题 \(y\) 的最优解,那么在子问题图中就会有一条从子问题 \(x\) 的顶点到子问题 \(y\) 的顶点的有向边。

自顶向下动态规划处理子问题图中顶点的顺序为拓扑序,自底向上动态规划处理子问题图中顶点的顺序为逆拓扑序。

通常情况下,动态规划算法的运行时间与子问题图中顶点和边的数量呈线性关系。

选择自顶向下,还是自底向上

通常情况下,如果每个子问题都必须至少求解一次,自底向上动态规划算法会更快,因为没有递归调用的开销,而且对于某些问题,可以利用表的访问模式降低时空开销。如果子问题空间中的某些子问题完全不必求解,自顶向下动态规划算法会更快,因为它只会求解那些必要的子问题。

背包 DP

题目:有 \(n\) 种物品和一个容量为 \(W\) 的背包,每种物品有数量 \(k_{i}\)、重量 \(w_{i}\) 和价值 \(v_{i}\) 三种属性,要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

0-1 背包

每种物品只能取一次,即 \(k_{i}=1\) 对任意 \(i\) 都成立。

转移方程:

$$ dp[i][j]=\max{(dp[i-1][j],dp[i-1][j-w[i]]+v[i])} $$

空间优化(倒序枚举):

$$ dp[j]=\max{(dp[j],dp[j-w[i]]+v[i])} $$

完全背包

每种物品可以取无限次,即 \(k_{i}=\infty\) 对任意 \(i\) 都成立。

转移方程:

$$ dp[i][j]=\max_{k=0}^{\infty}{dp[i-1][j-k\cdot w[i]]+k\cdot v[i]} $$

方程优化:

$$ dp[i][j]=\max{(dp[i-1][j],dp[i][j-w[i]]+v[i])} $$

空间优化(正序枚举):

$$ dp[j]=\max(dp[j],dp[j-w[i]]+v[i]) $$

多重背包

每种物品可以取 \(k_{i}\) 次,即 \(k_{i}\in\mathbb{N}\) 对任意 \(i\) 都成立。

转移方程:

$$ dp[i][j]=\max_{k=0}^{k[i]}{dp[i-1][j-k\cdot w[i]]+k\cdot v[i]} $$

二进制分组优化:将每种物品的 \(k_{i}\) 拆分为多个组,每组的数量为 \(2^{0},2^{1},\dots,2^{\lfloor{\log{k_{i}+1}}\rfloor -1}\),如果 \(k_{i}+1\) 不是二的幂,就将多余的数量作为一组,最后将 \(k_{i}\) 拆出来的每组都看作数量为 \(1\) 的新物品,从而转化为 0-1 背包。可以证明,如果选择 \(x\) 次第 \(i\) 种物品,其中 \(x\in[0,k_{i}]\),则该选择方式总是可以由分组后的新物品的某个组合表示。

例题

Introduction to Linear Algebra

参考 Introduction to Linear AlgebraMIT 18.06SC Fall 2011SOLUTIONS TO PROBLEM SETS

Vectors and Matrices

Vectors and Linear Combinations

\(n\) 个 \(m\) 维向量组成 \(m \times n\) 矩阵 \(A\) 的列。两个关键问题:① 列向量的线性组合 \(Ax = x_{1}v_{1} + x_{2}v_{2} + \cdots + x_{n}v_{n}\) 是否填满整个空间?如果不能,则 \(A\) 是奇异矩阵,其列向量是线性相关的。② 已知 \(A\) 和 \(b\),求解 \(Ax = b\)。

$$ A= \left[\begin{matrix} v_{1} & v_{2} & \cdots & v_{n} \end{matrix}\right] $$

从列、行和矩阵角度理解:向量的线性组合,线性方程组,矩阵相乘。如果向量 \(v\) 和 \(w\) 线性无关(不共线),则 \(2 \times 2\) 矩阵 \(A=\left[\begin{matrix}v & w\end{matrix}\right]\) 是可逆的,向量 \(v\) 和 \(w\) 的线性组合可以填满 \(xy\) 平面。

$$ c \left[\begin{matrix} v_{1} \\ v_{2} \end{matrix}\right] + d \left[\begin{matrix} w_{1} \\ w_{2} \end{matrix}\right] = \left[\begin{matrix} b_{1} \\ b_{2} \end{matrix}\right] \iff \begin{align} v_{1}c + w_{1}d = b_{1} \\ v_{2}c + w_{2}d = b_{2} \end{align} \iff \left[\begin{matrix} v_{1} & w_{1} \\ v_{2} & w_{2} \end{matrix}\right] \left[\begin{matrix} c \\ d \end{matrix}\right] = \left[\begin{matrix} b_{1} \\ b_{2} \end{matrix}\right] $$

Lengths and Angles from Dot Products

向量 \(v=\left[\begin{matrix}v_{1} \ v_{2} \ \vdots \ v_{n}\end{matrix}\right]\) 和 \(w=\left[\begin{matrix}w_{1} \ w_{2} \ \vdots \ w_{n}\end{matrix}\right]\) 的点积 \(v \cdot w = v_{1}w_{1} + v_{2}w_{2} + \cdots + v_{n}w_{n}\)。点积 \(v \cdot v\) 表示向量长度的平方 \(|v|^{2} = v_{1}^{2} + \cdots + v_{n}^{2}\)。单位向量 \(u\) 的长度 \(|u| = 1\),如果 \(v \neq 0\),则 \(u=\frac{v}{|v|}\) 是单位向量。

垂直向量满足 \(v \cdot w = 0\),则 \(|v + w|^{2} = |v|^{2} + |w|^{2}\)。如果 \(|v| = 1\) 且 \(|u| = 1\),则 \(v\) 和 \(u\) 之间的夹角 \(\theta\) 满足 \(\cos{\theta} = v \cdot u\)。如果 \(v\) 和 \(w\) 都不是零向量,则 \(\frac{v \cdot w}{|v||w|} = \cos{\theta}\)。SCHWARZ INEQUALITY \(|v \cdot w| \leq |v||w|\),TRIANGLE INEQUALITY \(|v + w| \leq |v| + |w|\)。

Matrices and Their Column Spaces

If I have numbers in \(A\) and \(x\), and I want to compute \(Ax\), then I tend to use dot products: the row picture. But if I want to understand \(Ax\), the column picture is better.

矩阵 \(A\) 的列向量线性无关意味着:① 只有 \(x\) 是零向量时,能使 \(Ax = 0\);② 每个列向量都不是之前列的线性组合,通常从左到右检查相关性。矩阵 \(A\) 的列向量的所有线性组合构成矩阵的列空间 \(C(A)\),或者说矩阵 \(A\) 的列向量张成(span)列空间。当且仅当 \(v\) 在矩阵 \(A\) 的列空间中,\(Ax = v\) 有解。对于 \(m \times m\) 矩阵 \(A\),所有列向量线性无关,才能张成整个 \(\mathbf{R}^{m}\) 空间,如果线性相关则只能张成得到 \(\mathbf{R}^{m}\) 的子空间。

Matrix Multiplication AB and CR

个人理解,矩阵相乘可以看作由向量点积组合而成,只不过将不同部分视为整体,就有不同的表现形式。例如,矩阵 \(A\)(\(m \times s\))乘以矩阵 \(B\)(\(s \times n\)):

$$ C = AB = \left[\begin{matrix} a_{11} & a_{12} & \cdots & a_{1s} \\ a_{21} & a_{22} & \cdots & a_{2s} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{ms} \end{matrix}\right] \left[\begin{matrix} b_{11} & b_{12} & \cdots & b_{1n} \\ b_{21} & b_{22} & \cdots & b_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{s1} & b_{s2} & \cdots & b_{sn} \end{matrix}\right] = \left[\begin{matrix} c_{11} & c_{12} & \cdots & c_{1n} \\ c_{21} & c_{22} & \cdots & c_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \cdots & c_{mn} \end{matrix}\right] $$

① 矩阵 \(A\) 中的行向量点乘矩阵 \(B\) 中的列向量,得到矩阵 \(C\) 中的单个元素。

$$ c_{ij} = \sum_{k = 1}^{s}{a_{ik}b_{kj}} $$

② 将矩阵 \(A\) 视为单个行向量,其每个分量都是一个列向量。该行向量点乘矩阵 \(B\) 中的列向量,则矩阵 \(C\) 中列向量是矩阵 \(A\) 中列向量的线性组合。

$$ \left[\begin{matrix} c_{1j} \\ c_{2j} \\ \vdots \\ c_{mj} \end{matrix}\right] = \left[\begin{matrix} a_{11} & a_{12} & \cdots & a_{1s} \\ a_{21} & a_{22} & \cdots & a_{2s} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{ms} \end{matrix}\right] \left[\begin{matrix} b_{1j} \\ b_{2j} \\ \vdots \\ b_{sj} \end{matrix}\right] = \sum_{k = 1}^{s}b_{kj} \left[\begin{matrix} a_{1k} \\ a_{2k} \\ \vdots \\ a_{mk} \end{matrix}\right] $$

③ 将矩阵 \(B\) 视为单个列向量,其每个分量都是一个行向量。矩阵 \(A\) 中的行向量点乘该列向量,则矩阵 \(C\) 中行向量是矩阵 \(B\) 中行向量的线性组合。

$$ \left[\begin{matrix} c_{i1} & c_{i2} & \cdots & c_{in} \end{matrix}\right] = \left[\begin{matrix} a_{i1} & a_{i2} & \cdots & a_{is} \\ \end{matrix}\right] \left[\begin{matrix} b_{11} & b_{12} & \cdots & b_{1n} \\ b_{21} & b_{22} & \cdots & b_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ b_{s1} & b_{s2} & \cdots & b_{sn} \end{matrix}\right] = \sum_{k = 1}^{s}a_{ik} \left[\begin{matrix} b_{k1} & b_{k2} & \cdots & b_{kn} \end{matrix}\right] $$

④ 将矩阵 \(A\) 中的列向量和矩阵 \(B\) 中的行向量相乘(外积),得到秩为 \(1\) 的 \(m \times n\) 矩阵,将这些矩阵求和得到矩阵 \(C\)。

$$ C = AB = \sum_{k = 1}^{s} \left[\begin{matrix} a_{1k} \\ a_{2k} \\ \vdots \\ a_{mk} \end{matrix}\right] \left[\begin{matrix} b_{k1} & b_{k2} & \cdots & b_{kn} \end{matrix}\right] $$

矩阵乘法不满足交换律 \(AB \neq BA\),但是满足结合率 \((AB)C = A(BC)\)。矩阵 \(A\) 右乘 \(B\) 得到 \(AB\),其列向量是 \(A\) 中列向量的线性组合(列变换);矩阵 \(A\) 左乘 \(B\) 得到 \(BA\),其行向量是 \(A\) 中行向量的线性组合(行变换)。

$$ \left[\begin{matrix} a & b \\ c & d \end{matrix}\right] \left[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}\right] = \left[\begin{matrix} a \\ c \end{matrix}\right] \left[\begin{matrix} 0 & 1 \end{matrix}\right] + \left[\begin{matrix} b \\ d \end{matrix}\right] \left[\begin{matrix} 1 & 0 \end{matrix}\right] = \left[\begin{matrix} 0 & a \\ 0 & c \end{matrix}\right] + \left[\begin{matrix} b & 0 \\ d & 0 \end{matrix}\right] = \left[\begin{matrix} b & a \\ d & c \end{matrix}\right] $$
$$ \left[\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}\right] \left[\begin{matrix} a & b \\ c & d \end{matrix}\right] = \left[\begin{matrix} 0 \\ 1 \end{matrix}\right] \left[\begin{matrix} a & b \end{matrix}\right] + \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] \left[\begin{matrix} c & d \end{matrix}\right] = \left[\begin{matrix} 0 & 0 \\ a & b \end{matrix}\right] + \left[\begin{matrix} c & d \\ 0 & 0 \end{matrix}\right] = \left[\begin{matrix} c & d \\ a & b \end{matrix}\right] $$

For computing by hand, I would use the row way to find each number in \(AB\). I visualize multiplication by columns: The columns \(Ab_{j}\) in \(AB\) are combinations of columns of \(A\).

矩阵的秩(rank)就是其线性无关的列向量的数目,所有秩为 \(r\) 的矩阵都可以表示为 \(r\) 个秩为 \(1\) 的矩阵之和。秩为 \(1\) 的 \(m \times n\) 矩阵的列空间是 \(m\) 维空间中的一条直线,其行空间是 \(n\) 维空间中的一条直线。

将矩阵 \(A\) 分解为 \(CR\),即 \(A = CR\),其中 \(C\) 由 \(A\) 中所有 \(r\) 个线性无关的列向量组成,\(r\) 就是矩阵 \(A\) 和 \(C\) 的秩。\(A\) 中列向量可以通过 \(C\) 中列向量的线性组合得到,而 \(R\) 中列向量表示如何组合可以得到 \(A\) 中对应的列向量。\(R\) 可以表示为 \(R=\left[\begin{matrix}I & F\end{matrix}\right]P\),其中 \(I\) 是单位矩阵,表示 \(A\) 中所有线性无关列如何由 \(C\) 中列向量组合得到,\(F\) 则表示线性相关列的组合方式,\(P\) 置换矩阵将列放在对应位置上。

$$ \left[\begin{matrix} 2 & 6 & 4 \\ 4 & 12 & 8 \\ 1 & 3 & 5 \end{matrix}\right] = \left[\begin{matrix} 2 & 4 \\ 4 & 8 \\ 1 & 5 \end{matrix}\right] \left[\begin{matrix} 1 & 3 & 0 \\ 0 & 0 & 1 \\ \end{matrix}\right] $$

\(A\) 中行向量的秩和列向量的秩相同,非正式证明:因为 \(R\) 包含 \(r \times r\) 单位矩阵 \(I\),所以 \(R\) 中所有 \(r\) 个行向量都是线性无关的,而 \(R\) 左乘 \(C\) 得到 \(A\),说明 \(A\) 中行向量是 \(R\) 中行向量的线性组合,那么 \(A\) 中行向量的秩也是 \(r\)。\(C\) 和 \(A\) 有相同的列空间,其列向量组是 \(A\) 列空间的一个基(basis)。\(R\) 和 \(A\) 有相同的行空间,其行向量组是 \(A\) 行空间的一个基。

Solving Linear Equations \(Ax = b\)

Elimination and Back Substitution

列向量线性无关的方阵 \(A\)(满秩矩阵),都可以被化简为主元(pivot)非零的上三角矩阵 \(U\)。如果主对角线上没有零,则上三角矩阵 \(U\) 满秩,所有列向量线性无关。将 \(A\) 转为 \(U\),相当于不断地左乘矩阵(消元矩阵 \(E\) 和 置换矩阵 \(P\))进行行变换。消元和置换过程可以使用增广矩阵 \(\left[\begin{matrix}A & b \end{matrix}\right]\),同时对 \(A\) 和 \(b\) 执行操作。

$$ \left[\begin{matrix} A & b \end{matrix}\right] = \left[\begin{matrix} 2 & 3 & 4 & 19 \\ 4 & 11 & 14 & 55 \\ 2 & 8 & 17 & 50 \end{matrix}\right] \rightarrow \left[\begin{matrix} U & c \end{matrix}\right] = \left[\begin{matrix} 2 & 3 & 4 & 19 \\ 0 & 5 & 6 & 17\\ 0 & 0 & 7 & 14 \end{matrix}\right] \rightarrow x = \left[\begin{matrix} 4 \\ 1 \\ 2 \end{matrix}\right] $$

如果方阵 \(A\) 的列向量线性无关,则方程 \(Ax = b\) 有唯一解,因为 \(A\) 的列空间是整个 \(\mathbf{R}^{n}\)。否则,方程无解或有无穷多个解,取决于 \(b\) 是否在 \(A\) 的列空间中。如果 \(b\) 在 \(A\) 的列空间中,则存在 \(x\) 使得 \(Ax = b\)。而且 \(A\) 的列向量线性相关,所以 \(AX = 0\) 有无穷多个解,那么 \(A(x + \alpha X) = b\) 对任意 \(\alpha\) 都成立,所以此时方程有无穷多个解。

Elimination Matrices and Inverse Matrices

如果矩阵 \(A\) 是可逆的,则存在 \(A^{-1}\) 使得 \(AA^{-1} = A^{-1}A = I\)。矩阵 \(A\) 可逆当且仅当,消元之后所有主元非零,\(Ax = b\) 有唯一解 \(x = A^{-1}b\),\(Ax = 0\) 没有非零解,\(A\) 的列向量线性无关,\(A\) 的行列式 \(|A| \neq 0\),\(A\) 是非奇异矩阵。利用增广矩阵求逆矩阵,将 \(\left[\begin{matrix}A & I \end{matrix}\right]\) 转化为 \(\left[\begin{matrix}I & A^{-1} \end{matrix}\right]\)。

\(B^{-1}A^{-1}\) illustrates a basic rule of mathematics: Inverses come in reverse order. It is also common sense: If you put on socks and then shoes, the first to be taken off are the shoes.

矩阵乘积的逆满足 \(ABB^{-1}A^{-1} = I \Rightarrow (AB)^{-1} = B^{-1}A^{-1}\),逆变换以相反的顺序执行。任意可逆矩阵都可以分解为 \(LU\) 的形式,\(EPA = U \Rightarrow PA = E^{-1}U = LU\),\(L\) 和 \(U\) 分别是下三角矩阵和上三角矩阵。假设 \(n = 3\),且置换矩阵 \(P = I\)。\(E_{ij}\) 表示 \(row_{i} = row_{i} - l_{ij} \times row_{j}\) 行变换,不断执行行变换消元,得到消元矩阵 \(E = E_{32}E_{31}E_{21}\)。其逆矩阵为 \(E^{-1} = E_{32}^{-1}E_{31}^{-1}E_{21}^{-1}\),所有的乘数 \(l_{ij}\) 都在矩阵 \(L\) 的相应位置上。

$$ E = \left[\begin{matrix} 1 \\ 0 & 1 \\ 0 & -l_{32} & 1 \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 & 1 \\ -l_{31} & 0 & 1 \end{matrix}\right] \left[\begin{matrix} 1 \\ -l_{21} & 1 \\ 0 & 0 & 1 \end{matrix}\right] = \left[\begin{matrix} 1 \\ -l_{21} & 1 \\ (l_{32}l_{21} - l_{31}) & -l_{32} & 1 \end{matrix}\right] $$
$$ E^{-1} = \left[\begin{matrix} 1 \\ l_{21} & 1 \\ 0 & 0 & 1 \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 & 1 \\ l_{31} & 0 & 1 \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 & 1 \\ 0 & l_{32} & 1 \end{matrix}\right] = \left[\begin{matrix} 1 \\ l_{21} & 1 \\ l_{31} & l_{32} & 1 \end{matrix}\right] = L $$

Matrix Computations and \(A = LU\)

The elimination steps from A to U cost \(\frac{1}{3}n^{3}\) multiplications and \(\frac{1}{3}n^{3}\) subtractions.

Each right side \(b\) costs only \(n^{2}\): forward to \(Ux = c\), then back-substitution for \(x\).

什么时候可以将矩阵 \(A\) 分解为 \(LU\),而不需要交换行(\(P = I\)),且所有主元非零?矩阵 \(A\) 的所有左上角的 \(k \times k\) 子矩阵必须是可逆的,其中 \(k \in [1, n]\)。因为消元也会分解每个 \(k \times k\) 子矩阵 \(A_{k}\),从 \(A = LU\) 得到 \(A_{k} = L_{k}U_{k}\),所以 \(A_{k}\) 必须是可逆的。

$$ \left[\begin{matrix} A_{k} & * \\ * & * \\ \end{matrix}\right] = \left[\begin{matrix} L_{k} & 0 \\ * & * \\ \end{matrix}\right] \left[\begin{matrix} U_{k} & * \\ 0 & * \\ \end{matrix}\right] $$

Permutations and Transposes

置换矩阵 \(P\) 和单位矩阵 \(I\) 有相同的行,只不过可以任意排列,总共有 \(n!\) 种排列方式。置换矩阵的性质:\(P^{T} = P^{-1}\);\(P\) 的列向量是正交的,列向量之间的点积都是零;置换矩阵的乘积 \(P_{1}P_{2}\) 也是置换矩阵;如果矩阵 \(A\) 可逆,则存在置换矩阵 \(P\),使得对 \(PA\) 消元可以得到主元非零的矩阵 \(U\),即 \(PA = LU\) 分解。可以在 \(A\) 中添加特殊的 \(1\ 2\ 3\) 列,该列跟踪原始的行号,可以从中得到 \(P\) 的值。

$$ P^{T}P = \left[\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}\right] \left[\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}\right] = \left[\begin{matrix} 1 \\ & 1 & \\ & & 1 \end{matrix}\right] = I $$
$$ \left[\begin{matrix} 1 & 2 & a & 1 \\ 2 & 4 & b & 2 \\ 3 & 7 & c & 3 \end{matrix}\right] \rightarrow \left[\begin{matrix} 1 & 2 & a & 1 \\ 0 & 0 & b - 2a & 2 \\ 0 & 1 & c - 3a & 3 \end{matrix}\right] \rightarrow \left[\begin{matrix} 1 & 2 & a & 1 \\ 0 & 1 & c - 3a & 3 \\ 0 & 0 & b - 2a & 2 \end{matrix}\right] \rightarrow P_{132} = \left[\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}\right] $$

转置矩阵 \(A^{T}\) 的列和矩阵 \(A\) 的行相对应,相当于沿主对角线翻转矩阵 \(A\),满足 \((A^{T})_{ij} = A_{ji}\)。转置矩阵的性质:\((A + B)^{T} = A^{T} + B^{T}\),\((AB)^{T} = B^{T}A^{T}\),\((A^{-1})^{T} = (A^{T})^{-1}\)。

\(n \times 1\) 的列向量 \(x\) 和 \(y\) 的点积(内积)相当于 \(x^{T}y\),得到 \((1 \times n)(n \times 1) = 1 \times 1\) 矩阵;而外积相当于 \(xy^{T}\),得到 \((n \times 1)(1 \times n) = n \times n\) 矩阵。\(A^{T}\) 满足 \((Ax)^{T}y = x^{T}(A^{T}y)\),即 \(Ax\) 和 \(y\) 的内积等于 \(x\) 和 \(A^{T}y\) 的内积。

对称矩阵 \(S\) 满足 \(S^{T} = S\),即 \(s_{ji} = s_{ij}\)(反对称矩阵满足 \(S^{T} = -S\))。如果对称矩阵 \(S\) 是可逆的,则 \(S^{-1}\) 也是对称矩阵,因为 \((S^{-1})^{T} = (S^{T})^{-1} = S^{-1}\)。对于任意矩阵 \(A\),\(AA^{T}\) 是对称矩阵,因为 \((AA^{T})^{T} = (A^{T})^{T}A^{T} = AA^{T}\)。

$$ S = \left[\begin{matrix} I & A \\ A^{T} & 0 \end{matrix}\right] = LU = \left[\begin{matrix} I & 0 \\ A^{T} & T \end{matrix}\right] \left[\begin{matrix} I & A \\ 0 & -A^{T}A \end{matrix}\right] = LDL^{T} = \left[\begin{matrix} I & A \\ A^{T} & 0 \end{matrix}\right] \left[\begin{matrix} I & 0 \\ 0 & -A^{T}A \end{matrix}\right] \left[\begin{matrix} I & A \\ 0 & I \end{matrix}\right] $$

The Four Fundamental Subspaces

Vector Spaces and Subspaces

向量空间的定义,向量加法 \(x + y\) 和标量乘法 \(cx\) 必须满足以下八个规则。向量空间的子空间是满足以下条件的向量集合:如果 \(v\) 和 \(w\) 在子空间中,且 \(c\) 和 \(d\) 是任意标量,则所有线性组合 \(cv + dw\) 都在子空间中。矩阵 \(A\) 的列向量的所有线性组合构成列空间 \(C(A)\),方程 \(Ax = b\) 有解当且仅当 \(b\) 在 \(A\) 的列空间中,因为 \(b\) 是 \(A\) 的列向量的线性组合。矩阵 \(A\) 的行是 \(A^{T}\) 的列,所以 \(A\) 的行空间就是 \(A^{T}\) 的列空间 \(C(A^{T})\)。

Computing the Nullspace by Elimination: \(A=CR\)

将 \(Ax = 0\) 化简为阶梯形式 \(Rx = 0\),如果 \(A\) 可逆,则 \(R = I\),否则 \(R=\left[\begin{matrix}I & F\end{matrix}\right]P\)。公式 \(H = WF\) 中,\(W\) 表示 \(A\) 中线性无关的列向量,\(H\) 表示 \(A\) 中线性相关的列向量,\(F\) 表示如何组合 \(A\) 中线性无关的列向量,可以得到 \(A\) 中线性相关的列向量。\(P\) 置换矩阵表示将线性无关的列向量放在 \(A\) 的对应位置上。行最简形矩阵 \(R\) 中,矩阵每行第一个非零元素被称为主元,主元所在的列是主元列,其余列是自由列,主元列对应的变量是主元变量,自由列对应的变量是自由变量。

$$ A = \left[\begin{matrix} 1 & 7 & 3 & 35 \\ 2 & 14 & 6 & 70 \\ 2 & 14 & 9 & 97 \end{matrix}\right] \rightarrow R_{0} = \left[\begin{matrix} 1 & 7 & 0 & 8 \\ 0 & 0 & 1 & 9 \\ 0 & 0 & 0 & 0 \end{matrix}\right] \rightarrow R = \left[\begin{matrix} 1 & 7 & 0 & 8 \\ 0 & 0 & 1 & 9 \end{matrix}\right] $$
$$ W^{-1}A = W^{-1} \left[\begin{matrix} W & H \end{matrix}\right] P \rightarrow R = \left[\begin{matrix} I & W^{-1}H \end{matrix}\right] P = \left[\begin{matrix} I & F \end{matrix}\right] P $$

\(R_{0}\) 是包含零行的 \(R\) 的变体 \(R_{0} = \left[\begin{matrix}I & F \ 0 & 0\end{matrix}\right]P\),\(R_{0}\) 中 \(I\) 的位置指示 \(A\) 中线性无关列向量的位置,从而可以将 \(A = CR\) 中的 \(C\) 求出。\(C\) 的列向量和 \(R\) 的行向量分别张成 \(A\) 的列空间和行空间,它们分别是列空间和行空间的一个基。

$$ A = \left[\begin{matrix} 1 & 7 & 3 & 35 \\ 2 & 14 & 6 & 70 \\ 2 & 14 & 9 & 97 \end{matrix}\right] = \left[\begin{matrix} 1 & 3 \\ 2 & 6 \\ 2 & 9 \end{matrix}\right] \left[\begin{matrix} 1 & 7 & 0 & 8 \\ 0 & 0 & 1 & 9 \end{matrix}\right] = CR $$
$$ A = CR = C \left[\begin{matrix} I & F \end{matrix}\right] P = \left[\begin{matrix} C & CF \end{matrix}\right] P $$

矩阵 \(A\) 的零空间 \(N(A)\) 由 \(Ax = 0\) 的所有解组成。当矩阵 \(A\) 是可逆矩阵时,\(A\) 的列向量线性无关,\(Ax = 0\) 只有零解 \(x = 0\),此时零空间只包含零向量。否则,当 \(m \times n\) 矩阵 \(A\) 有 \(r\) 个线性无关的列时,\(Ax = 0\) 有 \(n - r\) 个特殊解(special solutions),这些特殊解是零空间的一个基,它们的线性组合是 \(Ax = 0\) 的通解,可以直接使用以下方法求出。

$$ Ax = 0 \rightarrow Rx = 0 \rightarrow \left[\begin{matrix} I & F \end{matrix}\right] Px = 0 \rightarrow x = P^{T} \left[\begin{matrix} -F \\ I \end{matrix}\right] $$
$$ R = \left[\begin{matrix} 1 & 7 & 0 & 8 \\ 0 & 0 & 1 & 9 \end{matrix}\right] = \left[\begin{matrix} 1 & 0 & 7 & 8 \\ 0 & 1 & 0 & 9 \end{matrix}\right] \left[\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right] = \left[\begin{matrix} I & F \end{matrix}\right] P $$
$$ x = \left[\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right] \left[\begin{matrix} -7 & -8 \\ 0 & -9 \\ 1 & 0 \\ 0 & 1 \end{matrix}\right] = \left[\begin{matrix} -7 & -8 \\ 1 & 0 \\ 0 & -9 \\ 0 & 1 \end{matrix}\right] = P^{T} \left[\begin{matrix} -F \\ I \end{matrix}\right] $$

The Complete Solution to \(Ax = b\)

将 \(Ax = b\) 化简为 \(R_{0}x = d\),可以利用增广矩阵 \(\left[\begin{matrix}A & b\end{matrix}\right]\) 消元得到 \(\left[\begin{matrix}R_{0} & d\end{matrix}\right]\)。要使 \(Ax = b\) 有解,则 \(R_{0}\) 中的零行在 \(d\) 中也必须是零,此时 \(b\) 在 \(A\) 的列空间中。自由变量 \(x_{2} = x_{4} = 0\) 取值为零,可以得到主元变量 \(x_{1} = 1\) 和 \(x_{3} = 6\),此时得到 \(Ax = b\) 的特定解(particular solution)为 \(x_{p} = (1, 0, 6, 0)\)。当自由变量取零时,因为主元列组成单位矩阵,所以特定解中主元变量的值和 \(d\) 中的值相对应。\(Ax = b\) 的完整解(complete solution )由特定解 \(x_{p}\) 和零空间中的向量 \(x_{n}\) 组成。

$$ \left[\begin{matrix} A & b \end{matrix}\right] = \left[\begin{matrix} 1 & 3 & 0 & 2 & 1 \\ 0 & 0 & 1 & 4 & 6 \\ 1 & 3 & 1 & 6 & 7 \end{matrix}\right] \rightarrow \left[\begin{matrix} 1 & 3 & 0 & 2 & 1 \\ 0 & 0 & 1 & 4 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}\right] = \left[\begin{matrix} R_{0} & d \end{matrix}\right] $$
$$ R_{0}x_{p} = \left[\begin{matrix} 1 & 3 & 0 & 2 & 1 \\ 0 & 0 & 1 & 4 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}\right] \left[\begin{matrix} 1 \\ 0 \\ 6 \\ 0 \end{matrix}\right] = \left[\begin{matrix} 1 \\ 6 \\ 0 \end{matrix}\right] = d $$
$$ x = x_{p} + x_{n} = \left[\begin{matrix} 1 \\ 0 \\ 6 \\ 0 \end{matrix}\right] + x_{2} \left[\begin{matrix} -3 \\ 1 \\ 0 \\ 0 \end{matrix}\right] + x_{4} \left[\begin{matrix} -2 \\ 0 \\ -4 \\ 1 \end{matrix}\right] $$

对于 \(m \times n\) 矩阵,有 \(r \leq \min(m, n)\)。如果矩阵是方阵且满秩(\(r = m = n\)),则方程组有唯一解;如果矩阵不是方阵且列满秩(\(r = n < m\)),则方程组无解或者有唯一解;如果矩阵不是方阵且行满秩(\(r = m < n\)),则方程组有无穷多个解;如果矩阵不满秩(\(r < m, r < n\)),则方程组无解或者有无穷多个解。

Independence, Basis, and Dimension

如果 \(Ax = 0\) 只有零解 \(x = 0\),即零空间 \(N(A)\) 中只有零向量,则矩阵 \(A\) 的列向量线性无关。如果矩阵 \(A\) 是列满秩的,则 \(A\) 的列向量线性无关,此时矩阵 \(A\) 有 \(n\) 个主元、没有自由变量、\(A = CR\) 分解中 \(R = I\)、零空间中只有零向量。如果 \(m \times n\) 矩阵 \(A\) 有 \(n > m\),则矩阵 \(A\) 的列向量必定线性相关,矩阵 \(A\) 的秩 \(r \leq m < n\)、至多有 \(m\) 个主元、\(Ax = 0\) 有 \(n - m\) 个自由变量、\(Ax = 0\) 有非零解。

Another way to describe linear dependence is this: “One vector is a combination of the other vectors.” That sounds clear. Why don’t we say this from the start? Our definition was longer: “Some combination gives the zero vector, other than the trivial combination with every \(x = 0\).” We must rule out the easy way to get the zero vector.

向量空间的基是线性无关的一组向量,它们张成该向量空间。向量空间中的任意向量 \(v\),对应基向量的唯一线性组合。\(n \times n\) 单位矩阵的列向量,构成 \(\mathbf{R}^{n}\) 的标准基。每个 \(n \times n\) 可逆矩阵的列向量组,都构成 \(\mathbf{R}^{n}\) 的一个基。向量空间的基总是包含相同数量的向量,基向量的数量是该向量空间的维数。矩阵列空间的维数等于矩阵的秩。

零向量永远不会作为基向量,因为零向量总是和其他向量线性相关。将零向量的系数设为任意非零值,其他向量的系数设为零,就可以得到 \(Ax = 0\) 的非零解。只包含零向量的空间 \(\mathbf{Z}\) 的维数是零,空集是该空间的基。

Dimensions of the Four Subspaces

\(A\) 的行空间是 \(A^{T}\) 的列空间,\(A\) 的左零空间是 \(A^{T}\) 的零空间。之所以称为左零空间,是因为该空间由 \(xA = 0\) 的所有解组成,\(xA = 0 \rightarrow A^{T}x^{T} = 0 \rightarrow A^{T}y = 0\)。行变换不会改变行空间和零空间(变换矩阵是可逆的),但是会改变列空间和左零空间,列变换同理。列空间的基是 \(R\) 的 \(r\) 个主元列在 \(A\) 中对应的列,行空间的基是 \(R\) 的 \(r\) 个行,零空间的基是 \(Rx = 0\) 的 \(r\) 个特解。如果 \(EA = R_{0}\),因为 \(R_{0}\) 的最后 \(m - r\) 行都是零,所以左零空间的基是 \(E\) 的最后 \(m - r\) 行。消元矩阵 \(E\) 可以通过将增广矩阵 \(\left[\begin{matrix}A & I\end{matrix}\right]\) 消元为 \(\left[\begin{matrix}R_{0} & E\end{matrix}\right]\) 得到。

矩阵 \(AB\) 的行是矩阵 \(B\) 的行的线性组合,所以 \(rank(AB) \leq rank(B)\)。矩阵 \(AB\) 的列是矩阵 \(A\) 的列的线性组合,所以 \(rank(AB) \leq rank(A)\)。也就是说,\(rank(AB) \leq \min(rank(A), rank(B))\)。当矩阵 \(B\) 可逆时,\(rank(AB) = rank(A)\)。以下是推导过程,假设 \(A\) 是 \(m \times n\) 矩阵,\(B\) 是 \(n \times n\) 矩阵。

$$ rank(A) = rank(ABB^{-1}) \leq \min(rank(AB), rank(B^{-1})) = \min(rank(AB), n) = rank(AB) $$

Orthogonality

Orthogonality of Vectors and Subspaces

正交向量满足 \(v \cdot w = v^{T}w = 0\) 和 \(|v|^{2} + |w|^{2} = |v + w|^{2}\)。如果子空间 \(V\) 中的任意向量 \(v\) 和子空间 \(W\) 中的任意向量 \(w\) 满足 \(v^{T}w = 0\),则子空间 \(V\) 和 \(W\) 正交。如果 \(V\) 和 \(W\) 是 \(\mathbf{R}^{n}\) 中的正交子空间,则 \(\dim{V} + \dim{W} \leq n\)。\(V\) 的正交补 \(V^{\perp}\) 包含所有和 \(V\) 正交的向量。两个正交子空间的交集仅包含零向量。每个秩为 \(r\) 的矩阵都有 \(r \times r\) 的可逆子矩阵。

任意矩阵 \(A\) 的行空间和零空间正交,列空间和左零空间正交。非正式证明:零空间的向量 \(x\) 满足 \(Ax = 0\),可以发现 \(A\) 中的每个行向量点乘 \(x\) 都是零,所以 \(A\) 中行向量的线性组合和 \(x\) 正交,即行空间和零空间正交。正式证明:假设 \(x\) 在零空间中、\(A^{T}y\) 在行空间中,则 \(x\) 满足 \(Ax = 0\),两者的内积 \(x^{T}(A^{T}y) = (Ax)^{T}y = 0^{T}y = 0\),所以零空间和行空间正交。同理,可以证明列空间和左零空间正交。

行空间和零空间互为正交补 \(r + (n - r) = n\),列空间和左零空间互为正交补 \(r + m - r = m\)。行空间和零空间组合构成整个 \(\mathbf{R}^{n}\) 空间,列空间和左零空间组合构成整个 \(\mathbf{R}^{m}\) 空间。\(\mathbf{R}^{n}\) 空间中的向量可以表示为 \(x = x_{row} + x_{null}\),\(\mathbf{R}^{m}\) 中的向量可以表示为 \(y = y_{col} + y_{null}\)。对于 \(Ax = b, x = x_{r} + x_{n}\),列空间中的每个向量 \(b\) 都由行空间中唯一的向量 \(x_{r}\) 确定。

Projections onto Lines and Subspaces

假设向量 \(b\) 在向量 \(a\) 所在直线上的投影是向量 \(p\),则向量 \(p\) 是向量 \(a\) 的倍数,误差向量(error vector)\(e = b - p\) 和向量 \(a\) 垂直。如果 \(b = a\),投影 \(p = a\)。如果 \(a^{T}b = 0\),则投影 \(p = 0\)。向量 \(bpe\) 组成直角三角形的三条边。

$$ p = \hat{x}a, e = b - p, a \cdot e = 0 \rightarrow \hat{x} = \frac{a \cdot b}{a \cdot a} = \frac{a^{T}b}{a^{T}a} \rightarrow \|p\| = \frac{\|a\|\|b\|\cos{\theta}}{\|a\|^{2}}\|a\| = \|b\|\cos{\theta} $$

将向量 \(b\) 投影到向量 \(a\) 所在直线上的投影矩阵 \(P\) 满足 \(p = Pb\) 和 \(P^{2} = P = P^{T}\)。通过以下推导可知,矩阵 \(P\) 由列向量 \(a\) 和行向量 \(a^{T}\) 的外积再除以 \(a^{T}{a}\) 得到,它的秩为 \(1\),而且和向量 \(b\) 无关,只和向量 \(a\) 有关。如果 \(P\) 将向量投影到某个子空间,则 \(I - P\) 将向量投影到该子空间的正交子空间中。

$$ p = a\hat{x} = a\frac{a^{T}b}{a^{T}a} = Pb \rightarrow P = \frac{aa^{T}}{a^{T}a} $$

将向量 \(b\) 投影到 \(m \times n\) 列满秩矩阵 \(A\) 的列空间中,投影向量 \(p\) 根据矩阵 \(A\) 列向量的某种组合 \(\hat{x}\) 得到,误差向量 \(e = b - p\) 和 \(A\) 的列空间垂直,\(|e|\) 是向量 \(b\) 到列空间的距离。根据垂直关系,分别求解得到向量 \(\hat{x}\)、投影向量 \(p\) 以及投影矩阵 \(P\)。对称矩阵 \(A^{T}A\) 是可逆的,当且仅当 \(A\) 的列向量线性无关,两者有相同的零空间 \(\mathbf{N}(A^{T}A) = \mathbf{N}(A)\)。如果 \(P\) 是可逆矩阵,则必然有 \(P^{-1}P^{2} = P^{-1}P \rightarrow P = I\)。

$$ A = \left[\begin{matrix} a_{1} & a_{2} & \cdots & a_{n} \end{matrix}\right] , \hat{x} = \left[\begin{matrix} \hat{x_{1}} \\ \hat{x_{2}} \\ \vdots \\ \hat{x_{n}} \end{matrix}\right] , p = A\hat{x} $$
$$ A^{T}e = A^{T}(b - A\hat{x}) = 0 \rightarrow \hat{x} = (A^{T}A)^{-1}A^{T}b \rightarrow p = A\hat{x} = A(A^{T}A)^{-1}A^{T}b = Pb \rightarrow P = A(A^{T}A)^{-1}A^{T} $$

Least Squares Approximations

假设矩阵 \(A\) 的列向量线性无关,误差 \(e = b - Ax\) 不总是为零,当 \(e\) 为零时,\(x\) 是 \(Ax = b\) 的精确解。否则,假设 \(e\) 的长度在 \(\hat{x}\) 处取到最小值 \(|b - A\hat{x}|^{2}\),此时 \(\hat{x}\) 是 \(Ax = b\) 的最小二乘解。误差 \(e\) 何时取到最小值?

几何角度:当 \(b\) 不在 \(Ax\) 的列空间中时,找到列空间中最接近 \(b\) 的点 \(p\),该 \(p\) 就是 \(b\) 在列空间上的投影,此时 \(e\) 的长度最小,根据上节投影知识,知道 \(\hat{x}\) 满足 \(A^{T}A\hat{x} = A^{T}b\)。代数角度:将向量 \(b\) 分解为在 \(Ax\) 的列空间中的向量 \(p\) 和垂直列空间的向量 \(e\),\(Ax = b = p + e\) 无解,但是 \(Ax = p\) 有解,误差向量长度的平方 \(|Ax - b|^{2} = |Ax - p|^{2} + |e|^{2}\),当 \(Ax = p\) 时误差最小,此时 \(x = \hat{x}\)。(还有微积分角度,偏导为零)

如果矩阵 \(A\) 的列向量线性相关,此时 \(A^{T}A\) 不可逆,不能使用 \(A^{T}A\hat{x} = A^{T}b\) 求解 \(\hat{x}\)。将 \(b\) 分解为 \(b = p + e\),此时 \(A\hat{x} = p\) 有无穷多个解,因为 \(A\) 的零空间有非零向量。

Orthonormal Bases and Gram-Schmidt

互相垂直的单位向量(长度为 \(1\) 的向量)构成的基被称为标准正交基(orthonormal basis)。注意,标准基(standard basis)是标准正交基的特例。如果 \(m \times n\) 矩阵 \(Q\) 的列向量是标准正交的,则 \(Q^{T}Q = I\)。如果 \(Q\) 不是方阵,则反过来不成立 \(QQ^{T} \neq I\)。如果 \(Q\) 是方阵,则 \(Q^{T}Q = I\) 意味着 \(Q^{T} = Q^{-1}\),此时 \(Q\) 被称为正交矩阵。每个置换矩阵都是正交矩阵。如果 \(Q\) 的列向量是标准正交的,则 \((Qx)^{T}(Qy) = x^{T}Q^{T}Qy = x^{T}y\),所以 \(|Qx| = |x|\)。

如果投影使用列向量标准正交的矩阵 \(Q\),而不是列向量线性无关的矩阵 \(A\),可以得到如下公式。投影 \(p\) 由标准正交向量组合而成,其分量是 \(q_{i}(q_{i}^{T}b) = q_{i}(|q_{i}||b|\cos{\theta_{i}}) = q_{i}(|b|\cos{\theta_{i}})\)。

$$ Q^{T}Q\hat{x} = Q^{T}b \rightarrow \hat{x} = Q^{T}b \rightarrow p = Q\hat{x} = QQ^{T}b \rightarrow P = QQ^{T} $$
$$ p = \left[\begin{matrix} q_{1} & q_{2} & \cdots & q_{n} \end{matrix}\right] \left[\begin{matrix} q_{1}^{T}b \\ q_{2}^{T}b \\ \vdots \\ q_{n}^{T}b \end{matrix}\right] = q_{1}(q_{1}^{T}b) + \cdots + q_{n}(q_{n}^{T}b) $$

使用 Gram-Schmidt 方法,从线性无关向量 \(a_{1},\cdots,a_{n}\) 构造标准正交向量 \(q_{1},\cdots,q_{n}\)。首先将 \(a_{1}\) 作为第一个正交向量 \(A_{1}\),假设当前已经处理到 \(a_{j}\),之前的标准正交向量是 \(q_{1}\) 到 \(q_{j - 1}\)。那么第 \(j\) 个正交向量 \(A_{j}\) 就是 \(a_{j}\) 中和之前所有正交向量都垂直的分量,求该分量类似求投影中的误差向量 \(e\)。让 \(a_j\) 减去其在所有 \(q_{i}\) 上的投影向量 \(p_{j}\),得到的就是分量 \(A_{j}\),再除以自身长度就得到标准正交向量 \(q_{j}\)。

$$ A_{j} = a_{j} - p_{j} = a_{j} - \sum_{i = 1}^{j - 1}q_{i}({q_{i}^{T}a_{j}}) = q_{j}\|A_{j}\| = q_{j}(\|a_{j}\|\cos{\theta_{j}}) = q_{j}(q_{j}^{T}a_{j}) $$

使用该方法构造的向量满足 \(A = QR\),矩阵 \(R = Q^{T}A\) 是上三角矩阵,因为之后的 \(q\) 和之前的 \(a\) 正交。因为 \(A\) 的列向量线性无关,\(a_{i}\) 在 \(q_{i}\) 上的分量必然不为零,所以 \(R\) 中的对角元素都是非零正数,矩阵 \(R\) 可逆。正交矩阵 \(Q_{1}\) 乘以正交矩阵 \(Q_{2}\) 结果仍是正交矩阵,\(Q_{2}^{T}Q_{1}^{T}Q_{1}Q_{2} = I = (Q_{1}Q_{2})^{T}(Q_{1}Q_{2})\)。

$$ A = \left[\begin{matrix} a_{1} & a_{2} & \cdots & a_{n} \end{matrix}\right] = \left[\begin{matrix} q_{1} & q_{2} & \cdots & q_{n} \end{matrix}\right] \left[\begin{matrix} q_{1}^{T}a_{1} & q_{1}^{T}a_{2} & \cdots & q_{1}^{T}a_{n} \\ & q_{2}^{T}a_{2} & \cdots & q_{2}^{T}a_{n} \\ & & \ddots & \vdots \\ & & & q_{n}^{T}a_{n} \end{matrix}\right] = QR $$
$$ A^{T}A\hat{x} = A^{T}b \rightarrow (QR)^{T}QR\hat{x} = (QR)^{T}b \rightarrow R\hat{x} = Q^{T}b $$

The Pseudoinverse of a Matrix

每个矩阵 \(A\) 都有伪逆 \(A^{+}\)。当 \(r = n < m\) 时,\(Ax = b\) 无解或者有唯一解,左逆 \(A^{+}\) 对应方程的最小二乘解 \(\hat{x} = (A^{T}A)^{-1}A^{T}b = A^{+}b\)。当 \(r = m < n\) 时,\(Ax = b\) 有无穷多个解,右逆 \(A^{+}\) 对应方程的最小长度解 \(x^{+} = A^{+}b\),通解是 \(x = x^{+} + x_{n}\),最小长度意味着在零空间中的分量为零。当 \(r < m, n\) 时,\(Ax = b\) 无解或者有无穷多个解,伪逆 \(A^{+}\) 对应方程的最小范数(norm)最小二乘解 \(x^{+} = A^{+}b\),不仅最小化 \(|Ax - b|^{2}\),而且最小化 \(|x|\)。

对于 \(m \times n\) 矩阵 \(A\),其伪逆 \(A^{+}\) 是 \(n \times m\) 矩阵。每个在 \(m\) 维空间中的向量 \(y\) 可以分解为垂直的两部分 \(y = b + z\),\(b\) 在 \(A\) 的列空间中,\(z\) 在 \(A\) 的左零空间中,行空间中的某个向量 \(x\) 满足 \(Ax = b\)。\(A^{+}\) 和 \(A^{T}\) 有相同的四个子空间,\(A^{+}A\) 将向量投影到矩阵 \(A\) 的行空间中,\(AA^{+}\) 将向量投影到矩阵 \(A\) 的列空间中。

$$ A^{+}b = x,\ A^{T}z = A^{+}z = 0,\ A^{+}y = A^{+}b + A^{+}z = x $$
$$ P_{row} = A^{+}A = (A^{+}A)^{2} = (A^{A}A)^{T},\ P_{column} = AA^{+} = (AA^{+})^{2} = (AA^{+})^{T} $$

$$ A^{+} = R^{+}C^{+} = R^{T}(RR^{T})^{-1}(C^{T}C)^{-1}C^{T} = R^{T}(C^{T}CRR^{T})^{-1}C^{T} = R^{T}(C^{T}AR^{T})^{-1}C^{T} $$
$$ AA^{+}A = A,\ A^{+}AA^{+} = A^{+},\ (A^{+}A)^{T} = A^{+}A,\ (AA^{+})^{T} = AA^{+} $$

Determinants

3 by 3 Determinants and Cofactors

单位矩阵的行列式有 \(\det{I} = 1\),行交换会反转行列式的符号,行向量乘以某个数会使行列式也乘以该数,行列式是行向量的多重线性函数,\(n\) 阶行列式有 \(n!\) 项,每项包含不同行不同列的元素。矩阵 \(A\) 中元素 \(a_{ij}\) 的余子式(minor)\(M_{ij}\) 是将第 \(i\) 行第 \(j\) 列移除之后,剩余的 \(n - 1\) 阶子矩阵的行列式。元素 \(a_{ij}\) 的代数余子式(cofactor)\(C_{ij}\) 是余子式乘以符号因子 \(C_{ij} = (-1)^{i + j}M_{ij}\)。将第 \(i\) 行中的元素分别乘以对应的代数余子式,然后求和可以得到矩阵 \(A\) 的行列式。

$$ \det \left[\begin{matrix} xa + yA & xb + yB \\ c & d \end{matrix}\right] = x(ad - bc) + y(Ad - Bc),\ \det A = a_{i1}C_{i1} + \cdots + a_{in}C_{in} $$

将矩阵 \(A\) 乘以对应的代数余子式矩阵 \(C\) 的转置(伴随矩阵),将会得到 \((\det{A})I\)。对角线以外的元素都为零,因为其余元素都可以看作是具有两个相同行的矩阵的行列式,行交换会改变行列式的符号,而交换两个相同行得到的行列式相同,所以该矩阵的行列式是零,即其余元素的值为零。由于 \(A^{-1}\) 需要除以行列式得到,所以可逆矩阵的行列式不等于零。逆矩阵 \(A^{-1}\) 中的每个元素,都由两个行列式之比得到(代数余子式比 \(A\) 的行列式)。

$$ AC^{T} = \left[\begin{matrix} a & b \\ c & d \end{matrix}\right] \left[\begin{matrix} d & -c \\ -b & a \end{matrix}\right] = \left[\begin{matrix} \det{A} & 0 \\ 0 & \det{A} \end{matrix}\right] = (\det{A})I \rightarrow A^{-1} = \frac{C^{T}}{\det{A}}, (A^{-1})_{ij} = \frac{C_{ji}}{\det{A}} $$

Computing and Using Determinants

三角矩阵和对角矩阵的行列式可以由对角线元素相乘得到,转置矩阵和原矩阵的行列式相同,矩阵乘积的行列式等于矩阵行列式的乘积。矩阵相加的行列式不意味着矩阵行列式相加,例如 \(\det{I + I} = 2^{n}\)。正交矩阵的行列式为 \(\pm{1}\),可逆矩阵的行列式为主元乘积再乘上 \(\pm{1}\),矩阵 \(U\) 的行列式是主元乘积,矩阵 \(L\) 的行列式是 \(1\),矩阵 \(P\) 的行列式是 \(\pm{1}\)。

$$ \det \left[\begin{matrix} a & b & c \\ & q & r \\ & & z \end{matrix}\right] = \det \left[\begin{matrix} a & & \\ & q & \\ & & z \end{matrix}\right] = aqz,\ \det{A^{T}} = \det{A},\ \det{AB} = (\det{A})(\det{B}) $$
$$ (\det{Q})^{2} = (\det{Q^{T}})(\det{Q}) = \det{Q^{T}Q} = \det{I} = 1 $$
$$ PA = LU \rightarrow (\det{P})(\det{A}) = (\det{L})(\det{U}) = (\det{U}) $$
$$ \det \left[\begin{matrix} row\ 1 \\ row\ 2 - drow\ 1 \\ row\ n \end{matrix}\right] = \det \left[\begin{matrix} row\ 1 \\ row\ 2 \\ row\ n \end{matrix}\right] - d\det \left[\begin{matrix} row\ 1 \\ row\ 1 \\ row\ n \end{matrix}\right] = \det{A} $$

克莱姆法则:如果 \(\det{A}\) 不为零,则可以使用行列式求解 \(Ax = b\),矩阵 \(B_{j}\) 通过将 \(A\) 的第 \(j\) 列替换为向量 \(b\) 得到。

$$ AM_{1} = \left[\begin{matrix} & & \\ & A & \\ & & \end{matrix}\right] \left[\begin{matrix} x_{1} & 0 & 0 \\ x_{2} & 1 & 0 \\ x_{3} & 0 & 1 \end{matrix}\right] = \left[\begin{matrix} b_{1} & a_{12} & a{13} \\ b_{2} & a_{22} & a_{23} \\ b_{3} & a_{32} & a_{33} \end{matrix}\right] = B_{1} \rightarrow x_{1} = \frac{\det{B_{1}}}{\det{A}} $$
$$ x_{1} = \frac{\det{B_{1}}}{\det{A}}, x_{2} = \frac{\det{B_{2}}}{\det{A}}, \dots, x_{n} = \frac{\det{B_{n}}}{\det{A}} $$

Eigenvalues and Eigenvectors

Introduction to Eigenvalues: \(Ax = \lambda x \)

对于 \(n \times n \) 矩阵 \(A \),如果存在非零向量 \(x \) 和标量 \(\lambda \) 使得 \(Ax = \lambda x \),则 \(x \) 和 \(\lambda \) 分别是矩阵 \(A \) 的特征向量和特征值。特征向量 \(x \) 乘矩阵 \(A \) 不会改变方向,只是变为原来的 \(\lambda \) 倍。矩阵 \(A \) 存在特征向量的前提是,\((A - \lambda I)x = 0 \) 有非零解,所以有 \(\det{(A - \lambda I)} = 0 \)。求解该方程可以得到 \(n \) 个特征值(可能重复),然后代入 \((A - \lambda I)x = 0 \) 求解特征向量,特征向量 \(x \) 在矩阵 \(A - \lambda I \) 的零空间中。矩阵 \(A \) 的特征向量 \(x \) 也是矩阵 \(A^{n} \) 的特征向量,只是特征值变为 \(\lambda^{n} \),有 \(A^{n}x = \lambda^{n}x \)。

对于投影矩阵 \(P \),其列空间中的向量 \(x \) 投影到自身 \(Px = x \),其零空间中的向量 \(x \) 投影到零 \(Px = 0x \)。有特征值 \(\lambda = 0 \) 和 \(\lambda = 1 \),特征向量 \(x_{1} = (1, 1) \) 和 \(x_{2} = (1, -1) \)。矩阵 \(P \) 是 Markov 矩阵,每列之和为 \(1 \),必然有特征向量 \(\lambda = 1 \)。矩阵 \(P \) 是奇异矩阵,因为有特征值 \(\lambda = 0 \),所以有 \(\det{(A - \lambda I)} = \det{A} = 0 \)。矩阵 \(P \) 是对称矩阵,特征向量必然正交。如果矩阵偏移单位向量 \(I \),则特征值偏移 \(1 \),特征向量不变,因为 \((A + I)x = (\lambda + 1)x \)。

$$ P = \left[\begin{matrix} 0.5 & 0.5 \\ 0.5 & 0.5 \end{matrix}\right] $$

矩阵 \(A \) 的特征值的乘积等于其行列式,特征值之和等于其主对角线元素和(\(A \) 的迹,trace)。三角矩阵 \(U \) 的特征值就是其主对角线上的元素,因为 \(\det{(A - \lambda I)} \) 就是其主对角线上的元素之积。消元不会改变行列式,但是会改变特征值。正交矩阵 \(Q \) 的特征值的绝对值满足 \(|\lambda| = 1 \),因为 \(|Qx| = |x| \rightarrow |\lambda x| = |x| \)。对称矩阵的特征值为实数,反对称矩阵的特征值为纯虚数。如果矩阵 \(A \) 的特征值是 \(\lambda \),矩阵 \(B \) 的特征值是 \(\beta \),且 \(x \) 是 \(A \) 和 \(B \) 的特征向量,则 \(ABx = A\beta x = \beta Ax = \beta \lambda x \)。

Diagonalizing a Matrix

如果 \(n \times n \) 矩阵 \(A \) 有 \(n \) 个线性无关的特征向量 \(x_{1},\dots,x_{n} \),将这些特征向量作为矩阵 \(X \) 的列向量,则 \(X^{-1}AX \) 是特征值对角矩阵 \(\Lambda \),此时矩阵 \(A \) 被对角化。\(A^{k} \) 有相同的特征向量矩阵 \(X \),特征值对角矩阵 \(\Lambda \) 变为 \(\Lambda^{k} \)。如果矩阵 \(A \) 有 \(n \) 个不同的特征值,则其必然有 \(n \) 个线性无关的特征向量,矩阵可以被对角化。可逆和可对角化之间没有关系,可逆意味着特征值不为零,可对角化意味着有 \(n \) 个线性无关的特征向量。

$$ AX = X\Lambda \rightarrow X^{-1}AX = \Lambda = \left[\begin{matrix} \lambda_{1} \\ & \ddots \\ & & \lambda_{n} \end{matrix}\right] $$
$$ A = X\Lambda X^{-1} \rightarrow A^{k} = (X\Lambda X^{-1})^{k} = X\Lambda^{k}X^{-1} $$

所有矩阵 \(A = BCB^{-1} \) 是相似的(similar),它们有和矩阵 \(C \) 相同的特征值,矩阵 \(B \) 是任意可逆矩阵。如果 A 是 \(m \times n \) 矩阵,\(B \) 是 \(n \times m \) 矩阵,\(AB \) 和 \(BA \) 有相同的非零特征值。可以利用特征向量的性质求斐波那契数列的第 \(k \) 项。

$$ \begin{align} & F_{k + 2} = F_{k + 1} + F_{k} \\ & F_{k + 1} = F_{k + 1} \end{align} \rightarrow u_{k + 1} = \left[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right] u_{k} = Au_{k} \rightarrow \lambda_{1} = \frac{1 + \sqrt{5}}{2}, \lambda_{2} = \frac{1 - \sqrt{5}}{2}, x_{1} = (\lambda_{1}, 1), x_{2} = (\lambda_{2}, 1) $$
$$ u_{0} = \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] = \frac{1}{\lambda_{1} - \lambda_{2}} \left( \left[\begin{matrix} \lambda_{1} \\ 1 \end{matrix}\right] - \left[\begin{matrix} \lambda_{2} \\ 1 \end{matrix}\right] \right) = \frac{x_{1} - x_{2}}{\lambda_{1} - \lambda_{2}} \rightarrow u_{k} = A^{k}u_{0} = \frac{(\lambda_{1})^{k}x_{1} - (\lambda_{2})^{k}x_{2}}{\lambda_{1} - \lambda_{2}} $$

Symmetric Positive Definite Matrices

Calculus

参考 Single Variable CalculusMultivariable Calculus

Differentiation

Part A: Definition and Basic Rules

几何解释:切线的斜率。物理解释:变化率。如果函数在 \(x_{0}\) 处连续,则 \(\lim_{x\to x_{0}}f(x) = f(x_{0})\)。而极限 \(\lim_{x\to x_{0}}f(x)\) 存在,意味着 \(\lim_{x\to x_{0}^{-}} f(x) = \lim_{x\to x_{0}^{+}} f(x)\)。如果函数在 \(x_{0}\) 处可导,则函数在 \(x_{0}\) 处连续。

$$ f^{\prime}(x) = \lim_{\Delta x\to 0} \frac{f(x + \Delta x) - f(x)}{\Delta x} $$
$$ \lim_{x\to 0}\frac{\sin x}{x} = 1,\ \lim_{x\to 0}\frac{1 - \cos x}{x} = 0 $$

第一类间断点(左右极限都存在):① 跳跃间断点,左右极限存在且不相等;② 可去间断点,左右极限存在且相等,但是函数在该点未定义,或者函数值不等于极限值。第二类间断点(左右极限至少有一个不存在):① 无穷间断点,左右极限为无穷大;② 振荡间断点:左右极限在该点振荡。

$$ (f \pm g)^{\prime} = f^{\prime} \pm g^{\prime},\ (fg)^{\prime} = f^{\prime}g + fg^{\prime},\ (\frac{f}{g})^{\prime} = \frac{f^{\prime}g - fg^{\prime}}{g^{2}},\ (f \circ g)^{\prime}(x) = f^{\prime}(g(x))g^{\prime}(x) $$
$$ f^{(n)}(x) = \frac{d}{dx}f^{(n - 1)} = \frac{d^{n}f}{dx^{n}} = (\frac{d}{dx})^{n}f = D^{n}f $$

Part B: Implicit Differentiation and Inverse Functions

对隐函数求导,可以利用链式法则,令 \(u = y^{2}\),则 \(\frac{d}{dx}y^{2} = \frac{du}{dx} = \frac{du}{dy}\frac{dy}{dx} = 2y\frac{dy}{dx}\)。函数 \(f^{-1}(y)\) 是 \(f(x)\) 的反函数,则 \(f^{-1}(f(x)) = x\),原函数和反函数关于 \(y = x\) 对称。根据如下推导,反函数的导数是原函数导数的倒数。

$$ x^{2} + y^{2} = 1 \rightarrow \frac{d}{dx}(x^{2} + y^{2}) = \frac{d}{dx}(1) \rightarrow \frac{d}{dx}x^{2} + \frac{d}{dx}y^{2} = 0 \rightarrow 2x + (\frac{d}{dy}y^{2})\frac{dy}{dx} = 0 \rightarrow 2x + 2y\frac{dy}{dx} = 0 \rightarrow \frac{dy}{dx} = -\frac{x}{y} $$
$$ y = f(x) \rightarrow f^{-1}(y) = x \rightarrow \frac{d}{dx}f^{-1}(y) = \frac{d}{dx}x \rightarrow \frac{d}{dy}(f^{-1}(y))\frac{d}{dx}y = 1 \rightarrow \frac{d}{dy}f^{-1}(y) = \frac{1}{\frac{dy}{dx}} $$
$$ y = \tan^{-1}x \rightarrow \tan y = x,\ \frac{d}{dy}\tan y = \sec^{2}y \rightarrow \frac{d}{dx}\tan y = \frac{d}{dx}x \rightarrow \frac{d}{dy}(\tan y)\frac{d}{dx}y = \frac{d}{dx}x \rightarrow \frac{dy}{dx} = \cos^{2}y \rightarrow \frac{dy}{dx} = \frac{1}{1 + x^{2}} $$

假设某个数 \(e\) 满足 \(M(e) = 1\),定义 \(e^{x}\) 的反函数为 \(\ln x\),则 \(\frac{d}{dx}a^{x} = a^{x}\ln a\)。

$$ \frac{d}{dx}a^{x} = \lim_{\Delta x\to 0}\frac{a^{x + \Delta x} - a^{x}}{\Delta x} = a^{x}\lim_{\Delta x\to 0}\frac{a^{\Delta x} - 1}{\Delta x} = a^{x}\left.\frac{d}{dx}a^{x}\right|_{x = 0} = a^{x}M(a) \\ M(e) = 1,\ \frac{d}{dx}e^{x} = e^{x}M(e) = e^{x} \\ \frac{d}{dx}a^{x} = a^{x}M(e^{\ln a}) = a^{x}\ln a $$
$$ \lim_{x\to \infty}(1 + \frac{1}{x})^{x} \rightarrow \ln(1 + \frac{1}{x})^{x} = x\ln(1 + \frac{1}{x}) \\ \lim_{x\to \infty}(x\ln(1 + \frac{1}{x})) = \lim_{\Delta x\to 0}(\frac{1}{\Delta x}\ln(1 + \Delta x)) = \lim_{\Delta x\to 0}(\frac{1}{\Delta x}(\ln(1 + \Delta x) - \ln 1)) = \left.\frac{d}{dx}\ln x\right|_{x = 1} = 1 \\ \lim_{x\to \infty}(1 + \frac{1}{x})^{x} = \lim_{x\to \infty}e^{\ln(1 + \frac{1}{x})^{x}} = e^{\lim_{x\to \infty}(x\ln(1 + \frac{1}{x}))} = e $$

Applications of Differentiation

Part A: Approximation and Curve Sketching

在 \(x = x_{0}\) 附近,有 \(f(x) \approx f(x_{0}) + f^{\prime}(x_{0})(x - x_{0})\)。可以从图像角度理解,切线和函数在该点附近近似。或者从变化率角度理解,\(f^{\prime}(x_{0})(x - x_{0}) = f^{\prime}(x_{0})\Delta x\),即该点的变化率乘以 \(\Delta x\) 就是 \(\Delta f\) 的近似。\(\Delta x\to 0\) 但是不是极限,所以有误差。在 \(x = x_{0}\) 处,泰勒公式和原函数的各阶导数相同。

$$ f(x) \approx f(x_{0}) + f^{\prime}(x_{0})(x - x_{0}) + \frac{f^{\prime\prime}(x_{0})}{2!}(x - x_{0})^{2} + \dots + \frac{f^{(n)}(x_{0})}{n!}(x - x_{0})^{n} \quad (x \approx x_{0}) $$
$$ \sin x \approx x,\ \cos x \approx 1,\ e^{x} \approx 1 + x,\ \ln(1 + x) \approx x,\ (1 + x)^{r} \approx 1 + rx \quad (x \approx 0) $$
$$ \frac{e^{-3x}}{\sqrt{1 + x}} \approx (1 - 3x)(1 - \frac{1}{2}x) \approx 1 - \frac{7}{2}x + \frac{3}{2}x^{2} \approx 1 - \frac{7}{2}x \quad (x \approx 0) $$

如果 \(f^{\prime} > 0\),则函数递增。如果 \(f^{\prime} < 0\),则函数递减。如果 \(f^{\prime\prime} > 0\),则函数下凸(上凹)。如果 \(f^{\prime\prime} < 0\),则函数上凸(下凹)。当 \(f^{\prime}(x_{0}) = 0\) 时,称 \(x_{0}\) 为驻点,\(f(x_{0})\) 为驻点值。当 \(f^{\prime\prime}(x_{0}) = 0\) 时,且该点两侧二阶导数符号不同,称 \(x_{0}\) 为拐点,\(f(x_{0})\) 为拐点值。

使用牛顿迭代法求方程 \(f(x) = 0\) 的近似解,基本思路是选择接近解的点 \(x_{0}\),然后找到函数 \(f(x)\) 在该点的切线,切线和 \(x\) 轴的交点作为 \(x_{1}\),以此类推,最终 \(x_{n + 1}\) 会收敛到方程 \(f(x) = 0\) 的某个解上。

$$ x_{n + 1} = x_{n} - \frac{f(x_{n})}{f^{\prime}(x_{n})} $$

牛顿迭代法适用条件:\(x_{0}\) 在解附近,\(|f^{\prime}|\) 不太小,\(|f^{\prime\prime}|\) 不太大。\(|f^{\prime}|\) 太小意味着斜率太小,\(x_{1}\) 距离 \(x_{0}\) 就会很远,导致收敛到其他解上或者无法收敛。\(|f^{\prime\prime}|\) 太大表示斜率变化率太大,该点的切线不能很好的近似函数 \(f\)。

Part C: Mean Value Theorem, Antiderivatives and Differential Equations

中值定理:如果函数 \(f(x)\) 在闭区间 \([a, b]\) 上连续,在开区间 \((a, b)\) 上可导,则在开区间 \((a, b)\) 中至少存在一点 \(c\),使得 \(f^{\prime}© = \frac{f(b) - f(a)}{b - a}\)。对于函数 \(y = f(x)\),\(y\) 的微分是 \(dy = f^{\prime}(x)dx\)。函数 \(g(x)\) 的不定积分是 \(G(x) = \int g(x)dx\)。

$$ \min_{a \leq x \leq b}f^{\prime}(x) \leq \frac{f(b) - f(a)}{b - a} = f^{\prime}(c) \leq \max_{a \leq x \leq b}f^{\prime}(x) $$
$$ G^{\prime}(x) = g(x),\ dG = g(x)dx $$
$$ \int x^{n}dx = \frac{x^{n + 1}}{n + 1} + c \quad (n \neq 1),\ \int \frac{1}{x}dx = \ln{|x|} + c $$

使用换元法求解积分,使用分离变量法求解微分方程。虽然求解得出 \(a > 0\),但是验证之后发现该解对任意 \(a\) 都成立,所以结果不对其做限制。

$$ \begin{align} \int x^{3}(x^{4} + 2)^{5} &= \int (x^{4} + 2)^{5}x^{3}dx \quad (u = x^{4} + 2,\ x^{3}dx = \frac{1}{4}du) \\ &= \frac{1}{4}\int u^{5}du = \frac{1}{24}u^{6} + c = \frac{1}{24}(x^{4} + 2)^{6} + c \end{align} $$
$$ \frac{dy}{dx} + xy = 0 \rightarrow \frac{1}{y}dy = -xdx \quad (y \neq 0) \rightarrow \int \frac{1}{y}dy = \int -xdx \quad (y \neq 0) \rightarrow \\ \ln y = -\frac{1}{2}x^{2} + c \quad (y \gt 0) \rightarrow y = ae^{-\frac{1}{2}x^{2}} \quad (a = e^{c} \gt 0) \rightarrow y = ae^{-\frac{1}{2}x^{2}} $$

The Definite Integral and its Applications

Part A: Definition of the Definite Integral and First Fundamental Theorem

\(\int_{a}^{b}f(x)dx\) 表示函数 \(f(x)\) 在区间 \((a, b)\) 下的面积(有正负)。可以将区间 \((a, b)\) 划分为 \(n\) 等分,计算 \(n\) 个矩形的面积之和(黎曼和),在 \(\lim_{n \to \infty}\) 时得到定积分的值。

$$ \lim_{n \to \infty}\sum_{i = 1}^{n}f(c_{i})\Delta x = \int_{a}^{b}f(x)dx $$

微积分第一基本定理:如果函数 \(f(x)\) 在区间 \([a, b]\) 上连续,且 \(F^{\prime}(x) = f(x)\),则其满足以下公式。如果 \(f(x) \leq g(x)\) 且 \(a \leq b\),则 \(\int_{a}^{b}f(x)dx \leq \int_{a}^{b}g(x)dx\)。如果 \(u\) 在区间 \(x_{1} \lt x \lt x_{2}\) 是单调的,则 \(\int_{u_{1}}^{u_{2}}g(u)du = \int_{x_{1}}^{x_{2}}g(u(x))u^{\prime}(x)dx\),其中 \(u_{1} = u(x_{1})\)、\(u_{2} = u(x_{2})\)。

$$ \int_{a}^{b}f(x)dx = F(b) - F(a) = \left.F(x)\right|_{a}^{b} $$
$$ \int_{a}^{b}f(x)dx = -\int_{b}^{a}f(x)dx,\ \int_{a}^{b}f(x)dx + \int_{b}^{c}f(x)dx = \int_{a}^{c}f(x)dx $$
$$ \int_{-1}^{1}x^{2}dx = \frac{2}{3} \neq \int_{1}^{1}u\frac{1}{2\sqrt u}du = 0 \quad (u = x^{2}) $$

Part B: Second Fundamental Theorem, Areas, Volumes

微积分第二基本定理:如果 \(f(x)\) 在区间 \([a, b]\) 上连续,且 \(G(x) = \int_{a}^{x}f(t)dt\),则 \(G^{\prime}(x) = f(x)\),\(G(a) = 0\)。

$$ F(x) = \int_{0}^{x}e^{-t^{2}}dt,\ \lim_{x \to \infty}F(x) = \frac{\sqrt \pi}{2},\ \lim_{x \to -\infty}F(x) = -\frac{\sqrt \pi}{2} \\ erf(x) = \frac{2}{\sqrt \pi}\int_{0}^{x}e^{-t^{2}}dt = \frac{2}{\sqrt \pi}F(x) $$

Part C: Average Value, Probability and Numerical Integration

$$ \text{Continuous Average} = \frac{1}{b - a}\int_{a}^{b}f(x)dx = Ave(f) $$
$$ \text{weighted average} = \frac{\int_{a}^{b}f(x)w(x)dx}{\int_{a}^{b}w(x)dx} $$
$$ P(x_{1} \lt x \lt x_{2}) = \frac{\int_{x_{1}}^{x_{2}}w(x)dx}{\int_{a}^{b}w(x)dx} = \frac{\text{Part}}{\text{Whole}} \quad (a \leq x_{1} \lt x_{2} \leq b) $$

Techniques of Integration

Part A: Trigonometric Powers, Trigonometric Substitution and Completing the Square

$$ \int \sin^{3}xdx = \int (1 - \cos^{2}x)\sin xdx = \int (1 - u^{2})(-du) = -\cos x + \frac{\cos^{3}x}{3} + c \quad (u = \cos x) $$
$$ \int \cos^{2}xdx = \int \frac{1 + \cos(2x)}{2}dx = \frac{x}{2} + \frac{\sin(2x)}{4} + c $$
$$ \sec^{2}x = 1 + \tan^{2}x,\ \frac{d}{dx}\tan x = \sec^{2}x,\ \frac{d}{dx}\sec x = \sec x\tan x $$
$$ \int \frac{dx}{x^{2}\sqrt{1 + x^{2}}} = \int \frac{\sec\theta d\theta}{\tan^{2}\theta} \quad (x = \tan\theta) = \int \frac{\cos\theta d\theta}{\sin^{2}\theta} = -\frac{1}{u} + c \quad(u = \sin\theta) = -\csc\theta + c = -\frac{\sqrt{1 + x^{2}}}{x} + c $$

Part B: Partial Fractions, Integration by Parts, Arc Length, and Surface Area

使用 Partial Fractions 分解 \(\frac{P(x)}{Q(x)} = \text{quotient} + \frac{R(x)}{Q(x)}\)。如果 \(P(x)\) 的幂次大于等于 \(Q(x)\) 的幂次,则将商提取出来。然后分解 \(Q(x)\),根据以下规则将分子设置为未知数形式,使用 cover-up 方法求解未知数。对于无法这样求解的未知数,则通过对比左右对应幂次项的系数或者直接设置 \(x\) 的值得到方程组,求解方程组得到剩余未知数的解。

$$ \frac{x^{2} + 2}{(x - 1)^{2}(x + 2)} = \frac{A}{x - 1} + \frac{B}{(x - 1)^{2}} + \frac{C}{x + 2},\ \frac{x^{2}}{(x - 1)(x^{2} + 1)} = \frac{A}{x - 1} + \frac{Bx + C}{x^{2} + 1},\ \frac{x^{3}}{(x - 1)(x + 2)} = x - 1 + \frac{3x - 2}{x^{2} + x - 2} $$

使用分部积分法求积分,需要 \(u\) 的导数更简单,而 \(v\) 的积分不会太复杂。使用勾股定理推出弧长公式。

$$ (uv)^{\prime} = u^{\prime}v + uv^{\prime} \rightarrow \int uv^{\prime}dx = uv - \int u^{\prime}vdx \\ ds = \sqrt{dx^{2} + dy^{2}} \rightarrow \text{Arc Length} = \int_{a}^{b}\sqrt{1 + (\frac{dy}{dx})^{2}}dx $$
$$ \int (\ln x)^{n}dx = x(\ln x)^{n} - n\int(\ln x)^{n - 1}dx \quad (u = (\ln x)^{n},\ v = x) \\ F_{n}(x) = \int (\ln x)^{n}dx \rightarrow F_{n}(x) = x(\ln x)^{n} - nF_{n - 1}(x) $$

Part C: Parametric Equations and Polar Coordinates

可以将参数方程的变量 \(t\) 看作时间,坐标 \((x(t), y(t))\) 看作轨迹。使用勾股定理推出参数化的弧长公式。

$$ ds = \sqrt{dx^{2} + dy^{2}} \rightarrow ds = \sqrt{(\frac{dx}{dt})^{2} + (\frac{dy}{dt})^{2}}dt $$
$$ \left\{\begin{align} x &= 2\sin t \\ y &= \cos t \end{align}\right. \rightarrow \frac{x^{2}}{4} + y^{2} = 1 \rightarrow \frac{ds}{dt} = \sqrt{(2\cos t)^{2} + (\sin t)^{2}} = \sqrt{4\cos^{2}t + \sin^{2}t} \\ \text{Arc Length} = \int_{0}^{2\pi}\sqrt{4\cos^{2}t + \sin^{2}t}dt $$

极坐标使用到原点的距离 \(r\) 和夹角 \(\theta\) 表示平面上的点。使用面积占比等于弧长占比推出面积公式。

$$ x = r\cos\theta,\ y = r\sin\theta,\ r^{2} = x^{2} + y^{2},\ \tan\theta = \frac{y}{x} \\ \frac{dA}{\pi r^{2}} = \frac{d\theta}{2\pi r} \rightarrow dA = \frac{1}{2}r^{2}d\theta \rightarrow A = \int_{\theta_{1}}^{\theta_{2}}\frac{1}{2}r^{2}d\theta $$

Exploring the Infinite

Part A: L’Hospital’s Rule and Improper Integrals

使用洛必达法则求解 \(0/0\) 和 \(\infty/\infty\) 型未定式 \(\lim_{x\to a}\frac{f(x)}{g(x)} = \lim_{x\to a}\frac{f^{\prime}(x)}{g^{\prime}(x)}\)。如果 \(p \gt 0\),当 \(x \to \infty\) 有 \(\ln x \ll x^{p} \ll e^{x}\)。

$$ \lim_{x \to a}\frac{f(x)}{g(x)} = \lim_{x \to a}\frac{f(x)/(x - a)}{g(x)/(x - a)} = \frac{\lim_{x \to a}(f(x)/(x - a))}{\lim_{x \to a}(g(x)/(x - a))} = \frac{\lim_{x \to a}\frac{f(x) - f(a)}{x - a}}{\lim_{x \to a}\frac{g(x) - g(a)}{x - a}} \quad (f(a) = g(a) = 0) = \frac{f^{\prime}(a)}{g^{\prime}(a)} $$
$$ \lim_{x \to 0^{+}}x^{x} = e^{\lim_{x \to 0^{+}}x\ln x} = e^{\lim_{x \to 0^{+}}\frac{\ln x}{\frac{1}{x}}} = e^{\lim_{x \to 0^{+}}-x} = e^{0} = 1 $$

函数 \(f(x) \gt 0\) 的反常积分为 \(\int_{a}^{\infty}f(x)dx = \lim_{N \to \infty}\int_{a}^{N}f(x)dx\),如果极限存在,则反常积分收敛,否则发散。

$$ \int_{0}^{\infty}e^{-kx}dx = \frac{1}{k},\ \int_{-\infty}^{\infty}e^{-x^{2}}dx = \sqrt \pi,\ \int_{1}^{\infty}\frac{dx}{x^{p}} = \frac{\infty^{-p + 1}}{-p + 1} + \frac{1}{p - 1} \quad (p \neq 1) $$
$$ \int_{-1}^{1}\frac{dx}{x^{2}} = \int_{-1}^{0}\frac{dx}{x^{2}} + \int_{0}^{1}\frac{dx}{x^{2}} = \infty \neq \left.-x^{-1}\right|_{-1}^{1} = -2 $$

Part B: Taylor Series

如果 \(f(x)\) 在区间 \([1, \infty]\) 递减且 \(f(x) > 0\),则 \(\sum_{1}^{\infty}f(n)\) 和 \(\int_{1}^{\infty}f(x)dx\) 同时收敛或发散,其满足如下公式。如果 \(f(n) \sim g(x)\)(\(\lim_{n \to \infty}\frac{f(n)}{g(n)} = 1\)),且对于所有 \(n\) 都有 \(g(n) \gt 0\),则 \(\sum_{n = 1}^{\infty}f(n)\) 和 \(\sum_{n = 1}^{\infty}g(n)\) 同时收敛或发散。

$$ \sum_{1}^{\infty}f(n) - \int_{1}^{\infty}f(x)dx < f(1) $$
$$ \sum_{n = 0}^{\infty}x^{n} = \frac{1}{1 - x} \quad (|x| \lt 1),\ \sum_{n = 1}^{\infty}\frac{1}{n^{2}} = \frac{\pi^{2}}{6},\ \lim_{N \to \infty}\ln N \lt \sum_{n = 1}^{\infty}\frac{1}{n} = \infty \lt \lim_{N \to \infty}\ln N + 1 $$

Vectors and Matrices

Part A: Vectors, Determinants, and Planes

向量可以被视作位移,\(\vec{PQ} = \vec{Q} - \vec{P}\) 表示从点 \(P\) 到 \(Q\) 的位移。使用余弦定理证明点积的代数和几何表示等价。如果 \(\hat u\) 是单位向量,则向量 \(A\) 在 \(\hat u\) 方向上的分量是 \(A \cdot \hat u = |A|\cos\theta\)(分量是标量)。两个向量的叉乘仍是向量,方向垂直于两个向量所在的平面,符合右手定则。使用拉格朗日恒等式推出叉乘的几何表示。

$$ |A - B|^{2} = |A|^{2} + |B|^{2} + 2|A||B|\cos\theta \rightarrow A \cdot B = ac - bd = |A||B|\cos\theta $$
$$ \text{Area} = |\det(A, B)|,\ \text{Volume} = |\det(A, B, C)| $$
$$ A \times B = \left|\begin{matrix} i & j & k \\ a_{1} & a_{2} & a_{3} \\ b_{1} & b_{2} & b_{3} \end{matrix}\right| = i \left|\begin{matrix} a_{2} & a_{3} \\ b_{2} & b_{3} \end{matrix}\right| - j \left|\begin{matrix} a_{1} & a_{3} \\ b_{1} & b_{3} \end{matrix}\right| + k \left|\begin{matrix} a_{1} & a_{2} \\ b_{1} & b_{2} \end{matrix}\right| = \langle a_{2}b_{3} - a_{3}b_{2}, a_{3}b_{1} - a_{1}b_{3}, a_{1}b_{2} - a_{2}b_{1} \rangle $$
$$ |A \times B|^{2} = |A|^{2}|B|^{2} - (A \cdot B)^{2} \rightarrow |A \times B| = |A||B|\sin\theta $$

Part B: Matrices and Systems of Equations

$$ A = \left[\begin{matrix} 4 & 1 \\ 1 & 3 \end{matrix}\right] , i = \left[\begin{matrix} 1 \\ 0 \end{matrix}\right] , j = \left[\begin{matrix} 0 \\ 1 \end{matrix}\right] \rightarrow Ai = \left[\begin{matrix} 4 \\ 1 \end{matrix}\right] , Aj = \left[\begin{matrix} 1 \\ 3 \end{matrix}\right] $$

如果已知平面上的点 \(P_{0} = (x_{0}, y_{0}, z_{0})\) 和法向量 \(\vec{N} = \langle a, b, c \rangle\),设 \(P = (x, y, z)\) 为平面上任意点,则平面方程如下。

$$ N \cdot \vec{P_{0}P} = 0 \iff a(x - x_{0}) + b(y - y_{0}) + c(z - z_{0}) = 0 $$
$$ d = |PR| = |\vec{PQ}|\cos\theta = \left|\vec{PQ} \cdot \frac{N}{|N|}\right| $$

$$ d = |\vec{QP}|\sin\theta = \left|\vec{QP} \times \frac{v}{|v|}\right| $$

Part C: Parametric Equations for Curves

如果直线过点 \(P_{0} = (x_{0}, y_{0}, z_{0})\),且和向量 \(\vec{v} = \langle v_{1}, v_{2}, v_{3} \rangle\) 的方向相同,则直线的参数方程如下。圆、抛物线和摆线的参数方程也在下面列出。将 \(t\) 看作时间,则位置、速度(切向量)、速率和加速度的关系如下。

$$ r(t) = \langle x, y, z \rangle = \vec{OP_{0}} + tv = \langle x_{0} + tv_{1}, y_{0} + tv_{2}, z_{0} + tv_{3} \rangle $$
$$ x(t) = a\cos t, y(t) = a\sin t \quad x(t) = a\cos t, y(t) = b\cos t \quad x(\theta) = a\theta - a\sin\theta, y(\theta) = a - a\cos\theta $$

Partial Derivatives

Part A: Functions of Two Variables, Tangent Approximation and Optimization

对于函数 \(w = f(x, y)\),当固定 \(y = y_{0}\) 时,得到偏函数 \(w = f(x, y_{0})\)。该偏函数在 \(x = x_{0}\) 处的导数就是函数 \(f\) 在 \((x_{0}, y_{0})\) 处的偏导数,表示当 \(y = y_{0}\) 时,\(w\) 关于 \(x\) 的变化率。该函数在点 \((x_{0}, y_{0}, w_{0})\) 处的切平面,必然包含两个偏函数在该点的切线,其方程如下所示。如果在 \((x_{0}, y_{0})\) 附近,偏函数 \(f_{x}\) 和 \(f_{y}\) 连续,则在该点附近切平面近似曲线。

$$ \left.\frac{d}{dx}f(x, y_{0})\right|_{x_{0}} = \left.\frac{\partial f}{\partial x}\right|_{(x_{0}, y_{0})} = \left.\frac{\partial w}{\partial x}\right|_{(x_{0}, y_{0})} = \left(\frac{\partial f}{\partial x}\right)_{0} = \left(\frac{\partial w}{\partial x}\right)_{0} = f_{x}(x_{0}, y_{0}) $$
$$ A(x - x_{0}) + B(y - y_{0}) + C(w - w_{0}) = 0 \rightarrow w - w_{0} = a(x - x_{0}) + b(y - y_{0}) \quad (C \neq 0, a = \frac{A}{C} = \left(\frac{\partial w}{\partial x}\right)_{0}, b = \frac{B}{C} = \left(\frac{\partial w}{\partial y}\right)_{0} $$
$$ f(x, y) \approx w_{0} + \left(\frac{\partial w}{\partial x}\right)_{0}(x - x_{0}) + \left(\frac{\partial w}{\partial y}\right)_{0}(y - y_{0}) \iff \Delta w \approx \left(\frac{\partial w}{\partial x}\right)_{0}\Delta x + \left(\frac{\partial w}{\partial y}\right)_{0}\Delta y \quad (\Delta x, \Delta y \approx 0) $$

极值点处的切平面水平,有 \(f_{x} = 0\) 和 \(f_{y} = 0\),但是满足该条件的点不一定是极值点。最小二乘法拟合直线 \(y = ax + b\),需要最小化 \(D = \sum_{i = 1}^{n}(y_{i} - (ax_{i} + b))^{2}\),相当于求 \(D = f(a, b)\) 的极值点,令各个偏导为零可以推出如下方程组。

$$ \left\{\begin{align} \bar{s}a + \bar{x}b &= \frac{1}{n}\sum{x_{i}y_{i}} \\ \bar{x}a + b &= \bar{y} \end{align}\right. \quad (\bar{s} = \sum{\frac{x_{i}^{2}}{n}}) $$

对于单变量函数 \(f(x)\),如果 \(f^{\prime}(x_{0}) = 0\) 且 \(f^{\prime\prime}(x_{0}) \gt 0\),则 \(x_{0}\) 是局部最小值点,而 \(f^{\prime\prime}(x_{0}) \lt 0\) 则为局部最大值点。基本想法是,二阶导数大于零或小于零则一阶导数递增或递减,说明该点两侧的一阶导数符号不同,该点局部最小或最大。对于多变量函数 \(f(x, y)\),假设导数存在且连续,令各个偏导为零,求得临界点 \((x_{0}, y_{0})\),然后通过以下测试判断该点是否是极值点。

$$ (f)_{0} = f(x_{0}, y_{0}),\ A = (f_{xx})_{0},\ B = (f_{xy})_{0} = (f_{yx})_{0},\ C = (f_{yy})_{0} $$

Part B: Chain Rule, Gradient and Directional Derivatives

如果 \(w = f(x, y), x = x(u, v), y = y(u, v)\),\(u, v\) 是自变量,\(x, y\) 是中间变量,\(w\) 是因变量,根据切平面近似公式可以推出偏导满足链式法则。同样根据近似公式,得出函数 \(w = f(x, y)\) 的全微分为 \(dw = f_{x}dx + f_{y}dy\)。

$$ \Delta w \approx \left.\frac{\partial w}{\partial x}\right|_{0}\Delta x + \left.\frac{\partial w}{\partial y}\right|_{0}\Delta y \rightarrow \frac{\Delta w}{\Delta u} \approx \left.\frac{\partial w}{\partial x}\right|_{0}\frac{\Delta x}{\Delta u} + \left.\frac{\partial w}{\partial y}\right|_{0}\frac{\Delta y}{\Delta u} \rightarrow \frac{\partial w}{\partial u} = \frac{\partial w}{\partial x}\frac{\partial x}{\partial u} + \frac{\partial w}{\partial y}\frac{\partial y}{\partial u} \quad (\Delta x, \Delta y \approx 0) $$

如果 \(w = f(x, y)\),则 \(\frac{\partial w}{\partial x}\) 和 \(\frac{\partial w}{\partial y}\) 是 \(w\) 在向量 \(i\) 和 \(j\) 方向上的变化率,这两个偏导组成的向量就是 \(w\) 的梯度,梯度和等值线垂直。求 \(x^{2} + 2y^{2} + 3z^{2} = 6\) 在点 \(P = (1, 1, 1)\) 的切平面,可以先求 \(w = x^{2} + 2y^{2} + 3z^{2}\) 在等值面 \(w = 6\) 的梯度,该梯度和等值面垂直也就和切平面垂直,所以可以使用点法式得出切平面的方程 \(2(x - 1) + 4(y - 1) + 6(z - 1) = 0\)。

$$ \text{grad } w = \nabla w = \left\langle\frac{\partial w}{\partial x}, \frac{\partial w}{\partial y}\right\rangle $$

函数 \(w = f(x, y)\) 在点 \(P_{0}\) 处沿单位向量 \(u\) 方向的导数如下,其中 \(\Delta w\) 表示沿 \(u\) 方向移动 \(\Delta s\) 距离之后 \(w\) 的变化量,单位向量 \(u\) 在 \(xy\) 平面中。梯度 \(\nabla w\) 的方向就是 \(w\) 变化率最大的方向,方向导数就是梯度在 \(u\) 方向上的投影大小。

$$ \left\{\begin{align} (\Delta s)^{2} = (\Delta x)^{2} + (\Delta y)^{2} &\rightarrow u = \left\langle\frac{\Delta x}{\Delta s}, \frac{\Delta y}{\Delta s}\right\rangle \\ \Delta w \approx \left(\frac{\partial w}{\partial x}\right)_{0}\Delta x + \left(\frac{\partial w}{\partial y}\right)_{0}\Delta y &\rightarrow \frac{\Delta w}{\Delta s} \approx \left(\frac{\partial w}{\partial x}\right)_{P_{0}}\frac{\Delta x}{\Delta s} + \left(\frac{\partial w}{\partial y}\right)_{P_{0}}\frac{\Delta y}{\Delta s} \end{align}\right. \rightarrow \left.\frac{dw}{ds}\right|_{P_{0}, u} = \lim_{\Delta s \to 0}\frac{\Delta w}{\Delta s} = \left.\nabla w\right|_{P_{0}} \cdot u $$
$$ \left.\frac{dw}{ds}\right|_{u} = \nabla w \cdot u = |\nabla w||u|\cos\theta = |\nabla w|\cos\theta $$

Part C: Lagrange Multipliers and Constrained Differentials

拉格朗日乘数问题:最小化或最大化 \(w = f(x, y, z)\),且满足约束条件 \(g(x, y, z) = c\)。解决方案:局部最小值或最大值必定出现在临界点上,该点满足 \(\nabla f = \lambda\nabla g\)(两个梯度平行)和 \(g(x, y, z) = c\)。对于函数 \(w = f(x, y, z, t)\),\(\left(\frac{\partial w}{\partial x}\right)_{y, t}\) 表示 \(w\) 关于 \(x\) 的偏导,其中 \(x, y, t\) 是自变量,\(z\) 是因变量,\(y, t\) 视为常量。

$$ \left(\frac{\partial x}{\partial y}\right)_{z}\left(\frac{\partial y}{\partial x}\right)_{z} = 1,\ \left(\frac{\partial x}{\partial y}\right)_{z}\left(\frac{\partial y}{\partial t}\right)_{z} = \left(\frac{\partial x}{\partial t}\right)_{z},\ \left(\frac{\partial x}{\partial y}\right)_{z}\left(\frac{\partial y}{\partial z}\right)_{x}\left(\frac{\partial z}{\partial x}\right)_{y} = -1 $$

Double Integrals and Line Integrals in the Plane

Part A: Double Integrals

函数 \(f(x, y)\) 在平面区域 \(R\) 上的二重积分如下。将区域 \(R\) 分为 \(n\) 份,假设第 \(i\) 份的面积为 \(\Delta A_{i}\),点 \((x_{i}, y_{i})\) 在其中,则该二重积分可以看作以曲面 \(f(x, y)\) 为顶,区域 \(R\) 为底的曲顶柱体的体积。

$$ \int\int_{R}f(x, y)dA = \lim_{\Delta A \to 0}\sum_{i = 1}^{n}f(x_{i}, y_{i})\Delta A_{i} $$

计算区域 \(R\) 的二重积分的步骤如下,假设先对 \(y\) 积分再对 \(x\) 积分:将 \(x\) 固定,沿 \(y\) 递增的方向做垂线,积分的下限和上限就是垂线进入和离开区域 \(R\) 时对应的 \(y\) 值;然后让 \(x\) 递增,积分的下限和上限就是垂线和区域 \(R\) 相交的最小和最大 \(x\) 值。先对 \(x\) 积分再对 \(y\) 积分的形式同理,极坐标中的二重积分也是这样计算的。

$$ \int\int_{R}f(x, y)dydx = \int_{0}^{1}\int_{1 - x}^{\sqrt{1 - x^{2}}}f(x, y)dydx = \int_{0}^{1}\int_{1 - y}^{\sqrt{1 - y^{2}}}f(x, y)dxdy $$

$$ dA = rdrd\theta $$

质心是位置根据质量的加权平均值,对于连续的线段或区域,其质量和质心的公式如下,其中 \(\delta\) 是密度函数。

$$ M = \int_{a}^{b}\delta(x)dx,\ x_{cm} = \frac{1}{M}\int_{a}^{b}x\delta(x)dx \\ M = \int\int_{R}\delta(x, y)dA,\ x_{cm} = \frac{1}{M}\int\int_{R}x\delta(x, y)dA,\ y_{cm} = \frac{1}{M}\int\int_{R}y\delta(x, y)dA $$

二重积分的换元步骤:使用 \(u = u(x, y), v = v(x, y)\) 将 \(f(x, y)\) 替换为 \(g(u, v)\),使用 Jacobian 行列式得到由 \(dudv\) 表示的 \(dA\),根据区域 \(R\) 得到积分的上下限。面积 \(dA\) 的推导过程如下,求解 \(PQ\) 的 \(\Delta x\) 时,固定 \(v = v_{0}\) 不变,此时 \(x\) 可以看作关于 \(u\) 的单变量函数,\(\Delta x\) 就是 \(x\) 在 \(u\) 方向上的变化率(偏导)乘以 \(\Delta u\)。

$$ \frac{\partial(x, y)}{\partial(u, v)} = \left|\begin{matrix} x_{u} & x_{v} \\ y_{u} & y_{v} \end{matrix}\right|,\ dA = \left|\frac{\partial(x, y)}{\partial(u, v)}\right|dudv,\ \int\int_{R}f(x, y)dxdy = \int\int_{R}g(u, v)\left|\frac{\partial(x, y)}{\partial(u, v)}\right|dudv $$
$$ PQ = \Delta xi + \Delta yj \approx \left(\frac{\partial x}{\partial u}\right)_{0}\Delta u\mathbf{i} + \left(\frac{\partial y}{\partial u}\right)_{0}\Delta u\mathbf{j} \\ PR = \Delta xi + \Delta yj \approx \left(\frac{\partial x}{\partial v}\right)_{0}\Delta v\mathbf{i} + \left(\frac{\partial y}{\partial v}\right)_{0}\Delta v\mathbf{j} \\ \Delta A \approx \text{area of parallelogram PQRS} = |PQ \times PR| = \left|\begin{matrix} x_{u} & x_{v} \\ y_{u} & y_{v} \end{matrix}\right|_{0} \Delta u \Delta v \rightarrow dA = \left|\frac{\partial(x, y)}{\partial(u, v)}\right|dudv $$

有时根据 \(u = u(x, y), v = v(x, y)\) 求解 \(x = x(u, v), y = y(u, v)\) 比较困难,此时可以使用以下公式求解 \(\frac{\partial(x, y)}{\partial(u, v)}\)。如果区域 \(R\) 不是由 \(u, v\) 的等值线围成,那么积分的上下限就不是常数,此时需要找到边界关于 \(uv\) 的方程。

$$ \frac{\partial(x, y)}{\partial(u, v)}\frac{\partial(u, v)}{\partial(x, y)} = 1 $$

Part B: Vector Fields and Line Integrals