======Matrix-Vector Operations====== LAFF Week 3 Notes ---- 本章的核心概念主要在于理解矩阵与向量的乘法的意义。矩阵是一种线性变换(映射),那么向量通过变换得到的结果就是一个新的向量,形式上表现为**矩阵的列的线性组合**。\\ \\ 除此之外,本章还有大量内容关于矩阵的操作、矩阵向量乘法的操作,以及这些内容在计算机中实现,以及优化。 ====Special Matrices==== ===Partition Matrix into Quadrants=== 这一点值得在学习所有特殊矩阵之前提出来,因为相较于按列划分矩阵的方式 [[math:linear_algebra:laff:week_2#线性变换的验证方法|week2 note 2.1]],该划分方法贯穿了绝大多数的矩阵的操作(初始化,矩阵与向量的乘法等等)。我们来看看这种划分是如何进行的: \\ \\ 该方法的核心是将矩阵划分为大的四部分。为了算法设计的方便,又将该四大部分详细划分称了9部分,如下图所示: \\ \\
\\ \\ 下面用一个矩阵来作为示例。\\ \\ **第一步迭代**: \\ \\ 我们从左上角的 $A_{TL}$ 部分开始遍历。默认情况为 $A_{TL}$ 为没有任何元素。那么很显然,此时的$A_{BR} $ 包含了了所有的矩阵元素,也就是说,$A_{TR}$、$A_{BL}$ 都是没有任何元素的: \\ \\
\\ \\ 那么很显然,此时的,作为$A_{BR}$最左上角的一个元素, $a_{00}$ 就是划分图中的 $A_{11}$,也就是本次迭代过程中的 $A_{11}$。 \\ \\
\\ \\ 这里的 $A_{12}^T$ 实际上就是我们的 $A_{12}$。 因为根据上图,我们发现 $A_{12}$ 划分的区域实际上是一个行向量,因此将其写成 $A_{12}^T$。 **中间迭代**: \\ \\ 我们继续按上面的分块方法来划分矩阵,那么经过划分的 $A_{BR}$ 则有了新区域,伴随而来的是 $A_{11}$ 等区块又发生了新的改变,如下图: \\ \\
\\ \\ 而通过上述的中间迭代,我们可以很顺利的通过这样的迭代方式遍历整个矩阵。 \\ \\ 使用这种方式的优势在哪里?目前我们可以看到的是:这种分块的方式可以**直接对对角线上的元素进行操作**。这对于某些特殊矩阵的算法设计以及操作是非常便利的。 ===Zero Matrix=== 零矩阵代表了一种将所有输入向量统统映射到**原点**的线性变换。零矩阵中所有的元素都为 0,可以记作: \\ \\ $$ L_0(x) = 0 \,\, \text{for all x} \\ L_0 : \mathbb{R}^n \to \mathbb{R}^m \\ $$ \\ 如下的矩阵就是一种零矩阵: $$ \begin{pmatrix} 0 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \\ \end{pmatrix} $$ ==算法:初始化矩阵为零矩阵== {{ math:linear_algebra:laff:zeromatrix.png?600 |}} \\ \\ 这个算法的主要实现步骤: * 将矩阵按列划分 * 将每一列设置为 0 ===The Identity Matrix=== 单位矩阵代表了一种**不更改原有向量 / 矩阵**的线性变换。该矩阵的特点是以**左上**为起始位置的矩阵**对角线**上所有的元素为 $1$,矩阵其他部分均为 $0$。该矩阵可以用代数的形式表示为: \\ $$ L_I (x)=x \,\, \text{for every x} \in \mathbb{R}^n \\ $$ \\ 需要注意的是,单位矩阵必须是方阵。 \\ \\ 如下是一个单位矩阵的例子: $$ \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots &1 \\ \end{pmatrix} $$ ==算法:初始化矩阵为单位矩阵== {{ math:linear_algebra:laff:identitymatrix.png?600 |}} \\ \\ 该算法的主要内容如下: * 将矩阵从列与行两个方向上进行划分(也就是之前提到的象限划分法)。 * 在左上区域 $A_{TL}$ 的行数小于整个矩阵的行数之前,对矩阵对角线上的元素 $a_{11}$ 赋值 $1$,对其上下划分出来的(元素或者向量)进行赋 0 操作。迭代此操作,直到 $A_{TL}$ 的行数与 $A$ 的行数相等为止。 \\ ===Diagonal matrices=== 对角矩阵(//Diagonal matrices//)是一种除了主对角线之外其他元素皆为 0 的矩阵。也就是说,如果将该类矩阵按列分割表示,那么就有: \\ $$ \text{if} \,\, y = L_D(x) \,\, \text{then} \,\, y_{i} = e_ix_i $$ \\ 因为对角矩阵中只有主对角线上的元素不为 0,因此该矩阵的每列都可以表示成一个 unit basis vector 。因此目标向量 $y$ 的第 $i$ 个分量等于原向量 $x$ 的第 $i$ 个分量与矩阵中第 $i$ 列代表的 unit basis vector 的点积。如下是一个对角矩阵的例子: \\ $$ \begin{pmatrix} 5 & 0 & \cdots & 0 \\ 0 & 12 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots &17 \\ \end{pmatrix} $$ \\ 对角矩阵也必须是方阵。 ==算法:将矩阵初始化为对角矩阵== 该算法利用到了本章开头所讲述的矩阵的象限分割法;算法图如下: \\ \\ {{ math:linear_algebra:laff:diagonalmatrix.png?600 |}} \\ \\ 需要分割的部分除了矩阵外,还需从上到下的分割向量 $x$,使对角线上的元素等于对应的 $x$ 分量的值。 ===Triangular Matrices=== 三角矩阵 (Triangular Matrices)指其非零系数只在主对角线一侧的矩阵。 \\ \\ 三角矩阵存在着一些分支: * 按照非零系数的位置,又分为**上三角矩阵**与**下三角矩阵**。 * 如果三角矩阵的所有非零系数均为 1,那么称该三角矩阵为**单位三角矩阵** (Upper triangular Matrices)。 * 如果三角矩阵的主对角线也同时为 0,那么就称该三角矩阵为**严格三角矩阵**(Strictly triangular Matrices)。 \\ \\ 细致的代数定义如下: {{ math:linear_algebra:laff:3_5_2_part3.png?600 |}} 下面是三角矩阵的演示: \\ 上三角矩阵: $$ \begin{pmatrix} 5 & 3 & \cdots & 4 \\ 0 & 6 & \cdots & 2 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots &8 \\ \end{pmatrix} $$ 严格上三角矩阵: $$ \begin{pmatrix} 0 & 3 & \cdots & 4 \\ 0 & 0 & \cdots & 2 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots &0 \\ \end{pmatrix} $$ 单位三角矩阵: $$ \begin{pmatrix} 1 & 1 & \cdots & 1 \\ 0 & 1 & \cdots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots &1 \\ \end{pmatrix} $$ \\ 与之前对角矩阵相同,**三角矩阵也是方阵的一种**。 ==算法:初始化矩阵为三角矩阵== 初始化三角矩阵的具体操作根据不同的矩阵有不同的操作,但整体步骤是大致相同的: \\ \\ {{ math:linear_algebra:laff:3_2_4_5_picture.png?600 |}} \\ \\ 上面的算法是我们之前提到过的矩阵分割算法。我们只需要在每一个迭代中进行对应的赋值,就能得到对应的三角矩阵。来看看具体的操作: \\ \\ 对上三角矩阵,只需要在每次迭代中对 $A_{10}^T$ 或 $A_{21}$ 所代表的向量赋零即可,也就是: a10t = 0; %in row a21 = 0; %in col
\\ \\ 严格上三角矩阵只需对对角线元素,即 $A_{11}$ 赋零即可: a10t = 0; a11 = 0 ; //in row a21 = 0; a11 = 0; // in col 下三角矩阵只需将对角线全部赋值 1即可: a10t = 0; a11 = 1 ; //in row a21 = 0; a11 = 1; // in col 而下三角矩阵与上三角矩阵类似。相对于上三角矩阵,下三角矩阵对应的归零区域是 $A_{12}^T$(按行迭代)、$A_{01}$ (按列迭代),因此只需将之前上三角矩阵算法中的 $A_{10}^T$ 与 $A_{21}$ 分别替换成 $A_{12}^T$ 和 $A_{01}$ 即可: \\ \\
\\ \\ ===Transpose Matrix=== 转置矩阵(Transpose Matrix)在运算上表现为将**原矩阵的行作为新矩阵的列**而得到的矩阵。数学上的表现如下: {{ math:linear_algebra:laff:transpose.png?600 |}} \\ \\ 具体的例子可以参考下图: \\ \\
\\ \\ ==算法:求矩阵的转置矩阵== 求矩阵的转置矩阵就如上图所示,只需要按顺序将原矩阵中的行依次转换为新矩阵的列就可以。 \\ \\ {{ math:linear_algebra:laff:transpose_algo.png?600 |}} \\ \\ ==转置矩阵的性质== * 上下三角矩阵互为转置矩阵 * 单位矩阵的转置依然是单位矩阵 ===Symmetric Matrices=== 对称矩阵(Symmetric Matrices)是指原矩阵与目标矩阵相对于主对角线“对称”。数学上的定义如下: $$A \in \mathbb{R}^{n \times n} \\ \text{A is said to be symmetric if}\,\, A = A^T.$$ \\ {{ math:linear_algebra:laff:sy.png?600 |}} \\ \\ 根据定义,原矩阵必须要与其转置矩阵相等才能对称,因此可以判断原矩阵与其对称矩阵必为方阵。 ==算法:求三角矩阵的对称矩阵== 矩阵的对称矩阵是相对于主对角线对称的(转置)。也就是说 ,求三角矩阵的对称矩阵,只需要在每次迭代中将对应区域的元素进行转置即可。下面是求下三角矩阵的对称矩阵算法: \\ \\ {{ math:linear_algebra:laff:3.2.6.3_symmetrizepicture.png?600 |}} \\ \\ 每次迭代中,我们都将下三角矩阵中 $A_{10}^T$ 区域的值复制到 $A_{01}$中。但因为 $A_{10}^T$ 中的内容是行向量,因此我们需要将 $A_{10}^T$ 进行一次转置: a01 = (a10t)t; //row a12t = (a21)t; //col 下面是一个具体的实例图解: \\ \\
\\ \\ 上三角矩阵只需要将两者互换即可。 \\ \\ ====Operations with Matrices==== ===Scaling a Matrix=== 矩阵的缩放与向量的缩放是一样的。正式定义如下: >Let $L_A : \mathbb R^n \; \rightarrow \; \mathbb R^m$ be a linear transformation and, for all $x \in \mathbb R^n$, define $L_B : \mathbb R^n \; \rightarrow \; \mathbb R^m$ by $L_B(x)=\beta L_A(x)$ where $\beta$ is a scalar. ==矩阵缩放的性质== * $A$ 是对称矩阵,那么 $\beta A$ 也是对称矩阵,当 $\beta$ 为标量的时候。 * 第一条性质对三角矩阵,对角矩阵,转置矩阵均适用。 ===Adding matrices=== 矩阵的加法与向量相同。正式定义如下: >Let $L_A : \mathbb R^n \rightarrow \mathbb R^m$ and $L_B : \mathbb R^n \rightarrow \mathbb R^m$ both be linear transformations and $$ , for all $x \in \mathbb R^n$ , define the function $L_C: \mathbb R^n \rightarrow \mathbb R^m$ by $L_C(x) =L_A(x)+L_B(x)$ . ==算法:矩阵的加法== 非常简单的算法。只需要将矩阵进行或者列的分割,再对每一部分对应的分量相加即可。 ==矩阵加法的性质== * $A + B = B + A$ * $( A + B ) + C = A + ( B + C )$ * $ \gamma (A + B) = \gamma A + \gamma B$, $\gamma$ 为标量 * $ ( \beta + \gamma ) A = \beta A + \gamma A$ * $(A + B)^T = A ^ T + B ^ T$ * 若 $A、B$ 均为对称矩阵,那么 $A+B$ 也为对称矩阵,$\beta A + \gamma B$ 也为对称矩阵,即对称矩阵的任意线性组合也为对称矩阵。 ===矩阵与向量的乘法:点积解释=== 参考[[math:linear_algebra:laff:week_2#线性变换的验证方法|week2 note 2.1]],我们可以得到下面一个等式: $$ \begin{array}{r c l} A x & = & \left( \begin{array}{c c c c } \chi _{0} \alpha _{0,0} + \chi _{1} \alpha _{0,1} + \cdots + \chi _{n-1} \alpha _{0,n-1} \\ \chi _{0} \alpha _{1,0} + \chi _{1} \alpha _{1,1} + \cdots + \chi _{n-1} \alpha _{1,n-1} \\ \vdots \\ \chi _{0} \alpha _{m-1,0} + \chi _{1} \alpha _{m-1,1} + \cdots + \chi _{n-1} \alpha _{m-1,n-1} \end{array} \right) \\ & = & \left( \begin{array}{c c c c } \alpha _{0,0} & \alpha _{0,1} & \cdots & \alpha _{0,n-1} \\ \alpha _{1,0} & \alpha _{1,1} & \cdots & \alpha _{1,n-1} \\ \vdots & \vdots & & \vdots \\ \alpha _{m-1,0} & \alpha _{m-1,1} & \cdots & \alpha _{m-1,n-1} \\ \end{array} \right) \left( \begin{array}{c} \chi _0 \\ \chi _1 \\ \vdots \\ \chi _{n-1} \\ \end{array} \right) \end{array} $$ 如果我们仔细检查等式第一行的矩阵,我们会发现中间的每一行都是第二行公式中每一行与向量 $x$ 的点积的结果,即: \\ \\
\\ \\ 因此,我们可以从点积的角度归纳出,矩阵与向量 $x$ 的乘法的结果是一个向量 $y$,$y$ 上的每一个分量,等于对应矩阵的行,与向量 $x$ 的点积。因此不难得到点击角度下向量与矩阵乘法的算法: \\ \\ {{ math:linear_algebra:laff:mvmult_n_unb_var1.png?600 |}} \\ \\ 可以看出的是每次迭代的点积结果,都加到了对应的 $y$ 的分量上。实质上就是一个行优先的循环: for i = 0, i <= m -1, ++i for j = 0, j <= n-1, ++j yi += aij * xj ===矩阵与向量的乘法:Axpy解释=== 同样参考[[math:linear_algebra:laff:week_2#线性变换的验证方法|week2 note 2.1]],如果将矩阵按列分割,那么实际上矩阵与向量的乘积可以通过以下的途径计算: \\ \\ $$\begin{array}{r c l} A x \\ & =& \left( \begin{array}{c | c | c | c} a_0 & a_1 & \cdots & a_{n-1} \end{array} \right) \left( \begin{array}{c} \chi _0 \\ \chi _1 \\ \vdots \\ \chi _{n-1} \\ \end{array} \right) \\ & =& \chi _0 a_0 + \chi _1 a_1 + \cdots + \chi _{n-1} a_{n-1} \\ & = & \chi _0 \left( \begin{array}{c c c c } \alpha _{0,0} \\ \alpha _{1,0} \\ \vdots \\ \alpha _{m-1,0} \end{array} \right) + \chi _1 \left( \begin{array}{c c c c } \alpha _{0,1} \\ \alpha _{1,1} \\ \vdots \\ \alpha _{m-1,1} \end{array} \right) + \cdots + \chi _{n-1} \left( \begin{array}{c c c c } \alpha _{0,n-1} \\ \alpha _{1,n-1} \\ \vdots \\ \alpha _{m-1,n-1} \end{array} \right) \\ & \end{array}$$ \\ \\ 如果我们按列循环,那么每一次循环都可以视作 $x$ 的一个分量与矩阵 $A$ 对应的列的 AXPY 的操作。因此,从AXPY操作来设计矩阵与向量的乘法,我们可以得到如下的算法: \\ \\ {{ math:linear_algebra:laff:mvmult_n_unb_var2.png?600 |}} \\ \\ 该算法中的每个循环不再进行点积操作,而是进行AXPY操作,但得到的任然是一个向量;通过循环将这个向量累加到 $y$ 上,最终也可以得到矩阵与向量相乘的结果。其实质就是一个列优先的双重循环: for i = 0, i <= n -1, ++i for j = 0, j <= m-1, ++j yi += aij * xj ===参考资料=== * 本页面所有非 svg 图片来源于 LAFF 课件。